Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Automated Chess Battling

Hemos posted more than 13 years ago | from the pretty-cool-idea dept.

Programming 165

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"

cancel ×

165 comments

Many false assumptions (1)

Anonymous Coward | more than 13 years ago | (#270579)

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

Re:human advantage given less time? (1)

mandolin (7248) | more than 13 years ago | (#270581)

shorting the time even a little bit between moves might give Vladimir Kramnik an advantage.

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...

Re:Finite amount of moves... (1)

mandolin (7248) | more than 13 years ago | (#270582)

Wouldn't it be possible, then, to simply have a program with enough memory

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)

Re:Unfair to the program (1)

mandolin (7248) | more than 13 years ago | (#270583)

If you want fair, then the programmers should have to make the computers build their own book

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)

Re:Unfair to the program (1)

mandolin (7248) | more than 13 years ago | (#270584)

Anyway, giving Kremnik a copy of the program is very unfair especially if the copy includes the database of computer openings

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 /.

Re:Give the AC a cigar (1)

mandolin (7248) | more than 13 years ago | (#270585)

Computer against computer would always be a draw

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.

Re:Give the AC a cigar (1)

mandolin (7248) | more than 13 years ago | (#270586)

Or a game of russian roulette with all six chambers loaded.

Re:Unfair to the program (1)

mph (7675) | more than 13 years ago | (#270587)

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.

Re:Genetic Algorithm... (2)

MAXOMENOS (9802) | more than 13 years ago | (#270588)

Am I oversimplifying the situation?

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 [sourceforge.net] (GPL'd Java ODMG) needs volunteers.

Re:Finite amount of moves... (1)

Bellwether (12891) | more than 13 years ago | (#270590)

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.

Re:Just Taking Up Space? (1)

Bellwether (12891) | more than 13 years ago | (#270591)

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.

If however, there's something on Wired (or any other news site) that's interesting, why not discuss it here? /. offers a unique forum and audience for discussion of topics that interest us all.

machines are ahead?? (1)

ethereal (13958) | more than 13 years ago | (#270594)

So far, the machine has the edge. The great Russian champion Garry Kasparov lost a six-game match in 1997 to IBM's Deep Blue.

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.

Give the AC a cigar (2)

rakjr (18074) | more than 13 years ago | (#270596)

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.

IBM's Deep Blue was originally named Deep Thought (1)

cpeterso (19082) | more than 13 years ago | (#270597)

but apparently the name Deep Thought is too risque, so it was renamed Deep Blue.

In Spain? (2)

GC (19160) | more than 13 years ago | (#270598)

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.

Programmer vs. programmer (2)

toofast (20646) | more than 13 years ago | (#270599)

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?

Re:Genetic Algorithm... (1)

Bob Dobbs (21396) | more than 13 years ago | (#270600)

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.

Re:Since Kasparov lost..... (1)

Bob Dobbs (21396) | more than 13 years ago | (#270601)

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).

Re:Unfair to the program (2)

Bob Dobbs (21396) | more than 13 years ago | (#270603)

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".

attention story submittors (1)

novarese (24280) | more than 13 years ago | (#270604)

When submitting a story to slashdot, please use the "printable" version when possible, ie:

http://www.wired.com/news/print/0,1294,43203,00.ht ml [wired.com]

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.

Unfair to the program (2)

scruffy (29773) | more than 13 years ago | (#270606)

This is almost as entertaining as the WWF. Shredder would be a great WWF name. Maybe someone already uses it.

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.

Re:Connectivity? (2)

jazman_777 (44742) | more than 13 years ago | (#270608)

For example: The Shredder team declined the invitation to come to Spain. I guess we can conclude from this piece that those computers aren't able to connect over public networks (yet?). If they can't do that i'm somewhat convinced they can't communicate directly between each other. IMO that would/could improve the games and totally get rid of any possible human errors.

The machine needs to be there physically so they can open it up and make sure Kasparov is not in there.
--

even if that set were small (2)

Illserve (56215) | more than 13 years ago | (#270610)

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.

Re:Always Chess! (1)

PurpleBob (63566) | more than 13 years ago | (#270612)

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).
--

Re:Do Humans stand a chance? (2)

bugg (65930) | more than 13 years ago | (#270613)

The source code would be absolutely useless, because even the best heurestics for evaluating positions does not compare to what a human of any serious level can do.

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.

Re:Finite amount of moves... (2)

DanMcS (68838) | more than 13 years ago | (#270614)

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...
--

Finite, but Big (3)

DanMcS (68838) | more than 13 years ago | (#270616)

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? (3)

DanMcS (68838) | more than 13 years ago | (#270617)

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:Genetic Algorithm... (2)

Stonehand (71085) | more than 13 years ago | (#270618)

*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.

How boring (2)

decipher_saint (72686) | more than 13 years ago | (#270619)

Couldn't the games be condensed down to super fast matches? How about we get two computers playing pong, it would just be one tremendously long round...

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...

-----

Re:In Spain? (1)

geofft (79878) | more than 13 years ago | (#270621)

Since they are even bothering to hold this event in a geographical location, it wouldn't surprise me in the least if they set the machine's consoles across from each other on the table, and had little robotic arms move the pieces.

Connectivity? (1)

Lion-O (81320) | more than 13 years ago | (#270622)

Nice article but unfortunatly (at least IMO) its just commenting on the thingie without giving us any technical details... What I'd like to know is how those machines will compete against each other.. Is this going the 'old fashioned' way (2 machines, 1 chessboard and the pityfull humans to operate it) or did they evolve on the programming _and_ the hardware allready? So far the whole issue is focussing on writing the software to actually compete. IMHO its a shame no one seems to care about other details like getting a competition to a more cutting edge. For example: The Shredder team declined the invitation to come to Spain. I guess we can conclude from this piece that those computers aren't able to connect over public networks (yet?). If they can't do that i'm somewhat convinced they can't communicate directly between each other. IMO that would/could improve the games and totally get rid of any possible human errors.

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.

Re:How boring (1)

Ioldanach (88584) | more than 13 years ago | (#270627)

Couldn't the games be condensed down to super fast matches?

Not really, since the programs require a good deal of time to decide their next move. One of the requirements of the chess playing program is that it be able to find an answer in an allotted time. A good deal of the evolution of the chess playing program has been in the area of refining what moves should be looked at so that the computer can find the best move more quickly out of the n^n^n... available games.

Deep Fritz? (1)

X_Bones (93097) | more than 13 years ago | (#270628)

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 [161.58.237.201] .)

Um . . . (1)

Kreeblah (95092) | more than 13 years ago | (#270629)

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.

Re:Unfair to the program (1)

Paradise_Pete (95412) | more than 13 years ago | (#270630)

You don't play much chess, do you?

Re:Always Chess! (1)

Trebuchet (98044) | more than 13 years ago | (#270631)

I think scrabble would be a bit unfair to the human, and you can probably tell why.

Malcolm solves his problems with a chainsaw,

Re:Unfair to the program (1)

Life Blood (100124) | more than 13 years ago | (#270635)

Just one problem. The program has access to the humans game history, the moves he prefers and openings he usually uses. It can be programmed to take this into account. The human should have an equivalent understanding of the computer. Chess masters don't go into their matches cold after all. Perhaps the source code wasn't the best way to do this, but it is a step in the right direction.

mod down... (1)

jon_c (100593) | more than 13 years ago | (#270636)

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 [homestead.com] . pretty young lookin.

-Jon

what about the machine? (1)

jon_c (100593) | more than 13 years ago | (#270637)

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)

Re:Unfair to the program (1)

haystor (102186) | more than 13 years ago | (#270638)

Uh, giving Kramnik the Computer's opening book is hardly unfair, since that book was developed by humans.

If you want fair, then the programmers should have to make the computers build their own book. This would set the computers ability back years as the initial position is relatively inscrutable.

Re:Since Kasparov lost..... (1)

haystor (102186) | more than 13 years ago | (#270639)

Yes they do actually. Deep Blue had many grandmasters working with the programmers to train it to beat one specific person. It played only 6 published games and was dismantled.

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.

Re:Unfair to the program (1)

haystor (102186) | more than 13 years ago | (#270640)

Well they can build their books from games played, but that doesn't mean its useful. Part of the problem is that if a specific line is successful for 40 years, then is disproven in 1 game, a computer has no concept of it being disproven. While all the humans might immediately drop that opening line, a computer will only see 1 bad instance against many successful ones, and continue playing it. That's a vast oversimplification of the problem, but even with the ability to build its own book, a computer needs to be fed what games it should build from.

Re:Always Chess! (1)

Tom7 (102298) | more than 13 years ago | (#270641)

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.

Is your "true" AI improvement really "true"? (1)

Tom7 (102298) | more than 13 years ago | (#270642)


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... (2)

Tom7 (102298) | more than 13 years ago | (#270643)

Of course, this is nowhere near the level of play found at Schizophrenic Internet Chess Online [snoot.org] , where most people think to a depth of 0. Chess without remorse!

"Open Source" Chess (2)

Tom7 (102298) | more than 13 years ago | (#270644)

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.

Deep Blue doesn't use AI... (2)

tokengeekgrrl (105602) | more than 13 years ago | (#270645)

...atleast according to IBM it doesn't. Below information are excerpts from IBM's Deep Blue FAQ, Does Deep Blue use artificial intelligence? [ibm.com]

The short answer is "no." Earlier computer designs that tried to mimic human thinking weren't very good at it. No formula exists for intuition. So Deep Blue's designers have gone "back to the future." Deep Blue relies more on computational power and a simpler search and evaluation function.

...

"There is no psychology at work" in Deep Blue, says IBM research scientist Murray Campbell. Nor does Deep Blue "learn" its opponent as it plays. Instead, it operates much like a turbocharged "expert system," drawing on vast resources of stored information (For example, a database of opening games played by grandmasters over the last 100 years) and then calculating the most appropriate response to an opponent's move. Deep Blue is stunningly effective at solving chess problems, but it is less "intelligent" than the stupidest person. It doesn't think, it reacts. And that's where Garry Kasparov sees his advantage. Speaking of an earlier IBM chess computer, which he defeated in 1989, Kasparov said, "Chess gives us a chance to compare brute force with our abilities."

Another interesting read is IBM's page on How Deep Blue Works [ibm.com] .

Now I really want to get back into playing chess. There goes another 10 hours a week minimum.

- tokengeekgrrl

hardware details? (1)

mrdisco99 (113602) | more than 13 years ago | (#270650)

So, what are the hardware specs on these machines? We've already seen an IBM SP beat a human. I'm wondering what other architectures will have a crack at it this time...


+++

I know why Shredder is declining! (1)

SpookComix (113948) | more than 13 years ago | (#270651)

The Shredder team declined the invitation to come to Spain. It felt that the rules of the competition in Bahrain tilted too much toward man, rather than machine. For example, Kremnik will be given a copy of the program to evaluate on his own.

"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

Re:Since Kasparov lost..... (1)

KingAdrock (115014) | more than 13 years ago | (#270652)

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

Where'd you get 10^40? (1)

Galvatron (115029) | more than 13 years ago | (#270653)

The first site I found [planetbig.com] 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.

Re:Finite amount of moves... (3)

Galvatron (115029) | more than 13 years ago | (#270654)

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:Why isn't Deep Blue participating? (1)

Verloc (119412) | more than 13 years ago | (#270655)

He was dismantled. I think his parts became some sort of weather simulation device.

Re:Deep Blue doesn't use AI... (1)

~MegamanX~ (119882) | more than 13 years ago | (#270656)

If someone would make "artificial grape flavour" so close to "grape flavour" that event the best taster would not make the difference between the artificial flavour and the real flavour, i would call it "artificial grape flavour" (or even "grape flavour")...

It doesn't have to be intelligence to be artificial intelligence. IBM here answer as if their definition of AI was really accepted by everyone, and it is not the case.

Automating human behaviour will be called by many people artificial intelligence. Taking humanlike decisions as well, even if the decision process is different then in the human brain. Some people try to make the machine think our way, some people want the same result.

(read Luger & Stubblefield or any other AI book to see that that the definition of AI is not as clear as what IBM can make us feel)

phobos% cat .sig

Re:Deep Blue doesn't use AI... (1)

~MegamanX~ (119882) | more than 13 years ago | (#270657)

[...] than in the human brain [...]

Sorry, my first language is not English.

phobos% cat .sig

Re:Programmer vs. programmer (2)

Scarblac (122480) | more than 13 years ago | (#270658)

This is *Kramnik*.

His style (positional, extremely good at tiny technical nuances, fantastic endgame, nerves of steel) make him a far harder opponent for computers than Kasparov was when facing Deep Blue (and he didn't reach his own level then).

The computers won't have a chance, unless the time control is quite fast.

Re:human advantage given less time? (3)

Scarblac (122480) | more than 13 years ago | (#270659)

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 [lostcity.nl] . 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 (4)

Scarblac (122480) | more than 13 years ago | (#270660)

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:the value of chess (1)

jbrians (135805) | more than 13 years ago | (#270668)

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

Finite amount of moves... (2)

Electric Angst (138229) | more than 13 years ago | (#270669)

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?


--

Re:Finite amount of moves... (2)

e_lehman (143896) | more than 13 years ago | (#270670)

Yes, this is theoretically possible. But the amount of memory required is really too much... there are 10^80 positions or something.

That said, I think it is not impossible to imagine that someone will figure out some custom compression tricks to store those 10^80 or so win-loss bits. I think chess could well be solved within a couple generations.

If had a program that could play perfectly, I'd set it to always make the WORST winning move. I think it would be hilarious to see it throwing away pieces, wasting moves, and still *just* squeaking out the win. :-)

Correction (2)

zaius (147422) | more than 13 years ago | (#270671)

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.

Re:Genetic Algorithm... (4)

zaius (147422) | more than 13 years ago | (#270673)

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...).

computer vs. computer != computer vs. man? (1)

ASMprogrammer (154812) | more than 13 years ago | (#270677)

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.

Re:In Spain? (1)

Joan23 (160086) | more than 13 years ago | (#270678)

BTW, if you go to Cadaqués ( the village were the meeting will take place ) and say that you are in Spain, a lot of inhabitants won't be happy.

There, the main feeling is that they belong to Catalonia and they are not proud of belonging to Spain. ( FWIW )

I like those odds.. (1)

PopeAlien (164869) | more than 13 years ago | (#270686)

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..)

Re:Why isn't Deep Blue participating? (1)

digitaltraveller (167469) | more than 13 years ago | (#270687)

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)

Re:Since Kasparov lost..... (1)

FortKnox (169099) | more than 13 years ago | (#270688)

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...

Genetic Algorithm... (2)

FortKnox (169099) | more than 13 years ago | (#270689)

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?

Re:Unfair to the program (2)

FortKnox (169099) | more than 13 years ago | (#270690)

But a good chess player will say stuff like "Mate in 5 moves." Giving the opponent an opportunity to see the strategy.

A true chess master wants the opponent to know his strategy, and how he plans on beating the opponent. Because if you can win and your opponent is helpless to stop you even though he knows how you are going to win, you, truely, dominate the game.

Always Chess! (1)

Beowulfto (169354) | more than 13 years ago | (#270691)

I would like to see a checkers or even a scrabble face-off between man and machine.
----

Re:Just Taking Up Space? (1)

AaronStJ (182845) | more than 13 years ago | (#270694)

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.

About the rest, I agree...the source code? (1)

cbr372 (193706) | more than 13 years ago | (#270696)

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.

human advantage given less time? (1)

Big Torque (196609) | more than 13 years ago | (#270697)

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.

Re:Why isn't Deep Blue participating? (2)

DmitriA (199545) | more than 13 years ago | (#270698)

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 [gmchess.com] , he is only 12th on the list!

The computer will win, eventually (1)

CharmQuark (200261) | more than 13 years ago | (#270699)

The notion that the best chess player should inherently beat the best computer program seems quite quaint. Such a concept belongs in the world of mid 20th century science fiction, in which house cleaning and nursing was automated but trajectories were still calculated with slide rules and triangles, rather that the real 21st century.

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.

Just Taking Up Space? (1)

cribcage (205308) | more than 13 years ago | (#270700)

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

Re:Some Corrections (1)

LuckyLuke58 (207964) | more than 13 years ago | (#270702)

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?

do they webcast? (1)

graveyhead (210996) | more than 13 years ago | (#270704)

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;

Hmmm... (1)

BigumD (219816) | more than 13 years ago | (#270705)

Lotsa drama there....
I think I'm going to go set up my 486 to play my iMac in battle chess... think different indeed...

Re:Finite amount of moves... (1)

madro (221107) | more than 13 years ago | (#270706)

From the article:

The number of potential chess moves exceeds the number of atoms in the universe.

So it's as possible as extracting the works of Shakespeare from the set of all possible C-strings less than (insert number of characters in longest play) characters long.

Why isn't Deep Blue participating? (1)

wrinkledshirt (228541) | more than 13 years ago | (#270707)

Er...

Read the subject header.

Re:Always Chess! (2)

zhensel (228891) | more than 13 years ago | (#270708)

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 :)

Re:Since Kasparov lost..... (1)

FreeMath (230584) | more than 13 years ago | (#270710)

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.

Re:Genetic Algorithm... (1)

sheetsda (230887) | more than 13 years ago | (#270711)

THEN you put it up against a human.

Why? Human champions have already been beaten by computers, and I'm sure todays AI plays even better than Deep Blue did.

"// this is the most hacked, evil, bastardized thing I've ever seen. kjb"

Neural Networks SUCK at chess (1)

MillionthMonkey (240664) | more than 13 years ago | (#270715)

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.

Re:Since Kasparov lost..... (1)

EFGearman (245715) | more than 13 years ago | (#270718)

"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

I'll let you try my Sargon-style! (1)

Dancin_Santa (265275) | more than 13 years ago | (#270723)

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

You may be surprised... (1)

nanojath (265940) | more than 13 years ago | (#270724)

A lot of the comments here presume that the human chess master will lose... I hardly think this is foregone conclusion. Certainly we are approaching a point where computational power and speed will insure that the best a human can acheive against state of the art chess computers is a draw. I don't know that we're there yet. But even so, I really question whether these kinds of contests say anything significant about the development of automated "intelligence."

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.

violence (1)

Targetman (308365) | more than 13 years ago | (#270730)

gee, I hope that the mothers of the world don't think that this type of gaming is too violent.

Re:Is your "true" AI improvement really "true"? (2)

ryants (310088) | more than 13 years ago | (#270731)

And here we have the classic division in AI between the "scruffies" and the "neats" :)

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

Brute force (3)

ryants (310088) | more than 13 years ago | (#270732)

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

Re:Why isn't Deep Blue participating? (2)

dorkstar (318427) | more than 13 years ago | (#270733)

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!

Battle Chess (1)

strictnein (318940) | more than 13 years ago | (#270734)

Yeah... but do they have guys that fight each like Battle Chess for NES? Battle Chess could take any of these fools anyday.

Re:I'll let you try my Sargon-style! (1)

CKW (409971) | more than 13 years ago | (#270737)


I was unable to beat the chess program entered in the 5k webpage challenge!

the value of chess (1)

redcup (441955) | more than 13 years ago | (#270738)

From the article:
"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 [nott.ac.uk] . 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.

Re:the value of chess (1)

redcup (441955) | more than 13 years ago | (#270739)

that is, one player has a best strategy that, if played, the other could do nothing to prevent the outcome!

To clarify: I never meant to imply the outcome of a chess game is theoretically a certain victory (is that an oxymoron or what?). The value of chess could easily be 1/2 (a draw).

And like tic-tac-toe, the value of a game does not mean you cannot win, but it does mean one player can force a certain outcome (whatever that outcome is for that particular game) every time.

Do Humans stand a chance? (1)

ryuspeed (443132) | more than 13 years ago | (#270741)

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.

To be fair to Kramnik... (1)

quarky2 (445397) | more than 13 years ago | (#270742)

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.
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...