AI implementation for Owaré (Part 2)

Hellooo, this article is the continuation of another which introduces the concepts needed to understand the code presented here. If you haven’t already, I urge you to do so, at the risk of missing out on all that’s going on here.

Jeu d’awalé

Implementing the simulator in Dart

Why Dart? Firstly, because it’s a simple language that’s easy for everyone to understand, and quite similar to Javascript. Secondly, because it will be easier to integrate later into a mobile game made with Flutter & Flame 😁.

When it comes to implementation, we’re not all equal, and what’s more, we don’t all have the same tastes. The implementation I propose here is not intended to be the best, if you find a better implementation I’d be happy for you to share it with me 😊.

Game state class

Let’s start this programming journey with the class associated with the game state. I’ve deliberately chosen not to use a real matrix to implement the board here, to improve readability and facilitate debugging. You can use a matrix of your own if you wish.

class GameState {
  List<int> p1pad;
  List<int> p2pad;
  int p1points;
  int p2points;
  GameState({
    required this.p1pad,
    required this.p2pad,
    required this.p1points,
    required this.p2points,
  });

p1pad represents the first row of the matrix, p2pad represents the second row. The points of players 1 and 2 are respectively p1points and p2points. We enumerate our players, defining their associated types:

enum GamePlayer {
  p1,
  p2,
}

Tadaaaa! our evaluation function can take shape:

int evaluate([GamePlayer mainPlayer = GamePlayer.p1]) {
    int v1 = p1pad.where((p) => p == 1 || p == 2).length;
    int v2 = p2pad.where((p) => p == 1 || p == 2).length;
    switch (mainPlayer) {
      case GamePlayer.p1:
        return (2 * p2points + v1) - (2 * p1points + v2);
      case GamePlayer.p2:
        return (2 * p1points + v2) - (2 * p2points + v1);
    }
  }

If you’ve understood the formula, the code shouldn’t bother you — it’s its implementation in its most naive form.

I’ll spare you the scrolling and just give you the formula.

And the delta 😁

A little detour before simulation

Before we can write our simulation function, we’re going to write the class that will enable us to manage our “circular” matrix. In order to make the various conversions between the vector and the state matrix.

class CircularMatrix {
  List<int> buffer; 
  int rowLength;

CircularMatrix({
    required this.buffer,
    required this.rowLength,
  });
}

Buffer represents the vector, and rowLength represents N, the width of the row, the number of squares per player. Forgive my old system programmer’s lexicon. 😞

We give the constructor that builds the vector from the two rows of the matrix:

factory CircularMatrix.from2Rows(List<int> row0, List<int> row1) {
    if (row0.length != row1.length) {
      throw Exception("Les lignes n'ont pas pas la même taille");
    }
    int rowLength = row0.length;
    return CircularMatrix(buffer: [
      ...row1,
      ...row0.reversed,
    ], rowLength: rowLength);
  }

We check that the 2 rows have the same number of columns, and calculate the vector, which is nothing more than a list with the second row of the matrix as its elements, followed by the first row of the matrix inverted. Then you need to convert the matrix indices into vector indices:

int getCircularIndex(int row, int index) {
    if (index < 0 || index > rowLength) {
      throw Exception("Indexation en déhors des limites");
    }
    return row == 1 ? index : 2 * rowLength - 1 - index;
  }

For each row and column of the matrix, return the index of the corresponding vector. The formula is slightly different here because the indices start from 0 , instead of 1. I’ll quickly explain how to find these expressions.

Let’s recall the formula:

We’ll keep the first line:

Let’s frame the indices:

Let’s set the variables k and l, which represent indices i and j respectively, but which start from 0:

I’ve added (-1) to the last expression so that the result is between N and 2N-1 instead of N+1 and 2N, since the vector indices also start from zero. After performing the subsitutions, we found the same formulas as in the code:

This method is used to switch between vector and matrix indices:

List<int> getMatrixIndex(int circularIndex) {
    if (circularIndex >= 0 && circularIndex < rowLength) {
      return [1, circularIndex];
    } else {
      return [0, 2 * rowLength - 1 - circularIndex];
    }
  }

By applying the same change of variable, we can easily find these expressions too. From the vector, it’s also possible to retrieve the rows of our matrix. No formulas this time, I promise!

/// Retourne la seconde ligne de la matrice
  /// (celle du bas)
  List<int> getRow1() {
    return buffer.sublist(0, rowLength);
  }

/// Retourne la première ligne de la matrice
  /// (celle du haut)
  List<int> getRow0() {
    return buffer.sublist(rowLength, 2 * rowLength).reversed.toList();
  }

getRow0 returns the first line, and getRow1 returns the second one. The second line must be reversed, and you should know why if you’ve made it this far in the reading 😉

Now that we’ve got everything we need, we can calmly move on to implementing our simulation.

Seed distribution implementation

We implement the seed distribution algorithm in the game state class as follows:

/// Performs a game for the [player] at the [cavityIndex] location
  /// On a game with circular matrix [circularMatrix]
  /// And returns the last location
  int _distributeHand(
    CircularMatrix circularMatrix,
    GamePlayer player,
    int cavityIndex,
  ) {
    int row = player == GamePlayer.p1 ? 0 : 1;
    int startIndex = circularMatrix.getCircularIndex(row, cavityIndex);
    int hand = circularMatrix.buffer[startIndex];
    circularMatrix.buffer[startIndex] = 0;
    int index = startIndex;
// Distribute the hand skipping the start case
    while (hand != 0) {
      index = (index + 1) % circularMatrix.buffer.length;
      if (index != startIndex) {
        circularMatrix.buffer[index]++;
        hand--;
      }
    }
    return index;
  }

The algorithm receives the circular matrix, the player who is playing and the index, the number of the square from which he is playing. It begins by determining the index of the game vector, then the algorithm runs as described above.

Implementing seed harvest

The code is a little naughtier to look at:

/// Determine the winnings of the player who played, based on the last index [lastIndex] and
  /// the last row [lastRow].
  /// And returns a list with
  /// [0] => player 1's winnings
  /// [1] => player 2's winnings
  List<int> _computeGains(
    CircularMatrix circularMatrix,
    GamePlayer player,
    int lastCircularIndex,
  ) {
    int index = lastCircularIndex;
    final [lastRow, _] = circularMatrix.getMatrixIndex(lastCircularIndex);
    int gains = 0;
// returns true if the position is winning
    isGaining(int idx) =>
        circularMatrix.buffer[idx] == 2 || circularMatrix.buffer[idx] == 3;
    // Does the first player finish on the second player's zone?
    bool isPlayer1Jackpot = player == GamePlayer.p1 && lastRow == 1;
    // Does the second player finish on the first player's zone?
    bool isPlayer2Jackpot = player == GamePlayer.p2 && lastRow == 0;
    if (!isPlayer1Jackpot && !isPlayer2Jackpot) {
      return [0, 0];
    }
    bool sameRow = true;
    bool gaining = true;
    do {
      final [row, _] = circularMatrix.getMatrixIndex(index);
      sameRow = row == lastRow;
      gaining = isGaining(index);
      if (sameRow && gaining) {
        gains += circularMatrix.buffer[index];
        circularMatrix.buffer[index] = 0;
        --index;
        if (index < 0) {
          // if you exit at the beginning, you return to the end
          index = circularMatrix.buffer.length - 1;
        }
      }
    } while (sameRow && gaining);
    return [
      isPlayer1Jackpot ? gains : 0,
      isPlayer2Jackpot ? gains : 0,
    ];
  }

I hope the comments will help you to better understand the rest of the algorithm we’ve already seen above.

Implementing the simulation function

GameState simulate(GamePlayer player, int cavityIndex) {
    CircularMatrix circularMatrix = CircularMatrix.from2Rows(p1pad, p2pad);
    int lastCircularIndex =
        _distributeHand(circularMatrix, player, cavityIndex);
    final [p1gains, p2gains] =
        _computeGains(circularMatrix, player, lastCircularIndex);
    return GameState(
      p1pad: circularMatrix.getRow0(),
      p2pad: circularMatrix.getRow1(),
      p1points: p1points + p1gains,
      p2points: p2points + p2gains,
    );
  }

Implementing the Alpha Beta algorithm

Now that we’ve got our heuristics correctly implemented, we can get down to implementing the MinMax search coupled with the Alpha Beta hack, so that our computer can intelligently play Awalé with us.

We start by creating a class that will contain the AI parameters:

const __infinty = 0xFFFFFFFF;
const __invalidMove = -100; 

class AlphaBetaContext {
  GameState currentState;
  GamePlayer mainPlayer;
  int maxDepth;
  AlphaBetaContext({
    required this.currentState,
    required this.mainPlayer,
    required this.maxDepth,
  });

Two constants are defined:

• The first symbolizes the infinity required for the MinMax to function, I personally chose the max value that can be had on 32 bits, I doubt you’ll ever need to make evaluation functions that return values > 2³²- 1 even if you’re making an AI for chess. 😅
• The second is used to represent a movement, an invalid game, which is useful for our MinMax implementation.

Then we define the AI parameters:

• The current state of the game
• The main player, the one controlled by the AI
• The depth of the MinMax search tree.

Wait a little bit !

Before we can implement the search algorithms, and their nasty mutual recursivity, we need a method at game state level that returns the possible games for a player relative to the current state. Each possible game is represented by each non-empty square in front of the relevant player.

