jgaunt.com

When I started looking into the use of AI in games one of the first things I came across was boardgames. It was an interesting application I had not at first thought of. But as I looked deeper it became clear that many of the concepts at play there were the same as in more complicated games, just without the complication of 3D space, explosions and damage calculations. A computer player still needed to look at the current state and decide on the next thing to do based on that state and what would happen given a variety of different moves.

Boardgames also offer an easy entry point. Most games are already familiar and are not too difficult to code up. Something as simple as tic-tac-toe can still teach lessons in AI. When one progresses to more complicated games such as go, pente or chess the coding becomes more complex do to additional rules and the size of the board. The AI as well becomes more complex, but still based on the AI you could write for tic-tac-toe in an afternoon. What makes it more complex is the complexity of the game.

The first technique I came across looks at just the next move and assigns priorities to each of them based on the resulting state. I call it a Priority Map (aka priority board)[1] . I'll demonstrate it's use on connect four.

We'll start with the board in the following state:

Now we will assign prioirties to the 7 possible plays for X based on the current state. We come up with values by enumerating a set of rules and evaluating each play against the rules. Each rule has a point value and it is the sum of the point values that gives us the priority of the play. Here are the rules I've developed for ConnectFour:

1. make 4 in a row (100 points)
2. block 4 in a row (50 points)
3. make 3 in a row (4 points)
4. make 2 in a row (3 points)
5. block 3 in a row (2 point)
6. block 2 in a row (1 point)

Given these rules and the above state the priority map would look as follows:

Because there are 2 ways to win by placing an X to the left of center that position gets twice the points for making 3 in a row. It also gets another point for blocking a two in a row for O diagonally. The rules defined above place a priority on offensive moves over defensive. It is important to note that a purely offensive AI is easy to defeat. But by reordering the rules and their point values it is possible to create different levels of opponents. Indeed more complex rules that look an extra step ahead could be created. But once you head down that road it is time to start working with another method of writing AI, MiniMax Trees.

This is a fairly basic example and to be sure the AI created by such a system is not too difficult to defeat with some practice. In fact a paper has been written that proves mathematically ConnectFour can be won every time by the player who goes first.[3] So against even a great AI opponent a talented ConnectFour player can win every time. But the illustration here is that the first step to AI in games is a simple one and that the more complex ones largely just build on this.

References

[1] Generation5 - Simple Board Game AI
[2] Tic-tac-toe AI Tutorial - uses a version of priority maps
[3] L. Victor Allis - ConnectFour Paper
[4] JavaScript Tic-tac-toe - procedural AI, always picks in the same order.
[5] Connect 4 - based on the Allis paper
[6] Generation5 - Connect 4 page
[7] Expert Play in Connect 4
[8] Generation5 - Virus Game proposal suggests using Priority Board (map).