iGipf - Developing an iOS game in 2 weeks

[igipf]

We all remember those "How to learn C++ in 21 days" books:

Many people are probably skeptical about this idea, but (as we’ve already been into the future) there is no reason to doubt it? Before we delve into the specifics of our programming venture, here is a brief introduction to our team. We are a couple of programmers with no claim (oh, really?) to fame like Angry Birds and, moreover, with very little experience in iOS or GameDev in general. Roughly speaking, for us, this project is being undertaken as both a challenge to ourselves and, ultimately, for the pure fun and experience even if little can be achieved (oh, really?) in the end.
Now that you know at least a little more about us than Google can tell you, let’s talk about the rules for this endeavor. “Two weeks are enough for every project” was a statement made by one of us (let’s call him Bill…No, Bond is better) in a Skype call late one night. “Okay, but maybe…” was the reply that was abruptly cut off by “No buts or maybes.” Well, OK, if you say so! Of course, we could spend these weeks investing time in our families, working, taking care of the fate of humanity, or any number of other noble pursuits. Yeah, right! If you’ll buy that, I have a bridge to sell you. If we weren’t doing this project, the honest truth is that we’d be playing Starcraft, wasting time on Facebook, or just drinking beer.
Anyway, back to the rules, which have been set:
Two weeks of deeply intensive development is enough if you think about it. After all, 2 * 7 * 24 = 336 hours, which translates, via the following sophisticated math (336/8 *7/5 = 58.8), into nearly 59 calendar days or 2 whole months! Clearly the math justifies the time limit (looks like there might be a trick somewhere… But millions of managers can be wrong!). And, quite seriously (this is a serious post; honestly), our programming practices prove that the best way to raise the priority of any given task is to decrease the time limits for completing it. So, exactly two weeks (“exactly” means two weeks plus an extra two weeks depending on the situation). Rule 1 is complete!
Work on other rules later.

OK, now that the time limit is set, we must decide what we should write. After an objective evaluation of our capabilities (who are we trying to fool?), we decide not to write a 4D-shooter with RPG (or BDSM) elements and multiplayer capabilities for 20,000,000 simultaneous players. However, after some discussion, we do think that having a simpler multiplayer option our game is a grand idea.

As a basis, we took the game called GIPF, as there is nothing in the AppStore (and not planned, as we see). We decided to change the rules of the original game a little bit to make it even simpler to play, to ensure that it is not an exact copy of the original game, and to make it even more fun. In short, it will be a logical game with rules a bit more complicated than Tic-tac-toe and with a bit less need for strategy than chess. This seems like a good way for roughly 67 to 68% of Americans to spend their time. This number of users is calculated using extremely strict formulas with basic expectations about the number of sales of the application, at the price of $149, that are needed in order for us to purchase an island in the Mediterranean Sea on which to live and carry on about our programming. These numbers can be slightly reduced (~1,000 fold) in case we decide that money is not the main goal of our lives.

Our plans for the day:

High-level architectural design of the application
List of tasks and time limits
Make decisions about the supported platforms and iOS version

Day 2.

