At the forefront of Artificial Intelligence

Home » Articles » Gaming » Applications/Code

PenteAI

Download here (65K) - Note: you will need MFC42.DLL to run this.

PenteAI, in its original form, was the first real Artificial Intelligence program I'd ever created. In its very original form, it was an MS-DOS program. When I got Visual C++, it was the first program I converted to Windows. In short, since it was both my first AI program and my first Windows program - it was crap! It looked ok, it even put up a fight in the game - but when you looked on the inside at the code, it was really quite terrible.

Two years later, I felt I should give it another try. Within an 4 hours, I had a program better than the original 4 month project! This new version is a lot more object-orientated, using a separate class for the board, and the opponent. The AI agent was written in such a way that it can play both players with no trouble. The evaluations are a lot more reliable, bug-free, and efficient. With the release of version 3.0, the graphics have slightly improved as well.

How to Play

Pente is a very simple game to play. Two players take it in turns to place stones on a 19x19 board. The first person to get either five stones in a row or five captures is the winner. The five stones in a row can be in any direction (including diagonals). Captures are made when you place two of your own pieces on either side of two adjacent opponent pieces. The picture on the right demonstrates this.

Note: The little blue pair in the corner is PenteAI showing how many pieces have been taken. Therefore, when five blue pairs are shown, red has won. Takes can occur in any direction, including the diagonals.

Using PenteAI

When you start PenteAI, a game is started automatically. The default player setting is human (playing red) vs. computer. Double-click on a space to make a move. PenteAI will inform you when the game has been won. The new version of PenteAI sports a save game feature (although it doesn't save whose go it is, therefore, always save on Player 1's turn!) so you can save your game and continue it later. To start a new game, simply select "File, New."

You can select the players in the new version, too. You can have a human vs. human match, human vs. computer, or computer vs. computer. Simply select the appropriate icon/menu item and the game will continue with those settings (you can, for example, have a human. vs. human match for the first five moves, then switch to human vs. computer).

Set Biases...

What is that?! Originally, I designed the Pente agent to allow a genetic algorithm to evolve some of the biases that it uses to make its moves. After a little experimenting, I decided against the idea since it took so long for even one generation to the genetic algorithm to complete. Even for a population of 7 in a tournament selection process, each generation took several minutes.

Therefore, I took out the genetic algorithm, but set up this dialog box to allow the user to alter the biases themselves. Please look at the code to get a full understanding of the various biases. If you want a quick explanation for the bias in a particular edit box, each bias has it's own tooltip; just hover the mouse over the edit box and a tooltip will appear.

Artificial Intelligence

The AI in Pente is simple, it uses a priority board and evaluates every single place on the board using specific heuristics. Then it cycles through each place and picks the highest priority place to move. For debug reasons, I added a function that overlaid the priority board on the main board when the shift key was pressed. I thought this was pretty cool, so I kept the function in. For more information on the AI behind Pente, look at the Simple Board Game AI essay.

Version 3.0

A major update that fixes a lot of bugs, new graphics and a statistics system. The AI still has some quirks that need to be ironed out, but I believe it is more a case of messing around with the biases than actually changing the code itself. In fact, I'd tried messing with hill climbing (well, it isn't hill climbing in the GA sense) to get the biases a little more robust, but it doesn't seem to work that well and it takes a long time to complete. If you compile PenteAI under a debug build it will include the hill climbing options. I'd be very happy to hear from anyone that creates a good set of biases for PenteAI.

Version 2.2

Although 2.2 was only written a day after 2.1, quite a few improvements have been made. I added a proximity bias that means the agent will build 5 in a row unless blocked, if it moves first. Before, it would "set-up" the maximum spread of possibilities which is good if defensive, but pointless if offensive. The agent is getting close to being quite good, since if the computer plays itself, Player 2 will nearly always win. Pente is said to be always winnable if you play first - and with in computer matches, Player 2 plays first. I'm getting there...

Version 2.1

Version 2.1 sees improved AI, although I'm still not completely happy with it. I think to really get the AI up to scratch, quite an extensive FSM is required. I don't have the time nor energy to implement that at the moment. The biases have been increased by three - offensive and defensive return values (values to be placed on priority board) and the three-in-a-row bias. You can now also select who plays first - the human or the computer.

Last Updated: 24/03/2001

Article Toolbar

BibTeX entry