Building a Game Engine with Cocoa, Part 3by Matthew Russell
In the grand finale of this three-part series, we'll finish up the infrastructure for our Lines of Action (LOA) game. In this rendition, we'll do some basic refactoring of the work from last time, introduce the logic for determining game-over conditions, and implement a game tree search called negamax--a variant of minimax that uses alpha-beta pruning to reduce the search space. If you'd like to download the finished project file and use it to follow along as you read this article, you may do so by clicking here.
At the end of this article, you'll have a working LOA game, complete with a built-in computer opponent that plays against you based upon a custom heuristic that you define.
By the end of the previous article, we had developed a nice game board that enforced making valid moves and displaying them to the user. Although the user interface looked fine, the code underneath was starting to get cluttered and there were at least a couple of fairly obvious weaknesses that would have been nice to change. Namely, our coordinate system was relying on
NSPoint, which is a struct defined in the Foundation framework, and we weren't using categories to compartmentalize our code into logical groupings of related methods.
The primary problem with using
NSPoint to represent our coordinate system is two-fold. Semantically, it doesn't make sense to represent discrete coordinates on a checkers board as float values, and as a related consequence, we have to continually cast the coordinate components into integer values whenever we want to access a value in the
board array. Since our game tree search algorithm will be almost constantly accessing and manipulating the
board array, we'll get a noticeable increase in performance for "free" by defining a custom structure (
Coord) that consists of two integer components instead of relying on
NSPoint. As we'll see a bit later, we'll want to do anything we can to make our game tree search as efficient as possible.
Coord is defined in
The other issue mentioned was code clutter. The approach we'll use to declutter our code is employing a category. A category is a powerful Objective-C mechanism for adding additional functionality to an existing class (maybe even one like
NSString for which the source code is not available.) We'll use categories for their lesser-known benefits of breaking up a single large object into smaller, more manageable chunks. Although it's fine to use categories for this purpose, it should be pointed out that using categories to compartmentalize code can be like a double-edged sword if misused. On the one hand, categories give you distinct source files to help manage complexity. On the other hand, categories can lead to lots of confusion because code gets tedious to follow when methods of the same class are spread out in all different places.
Here's our basic breakdown of what could have remained one big GameBoard class:
- GameBoard - The core class that defines primary data structures and contains the core logic for drawing on the screen and playing the game.
- GameBoard+Util - A small category containing some useful macros and two C++ methods that facilitate creating the
- GameBoard+Moves - A category that wraps up the core logic for move generation.
- GameBoard+AlphaBeta - A category used for encapsulating the search algorithm and any heuristics used by it.
- GameBoard+Connection - A category that exposes a single C++ method for checking connectedness.
In addition to reflecting a new
Coord struct that replaces the previous
NSPoint references, introducing a new
GameBoardMove struct that abstracts two
Coord structs into the concept of a move, and employing categories, a few other tweaks have also taken place. One important modification is that all previous method parameters that were defined as
int for purposes of passing the
board array around are now fully qualified as
int[DIMENSION][DIMENSION]. In addition to being a good practice, this change is necessary to successfully compile the code with GCC 4.0 and beyond.
Also note that since we're starting to introduce C++ code, Xcode requires that files containing or calling any of our custom C++ functions be renamed as *.mm files instead of *.m files. This is a small price to pay for getting instant access to things such as the STL, which we'll be using underneath the hood. Finally, there are no longer references to the class formerly known as
AppController. (The last installment illustrated how you could fetch the
board array and get it into
AppController, if you prefer a design that requires you to pass the underlying
board array outside of the
After tidying up a bit, we can now finish the project. As you already know, the objective of the game is for a player to connect all of his pieces together. Thus, determining connectedness is necessary for determining game-over conditions as well as potentially being very useful in the heuristic that is used in the game tree search. It is interesting to note that LOA is especially unique with respect to ending board positions, because the objective of the game is to connect all of your pieces together. It doesn't matter if they're spread out in a big long line, packed densely together in one huge cluster, or wrapped around in ring structure.
Since checking for connectedness will be a commonly used operation, we'll want it to be as efficient as possible. We could certainly implement the method for checking connectedness in Objective-C, but as a critical operation that will likely be executed thousands and thousands of times with each turn of the computer opponent, we'll take advantage of C++'s
vector data structure, which allows us to group
Coord structs without having to first wrap them as
NSValues, as we do with
NSArray. Recall that we are currently still doing this with the
COORD_OBJECT macro (previously
validMovesFromSpot: defined in GameBoard's Moves category.
The basic technique we'll use for checking a player's connectedness is simple:
- Find any piece in the game board for the player.
- Perform a search and erase all pieces that are in the same cluster as piece.
- If any other piece for the player is found afterward, return NO. Otherwise, return YES.