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.

Domain Analysis

With the above description we can make a domain analysis for the game. Here is the resulting list of concepts:

Piece placement

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:

1. 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.
2. 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);
var
  i:integer;
  pieceCount:integer;
  linc,lstop:integer;
  n:integer;
  w:double;
  p:tpoint;
begin
  //set the count incrementing piece and the
  //count stopping piece
  setIncStop(linc, lstop, anOponent);
  pieceCount:= 0;
  //count pieces
  for i := 0 to size -1 do begin
    p:= self.getCoord(x,y,i,dir);
    n:= board[p.x,p.y];
    // Increment piece count
    if n = linc then begin
    inc(PieceCount);
  end
  // interrupted line
  else if n= lstop then begin
    pieceCount := -1;
    break;
  end;
end;

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.

The 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 following formula:

  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:

procedure tpenteGame.IntCalcWeights(Anoponent,calc:boolean);
var
  x,y:integer;
  itop:integer;
begin
  itop := (self.fsize - self.flineSize)+1;
  //horizontal
  for y := 1 to self.fsize do begin
    for x := 1 to itop do begin
      line(x,y,flinesize,tldhorizontal,anOponent,calc);
    end;
  end;
  //Vertical
  for y := 1 to itop do begin
    for x := 1 to self.fsize do begin
      line(x,y,flinesize,tldvertical,anOponent,calc);
    end;
  end;
  //slash
  for y := 1 to itop do begin
    for x : = 1 to itop do begin
      line(x,y,flinesize,tldslash,anOponent,calc);
    end;
  end;
  //backslash
  for y := 1 to itop do begin
    for x := self.fsize downto (self.fsize +1 )-itop do begin
      line(x,y,flinesize,tldbackslash,anOponent,calc);
    end;
  end;
end;

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 that both have the same relevance -- which means the program will play balancing offensive and defensive moves.

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.

Conclusion

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.