Last.
Figure 2. The board after several valid moves from both sides.
With a spiffier user interface in place, we'll now turn our attention to generating moves for our game. What appears to be the official Lines of Action page lists a few basic rules:
We'll implement a move generator for these rules, but wait until next time when we develop a routine to check for "gameover" to handle the corner cases that may arise.
To get started with move generation, we'll implement a routine that computes the total number of pieces in each "line of action," given a spot on the board. For any given board position, we'll inspect the board from the starting spot in the following manner: up/down, left/right, up/right, then down/left, and finally, up/left, then down/right. Remember, all that matters is the total number of pieces in each of those four lines, so we'll only be returning a total of four values.
To make our lives a little easier, we'll introduce a helper
struct to encapsulate these four values, which we can pass off to another routine that will use this information to help generate the actual moves. Here are the necessary additions so far:
typedef struct { int up_down; int left_right; int up_right_down_left; int up_left_down_right; } LineCounts; - (LineCounts)lineCountsForSpot:(NSPoint)spot { //up down int up_down = 0; int y; for (y=0; y < DIMENSION; y++) if (board[(int)spot.x][y] != EMPTY) up_down++; //left right int left_right = 0; int x; for (x=0; x < DIMENSION; x++) if (board[x][(int)spot.y] != EMPTY) left_right++; //up right, then down left int up_right_down_left = 0; x=spot.x; y=spot.y; while (x < DIMENSION && y < DIMENSION) { if (board[x][y] != EMPTY) up_right_down_left++; x++; y++; } x=spot.x; y=spot.y; while (x >= 0 && y >= 0) { if (board[x][y] != EMPTY) up_right_down_left++; x--; y--; } //remove duplicate count if (board[(int)spot.x][(int)spot.y] != EMPTY) up_right_down_left--; //up left, then down right int up_left_down_right = 0; x=spot.x; y=spot.y; while (x >= 0 && y < DIMENSION) { if (board[x][y] != EMPTY) up_left_down_right++; x--; y++; } x=spot.x; y=spot.y; while (x < DIMENSION && y >= 0) { if (board[x][y] != EMPTY) up_left_down_right++; x++; y--; } //remove duplicate count if (board[(int)spot.x][(int)spot.y] != EMPTY) up_left_down_right--; LineCounts lc = { .up_down = up_down, .left_right = left_right, .up_left_down_right = up_left_down_right, .up_right_down_left = up_right_down_left }; return lc; }
Using the information provided by the
LineCounts struct and the board, we can easily start at a given spot and search in each of the eight possible directions to determine if any moves are available. For each direction, we only need to ensure a few conditions:
Each of these conditions can be wrapped up as a piece of a large conditional logic statement; in our case, we even use some of the recently discussed macros to make the code a bit tidier and readable. The only remotely challenging of these three conditions is detecting when opponents stand between a piece and its destination, so it's nice to wrap this one up in its own routine. A snippet of one possible approach,
opponentInLineBetweenCoord:andCoord:, is shown below and illustrates vertical detection of an opponent. All seven of the other directions work exactly the same way.
if (c1.x == c2.x) { if ((int)(c2.y-c1.y) > 0) { //up int dy; for (dy=c1.y; dy < c2.y; dy++) if (OPPONENT_AT(c1.x,dy)) return YES; } else { int dy; for (dy=c1.y; dy > c2.y; dy--) if (OPPONENT_AT(c1.x,dy)) return YES; } }
One other detail associated with move generation involves the desire to pass back the
NSArray from the
validMovesFromSpot: function. Since
NSArrays only house objects descended from
NSObject, we won't be able to directly add our
NSPoint structs to it. Apple, however, realized the convenience of passing around some of the most common structs and provides another class,
NSValue, which we can use to wrap
NSPoints whenever we'd like to add them to an array. This is precisely what we do inside of the
POINT_OBJECT macro, and it works like a charm.
Without further ado, meet
validMovesFromSpot:. Like other functions we've encountered so far, the same basic logic is in place for checking all eight directions, so a portion of the code is omitted inline below. The sample project, of course, contains all of the code for the entire project.
-(NSArray*)validMovesFromSpot:(NSPoint)spot { //make sure spot is occupied or else there's no move if (board[(int)spot.x][(int)spot.y] == EMPTY) return [NSArray array]; LineCounts lc; lc = [self lineCountsForSpot:spot]; NSMutableArray *moves = [NSMutableArray arrayWithCapacity:8]; //up if ( spot.y + lc.up_down < DIMENSION && PLAYER_MOVING_NOT_AT(spot.x,spot.y+lc.up_down) && OPPONENT_NOT_BLOCKING(spot,spot.x,spot.y+lc.up_down) ) [moves addObject:POINT_OBJECT(spot.x,spot.y+lc.up_down)]; //down if ( spot.y - lc.up_down >= 0 && PLAYER_MOVING_NOT_AT(spot.x, spot.y-lc.up_down) && OPPONENT_NOT_BLOCKING(spot,spot.x, spot.y-lc.up_down) ) [moves addObject:POINT_OBJECT(spot.x, spot.y-lc.up_down)]; //snip... //left,right,up right, down left, up left, down right //snip... return (NSArray*)moves;
Recalling that
validMovesFromSpot was called all the way back in
mouseDown:, we've now completed the circuit and grown the project to the point that two users could sit down at the keyboard and take turns moving until one of them identifies a gameover condition. Next time, we'll implement gameover checking and a few final details before delving head first into a game tree search where we will develop an AI opponent using some custom heuristics.
To prepare you for next time, the sample project already includes a hook in
AppController's called
validMovesFromSpot:withBoard:, which we'll be able to use for querying the game board about particular moves that are available from our game tree search. The implementation details are fairly straightforward and totally reuse existing code by temporarily swapping out the
GameBoard's instance variables
board and
playerMoving whenever it is invoked. Since all move generation logic depends on these two values, they're all we need to modify in order to produce a list of moves.
If you prefer to work on your own copy instead of using the sample project provided, be sure to remember to set the outlet for
AppController's
gameBoard, as shown in Figure 3, when you're trying to reference the
gameBoard from within
AppController.
Figure 3. Don't forget to set
gameBoard's outlet in
AppController
And while we're at it, there's also a method in
GameBoard called
board that simply returns a lightweight wrapper around the actual 2D integer array used to keep track of pieces. An illustration of this method is also in
AppController's
awakeFromNib method. In the next episode, the plan is to use this data board to feed our game tree search.
Have fun tinkering around with what we have so far until next time. As always, feel free to leave your thoughts, feedback, and suggestions below.
Matthew Russell is a computer scientist from middle Tennessee; and serves Digital Reasoning Systems as the Director of Advanced Technology. Hacking and writing are two activities essential to his renaissance man regimen.
Return to the Mac DevCenter.