Volume 10, Issue 2
In and Out
Download This Issue
Staff and Contributors
Exploring Board Game Strategies
A Design Pattern for Board Games
"So, in a broad sense, a board game is any that can be played on a flat surface such as a table or floor." David Parlett, Oxford History of Board Games
As quoted, the most important point when designing a board game implementation is to have a proper idea of the board itself, which represents the complete status of the game at each play and the rules that determine whether or not a play is legal.
In our design, we should keep in mind that we want the computer to analyze several games, to replay some of them, and to test some strategies.
Before going further, let us explain in detail what is exactly meant by game, board, play, and rules.
The game denotes a complete set of interactions between the program--or the physical support of the game, whatever it is--and the player. Hence, it is a succession of three phases:
Figure 1. Windows' famous Minesweeper board.
In the case of the well-known Minesweeper game (Figure 1), the initialization phase locates the mines on the board and hides all the locations; the playing phase consists, for the player, of de-mining by selecting one location at each play and getting back the information on the adjacent locations. The termination phase is what happens when a mine explodes or when the player discovers the last mine.
The board represents not only the physical board but, by extension, the complete status of the game at a given time. By definition, in a board game, this status is well defined by a mapping between a two-dimensional set of locations and additional information (usually qualitative or discrete) for each location.
Figure 2. A chess board.
In the case of chess (Figure 2), the physical board is simply made of 64 squares, given by their line and column references. We also consider as part of the board the information, for each square, of the color and kind of piece (if any) occupying it.
By definition, a play is one step of the playing phase. At each play, the player has to select which action, among the legal (valid) ones, to perform. In most of the games, such an action is completely defined just by selecting one or two locations on the board. In other games it may involve some random process represented by additional parameters, such as the result of dice throws in a backgammon game (Figure 3).
Figure 3. A backgammon board.
The information contained on the board and given by the player should be sufficient to decide whether the selected play is valid with respect to the rules of the game.
To execute the play, the computer has to ensure that the play is valid and then modify the status of the game.
If the computer is also supposed to act as a player, it must then analyze the game, select which action is the better one, and play it. Its doing so is another play, however!
The rules are the set of constraints that determine what can be played and how the status of the game should be modified by a play.
Figure 4. An Othello board before black's play.
In Othello (Figure 4), the rules state that to put a black piece somewhere it should enclose white pieces. The rules could consist of:
So, if we denote the rows from top to bottom by A, B, C, ... and the columns from left to right by 1, 2, 3, ... , black can only play at B2, C1, C6, D1, D2, D6, D7, and E7.
The rules should also state that enclosed pieces will change color after the play. For example, if black is played on D6, then the white pieces in D5, E5, E6, and F4 will be turned to black.
Designing the Board
What differs from one game to another concerning the board is its size, in rows and columns, and the possible values ( patterns) for each of the locations of the board.
For simplicity and readability of the code in this article, we decided to make extensive use of global variables, rather than providing a lot of arguments to functions. In a less experimental implementation, we would have used packages and contexts to avoid occasional shadowing of symbols. Here, we use three variables (Width, Height, and Patterns) to describe the configuration of the board and an additional one (Board) to store the board itself. To give a better picture, we use a chess game, as an example.
In most of the cases, the board can just be described by a list of lists of integers and the definition of a mapping between integers and patterns--giving the patterns as a sorted list is sufficient for that. The computation time of the algorithms involved in validating plays and modifying the board is usually negligible due to its size, and it is not necessary to further optimize the representation of the board.
The board is computed for the first time during the initialization phase by the generic NewGame function.
When no randomness is involved in the game (e.g., in chess or Othello), a configuration flag, NeedRandomness, is set to False, and the NewGame function only initializes the board and possibly performs an initial play.
When some randomness is necessary, we will provide a seed as an argument to control the randomness and to be able to replay the same game. In this case, the seed of the pseudorandom generator is stored in a variable (Seed) to allow replaying the same game--when it is possible. Without an argument, the last value of Seed is used as a seed.
With the string "new" as the argument, a randomly generated seed is used and then stored.
This ability to replay a game is a valuable feature to players who want to exercise their skills and improve their strategies.
InitBoard is another generic function that builds the board and returns the corresponding matrix as a list of lists. It is based on InitPosition, whose definition is unique and characteristic of each board game.
In the example of the chess game, the initial positions are as follows.
This produces the usual representation of the chess board at the beginning of the game.
Implementing the Transition Function
For most of the board games, playing is just doing one of these three kinds of actions:
So, from an implementation point of view, playing amounts simply to changing the status of one (or two) position(s) of the board and can be completely defined by giving the corresponding location(s) on the matrix as arguments to the transition function. A few games, such as backgammon, may let the player move several pieces during the same play. These cases require further refinement of the function.
Of course, only some positions are playable and, for a selected piece, only some motions are valid with respect to the rules of the game. Those constraints require us to check the arguments of the transition function before its application.
Hence, the generic transition function PlayThere relies on two nongeneric functions: IsPlayable, which performs the checking, and PlayBoard, which changes the board.
FalseQ is analogous to the standard TrueQ function and returns True only when its argument is False.
Many algorithms and computations can be invoked by IsPlayable depending on the complexity of the rules of the games. Usually, however, this computation will also provide information on how the board will change due to the play. For example, in chess, if you plan a play to capture a piece, checking this plan will produce the capture as a side effect. So, the results computed by IsPlayable usually affect PlayBoard. In the implementation, the value returned by the first function is given as an argument to the second.
Main Loop and Interaction with the Player
The main loop defines the game as a sequence of plays. It may be used for an interactive game and for batch games for analysis purposes. The generic function PlayGame implements this simple loop. We will show how to implement interaction through a notebook graphical interface.
Interaction with the player is made through View--for visualization--and through GetPlay. GetPlay may be used to apply a strategy in a batch game or to prompt the user for the selected play in an interactive game.
The termination phase of the game is performed by EndGame, which can be refined for a particular game but has this simple default value.
A Mathematica notebook, or a palette, can be used for a first approach to graphical visualization and a graphical user interface for a game. Here, we represent the matrix of the board with an array of buttons with text (or a color) for the pattern corresponding to the location. Each of the buttons invokes a transition function--defined in terms of PlayThere--with its location as the argument. Control of the game is made directly through the calls and no loop is necessary.
The generic function for playing a new game is NBPlayGame, which is analogous to PlayGame.
NBPlayGame displays the notebook created by NBView.
Inside NBView, NBBoard generically creates the array of buttons.
The only nongeneric function to develop when implementing a game is NBMakeButton. It has to take in account the transition of the board at each play, manage the end of the game, and refresh the display. For those purposes, NBMakeButton can use the generic NBPlayThere and NBRefresh. See the following examples for details of implementation.
About Mathematica | Download Mathematica Player
© 2006 Wolfram Media, Inc. All rights reserved.