Anyone new to the Artificial Intelligence field with an interest in gaming should attempt to create a simple board game program with an AI opponent. Generally, the best part about board games are the simple rules—this means less time implementing the game, more time on the AI. Furthermore, board games can be easily rendered, without specialized knowledge of 3D engines or graphical APIs.
This article will detail some of the techniques that can be applied to simple board games.
One popular technique often used is influence mapping. Despite the fancy name, it is surprisingly simple: an array identically sized to the game board is used to store the "usefulness" of each corresponding board position—the higher the value, the more likely the agent will move there. For example, let us take the simple game of tic-tac-toe. Imagine the following board scenario:
[x][ ][ ] [ ][O][ ] [x][O][ ]
With the computer playing X, X to move, and the influence map could look something like:
  
The program would move to 2,1 (the highest value) and win the game. Note that if that opportunity wasn't there for the computer, then it would move to 1,2 and block the opponent from winning the game. Now for a small board like tic-tac-toe, an influence map is not necessary but for larger games (like Virus (15x15, 225 positions) or Pente (19x19, 361 positions)) influence maps can be indispensable to assess the large number of positions.
Yet how do you assess each position?
The term heuristics is essentially another name for 'rules', and it is these heuristics that will make or break the effectiveness of your AI agent. Firstly, you should narrow down your board game rules to a couple of heuristics that you can easily implement. For example, the rules of Pente dictate that you win if you place 5 pieces in a row, or get 5 captures. Therefore, some possible heuristics are as follows:
Now obviously, the first 3 can be reduced further, "Check for x-pieces in a row" which narrows our heuristic list down to two. So far though we have only an offensive agent. In the worst case scenario, we'd want a purely defensive agent—a purely offensive agent will be easily beaten. An additional two heuristics are required to balance our agent's AI:
We now have four heuristics that can be applied to the game in both defensive and offensive styles. As an example here is a sample Pente board with the typical influence map values after the first heuristic has been assessed. Each position on the influence map is essentially assigned the total number of pieces present across each possible line (vertical, horizontal, diagonal):
For example, 1,3 has been assigned the value '2' because there is a piece present in the horizontal line (1,5), and another present in the \-diagonal line at (2,4). Note that the /-diagonal has the highest values since there are 3 pieces in the 5-line, therefore (3,3) and (5,1) get the highest values assigned to them.
Beyond Influence Maps
You can see now how easy it is to evaluate all board positions using influence maps, although conditions can arise where there is no single best position, but a range. It is up to you how you choose between multiple positions—hone your heuristics in an attempt to reduce the number of equal positions, randomly select from the maximums, or use the influence map simply to greatly reduce the number of positions your more advanced AI must assess.
The Generation5 JDK has three useful classes for implementing these sort of board games and agents: BoardGame, BoardGameAgent and InfluenceMap. One of the demonstrations implement the Virus game, and the applet allows the agent's influence map to be visualized as a gradient (white to yellow, yellow to green):
This article has been a very simple introduction to influence maps and heuristics.
Last Updated: 27/12/2004
Article content copyright © James Matthews, 2004.
All content copyright © 1998-2007, Generation5 unless otherwise noted.