Thanks for the help, cloud AI!

This is just a quick silly story that illustrates how the "intelligent" programs that monitor our lives can be both funny and creepy.

At my work, we have an intranet application -- something that runs in a web browser, but it's only visible from inside the office -- which tracks change requests and bugs we are working on. I am on the Client Account team, so most of my projects are identified with "CA-" and then a number, such as "CA-1234."

Usually after I have been working on one project for a while, I have memorized the number, and so I just type "CA-1234" into my browser. Since I have visited the feature page often, it automatically fills in the URL to take me there. But sometimes I mistype, or it doesn't work for some other reason, so my browser helpfully pulls up a Google search for CA-1234 instead.

That does not contain any information that is useful to me. However, it does often match a flight number on China Airlines.

So one morning I got an alert on my Android. It was Google's calendar program. It told me "It's time to leave for the airport if you want to catch that flight on China Airlines that you looked up!"

Wondrous number graph

Like many great ideas should, my latest pet project was inspired by an XKCD cartoon.




Of course I recognized the graph right away. I never heard it described as Collatz Conjecture before, but this concept also makes an appearance in my very favorite book of all time, Godel, Escher, Bach. In a dialogue between Achilles and the Tortoise, they were referred to as "Wondrous Numbers," and Wikipedia confirms that both terms are acceptable.

After reading the cartoon, I started doodling my own graphs, which -- despite the convulted twistiness of Randall's picture -- are essentially binary trees, going downward from one. If you draw the left branches as multiplying by two, and the right branches as "minus one divided by three", then you may get a graph like this:

1
|
2
|
4
|
8
|
16
|...\
32...5
|....|
64...10

... and so on.

The tree is easy to generate. Of course, it's an infinitely large tree, so you have to decide which nodes to expand. The two main ways I can see to do it are:
1. Start with 1, balance the depth by always expanding the leaves that are at the least distance from the origin.
2. Start with 1, always expand the leaves that have the smallest numerical value.

So for example, in the tree above, I've used method 1. If I had used method 2, I would have needed to add 5, 10, 20, 3, 6, 12, 24,and 40 to the tree before I could expand node 32.

Now, obviously this tree gets large in the vertical direction faster than the horizontal direction at first; later on, when the branches increase exponentially, the opposite is be true. But when I tried sketching the graphs, I was annoyed by all the white space at the top. I thought the tree would look much neater if I started with the root in the upper left corner and tried to push the left nodes downward, and the right nodes rightward. So the above graph would be changed to something like this:

1...5--10--3--6--12--24
|../../
2.|.20
|.|.|
4.|.40
|.|
8.|
|/
16
|
32
|
64

