The programming paradigms available in Mathematica together with the level of generality that can be obtained through its symbolic capabilities can be applied to a wide range of programming situations, particularly the rapid prototyping of applications. This article shows our use of this outstanding computational environment to develop playable prototypes of board games and explore game strategies. Mathematica features allow some general ad hoc design patterns for such games to be expressed, applied, and further refined. We show the benefits of such an approach—lots of code reuse, clearer design and programming, and ease of experimentation—by exhibiting our work on three different board games. We further show how the statistical and mathematical techniques available with Mathematica can be used to generate reports on the playability of a particular game as well as to develop winning strategies. We also show how J/Link and GUIKit can help refine and improve the interface of a game.

Introduction

Chess, backgammon, Abalone, Go, Tic-Tac-Toe, Mine Sweeper, Tetris, and many others are well-known examples in the large collection of so-called board games [1]. Board games provide many interesting topics of study for several academic disciplines, which have their own scientific societies and journals [2]. Board games are also very popular among freeware and shareware users. There are many ways to play against a machine, running the code online as an applet or servlet, or on a personal computer, a PDA, or even a mobile phone.

Developing a computerized version of a board game is an exciting challenge and a very good exercise for computer science students. From the theoretical point of view, the implementation of the evolution of a game usually involves a wide range of classical algorithms as well as implementation of the strategies played by the computer. It is also important to keep in mind that the fun derived from playing a game often critically relies on a nicely designed and efficient user interface.

Incorporating different kinds of programming paradigms, Mathematica [3] embeds a highly flexible and intuitive language for prototyping applications. Using a computational environment such as a development platform allows for a generic and high-level representation of the board and its evolution. It also makes development and testing of board game strategies easier.

The notebook environment is powerful enough to set up the interface between the game and the player and offers a good visualization of the board. However, even with careful and sophisticated development the graphics are not fancy enough to be addictive to players. Fortunately, with the help of Java toolkits, namely J/Link and GUIKit, the functionalities of Abstract Window Toolkit (AWT) and Swing [4] are within reach and permit the dream of an interface being developed with only a small effort.

In the first part of this article, we describe a generic design pattern for the implementation of board games. Actually such a game is uniquely and completely defined by a quite small set of information concerning the representation of the board, the playing rules, the initialization phase, and the termination phase. From this set of information and with the help of the generic design pattern, we can quickly develop a playable and smart implementation of the game.

Examples of such developments are given in the second part of the article where we describe in detail the full playable implementation of

1. HMaki—a Japanese puzzle game (a.k.a. Same Gnome by Linux users)
2. a classical lines game
3. Mancala—a well-known African game (a.k.a. Awale)

For each of these examples, we also provide a tutorial approach to the development of a fancy graphical user interface using Java technology with the help of J/Link and GUIKit.

The last part of the article is devoted to the exploration of strategies. One benefit of developing our own implementation of a board game with Mathematica is that it yields perfect control over the different steps of each game, the ability to unplay or to replay some or all of those steps, to add or remove randomness, and to add or remove interactivity during the game. Mathematica also makes it easier to implement and apply strategies and perform, on a large set of examples, statistical analysis on the resulting games.

A Design Pattern for 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.

Some Semantics

Before going further, let us explain in detail what is exactly meant by game, board, play, and rules.

Game

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:

• an initialization phase when the game starts or restarts
• a playing phase (i.e., when the user is playing). This is the most common behavior of the game and consists in a sequence of successive plays.
• a termination phase at the end of the game

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.

Board

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.

Play

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!

Rules

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:

• A new piece should be contiguous to a piece of the other color.
• There must exist a segment (horizontal, vertical, or diagonal) starting at the new piece and ending at a piece with the same color containing only pieces of the other color.

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.

Initialization

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:

• removing a piece from the board
• adding a piece to the board
• moving a piece

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.

Notebook Visualization

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.

The HMaki Example

Figure 5. The board of SameGame, the Gnome/KDE version of HMaki.

Let us try our design pattern for implementing this board game (Figure 5).

Configuration of the Board

We give some values for the size of the board and the number of colors. We also set the flag for randomness.

Positions of colored tiles are given by a succession of calls to the pseudorandom number generator.

Visualizing the Board

We are now able to initialize the game.

Choosing some colors, we can define the function View for a nicer display of the board.

Transition Function

To deal with corner and boundary situations, we define the BoardValue function to access the values of the board. It returns if the arguments for location are outside the bounds of the board. This allows us to ignore the boundaries of the board when considering the neighbours of a location.

The positions of neighbours are computed by the following two functions.

To get the spot enclosing the selected location, (i.e., the neighbourhood of locations with the same color), we use a fixed-point algorithm applied to a neighbourhood extension function.

IsPlayable is now easy to implement: only a non-empty location within a spot of at least two can be played. The result of the function is the list of the locations within the spot.

