Reversi

• Download source code - 57.8 KB

Introduction

This project is an implementation of the game Reversi with a simple artificial intelligence.

Background

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.
• HumanPlayer, ComputerPlayer – classes for the types of players available in the game for now. Inherit the Player class.
• 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

1. A new instance of the Game class is created, using an instance of the Board class;
2. The two players are created using the CreatePlayer1() and CreatePlayer2() methods of the Game instance;
3. The new game is started by the Start() method of the Game instance.
4. Player1 takes turn.
5. The StartMove() method of Player1 is called. The move ends when an element of the Board property of the game is set using the SetFieldColor() method.
6. If Player2 can move, Player2 takes turn. The same actions for Player2 are made, as for Player1 at the previous step.
7. If 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 MainForm class:

Game game = new Game(new Board());
game.CreatePlayer1(frmStartNewGame.Player1Properties);
game.CreatePlayer2(frmStartNewGame.Player2Properties);

this.ctrlBoard.SetGame(game);
game.Start();

The AI

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 MoveSolver class:

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); 
        // because it is a terminal state, its weight must be bigger than the heuristic ones
        if (result < 0)
        {
            addend = -addend;
        }
        return result + addend;
    }
    else
    {
        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.