"Computer Player Algorithms"
PC Techniques, Vol. 6, No. 5
Dec/Jan 1996, page 74
What appears here is the original manuscript, as submitted to Jeff Duntemann. Any changes in the published version are due to Jeff's expert editing.
Human beings are, by nature, competitive. We compete with ourselves, with each other, with high scores lists, with our own personal best, with the guy next door, or the guy in the next office, our spouse, our kids, and our computer.
Our computer? We compete with our computer? Of course we do! We love to. When we play games with a computer, we want the computer to play too. We want the satisfaction of beating an opponent that gives the illusion of being almost as intelligent as we are.
When you play a game with a computer, and the computer plays back, the strategy for the computer's artificial intelligence is called the computer player algorithm. Computer player algorithms come in many different forms and levels of complexity. In this article, we are going to take a quick look at the general theory of computer player algorithms, and then look at the code to implement a simple computer player algorithm for a one- player card game.
Computer player algorithms are an essential element of most card games, board games, and strategy games. In these games, game play is not based on hand-eye coordination, but rather on luck and skillful decision making. The player tests his mental acuity against his opponent, often taking minutes or hours to decide his next move. After he moves, he expects the opponent to make a skillful counter-move. If the opponent is a computer, then the move is determined by the computer player algorithm.
Computer player algorithms are most common in two-player games such as checkers, chess, cribbage and backgammon, but you will also see them in multi-player games such as poker and Chinese checkers, and one-player games like solitaire. In solitaire, the computer player algorithm is used for both the demo mode and the hint mode. In the demo mode, the player learns to play solitaire (or simply entertains himself) by watching the computer play continuously. In the hint mode, the player plays his own game of solitaire, but at some point needs help deciding which card to move next, so he presses a hot-key sequence for a hint.
Arcade games also have a type of computer player algorithm. Even when game play is mostly action oriented, there is still an element of strategy involved. For example, in the game Pac Man, a small hoard of ghosties tries to get you before you get them. The motion of the ghosties is determined by the computer player algorithm.
Sometimes adding a computer player algorithm will add new life to an old game. An arcade game like Tetris, for example, which seems to do quite nicely without a computer player algorithm, will benefit when one is added. You can use the computer player algorithm to generate a self-playing demo mode, which is useful for promoting your game. You can also find ways to incorporate the computer player algorithm in the game play itself. For example, you could have time trials. Both the player and the computer get the same set of bricks, and whoever stays alive the longest (or removes the most bricks during a fixed period of time) wins.
In order to write a computer player algorithm, you need to understand the game thoroughly. Usually, that means you need to play it over and over. If you have been playing dominoes with your family since you were in kindergarten, then you are a good candidate to write a dominoes computer player algorithm. If you just learned the rules to chess yesterday, don't even attempt to write the program. Leave it to someone who knows what they are doing.
Sometimes you can find documentation for computer player algorithms. Books have been written about chess, checkers, and bridge strategies. Clubs exist for Scrabble and backgammon. Sometimes graduate students write papers on these subjects. It may take a little digging, but for classic problems you can often get a head start by looking at algorithms developed by others.
Ideally, you want to write your computer player algorithm in such a way that the computer goes through the same thought processes as a human player. To do this, you need to start with a human player, and watch how he plays. Ideally, the human player should be yourself. Play the game over and over, until you become an expert at it. In the process of playing the game, pay attention to the decisions you make. Don't play by "instinct" or "intuition", rather try to understand the logic behind each move you make. Once you understand why you make decisions, you will be able to codify the steps in the decision making process. In other words, write the code to work exactly the way you think when you are playing the game.
For example, in solitaire, you often have your choice of several cards that can be played. I always play the card that frees up the most other cards, but I try not to cut off my opportunities to play future cards. That means I won't play a card if it is the last one on the row, it unless there is a king waiting to occupy that place, and I won't move a card to the discard piles if I think it may be needed to capture a lower card later. Refer to the sample code to see how I implemented this.
Sometimes even an experienced game player is not sure of the optimal algorithm. In the case of Solitaire, my husband Ted and I could not agree on whether the best strategy was to take a card from the shortest column or the longest column. My argument was, clear up the shorter columns so there will always be a place to put a king if one should appear. Ted said that was all wrong, you have to clear out the longer columns and let the short columns take care of themselves. How do you decide which method is best? It’s very simple. You just write the program in such a way that the computer can play against itself. Then you let the computer play against itself over and over. In my case, I let the computer play 1000 games. Then I tweaked the algorithm and let it play another 1000 games. I kept doing this, recording the number of wins, until I had what I considered to be an optimal algorithm. The next_move() function in Figure 3 made this kind of optimization strategy quite simple.
The next_move() function only makes one move at a time. I believe, in general, this is the best way to write a computer player algorithm. In the case of solitaire, this allows the human player to control whether he makes the moves, or whether the computer does. In a multi-player game, the computer player algorithm should be general purpose enough so that it can make anybody's next move. In a game such as Chinese checkers, the computer player algorithm should be able to examine the state of the game from the point of view of any player, and make the optimal move for that player. That way, one function can handle all the moves for all the computer players and can be used for the cheat mode for the human player.
The rules of solitaire are fixed, so we can't have different levels of difficulty. In multi- player games, you will want to incorporate different levels of difficulty in your computer player algorithm. This is important, because many players will start at the novice level and will continue playing until they reach the expert level. In fact, this is what you want them to do. You want people to play your game over and over, and become addicted to it. If your game always beats them too often in the beginning, or if they always beat it, they will get tired of playing it and move on to something else. So it is best to gear your levels of difficulty toward a broad spectrum of players.
There are many ways of adjusting the level of difficulty of a game. You can use the trick of letting the computer play against itself to determine the best algorithm, and then use the second-best algorithm as the medium difficulty level, and the third best algorithm as the easy level. Another strategy is to take your best computer player algorithm, and stop part way through. For example, if you have a word game that examines 30,000 words at its best level, have it examine 10,000 words at the medium difficulty level, and 5,000 words at the easy level.
While these ideas work in theory, in actual practice the easy and medium difficulty levels may not feel right to the players. That is why it is so important to have beta testers and to play the game many times yourself. Remember, the goal is not to write a game that always wins, but to write a game that is fun to play.
While it is not absolutely necessary to have the computer exhibit personality while playing against you, I think it greatly improves the playability of most games. When playing poker, for example, if you are looking across the table at a gunslinger or a pretty lady, you will take more pleasure in winning the hand.
This is, unfortunately, a common practice in the gaming world. When the computer plays against you at bridge, for example, it peeks at your cards. As a programmer, I would take no pride in writing a computer player algorithm that cheats. I believe the information that is traditionally kept secret from the human player should not be used in the computer player algorithm. The computer player algorithm should be able to play bridge without looking at the opponent's cards. As a player, wouldn't you rather win fair and square? The computer player should play by the same rules as the human player.
The code in Figure 3 is the computer player algorithm for a game of computer solitaire. The entire algorithm takes place in one short function called next_move(). Recall that the object of the game is to remove cards from the columns and the stack and place them on the piles. The stack is replenished from the deck, either three cards at a time (classic solitaire) or one card at a time (Klondike). The next_move() function examines the columns, the piles, and the stack, and chooses the most favorable move based on the current state of the game.
The first thing next_move() does is check if there are any vacant columns, and any kings waiting for a vacant column. It’s important that this information be determined first, because it will affect other decisions later in the function. It looks for kings both at the bottoms of columns with more than one card in them, and on the top of the stack. If it finds one or more kings, the local variable king_waiting is set to TRUE.
The next step is to try to move one column to another column. Non-empty columns (columns which contain face-down cards) are moved first, because we want to free up whatever cards may be hidden. If a non-empty column cannot be moved, we try to move an empty column, but only if a king is waiting. It is pointless to move an empty column if there is no king waiting for it.
If we are unable to move a column, we try to take a card off the stack and put it on a column. Failing that, we try to take a card from the stack and put it in one of the discard piles. The next thing we try is taking a card from a column and putting it on one of the discard piles. We have to be careful with this move, though. We don’t want to take cards off the column if they may be needed later to take a card off the stack. For example, if a red three is still in the deck somewhere, we don’t want to remove all the black fours from the columns. If the red twos have already been put on the piles, then we know the red threes are safe, so we can remove the black fours.
The next move, in order of priority, is to remove a card from the deck and put it on the stack. If there are no cards remaining in the deck, then we try one last time to take a card off a column and put it on a pile. If there are no advantageous moves we give up, and return to the calling function. At this point, the game is over and it is time to shuffle.
Computer player algorithms are rarely talked about any more. That is probably because everybody wants to write arcade games, and all they want to talk about is the frame rate. I think that is a mistake. After a certain point, users no longer care how many frames per second they are getting. What they really want in a game is playability. The classic games are classic for a reason. Something about them grabs the player’s attention, and makes him play them over and over. Games like poker and checkers will never go out of style. This is to the game programmer’s advantage. Arcade games will come and go, and their faddish nature leads to a short shelf life, but people will buy the classics forever. Therefore, it pays to study the nature of the classics, and perhaps even write a few yourself. The earmark of a great classic game is an excellent computer algorithm.
void next_move()
{
int col,card,suit,value,color;
int x1,x2,y1,y2,col1,col2;
int card1,card2,value1,suit1,value2,suit2;
int color1,color2;
char string[2];
int first,valid;
int card_moved,won,vacant,king_waiting;
int i;
int col3;
/* check if a king is waiting for a vacant column */
no_moves = FALSE;
vacant = FALSE;
king_waiting = FALSE;
for (i = 7; i >= 1; i--)
{
if (top[i] == 0)
{
vacant = TRUE;
}
else if (top[i] != 1)
{
card = column[top[i]][i];
get_card_value(card,&value,&suit,&color);
if (value == 13) king_waiting = TRUE;
}
}
if (stacktop >= 0)
{
card = stack[stacktop];
get_card_value(card,&value,&suit,&color);
if (value == 13) king_waiting = TRUE;
}
/* try to move column to column without leaving a vacant column */
for (col1 = 7; col1 >= 1; col1--)
{
if (bottom[col1] != 0 && top[col1] != 1)
{
card1 = column[top[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
for (col2 = 7; col2 >= 1; col2--)
{
if (col1 != col2)
{
/* move a king to an empty column */
if (bottom[col2] == 0)
{
if (value1 == 13)
{
move_column(col1,col2);
return;
}
}
/* move col1 to bottom of col2 */
else
{
card2 = column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 != color2 && value2 == value1+1)
{
move_column(col1,col2);
return;
}
}
}
}
}
}
/* leave a vacant column only if there is a king waiting for it */
for (col1 = 7; col1 >= 1; col1--)
{
if (top[col1] == 1)
{
card1 = column[top[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 != 13)
{
for (col2 = 7; col2 >= 1; col2--)
{
if (col1 != col2 && bottom[col2] != 0)
{
/* move col1 to bottom of col2 */
card2 = column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 != color2 && value2 == value1+1)
{
/* only move the top of column if a king is waiting */
if (!vacant && king_waiting)
{
move_column(col1,col2);
return;
}
}
}
}
}
}
}
/* couldn't move column to column, try stack to column */
if (stacktop >= 0)
{
card1 = stack[stacktop];
get_card_value(card1,&value1,&suit1,&color1);
for (col2 = 7; col2 >= 1; col2--)
{
if (bottom[col2] == 0)
{
if (value1 == 13)
{
stack_to_column(col2);
return;
}
}
else
{
card2 = column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 != color2 && value2 == value1+1)
{
stack_to_column(col2);
return;
}
}
}
/* couldn't move stack to column, try stack to the pile */
if (value1 == pile[suit1]+1)
{
stack_to_pile(card1,suit1);
return;
}
/* couldn't put stack on column or pile, put matching card on pile? */
for (col2 = 7; col2 >= 1; col2--)
{
if (bottom[col2] > 1)
{
card2 = column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1 == color2 && value1 == value2)
{
if (value2 == pile[suit2]+1)
{
column_to_pile(col2,card2,suit2);
return;
}
}
}
}
}
/* if a card is the only card on a column, try to move it to a pile */
for (col1 = 7; col1 >= 1; col1--)
{
if (bottom[col1] != 0)
{
if (bottom[col1] == 1)
{
if (king_waiting)
{
card1 = column[bottom[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 == pile[suit1]+1)
{
column_to_pile(col1,card1,suit1);
return;
}
}
}
else if (top[col1] == bottom[col1])
{
card1 = column[bottom[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 == pile[suit1]+1)
{
column_to_pile(col1,card1,suit1);
return;
}
/* can't put it on pile, put matching card on pile? */
else
{
for (col2 = 7; col2 >= 1; col2--)
{
if (col1 != col2 && bottom[col2] > 1)
{
card2 = column[bottom[col2]][col2];
get_card_value(card2,&value2,&suit2,&color2);
if (color1==color2 && value1== value2)
{
if (value2 == pile[suit2]+1)
{
column_to_pile(col2,card2,suit2);
return;
}
}
}
}
}
}
}
}
/* couldn't move any cards, take one off deck */
if (decktop >= 0)
{
deck_to_stack();
return;
}
/* no more cards on deck, try to move a card to the pile */
for (col1 = 7; col1 >= 1; col1--)
{
if (bottom[col1] != 0)
{
card1 = column[bottom[col1]][col1];
get_card_value(card1,&value1,&suit1,&color1);
if (value1 == pile[suit1]+1)
{
column_to_pile(col1,card1,suit1);
return;
}
}
}
/* give up -- there's nothing we can do */
no_moves = TRUE;
return;
}