Today there won't be any jokes because the serious development process has started. Let's begin on a positive note: we still have some development time left and our time milestone hasn’t passed yet. While being serious, we should look at what our current decisions are:
We will use Cocos2d as the graphical engine (cocos2d for iPhone)
The minimum target iOS version will be 4.2 or 5.0 (there are some good reasons). This decision has been made after analysis of the iOS statistics for August 2011 (http://www.marco.org/2011/08/13/instapap...ts-update)

Initial architecture thoughts:

Model: low level

We thought that when it comes to AI and processing tons of data, any overhead would be multiplied by a large factor (maybe several thousand fold). As a result, we decided to write the low-level (everything that is connected with data representation and the board state) in pure C.

The two base classes are:

* BoardInfo – This contains data that does not change during the whole game: board parameters: width/height, field structure, etc.

* BoardState – This contains data that changes during the game: current set of pieces on board, number of pieces in reserve for both players, etc.

Our AI thoughts are based on evaluation of a large quantity of board states (for example, if we use Alpha-Beta pruning), so we absolutely need to use simple 'memcpy' to copy them and the fastest operations to operate with them. That's why the data organization above and pure C were chosen.

Model: high level

Here comes Objective-C and high-level wrappers of the two classes discussed above. AI uses low-level model only to make decisions about what is the “best move.” In all other cases, high level model objects are used (even to make the move, which was just evaluated using low-level structures only).

HexBoardGame – This class contains inner variables of type BoardInfo that do not change during the game. It also contains an inner variable of type BoardState, which is changed every turn, as well as initialization functions. Everything that is needed to create a game skeleton from board parameters (BoardInfo) and changing board states (BoardState) is also included in this class.

GipfBoardGame – This contains the specific implementation of HexBoardGame for iGipf rules. It expands HexBoardGame with such things as moves with pieces shifting (see the rules), row removal (see the rules), etc.

Controller
Here, we think everything is clear.

Views
Everything is even clearer here. CCScene -- is a class from Cocos2d.

Conclusion:
Enough for today. These drafts helped us to understand what we are going to implement and how to start the basic coding routine. The next interesting step will be AI experiments for which we need a proof-of-concept; but we'll talk about that.



_________________________________________________
Edited by Moderator - blog liks are not allowed, please read the forum rules

 

[igipf]

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.

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
More AI. Unit-tests.

Last time we talked about AI and alpha-beta pruning and we can now happily report that the AI work is done! We haven’t written anything about evaluation function yet, so we’ll cover that today.

Evaluation function

One of the requirements of AI for turn-based game is that every position must be evaluated; otherwise we don’t have the necessary information needed to choose a move. To build an evaluation function, we need to understand what parameters we are will be working with. Basically they are:
- the number of pieces on board that are ours;
- the number of the pieces on the board that belong to our opponent;
- the number of pieces in our reserve; and,
- the number of pieces in the opponent’s reserve
Now, in a more advanced version we can build a heuristic, such as evaluating the number of rows that can be removed in 1(2, ...) move, key position points occupied and so forth. Right now, however, we don’t use any of them and with good depth of search they are redundant. Even with 4 parameters, writing an evaluation function isn’t such an easy task. After all, what should be considered the stronger position: 10 pieces on board + 2 in reserve or 2 pieces on board + 10 in reserve? In which case does adding 1 piece give more power? Unfortunately, we aren’t gurus of gipf theory so we need other way to figure this all out.

Practice: AI vs AI

The method we settled on consisted of us pairing one AI with another AI using a different evaluation function and then testing all combinations we could invent. Practice is the best criteria of truth! Actually, trial and error can be a very good way to check that an AI mechanism is correct: pair AI that considers n-turns deeps with AI that considers m-turns deep. Here are some cool stats from our work (We counted each player’s turn as separate, so sequence player 1 – player 2 – player 1 is 3 turns.):

5-levels AI beats 3-levels AI in ~60 turns
5-levels AI beats 4-levels AI in ~130 turns
5-levels AI vs 5-levels AI played over 200 turns!

Pure C: Profit!

This probably isn’t going to be one of the more disputed points in this process, but we stilled ask ourselves if pure C as it worth it? Certainly, yes!

Our python prototype started to lag at depth level 4. We had to wait roughly one minute or so for an AI move at that level. Basically, allocations\copies took too much time and processing power. In our C version, with no heap alloc, struct memcpy-only, and optimized calc code, a depth level 4 analysis took roughly a second (~0.6 s - 1.2 s).

In other words, we got a 60-fold increase performance improvement by using pure C, which made the game more friendly for users (User will wait a couple of seconds, not minutes). So the answer is a resounding yes; going with pure C was worth the effort.

Unit tests

Another topic we want to cover here is unit-tests. Playing with an evaluation function and watching how 2 AI players interacted, we were able to discover some bugs. Yep, we aren’t perfect. Thankfully, we planned for our imperfections when we decided to add regression testing and spent a couple of hours adding the ability to set up any game scenario and execute AI based on that.

In just 2 days we already had about 20 tests. About half of them caught bugs and other half were related to restrictions we constructed to save us from another dozen of bugs. Of course, with AI it is almost impossible to expect accurate, perfect moves in the middle of the game, but in the end of the game some moves are 100% precise. As an example, consider that player has only 1 piece left, his optimal strategy is to remove his pieces lest he lose. This was not always how the AI played, which led to a few bugs in the end of the game.

To share one bug with you to give an idea of what we are talking about, consider this situation. Sometimes AI managed to find a very good turn on depth 4 and collected many pieces. The problem, however, was that he was out of pieces on depth 2 meaning he had already actually lost the game. Clearly, fixing this error in logic led to better game play. The bottom line is this. If you ask us “is unit-testing worth it?” the answer is “yes, absolutely!”

Before wrapping up, let’s look at our current status.

Done:
- AI module
- Core mvc architecture basis according to the docs
- Model library (GipfGame) -> GameController
- Added scene controllers for all scenes
- Player model layer basic (PlayerBase, UserPlayer, CPUPlayer)

LOC and files:

$ find . "(" -name "*.m" -or -name "*.c" -or -name "*.h" ")" -print | xargs wc -l
20 ./AppDelegate.h
172 ./AppDelegate.m
16 ./CCSprite+Utility.h
23 ./CCSprite+Utility.m
10 ./Constants.c
35 ./Constants.h
21 ./ContentControllerDelegate.h
23 ./ControllerBase.h
32 ./ControllerBase.m
27 ./CPUPlayer.h
46 ./CPUPlayer.m
45 ./GameConfig.h
54 ./GameController.h
88 ./GameController.m
18 ./GameParameters.h
21 ./GameParameters.m
22 ./GameScene.h
29 ./GameScene.m
26 ./GameSceneController.h
44 ./GameSceneController.m
27 ./GameSceneDelegate.h
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
17 ./main.m
45 ./MainAppViewController.h
221 ./MainAppViewController.m
36 ./MenuController.h
39 ./MenuController.m
26 ./MenuScene.h
77 ./MenuScene.m
26 ./MenuSceneDelegate.h
61 ./PlayerBase.h
62 ./PlayerBase.m
28 ./PlayerBaseSub.h
40 ./PlayerDelegate.h
16 ./SceneBase.h
18 ./SceneBase.m
16 ./SceneManager.h
37 ./SceneManager.m
60 ./SinglePlayerLobbyController.h
67 ./SinglePlayerLobbyController.m
16 ./SinglePlayerLobbyScene.h
13 ./SinglePlayerLobbyScene.m
37 ./SinglePlayerLobbySceneDelegate.h
26 ./UserPlayer.h
25 ./UserPlayer.m
3582 total


_________________________________________________
Edited by Moderator - blog link removed, please read the forum rules