first year reversi AI bot gets the W

#reversi #ai #minimax #c

Throwback to when we played Reversi/Othello in first year of engineering at the University of Toronto. But play it to win, automatically.

The Challenge

They told us to first code the board game interactions in C. If you haven’t played Reversi before, it's pretty simple. On a board (usually sized 8 by 8 tiles), there are black and white pieces. On your turn, you place a piece so that your opponent's pieces are between two of your pieces. The opposing pieces between yours get captured, and the goal is to have more pieces of your colour by the time there are no moves left.

In parts 1 and 2 of the lab, we code up the game interactions with variable board sizes, such as capturing pieces in multiple directions. The game is played in the terminal. We also code helper functions to find legal moves, make sure we're only playing legal moves, evaluate the number of pieces of each colour, etc. And use that to statically evaluate a position on an 8x8 board.

/* Basic functions */
bool inBounds(char board[][26], int n, int row, int col);
bool positionInBounds(int n, int row, int col);
void setupBoard(char board[][26], int n);
void printBoard(char board[][26], int n);
bool checkLegalInDirection(char board[][26], int n, int row, int col,
                           char colour, int deltaRow, int deltaCol);
bool isLegal(char board[][26], int n, int row, int col, char colour);
void enterMove(char board[][26], int n, char colour);
int flip(char board[][26], int n, int row, int col, char colour);
void copyBoard(char board[][26], char dupe[][26], int n);

Then the fun part: a leaderboard with bonus marks. Yeah that’s how I found out extra credit existed in university. But anyways we had to beat the 2 instructor bots (actual bots gg ez) and then our bot would be sent into the ring in round-robin format to rank on the course leaderboard.

How do you create a bot for a game you only learned 2 weeks earlier to dominate other UofT engineers? Well, i played chess before, but i didnt know reversi tech and they wouldnt tell us.

So off to the internet; I wasn’t trying to sweat it, but I dug deeper than I planned.

Algorithm & Heuristics

I used minimax with alpha-beta pruning to keep moves under 1s (one of the requirements).

With minimax, you score a future position (higher is better) depending on how favourable it is to you. Based on that score, you assume your opponent plays optimally for themself (minimum score), and you move backward from that future board state to the current state to determine which move to play that maximizes your own score.

In this position from YouTube “Algorithms Explained – minimax and alpha-beta pruning” by Sebastian Lague, black playing optimally would make a move that leads them to the best score for them, which would be 3, the smaller of 3 and 5.

You wouldn't need to optimize on such a small tree, but there are usually a lot of possible moves and each of those would have possible moves as you go deeper down the tree, a deeper tree meaning seeing further into the future for better accuracy. You cut redundant operations through alpha beta pruning: going down a branch, you keep track of the best score for each player (“alpha” for white, “beta” for black) and if playing a move leads to a branch that allows the opponent a more favourable score, you prune that branch.

In this example, because white can possibly get a score of 5, which is better than 3, we don’t bother with further evaluation because black does not want to give white the opportunity to get a higher score than 3.

The pseudocode for AB pruning looks like this:

if (isWhite) {
    best = INT_MIN;
    for (int r = 0; r < size && lo < hi; r++) {
      for (int c = 0; c < size && lo < hi; c++) {
        if (!isValidMove(grid, size, r, c, player)) continue;

        char copy[26][26];
        copyBoard(grid, copy, size);
        applyMove(copy, size, r, c, player);

        score = findBest(copy, size, (player == 'B') ? 'W' : 'B', outRow,
                         outCol, depth - 1, false, lo, hi);

        if (score > best) {
          best = score;
          if (depth == MAX_DEPTH) {
            *outRow = r;
            *outCol = c;
          }
        }
        if (score > lo) lo = score;
      }
    }
  } else {
    # opposite for black
  }

Static evaluation is more unique to the game itself. After tweaking, my bot valued tiles occupied, corners, and most importantly, available moves:

return TILES_WEIGHT * tiles_score(board, n) + 
       CORNER_WEIGHT * corner_score(board, n) + 
       MOBILITY_WEIGHT * mobility_score(board, n, turn) ;