15,742,764 members
Articles / Artificial Intelligence
Article
Posted 18 Mar 2008

83.4K views
46 bookmarked

# Reversi

Rate me:
An implementation of the popular game Reversi, written as a project for an AI course.

## 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:

C#
```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:

C#
```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)
{
}
}
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.

Written By
Bulgaria
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 My vote of 5 KrirkDev 13-Dec-22 14:59 KrirkDev 13-Dec-22 14:59
 Thank you Member 948714218-Dec-12 3:14 Member 9487142 18-Dec-12 3:14
 reversi blow 'em out12-Jul-10 3:08 blow 'em out 12-Jul-10 3:08
 My vote of 1 geniaz110-Feb-10 7:24 geniaz1 10-Feb-10 7:24
 Very small bug ? Kestutis21-Jul-08 23:48 Kestutis 21-Jul-08 23:48
 Nice, but there is missing text... marco_br18-Mar-08 7:00 marco_br 18-Mar-08 7:00
 Nice article, but, in the first paragraph of "The AI" section (before the code snippet), there is missing text (the sentence ends in "the...").
 Re: Nice, but there is missing text... Zdravko Krustev18-Mar-08 7:17 Zdravko Krustev 18-Mar-08 7:17
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Sep-23 18:31 Refresh 1