Today we’re writing about the AI part. Hopefully a bit of theory will be useful.
Minimax
We’re developing a turn-based game with zero-sum play ( if someone wins n-points, second player loses n-points). The whole game can be represented as a tree with min-levels where one player tries to minimize possible loss and max-levels where second player tries to maximize gain.
Let’s look at the picture:
Imagine that the max player (circle) is considering his next turn. If we expand all of his turns, then all of his opponent’s turns that come after his turn and continue to do so, we can get the tree as above. Look at level 4 - it’s min turn, we compare all possible outcomes and propagate minimum value to the level above (3). 10 is less than +infinity, so 10 goes to third level, 5 and -10 have only one possible turn in their sub-branches, they are propagated as is, 5 is less than 7 so it is propagated, and so forth.
This brings us to level 3. It’s max turn. We compare each possible outcome and propagate max for every sub-branch, just as we did going from level 3 to level 4. We repeat this pattern again and again and again unless we reach top level. So, the value of game is -7.
Absolute value doesn’t mean anything so far - it’s just a cost of game according to rules that we defined. If both players are rational than min player will lose 7 points and max player will win 7 points; so far so good.
Complexity
It’s a pretty simple solution, isn’t it? Nevertheless, let’s look at our case: we have 24 edge points and 42 possible ways on each level (actually even more - some turns require an extra-step). Just by simple math we know that on the 4th level we’ll have 42*42*42*42 ~3M leaves, by the 5th level this count is already 130M. And don’t forget that we’re working with mobile phones, not super-computers. It seems as though we’re in trouble, but this is where alpha-beta pruning comes to help us.
Alpha-beta pruning
The idea is pretty simple. In real trees we can skip some branches, because they don’t give us a better solution.
Look at the right branch on level 1 (consider top level as 0) - it’s min turn and here we have options: 5 and 8 -- in reality we never need to expand the 8 sub-branch because we already know that it doesn’t provide any benefit to the min player when compared to branch 5. Hence, we can prune 8-branch. That’s the idea behind the very simple and very efficient algorithm called: alpha-beta pruning.
Simple prototype
Because the move engine isn’t completed yet, we built a simple simulation by generating a tree with random numbers and trying to calculate cost of a game. We can then check how many nodes have been pruned. The results are amazing:
Leaves per level: 42
Levels: 3
Number of leaves: 74088
Pruning per level: {level 1: 40, level 2: 245}
Evaluated: 6823 (9%)
Leaves per level: 42
Levels: 4
Number of leaves: 3111696
Prunings per level: {level 1: 41, level 2: 509, level 3: 10194}
Evaluated: 150397 (4%)
Note: 4% and 9% means that pruning saved us about ~ 96% and 91% of calculation times.
Of course the real evaluation function doesn’t return pure random values, but we suppose that that result will be pretty similar. Our plans are to complete the move engine over the weekend.
Current status
Lines of code and files:
$ find . "(" -name "*.m" -or -name "*.c" -or -name "*.h" ")" -print | xargs wc -l
157 ./HexBoardStatic/BoardInfo.c
94 ./HexBoardStatic/BoardInfo.h
58 ./HexBoardStatic/BoardState.c
66 ./HexBoardStatic/BoardState.h
25 ./HexBoardStatic/Common.h
44 ./HexBoardStatic/Common.m
17 ./HexBoardStatic/CommonHexConst.c
85 ./HexBoardStatic/CommonHexConst.h
97 ./HexBoardStatic/CommonOperations.c
76 ./HexBoardStatic/CommonOperations.h
87 ./HexBoardStatic/GipfGame.h
346 ./HexBoardStatic/GipfGame.m
210 ./HexBoardStatic/GipfOperations.c
38 ./HexBoardStatic/GipfOperations.h
10 ./HexBoardStatic/GipfSpecificConstants.c
35 ./HexBoardStatic/GipfSpecificConstants.h
113 ./HexBoardStatic/HexBoardGame.h
216 ./HexBoardStatic/HexBoardGame.m
1774 total
