iGipf - Developing an iOS game in 2 weeks

we remember "how learn c++ in 21 days" books:



many people skeptical idea, (as we’ve been future) there no reason doubt it? before delve specifics of our programming venture, here brief introduction our team. couple of programmers no claim (oh, really?) fame angry birds and, moreover, little experience in ios or gamedev in general. speaking, us, project being undertaken both challenge ourselves and, ultimately, pure fun , experience if little can achieved (oh, really?) in end.
know @ least little more google can tell you, let’s talk rules endeavor. “two weeks enough every project” statement made 1 of (let’s call him bill…no, bond better) in skype call late 1 night. “okay, maybe…” reply abruptly cut off “no buts or maybes.” well, ok, if so! of course, spend these weeks investing time in our families, working, taking care of fate of humanity, or number of other noble pursuits. yeah, right! if you’ll buy that, have bridge sell you. if weren’t doing project, honest truth we’d playing starcraft, wasting time on facebook, or drinking beer.
anyway, rules, have been set:
2 weeks of intensive development enough if think it. after all, 2 * 7 * 24 = 336 hours, translates, via following sophisticated math (336/8 *7/5 = 58.8), 59 calendar days or 2 whole months! math justifies time limit (looks there might trick somewhere… millions of managers can wrong!). and, quite (this serious post; honestly), our programming practices prove best way raise priority of given task decrease time limits completing it. so, 2 weeks (“exactly” means 2 weeks plus 2 weeks depending on situation). rule 1 complete!
work on other rules later.

ok, time limit set, must decide should write. after objective evaluation of our capabilities (who trying fool?), decide not write 4d-shooter rpg (or bdsm) elements , multiplayer capabilities 20,000,000 simultaneous players. however, after discussion, think having simpler multiplayer option our game grand idea.

basis, took game called gipf, there nothing in appstore (and not planned, see). decided change rules of original game little bit make simpler play, ensure not exact copy of original game, , make more fun. in short, logical game rules bit more complicated tic-tac-toe , bit less need strategy chess. seems way 67 68% of americans spend time. number of users calculated using extremely strict formulas basic expectations number of sales of application, @ price of $149, needed in order purchase island in mediterranean sea on live , carry on our programming. these numbers can reduced (~1,000 fold) in case decide money not main goal of our lives.

our plans day:

high-level architectural design of application
list of tasks , time limits
make decisions supported platforms , ios version

day 2.