  List<int> getAvailableMoves(GamePlayer player) {
    if (player == GamePlayer.p1) {
      return List.generate(p1pad.length, (index) => index)
          .where((index) => p1pad[index] > 0)
          .toList();
    } else {
      return List.generate(p2pad.length, (index) => index)
          .where((index) => p2pad[index] > 0)
          .toList();
    }
  }

We just return the playable indexes, for the given current player.

Implementing the Alpha Beta algorithm

Now for the holy grail: the search algorithms.

The minimum

/// Min-max algorithm coupled with alpha-beta hack
  /// [state] is the current state of the game
  /// [depth] is the depth
  /// [alpha] is the alpha parameter
  /// [beta] is the beta parameter
  List<int> _min(GameState state, int depth, int alpha, int beta, int moveNo) {
    int bestMoveValue = __infinty;
    int bestMoveId = __invalidMove;
    List<int> availableMoves = getAvailableMoves(state, mainPlayer);
    if (depth == maxDepth || availableMoves.isEmpty) {
      return [moveNo, state.evaluate(mainPlayer)];
    }
    for (int move in availableMoves) {
      GameState simulated = state.simulate(mainPlayer, move);
      final [_, moveValue] = _max(simulated, depth + 1, alpha, beta, move);
      if (moveValue < bestMoveValue) {
        bestMoveValue = moveValue;
        bestMoveId = move;
      }
      beta = min(beta, bestMoveValue);
      if (beta <= alpha) {
        // hack: alpha beta pruning
        break;
      }
    }
    return [bestMoveId, bestMoveValue];
  }

The maximum

/// Min-max algorithm coupled with alpha-beta hack
  /// [state] is the current state of the game
  /// [depth] is the depth
  /// [alpha] is the alpha parameter
  /// [beta] is the beta parameter
List<int> _max(GameState state, int depth, int alpha, int beta, int moveNo) {
    int bestMoveValue = -__infinty;
    int bestMoveId = __invalidMove;
    GamePlayer oppositePlayer = _opposite(mainPlayer);
    List<int> availableMoves = getAvailableMoves(state, oppositePlayer);
    if (depth == maxDepth || availableMoves.isEmpty) {
      return [moveNo, state.evaluate(mainPlayer)];
    }
    for (int move in availableMoves) {
      GameState simulated = state.simulate(oppositePlayer, move);
      final [_, moveValue] = _min(simulated, depth + 1, alpha, beta, move);
      if (moveValue > bestMoveValue) {
        bestMoveValue = moveValue;
        bestMoveId = move;
      }
      alpha = max(alpha, bestMoveValue);
      if (beta <= alpha) {
        // hack: alpha beta pruning
        break;
      }
    }
    return [bestMoveId, bestMoveValue];
  }

