Introduction to C#Othello / Reversi

Have you ever played Othello? The Wikipedia has a nice article explaining the rules. It will probably remind you to other strategy board-games such as draughts (checkers) or the Chinese Go.

Download the example!

This example is very basic. It doesn't give weights to the different moves nor takes any strategies into account; it only calculates the available positions and the disks that must be flipped.

The player plays with the black disks and chooses one of the calculated available positions. The computer then does the same with its available positions, choosing one randomly.

Players are represented by a Boolean variable player or thisPlayer, which is false for blacks.

Attributes

The class Board has two constant attributes ROWS and COLS that allow us to change the dimensions of the board.

The positions of the squares and the information of the disk colour (or if the square is empty) is saved in an integer matrix board[ROWS, COLS]. Each element of that matrix stores:

  • -1 – if it is empty,
  • 0 – if it contains a black disk, and
  • 1 – if it contains a white disk.

Methods

The methods of the class Board are:

void opening(int i)
The different openings go here, only one is defined at the moment.
void printBoard() and void printBoard(int[,] moves)
Prints the board (the board matrix) to the console, with or without the available positions.
string index2letter(int i, int j)
The different openings go here, only one is defined at the moment.
int letter2index(string position, out int i, out int j)
Converts from algebraic notation to vector notation.
int[,] calculateMoves(Boolean thisPlayer, out int found)
Calculates the available squares for a player. Returns a matrix of ones and zeros, where the ones appear in the available positions.
int newTurn()
Launches a turn for each player. The variable noMorePos checks if both players have no more available positions, in which case the game is over.
void andTheWinnerIs()
Fancy way of disclosing the winner.

In the main class (Program) a Board is instantiated, and a loop of 32 turns is created.

Explanation of the search algorithm

Let's break the algorithm into small parts:

  • Searches for a disk of the opposite colour.
  • If nothing is found, found is set to zero and there are no available squares. We exit the method.
  • However, if a disk is found (in the position (i,j)), it scans the adjacent squares, represented by the indexes (m,n), where i-1 < m < i+1 and j-1 < n < j+1, and checks which are empty:
    Indexes (m, n) represent the adjacent squares of the position where the enemy's disk is placed, which are the positions that the payer's disk can occupy.
    (m, n) = (i-1, j-1) (m, n) = (i-1, j) (m, n) = (i-1, j+1)
    (m, n) = (i, j-1) i, j (m, n) = (i, j+1)
    (m, n) = (i+1, j-1) (m, n) = (i+1, j) (m, n) = (i+1, j+1)
  • If the square is not empty or we get out of the board limits, the loop jumps to the next (m,n) position.
  • If we aren't out and the square is empty, we advance in the direction marked by (m,n), to search a player's disk. The positions in the direction of advance are given by the pairs (k,l).
  • To implement the direction of advance, we calculate the sign of the unit increment so that it increases or decreases automatically in the vertical or horizontal direction as appropriate. The solution is deltam = i-m and deltan = j-n.

    (m, n) =
    (i-1, j-1)
    i, j
    (i+1, j+1)
    . . .

    Example:

    
    (i, j) = (2, 2) 
    (m, n) = (i-1, j-1) = (1, 1)
    deltam = i - m = 1
    deltan = j - n = 1
    					

    The first pair (k,l) will start searching in (i+deltam, j+deltan) = (3,3) and will continue incrementing in that direction.

    . . .
    (i-1,j)
    (i, j)
    (m, n) = (i+1, j)

    Example:

    
    (i, j) = (3, 4) 
    (m, n) = (i+1, j) = (4, 4)
    deltam = i - m = -1
    deltan = j - n =  0
    					

    The first pair (k,l) will start searching in (i+deltam, j+deltan) = (2,4) and will continue incrementing in that direction.

  • We calculate the following positions through the direction marked by the pair (m,n), which are given by (k,l), until we reach the end of the board or one of these three conditions is met:
    • An empty square is found. In this case, there is no point in continuing with the search, since we won't be able to capture an enemy's disk.
    • A square occupied by one of the players' disks. In that case, we will be able to capture the enemy's disks. Then, the pair (m,n) is added to the list of available positions and the found variable is incremented in one.
    • An enemy's disk is found. In this case, we continue searching until we find an empty square or a player's disk.

The algorithm to flip the disks is similar, but now the increments are deltam = m-i and deltan = n-j, and the indexes of the direction start in (k,l) = (m + deltam, n + deltan).

Can you improve this code? For example, how would you add weights for the available positions?
(Hint: You could try the Minimax algorithm)

Download the example!

Comments

Have any questions? Spotted any typos? Want to showcase what you did? Found a better solution? Your feedback and suggestions are welcome! And don't forget to share =)