today there won't jokes because serious development process has started. let's begin on positive note: still have development time left , our time milestone hasn’t passed yet. while being serious, should @ our current decisions are:
use cocos2d graphical engine (http://www.cocos2d-iphone.org/)
minimum target ios version 4.2 or 5.0 (there reasons). decision has been made after analysis of ios statistics august 2011 (http://www.marco.org/2011/08/13/instapap...ts-update)

initial architecture thoughts:

model: low level

thought when comes ai , processing tons of data, overhead multiplied large factor (maybe several thousand fold). result, decided write low-level (everything connected data representation , board state) in pure c.

2 base classes are:

* boardinfo – contains data not change during whole game: board parameters: width/height, field structure, etc.

* boardstate – contains data changes during game: current set of pieces on board, number of pieces in reserve both players, etc.

our ai thoughts based on evaluation of large quantity of board states (for example, if use alpha-beta pruning), absolutely need use simple 'memcpy' copy them , fastest operations operate them. that's why data organization above , pure c chosen.

model: high level

here comes objective-c , high-level wrappers of 2 classes discussed above. ai uses low-level model make decisions “best move.” in other cases, high level model objects used (even make move, evaluated using low-level structures only).

hexboardgame – class contains inner variables of type boardinfo not change during game. contains inner variable of type boardstate, changed every turn, initialization functions. needed create game skeleton board parameters (boardinfo) , changing board states (boardstate) included in class.

gipfboardgame – contains specific implementation of hexboardgame igipf rules. expands hexboardgame such things moves pieces shifting (see rules), row removal (see rules), etc.

controller
here, think clear.

views
clearer here. ccscene -- class cocos2d.

conclusion:
enough today. these drafts helped understand going implement , how start basic coding routine. next interesting step ai experiments need proof-of-concept; we'll talk that.

----------

today we’re writing ai part. bit of theory useful.

minimax

we’re developing turn-based game zero-sum play ( if wins n-points, second player loses n-points). whole game can represented tree min-levels 1 player tries minimize possible loss , max-levels second player tries maximize gain.

let’s @ picture:


imagine max player (circle) considering next turn. if expand of turns, of opponent’s turns come after turn , continue so, can tree above. @ level 4 - it’s min turn, compare possible outcomes , propagate minimum value level above (3). 10 less +infinity, 10 goes third level, 5 , -10 have 1 possible turn in sub-branches, propagated is, 5 less 7 propagated, , forth.

brings level 3. it’s max turn. compare each possible outcome , propagate max every sub-branch, did going level 3 level 4. repeat pattern again , again , again unless reach top level. so, value of game -7.

absolute value doesn’t mean far - it’s cost of game according rules defined. if both players rational min player lose 7 points , max player win 7 points; far good.

complexity

it’s pretty simple solution, isn’t it? nevertheless, let’s @ our case: have 24 edge points , 42 possible ways on each level (actually more - turns require extra-step). simple math know on 4th level we’ll have 42*42*42*42 ~3m leaves, 5th level count 130m. , don’t forget we’re working mobile phones, not super-computers. seems though we’re in trouble, alpha-beta pruning comes us.

alpha-beta pruning

idea pretty simple. in real trees can skip branches, because don’t give better solution.



@ right branch on level 1 (consider top level 0) - it’s min turn , here have options: 5 , 8 -- in reality never need expand 8 sub-branch because know doesn’t provide benefit min player when compared branch 5. hence, can prune 8-branch. that’s idea behind simple , efficient algorithm called: alpha-beta pruning.

simple prototype

because move engine isn’t completed yet, built simple simulation generating tree random numbers , trying calculate cost of game. can check how many nodes have been pruned. results 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% , 9% means pruning saved ~ 96% , 91% of calculation times.

of course real evaluation function doesn’t return pure random values, suppose that result pretty similar. our plans complete move engine on weekend.

current status

lines of code , 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 bit late, sorry that) in progress right now, have confess something. though did not have ios code written before project began, did have small prototypes implemented in python. prototype gave confidence project implemented in 2 weeks.

though lost couple of days of work on prototypes in scripting language, useful see work in action. indeed, raised important performance issues , led our decision implement part of game in pure c. in season.

the prototype

python prototype first console script of 300 lines; game logic (with restrictions such remove selection if many rows subject simultaneous removal). later added gui elements (otherwise frustrating , uncomfortable play command line) used kivy framework curious. our plan try run under android os , check performance on mobile hardware.
@ picture:



candidate appstore, isn’t it? kidding!

performance issue

news – game worked , can play, though not convenient.

bad news -- looking 3 levels deep, game needed 1 minute analysis. through simple profiling realized of time consumed copying (cloning) boards next move , performing operations hexagon rows. should mention analysis depth of 2 levels enough newbie, expert analysis needs go @ least 4 levels deep.

optimizations

okay, see, performance serious issue if deal ai calculations on object-level without special optimizations. thus, current goal create layer of highest possible performance use 100% of calculation capabilities of iphone/ipad.

main points:
- pure c, structs
- structures have strict grouping
--- copied (boardstate)
--- copied (boardinfo)
- no heap allocations in repeated operations (only stack)
- pre-allocated buffers in heap needed storage (arrays, temp vars, etc.)
- copy data using 'memcpy' only
- optimized board operations

believe beat our high-level python implementation, because performance in python prototype lost on allocations , constructing objects (instead of memcpy preallocated space). expect 10x improvement; we'll see.

 

more ai. unit-tests.

last time talked ai , alpha-beta pruning , can happily report ai work done! haven’t written evaluation function yet, we’ll cover today.

evaluation function

1 of requirements of ai turn-based game every position must evaluated; otherwise don’t have necessary information needed choose move. build evaluation function, need understand parameters working with. are:
- number of pieces on board ours;
- number of pieces on board belong our opponent;
- number of pieces in our reserve; and,
- number of pieces in opponent’s reserve
now, in more advanced version can build heuristic, such evaluating number of rows can removed in 1(2, ...) move, key position points occupied , forth. right now, however, don’t use of them , depth of search redundant. 4 parameters, writing evaluation function isn’t such easy task. after all, should considered stronger position: 10 pieces on board + 2 in reserve or 2 pieces on board + 10 in reserve? in case adding 1 piece give more power? unfortunately, aren’t gurus of gipf theory need other way figure out.

practice: ai vs ai

method settled on consisted of pairing 1 ai ai using different evaluation function , testing combinations invent. practice best criteria of truth! actually, trial , error can way check ai mechanism correct: pair ai considers n-turns deeps ai considers m-turns deep. here cool stats our work (we counted each player’s turn separate, sequence player 1 – player 2 – player 1 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 on 200 turns!

pure c: profit!

isn’t going 1 of more disputed points in process, stilled ask ourselves if pure c worth it? certainly, yes!

our python prototype started lag @ depth level 4. had wait 1 minute or ai move @ level. basically, allocations\copies took time , processing power. in our c version, no heap alloc, struct memcpy-only, , optimized calc code, depth level 4 analysis took second (~0.6 s - 1.2 s).

in other words, got 60-fold increase performance improvement using pure c, made game more friendly users (user wait couple of seconds, not minutes). answer resounding yes; going pure c worth effort.

unit tests

topic want cover here unit-tests. playing evaluation function , watching how 2 ai players interacted, able discover bugs. yep, aren’t perfect. thankfully, planned our imperfections when decided add regression testing , spent couple of hours adding ability set game scenario , execute ai based on that.

in 2 days had 20 tests. half of them caught bugs , other half related restrictions constructed save dozen of bugs. of course, ai impossible expect accurate, perfect moves in middle of game, in end of game moves 100% precise. example, consider player has 1 piece left, optimal strategy remove pieces lest lose. not how ai played, led few bugs in end of game.

share 1 bug give idea of talking about, consider situation. ai managed find turn on depth 4 , collected many pieces. problem, however, was out of pieces on depth 2 meaning had lost game. clearly, fixing error in logic led better game play. bottom line this. if ask “is unit-testing worth it?” answer “yes, absolutely!”

before wrapping up, let’s @ our current status.

done:
- ai module
- core mvc architecture basis according docs
- model library (gipfgame) -> gamecontroller
- added scene controllers scenes
- player model layer basic (playerbase, userplayer, cpuplayer)

loc , 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

 

Forums iPhone, iPad, and iPod Touch iOS Programming

• iPhone
• Mac OS & System Software
• iPad
• Apple Watch
• Notebooks
• iTunes
• Apple ID
• iCloud
• Desktop Computers
• Apple Music
• Professional Applications
• iPod
• iWork
• Apple TV
• iLife
• Wireless