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"
After reading the previous postings, I noticed quite a lot of (sometimes completely) false assumption about computer chess that I would like to address.
- The competing programs all run on standard PCs (Deep Fritz and a special version of The Shredder can also take advantage of SMP-machines)
- These programs are capable of generating and evaluating hundreds of thousands up to millions of moves per second (at least my chess engine can do that.) On plain PCs.
- Knowing the source code does not help that much. A human simply cannot foresee the result of many millions of simulated chess moves/positions.
- Computer chess programs use a clever mixture of brute force and formalized chess knowledge. The brains of human grand masters seem to work rather differently. They seem to use a kind of very powerful associative memory, which was fed and trained during many years of extremely intense training and learning and playing. All grand human chess player have an excellent memory and extraordinary mnemonic capabilities. They seem to be able to detect patterns and structures of 'good' positions and interpolate between these patterns. No human player can actually explain this holistic thinking and describe how he actually makes his moves.
- The (huge) advantages in computer chess during the last years came mostly from algorithmic improvements. Increased CPU speed helps, but not that much. Very easy to understand if you consider that the number of possible moves grows exponentially with each ply. But modern chess programs use internal hash tables of several dozens of MB to store intermediate positions/moves. They also use table/DBs for the opening and especially for the end game. (All end games with up to five pieces have been solved.)
- My understanding about the match between Kasparow and Deep Blue is that the machine won because they had some grand masters in the Deep Blue Team who analysed the game and change the settings of the program to make it win. Human players normally win against chess programs by setting up very subtle traps which will be become effective only in more than 15-20 half moves. This is beyond the 'horizon' of a chess program, it cannot foresee these traps. But grand masters can, and they can change the evaluation functions of the program to take care of the trap.
There is a lot more to say about the topic, but it is getting late and my time runs out...
Juergen
These challenges should be done with another, more advanced game, such as 'Go'. Go is not amenable to brute-force solutions, as chess is, and therefore a program able to play a decent game would be a far greater achievement. To date, there are no computer programs that can beat a reasonably skilled Go player. (Of course, they can still beat me...)
Chess is just a more elaborate form of checkers, and is very close to being solved by purely brute-force methods. Computer chess programs shouldn't impress anyone.
Incorrect. The less time a human has to think, the more prone they are to dumb mistakes. Given a fraction of a second the machine can generally come up with a move that doesn't suck *too* bad. You can verify this by hooking up to one of your favorite chess servers and checking out the respective lightning/blitz/standard chess ratings of a computer player.
Machine chess has advanced to the point where they are impossible to beat tactically; best to up the time and rely on the human's (hopefully) better evaluation and tree-pruning algorithms to create a better strategy.
One of the many ways kasparov was 'disadvantaged' (from a human POV) against deep blue was that he didn't have enough time.
Incidentally, what is up with all the 'deep' monikers? Yeah Deep Thought was a great name waybackwhen but it's gotten old. 'Shredder' is much cooler even though it reminds me of TMNT...
The short answer is that the amount of memory you're talking about is, um, *way* out there. Most better chess programs try to approximate that with an opening book and endgame databases. (Heh, I think that's actually cheating, morally speaking, but then I've never been a big fan of the 'same old opening' .. maybe that's why I lose so much)
Many programs (including crafty, last I checked) can and do build their own opening books. (or you can feed it a pre-done one) .. The positions are stored along with their evaluations and a move is selected accordingly (higher-evaluated moves being played more often)
Not really, given that grandmaster games tend to be catalogued, scrutinized, and generally public knowledge. Deep Blue (and its programmers) had access to many of Kasparov's old games. In fact there is the true story (really) of one 'normal' student-player who fought out a draw with a grandmaster. The GM wondered how the student was finding his moves so quickly, and it turned out that the GM had actually played the same game before and the student had memorized it :)
Wish I could remember the name of that GM, but then I couldn't waste more time trolling /.
Unless it turns out that chess doesn't work that way. As I recall, in a 'perfect' game of Connect Four the 2nd person to move always wins.
Or a game of russian roulette with all six chambers loaded.
Saying "mate in 5" means that you will lose in 5 moves or fewer, no matter what you do. It's a little late to think of it as helpful advice.
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.
The problem is that the number of possible chess positions is on the order of 10^40 -- the branching factor for a decision tree is around 36, I believe. This means that for anything but the most trivial games, storing the full decision tree in memory is not possible with today's technology. Even if you put the problem in a vastly distributed network -- that 10^40 is really big.
This is why typical algorithms used in chess include limited frontier search -- you want to reduce the number of states you consider by use of a heuristic function. This function is informed by the pieces involved in the game, the positions of those pieces, etc.
Actually, I think this is not at all true. Wired's quality has degraded so much in the last few years, it's almost pointless to spend any time there. On the other hand, while not all articles on /. are amazingly good, the vast majority are interesting and keep my attention.
/. offers a unique forum and audience for discussion of topics that interest us all.
If however, there's something on Wired (or any other news site) that's interesting, why not discuss it here?
The number of possible positions isn't the
biggest problem, as far as I can tell. After
all, the number of positions in Chess is already
way too big.
The lack of an obvious evaluation function
(e.g. material in Chess) makes life hard.
The length of the game doesn't help.
The existence of the ko rule doesn't help either.
See the complete and utter Go links
page at http://nngs.cosmic.org/hmkw/golinks.html
-- You've got to get a hat if you want to get ahead.
If the 10^40 figure uses a definition of
"position" which includes the history
of the game, then ok. Otherwise, bear in
mind that just knowing which pieces are where
doesn't tell you enough.
You certainly need to know who has castled,
whether an en passant capture is possible,
the number of moves since the last capture
or pawn move, and indeed all previous board
positions so you could recognise repetition
of position if it happened.
-- You've got to get a hat if you want to get ahead.
Totally disregarding the last few centuries of humans who were better than machines, of course. The average chess-playing computer has only recently become better than the average chess-playing human, especially when you consider that the average chess-playing computer has been essentially hand-tutored by great chess players. I bet if I had that level of tutoring, I could beat many of the chess-playing machines on the market too.
Not that the machines won't have their day, and not that the day isn't at hand, but the article makes it sound like humans have been behind from the start and that isn't correct.
Your right to not believe: Americans United for Separation of Church and
As stated in my initial post, the only data you need to keep are the pruned trees, not the entire table of possible moves. Thought there may be 32 pieces in play, there are only a restricted number or valid positions those pieces can end up in during real play. Of those positions, there is only one per given state of play which would be optimal. So even at the start of play where computer goes first, there truth is for that state, there is one optimal move. There are 20 possible moves for the computer's oponent. There is then only one optimal move per state.The method used for pruning the tree is to first remove from the database each branch which leads only to a loss. Then based on the remaining tree you would seek out branches which lead to guarenteed wins, etc.I agree that the initial database would be astronomically huge, but the pruned version would not be.
In a place beyond time and space, in a land far better than this, look for me there...
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...
but apparently the name Deep Thought is too risque, so it was renamed Deep Blue.
cpeterso
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?
The problem is that current crop of chess programs aren't really "AI". They're (mostly) brute forcers that simply search the move tree.
There's a little "AI" element in the evalatution function that decides if one position is better than another, but it's not much.
It can be argued that giving all the info to the human is simply slanting the playing field the other way. Certainly in human vs. human, the players will study how the other guy has played and try to come up with opening lines that play against the other guys weakness. However, as "the other guy" you do some of the same stuff, such as plan to play something you haven't done before so your opponents study is less useful.
If one player is a computer, it's a little different. It's a bit easier for a human to change their style of play. It's not so easy for the computer (at least, it's not been so easy for the majority of the chess programs written to date, it's certainly possible to make a program that could change styles).
How humans do it doesn't mean much in the way that a computer does it. Humans and computers have very different strengths and weaknesses in their "brains". The computer can manage a very large search tree without any problems. The human can't and doesn't maintain search tree anywhere near the size that a computer can.
On the otherhand, the human is a great pattern matcher and can see that certain moves aren't even worth considering very quickly whereas the computer is "stupid" and has to search the tree to see the move is no good.
They way a top level chess player goes about move selection is very different than the way a top level chess program does move selection.
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".
http://www.wired.com/news/print/0,1294,43203,00.ht ml
Salon, Wired, and almost every other major web publication offers some option like this, and they are always about 50 times more readable than the "standard" version, and all the text is on a single page, so you don't have to wait for five pages. Most of the time, you don't have any annoying banner ads, either.
If the number of moves is more than number of atoms in the universe, why should that stop us?
:->
Haven't you d00dz ever heard about recycling? Where I live we sort out all the paper from the trash for recycling, so why can't the chess computer do this?
(just had to)
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.
Yea I forgot about that.
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.
The difference is that we can in fact make chess playing machines today.
But we can't make a good version of a human mind, that's true.
Interestingly enough, on Scrabble servers such as MarlDOoM, a computer (named ACBot) which uses exactly that 'greedy' strategy turns out to be not such a great player. I even beat it once.
Once you get two players who are really good at Scrabble, three factors are equally important: vocabulary (you're dead if you don't know useful words like QAT and KEX), strategy (blocking triple word scores, knowing when to open up the board and when to make it nearly impossible to play), and psychology (only with humans, of course - you can leave yourself a hook for a word that you don't believe the other player will know, and of course, bluffing over whether something is a real word is essential).
--
Win dain a lotica, en vai tu ri silota
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
Nope. Move the A-pawn on the first move, and it can only move one rank next move.
"All I do is eat and poop!" -- Bean
Maybe even better; it could make it easier for mere mortals to actually play against such machines without the need of much effort from its operator/creator.
Yes, because there is no bound on number of moves played. But for a match with a fixed number of moves N, there is some expression that describes the number of games that could possibly be played with that number of moves.
120 characters isn't enough to explain it.
Neither does the notion that the computer will inevitably win hold any water. Chess is a well understood finite situation? Even finite problems can be intractable or undecideable, in which case computers could not ever arrive at a single, verifyable solution. That is something a human can do, through intuition, which is a mysterious and powerful trait of intelligence. A human can prove something with an insight into the problem, a computer could never.
And Kasparov being beaten by Deep Blue? How many times had he defeated "chess master" machines prior? The fact the human brain can compete with and even defeat a machine with its incredible computational power says a lot in itself.
120 characters isn't enough to explain it.
Would this be related in any way to the Fritz chess program Sergei Avdeev had when he was on Mir? (there was a ./ story on it a while ago, but I couldn't find it; one of the pages it linked to was here.)
the coolest club on
So what? While it's cool that they're doing this (I love playing chess), I think it would have been better reported after it was over. Until then, there's nothing really to see here (unless you want to know what software will be competing). Just release the log of the games, including how long it took for each move. Then people can write progs to simulate the game.
I think scrabble would be a bit unfair to the human, and you can probably tell why.
Malcolm solves his problems with a chainsaw,
Malcolm solves his problems with a chainsaw,
And he never has the same problem twice.
I believe this fails because you have not really freed yourself from the limitations of brute force and perfect computation. Good strategy is not just something a human comes up with in a blink (well, unless you're lucky). Good strategy is developed over time, ie, you learn what could work and what don't, and why. ON A HIGHER LEVEL. This is where fuzziness, genetic algorithms and neural nets SHOULD work. Just don't expect to be able to verify it within reasonable time. You don't have to, you just have to beat the opponent.
Of course you have to rely on brute force to recognize and model strategies, and use brute-force tactics as conventional chess-programs when appropriate. However, the selection process of strategies could in theory be solved by fuzzy logic. However, I would expect more consistency using rule-based languages like prolog. Strategy is about knowing what details NOT to pay
attention to, ideas/creativity and experience.
The pattern recognizer would probably be the hardest part. The easiest initial solution could be to have several hard-coded algorithms, just like in conventional chess-programs that are used to evaluate position strengths.
I don't claim it's easy though, but it's much easier now than 10 years ago.
- Steeltoe
http://www.debunkingskeptics.com/
Is it? I think it's a horrible idea, and support the makers of Shredder to ignore this match because of it. Chess isn't about telepathy, so someone should make a new game for that. My reason for this? Basically, it allows for an unfair advantage to the human player. He/She can just study the code and take advantage of the bugs/features contained within. That's not chess. Study past games? Yes.
- Steeltoe
http://www.debunkingskeptics.com/
I'm by no means a chess expert, but I can fathom that these programs are well-known already. Just hire some chess-programmer expert to evaluate that specific code, and you might find some loop-holes. As the simplest example, many computer-systems tend to overvaluate their pawns, instead of better positions. That means the human players can easily beat a computer if you just know the tricks involved. Knowing the most powerful tricks involved against this specific program becomes insanely much easier if you spend time and money on evaluating the code, especially if it's full of comments and other documentation. Do you really think the greatest chess-eating people haven't done this already?
;-)
Another method is that you can just compile the source, give it a go against another CPU- or human player and discover the best paths of attack against this specific program.
Fair? I think not. It's easy to beat GNUchess if you just takeback enough. A hundred times or so when you're as weak as me
- Steeltoe
http://www.debunkingskeptics.com/
first off a genetic algorithm and a neural net are totally different things.
second, not it's wouldn't be easy. at least no to get good results. in a genetic algorithm your building virtual DNA. a set of something that is "fit" for something.
while the fitness could be how much you won or lost buy. i can't think of a way to convert a set of data into how to play chess.
btw: i'm out of the loop, i thought kasporv was still the champ, now it's this new guy. pretty young lookin.
-Jon
this is my sig.
isn't that a little more important. i know my C64 could kick MY ass. but i didn't hear about it beating the world champ.
IMO you could put GNUChess on a 10,000 nod beowolf cluster and kick the champs ass.
-Jon
(youd prob have to recode gnuchess to worlk over a dist env tho)
this is my sig.
In its training it had literally thousands of Kasparov games to view.
How could a chess champion allow such a matchup? Well at the time there was a split between FIDE (most of the world), and the PCA(Kasparov and a few other top players. IBM had all the leverage in dealing with Kasparov. They could go to him and say, "we're running a big marketing campaign that will be calling someone the world chess champion, and if its not you, we'll get someone from FIDE." Kasparov is essentially forced into tournament, or face someone else being recognized as the world champ.
That's just the way I see it.
t
A computer would *destroy* a human in scrabble, since with a reasonably powerful computer it's possible to try all words, and always make the highest-scoring one. For scrabble, this greedy strategy does really, really well (a bit of a heuristic about blocking TWS and similar might be the only thing worth bothering with as far as lookahead).
For checkers, computers can look ahead so deep that I'd guess (but I don't actually know) they'd also cream the human opponent. (Or, against sufficiently advanced players, tie.)
Go is a good one, though. Word has it that the best go computers can't beat even novice players with a week of training.
Well, lots of reductionists (myself included) believe that the human "thinking" is actually just a very powerful computer, and that the best way to "true" human-like play is in fact more power. Probably, humans are pattern matching and doing shallow parallel search (rather than exhaustive deep search). But I believe they are doing this through the massive and chaotic power of the human brain, not some kind of special ingenuity.
We can try to codify certain strategies, but the best way to encode these will probably turn out to be like the human brain does: lots and lots of tiny nodes, trained in a mysterious and incomprehensible way. Is intelligence really something that we can understand, or does it just fall out of a sufficiently complex system? You seem to say the former, I say the latter.
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
Actually there are 64^13 (=2^156) possibilities for the chess board (of course, many of which are impossible in real life).
(Each of the 64 squares could have one of {white rook, white knight, ... white pawn, black rook, black night, ... black pawn, nothing}), but since a maximum of half the pieces can be on the board at a time, you wouldn't need 1/2 of these entries. So a database with (slightly less than) 2^155 entries could "solve" chess.
It would be a very large but finite number, so yes, someday technology will solve chess as easily as it did tic-tac-toe in War Games
--
Sleep is just a poor substitute for caffeine, anyway. -Bob Lehmann
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 CARRIER
"Shredder" is really "Kasparov" in a box. He thought he could get a rematch with Kremnik this way...now he's pissed that he has to battle other computers first. Plus, he's not thrilled about spending a few weeks/months crammed in his little box at Kremnik's crib, being "evaluated".
--SC
You read fiction? I write it! Lemme know what you th
How does giving the source code of the program to the player make it fair? Are we to assume that when two humans play, the one human knows how the other will always react. Maybe next time we go to war each side should swap battle plans so it is fair Or maybe NOT
The first site I found claimed that there are 10^120 possible moves, which would be considerably more than the number of atoms in the universe.
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
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
He was dismantled. I think his parts became some sort of weather simulation device.
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.
At the moment I think that the best programs are rated around 7 kyu. Here is a link to the annual championships . Every year the ing foundation offers a grand price if someone can write a program that can beat a pro, but this will not happen in near future.
If you guys are interested in solvable games, then you should have a look at this thesis It describes games such as go-moku , connect four, othello and checkers. I think that they use partly brute force and partly clever analysis of the games.
From my experience with current Go programs, they are not so bad in the opening. They have huge joseki (standard opening) databases and very elaborated estimation functions.
The midgame is by far their weakest part. The best programs I tried played the openings as strong kyu or even weak dan human player, but the midgame was significantly worse, probably on the level around 5-10 kyu. I heard that one of the programs is officially certified as 5 kyu player, but it might be just marketing, I don't know. For me, it's usually interesting to play with programs giving them the maximum handicap (9 stones). I can easily win if I play tricky, but it's not easy if I play "fair" (not counting on the opponent's error).
Long ago, Mr. Ing offered 40 million Taiwanese dollars (over 1 million USD) to anyone who can write a Go program that can beat any Taiwanese professional. The contest ended in 2000, but I heard his son prolonged it recently till 2010. It's still very unlikely, though.
Deep Blue, for example, used the specialized chess processors working in parallel, so they were able to build deepest tree. BTW, IMB usually don't advertize this fact, making you believe it's so good because of the central processor, RS 6000.
Back to Go, it's almost impossible to cut the tree and the number of branches quicky exceeds any computer capabilities available today or, say, in 10 years from now.
Fortumately, Go programs currently have very interesting heuristic algoritms, trying to simulate the process of human Go player thinking... They are still weak, but even the fact that they play better than weak human kyu players - it's already amazing to me ( I personally tried to write my own Go player about 10 years ago, without any significant success :)
From the beginning of 90-s, the best backgammon programs play at a very high level and almost match the best human players. Currently, two best programs are JellyFish and Snowie. But they are still considered to be a little bit weaker than world champions. I would say, the same situation as with best chess programs and best chess players. They are almost equal, but humans are still better, despite that Kasparov-Deep Blue match :)
Could this not be a project for distributed.net or some similar organisation? Calculate "scores" of some kind for each of the possible states of a chess board? There's a stupidly large number of combinations, but Internet-wide distributed computing is better than any Beowulf cluster in existence...
Connect-Four on the other hand. That's a win for the first player. http://www.cwi.nl/~tromp/c4/c4.html
ok then your [sic] infringing on my copyright! Could you as [sic] me next time before STEALING my comments for your own?
Therefore, Chess has a value when using pure strategies - that is, one player has a best strategy that, if played, the other could do nothing to prevent the outcome!
Not quite. Tic-tac-toe has the same properties, but there is no guarenteed way to win. You can guarentee a draw, if you are perfect.
-Brian
"Faith strikes me as intellectual laziness." -Robert A. Heinlen
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 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.
According to AI researchers I've spoken to, the field of artificial intelligence is still in a "pre-science" stage. There hasn't been a unifying theory or someone (like Newton in physics, for example) to throw down the gavel with a conclusive, all-in-one set of findings. There are many schools of thought in AI research (genetic programming, neural nets, semantic trees, case-based reasoning, and symbolic representations, to name a few) that all have their plusses and minuses.
There really isn't a "true" AI when one can't define how to define the AI; in a sense, what is an intelligence? Is it a piece of code that changes itself? Is it a brute-force algorithm? How about a network of simulated synapses with threshold functions? When we don't have the metrics for defining something, it all comes down to how well you present your research findings in a way that makes it look apropos to the problem at hand. =)
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
If I'm not mistaken, one computer chess program might play very well against computers, and another might do very well against humans, so the winner of the computer duel might not be the best suited for the job against what's-his-name.
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.
The winner moves on to the eight-game match this October in Bahrain against Kramnik -- who will collect a cool $1 million if he wins and $600,000 if he loses.
Now thats my kind of contest, where can I sign up? (and I dont even play chess, but still, 600,00! yeah..)
air and light and time and space
Complete agreement.
This is exactly right. I would also like to further add that the Man vs. Machine debate is nowhere near over. The top human players are now routinely beating the best chess engines (Fritz,Junior,Shredder) now that they have a better conception of the machine's weaknesses and strengths. Weaknesses are long term planning, strengths are short term tactical calculations.
Another thing that has been discovered in the last 5 or so years is that machines tend to play very poorly in closed positions. (French defense, Caro-kann, etc) In these deeply strategic positions computers tend to move their peices around randomly with no "plan". The search depth is far beyond their computing power. They make no progress beyond maintaining a somewhat stable position while the human player instinctively knows how to slowly manipulate the game to his advantage. I hypothesize this strongly advantages strategic players like Kramnik and disadvatages tactical players like Shirov. I would have loved to see Tigran Petrosian play deep blue. A true tactical chess genius.
If Kasparov were to play Deep Blue again today, I think the general consesus among top chess players is that he would win, and win easily. Same for most of the other top players. Last year Siemens had a big human vs. computer event with most of the top GM's getting draws or wins.
Search for it here:
http://www.chesscenter.com/twic/twic.html
(Anti-goatse,anti-click filter)
But in all honesty, does the computer know the chessmasters technique and strategy? No? Then why should the chessmaster know the computer's strategy?
Fairness is a double-edged sword...
Good quote, too many chars. Seriously, the slashdot 120 char limit sucks!
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!
I would like to see a checkers or even a scrabble face-off between man and machine.
----
There's no point in being grown up if you can't be childish sometimes. -- Dr. Who
Not to bitch, but really: must you inform us of stories on sites like Wired? Isn't it fair to assume that most people who visit Slashdot are well aware of -- and probably check with at least the same frequency -- Wired's site?
Having an open comment forum, though, is nice. I visit slashdot for the insightfull comments on the articles, not the articles themselves.
Stupid like a fox!
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/
I'm not sure that reading the source code would help the chess player unless they also happened to be a programmer :-)
Although, I don't see why it should be neccessary in the first place... it's just a game, get a grip, folks.Yes, the humans involved should be allowed to rest, and in fact take as long as they want in pondering their moves against the computers. The computers obviously won't take long in deciding what moves they're going to play, but humans like to ponder.
Cedric Balthazar Rotherwood
Sun Certified Programmer for the Java Platform +
System Admin. for Solaris
It is interesting that playing chess for a computer is really a matter of computing power. The AI logic used has been around since the 50's. The more powerful the computer the more moves it can evaluate. Considering that speed and the number of moves being evaluated is very high in the computer, each second being thousands of moves shorting the time even a little bit between moves might give Vladimir Kramnik an advantage. Being he can not solves his chess problems the same way computers do and have any chance of keeping up.
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!
Chess is a complex game of strategy requiring great knowledge and instinct. Chess is also a wellunderstood finite state situation with well known attacks and counterattacks. It is no more surprising that a person can write a program to better play chess than it is that we write a program to better fly a jet. In the later case a human is needed only because we are in a near infinite state situation.
Not to bitch, but really: must you inform us of stories on sites like Wired? Isn't it fair to assume that most people who visit Slashdot are well aware of -- and probably check with at least the same frequency -- Wired's site?
There's got to be SOMETHING in your "bag-o-plentiful-submissions" that's just as interesting as a story about chess-playing computers, and that most of us HAVEN'T already read.
crib
Please don't read my journal
The number of possible games is much larger than the number of atoms in the universe
Isn't the "number of possible games" theoretically infinite?
I'm aware of that rule, but as I see it surely there is a "workaround" .. you could (theoretically at least, it would be stupid in a real game) move your left knight, then the other player could move his left knight, then you could move your right knight, then he could move his right knight, then you could move your left knight back where it was, then he move his back where it was, then same for the right knights etc .. i.e. you could create a loop of repeating a set of moves rather than repeating a single move. Or is this also case also included in the rule?
I built an engine for this sort of thing, written as a Java application. It could pitch two automated chess AIs against each-other, a human against chess AI, or a human against a human. The AI interface worked as long as they have HTML/CGI interfaces, and a small Java adapter class is written that supports the site. I think I even got started on a spectator interface. It had some neat special effects too [including fire animation on threatened pieces]. Anyone care to help me finish it up? I'd gladly GPL the code, and hand it over to a loving family. All it needs is some polish, bug fixing, and some new piece graphics (they were stolen from CM3000, I admit it). I would do it myself, except that I've already volunteered for too much GPL work.
Well, your fingers weave quick minarets; Speak in secret alphabets;
std::disclaimer<std::legalese> sig=new std::disclaimer; sig->dump(); delete sig;
Lotsa drama there....
I think I'm going to go set up my 486 to play my iMac in battle chess... think different indeed...
--The space between my ears was intentionally left blank--
Er...
Read the subject header.
--------
Bleah! Heh heh heh... BLEAH BLEAH!!! Ha ha ha ha...
The article says that the match between Kasparov and Deep Blue was biased towards Deep Blue. They try to level the playing field by giving the human the source code to the programs.
This sig intentionally left blank.
My impression is that real thinking will be needed in Go because of the fantastically larger number of possible positions.
I think that the game Video Chess for the Atari 2600 is the hardest chess game ever. Heck it can beat anybody. You set the option so that it can think for the longest amount of time before making a move and it never ever loses. Emulate the program on a computer that has a processor so that it doesn't take hours and hours for each move and you've got it. Video Chess, Atari, best ever. If you don't believe me, try to beat it.
The GeekNights podcast is going strong. Listen!
If you read the literature on neural networks you will find that chess and strategy games are usually cited as the stereotypical problem domain that a neural net is LEAST suited for. They're good for automation of such tasks as recognizing faces, patterns, applying rudimentary common sense in fuzzy, ill-defined situations, that kind of thing. Not problems like chess that are so well-defined and easily attacked by brute force computation. The same goes for genetic algorithms. You can usually, at least in theory, simulate any genetic algorithm with a neural network and vice versa. Neither approach works well on chess. The fuzziness and adaptability that are the prized characteristics of these systems are simply not very useful for playing chess! (Not that it might not be interesting, maybe, to try training a neural net to play chess, to see what mistakes it makes compared to a human beginner. But it wouldn't play a very decent game.)
Remember, a human grandmaster's brain operates on principles which at least served as the inspiration for neural networks. The best chess players that the entire neural paradigm can offer are not neural networks at all, but humans such as Kasparov. And these guys are now routinely beaten by conventional von-Neumann devices that simply carry out brute-force analyses of the board.
The most any analog device can hope for in a chess match against a digital computer- whether truly analog, such as a human brain, or artificial, such as a digitally simulated analog neural network- is to exploit the horizon effect (where the digital algorithm explores all branches up to N moves ahead, and remains oblivious to traps that lie waiting at N+2 moves). The horizon effect strikes digital computing paradigms rather abruptly and can become useful to you in the endgame when there's only a few pieces left on the board and it's easy to see that far ahead. But it's a rare analog processor that can even see halfway to the horizon during the middlegame. Frankly I don't see how Kasparov lasted as long as he did.
I trust what you say is true. It still doesn't affect my original point that chess isn't in a good problem domain for application of neural networks in their current forms. People are not neural networks.
Human players bring intelligent knowledge to the table (accumulated by humanity over centuries, no less) about chess strategy ("strategery" as W would say) that neural networks don't incorporate well on their own. People like to think of the human brain as a sort of big neural network with 10^12 nodes but NN models are only inspired by the brain. They miss a lot of subtleties that the brain has. A neural network that big wouldn't necessarily play chess very well at all. Not by itself, anyway.
Maybe incorporating a NN into a larger algorithm with more conventional modules in it (brute force, heuristic analysis, etc.) would be interesting. A NN might be capable of assisting an overall algorithm in making thousands of small atomic decisions per move, like whether to prune individual branch searches. Humans are clearly making decisions at some points in their analyses that aren't trivially duplicated in conventional von Neumann paradigms because they're hard to define. (Too much "fuzzy math"!) Like, everybody knows you don't do things like immediately start pushing the king out into the center of the board starting on move 2. A blind brute force attack will spend time searching unpromising territory like that. (Yeah I know that's a bad example because they all use opening books but you get the point.) How do you tell a computer how to recognize a stupid looking branch? They usually build a heuristic evaluation function with lots of IF statements in it, but they tend to be brittle. It may be possible to convert the problem into many smaller subproblems of recognition, and then you might be able to apply a neural network to that. But it isn't necessarily clear how you would do it.
"How does giving the source code of the program to the player make it fair? Are we to assume that when two humans play, the one human knows how the other will always react." Always? No. But in a match of this type, human players usually get to see tapes, write-ups, etc. of thier opponent beforehand to get some idea of the style of who they will play. You do get an idea in tournament play of what kind of adversary you will be facing. Plus, just having the source doesn't mean that he will be able to understand it. I mean, what if they wrote it in PERL?? :)
Eric Gearman
Atomic batteries to power! Turbines to speed!
I haven't read through all the replys, forgive me if this has been said before.
This isn't something all to amazing and fancy to me. These are commercially available programs. Set up a Quad Xeon box and load one of these babys up (SMP Capable) and you've got one of the worlds strongest computer chess machines in the entire world. Needless to say for some people that is super computer chess. It isn't though if you consider that there are similar, even those of lesser strength, computer chess engines battling these same processes and winning. Crafty comes to mine, created by Dr. Hyatt. It's a wonderful piece of coding, well commented even, quite possibly the strongest engine that is open source.
What seperates Deep Blue from these is that Deep blue was created for it's own specific machine, Code came second, muscle came first. These most likely started as a college programming project to get him an A that spawned into something else, or they might not. Either way Deep blue stands apart from these. I still do miss Deep blue and wish something would come around to take it's place as computer super champion.
I also look forward to the completion of Dr. Hyatt's Beowulf Crafty. Yes, a Beowulf capable computer chess engine, how's that for frightening? I'm scared by it already. Look long enough and you can find all the information about crafty, as I can't recall any URL's for you.
Computational Madness in a round package.
This bit is simply inaccurate. The best meat-based chess players like Kramnik, Anand, and Kasparov still win overwhelmingly high puls scores against even the best silicon chess computers on offer today.
It's hard for many folks with fath in thecnology to appreciate, but even an array of fast precessors with the best algorithms and extensive databases of every possible endgame position (with its best moves) and all known opening moves cannot score 50-50 against a run of the mill super grandmaster (FIDE ELO 2600+). There are now nearly a hundred known super grandmasters.
The Deep Blue event involved Kasparov (who did not defend his "title" for almost six years and refused the official qualfied opponents certified by his own organization) trying new and untested techniques designed to lure computers into mistakes and failing spectacularly. But humans immediately pointed out conventional winning techniques he could have used if he weren't committed to proving that computers are simply no good.
IBM noticed this and immediately disassembled DB and never again consdiered holding a match against Kasparov out of fear that he would shape up and play like a regular human. That's because IBM is aware that there are dozens and dozens of humans who can wipe out DB alive today.
The returns to brute force are less and less as the search deepens and the possible moves multiply. Computers continue to make advances but those advances are slowing and when Moore's Law peters out and stops handing a few more rating points to the silicon every year, it is entirely possible that human players will still be able to defeat silicon.
That tension, the possibility that there may not be a computer world champion in our lifetimes, is the tension that places computer chess among the most interesting developments to watch. Maybe the first computer WC will be a true AI, or maybe there will never be a computer that beats meat chess players.
And the question of what combination of subtle evaluations of shapes of pieces and patterns of play, and brute force human grandmasters use to play chess is a fascinating topic with many different answaers from different GMs. One thing common to top players is that they can think at least fifteen or twenty moves deep (sometimes as many as sixty or more) in the middlegame. Humans probably are not doing this by pure brute force like the machines (who thinik 15 to 20 moves deep also) but through a constant evaluation and pruning at evry step of the search tree and massive parallelism collapsing possibilities together into single computations. That's a software problem more than a hardware problem, and it makes computer chess seem much more fascinating and difficult.
-B. Earl
I never could beat Sargon Chess for the Apple II. Of course I was 10 and had no idea what I was doing.
Dancin Santa
For one thing, the power of these computer programs draw from generations of human experience with chess. Chess is one of the most studied, commented upon and recorded strategy games in existence. Show me a computer that learns from just the basic rules to play at the grnad master level and I'll really be impressed.
More to the point, playing chess isn't that impressive of an activity as games go. Certainly it is traditionally associatd with intelligence, and there is a particular kind of savant-like talent behind the grand master types. But in the end the number of potential moves in a given situation are rather limited and to a large degree the success of a chess program falls to the brute force of calculating potential moves ahead. Computer opponents have demonstrated significantly less impressive performance when playing less rigidly structured games such as Go or Backgammon.
It Is the Nature of Information to Transgress Artificial Boundaries
And what about GNU chess programs like Crafty or GNUchess? On a 1.3Ghz machine I thought they could beat any player or comercial product. Anyway computer vs humans are not interesting at all. only $$$ matters..
gee, I hope that the mothers of the world don't think that this type of gaming is too violent.
I didn't do it, and if I did, you can't prove it. Bart Simpson
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"
Yeah... but do they have guys that fight each like Battle Chess for NES? Battle Chess could take any of these fools anyday.
Casual Games/Downloads
"Chess is not mathematics," Kasparov told Wired magazine in February 1995. "Chess is fantasy. It's our human logic, not a game with a concrete result. Mathematically, it cannot be expired. The number of potential chess moves exceeds the number of atoms in the universe. It's a number beyond any possible calculation. Theoretically, it's unsolvable."
This simply isn't true. Chess is a strictly competative zero-sum game (what is good for me is bad for you and vice verse) with perfect information (there is a finite number of possible positions). Therefore, Chess has a value when using pure strategies - that is, one player has a best strategy that, if played, the other could do nothing to prevent the outcome! We just don't know what this value is... yet.
While this may be counter-intuitive, this was first put forth by E. Zermelo in 1913! But it requires rational players that consider all possible moves... something humans can't do but computers someday just might.
Dr. Walker of The University of Nottingham has a very interesting page on computerchess. On a general level he discusses techniques for chess computers. For anyone unfamiliar with gaming AI, I would recommend it as a good place to start.
RC
I'm in one of Dr. Robert Hyatt's classes this month, honing my Linux chops. The whole idea of setting up my own chess server on your home network is killer, especially because it is an example of open-source technologies that can have an "omigosh" effect on normal folks (RTFM if you want Crafty to work with other chess apps ... it's all on the FTP server, of course).
t ml
Want a copy of Crafty or find out if it will run on your OS? Stop by the University of Alabama at Birmingham's CIS department or find a mirror: ftp://ftp.cis.uab.edu/pub/hyatt/
Want to find out more about Dr. Robert Hyatt? Go here: http://www.cis.uab.edu/info/faculty/hyatt/hyatt.h
Even superheroes once were losers
I agree that to allow the human to read the computer's source code is somewhat rediculous. It's akin to allowing humans to hypnotise and ask other humans chess questions before the match. However, I believe that we do need to allow the humans to rest. That's only fair.
He should be allowed some practice games against his future chess program opponnent (assuming that he is unfamilar with it). The main reason Kasparov lost to Deep Blue is that he was unprepared, while Deep Blue knew had analyzed every nuance of every published game Kasparov had played.