Kalah A.I.

Posted on Dec 16, 2018

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.

Mancala

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.

Min-Max

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.

github.com/thee-engineer/kalah-ai