Unlike tic-tac-toe, Pente is played on a variable-sized square board: 5x5, 10x10, etc. The game is played by two players, each with different pieces. The goal is to
make a line with five pieces. The line may be horizontal, vertical or diagonal. Once a
piece has been put on the board it cannot be removed. Nor can a piece be placed in the
same place as another piece.
There are two possible outcomes for the game. Either a player wins by making a line with
his pieces or there is a tie because it is no longer possible to make a line with any of
the player pieces.
With the above description we can make a domain analysis for the game. Here
is the resulting list of concepts:
||A person or system playing Pente.
||A square matrix on which pieces can be placed.
||A line of pieces of the same player. Lines may be horizontal,
vertical or diagonal.
||A player who has made a line with 5 or more pieces.
||A game in which it is no longer possible to make a line
||A piece must be placed in an unoccupied "cell" of
the board. Each time a piece is placed two goals must be taken into account:
The player will try to make a line of five pieces, and the player will try
to prevent the opponent from making or completing such a line.
The hardest and most important issue regarding the game is how we can determine the
position in the board where the computer will place a piece. According to the goals of
piece placement we have two basic ways of choosing:
- Following a purely defensive strategy, we will try to detect the lines our
opponent can make and place a piece at some point which blocks his line.
- Following a purely offensive strategy, we will try to detect all the lines we can
make and place a piece in any of the positions which are part of a line.
Of course, we have a third option, too, which is to combine both of these strategies so
the computer player can be partly offensive and partly defensive.
In order to keep track of the possible locations for a piece we will use a
"weight" matrix. For the offensive strategy we will add weight to every
cell which is part of a line we can complete. For the defensive strategy, we will add weight to every cell which is part of a line that our opponent can complete.
A line that can completed consists of a combination of adjacent cells which are either
blank or contain our own pieces. The code used to determine if a line can be completed
looks like this:
procedure tpenteGame.line(x, y, size: integer;
dir: tlinedir; AnOponent, AcalcWeight: boolean);
//set the count incrementing piece and the
//count stopping piece
setIncStop(linc, lstop, anOponent);
for i := 0 to size -1 do begin
// Increment piece count
if n = linc then begin
// interrupted line
else if n= lstop then begin
pieceCount := -1;
Once that we know if a line can be completed we will add weights to every cell it
touches. Of course, lines which can no longer be completed will get no weight added.
code above can be modified to determine if a player has won. Whenever the
number of pieces of a line reaches five we will know the line is complete and a player has
won. The same code will tell us if it is no longer possible to have a
winner if after evaluating all the possible lines for the board we can't find at least one
line which can be completed.
In a tic-tac-toe game there are eight possible winning lines (three horizontal,
three vertical, and two
diagonal). The number of winning lines in a Pente game is given by the
N = (2 * size * delta) + (2 * delta^2)
Size is the size of a board, and delta is the size of the board plus one minus the size of the line.
Hence, for a 10x10 board with a line size of five the number of winning lines would be:
(2 * 10 * 6) + (2 * 6 * 6) = 192
These 192 lines are composed of 60 horizontal lines, 60 vertical lines, and 72 diagonal lines.
This code verifies each line in order to calculate the weights for each cell:
itop := (self.fsize - self.flineSize)+1;
for y := 1 to self.fsize do begin
for x := 1 to itop do begin
for y := 1 to itop do begin
for x := 1 to self.fsize do begin
for y := 1 to itop do begin
for x : = 1 to itop do begin
for y := 1 to itop do begin
for x := self.fsize downto (self.fsize +1 )-itop do begin
Once we have verified each of the lines and calculated the weights for every cell, we
will pick the cell with the highest value and place our piece there.
Of course, it is
extremely important to choose the right weights to add to our weight matrix
according to the number of pieces in each line. There are two sets of values: one for the
opposing player and one for the system player. The particular set of values I
use reflects the fact that the last two pieces of a line must be blocked or
filled as soon as possible. This is so because normally a line has two ends and both ends
have to be blocked.
By giving the same weights for the opposing array and the system array, we ensure
have the same relevance -- which means the program will play balancing offensive and defensive
|Number of Pieces
|N-3 .. 1
||N div 2
In order to keep the project at least slightly object-oriented, the game and the
playing strategy have been encapsulated into the TpenteGame class.
To create a new game, you must specify the board size and the line size. The line size
must be less than or equal to the board size.
You can place and retrieve a piece with the
setBoard and getBoard methods. To pick the cell in which the next move will be made,
use the ChooseCell method. You must indicate whether you want to apply a defensive
strategy or an offensive-defensive one.
In order to create a strategy game one must ensure that the following elements are
present in the program: A board, a map, a set of rules, and a strategy. The board
represents the state of the game as seen by the user, while the map presents the game in a way
that is easily interpreted by the program. The rules ensure that all the movements and
conditions are legal. And the strategy determines how the computer will
make its moves. As in many other programming tasks, it is important to separate the
game itself (the model) from the user interface (the view).
You can download the source of this game at Code
Central or from my Web site.