Automated Chess Battling

Matt Watson writes "Here is a link over to a story on wired that talks about the upcoming chess match in Spain between the world's top 4 computer chess programs. The winner will go on to play Vladimir Kramnik for the second round of human vs computer chess. I think that "deep fritz" sounds the coolest and my money is on that one. Read the article from Wired"

Comments

Finite, but Big

[DanMcS]

According to my AI textbook, the number of possible legal chess positions is about 10^40. Assuming 1 "best" move for each position, you could store each move with, um, 4 bits to indicate piece to move, and 3 for each axis, 10 bits- 10^41 bits total. High end systems now have what, 4 GB of RAM? That's 2^35 bits, about 10^10. To store all the moves, you'd need ~2^133 bits, that's 1.24*10^30 Gigabytes.

And that's just the table. You'd need a pretty spiffy lookup function and table organization to find the entry you want in reasonable time. Though, now that I think about it, since you could track from the beginning of the game, you'd only need about 35 subtrees to every position based on what your opponent does, so that isn't as difficult as the raw memory required.

Chess is not near to being solved, I would say. Searching functions are a much better way to use the memory we have.

And even when we do solve chess (if memory doubles every year or two, that figure I gave above [2^130] could be feasible in a century or two), there's always Go, which has a branching factor of about 360, as compared to chess's measly 35 :)
--

Re:Where'd you get 10^40?

[DanMcS]

That site is discussing the game tree, that is, the possible sequence of moves. An average branch factor in a chess search tree is 35, and games might go to 50 moves each, so 35^100 is another number I've heard, that's about 10^155 possible nodes in a game.

However, that decision tree you linked to doesn't differentiate between identical positions arrived at by different routes. There are only 10^40 or so different positions on the board, and since we were postulating that from each one there is one perfect move, you just have to know it for each of them. No move would matter besides the current one.
--

Re:Finite amount of moves...

[Galvatron]

Wouldn't it be possible, then, to simply have a program with enough memory to know all possible moves and every possible game result, then allowing that program, at every turn, to simply perform whatever move has the highest number of possible wins associated with it?

No.

There are more possible chess moves than atoms in the universe, so you could not build a computer with enough storage space. Some have argued that there may be a much much smaller number of USEFUL moves, and perhaps we would be able to create a computer the plays a "perfect" game if we could somehow eliminate most of those useless moves before we started calculating (since otherwise we won't get done calculating until sometime after the Big Crunch, or the Big Freeze, whichever it is that ends up occuring).

The only "intuitive" interface is the nipple. After that, it's all learned.

Re:human advantage given less time?

[Scarblac]

In fact a quick time control is a huge advantage to the computer. No human can beat a computer at blitz, we need time to see the tactics. But with longer time controls, it's strategy that counts, and computers are still absolutely hopeless at that.

For instance, go to the site of last year's Dutch championships, in which Fritz also played. There is a Java applet with the games at http://chess.lostcity.nl/java/AppletNK2000.html. Click on round 7, the game Van Wely-Fritz SSS*.

The computer was absolutely hopeless and could do nothing at all during the whole game, because of the closed position without tactics. He will be mated after a few more moves, but the operator resigned.

Chess computers are, in essence, still brute force programs, albeit with a lot of pruning. There haven't been many advances in chess AI in ages. Their strength is going up pretty slowly, considering the hardware speed increases.

Kramnik will cream the computer.

Re:Give the AC a cigar

[Scarblac]

Such perfect move databases already exist. They started with all the positions with only the kings, they are all draws. Then they produce all the positions with an extra piece that convert to two kings (king takes) or that lead to an end position (for instance K and R mating a K). Since all positions are in the DB, you can deduce the perfect best moves. Some simple positions that look like a draw turn out to be mate in 224, that sort of thing.

The best databases for this do all positions with 5 pieces (so two kings plus three other pieces), and that takes up 4 cdroms.

Doing the six piece version is much, much bigger. For every position in the 5 piece databases, there must be about 55 legal ways to add another piece, and there are ten different pieces that can be added. So about 4x550=2200 CDs for the six piece positions (on that order, anyway, this is a very imprecise guess).

The initial position has 32 pieces. Fit on a DVD? Hahahaaaa... The size of the universe is a limit on storage.

Re:Genetic Algorithm...

[zaius]

Yes, you are oversimplifying it.

An AI that 'won' in a natural selection process agains other AI's is going to be adapted to playing other AI's, not humans. Much as land animals tend to fare poorly when put into marine environments, and vice versa; AI chess players won't do to well agains human opponents.

Also, there's an incredibly massive state space for chess... the first player has 10 options (8 pawns+2 knights) on his first move, so in the first pair of moves there's already 100 possible states... strategy and/or complete tree-traversals is nearly impossible (unless you encode the entire tree of possible moves beforehand, then search it... but I don't think we have that much storage capacity available yet...).

Brute force

[ryants]

One of the overlooked things about these recent advances in chess playing is that it is (often) more about advances in brute-force computational power than "true" AI improvements.

In other words, we really aren't any closer to understanding how a human chess master thinks.

I don't think we will make any significant gains in "true" AI until we sit down and figure out the principles of human intelligence, rather than trying a) mimicry or b) more silicon.

The analogy presented in most AI textbooks (Russel and Norvig, for example) is that of flight: for a long time man wanted to fly, and built machines with bird-like wings that flapped. Mimicry didn't work. Then they tried making wings that flapped a lot, or really hard. More horsepower didn't work. It wasn't until the principles of flight (Bernoulli's principle) were discovered that we were able to make flying machines.

Ryan T. Sammartino