On August 8, 2011 we issued a TicTacToe Challenge.
The objective was to submit your own code to be implemented in our iPhone TicTacToe game that we wrote together in the Programming in Objective-C course. We have had a lot of interest, however, no one submitted any code! What gives??!!!
Well, perhaps one problem is that many of you guys may not have followed the Objective-C course. That’s cool, we can’t expect everyone to be interested in this.
I would like to write up a blog that showcases my version of the AI and provide a springboard for a version of the CPU logic (just incase you’re considering submitting your code).
WATCH A PREVIEW OF THE AI IN ACTION
Before I continue, I would like to restate the requirements:
Write an intelligent Tic Tac Toe algorithm that will be used in our iPhone App. Your code is intended to make the single player experience better by adding logic to the CPU moves. Currently the CPU simply selects random cells based on the C Pseudo Random Number Generator.
Here is the method template we want you to use:
// ------------------------------------------------------------
- (void) cpuMakeMoveHard
{
_isLocked = YES;
sleep(rand() % 2 + 1);
NSInteger cpuRow, cpuCol, cpuTag;
/* YOUR CODE GOES HERE */
cpuTag = ((cpuCol + 1) * 10) + (cpuRow + 1);
_isLocked = NO;
switch(cpuTag)
{
case 11: [ self tileHasBeenSelected: btnA1 ];break;
case 12: [ self tileHasBeenSelected: btnA2 ];break;
case 13: [ self tileHasBeenSelected: btnA3 ];break;
case 21: [ self tileHasBeenSelected: btnB1 ];break;
case 22: [ self tileHasBeenSelected: btnB2 ];break;
case 23: [ self tileHasBeenSelected: btnB3 ];break;
case 31: [ self tileHasBeenSelected: btnC1 ];break;
case 32: [ self tileHasBeenSelected: btnC2 ];break;
case 33: [ self tileHasBeenSelected: btnC3 ];break;
}
}
// ------------------------------------------------------------
- Please view the ‘Programming in Objective-C’ course first!
- You must use the method template above (cpuMakeMoveHard). Apply your algorithm in the commented section marked “YOUR CODE GOES HERE”
- The method cpuMakeMoveHard must be a part of the TicTacToe_iPhone_AppViewController class (TicTacToe_iPhone_AppViewController.m)
- You CAN add code outside the context of the method cpuMakeMoveHard only if used to eliminate code redundancy
- Your algorithm will intelligently select a ROW number (cpuRow) and COLUMN number (cpuCol) to place the ‘O’ for Buzz the Fly
Sounds simple enough, right? Now, how do you tackle such a problem? Let’s break it down. First, what does a basic TicTacToe CPU algorithm need to do in order to be effective?
The offensive strategy of the game is simple: try to get three of your marks in a row. The defensive strategy of the game is quite subjective, but there are some very basic elements that you can extract.
The way I see this algorithm playing out is like Football strategy. When I was a football player, my coaches would always say that the best way to scheme an offense is by building a solid defense. By using this strategy, you protect yourself first and attack second. So, just like my view of Football, my Tic Tac Toe Strategy would be like:
Seek an opportunity to win now
Just like any good sports strategy, if you can strike now, then do it! No need to block your opponent if you can defeat them immediately.
[X] [X] [ ] [O] [O] [ ] [ ] [X] [ ] |
[X] [X] [O] [X] [O] [ ] [ ] [X] [ ] |
[X] [O] [X] [X] [O] [ ] [ ] [ ] [ ] |
The above three scenarios are situations where I can win now! The red box is the logical move. This will put an immediate end to the game and make me the victor!
Try to stop the opponent from winning
If there are no opportunities to win now, then I must think about the future. In many contests, your ability to win is based on how good you are at preventing others from winning. In this situation you must look for any place where your opponent is about to win and stop them right away. This gives you a chance to fight another day.
[ ] [ ] [ ] [ ] [X] [ ] [X] [ ] [O] |
[X] [ ] [O] [X] [ ] [ ] [ ] [ ] [ ] |
[ ] [ ] [O] [ ] [ ] [ ] [X] [X] [ ] |
In contrast to our first action, now we want to play saboteur! It’s the classic “If I can’t win then NOBODY CAN!” The above situations show cases of how to apply this logic. In each three games you can see that X is one move away from winning; therefore, it makes logical sense to stop them by placing my O in one of the red squares.
Seek an opportunity to put myself in a better position to win later
If I cannot win right now, and my opponent is not about to win, then I must tactically look for a way to position myself for a win later.
[X] [ ] [ ] [ ] [O] [ ] [ ] [ ] [X] |
[ ] [X] [ ] [ ] [X] [ ] [ ] [O] [ ] |
[O] [X] [ ] [ ] [X] [ ] [ ] [O] [X] |
In deciding this move, I must scan the board and find places that put me in position to strike later. All three of the games above have me in no position to win now or stop my opponent from winning. This means that I can look for a place to set myself up for my next move. In the first game, you can see that there are MANY different options for me to have three in a row. This is why Tic Tac Toe strategies often start by selecting the middle position. The second game shows that I have a developing opportunity across the bottom row, and the third gives me a good chance if I populate the left column.
Seek a location to prevent my opponent from having a chance to win later
If I cannot win right now, my opponent is not about to win, and there are no real opportunities to position myself for a future move, then I must attempt to stop my opponent from having future opportunities.
[O] [X] [ ] [X] [ ] [ ] [X] [O] [ ] |
[X] [ ] [ ] [O] [ ] [ ] [O] [X] [X] |
[ ] [ ] [ ] [ ] [X] [ ] [ ] [ ] [ ] |
In each of the games above, I do not have any situations to win or stop my opponent from winning. However, I am able to locate situations where the opposition has opportunities to set up for future gains. When using this strategy, I must seek positions where I can play spoiler to my enemies game plan.
Now, the next question is, how can you represent this in Objective-C code? There are tons of ways to pull this off. I wrote some code the other day that kind of performs the above strategies. Is it perfect? Maybe, but not likely.
Setting up
NSInteger xGrid[3][3], oGrid[3][3];
for(NSInteger i = 0; i < 3; i++)
{
for(NSInteger j = 0; j < 3; j++)
{
if([ ttt getValueAtColumn: j andRow: i ] == 'X')
{
xGrid[i][j] = 1;
oGrid[i][j] = 0;
}
else if([ ttt getValueAtColumn: j andRow: i ] == 'O')
{
xGrid[i][j] = 0;
oGrid[i][j] = 1;
}
else
{
xGrid[i][j] = 0;
oGrid[i][j] = 0;
}
}
}
I chose to build two multidimensional arrays that will store numbers for populated cells. As I iterate through each cell, if the current cell contains a X, then set the xGrid index to 1 and oGrid index to 0. Else if the current cell contains an O, then set the xGrid index to 0 and oGrid index to 1. If the cell is not occupied, then just set it to zero. This is one way that I can count the elements in the cells.
NSInteger xRowCounts[3], oRowCounts[3];
NSInteger xColCounts[3], oColCounts[3];
NSInteger xDiagCounts[2], oDiagCounts[2];
xRowCounts[0] = xGrid[0][0] + xGrid[0][1] + xGrid[0][2];
xRowCounts[1] = xGrid[1][0] + xGrid[1][1] + xGrid[1][2];
xRowCounts[2] = xGrid[2][0] + xGrid[2][1] + xGrid[2][2];
oRowCounts[0] = oGrid[0][0] + oGrid[0][1] + oGrid[0][2];
oRowCounts[1] = oGrid[1][0] + oGrid[1][1] + oGrid[1][2];
oRowCounts[2] = oGrid[2][0] + oGrid[2][1] + oGrid[2][2];
xColCounts[0] = xGrid[0][0] + xGrid[1][0] + xGrid[2][0];
xColCounts[1] = xGrid[0][1] + xGrid[1][1] + xGrid[2][1];
xColCounts[2] = xGrid[0][2] + xGrid[1][2] + xGrid[2][2];
oColCounts[0] = oGrid[0][0] + oGrid[1][0] + oGrid[2][0];
oColCounts[1] = oGrid[0][1] + oGrid[1][1] + oGrid[2][1];
oColCounts[2] = oGrid[0][2] + oGrid[1][2] + oGrid[2][2];
xDiagCounts[0] = xGrid[0][0] + xGrid[1][1] + xGrid[2][2];
xDiagCounts[1] = xGrid[2][0] + xGrid[1][1] + xGrid[0][2];
oDiagCounts[0] = oGrid[0][0] + oGrid[1][1] + oGrid[2][2];
oDiagCounts[1] = oGrid[2][0] + oGrid[1][1] + oGrid[0][2];
After I loaded my counting arrays, I begin to calculate the potential. At first, I built some arrays to store the different counts for the two players. xRowCounts is a three element array that will store the number of occurrences of X in each row. oRowCounts will store similar data, except for O. In a similar way, the column counts are kept track of by using the xColCounts and oColCounts arrays. The xDiagCounts and oDiagCounts arrays will store the values diagonally. In this code, the diagonal index 0 represents upper left to lower right, and 1 represents upper right to lower left.
[O] [X] [ ] [X] [ ] [ ] [X] [O] [ ] |
[X] [ ] [ ] [O] [ ] [ ] [O] [X] [X] |
[ ] [ ] [ ] [ ] [X] [ ] [ ] [ ] [ ] |
xRowCounts [0] = 1 xRowCounts [1] = 1 xRowCounts [2] = 1
xColCounts[0] = 2 xColCounts[1] = 1 xColCounts[2] = 0
xDiagCounts[0] = 0 xDiagCounts[1] = 1
|
xRowCounts [0] = 1 xRowCounts [1] = 0 xRowCounts [2] = 2
xColCounts[0] = 1 xColCounts[1] = 1 xColCounts[2] = 1
xDiagCounts[0] = 2 xDiagCounts[1] = 0
|
xRowCounts [0] = 0 xRowCounts [1] = 1 xRowCounts [2] = 0
xColCounts[0] = 0 xColCounts[1] = 1 xColCounts[2] = 0
xDiagCounts[0] = 1 xDiagCounts[1] = 1
|
oRowCounts [0] = 1 oRowCounts [1] = 0 oRowCounts [2] = 1
oColCounts[0] = 1 oColCounts[1] = 1 oColCounts[2] = 0
oDiagCounts[0] = 1 oDiagCounts[1] = 0
|
oRowCounts [0] = 0 oRowCounts [1] = 1 oRowCounts [2] = 1
oColCounts[0] = 2 oColCounts[1] = 0 oColCounts[2] = 0
oDiagCounts[0] = 0 oDiagCounts[1] = 1
|
oRowCounts [0] = 0 oRowCounts [1] = 0 oRowCounts [2] = 0
oColCounts[0] = 0 oColCounts[1] = 0 oColCounts[2] = 0
oDiagCounts[0] = 0 oDiagCounts[1] = 0
|
Seek CPU Move Method (Selection Algorithm)
-(void) seekCpuMove: (NSInteger*) inRowCounts : (NSInteger*) inColCounts : (NSInteger*) inDiagCounts : (NSInteger*) cpuRow : (NSInteger*) cpuCol: (NSInteger) countSeek
{
NSInteger i, rowTarget = -1, colTarget = -1, diagTarget = -1;
if(*cpuCol == -1 || *cpuRow == -1)
{
for(i = 0; i < 3; i++)
{
if(rowTarget == -1 && inRowCounts[i] == countSeek) rowTarget = i;
if(colTarget == -1 && inColCounts[i] == countSeek) colTarget = i;
if(i < 2 && diagTarget == -1 && inDiagCounts[i] == countSeek) diagTarget = i;
}
NSLog(@"rowTarget=%d", rowTarget);
NSLog(@"colTarget=%d", colTarget);
NSLog(@"diagTarget=%d", diagTarget);
for(i = 0; i < 3; i++)
{
if( rowTarget != -1 && [ ttt getValueAtColumn: i andRow: rowTarget ] == ' ')
{ *cpuCol = i; *cpuRow = rowTarget; break; }
if( colTarget != -1 && [ ttt getValueAtColumn: colTarget andRow: i ] == ' ')
{ *cpuCol = colTarget; *cpuRow = i; break; }
if(diagTarget == 0 && i == 0)
{
if([ ttt getValueAtColumn: 0 andRow: 0 ] == ' ')
{ *cpuCol = 0; *cpuRow = 0; break; }
if([ ttt getValueAtColumn: 1 andRow: 1 ] == ' ')
{ *cpuCol = 1; *cpuRow = 1; break; }
if([ ttt getValueAtColumn: 2 andRow: 2 ] == ' ')
{ *cpuCol = 2; *cpuRow = 2; break; }
}
else if(diagTarget == 1 && i == 1)
{
if([ ttt getValueAtColumn: 2 andRow: 0 ] == ' ')
{ *cpuCol = 2; *cpuRow = 0; break; }
if([ ttt getValueAtColumn: 1 andRow: 1 ] == ' ')
{ *cpuCol = 1; *cpuRow = 1; break; }
if([ ttt getValueAtColumn: 0 andRow: 2 ] == ' ')
{ *cpuCol = 0; *cpuRow = 2; break; }
}
}
}
}
The first thing you may notice is that the method declaration does not use any fancy Objective-C parameter label text. This is because I am being rebellious!-(void) seekCpuMove: (NSInteger*) inRowCounts : (NSInteger*) inColCounts : (NSInteger*) inDiagCounts : (NSInteger*) cpuRow : (NSInteger*) cpuCol: (NSInteger) countSeekThis method is intended to be reusable to multiple situations. The parameters that this accepts is
- The row array you want to work on [xRowCounts or oRowCounts]
- The column array you want to work on [xColumnCounts or oColumnCounts]
- The diagonal array you want to work on [xDiagCounts or xDiagCounts]
- A pointer to the cpu row
- A pointer to the cpu column
- The number of ‘hits’ to look out for
By breaking it apart in this way, I can look for each situation where I and my opponent is about to win (countSeek = 2) and where we may have opportunities (countSeek = 1).Next, I created some local variables. NSInteger i, rowTarget = -1, colTarget = -1, diagTarget = -1;These integers represent data that I will be processing in this method.
- i is used to traversing for loops
- rowTarget is designed to store the row that our selection algorithm is considering targeting
- colTarget is designed to store the column that our selection algorithm is considering targeting
- diagTarget is designed to store which diagonal that our selection algorithm is considering targeting
Next, the algorithm will check the selected row and column. if(*cpuCol == -1 || *cpuRow == -1)The calling code will set the value of these two integers to -1 if nothing has been selected. Therefore, we only want to select a move if it has not previously been determined.Next, I will count the values that are contained in the passed arrays.
for(i = 0; i < 3; i++)
{
if(rowTarget == -1 && inRowCounts[i] == countSeek) rowTarget = i;
if(colTarget == -1 && inColCounts[i] == countSeek) colTarget = i;
if(i < 2 && diagTarget == -1 && inDiagCounts[i] == countSeek) diagTarget = i;
}
This loop is traversing through the passed arrays and attempting to find a target. If the row has not been targeted yet [rowTarget == -1] and the current row count is equal to the value we’re looking for [&& inRowCounts[i] == countSeek], then the current row has been targeted [rowTarget = i]!
The same logic is applied to the columns, and a slightly modified version is used on the diagonals. If diagonals are not treated separately then we will extend the bounds of the array.Admittedly, this process is not entirely efficient, but it still attempts to sniff out a potential move on either my self or my opponent. After we have our targets, we will then try to find a place to make a move.
for(i = 0; i < 3; i++)
{
if( rowTarget != -1 && [ ttt getValueAtColumn: i andRow: rowTarget ] == ' ')
{ *cpuCol = i; *cpuRow = rowTarget; break; }
if( colTarget != -1 && [ ttt getValueAtColumn: colTarget andRow: i ] == ' ')
{ *cpuCol = colTarget; *cpuRow = i; break; }
if(diagTarget == 0 && i == 0)
{
if([ ttt getValueAtColumn: 0 andRow: 0 ] == ' ')
{ *cpuCol = 0; *cpuRow = 0; break; }
if([ ttt getValueAtColumn: 1 andRow: 1 ] == ' ')
{ *cpuCol = 1; *cpuRow = 1; break; }
if([ ttt getValueAtColumn: 2 andRow: 2 ] == ' ')
{ *cpuCol = 2; *cpuRow = 2; break; }
}
else if(diagTarget == 1 && i == 1)
{
if([ ttt getValueAtColumn: 2 andRow: 0 ] == ' ')
{ *cpuCol = 2; *cpuRow = 0; break; }
if([ ttt getValueAtColumn: 1 andRow: 1 ] == ' ')
{ *cpuCol = 1; *cpuRow = 1; break; }
if([ ttt getValueAtColumn: 0 andRow: 2 ] == ' ')
{ *cpuCol = 0; *cpuRow = 2; break; }
}
}
As you can see, the above code takes precedence. For example, it favors rows first, columns second, and diagonals last. Why? I don’t know! I was lazy, and this is just what I came up with at 3:00 AM the other night!The logic simply tries to find an unoccupied cell on our target. For instance, if we targeted a row [rowTarget != -1] and the current cell is unoccupied [&& [ ttt getValueAtColumn: i andRow: rowTarget ] == ’ ’] then decide to occupy it [*cpuCol = i; *cpuRow = rowTarget; break;].
The exact same logic is applied to columns. Designing the code this way gives it the flexibility to select based on multiple criteria.
So, if we targeted a row, but there is no place on the row to occupy, then we can attempt to select from a targeted column or diagonal. As I stated before, there is an order of precedence. This can easily be changed if you wanted to.Now that we know how the selection is to be made, let’s see how we could implement this.
// Tries to win
[ self seekCpuMove: oRowCounts : oColCounts : oDiagCounts : &cpuRow : &cpuCol : 2 ];
// Tries to stop other player from winning
if(cpuCol == -1 || cpuRow == -1)
[ self seekCpuMove:xRowCounts : xColCounts : xDiagCounts : &cpuRow : &cpuCol : 2 ];
// Tries to find a place where it has a better chance at winning
if(cpuCol == -1 || cpuRow == -1)
[ self seekCpuMove: oRowCounts : oColCounts : oDiagCounts : &cpuRow : &cpuCol : 1 ];
// Tries to find a place where is has a better chance at stopping the other player from winning
if(cpuCol == -1 || cpuRow == -1)
[ self seekCpuMove:xRowCounts : xColCounts : xDiagCounts : &cpuRow : &cpuCol : 1 ];
NSLog(@"cpuRow=%d cpuCol=%d", cpuRow, cpuCol);
if(cpuCol == -1 || cpuRow == -1)
{
[ self cpuMakeMove ];
return;
}
A multitude of scenarios are outlined above. Just like in the discussion above, we try to win the game right now. If we are unable to find a winning cell, then we default to trying to stop the opponent from winning.
Notice how in these two situations the final parameter is 2. This means that we are seeking '2 in a row’.If the opponent has no winning opportunities, then we try to find a place to give us a chance to win. If we have nothing on the board, then we try to see if we can stop our opponent from game planning! In these last two situations, notice how the last parameter is 1. This means that we are looking for '1 in a row’. Therefore, if we or our opponent has not made a move yet these will be ineffective.If all-else-fails, then we default to a random move by calling the cpuMakeMove method.
Whew! That was a mouth full! I hope I didn’t forget anything… Just so that you are not completely in the dark, I will paste the full code implementation below. Keep in mind that the seekCpuMove method is already above. Just remember to update your .h file!
- (void) cpuMakeMoveHard
{
NSAutoreleasePool* makeMovePool = [ NSAutoreleasePool new ];
_isLocked = YES;
sleep(rand() % 2 + 1);
NSInteger cpuRow = -1, cpuCol = -1, cpuTag;
//CODE GOES HERE
NSInteger xGrid[3][3], oGrid[3][3];
for(NSInteger i = 0; i < 3; i++)
{
for(NSInteger j = 0; j < 3; j++)
{
if([ ttt getValueAtColumn: j andRow: i ] == 'X')
{
xGrid[i][j] = 1;
oGrid[i][j] = 0;
}
else if([ ttt getValueAtColumn: jandRow: i ] == 'O')
{
xGrid[i][j] = 0;
oGrid[i][j] = 1;
}
else
{
xGrid[i][j] = 0;
oGrid[i][j] = 0;
}
}
}
NSInteger xRowCounts[3], oRowCounts[3];
NSInteger xColCounts[3], oColCounts[3];
NSInteger xDiagCounts[2], oDiagCounts[2];
xRowCounts[0] = xGrid[0][0] + xGrid[0][1] + xGrid[0][2];
xRowCounts[1] = xGrid[1][0] + xGrid[1][1] + xGrid[1][2];
xRowCounts[2] = xGrid[2][0] + xGrid[2][1] + xGrid[2][2];
oRowCounts[0] = oGrid[0][0] + oGrid[0][1] + oGrid[0][2];
oRowCounts[1] = oGrid[1][0] + oGrid[1][1] + oGrid[1][2];
oRowCounts[2] = oGrid[2][0] + oGrid[2][1] + oGrid[2][2];
xColCounts[0] = xGrid[0][0] + xGrid[1][0] + xGrid[2][0];
xColCounts[1] = xGrid[0][1] + xGrid[1][1] + xGrid[2][1];
xColCounts[2] = xGrid[0][2] + xGrid[1][2] + xGrid[2][2];
oColCounts[0] = oGrid[0][0] + oGrid[1][0] + oGrid[2][0];
oColCounts[1] = oGrid[0][1] + oGrid[1][1] + oGrid[2][1];
oColCounts[2] = oGrid[0][2] + oGrid[1][2] + oGrid[2][2];
xDiagCounts[0] = xGrid[0][0] + xGrid[1][1] + xGrid[2][2];
xDiagCounts[1] = xGrid[2][0] + xGrid[1][1] + xGrid[0][2];
oDiagCounts[0] = oGrid[0][0] + oGrid[1][1] + oGrid[2][2];
oDiagCounts[1] = oGrid[2][0] + oGrid[1][1] + oGrid[0][2];
// Tries to win
[ self seekCpuMove: oRowCounts : oColCounts : oDiagCounts : &cpuRow : &cpuCol : 2 ];
// Tries to stop other player from winning
if(cpuCol == -1 || cpuRow == -1)
[ self seekCpuMove:xRowCounts : xColCounts : xDiagCounts : &cpuRow : &cpuCol : 2 ];
// Tries to find a place where it has a better chance at winning
if(cpuCol == -1 || cpuRow == -1)
[ self seekCpuMove: oRowCounts : oColCounts : oDiagCounts : &cpuRow : &cpuCol : 1 ];
// Tries to find a place where is has a better chance at stopping the other player from winning
if(cpuCol == -1 || cpuRow == -1)
[ self seekCpuMove:xRowCounts : xColCounts : xDiagCounts : &cpuRow : &cpuCol : 1 ];
NSLog(@"cpuRow=%d cpuCol=%d", cpuRow, cpuCol);
if(cpuCol == -1 || cpuRow == -1)
{
[ self cpuMakeMove ];
[ makeMovePool release ];
return;
}
cpuTag = ((cpuCol + 1) * 10) + (cpuRow + 1);
_isLocked = NO;
switch(cpuTag)
{
case 11: [ self tileHasBeenSelected: btnA1 ]; break;
case 12: [ self tileHasBeenSelected: btnA2 ]; break;
case 13: [ self tileHasBeenSelected: btnA3 ]; break;
case 21: [ self tileHasBeenSelected: btnB1 ]; break;
case 22: [ self tileHasBeenSelected: btnB2 ]; break;
case 23: [ self tileHasBeenSelected: btnB3 ]; break;
case 31: [ self tileHasBeenSelected: btnC1 ]; break;
case 32: [ self tileHasBeenSelected: btnC2 ]; break;
case 33: [ self tileHasBeenSelected: btnC3 ]; break;
}
[ makeMovePool release ];
}
Go ahead and try for yourself! Make your own version of this code, we beg you!!!!! If you make a good one, we will credit you and give you a change to get your name on something that is on the Apple App Store