Teaching a browser to play Oware
Oware is a West African sowing game, one of the mancala family, and it's played across Ghana. The Lab has a version you can play against the computer on two levels: easy and ruthless. The whole opponent is about a hundred lines of TypeScript that run in your browser. Here's how it works.
The rules, briefly
This version uses Abapa rules:
- Two rows of six pits, four seeds in each: 48 seeds in all. The bottom row is yours, the top row the computer's.
- On your turn you pick up every seed in one of your pits and sow them one at a time, anticlockwise, into the following pits. If a pit holds twelve or more seeds, the lap skips the pit you started from.
- If your last seed lands in an opponent's pit and makes it 2 or 3, you capture those seeds, then check the pit before it, and keep going back while each one holds 2 or 3 and is still on their side.
- Grand slam: a move that would capture every seed your opponent has captures nothing. Leaving someone empty-handed doesn't count.
- Feeding: if your opponent has no seeds, you must make a move that gives them some.
- More than 24 seeds wins. To stop endless loops, the game also ends after 60 moves without a capture, and each side keeps what's on its own row.
The board is just an array
The state is twelve numbers, two stores, whose turn it is and a counter of moves since the last capture:
type State = { board: number[]; store: [number, number]; turn: 0 | 1; quiet: number; over: boolean };
Pits 0 to 5 are yours and 6 to 11 the computer's, so sowing is pos = (pos + 1) % 12. Capturing walks backwards from the last pit while it's on the opponent's side and holds 2 or 3.
The important design choice is that play(state, pit) never changes the state it's given. It returns a new one. That makes the game easy to save (the whole state goes into localStorage, so a refresh resumes mid-game), easy to test, and, most of all, easy to search.
Searching ahead: minimax
The computer picks a move by imagining the future:
- Try each legal move.
- For each, assume the opponent replies with the move that's worst for the computer.
- Then assume the computer replies with its best move, and so on, to a fixed depth.
- At the bottom, score the position as
computer's store − your store.
The computer is the maximising player and you're the minimising one, which gives the algorithm its name: minimax. The move with the best guaranteed outcome wins.
Pruning: alpha–beta
Oware has at most six moves per turn, so six moves ahead is at most 6⁶ = 46,656 positions. That's already fine for a browser, but alpha–beta pruning cuts it further. While searching, the computer tracks the best score it's guaranteed (alpha) and the best score you're guaranteed (beta). As soon as a branch provably can't change the decision, it stops exploring it:
best = Math.max(best, search(play(s, m), depth - 1, alpha, beta));
alpha = Math.max(alpha, best);
if (alpha >= beta) break; // you'd never allow this line, so stop looking
Pruning returns exactly the same move as full minimax, just faster.
Two levels from one number
The difficulty is only the search depth:
- Easy looks one move ahead. It grabs any capture it can see and walks into traps.
- Ruthless looks six moves ahead, three of its own and three of yours, so it sees captures coming and sets up its own.
When several moves score the same, it picks one at random, so it doesn't play the same game every time.
What a stronger version would add
The scoring is deliberately simple: only seeds already captured count. Ideas for a stronger opponent, in order of payoff:
- Iterative deepening: search depth 1, then 2, then 3, until a time budget runs out, so it plays as deep as the device allows.
- A better evaluation: reward seeds kept on your own side and the number of moves available, not just captures.
- A transposition table: different move orders often reach the same board, and remembering positions already scored avoids searching them twice.
Even without them, a small, well-defined state plus a plain search makes a surprisingly hard opponent.