# Kalah A.I.

## Kalah

Kalah, also known by many as Mancala is one of the oldest games that is still played to the day. The game is very simple in design and mechanics, it involves two players taking turns moving beans/seeds/pebbles on a board or game surface.

### Gameplay

The board may vary in the number of holes it has and the number of pebbles each hole starts with. Some games include a “pie rule” which allows the second player to “switch” sides with the opponent.

On a general turn, the player must pick all the beans from a hole and then proceed to move them one by one in the holes following a counter-clockwise direction. When it comes to score holes, you can only place beans inside your own and skip the opponent’s. There is no way to remove beans from any of the score holes.

### Mechanics

When the final bean falls inside your score hole, you get an extra turn. This allows you to chain multiple turns one after another.

When the final bean falls inside your own board, inside a hole without any other beans **and** the opposite hole on your opponents board contains any number of pebbles, you then get **all** the beans from the opponents hole + your bean, added to your score. This adds quite a lot of complexity to the game, as you must be both defensive and offensive.

Another thing to watch out in a Mancala game, is the end. The game ends when either of the players runs out of beans on **their side** of the board. When this happens to a player, the other player takes all the remaining beans and adds them to their score.

One strategy is to *starve* your opponent and hoard as many beans as possible. Your opponent might have a higher score during the game, but at the end you’ll bet a considerable bonus to your score.

The winner is decided based on the final number of beans inside each player’s score hole. The player with more beans is considered the winner. It is possible (depending on the number of starting beans) for the players to end in a **draw**.

In reality, the game might end earlier, when one of the player obtains `50% + 1`

of the beans.

### A.I. Strategies

#### Min-Max

Min-Max is a straightforward and simple to implement algorithm. All you have to do is compute the game tree and when the desired depth is reached (or the game ends on the branch) you assign a score to the respective leaf.

After that we go back, and select the **max** node during our turns and **min** node during the opponents turn.

A good thing to do (but resource intensive) is computing the game tree on each move. You could only compute the tree when an un-expected move from your optimal tree happens. And you could also get some performance increase when performing chaining moves.

Another implementation-based optimization is to compute the game tree during the opponents turn for each of their moves.

Other thing to consider for a mancala min-max game tree are:

- Invalid moves (assign an extremply small score)
- When to consider a game end?
`50% + 1`

- Real-end of game

- Chaining moves

##### Heuristics

The most important part of the min-max tree is deciding how to determine the value of a leaf node. This can be achieved simply by returning your score, or the score difference but this will not be optimal, as there are other factors to consider.

From our experience, there are 7 factors, each with a different weight.

- Non-zero holes
- Own board sum
- Own score
- First hole value
- Right most move
- Sum board opponent (negative)
- Score opponent (negative)

Another way of determining the score is *MCTS* but that is an entirely different story.

##### Alpha-Beta Pruning

Alpha-Beta pruning adds two new variables (alpha and beta) which get passed down the min-max tree search.

`alpha`

will be the**maximum**value during your turn.`beta`

will be the**minimum**value during your opponent’s turn.

When computing the min-max tree for a specific move, if `beta`

is ever **less than or equal** to `alpha`

, then we deem that move as sub-optimal and ignore the branch all-together, thus reducing the number of computation we must perform.

##### Code

```
func walkTree(depth int, board []int, scoreNorth, scoreSouth int, side position, alpha, beta int) int {
// reach end of search (or game over)
if depth == 0 || side == gameOver {
return computeHeuristics(board, scoreNorth, scoreSouth, g.positionOur)
}
// max player
if side == ourPosition {
maxVal := -100000
// iterate move
for move := 7; move >= 1; move-- {
// ignore invalid move
if board[move] == 0 {
continue
}
// walk tree
localVal := g.walkTree(
depth-1, newBoard, newScoreNorth, newScoreSouth, nextSide,
alpha, beta)
// do max, alpha
maxVal = max(maxVal, localVal)
alpha = max(alpha, localVal)
// pruning
if beta <= alpha {
break
}
}
return maxVal
} // else
// min player
minVal := 100000
for move := 7; move >= 1; move-- {
// ignore invalid move
if board[move] == 0 {
continue
}
// walk tree
localVal := g.walkTree(
depth-1, newBoard, newScoreNorth, newScoreSouth, nextSide,
alpha, beta)
// do min, beta
minVal = min(minVal, localVal)
beta = min(beta, localVal)
// pruning
if beta <= alpha {
break
}
}
return minVal
}
```

#### Other strategies

Other strategies include (and could be discussed in a lot of detail):

- Machine Learning
- Reinforcement Learning
- MCTS (Monte-Carlo Tree Search)

### Repository

You can find an implementation of the min-max alpha-beta pruning with weighted heuristics agent for Mancala on my GitHub page.