PlayBoard will “remove” the spot from the board, propagating individual tiles to the bottom and columns to the left whenever it is possible.

Main Loop

To check whether the game is over, it is necessary to decide if there remain two spots of the same color contiguous by a face.

Interaction with the player here is very basic.

And we are able to play—but the interface is a bit cumbersome.

With a Notebook Interface

To improve the interface, only one function has to be defined: one which colors the buttons and manages the end of the game (Figure 6).

And we are able to play without the keyboard!

Figure 6. A view of the notebook interface of the board of HMaki.

Playing Lines

Figure 7. The board of the five-star version of the game Lines.

Once again, the design pattern will help us quickly implement this game (Figure 7).

Configuration of the Board

The following values define the physical parameters of the board.

Initially, the board is empty.

But before the first play, the computer makes three balls appear.

The colors of the next three balls to be added are selected in advance and must be shown to the player to help him play. They are selected randomly by the Next function and kept in a global variable, NextBall.

Adding Balls

The positions at which to add the balls are also selected randomly in the list of the empty positions.

RandomElement is a miscellaneous function randomly selecting an element of a list.

Visualizing the Board

Let us initialize the game and visualize it.

With some colors and a few graphics primitives, we are able to display the board and the next three balls.

Transition Function

In this game, a play consists of three possible successive actions: selecting and adding three balls, moving a ball, and deleting a line of balls. When a player selects a ball and a new location for it, this ball is moved. If possible a line is deleted and the computer adds three balls, possibly deleting a line.

Moving Balls

To decide whether a motion is valid or not, we again use a fixed-point algorithm applied to a neighbourhood extension function: the set of reachable positions is incrementally built from the starting position by exploring empty locations.

We reuse the function BoardValue to simplify the computations of the neighbourhood.

Neighbour is slightly different than FaceNeighbour from the previous example.

Possible searches for empty locations in the neighbourhood.

The fixed-point algorithm is performed by IsPlayable, which returns a Boolean.

PlayBoard updates the board, checks for lines of five balls to delete, and adds three balls.

Checking for Lines to Delete

To check if there is a line of five balls to delete, we try to extend the position in four (nonoriented) directions as long as the color of the ball remains the same. This is performed by Extend.

DeleteBall suppresses the balls from the line.

And NewLine is the top-level function, returning a Boolean.

Main Loop

Playing

The game continues until fewer than three slots are available for the balls.

Once again, the interface with the player is extremely basic.

But we can play!

A Notebook Interface

To cope with the display of the “balls to come”, it is necessary to adapt the NBView function and develop the dedicated function NBNext, which is similar to NBBoard.

To select two locations, the player clicks twice in a play on the board. This is taken into account through the variable FromLoc and by a small difference in the implementation of NBPlayThere.

With the notebook interface, playing becomes easier, even if the graphical design is not so nice.

Mancala: A Two-Player Game

Figure 8. A board of 4 x 8 Mancala.

Mancala is the ancient game of counting and strategy where each player must attempt to collect as many stones as possible before one of the players clears his side of stones (Figure 8). There are many versions of this traditional game.

Here are the rules of the version we will implement:

Configuration of the Board

The following values define the physical parameters of the board (i.e., in our example a set of six cups for each of the two players). The last column of each row corresponds to the mancala of the player. The patterns are the number of stones in a cup.

Initially, the stones are equally distributed in the cups.

We use an additional global variable, Player, to manage the players.

Visualizing the Board

A very basic visualization of the board is sufficient for playing—mancalas are separated.

Transition Function

In this game, playing is just selecting one of the cups. IsPlayable only verifies that the selected cup is not empty.

The rules of the evolution of the board are much trickier to implement as many different cases may arise. GiveStone redistributes the stones of the selected cup.

Other just permutes 1 and 2, while PlayBoard manages the complete evolution of the board.

Main Loop

The game ends when one player’s cups are empty.

For this game, the basic textual interface for playing is quite convenient, as the player is only asked for one digit at each play.

When one player has no more stones, the other player puts all his remaining stones in his mancala. This is implemented by a refinement of the function EndGame.

Interface with GUIKit

Although we have succeeded in easily building a graphical interface for playing using the notebooks and buttons in them, the result is very poor in terms of graphics and functionalities.

Until a new version of graphics management exists in Mathematica, there is no way, within notebooks, to make a part of a graphic object active. But GUIKit makes the power of J/Link and the richness of AWT and Swing Java libraries accessible.

In this section, we go back to the HMaki example and show how to build a nice and efficient interface with this new package.

Visualizing the Board

GUIKit provides , which allows us to display an array or rectangles with different colors. Very few settings are necessary to represent the HMaki board with this widget.

To transform this widget into an active one, we have to bind the event of clicking with the mouse to the action of playing and refreshing the board.

A JPlayGame function is then defined, initializing the game, loading, and running the interface definition.

