Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

Automated Chess Battling 165

Posted by Hemos from the pretty-cool-idea dept.
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"
This discussion has been archived. No new comments can be posted.

Automated Chess Battling More

Automated Chess Battling

Comments Filter:

  • Many false assumptions (Score:1)

    by Anonymous Coward
    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.
  • 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...

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

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

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

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

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

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

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

  • 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.
  • 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.
  • but apparently the name Deep Thought is too risque, so it was renamed Deep Blue.

  • In Spain? (Score:2)

    by GC ( 19160 )
    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".
  • 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.

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

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

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

  • 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...
    --
  • Yes, I was taught exponents. I converted it to Gigabytes, and you didn't check the figures before you flamed me.

    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 [slashdot.org] 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 :) Definitely not more than the number of atoms in the universe.

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

  • Finite, but Big (Score:3)

    by DanMcS ( 68838 ) on Monday April 23, 2001 @02:31PM (#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? (Score:3)

    by DanMcS ( 68838 ) on Monday April 23, 2001 @03:47PM (#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.
    --
  • *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.
  • 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...

    -----

  • Nope. Move the A-pawn on the first move, and it can only move one rank next move.
  • 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.
  • 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.

  • 2^130? Were you not taught exponents in high school? That's around 10^39. That is...as they said, more than the number of atoms in the universe, so just where again where you planning to store this data?

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

  • The game history is only useful if you are not playing "perfectly". If you know you will checkmate in 3 moves then your opponents mindset doesn't matter anymore. The same is true if you know you can mate in 20 moves.
    --
    Be insightful. If you can't be insightful, be informative.
    If you can't be informative, use my name

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

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

  • 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.
  • You don't play much chess, do you?

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

    Malcolm solves his problems with a chainsaw,
  • 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
  • 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
  • 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

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

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

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

  • 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.
  • 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 [snoot.org] , 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.
  • ...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

  • I wondered when somebody would bring this up.

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

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

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

  • The evaluation functions for Go are not so bad, actually. The biggest problem is branching - the huge number of possible moves from any given position in the opening and middlegame

    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.

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

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


    +++

  • 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

  • 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 [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... (Score:3)

    by Galvatron ( 115029 ) on Monday April 23, 2001 @01:28PM (#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.

  • He was dismantled. I think his parts became some sort of weather simulation device.
  • 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
  • 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.

  • 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 (Score:4)

    by Scarblac ( 122480 ) <slashdot@gerlich.nl> on Monday April 23, 2001 @02:01PM (#270660) Homepage
    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.

  • 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?


    --

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

  • 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.
  • Yes, it would be a great project... the only problem is storage. Storing one possible game would, at minimum, require ~10k (really, really ballpark figure). Storing 10 billion games (and believe me, there are more than that) therefore takes 100TB of disk space... AFAIK there's only a few disk arrays in the world that have this much capacity (and they're probably all pr0n anyways...).

    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.

  • Re:Genetic Algorithm... (Score:4)

    by zaius ( 147422 ) <jeff@zai u s . d y ndns.org> on Monday April 23, 2001 @03:44PM (#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...).

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

    But this is not that different from what human contenders to the title do. They spend months training to beat the current title holder.

    Kasparov made two big mistakes one was to agree to play Deep Blue without being allowed to see it play a couple of games before hand. The second was to train against a simpler program, expecting deep blue to behave the same, but faster. This is akin to say that Kasparov and I play the same chess, only that he plays faster (I only wish)....

  • I don't know about anyone else, but did anyone else realize they could make that kind of money playing chess? I'm sure one factor to this was that I am an American, and I love my country, but I really wish our society had more things like this. I do know how to play chess, but I'd say the majority of people I know don't, and I am a pretty hardcore nerd. Ok, so I don't use Linux, but otherwise...at least being a nerd in high school. And there isn't even a chess club at my school, what a shame huh?

    Well, time to go practice on Yahoo!, and remember, never play anyone who's UID is "Shredder"
  • in the case of deep fritz, the deep refers (mostly) to SMP support. The standard fritz 6.0 lacks SMP support, so they added smp and doubled the price, and you have deep fritz.

    the deep prefix is getting a bit tired though. Maybe Hyatt needs to rename crafty to deep crafty, since it supports SMP out of the box.
  • well it is getting a little better. Of course, a lot of the improvements are not algorithmic improvements, but rather the use of big hash tables. The endgame databases are case in point, the nalimov tablebases (can solve any endgame up to 5 pieces, some 6 piece endgames as well) dramatically improve endgame performance of computers. Some positional knowledge is available to computers as well, schredder in particular has more positional knowledge than most computer programs, but it is still nothing compared to a strong GM.

    I think if kramnik can play a very positional game, and keep tactics to a bare minimum, he will win. If the computer can bust open the game and make it open, then the computer will win.

    Who knows though.
  • I think they are halfway to the point of making a great AI. Put the four AI's up against each other, then insert genetic algorithm code to modify the strategy for the losers over a few months, until one evolution dominates. THEN you put it up against a human.

    Am I oversimplifying the situation?

    Has anyone tried using a neural network for a chess AI?
  • 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.
  • 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/ [usgo.org]
  • 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!
  • I imagine a computer could probably determine a perfect checkers game (ie, unbeatable string of moves based on opponents reaction.) There just aren't as many possibilities as chess. Hell, there is probably a perfect chess game too - not that anyone knows it yet... or that any human could memorize it :)
  • It would be far more than memorizing a single game of moves. You would have to know the correct move to every possible move of the opponent. Obviously the opponent's cache of likely moves would decrease as the game wore on, but you're still talking an incredibly large number of possible games that you'd have to memorize. There is no "perfect game" where you can make the same moves every time and win... chess isn't a rubiks cube.
  • 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 (Score:3)

    by ryants ( 310088 ) on Monday April 23, 2001 @01:11PM (#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

  • Deep Blue (and its successor, "Deeper Blue") were essentially a advertisements for IBM's RS/6000 servers and (probably to a lesser extent) their decision support software.

    IBM was never very serious about maintaining Deep Blue on the world chess circuit. All they ever cared about was beating the World Champion for a one-time publicity stunt. It is very unfortunate that Kasparov agreed to the rather unfair terms they proposed, because many people still think that Kasparov was a better player than IBM's box.

    Now, of course, they refuse rematches, since they can only lose their reputation.

    Anyhow, Deep Blue is a Kasparov-killing machine, not a general chess-playing machine. It was tuned to Kasparov's game and no-one else's. Probably someone like Karpov would have beaten Deeper Blue hands down, since he was nearly as good as Kasparov but the machine wasn't built specifically to defeat him.

    I wonder what type of machines the software in this contest runs on--IIRC Deeper Blue was custom chess-playing hardware!

  • This wheel is already invented. freechess.org [freechess.org] has enabled (human|computer) vs (human|computer) chess over the internet since 1995. Their now commercial parent chessclub.com [chessclub.com] started in 1992. They sometimes have tournaments for homemade chess programs. Tim Mann's [tim-mann.org] XBoard/Zippy is a nice stable client if you want a GUI for your brainchild; RoboFICS is good if you don't.

    Someone on freechess.org usually sets up a mirror game for people to observe when there's a human championship. Maybe they'll do the same for the computer championship.

Slashdot Top Deals

You knew the job was dangerous when you took it, Fred. -- Superchicken

Close