Introduction
This is an implementation of the game Reversi, written in C#.
Background
I originally wrote this program as an exercise for learning C# and .NET programming in general. Reversi - or Othello as it is also known - is a popular game that is fun, requires just a few basic elements and has simple rules. This made it a good choice for learning a new programming environment.
The result was a fairly playable game but it lacked some of the more common features of computer board games, such as the ability to undo moves. So, having gained more experience with .NET, the time came for an upgrade. The result adds some new features and improves on the original graphics and AI.
Using the Code
Compile the source files and run the resulting Reversi.exe executable to play the game. You can play around with the various options and settings using the menu or toolbar. Try resizing the window, changing colors or switching sides with the computer in mid-game.
You may note that the program creates a file called Reversi.xml when you exit it. This file is used to save various settings such as game options, window size, and position and player statistics which are reloaded when the program is run again.
Help Files
A Windows help file is included with the source code. It can be found in the help files subdirectory within the archive. To make the help file available to the program, simply copy the Reversi.chm file from there to the directory where the Reversi.exe executable is located. You can run the program without it, but clicking the Help Topics option will display an error saying the file cannot be found.
All the source files used to create this help file are included in that subdirectory. You can edit and recompile it using the Microsoft HTML Help Workshop.
Points of Interest
The source is pretty well commented but some general overviews are in order.
Game AI
A good portion of the code is related to calculating moves for the computer player so it is worth discussing. The program uses a standard min-max look-ahead algorithm to determine the best move for the computer. Alpha-beta pruning is used to improve the efficiency of the look-ahead search. If you're not familiar with the min-max algorithm and/or alpha-beta pruning, a Google search will turn up plenty of information and examples.
Naturally, there are too many possible sequences of moves in the game to do an exhaustive look-ahead search, it would simply take too long to generate all possible move combinations. The exception is towards the end of a game where there are relatively few empty squares left - around ten or twelve. At this point, a complete search can be done and it is possible to find the move with the best possible outcome for a given player.
But in most cases, the look-ahead depth must be limited to a certain number of turns (based on the game's difficulty setting). So for each series of possible moves and counter-moves searched, the resulting game board must be evaluated to determine which player has the best chance of eventually winning the game. This evaluation is done by calculating a rank using the following criteria:
- forfeit - Leaving your opponent with no legal move forces her to forfeit her turn, giving you a big advantage in being able to move two (or more) times in a row.
- mobility - This is a measure of how many legal moves you can make vs. how many legal moves your opponent will be left with. Similar to forfeit, the idea is to reduce your opponent's options while maximizing your own.
- frontier - A frontier disc is one that is adjacent to an empty square. Having a large number of frontier discs will, generally speaking, give your opponent greater mobility on subsequent turns. Conversely, having fewer frontier discs means your opponent will have limited mobility later on. This score reflects the number of your frontier discs vs. your opponent's.
- stability - Corner discs are stable, they can never be outflanked. As a game progresses, other discs will become stable as well. This score reflects the number of your stable discs vs. your opponent's.
- score - This is simply the difference between the number of your discs on the board vs. your opponent's.
Different weights are assigned to each of these scores (again, based on the game's current difficulty setting). A board is assigned a rank by multiplying each criteria score by its corresponding weight and adding these values together. A large negative rank represents a board favorable to Black while a large positive rank represents a board favorable to White. So for a given set of possible moves, the computer will select one that results in the best ranked board for the color being played.
A constant named maxRank is used to indicate an end-game. It is set to the value of System.Int32.MaxValue - 64. This assures that any move resulting in the end of the game will always have a higher rank (negative or positive) than other moves.
Subtracting 64 from the system's maximum integer value allows us to add the final score to the rank so that a win by 10 discs will rank higher than a win by 2 discs. This causes the computer player to maximize its score when winning (or to minimize the opponent player's score when it's losing).
The current implementation is no match for the better AI players out there, but it plays pretty tough against a puny human opponent (at least, this puny human opponent). Again, a Google search will turn up plenty of resources describing strategies and AI approaches to the game.
Game Components
The Board Class
The Board class represents a game board. It uses a two-dimensional array to track the contents of each board square, which can be one of the following constant values defined in the class:
Black = -1
Empty = 0
White = 1
Two constructors are provided. One creates a new, empty board while the other creates a copy of an existing board.
It provides public methods like MakeMove() which adds a disc to the board, flipping over any outflanked opponent discs. For example, IsValidMove() can be used to determine if a given move is valid for a given player. HasAnyValidMove() returns false if the given player cannot make any legal moves.
It also tracks disc counts for each player which are used by the computer move AI routine. These counts include the total number of discs, the number of frontier discs and the number of safe (or unflippable discs) of each color.
Move Structures
In the main ReversiForm class, a couple of structures are defined for storing game moves. Both contain a row and column index pair which corresponds to a particular board square.
The ComputerMove struct is used for the computer AI. In addition to the move position, it has a rank member. This is used to track how good or bad the move is, as determined during the look-ahead search.
The MoveRecord struct is used for storing information about each move made during the course of a game. To allow the move undo/redo feature, an array of these is kept to track the board during each turn. A move record contains a Board representing the game board as it was before the particular move was made, as well as value indicating which player is to make the next move. An array of these is kept as moves are made by each player, allowing the game to reset to the state it was in at any point in the move history.
The RestoreGameAt() method handles the resetting of the game to a particular move number. While it potentially allows the game to be restored to any move currently in the history, the menu and tool bar options on the main form currently only provide for a single move undo/redo at a time or an undo/redo of all moves. A future enhancement might be to allow the user to click on items in the move list to restore the game to the corresponding move number.
Graphics and the User Interface
The Game Board
Squares on the board are represented by a user control named SquareControl. There is one of these for every square on the game board display. The control contains information for displaying the square and its contents (empty or a black or white disc) including the animation of discs and any highlighting.
Displaying the Discs
Each disc is drawn dynamically. The basic shape is a circle with some highlighting and a shadow to give it a pseudo-3D appearance. The shapes are scaled in size based on the current size of the square control. By rendering them this way, instead of using static images, the board may be dynamically resized to fit within the form window.
The Click event on the square controls handled within ReversiForm allows the user to make a move to a particular square (assuming it's a legal move). Likewise, the MouseMove and MouseLeave events are handled to update the board display to highlight valid moves or preview a move when those options are active.
Animation of Moves
The disc flip animation is done using counters defined within the SquareControl class along with a System.Windows.Forms.Timer. Basically, this is a thread controlled by the operating system which periodically raises an event that your form application can respond to.
After a move is made, if the move animation option is active, each affected square control has its counter initialized and the timer is activated. The main form's AnimateMove() method is called each time the timer ticks (see below). This method updates the square counters and redraws their display. The animation basically consists of changing the disc shape from a circle to ever thinner ellipses, then back to a full circle but in the opposite color. The smoothness and speed of this animation depends on how large the initial counter value is (set by the constant SquareControl.AnimationStart) and how often the timer ticks (set by the constant animationTimerInterval in the main form).
Game Play
The following variables are used to handle play during a game:
private GameState gameState;
private int currentColor;
private int moveNumber;
moveNumber should be self-explanatory. currentColor indicates which player has the current turn (Black or White). gameState is set to one of these enumerated values:
private enum GameState
{
GameOver,
InMoveAnimation,
InPlayerMove,
InComputerMove,
MoveCompleted
}
Most of the game play is event driven, so the use of gameState allows the various event handlers to determine the proper actions to take. For example, when the user clicks on a board square, SquareControl_Click() is called. If the game state is InPlayerMove, the move will be made on that square. But if the game is in some other state, it's not the user's turn to move so the click is ignored.
Likewise, if the user clicks the tool bar "Undo Move" button, we want to check the game state to see if any thing needs to be done before resetting the game to the previous move. For example, if the state is InMoveAnimation, the animation timer needs to be stopped and the square controls need their counters and display reset. Or if the state is InComputerMove, the program is currently doing a look-ahead search in a separate thread (see below) which will need to be stopped.
Program Flow
The diagram below illustrates the general program flow during the course of a game:
StartTurn() gets called at the beginning of a game, after a move is made by either player and whenever a move undo or redo is performed. It is responsible for evaluating the game situation and setting up for the next move.
It first checks to see if the current player can make a legal move. If not, it switches to the other player and checks if that player has any legal move. When neither player can make a move, by rule, the game is over and it will end the game.
Otherwise, the function will set things up for the current player to make a move. If the current player is under user-control, it simply exits. The user can then make a move by clicking the mouse pointer on a valid square or by typing in a valid column letter and row number. This results in a call to MakePlayerMove() which does some housekeeping and then calls MakeMove() to perform the move. If the current player is under computer-control, it starts the look-ahead search to find the best move.
Using a Worker Thread
Because the look-ahead search is computationally intensive, it is performed in a worker thread. It this were not done, the main form would freeze and become unresponsive during the time it takes for the computer to calculate its best move. So StartTurn() creates a worker thread to execute the CalculateComputerMove() method and starts it.
A lock is used on the main game board object to prevent race conditions. As an example, both the MakeComputerMove() and the UndoMove() methods change to the game board. Both methods first attempt to put a lock on it. So if one method happen to be called while the other is in the middle of updating the board, it will be forced to wait until those changes are completed and the lock is freed.
Once a move has been found, the CalculateComputerMove() method does a callback to run MakeComputerMove() in the main form. This method gets a lock on the board and calls MakeMove() to perform the move.
Performing a Move
MakeMove() does the actual updating of the board, placing the new disc at the specified location. It also does some maintenance on the undo/redo move history and removes any square highlighting.
Then, if the move animation option is turned off, it simply calls EndMove() which will switch currentColor and start the next turn with a call to StartTurn().
But if the animate option is on, it will instead initialize the discs to be animated and start the animation timer. As discussed previously, the timer causes AnimateMove() to run every few milliseconds, updating the display and decrementing the animation counters each time. Eventually, the counters will reach their end and AnimateMove() will then call EndMove() to complete the move.
Future Enhancements
There is much room for improvement in the computer-player AI. The look-ahead algorithm could be augmented with a book of opening moves or a set of corner and edge patterns that have been pre-ranked. It could be made to utilize selective deepening, where the search depth could be extended for moves that generally have more impact on the game, such as near the corners. Another improvement would be to store the look-ahead tree. This would allow it to be searched to a greater depth because the program would not have to regenerate the same moves each time.
History
- August 1, 2003 - version 1.0
- September 16, 2005 - version 2.0
- Enhanced graphical display.
- Added unlimited move undo/redo.
- Improved computer player AI.
- Corrected threading issues.
- Expanded help.
