Game Theory: Solving Twelve Bead

How do computers learn to play games? While modern systems use reinforcement learning to master complex environments like Go or chess, classic strategic board games can be solved using fundamental Graph Theory and Tree Search Algorithms.

In this column, we analyze Baro Guti (Twelve Beads), a traditional abstract strategy board game from South Asia, and explore how to build a mathematical coordinate model and an intelligent AI opponent using the Minimax Algorithm.

1. Modeling the Board as a Coordinate Graph

In twelve-bead, the board consists of 25 intersection nodes laid out in a 5x5 grid:

A slide move is only legal if the starting node $A$ and destination node $B$ are connected by a line. We represent these pathways mathematically:

• Horizontal / Vertical: $

  r_A - r_B

  = 1$ or $

  c_A - c_B

  = 1$.

• Diagonal: Valid only if at least one of the nodes is a diagonal center intersection: \(\text{Centers} = \{(1,1), (1,3), (3,1), (3,3), (2,2)\}\)

2. Vector Capture Jumps

To capture an opponent’s bead, a player must jump over it in a straight line into a vacant node immediately behind it.

To model this, we check three nodes: the start node $A$, the middle node $B$ (containing the opponent’s bead), and the landing node $C$. The jump is valid if and only if the direction vector from $A \to B$ matches the vector from $B \to C$ exactly:

\(\Delta r_1 = r_B - r_A, \quad \Delta c_1 = c_B - c_A\) \(\Delta r_2 = r_C - r_B, \quad \Delta c_2 = c_C - c_B\) \(\Delta r_1 = \Delta r_2 \quad \text{and} \quad \Delta c_1 = \Delta c_2\)

This simple vector slope validation handles horizontal, vertical, and diagonal jumps across the entire board.

3. The Minimax Search Engine

To build the AI opponent, we implement a Minimax Search Tree. The engine models the game as a tree of possible future moves. The AI (Max) attempts to maximize its score, while assuming the human player (Min) will make moves to minimize it.

       [AI Turn (Max)]          Level 0
          /        \
     [Move 1]    [Move 2]       Level 1 (Human Turn - Min)
      /    \      /    \
    [-10]  [+5]  [+20] [-5]     Level 2 (Evaluated Leaves)

In the tree above, the AI chooses Move 2 because it guarantees a score of at least -5 (better than -10). To speed up computation, we use Alpha-Beta Pruning to stop scanning branches that are already worse than previously discovered paths.