Slashdot Mirror
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"
Yeah, unfortunately. Many of these chess programs are written to run on specialized hardware (for example: Deep Blue ran on a custom made machine optimized to traverse trees very quickly). Putting them all on one platform to run the genetic algorithm would necessarily bias the selection algorithm in favor of the program whose native hardware was closest to the host platform.
There's also the matter of fundamental algorithm incompatibilities: neural nets are not alpha-beta trees are not apples are not oranges. I'm not sure combining neural nets with alpha-beta trees would work in this context (although a neural net might make an interesting heuristic function).
ObJectBridge (GPL'd Java ODMG) needs volunteers.
Finding God in a Dog
It is also not the case that the what is good for me is bad for you. There are chess positions where what is good for me is also good for you -- for example, consider the situation where I am in 2nd place in a tournement. The 1st place player's game has finished and he is 1/2 point ahead of me. I need a win, period. Now, it is concievable that there is a position arises on the board where if I choose move (A) it leads to a state tree where there the win-tie-loose ratios are 25-50-25 but if I choose move (B) it leads to a state tree where the win-tie-loose ratios are 50-0-50. Now, it is good for me to choose plan (B) because that maximizes my chances of choosing moves that lead to a win. However, it also maxmizes your chance of choosing moves that lead to a win for you. It is important to remember that chess isn't played as a single game, but in a match or tournement where the game results have cummulative effects. Further, that while the value of the plan (A) above is arguably mathematically the same as plan (B) it is difficult to argue to a chess player that a 50% chance of drawing and a 25% chance of winning is just as good as a 50% chance of winning. We VALUE wins higher than draws, for a number of reasons. First, because of the ways rating systems work, the win is often worth more. Second, because of the fact that one's position in a tournement is significantly increased by winning versus drawing -- particularly in Swiss systems -- the win is worth more than 2 draws for most tie-break systems.
Yes. There is no need for AI after the data has been gathered. My guess is a program could be written to produce all possible real game moves. Then the tree of moves could be pruned based on moves which provide guarenteed wins. There would be two versions of the tree, Computer goes first, and Computer goes second.At this point, it would no longer be a matter of how powerful the computer was because it would get down to a single lookup in a db. Properly pruned trees would probably fit on a DVD. So any current box should be able to pay to a draw or a win every time. Computer against computer would always be a draw.As long as there are no limitations on storage and coding, I do not see how this approach is beatable.
In a place beyond time and space, in a land far better than this, look for me there...
It's a bit silly to hold these matches in Spain, isn't it?
These matches should be held in Cyberspace (oooooh - I cringe at the word)
The exchange of bandwidth between the two partys is minimal, the TCP/IP headers themselves outweigh the data for each move.
It will all come down to the best programmer, the one that wrote the best algorithms and the most efficient code. Poor human... Does he even stand a chance?
If player says something like "mate in 5 moves", they've seen a forced checkmate..... It's not showing the other guy the strategy, it's saying "Ok, I can see a forced end to this".
Anyway, giving Kremnik a copy of the program is very unfair especially if the copy includes the database of computer openings. Kremnik can then try to tilt the games towards openings that he knows in advance the that the program is not good at. As I understand it, chess players spend a lot of time preparing surprises and the rules of this computer vs. human match eliminates that for the computer. Also, it will look very bad for Kremnik if he loses with this kind of advantage.
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.
If you want to study AI, chess is the wrong way to do it. There is no reason to think that the human approach to chess is any more successful that brute force. Your average PC has much less total computing power that your brain, but it will still beat you at chess (unless you're a grand master). Given a limited amount of hardware, the computer's way of playing chess may be more optimal than the human way of playing chess. Humans aren't build for chess, they are build to survive in the woods. The fact that some of them can learn to play chess pretty well is a coincidence.
If you want to build a strong chess computer, there is no reason why it should be based on "true" AI.
If you want "true" AI, you need to pick a different problem to solve. Preferably one that's much fuzzier than chess. The game of 'Go' would be much more suitable because brute force doesn't work there.
The machine needs to be there physically so they can open it up and make sure Kasparov is not in there.
--
Slashdot: Failed Car Analogies. Amateur Lawyering. Anecdote Battles.
Perfect chess involves alot more than responding with a given move in response to a given board setup. The history of moves that got one to a given position can be just as important in that it exposes the mindset and intentions of the opponent.
This is going to be a stumbling block for computers for awhile, but it looks like brute force might be enough for now. I'm predicting though, that human chess players will adapt and learn how to beat some chess machines.
Computer programs have to analyze millions of trees that people don't, because computers lack a 'chessic instinct' - computers tend to make up for their weak ability to evaluate a position by just evaluating much more of them.
-bugg
According to this, there are ~3*10^78 atoms in the universe.
http://itss.raytheon.com/cafe/qadir/q1797.html
There are "only" (hah) 10^40 or so legal chess positions, so your statement above is not quite true. Gathering enough of them up to make memory might be hard, though. There are about 3*10^51 atoms in the earth, and 10^57 atoms laying around doing nothing useful in our sun, so scrape off some of those and we've got plenty. Or we could use some replicator tech to turn some small, useless planets directly into RAM...
--
Communication is only possible between equals
Yes, I was taught exponents. I converted it to Gigabytes, and you didn't check the figures before you flamed me.
:) Definitely not more than the number of atoms in the universe.
Yes, 2^133 ~= 10^40. It is also:
2^133 = 2^100 * 2^33;
2^33 bits is 1 gigabyte.
2^100 is about 10^30th.
As I said. My numbers weren't off. And I cited a source elsewhere in this discussion which puts the number of atoms in the universe at about 10^75. The number of atoms in the earth is around 10^51, IIRC, so 10^40th is plenty small, on a sufficiently large scale
Besides, if we use up all the atoms in this universe, we can just use a quantum computer, and do our computing with atoms from other universes which aren't putting them to good use.
--
Communication is only possible between equals
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
--
Communication is only possible between equals
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.
--
Communication is only possible between equals
*blink*
Er, how would you encode the strategy? There's the rub; Chess has a massive state space with a large number of possible transitions, after all.
The other bit is that AI vs. AI may lead to AIs that are only good at defeating AI opponents.
Only the dead have seen the end of war.
Or maybe we will be breeding some kind of super intelligent master race of chess playing AI. Hmmm...
"Don't worry Neo, these guys can only move diagonally"
"Whoa..."
Ah well...
-----
crazy dynamite monkey
Of course, this is nowhere near the level of play found at Schizophrenic Internet Chess Online , where most people think to a depth of 0. Chess without remorse!
Giving the human the source code is a great idea. (In practice, I doubt the human will be able to take much advantage from this, but it will certainly make it more embarassing when he loses!)
In fact, it would be even cooler if the computer players each could read each other's source code* and/or memories. Now *that* would be an interesting program to write...
* It should hopefully be possible to force the programmers to use total functions, or some other interesting but not turing-interesting way of writing their heuristics.
Now I really want to get back into playing chess. There goes another 10 hours a week minimum.
- tokengeekgrrl
Sorry, it isn't quite that simple. There is a matemathical endgame theory that covers the last point on the board (Berlekamp). It has been demonstrated that even professional players occasionally miss the last point in complex situations. unfortunately the theory does not generalize well for earlier positions...
In Murphy We Turst
I beg to disagree. In order to evaluate a position, you need to have some idea which groups are alive, strong, uncertain, weak, or dead. There are some simple heuristics for this, but they are pretty bad. The only way to be sure (at least of the extreme cases, dead or alive), is to read the positions out. This sort of tactical reading may require quite deep local reading, and isolating the borders of each tactical situation is far from trivial. A mistake in any of this may throw the evaluation off by a hundred points, making it worse than useless.
I think GnuGo is typical in that it does no global reading at all, only the local tactical stuff, and from that it estimates the value of several promising-looking moves, and chooses the best. On a fast machine it can do this in 10-60 seconds. Doing global read-ahead for the most promising moves, and their most obvious responses would slow this by a factor of 10 at least. And, not having a good positional evaluation function, might not give us anything at all. I do not see GnuGo going this way in the foreseeable future.
In Murphy We Turst
First of all, Go endgames are entirely deterministic. A good go player (say 3 dan or better) can read out endgames pretty much flawlessly, as can a computer. You can buy end-game tutuors which literally can't be beat.
Midgame programming is gradually progressing, but it's tough--not exactly because of the number of positions, but because of the vagueness in what defines them as strong or weak.
Openings are almost completely beyond current computer thought. Note that I didn't say computing power--it's our (current) lack of ability to translate abstract thoughts into deterministic code that limits computer Go.
I don't know where the programs are currently, but I'm quite sure that it'll be a good number of years and some serious advances in programming theory before Go programs even begin to challenge good players. Given that chess programs are roughly neck-and-neck with the best human players in the world, I suspect that it'll be a decade or two before go programs get that good.
"People who do stupid things with hazardous materials often die." -- Jim Davidson on alt.folklore.urban
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.
"The question of whether a computer can think is no more interesting than that of whether a submarine can swim" -EWD
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.
I believe posters are recognized by their sig. So I made one.
I've got a question, as someone with only a moderate knowledge of AI or chess (I constantly get whomped by xboard). While I'm sure that the number of possible chess moves and games is very large, it is finite, right? 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? Also, if this is how it's done, how is this intelligence?
--
Feminism is the wild notion that women are human beings.
I take it back... there are even more possible opening moves. Since a pawn can move one or two spaces, there's 16+2, or 18 moves for each player. That's a total of 324 possible states after the first round.
IBM had a better solution with Deep Blue, and that was to store all of the games played by Grandmasters in the last 100ish years, giving them a vast selection of good games to search.
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...).
But this is not that different from what human contenders to the title do. They spend months training to beat the current title holder.
Kasparov made two big mistakes one was to agree to play Deep Blue without being allowed to see it play a couple of games before hand. The second was to train against a simpler program, expecting deep blue to behave the same, but faster. This is akin to say that Kasparov and I play the same chess, only that he plays faster (I only wish)....
I don't know about anyone else, but did anyone else realize they could make that kind of money playing chess? I'm sure one factor to this was that I am an American, and I love my country, but I really wish our society had more things like this. I do know how to play chess, but I'd say the majority of people I know don't, and I am a pretty hardcore nerd. Ok, so I don't use Linux, but otherwise...at least being a nerd in high school. And there isn't even a chess club at my school, what a shame huh?
Well, time to go practice on Yahoo!, and remember, never play anyone who's UID is "Shredder"
Twitter.com/TrentonHyatt
in the case of deep fritz, the deep refers (mostly) to SMP support. The standard fritz 6.0 lacks SMP support, so they added smp and doubled the price, and you have deep fritz.
the deep prefix is getting a bit tired though. Maybe Hyatt needs to rename crafty to deep crafty, since it supports SMP out of the box.
well it is getting a little better. Of course, a lot of the improvements are not algorithmic improvements, but rather the use of big hash tables. The endgame databases are case in point, the nalimov tablebases (can solve any endgame up to 5 pieces, some 6 piece endgames as well) dramatically improve endgame performance of computers. Some positional knowledge is available to computers as well, schredder in particular has more positional knowledge than most computer programs, but it is still nothing compared to a strong GM.
I think if kramnik can play a very positional game, and keep tactics to a bare minimum, he will win. If the computer can bust open the game and make it open, then the computer will win.
Who knows though.
I think they are halfway to the point of making a great AI. Put the four AI's up against each other, then insert genetic algorithm code to modify the strategy for the losers over a few months, until one evolution dominates. THEN you put it up against a human.
Am I oversimplifying the situation?
Has anyone tried using a neural network for a chess AI?
Good quote, too many chars. Seriously, the slashdot 120 char limit sucks!
Chess is fine and dandy, but for a game that is much farther from being "solved" by computers, and for competition that is actually accessible by amateur AI programmers, check out the Computer Go pages at the American Go Association...
http://www.usgo.org/computer/
Probably someone like Karpov would have beaten Deeper Blue hands down, since he was nearly as good as Kasparov but the machine wasn't built specifically to defeat him.
15 years ago, when Kasparov was just starting out, perhaps. Now, Karpov doesn't stand a chance against Kasparov. According to the FIDE world chess ratings, he is only 12th on the list!
I imagine a computer could probably determine a perfect checkers game (ie, unbeatable string of moves based on opponents reaction.) There just aren't as many possibilities as chess. Hell, there is probably a perfect chess game too - not that anyone knows it yet... or that any human could memorize it :)
It would be far more than memorizing a single game of moves. You would have to know the correct move to every possible move of the opponent. Obviously the opponent's cache of likely moves would decrease as the game wore on, but you're still talking an incredibly large number of possible games that you'd have to memorize. There is no "perfect game" where you can make the same moves every time and win... chess isn't a rubiks cube.
Scruffies advocate trying lots of stuff and seeing what works best; a sort of natural selection.
Neats advocate trying to understand the problem on some fundamental level, then implementing a solution
Who will win? Hard to say. Both camps have contributed a lot to AI. Maybe nobody will ever win, and we'll need both "scuffy" and "neat" thinking.
When it comes to "true" AI, I just think that the scruffy approach has taken us far, but now it's hitting a (technological) wall... I think it's time for a dash of "neat"ness now, is all.
Ryan T. Sammartino
Ryan T. Sammartino
"Ancora imparo"
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
Ryan T. Sammartino
"Ancora imparo"
Deep Blue (and its successor, "Deeper Blue") were essentially a advertisements for IBM's RS/6000 servers and (probably to a lesser extent) their decision support software.
IBM was never very serious about maintaining Deep Blue on the world chess circuit. All they ever cared about was beating the World Champion for a one-time publicity stunt. It is very unfortunate that Kasparov agreed to the rather unfair terms they proposed, because many people still think that Kasparov was a better player than IBM's box.
Now, of course, they refuse rematches, since they can only lose their reputation.
Anyhow, Deep Blue is a Kasparov-killing machine, not a general chess-playing machine. It was tuned to Kasparov's game and no-one else's. Probably someone like Karpov would have beaten Deeper Blue hands down, since he was nearly as good as Kasparov but the machine wasn't built specifically to defeat him.
I wonder what type of machines the software in this contest runs on--IIRC Deeper Blue was custom chess-playing hardware!
This wheel is already invented. freechess.org has enabled (human|computer) vs (human|computer) chess over the internet since 1995. Their now commercial parent chessclub.com started in 1992. They sometimes have tournaments for homemade chess programs. Tim Mann's XBoard/Zippy is a nice stable client if you want a GUI for your brainchild; RoboFICS is good if you don't.
Someone on freechess.org usually sets up a mirror game for people to observe when there's a human championship. Maybe they'll do the same for the computer championship.