Artificial intelligence in games, part 3

As I warned when I started this blog, I've allowed it to lie dormant for a while, but I feel like it's high time to pick up where I left off and finish the series about playing chess by look-ahead.

So to review the posts that led up to this one:

• It's possible, and not even very hard, to construct a tree that describes all games of tic-tac-toe.
• By doing so, you can prune off the branches that lead to a loss (and sometimes that lead to a draw) to write a program that plays a perfect game of tic-tac-toe.

Now we're going to turn our attention to chess.

Although chess is a much more complex game than tic-tac-toe, it's easy to see that you can apply the same tactics to systematically list all possible games of chess, in theory. Of course I'm not going to attempt to diagram them, but there's definitely a finite number of things you can do on each move. If you're the white player, on your first turn you have eight pawns that you can move forward one or two spaces, and then you have two knights that can move to two spots (forward two, left or right one). So the total possible moves on the first turn is (8*2)+(2*2), or 20.

Then it gets a little more complicated. Black has the same choices, but he has the same 20 choices for each of the 20 possible moves that white could make. So after each player has made one move, there are 20*20=400 possible states the board could be in. It only gets worse from there.

For instance, if white performed the traditional P-K4 opening, on the second move he has nearly all the other choices remaining (7 pawns to move one or two squares, plus two knights two ways, 18 moves) but he also has a whole lot of new choices. The king's knight may move into the spot occupied by the pawn (19). If the black king's pawn doesn't block it, the white king's pawn may advance one space (20) or, depending on what black did, capture an enemy pawn.

Also, the white king's bishop is now free to move to any of 5 spaces toward the upper left (25) and the queen can move to any of 4 spaces toward the upper right (29). So the number of possible moves keeps increasing as the board opens up, and so does the complexity of the tree. Now it looks like by the time white has moved twice, there are about (20*20*29) possible states the board could be in. (Some starters obviously make less than 29 moves possible, and there is more than one way to get to the same state; i.e., P-K4 followed by P-Q4 has the same result as P-Q4 followed by P-K4).

As we observed in the tic-tac-toe problem, you can calculate roughly how many possible games there are in two ways: by multiplying out the possibilities for all moves, or by figuring out every possible state of the board. The second method tends to be smaller because it eliminates various ways of GETTING to those states. However, in the case of chess, figuring out how many moves are possible from each state is massively complicated, so will go with the second approach.

Each side has 16 pieces. The pieces are not unique; for instance, the eight pawns are interchangeable with each other and so are the two rooks . However, to simplify the calculations we'll assume that all pieces are unique. So there are 32 pieces on the board, and 64 squares where they could be located. The first piece could be on any of the 64 squares, the second on any of the remaining 63, the third on any of the remaining 62, and so on. So as a rough guess, the number of board configurations is (64*63*62*...*35*34*33) and then the remaining 32 squares are blank. That is to say, the answer is "64 choose 32", or (64!/(32!*32!))

Side note: Cool feature of Google. Type "64 choose 32" into the search bar and it will answer the question for you. It's 1.83*10¹⁸.

Is this number an accurate portrayal of all chess boards? Not exactly. In the first place, many of the moves are not legal. This set of all possible boards includes boards where the two kings are next to each other, or in an impossible multiple check; it includes pawns on the first row, and positions where all eight pawns are on their home squares, but the king and queen are not.

On the other hand, it does not include any position where one or more pieces have been captured, nor does it include positions with two or more queens due to promotion. So there may be more games that are truly possibly, or there may be fewer, but on the order of 10¹⁸ possibilities is a fair guess.

Now, 10¹⁸ is a very large number. In point of fact, it is larger than the number of seconds since the universe began (about 4.4*10¹⁷... although it's only 189 billion if you're a creationist. Har har.) It's close to the number of grains of sand on earth, and much larger than the number of stars in the milky way.

In theory, you could have a computer run through the win/loss state of every one of those games, but not in a reasonable amount of time. If you could analyze one game a second, it would of course take longer than the universe has been around to decide on one move. Computers can do much better than that, of course. Currently the world's fastest supercomputer can perform 596 TeraFLOPs -- 596 trillion floating point operations per second. That means that if you were so incredibly optimistic that you believed that analyzing one board position could be done in a single operation (believe me, it can't), the world's fastest supercomputer would still take 40 minutes to analyze the outcome for a single move. And that level of optimism is ridiculous.

Granted, computers have become a lot more powerful since this topic was discussed in the 1970's, but it's still fairly impractical to play a decent game of perfect chess, unless you have several supercomputers lying around doing parallel computations. Your desktop PC would take years. More realistically, thousands of years. Needless to say, no computer plays chess based on the tic-tac-toe strategy of exploring every possible move.

Next time: What's a heuristic, and how come a computer can beat the human chess champion of the world?