This project is an implementation of the game Reversi with a simple artificial intelligence.
I had an assignment to write an artificial intelligence for the game Reversi, using the alpha-beta pruning algorithm. The assignment was a part of the AI course that I studied at the Sofia University, Faculty of Mathematics and Informatics. And here is the result.
Using the code
The project consists of several classes implementing the inner structure of the game, and several controls and forms for the user interface.
The classes, according to their functionality, are:
DiscColor - represents the possible colors of discs on the board: Black, White, and None – the field of the board is empty.
Board - implements a two-dimensional array, with each element representing a field of the game board (with a
DiscColor). The class provides some methods for determining whether a player can make a move at a specified position, for making the move, and for converting the opponent disks, etc.
Game - provides the whole process of playing: setting the properties of the players, starting a new game, switching between players, and completion of the game. An instance of the
Game class is created with an instance of the
Board class (like in the real world – to play a game, you must have a board first).
PlayerProperties – as you can guess, this class describes the properties of each player in the game. Players for a specific game are created by the
CreatePlayer1(PlayerProperties properties) and
CreatePlayer2(PlayerProperties properties) methods of the
Game class. The
PlayerProperties class supports serialization, and properties for the two players are stored in a configuration file as described below. This allows the next game to be played with the same players' properties.
Player – abstract class that provides the basic functionality of a player in the game. The
Type property of the class indicates the player type, and the
StartMove() method allows to add some functionality in the derived class that is executed when the player starts a new move.
ComputerPlayer – classes for the types of players available in the game for now. Inherit the
MoveSolver – provides the AI for a computer player.
The forms and controls are the following:
BoardFieldControl – represents a field of the game board. When a player can make a move on the specified field, it’s shown highlighted.
PlayerInfoControl – displays information about a specified player – name, type, color, disc on board.
BoardControl – this control provides the whole look of the game – a board, and information panes about the players and the result.
PlayerPropertiesControl – allows a user to choose the properties of a player at the beginning of a new game.
StartNewGameForm – as it is obvious, in this form, you enter the information needed to start a new game. The properties of the two players are stored in a configuration file named “PlayersInfo”, and the
StartNewGameForm initializes its fields from this file on load. Respectively, it stores them back there when the “OK” button is clicked.
MainForm – contains one
BoardControl, and calls a
StartNewGameForm when loaded.
Process of playing the game
- A new instance of the
Game class is created, using an instance of the
- The two players are created using the
CreatePlayer2() methods of the
- The new game is started by the
Start() method of the
Player1 takes turn.
StartMove() method of
Player1 is called. The move ends when an element of the
Board property of the game is set using the
Player2 can move,
Player2 takes turn. The same actions for
Player2 are made, as for
Player1 at the previous step.
Player1 can move,
Player1 takes turn.
Steps 5-7 are repeated until none of the players could make his move. The game is over then, and the
Finished event of the
Game is raised.
The process of creating a new game could be seen in the
StartNewGame() method of the
Game game = new Game(new Board());
Since it is a project for an AI course, the AI should be the most important part of it. As mentioned above, the program uses the alpha-beta pruning algorithm to achieve victory. As you know, the creation of the whole search tree (containing all possible moves from the beginning till the end of the game) needs a lot of memory. That’s why, when reaching at a specified depth in the search tree, the current node is being evaluated using a heuristic function. This happens in the following method of the
private int EvaluateBoard(Board board)
DiscColor color = this.Player.Color;
DiscColor oppositeColor = DiscColor.GetOpposite(this.Player.Color);
List<int> oppositePlayerPossibleMoves = this.GetPossibleMoves(board, oppositeColor);
List<int> possibleMoves = this.GetPossibleMoves(board, color);
if ((possibleMoves.Count == 0) && (oppositePlayerPossibleMoves.Count == 0))
int result = board.GetDiscsCount(color) - board.GetDiscsCount(oppositeColor);
int addend = (int)Math.Pow(board.Size, 4) + (int)Math.Pow(board.Size, 3);
if (result < 0)
addend = -addend;
return result + addend;
int mobility = this.GetPossibleConvertions(board, color, possibleMoves)
- this.GetPossibleConvertions(board, oppositeColor, oppositePlayerPossibleMoves);
int stability = (this.GetStableDiscsCount(board, color)
- this.GetStableDiscsCount(board, oppositeColor)) * board.Size * 2 / 3;
return mobility + stability;
As you can see (if you tried to figure out what this code really does), the heuristic value for the specified node (the
board parameter represents the whole board at the current state of the game) is formed using two criterions – stability (the number of stable discs on the player's board) and mobility (number of opponent disks that could be converted). The final value is evaluated using some "magical numbers" as coefficients. These coefficients are inspired by some tests I have made, and do not have any "reasonable" explanation.
If the current node is a leaf, this means that we are at the end of the game and could easily see if the state is winning or not. Just subtract the number of opponent discs from the number of the player's discs, and add a quite big number (positive or negative) so the result will be grater than any heuristic valuation made at the same depth in the search tree. That is because the valuation at the end of the game is surely correct and is more important than any heuristic valuation we have made.