and so on like that, giving me more space to expand toward the bottom right. (Hope that's clear.)

Once I was able to sketch this, I started writing it as a program, but currently haven't finished working out the algorithm to decide where in the grid to place each node. Basically the requirements are as follows:

1. You should be able to display any binary tree with this program (it doesn't have to be tied to Wondrous Numbers).
2. Root is displayed in the upper left corner.
3. Prefer to display children to the right of and below the parent, as much as possible.
4. The algorithm should eventually fill up all available space in a specified grid size.
5. The nodes should be as tightly packed as possible, avoiding empty spots.
6. Parents and children should be connected by straight lines, which do not cross. Failing that, fewer crossed lines is preferred.


I thought of a few different ways to accomplish these goals, but haven't been able to decide which one to focus on first. My first thought was just to place new nodes anywhere nearby, and then gradually move them out of the way as necessary when adding new nodes. This would require me to decide which nodes need to be moved, based on either position in the tree or position on the grid.

I also thought I might go with a hill climbing algorithm, where I just keep swapping nodes at random until the number of line intersections is decreased. However, I don't much like this solution, because calculating all possible intersections repeatedly could eat up more processing time than I like.

That's about as far as I've gotten. Any thoughts?

The Chess Master And The Computer

Garry Kasparov On Chess Metaphors

Thirteen years after Deep Blue beat him at chess, Garry Kasparov has written a long, thoughtful article about humanity's search for a meaning behind the event. Manages to cram in quite a lot of insights about both artificial intelligence in general, and the way the game of chess has changed among human opponents. As someone with a small fondness for chess and a large fondness for AI, I enjoyed it a lot.

There have been many unintended consequences, both positive and negative, of the rapid proliferation of powerful chess software. Kids love computers and take to them naturally, so it's no surprise that the same is true of the combination of chess and computers. With the introduction of super-powerful software it became possible for a youngster to have a top-level opponent at home instead of needing a professional trainer from an early age. Countries with little by way of chess tradition and few available coaches can now produce prodigies. I am in fact coaching one of them this year, nineteen-year-old Magnus Carlsen, from Norway, where relatively little chess is played.

The heavy use of computer analysis has pushed the game itself in new directions. The machine doesn't care about style or patterns or hundreds of years of established theory. It counts up the values of the chess pieces, analyzes a few billion moves, and counts them up again. (A computer translates each piece and each positional factor into a value in order to reduce the game to numbers it can crunch.) It is entirely free of prejudice and doctrine and this has contributed to the development of players who are almost as free of dogma as the machines with which they train. Increasingly, a move isn't good or bad because it looks that way or because it hasn't been done that way before. It's simply good if it works and bad if it doesn't. Although we still require a strong measure of intuition and logic to play well, humans today are starting to play more like computers.

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?

Artificial intelligence in games, part 2

In the previous post, we discussed the fact that tic-tac-toe is finite game, and you can even calculate all the possible states of the board: it's 19,683, with 362,880 different ways to get to the legal states.  Now we can talk about how to take advantage of this calculation to always win the game.

Let's imagine that we pit two perfect computer opponents against each other.  The first opponent, playing as "X", will want to evaluate each of the nine possible moves on a blank board.  How does it know which is best?

Well, starting in the corner, the question is: "Do I have a sure win on this path?  If so, then I will definitely make this move.  If not, then does my opponent have a sure win?  If so, then I will definitely not make this move."

But how do you know if you or the opponent has a sure win?  Simple: Imagine that you already made this move, and then try to make the best move for the opponent.

You can easily see that this is a recursive process.  It has a recursive step ("Let me try this move") and it definitely has a terminating condition.  After all, if you come to a step where (a) the board is full, (b) X has won, or (c) O has won, you don't need to look ahead to any other moves.

Here's an example of how the computer would evaluate the first possible path.

|  X |   |       X | O |       X | O | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|  X | O | X     X | O | X     X | O | X
| ---+---+---   ---+---+---   ---+---+---
|  O |   |       O | X |       O | X | O
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|  X | O | X
| ---+---+---
|  O | X | O
| ---+---+---
|  X |   |

This game ends in a win for the X player.  So if you are the X player, you like this game.  If you  are the O player, you do not like this game.  So the computer then backs up by two moves ("waking up," in the dream analogy) and assumes that O would not go there, but would instead do this:

|  X | O | X
| ---+---+---
|  O | X |
| ---+---+---
|  O |   |

Of course, this game will also result in a win for X if you follow it to the conclusion, which is this:

|  X | O | X
| ---+---+---
|  O | X | X
| ---+---+---
|  O | O | X

You get the idea.  The computer will play every game to its ending, at which point it will know exactly which games guarantee a win for one player or the other.

Now the pruning begins.  The X-playing intelligence will try to reach one of the game states that guarantees a win for X.  If it cannot, it will at least avoid reaching any game state that guarantees a win for O.

Writing an unbeatable tic-tac-toe opponent in this way is actually pretty straightforward.  You can write it to pick the first "good" move, where "good" means "First try to pick a move that guarantees a win; then try to pick a move that doesn't guarantee a loss."  If you do this, you'll find that your tic-tac-toe game will always play in the same way.  For instance, in the first move, the upper left corner is as good a move as any (the O play can never force a win).  So your program may well always start in the upper left.  This program will not appear to be intelligent.  But it will never lose.

If you want your program to be more interesting, throw in a randomizer.  If there are multiple moves that guarantee a win, then pick one at random.  Otherwise, if there are multiple moves that don't guarantee a loss, pick one of those.  Then you'll have a program that never loses, and also it will make moves that appear unpredictable.

Even though tic-tac-toe is an unwinnable game with two perfect players, some moves are better than others.  Against novice opponents, there are tricks you can use to moderately increase the likelihood that your opponent will make a mistake and lose.  This program doesn't know that.  It doesn't evaluate different positions as tactically stronger.  It just knows whether or not one player is guaranteed to win.

By the way, needless to say, this tic-tac-toe program does not have sufficient reasoning capacity to prevent it from launching a global thermonuclear war.  ;)  The computer doesn't have abstract thoughts; it's just following instructions.  Completely deterministic instructions for winning if it can.

Next time: Chess as a deterministic game.

Artificial intelligence in games, part 1

"Chess is not a game. Chess is a well-defined form of computation. You may not be able to work out the answers, but in theory there must be a solution."

- John von Neumann

I'd like to talk about some basic concepts of Artificial Intelligence, by talking about games. In a few posts I'm going to tell you how to play a perfect game of chess. Not just a good strategy, but a perfect strategy. With this strategy, you will always beat a non-perfect opponent. If no win is possible, you will most likely be able to end the game in a draw.

Unfortunately, once I've explained this strategy, you will realize that you can't actually use it. So before I talk about that, I'm going to try something less ambitious. I'll tell you how to teach your computer to play a perfect game of tic-tac-toe, also known as "noughts and crosses" in England.

Here's some quick background for those who don't know how to play. Tic-tac-toe is played on a three-by-three grid. Two players mark their squares, one with the letter "X", the other with the letter "O". Traditionally the X player goes first, and may place a mark on any open square. The players continue to alternate marks until one of two conditions is met. A player can win by placing three of his or her marks in a row -- either horizontally, vertically, or on a diagonal. Much more commonly if the players are experienced, the board will fill up, no player will get three in a row, and the game ends in a draw.

Complexity of tic-tac-toe

How many possible games of tic-tac-toe are there? One way to do it might be to count all possible sequences of moves. The first player has nine possible moves to make. The second player can only go in an unoccupied square, so that's eight moves left. The first player can then go in any of seven remaining squares. And so on, so the number of possible games is at most 9*8*7*6*5*4*3*2*1.

This is a common mathematical operation called a factorial. "9 factorial" is abbreviated as "9!" Factorials are very big. Some algorithms have a running time of O(n!), which can be extremely dangerous -- but I'll get back to that in another post. Luckily, in this case n is only 9, and 9! is a fairly manageable number: It's 362,880.

That seems like a big number to people who are good at thinking in the abstract but bad at storing large amounts of information. However, computers are the opposite, and 362,880 is a very small, manageable number of objects to explore.

It is also an upper bound. We know that there are no MORE than 362,880 possible games of tic-tac-toe, but most of the games resemble each other. Another trick we could apply is to calculate possible states of the board without thinking of moves. Each square can be in one of three states. Either it is empty, or it has an X, or it has an O. Thus, the total number of possible states of the board (legal or not) is 3^9, which is 19,683. So actually, there are no more than this many different ways to set up the board.

In fact, there are even fewer possible states, because many of them aren't legal. For instance, the board could contain all X's, but that's not the state of a real game, because the "O" player never got to move. So there are actually far less than 19,683 states, but all we need is a rough order of magnitude estimate to see how big a problem we have ahead of us.

Calculating all possible games of tic-tac-toe

If you go first in a game of tic-tac-toe, there are nine moves that you can make. The possibilities break down like this:

|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |

|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X 

Actually, these nine positions do not really represent unique games. Really, there are three unique moves that you can make: Go in the center, go in a corner, and go on an edge. The rest of the moves simply lead to rotated or mirrored versions of the same games. Some algorithms might take advantage of this similarity and reduce the search space, but for our purposes, it still doesn't take too long to treat all combinations as unique.

Now, if you go in the upper left corner, there are eight moves that the "O" player could make. Here are a few.

|  X | O |       X |   | O     X |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |       O |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |

Again, these do not represent unique games. For all practical purposes, the first move and the third move are the same game. But it's easier to program (though slower to run) if you don't bother trying to analyze the games.

In the next post, I'll explain how we can use this system for categorizing every possible game to write an unbeatable opponent.