I've been working on Merelles for the last 4 months and I'm pleased to say, I've finally finished it. It's available on the Apple App Store for a small amount.
Merelles is an abstract strategy game. It is also know as Mills, x Men's Morris (4, 6, 9 and 12 men variations) and by many other names.
Seeing as this is my technical blog (and the Apple NDA has been lifted), I feel compelled to provide some technical details. The app itself is written in Objective-C (of course) using TDD (of course!) driven by OCUnit.
The computer AI uses a negascout tree search to examine the game tree. The use of the negascout algorithm means that some pruning will occur on the game tree so that not every node needs to be examined, as long as the moves are ordered so that better moves are examined first!
Iterative deepening is applied on top of this, starting by searching one move ahead, then two, and so on. The moves that look to be good after a search are considered first when searching deeper. In addition, as the same board position can occur several times during a single tree search, moves that result in a really promising board position are classified as killer moves and examined before other moves if they occur again during the search. All this helps in obtaining an amazing prune rate of more than 90%
A question that is often asked is how do you determine if a board position is better than another board position? Unfortunately, it's a fuzzy answer. A set of heuristics is applied, which take into account things like how many pieces each player has in play, how mobile each player is (how many valid moves they have), how easily they can form a row of three pieces, and so on. The strength of the AI is determined largely by these heuristics.
There are 3 difficulty levels. For each level, the heuristics are mostly the same, with varying depths for the tree search and the maximum number of board positions that are considered. For the most complex game (the 12 men game):
- On easy, the AI only looks 2 moves ahead.
- On medium, the AI looks 2 to 4 moves ahead examining up to 3000 board positions.
- On difficult, the AI looks as many moves ahead as it can in examining up to 15000 board positions - in practice this is between 4 and 8 moves ahead, depending on the state of the game.
The resulting game play feels quite natural to me, with the AI coming up with some clever strategies, which in themselves have not been programmed into it, but rather are the result of the tree search and the heuristics. I've been astounded a few times at the way it has trapped me!
The primary challenge in writing this game was to balance the heuristics to set up board positions that would yield good results later in the game rather than just constantly pursue the capture of opponent pieces, which would result in rather one dimensional game play. On top of this, it was necessary to keep the calculations light and to optimise the code as much as possible so that the tree search would not take too long, remembering that it's running on a device with limited computational power. On difficult, the deepest tree searches take up to just over 4 seconds on the iPhone.
