Wari iOS Game
Wari is a game in the family of Mancala Games from Africa. Each player has six pits on the game board. On the left and right side of the board are capture pits–one owned by each player. Each pit starts a game with 4 stones. On each turn, a player picks up all of the stones from a pit, and “sows” them one by one, counter-clockwise in the subsequently adjacent pits. If the last stone you sow lands in the opposing player’s pit, and it contains 2 or 3 stones, then you capture those stones, and stones previously sown adjacent enemy pits that also contain 2 or three stones. There are additional rules, but that gives you the idea. If you are interested you can find the full Wari rules here.
I think this is an interesting project, because it lends itself well to computer AI play, because it is a perfect information game. In other games, such as poker, the player only has partial information, and building a competitive AI is more difficult.
Wari is ideally suited as a “tree search” AI game. That is, the computer can select possible moves by searching a tree and evaluating possible opponent responses. To improve play further, the tree can search further possible moves and opponent responses.
The number of moves a player has each turn determines the complexity of the search. This is referred to as the branching factor. So, if I want evaluate the game two moves deep, I would have to evaluate all of my possible moves, all of my opponent’s possible responses. And then, for each of my opponents responses, all of my responses, and all of my opponents possible responses. So, that’s 6^4=1296 possible moves. That’s much more manageable than something like Chess, which would have to compute roughly 10^4=10,000 moves.
Since the number of moves to evaluate increases exponentially with search depth, Wari is a more friendly problem to solve for a mobile game, than is chess due to the smaller branching factor.
In addition to a tree of moves, the board after each move must be evaluated to assign a score based on how favorable the board is after the move. Scoring the board allows a number of nodes to be skipped during the search, through different tree search techniques. In my case, I intend to use a Minimax search with Alpha/Beta Pruning.
I’ve currently developed and tested the tree search algorithm using a Tic Tac Toe game, and will adapt it to Wari when I resume work on this project after my WW2 Game project.