AI in Board Games
AI stands for Artificial Intelligence and is a misused term but is commonly used in computer games to describe a computer controlled opponent. Scientists also use the term AI to describe research into Artificial Intelligence. AI research has resulted in a variety of techniques that can be used to help a computer make complex decisions such as fuzzy logic, neural networks, genetic algorithms, expert systems, and many others. The techniques used in the scientific research of AI, however, are not always appropriate for use in computer games. What many beginning programmers seem to forget is that the goal of a computer game is to have a computer opponent capable of playing the game intelligently enough to provide a challenge to the player, not to necessarily beat the player.
I am not saying that you shouldn’t look into the various AI research that has been done. What I am saying is to keep your goal (creating an enjoyable opponent for the player to play against) in mind. Most people tend to play games to win and don't like losing. If the computer opponent always wins, they will quickly stop playing the game. At the same time, if the computer opponent doesn't play very well, the games will be too easy to win and the boring to play. This is the real challenge to creating a computer opponent.
While there are numerous techniques that can be used to build an AI for board games, the two techniques that tend to work the best are tree searches and decision trees. Some more complicated board games (such as war games) may require other techniques, but for most classic board games these two techniques should work.
Tree searches tend to use recursive algorithms and are mostly associated with chess games. Even today’s chess games use some variation of the recursive algorithm (with AlphaChess using a varient known as Monte Carlo tree search to help it's neural network understand how good different moves are). This technique simply has the computer take a look at every possible move, with each move being examined by taking a look at the possible moves the opponent could make, with each of these moves then being examined for all the possible moves the computer could make which are then examined for ... well, you get the idea. Each level of examination is a recursion (with recursion being a mathematical term for when functions fall back on themselves) The theoretical ideal of this technique is that you would keep looking at possible moves until there are no more moves. Realistically, you can only look at so many moves, so a limit on the level of recursion is usually placed on the computer. By reducing the number of recursions the computer executes, you reduce the intelligence of the computer, so you can use recursion levels as a way of controlling difficulty.
A Decision Tree is a light weight expert system. The computer makes its decision about what to do by following a set of branching rules. As branching rules simply correlate to if..then blocks, such an algorithm is fairly easy to write once the tree has been worked out. This type of technique is really good for track based games and for games that have random elements to them.
Advanced machine learning techniques such as Deep Learning tend to take advantage of the above techniques. While deep learning approaches can produce very good results, they do require training which can be a very computationally expensive. Having done research in this area, I can say that it definitely could be used but is a bit beyond the scope of this book.
Planning Pent Up AI
For Pent Up Anger we are going to use a decision tree to handle the computer moves. This is largely because of the random nature that the game has. As we don’t know what the player’s will roll, all decisions on the move will have to be based on the current state of the board. One problem with decision tree based AI’s is that they tend to be predictable. In some games, having a predictable opponent gives the player a fairly large advantage. In our case, knowing the way the computer thinks doesn’t help player much.
The best way to design a decision tree is to become familiar with the game you are designing the decision tree for. After playing through the game I came up with a basic strategy for the computer to use. All of this revolves around prioritizing the pieces that are able to move.
First, we assign a value to every piece and move the piece with the highest value. The weight value reflects the priority, so the higher the step is on the list of questions, the higher the weight.
1. Is the piece in the loading zone and the die roll that pieces number? This is our highest priority for two reasons. First, we want to win the game, and this is done by removing all our pieces. Second of all, getting to the loading zone is a time consuming process, so if an opponent takes us out at this point, we are losing a lot of time.
2. Is the piece in the starting location and the resulting move won’t take out one of my own pieces? If it is, then it is blocking new pieces from coming out of the starting gate.
3. Is the piece in the starting gate, the roll is that pieces number and the starting location is empty? We want to have as many pieces as possible on the board, as having to wait for the number to be rolled is not very efficient. Therefore, we get the pieces out on the board as soon as possible.
4. Can the piece be moved without taking out one of my pieces? Obviously, knocking yourself back to the start isn’t too bright.
The above is enough for our AI, and results in a decent computer opponent. There are other things we could add to the AI if we desired. For instance, we could make moves that take out an opponent piece a higher priority than moves that don’t take out a piece. We could also add some type of distributed movement system so that the computer doesn’t focus on just one piece. It is also possible to have different difficulty levels of computer opponents by having the decisions made differently based on the difficulty of the opponent.
Making a Computer Opponent
As computers can't think, we need to give the computer a set of rules for playing. There are many ways of handling the rules. The most common approach is to look at all possible moves and assign the moves a weight. This is the approach we will be using, and the piece class already has support functions for setting and getting a weight.
To determine the weight, we are going to make changes to the prepareMove function that is located in the board symbol. Quite simply, we are assigning a weight to each move. The weight is assigned using the rules we outlined earlier in the chapter.
First, in the area where we determine if a piece can be launched or finished we assign a piece the weight of 100 to make sure it will exit if it can. Likewise if a piece can be launched we will give it a 90 value. This means that putting a piece in the end zone is the most important thing to do while launching a piece is second-most in importance. Note that we forgot to check if there is a piece in the launching area, which is a bit of a bug but as that is how the game was released I will leave that bug here and leave it as an exercise to fix this bug.
// see if piece can be launched or finished
if ((cntr+1) == roll)
{
if ( (loc == (start+cntr)) || (zonedist < 5) )
{
console.log("Piece is launchable/exitable");
this.pieces[player][cntr].useHighlight.visible = true;
if (zonedist < 5)
this.pieces[player][cntr].weight = 100;
else if (this.layout_piece[home] != player)
this.pieces[player][cntr].weight = 90;
// pieces[player][cntr].onRelease = choosePiece;
++movecount;
}
}
We then need to add some weights to the pieces that are movable on the board. This simply makes sure that we are not taking out our own piece and if not then giving pieces on the home location a boost so they get out of the way of other pieces ready to be launched. Otherwise, the weight is how far from the loading zone the player is.
if ( (loc >= 50) && (zonedist > roll) )
{
console.log("piece movable on board");
this.pieces[player][cntr].useHighlight.visible = true;
var targetloc = loc + roll;
if (targetloc > 104)
targetloc -= 55;
var targetPiece = this.layout_piece[targetloc];
if ((targetPiece == null) || (targetPiece.playerID != player))
if (loc == home)
this.pieces[player][cntr].weight = 60;
else
this.pieces[player][cntr].weight = 60-zonedist;
++movecount;
}
Finally, at the end of the move preparation routine, we call the ai\_move method to actually get the AI player to make their move.
if (listener.playerTypes[player] == 3)
this.ai_move(player);
else if (movecount == 0)
listener.doneMove();
The actual routine that uses the weight is also placed in the board symbol. It simply goes through the pieces and moves the piece with the highest weight. Ties go to the earlier piece. This allows us to know if none of the pieces are able to move (as all the pieces will have a weight of 0 in this case).
spelchan.Board.prototype.ai_move = function(player) {
console.log("ai move called!");
var cntr, choice = -1;
var best = 0;
for (cntr = 0; cntr < 5; ++cntr)
{
if (this.pieces[player][cntr].weight > best)
{
choice = cntr;
best = this.pieces[player][cntr].weight;
}
}
if (choice == -1)
this.move_listener.doneMove();
else
this.choosePiece(player,choice);
}
The biggest problem with this AI is the predictability of the computer. Still, I have played against many human opponents who are just as predictable. To test the AI one can simply manually set the player type to 3, or wait until we add the title screen where players will be able to select which players are playing, and if active players are human or AI.
The next installment will be the final one where we wrap up everyting.