Here comes the playable Java version of HMaki!

Adding Interactivity

We now would like to be able to start a new game or replay the current game directly from the interface.

A good way to implement this interactivity is to define for each action and attach the corresponding Script to it. The script can refer to any Mathematica function, provided its context is within the scope of the script. Here, we use the function NewGame in our scripts.

It is then easy to define a menu, associating an action to each of the menu items

or associating actions with buttons.

Adding Scores

When you play HMaki, you can target various goals: suppressing as many tiles as possible, having as many tiles as possible once all the groups have been suppressed, suppressing as many biggest groups as possible, and so on. From the board, it is possible to compute a score, which measures how close to your goal you are.

Computation

The simplest score function computes the number of tiles on the board.

Visualization

To get the score on the interface, we should first set a label widget to show it as text.

We should also modify what happens when the mouse is clicked inside the board (i.e., change the definition of MouseClickBinding).

The previous command produces the Java interface (Figure 9).

Figure 9. GUIKit-generated Java version of HMaki.

Analysis and Strategies

In this section, we will show how easy it is to make the computer play on its own in order to analyze games or analyze, study, and improve playing strategies. We will focus again on the HMaki game, which is complex enough to demonstrate how powerful the analysis can be with our design.

Automatic Play

As randomness is involved in the initialization of the game, we need to play repeatedly to study the game with statistical tools. So the computer should be able to play a game alone and give us feedback on it.

Scoring

We are interested in the final score and the number of plays necessary to reach the end. Moreover, we consider two kind of scores: the number of remaining tiles and the sum of the scores obtained for removing each group of tiles—growing with the square of the size of the group. The global value Score contains a list of this information; it is initialized by InitScore and updated by UpdateScore.

Where to Play

Before playing, the computer should know where it is valid to play and then where to play. The function PlayableList computes the list of all the playable locations on the board, using an almost trivial algorithm.

The GetPlay function is rewritten to randomly select an element in the list of playable locations.

Playing

We define BatchPlayGame, an analog function to PlayGame, to make the computer play. Note the presence of the bound MaxPlay to avoid infinite loops and the call to SeedRandom to control random initialization of the board and select a play among the list of possible beginnings.

In the preceding results, the high computation time is due to the poor implementation of PlayableList: 76 is the number of plays in the game; 270 is the score when “playing for big”; and 60 is the number of remaining tiles.

Statistical Analysis

Once the computer is able to play alone and produce information on the game, we can make it play enough games to give us statistical results. Let us conduct an experiment.

Playing 100 Games

The first experiment consists of playing 100 different games; the second in playing the same game 100 times.

Statistical standard functions describe the dispersion of this data.

We can view the data using standard graphical functions for plotting.

The fairly even dispersion we observe in these graphics is a testimony to the interest of the game for a human player.

Strategies

Another goal of statistical analysis is to compare strategies and get a better understanding of how to play.

Groups

Simple strategies for playing HMaki are based on knowledge of the different groups of tiles of the same colors. The SpotList function returns the list of the groups computed from the board.

Strategies

A new version of BatchPlayGame takes an integer argument as an index of the selected strategy, and an option for visualization.

Different instances of GetPlay correspond to different strategies of selecting the group of tiles to remove:

1. the group is randomly selected in the list of groups
2. the group is randomly selected among the biggest groups
3. the first biggest group (starting from the upper-left corner, then from left to right and top to bottom)
4. the group is randomly selected among the smallest groups
5. the first smallest group (starting from the upper-left corner, then from left to right and top to bottom)

Experiment

Results of 170 games were collected—10 different games played 17 times: five times for the strategies involving randomness, only once for the two others. These results took several minutes to produce.

The following command produces the results in Table 1.

We can also visualize these results with an ad hoc plot function. The following plots show the numbers of remaining tiles for the first strategy.

Conclusion

This exercise proved that a couple of hundreds lines of Mathematica code are enough to completely implement three playable prototypes of board games together with the corresponding basic graphical user interface, plus an attractive Java Swing version of one of them. With the design pattern presented, we demonstrated that most of this code will be reusable with minor changes for implementing other board games.

As playing is one of the oldest human activities, trying to understand how the games work and why some of them are so addictive could be a recreational and exciting challenge. The library of applications that we created could be extended to different games. Many strategies could be implemented and tested, even on our three examples, to better understand and enjoy them.

References

About the Author

Yves Papegay has been a computer science researcher at INRIA Sophia Antipolis in southern France since 1994. One of his major research interests is symbolic computation methods, tools, and applications to modeling and simulation processes.

Papegay joined the French team of the Wolfram Education Group in its early weeks. He is a daily user of Mathematica and has developed several application packages for industrial purposes.

Yves Papegay
INRIA Sophia Antipolis
COPRIN 2004 route des Lucioles
F-06902 Sophia Antipolis
France
Yves.Papegay@sophia.inria.fr