One of the most daunting tasks when developing a computer version of a boardgame is creating a good computer opponent. Granted, with the advent of mobile devices and MMOs, it has become more important to connect users with each other than to have a strong AI. However, there are still lots of situations where it is simply more convenient to play against the computer: The AI won’t complain if you take a break and continue the game days later, it’s independent of your network connection and it’s available even at the strangest hour. So having an AI that is fun and/or challenging is great. A lot of users won’t notice it or will simply take it for granted but pretty much everyone will notice a bad one or none at all.
Looking Back
I still remember playing the original Age of Empires which I loved with a passion. I may not be the most astonishing general there ever was and – to be honest – I cannot really remember if I actually played it at the highest level of difficulty. Still, after all those years I remember something strange: Time and again, it worked to attack an opponent from the sea side and – when done right – used it to completely crush the opponent. What happened was that the ships had limited range but were pretty strong, so when a guard tower placed on the coast was heavily damaged, the AI would sent a worker to repair it. The trick was not to destroy the tower but seize fire and instead hit the poor repair guy. Again and again, the AI would sent new repair guys until it ran out of workers. One just had to make sure to never actually destroy that tower…
So although the AI was in general pretty strong, it managed to appear stupid. The inverse is also possible: For years people have wondered about how the ghosts in Pacman cooperate to corner you. As far as I’ve heard, they simply had a different – fairly simple – strategy to choose their path and users interpreted that as cooperation. So developing an AI that is fun is a tricky thing, especially if you have limited computational resources as on a mobile device. This article will show you a number of techniques that I applied when writing the AI for StreetSoccer.
Alpha-Beta Pruning
On a basic level, StreetSoccer is similar to chess: There are two players, all information is available to both players and there is one winner in the end. So it stands to reason that the same techniques developed for chess engines can be used for StreetSoccer as well. The basic algorithm I used is called alpha-beta pruning. In essence, the AI generates all possible moves for a given situation, evaluates each possible move and picks the one with the highest score. That is called a 1-ply search. A 3-ply search would first generate all moves for the current situation, then generate all the opponent’s moves for each of the generated moves and again all the AI’s moves for the opponent’s moves. The decision which top level move should be chosen is done by minimizing/maximizing the scores evaluated on the lowest level: If it’s the AI’s turn, it will pick the branch with the highest score, and if it’s the opponent’s turn, it assumes the opponent will choose the branch that puts the AI in the worst situation. Alpha-beta pruning is an optimization technique on top that drops a branch when one can already derive that that branch is worse than a previously found result.
Describing alpha-beta pruning in total is outside the scope of this article and there are already a lot of good resources for this. I recommend checking out the book Artificial Intelligence for Games by Millington and Funge which helped me a lot with the basic concepts. The standard volume on the topic is of course “Artificial Intelligence – A Modern Approach” by Russel and Norvig but personally I found it to “theoretical” for lack of a better word. There is also a series of tutorials on Chess Programming on GameDev which can be recommended. The rest of this article assumes that the reader is familiar with the basic concepts and implementations of alpha-beta pruning and focuses rather on the implementation details not discussed in the literature.
Iterative State Changing
One of the first lessons learned was that it’s usually a bad idea to generate all moves for a level, store it in a list and then evaluate each one in turn (which might require to recurse to the next deeper level. The main motivation to use this approach is usually a desire to filter out duplicate moves or do some sort of ordering.
Especially when doing a multiple-ply search, the cost of temporarily allocating the data structures to store the moves and destroying them again will slow down the computation tremendously. Instead, it worked much better to just have one state/board situation in memory and iteratively modify it. So for example if the move generation wants to move a piece by one field, apply that move to the state, call the next level of recursion and when returning from the call simply reverse the step. This usually just requires a very small number of variables to be stored on the stack instead of allocating massive numbers of moves on the heap.
Killer Moves
Alpha-beta pruning works best if the moves are order to maximize the pruning effect. While doing a complete ordering is a bit difficult when using the iterative state changing, what can easily be done is to at least do the single best move first. For example in StreetSoccer, movement is first computed for the player that is closest to the ball by the reasoning that he will have the biggest potential of actually moving the ball to a good location. That was quite a noticeable improvement in performance.
Use Transposition Tables
A transposition table is a hash table that “caches” evaluation results. If you are wondering whether you should implement one or not, do it! The key term to look for is “Zorbrist Keys” which are encoded representations of a board situation and used for indexing the entries in the transposition table.
Depending on the cost of your evaluation function and how likely your move generation is to produce duplicates, this can save you a lot of time. But make sure to add some form of debugging statistic and optimize the number of hash collisions.
Avoid the Cost of Method Calls
A turn in StreetSoccer gives the player an amount of movement points that can be used to move the pieces. So unlike chess, a turn is not done after moving a piece a field but instead, a piece can for example move two fields to the left, one up and one down again to spent 4 points of movement.
The original implementation of the StreetSoccer AI used a single call to the move generation function to move a player piece by exactly one field and deducted one point of movement. It then recursively called itself until all points were spent. That makes the implementation fairly easy but produces a large call tree. It is especially true for Objective-C but on some level also for pure C that each method invocation comes at a small performance cost. However, since we work recursively and do a multiple-ply search, that small cost will quickly sum up to a considerable amount of time just spent in invoking the method. Or in other words: If you do something a million times, you will notice it even if each individual execution takes just a fraction of a second.
In a long computation that took like 60 seconds, obj_sendmsg took up to 4 seconds before I optimized the call tree. So I first changed all except for the highest level of methods to pure C functions. Then I rewrote the move generation to produce all possible moves within a single call to the generation function
Avoid Duplicate Moves
Even if one is using a transposition table to store already calculated board positions, checking the table whether a given situation has already been calculated costs time. So I rewrote the move generation yet again and made sure that it would not generate duplicate positions. For example, a player piece may move left and then up or up and then left to come to the same board position. My initial idea was that having a fast move generation and then relying on the transposition table to filter out duplicates would be more efficient than having a complex move generation. However, in my case it turned out to be vastly more efficient to have a slightly more complex move generation and with it avoid a lot of duplicates. For one, checking the transposition table takes time, and for the other, transposition tables only have a limited capacity. What happened was that although the transposition table should have had stored the duplicated boards once and then reused the result, by simply having more requests going to the table the likeliness of hash collisions increased and already pre-computed results were overwritten by other board situations. So when a duplicated move checked against the transposition table, chance were that the previous entry was already overwritten by something else.
Chance Nodes: The Role of a Die
A turn in StreetSoccer starts with a die role, giving the player between 1 and 6 movement points. Unfortunately, chance nodes are often left out when it comes to discussions on alpha-beta pruning. I stumbled upon Joel Veness Bachelor thesis “Expectimax Enhancements for Stochastic Game Players” which shortly discusses the required extensions.
Instead of generating the movement tree for a specific die value, a new level of recursion starts by generating and evaluating the movement tree for all possible results of the die role. The score of the tree is than the sum of the scores weighted by their probability of occurring. To do alpha-beta pruning, one checks after each possibility if the sum of already computed scores plus the worst/best score of the remaining possibilities already invalidates the alpha/beta criteria. Or in other words: If I have computed the score for die role 1-4 and it is so bad that even if the opponent could score a goal with 5-6 he wouldn’t pick that movement branch, I don’t have to compute 5-6 at all.
char evaluatedDieValues = 0;
float summedScore = 0.0f;
for ( char dieValue = 1; dieValue <= 6; ++dieValue, ++evaluatedDieValues )
{
float const upperBound = ( summedScore + ( 6 - evaluatedDieValues ) * AI_GOAL_SCORE ) / 6.0f;
float const lowerBound = ( summedScore + ( 6 - evaluatedDieValues ) * -AI_GOAL_SCORE ) / 6.0f;
float subAlpha = MAX(-AI_GOAL_SCORE, ( *alpha - upperBound ) * 6.0f + AI_GOAL_SCORE );
float subBeta = MIN(AI_GOAL_SCORE, ( *beta - lowerBound ) * 6.0f - AI_GOAL_SCORE );
float possibleScore = ( currentState.isPlayer1Turn ? -10000.0f : 10000.0f);
if ( [self generateMovementWithAlpha:&subAlpha beta:&subBeta bestFoundScore:&possibleScore] )
{
summedScore += possibleScore;
}
else
{
if ( currentState.isPlayer1Turn == NO)
{
summedScore += possibleScore + ( 6 - evaluatedDieValues - 1 ) * -AI_GOAL_SCORE;
evaluatedDieValues = 6;
break;
}
else
{
summedScore += possibleScore + ( 6 - evaluatedDieValues - 1 ) * AI_GOAL_SCORE;
evaluatedDieValues = 6;
break;
}
}
return summedScore / (float)evaluatedDieValues;
}Note that depending on your specific game rules, it might make a difference in what order you evaluate the different possibilities. For example, evaluating the 6 before the 1 might lead to more pruning or not, it depends on your game. But it is one thing that you should profile for.
Optimize the Evaluation Function
On an average board situation with a 4 roled, a 3-ply search of StreetSoccer can lead to millions of board situations that have to be evaluated. So even checking a bool for being true will produces a cost. Here are some tips on what worked for me:
Lazy Evaluation
Think carefully about the order of computing the individual factors that contribute to your evaluation function. For example, the StreetSoccer AI uses the distance of the ball to both of the goals as one criteria. That criteria is also used to check if a move is valid: The rules say that no player is allowed to block the ball such that the other player cannot score a goal if he had an infinite amount of movement points. So if the distance computation fails, the rest of the evaluation function can be aborted, saving a couple of operations.
Remove Debug Code
Again, do something which is very fast often enough and it will hurt you. I had some conditional code in both the movement generation as well as the evaluation function, all of which was used just for debugging. I replaced the if-operations with preprocessor defines and again, a small speed boost.
Bit-Shifting
The distance computation in StreetSoccer is rather tricky. A player piece cannot walk through a field that is occupied by any other piece. The ball cannot be moved onto fields that are occupied by the opponent by one gains a point of movement when it moves onto a field occupied by a member of the the own team.
I tried at least four implementations of those distance functions: The simplest one was already a highly optimized region growing algorithm but it required a lot of ifs and some temporary memory to mark which fields had already been processed. The final version (which gave me a 50% speed boost) is actually just a set of bit-shifting operations!
The trick was to notice that the 6×10 fields within the lines can be represented as bits in a single long long variable. So at first, only the field containing the ball is set to one. Then for each iteration, the fields next to the already processed fields are calculated. For example, all fields adjacent and to the north of the already processed fields are simply calculated by shifting the process fields by 6 bits to the left, all to the south by 6 bits to the right. All fields to the west and east are done by shifting exactly one bit, one only has to be careful of not producing any overflow to the other side. Handling the player pieces is a bit tricky, but in the end the algorithm uses about 20 bit operations times the number of iterations it takes to reach the ball which needless to say is much, much faster than checking of fields individually.
........ ........ ........
. 1 . . 1 . . 1 .
. C4D . . C4D . . C4D .
. 2. . 2. . 2.
. . . . . X .
. . . X . . XXX .
. X B. . XXX B. .XXXXXB.
. 5 . . X 5 . . XXX5 .
. . . . . X .
. 3 . . 3 . . 3 .
. A E. . A E. . A E.
........ ........ ........
So what about player movement? Players can walk outside the lines, so all 8×12 fields have to be respected and that doesn’t fit into a single long long. However, it does fit into two, so the player distance computation actually uses two long long to represent the left/right half of the field. One just has to be careful to have the front correctly grow from one half to the other.
Don’t Assume, Profile
In general, never assume anything. The great thing about iOS development is that one has a great profiler already included in the development environment. So use Apple’s Instruments tool and use it often. Make sure that you have a fixed set of board positions that you run through the computation as a personal benchmark and check if the total time goes down. Instruments can only give you the percentage of time spent in a function and it is easy to optimize one function to notice that it has increased the computation time somewhere else. Which brings me to the next two point:
Record Games
Add something to your game to record the games you play and allows you to watch it again. Not only is it a great feature for your users, it will be invaluable to you. Record everything and then later analyze where the AI worked badly. Use these situations to verify that modifications you did actually solved he problem.
Test, Test, Test
If you have never ever used Unit Tests, you should do so now. It’s next to impossible to debug a highly recursive algorithm such as alpha-beta pruning with stepping through the code lines. What worked great for me was to play against the AI, and code unit tests for each misbehavior of the AI with the “correct” solution as expected test result. Over the time, I accumulated 20-30 different situations and now every time I do a modification to the AI, I just run the test suite to verify everything still works as expected.
Remember to also throw in some things that you always expect to fail and always expect to be true. Rather late in development, I noticed that a sub-function that checked whether a certain game rule was fulfilled always returned true. Now I got like three different tests where the sub-function always has to fail and the problem will never come up again.
Unit tests are also great as a performance benchmark. Just make sure you run them on the device and not on your Mac as the behavior can be quite different. For StreetSoccer, there is a speed factor of 5 or so between running the same situations on the Mac and my iPad.
Character
Don’t just have one AI, give it different characters. This is usually done by artificially limiting the ply-level and/or using different evaluation functions. Especially when someone is new to the game, it won’t be fun to play against an AI that you have been tweaking for ages. It’s just plain bad salesmanship if your AI beats a potential customer 5:0 in the very first game… : )
Images are very important so that users can associate behavior to an AI, so put in something that allows the user to distinguish the AIs. There is a reason why the ghosts in Pacman had different colors!
It’s hard to do right, but having the AI doing trash talk can be great. Things like “awh, you got me”, “damn, you’re lucky” or some character tag line can go a long way in actually loving/hating your AI.
Summary
So hopefully you got some inspiration from reading this. It by far is not meant as a complete “here is the code” article but something which should point you in the right direction. All in all, the StreetSoccer AI is about 3000 lines of code, 50% of which are written in pure C instead of Objective-C. When I began, the AI would take about an hour for a single 3-ply search, now it takes about two minutes to run my entire test suite. Compared to chess, you might be wondering why so slow but consider this: A single ply can lead to roughly 300 different board situations, plus there are chance nodes which add a factor of 6 plus the movement rules are rather complex. So all in all, StreetSoccer is a surprisingly complex game to compute!
Writing AIs is a lot of fun and it is strangely satisfying when some code you wrote actually beats you for the first time. As always, feel free to add your thoughts in the comments.
Leave a Reply