  int guessBestMove() {
    final [move, _] =
        _min(currentState, 0, -__infinty, __infinty, __invalidMove);
    return move;
  }

The other methods

  GamePlayer _opposite(GamePlayer player) {
    return player == GamePlayer.p1 ? GamePlayer.p2 : GamePlayer.p1;
  }

  List<int> getAvailableMoves(GameState state, GamePlayer player) {
    List<int> moves = state.getAvailableMoves(player);
    return moves;
  }

If you’re familiar with Alpha Beta algorithms, this code shouldn’t scare you. You should be familiar with the mutual recursion used here, which makes it all rather intimidating.

Can we play now?

Congratulations if you’ve made it this far, you’ve earned yourself a little main() function that will let you play quietly against your computer:

void displayGameState(GameState state) {
  final table0 = Table();
  for (var c in List.generate(state.p1pad.length, (index) => "($index)")) {
    table0.insertColumn(header: c);
  }
  table0.insertColumn(header: "P");
  table0.insertRows([
    [...state.p1pad, "p1"],
    [...state.p2pad, "p2"],
  ]);
print(table0);
  final table1 = Table()
    ..insertColumn(header: "Gains p1")
    ..insertColumn(header: "Gains p2")
    ..insertRow([state.p1points, state.p2points]);
  print(table1);
}

void main(List<String> arguments) {
  final cl = Console();
  cl.clearScreen();
  print("Welcome to the awale simulator");
  GameState state = GameState.start(6);
  GamePlayer player = GamePlayer.p2;
  GamePlayer opposite = player == GamePlayer.p2 ? GamePlayer.p1 : GamePlayer.p2;
  while (true) {
    displayGameState(state);
    print(
        "\r [${player.name}] Select a box [0-${state.p1pad.length - 1}] (-1 to quit) : ");
    int move = int.parse(cl.readLine() ?? '0');
    if (move == -1) {
      break;
    }
    state = state.simulate(player, move);
    AlphaBetaContext aiContext = AlphaBetaContext(
      currentState: state,
      mainPlayer: opposite,
      maxDepth: 10,
    );
    int bestAIMove = aiContext.guessBestMove();
    print("The AI plays square N°°$bestAIMove !");
    state = state.simulate(opposite, bestAIMove);
  }
}

The result

Welcome to the awale simulator:
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 4   │ 4   │ 4   │ 4   │ 4   │ 4   │ p1 │
│ 4   │ 4   │ 4   │ 4   │ 4   │ 4   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 0        │ 0        │
╰──────────┴──────────╯
 [p2] Select a box [0-5] (-1 to quit) : 
0
The AI plays square N°5 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 4   │ 5   │ 5   │ 5   │ 5   │ 0   │ p1 │
│ 0   │ 5   │ 5   │ 5   │ 5   │ 4   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 0        │ 0        │
╰──────────┴──────────╯
 [p2] Choisissez une case [0-5] (-1 to quit) : 
2
The AI plays square N°5 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 4   │ 5   │ 5   │ 5   │ 7   │ 0   │ p1 │
│ 0   │ 5   │ 0   │ 6   │ 6   │ 5   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 0        │ 0        │
╰──────────┴──────────╯
 [p2] Select a box [0-5] (-1 to quit) : 
1
The AI plays square N°2 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 5   │ 6   │ 0   │ 5   │ 7   │ 1   │ p1 │
│ 1   │ 1   │ 0   │ 7   │ 7   │ 6   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 2        │ 0        │
╰──────────┴──────────╯
 [p2] Select a box [0-5] (-1 to quit) : 
4
The AI plays square N°1 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 7   │ 0   │ 1   │ 6   │ 8   │ 2   │ p1 │
│ 2   │ 2   │ 1   │ 8   │ 1   │ 8   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 2        │ 0        │
╰──────────┴──────────╯
 [p2] Select a box [0-5] (-1 to quit) : 
1
The AI plays square N°3 !
╭─────┬─────┬─────┬─────┬─────┬─────┬────╮
│ (0) │ (1) │ (2) │ (3) │ (4) │ (5) │ P  │
├─────┼─────┼─────┼─────┼─────┼─────┼────┤
│ 8   │ 1   │ 2   │ 0   │ 8   │ 2   │ p1 │
│ 3   │ 1   │ 0   │ 9   │ 1   │ 8   │ p2 │
╰─────┴─────┴─────┴─────┴─────┴─────┴────╯
╭──────────┬──────────╮
│ Gains p1 │ Gains p2 │
├──────────┼──────────┤
│ 5        │ 0        │
╰──────────┴──────────╯
 [p2] Select a box [0-5] (-1 to quit) :

The AI plays as Player 1.

Personally I find it quite difficult to beat (I’ve given it a depth of 10, to reduce the difficulty you can lower this number), and since I’m not an Awale pro only you can judge, it’s up to you!

Conclusion

I’d like to sincerely thank you, and congratulate you if you’ve made it this far. If this article has taught you anything, if you’ve learned anything from it, I’m delighted. 🤓🤓

The simulator source codes are available here:

https://github.com/momole02/awale-simulate

The game made with flutter is available here:

https://github.com/momole02/awale-flutter.git

You can clone it and use them under the terms of the GNU GPL license.