AI implementation for Owaré (Awalé) — Part 1

Helloooo, in this article I’ll teach you how to write an AI that can play Awalé. In this part, we’ll only look at the concepts and algorithms. I’ll dedicate another entire article to talk about the actual implementation.

Owaré game

Awalé (or Owaré) is an African reflexion game played by two players on a board, using seeds. If you’d like to find out more about the game, take a look at the following articles:

• Wikipédia
• https://www.joansala.com/auale/rules/en/
• https://www.youtube.com/watch?v=HunzMxlbghQ

If you’re only interested for code and implementation you can skip this part and jump to the part 2 : https://medium.com/@mol02office/ai-implementation-for-owar%C3%A9-part-2-187b00ccbf09. But if you do this you will probably miss out the best part. The part which can make you understand what you’re really doing.

Heuristic approach to solution

The aim of the game is for each player to collect as many seeds as possible, and if one player wins, the other necessarily loses. With a little mathematical intuition, we can say that this is a zero-sum game. This mathematical jargon term simply means that the sum of each player’s winnings and losses at the end of the game is zero.

Let’s consider that a player who wins the game has a payoff of 1, a player who loses has a payoff of -1, and when the game is tied, each player has a payoff of 0. If I denote by G1 the payoffs of the top player, and G2 the payoffs of the bottom player, at the end of the game we’ll always have :

Zero-sum

This particularity of the game makes it possible to implement the MinMax search algorithm, and particularly its optimization called Alpha Beta for Owaré. I’ll refer to the MinMax algorithm and the Alpha Beta pruning as Alpha Beta for short.

This article is unfortunately not an introduction to Alpha Beta, which unfortunately requires another whole article. I’ll assume that you know and understand this algorithm. If not, don’t worry, there are plenty of articles about it, and I can recommend the following:

• https://www.youtube.com/watch?v=l-hh51ncgDI
• GeekForGeeks

Do further research if the needed , and come back here once you’ve got a good grasp of how the algorithm works. 😁

Mathematical formalization of the game state

In order to properly understand and implement the evaluation and the simulation, two functions required to run the Alpha Beta algorithm in our case, we first need to define a mathematical formalism associated with the state of an Owaré game.

The following information is available at any stage of the game:

• The number of seeds in each square of the board
• The number of seeds won by the top player
• The number of seeds won by the bottom player

The first information corresponds to a matrix M with 2 rows and N columns, where N corresponds to the number of squares per player and each element of the matrix corresponds to the number of seeds in each square.

The other two variables are just simple natural numbers.

We can therefore conclude that the state of the game can be likened to a tuple (M, P1, P2), where M is the state of the board, the matrix, P1 the winnings of the top player, P2 the winnings of the bottom player.

Here’s an example:

Consider the following case:

Case study from Wikipedia

Assuming that the top player has won 10 seeds and the bottom player has won 20 seeds.

Au will have:

Evaluation and simulation

The Alpha Beta algorithm requires that at each stage of the game, or for each state of the game as long as it is not a terminal state, we can:

• Evaluate the state: Quantify the current state, relative to a given player. The lower the value, the more favorable the state will be for that player; the higher the value, the less favorable it will be.
• Simulate a game: make a player’s move, which will result in a new game state.

In fact, this is the main difficulty in implementing Alpha Beta. The search algorithm remains the same, whatever the game or problem to be solved. The choice, however, of these two functions, known as heuristics, is crucial to the algorithm’s success. Bad heuristics are guaranteed to lead to errors and bad choices, and therefore to stupid AI.

The evaluation function

The evaluation function for a player must return a value such as :

• the smaller the value, the more the current player is favored by the situation
• The greater the value, the more the current player is disadvantaged by the situation.

Let’s say we wanted to evaluate the game for the bottom player, player 2, we might be tempted to base our evaluation on the difference between the gains (seeds) . The evaluation result would therefore be given by the following function:

In this case, the higher the winnings of player 2 in relation to those of player 1, the lower the result, and vice versa. We could stop there, but we missing a great deal of information : the state of the board.

When one of the players has squares containing 1 or 2 seeds on his side, this makes him particularly vulnerable, as he runs the risk of being eaten in the next game.

The more such squares he has in front of him, the more vulnerable he will be in the next game. We can consider this aspect in our evaluation function.

For player 2, let’s define the function that counts the number of vulnerable squares in the matrix.

We can modify the evaluation function, this time considering as total gains for one of the players: the seeds won and the number of vulnerable squares on the opponent’s side. The sum will be weighted, as seeds already won cannot be considered in the same way as vulnerable squares.

The evaluation function can be redefined as follows:

The choice of coefficient 1/2 is arbitrary; you can choose another, but make sure it’s not greater than the one associated with the number of seeds.

The little snag here is that in the implementation of alpha beta we generally prefer to work with integers, and the 1/2 used here simply can’t make it.

To solve this problem, we’ll multiply the result of the evaluation by 2 — you’re free to do so, as it has no effect on the evaluation properties. The final formula will be :

For player 1, all you have to do is swap the terms:

This is our evaluation function. Looks great, doesn’t it 😎?

As an exercise, evaluate the example we’ve seen with this function, swap the payoff values, change the number of seeds per box and see what results you get. It’ll help you get a better grasp of things.

The simulation algorithm

The Owaré game is played in a circular direction, which makes it difficult and computationally challenging to simulate the game with our matrix.

Let’s recall the direction of play:

Circular Matrix

This direction gives our matrix a circular character, but also defines an order relationship between the different squares.

If we have to play square C, we’ll put a seed in D, then another in E, then in F, then f, e, d, c, …

The order is A, B, C, D, E, F, f, e, d, c, b ,a. You may wish to switch between a vector representation of the board and its classical matrix representation, to facilitate implementation. In this way, we’ll run the simulation in a vector where the direction is much more natural, and once the simulation is complete we can switch back to the matrix.

Let’s recall the matrix:

This formula is used to convert from matrix to vector:

This formula is used to convert vectors into matrices:

Here’s an example:

Let’s take our case again:

The matrix and associated vector are :

The simulation takes place in two stages:

• The first involves spreading the seeds in the good circles
• The second is to collect the harvested seeds.

Algorithm for spreading seeds.

Algorithm spreadSeeds
Input:
V: Vector[N], start: integer
Output:
V: Vector[N], end: integer
Variables:
i: integer, hand: integer
Start: 
  i <- start + 1
  hand <- V[start]
  V[start] <- 0
  While hand <> 0:
    If i <> start:
      V[i] <- V[i] + 1
      hand <- hand- 1
    End if
    i <- (i + 1) modulo N 
  End while
  end <- i
End

The input to the algorithm is the vector and the start index of the game, while the output is the vector transformed by the simulation and the end index of the game. This end index will be useful later when we want to harvest the seeds.

The direction of the vector traversal as defined corresponds to the direction of play of the Owaré, so there’s no need to perform any calculations. The formulas defined above will be used to switch to the matrix indices when the need arises.

The modulo allows you to start again once you’ve reached the end, and the “if i <> start” prevents you from placing a seed where you originally took them.

Well, if I don’t want to lose you 😁 I think I’m obliged to trace the algorithm So that you understand it better.

Let’s recall our example :

Suppose we want to play the square with the first 6 at the bottom of M, we’ll place a seed on 0, on 6, on 2, on 1, on 3 and on 2.

The indices start from 1.

At initialization we have : 
V = [3, 1, 6, 0, 6, 2, 1, 3, 2, 3, 2, 4], debut <- 3

At the start of the algorithm:
i=4
hand=6
V = [3, 1, 0, 0, 6, 2, 1, 3, 2, 3, 2, 4]
While:
  #iteration 1: (hand = 6)
    if: (i=4 != 3)
      V = [3, 1, 0, 1, 6, 2, 1, 3, 2, 3, 2, 4]
      hand= 5
    i = 5
  #iteration 2: (hand = 5)
    if: (i=5 != 3)
      V = [3, 1, 0, 1, 7, 2, 1, 3, 2, 3, 2, 4]
      hand = 4
    i = 6
  #iteration 3: (hand = 4)
    if: (i=6 != 3)
      V = [3, 1, 0, 1, 7, 3, 1, 3, 2, 3, 2, 4]
      hand = 3
    i = 7
  #iteration 4: (hand = 3)
    if: (i=7 != 3)
      V = [3, 1, 0, 1, 7, 3, 2, 3, 2, 3, 2, 4]
      hand = 2
    i = 8
  #iteration 5: (hand = 2)
    if: (i=8 != 3)
      V = [3, 1, 0, 1, 7, 3, 2, 4, 2, 3, 2, 4]
      hand = 1
    i = 9
  #iteration 6: (hand = 1)
    if: (i=9 != 3)
      V = [3, 1, 0, 1, 7, 3, 2, 4, 3, 3, 2, 4]
      main = 0
    i = 10
  #end as long as: (hand = 0)
end = 10

The vector V at the end is V = [3, 1, 0, 1, 7, 3, 2, 4, 3, 3, 2, 4].

Seed harvest algorithm.

Remember that seed are harvested only when the game ends in the opponent’s camp. This check must be carried out before the winnings are recovered, otherwise the simulation may be distorted.

Algorithm harvestSeeds:
Input:
V:Vector[N], end: integer
Output:
gains: entier
Variables:
i:integer
Start:
  i <- fin
  gains <- 0
  While (V[i]=2 ou V[i]=3) et i is on the opposite player's side:
    gains <- gains + V[i]
    V[i] = 0
    i <- i - 1
    if i < 0 :
      i <- N
    end if
  End While
End

Now that we’re armed with our heuristics, we can proceed to the implementation.

Conclusion

In this part, we’ve looked at the concepts and algorithms needed to implement an AI for Owaré.

I hope you’ve understood everything without too much difficulty.

You can now jump to the second part: https://medium.com/@mol02office/ai-implementation-for-owar%C3%A9-part-2-187b00ccbf09.

Have Fun !