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. The best part about board games are the simple rules - this means less time implementing the game, more time on the AI. This essay will detail some of the techniques that you can apply to simple board games (this does not include chess, Go, Go-moku and the likes).

Priority Board

A technique often used is something I call a priority board, an identically sized board that the AI agent uses to store values in. Each value corresponds to the place on the board; the higher the value, the more likely the agent will move there. For example, let us take the overly-simple game of tictactoe, for this board:

[x][ ][ ]
[ ][O][ ]
[x][O][ ]

With the computer playing X and X to move, the priority board could look something like:

[0][5][0]
[9][0][0]
[0][0][0]

The program would obviously move to (2,1) and win the game. Notice that if that opportunity wasn't their for the computer, then it would move to (1,2) and block the opponent from winning the game. Now, for a small board like tictactoe, a priority board is not necessary, but for larger games (like Pente, which is on a 19x19 board - 361 positions!) priority boards can be very useful to assess the large number of places. So, how do you assess the positions?

Heuristics

Heuristics is basically a fancy name for rules, and it is these heuristics that will make or break the game. Firstly, you should narrow down your board game rules to a couple of heuristics that you can implement as code. 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:

• Check for 4-pieces in a row
• Check for 3-pieces in a row
• Check for 2-pieces in a row
• Check for captures

Now, obviously, the first 3 can be reduced further, "Check for x-pieces in a row" which narrows our heuristic down to two! Thing is, so far we have only an offensive agent. In the worst case scenario, we'd want a purely defensive agent - purely offensive agents will be easily beaten! So, we will add an additional 2 heuristics to our program:

• Check for opponent potentially getting x-pieces in a row
• Check for opponent potentially making a capture

We now have 4 heuristics that can be applied to the game in both defensive and offensive styles. I have found the best place to proceed from here is by applying a two step evaluation. Firstly, you assign a number to the priority board place in your heuristic routine. For example, in our "Check x-pieces in a row" heuristic we could assign the number of pieces to the priority board. For example, given a simple Pente board:

[ ][ ][ ][ ][x]
[ ][ ][ ][x][ ]
[ ][ ][ ][ ][ ]
[ ][x][ ][ ][ ]
[ ][ ][ ][ ][ ]

Our initial priority board after the first heuristic would look something like this:

[1][2][2][2][0]
[1][1][1][0][2]
[1][1][3][1][2]
[1][0][1][2][1]
[3][1][1][1][1]

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. With experience, I've found it useful to multiply each heuristic by a certain bias. I've also found it useful to assign a slightly higher value to defensive heuristics (for example, I use a bias of 1.2 as opposed to 1.0 (which is no bias) in PenteAI).

Hopefully, you will find with the right heuristics and biases, you will get a certain amount of emergent behaviour - behaviour you had not planned, but comes from all the heuristics interacting with each other. For example, when I first ran my recent PenteAI program, I found the AI spaced out its moves. I had not planned this at all, indeed I wanted quite the opposite! After playing with this for a while, I realized it was an excellent way of limiting your opponents moves 3 or 4 moves ahead - and it is a technique that I myself have now adopted when playing the game!

Beyond This...

For board games this simple, there aren't that many additional simple techniques. It all depends on your game and the complexity of the game itself. For more complex games, you start to look a certain number of moves ahead to keep in front of your opponent. You can also employ more advanced AI techniques to simple board games with some interesting results - genetic algorithms to evolve biases and weights (although this is time consuming) can generate a very formidable opponent. Using neural networks to recognize patterns in the players behaviour can also be very challenging for the player.