View Single Post
Old 04-04-2012, 04:52 PM   #2
igipf
Junior Member

Activity Longevity
0/20 7/20
Today Posts
0/11 ssssssss4
Default Re: iGipf - Developing an iOS game in 2 weeks

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

Confession

While weekend work (this post is a bit late, sorry for that) is in progress right now, we have to confess something. Even though we did not have any iOS code written before the project began, we did have small prototypes implemented in python. This prototype gave us confidence that the project could be implemented in 2 weeks.

Even though we lost a couple of days of work on prototypes in scripting language, it was really useful to see the work in action. Indeed, it raised important performance issues and led to our decision to implement part of the game in pure C. But everything is good in its season.

The prototype

The Python prototype was first a console script of 300 lines; basically just game logic (with some restrictions such as remove selection if many rows are subject to simultaneous removal). Later we added some GUI elements (otherwise it was very frustrating and uncomfortable to play from command line) for which we used the kivy framework for those who are curious. It was our plan to try to run it under the Android OS and check performance on mobile hardware.
Just look at this picture:



This is already a good candidate for the AppStore, isnít it? Just kidding!

Performance Issue

The good news Ė The game worked and we can play, though it was not so convenient.

The bad news -- By looking 3 levels deep, the game needed about 1 minute for analysis. Through simple profiling we realized that most of the time was consumed by copying (cloning) boards for the next move and performing all operations with hexagon rows. We should mention that analysis to a depth of 2 levels is enough for newbie, but for an expert analysis needs to go at least 4 levels deep.

Optimizations

Okay, as we see, performance is a serious issue if we deal with AI calculations on the object-level without special optimizations. Thus, the current goal is to create a layer of the highest possible performance to use 100% of the calculation capabilities of the iPhone/iPad.

Main points:
- Pure C, only structs
- Structures have strict grouping
--- Those that are frequently copied (BoardState)
--- Those that are rarely copied (BoardInfo)
- No heap allocations in repeated operations (only stack)
- Pre-allocated buffers in heap for all needed storage (arrays, temp vars, etc.)
- Copy any data using 'memcpy' only
- Optimized board operations

We believe that we could seriously beat our high-level Python implementation, because most performance in the Python prototype is lost on allocations and constructing objects (instead of memcpy to preallocated space). We expect something like a 10x improvement; but we'll see.

_________________________________________________
igipf.com
our blog
igipf is offline