Reversi Meng Tran – [email protected] Faculty Advisor: Dr. Barry Silverman Abstract: The game of Reversi was invented around 1880 by two Englishmen, Lewis Waterman and John W. Mollett. It later became incredibly popular when Mattel produced the game Reversi under the name Othello. Now the game of Reversi is also known as Othello. It took its name from Shakespeare’s play Othello probably referencing the conflict between the Moor Othello and Iago. Since 1978 there has been a World Othello Championship. The current reigning champion is Hideshi Tamenori from Japan. Rules: The game is played on an 8 by 8 board. The board can be bigger but it is usually 8 by 8 for a standard game. The game starts with 4 pieces of each color already on the board.White pieces are placed on D4 and E5 while black pieces are on E4 and D5. Black always goes first. It is up to the players to decide who will be black. Here Black plays on E6, which flanks the original white piece on E5 making it switch colors. Each player alternately takes turns. Each player must make a move whether they want to or not so each player is forced to move if there are any valid moves. Every piece that is flanked by the opponent’s piece on both sides switches colors. This is in every direction, horizontal, vertical and diagonal. This continues until all the places have been filled or neither player can make a move. The winner is the player who has a higher piece count than the other person. Therefore there are three outcomes to the game, you can win, lose or draw. Strategies: Reversi is a zero-sum game with perfect information and ends in a finite number of moves. Since all of the pieces are on the board andyou can perform a look-a-head to figure out if you win or lose, this is the perfect game for a computer to play. The rules are fairly simple, much simpler than chess and Go. Therefore a computer performing look-a-heads on every move can theoretical play perfectly all the time. Corners: Probably the most important strategy in the game is to capture the corners. With the corners, you can flank your opponent’s pieces on the edges or through the whole diagonal of the board. Plus you gain the advantage of staying alive as these corners can not be flanked. Therefore the squares around the corner are dangerous if you play into them. This gives the opponent an opportunity to grab a corner gaining the advantage. Edges: Edges are rows 1 and 8 and columns A and H that are not corners. Edges are important as well as it gives you the most potential in gaining more pieces across the board. You can use an edge piece to flank a whole row gaining 8 more pieces on the board. Also edge pieces can only flank other pieces therefore it is the second safest spots behind corners. Mobility: One of the best strategies that are hard to pull off is to limit your opponents move until they have no moves left and must forfeit a turn. This requires extensive look-a-head and usually requires you todominate one side of the board along the edge. Once this is achieved you have gained an extra turn therefore more opportunities to flip more pieces to your advantage. Endgame: This is the end of the game when there are about 8 to 12 pieces left to play. This is probably the most important part of the game as a good play can result in a win even though the player has been losing throughout the game. Looking ahead is very simple at this point as there are fewer squares to consider. Anybody can look-a-head a few pieces quite easily. Look ahead is a strategy itself as it is the best known strategy to find the best move for a perfect game. Related Work: There have been many computer programs that play Reversi ever since its popularity in the 1980s. The best known program to date is Logistello which beat the reigning human champion, Takeshi Murakami in Reversi in 1997 in a 6 to 0 sweeping win. Although the look-ahead strategy can almost guarantee a win in Reversi, the computations that are required for checking the moves are intense. Reversi has also not been mathematical solved making it a non-trivial game. There have been numerous others both for research purposes in human decision making and tools for teaching. Games are fairly popular as tools for teaching students how to program. Chess rulesare simply too complicated to program and the artificial intelligence for even a decent program requires many strategies and tactics. Each chess piece also has a different type of move and each play has a different weight depending on the piece that occupies it. Tic-tac-toe is simply too easy. Although it is a fairly good game to start, you can not extend the game beyond a beginner’s course. Reversi is just the right game as a teaching tool for anybody learning a new programming language or learning about artificial intelligence in general. Technical Approach: I have used Microsoft’s .NET C# programming language for Reversi’s game rules and framework. I chose C# because it is fairly easy to use and it wouldn’t take up much time creating the environment. Plus the graphics are the easiest to work with out of all the other programming languages. Not to mention the programming environment is probably the best. This gave me the advantage to quickly setup the game and work on the artificial intelligence side. For the artificial intelligence engine, I considered using Python since Python has been used fairly extensively in artificial intelligence research. Using Python in conjunction with C# would’ve been a fairly easy task. Although it would’ve been simple to use Python, there was always the risk of compatibility. I was also not as skillful inprogramming with Python. So I made the decision to make everything in C#. This would allow for smoother transitions between player and computer. Since I didn’t have to worry about converting data objects between the two languages, the program would run a bit faster. Representation: Representing the Reversi board was a fairly easy task as well. The game is already a matrix and all the information was available right on the board. It was either empty or had a stone of either color. I just used a matrix and represented the white stones as 1 and the black stones as -1. The empty positions were 0. Rules: The rules were fairly complicated to program, but it was doable. First it must be an empty position or else it’s not a valid move since