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

 


Forgot your password?
Close
typodupeerror
×
Games Entertainment

4th Computer Chess Tournament 195

Posted by timothy from the what-about-computer-speed-chess dept.
An anonymous reader writes: "The 4th computer chess tournament is being held online at Internet Chess Club over the next two weekends. Over 50 chess programs are involved, from commercial engines to amateur homebrews. Most will be operated by their authors. Details at CCT4 homepage. Last tournament (CCT3) there was live commentary by titled human chess masters. If you're a fan of chess or computer chess programming, login to ICC this weekend as a guest and watch the action."
This discussion has been archived. No new comments can be posted.

4th Computer Chess Tournament More

4th Computer Chess Tournament

Comments Filter:
  • Especially with no speed throttle on the chess programs, I would imagine a normal game could be over in a few seconds.
    • I don't know, playing GNUchess at the easiest level, it takes the computer a few seconds per move. And that's in the opening, near the end it can take a little longer.
    • Lots of chess programs will compute out the entire game. Since the possible moveset increases exponetially every turn, calculating the whole game can take much longer than a minute in many cases.

      Now, if the engines chunk up the game into larger metamoves, they might take less time, but also wouldn't be able to do it with the same chilling accuracy a brute-force program could.

      • Since the possible moveset increases exponetially every turn, calculating the whole game can take much longer than a minute in many cases

        Calculating the whole game would take, on average, a few dozen orders of magnitude longer than the expected life of the universe, using current computers, so I'd call "much longer than a minute" a rather large understatement.

      • You must either be kidding or you don't know what you are talking about. No chess program can compute out an entire game is a minute.

        The fastest chess program Deep Blue, a 32-processor parallel computer with 256 VLSI chess engines, was capable of 200,000,000 positions per second which meant that it was able to conduct an exhaustive 12 ply (or 12 half moves) search for every move.
      • I'm taking a leap here, but you haven't coded any chess algorithms, have you.

        Any half-thinking programmer will realize when creating a chess-playing algorithm that the prediction branches are much more likely to decrease throughout the game, effectively (on a basic level) decreasing your moveset. One of the cornerstones of this type of game programming is algorithmic pruning of the game or 'moveset' tree. Every capable chess program strives not to create every possible move, but to eliminate all non-possible moves, as well as most non-likely moves. The path of the branch prediction and generation routines will usually use some sort of weighting algorithm to determine how deep to search, but the pruning algorithm is of utmost importance since it will aid in how deep the program will be able to search.

        Now, granted, an algorithm, given infinite time and computer resources may very well try to predict every possible move, but it's not just unlikely, it's also likely to get it's ass kicked by other, more effecient algorithms.

        Just my $.02

    • Moron (Score:1, Insightful)

      by Anonymous Coward
      Maybe you don't feel it while playing Quake 3, but *time* is still a constraint for many many computational tasks. Chess programs in particular would *love* to have 10^36 years to make each move. They only have a few minutes, so they *are* time constrained.
    • lol


      ive head chess programs taking days to find a good move.

    • Re:How long do the games last? (Score:2, Informative)

      by Anonymous Coward
      Are you serious? : )

      I don't know the exact time controls for this tournament, but generally for human tournaments they are something like:
      40 moves in 2 hours, 1 hours sudden death
      Which means you each get 2 hours to make your first 40 moves, and then one more hour each to make the rest of your moves.

      Computer chess tournaments use the same time controls (approximately, there are many variations, and they probably use "fischer clocks", where you get an additional 5 seconds (or some other amount) every time you make a move).
      The games probably proceed along similar lines to human ones:
      Lots of moves (more then 20 is not rare...) are played in about 5-10 minutes, because both players have played them all before, (and for the computer it's in it's opening book, and played instantaneously), until one of them decides to deviate. Then one takes a long think to evaluate the new position, play proceeds fairly rapidly after that, the computer will use most of it's time (why not? it can definetly find better moves the longer it thinks).

      Besides, most of these engines will just run on somebody's desktop, which are a far cry from the power of Deep Blue (IBM's computer used in the matches against Kasparov).

  • Hardware (Score:4, Informative)

    by GigsVT ( 208848 ) on Thursday January 17, 2002 @10:07PM (#2859814) Journal

    As for the hardware, you are free to use what ever you want. It would be impossible to try to get all participants use the same computer-power and to make sure that they do.


    Imagine.... :)

    Without equal hardware platforms, this will be hard to be more than just entertainment. It isn't much of a good benchmark of the programs involved.

    This is especially true when you consider that certain processors are usually faster at certain critical operations in cases like this. It also apparently doesn't ban ASICs and other things that could make a huge difference. On the plus side, maybe we will start seeing PCI chess accelerator cards. :)

    • Re:Hardware (Score:3, Funny)

      by sporty ( 27564 )
      That's ok. If you don't have the IBM super computer, you could always use, dare I say, a Beowulf Cluster? :)
      • BeoWulf clusters aren't yet applicable for computer chess. At least not any typical player vs. player chess.

        there isn't a, not that I know of, engine capable of harnasing a beowulf cluster. There are though several which are capable of mutlithreading.

        The only beowulf engine in development, again that I know of, is by Hyatt. The creator of Crafty.

        He's got a cluster of 10, Quad Xeon boxes at his disposal. Lucky man.
    • Without equal hardware platforms, this will be hard to be more than just entertainment. It isn't much of a good benchmark of the programs involved.


      This is true only to an extent (unless you're playing a blitz game). Speed is very important, but chess is way to complicated to "brute force" on any type of hardware that I'd suspect would be used at the compitition. Speed is better found with incredible move analysis algorithms that are smart enough to find the best move in a short amount of time. Take, for example, the Rebel [rebel.nl] chess engine. On an Athlon 1200 it is nearing a 2800elo rating. Of course, giving it an Athlon XP 2000+ may make a difference, but many good chess engines rely a lot less on hardware and much more on the software.

      Of course, it would still be nice if they all had equal hardware. I'm just pointing out that once you get a fast enough machine the hardware becomes much less of a "speed" bottlneck.
    • While I agree that this is strictly true, the hardware used does not vary dramatically -- most every one is a 1 GHz - 2 GHz machine. Considering that the branching in the tree of game possibilities is a combinatoral explosion, the differences in hardware alone will not allow researchers to explore to a significantly greater depth.

      The main problem in computational chess playing is not so much in the brute force with which you can explore the tree, but in how one prunes a branch when the option starts looking unpromising. That is really an algorithmic question, and I would be willing to bet that the best algorithm will in fact win in a competition of this sort. It is a bit analogous to taking two comparable, but unequal hardware machines, and running bubble sort on one, and quick sort on the other. Quick sort will always win, hands down, because it is the far superior algorithm.

      What did surprise me was that there were no parallel machines on the list -- not even an SMP. I do think that with enough processors and a reasonably sophisticated algorithm, an amateur team could in fact stand to beat a more sophisticated algorithm. But that isn't the case here.

      Bob
      • You are incorrect about the SMP.

        1,26GHz PIII Dual Tualatin
        512MB

        1GHz PIII Dual
        512MB

        1,2GHz Athlon Dual
        1GB

        800MHz PIII Dual
        256MB

        700MHz Xeon Quad
        512MB

        Etc...

        I'm surprised no one is using a cluster though. With hardware prices so cheap, a 6 node cluster can be built for less than $1500. I am doing that right now in fact.

        I am in total agreement with you about how algorithms are overriding in determining performance. I do think that algorithms that are on the same order of algorithmic growth will not be fairly compared to each other with diverse hardware like this though.

        I mean I know a O(n) will always beat an O(n^2), but with dissimilar hardware, you aren't going to be able to compare 2n+34 with 2000n+100, if you get my drift. A large constant coefficient difference in two algorithms may be concealed under a fast processor.
        • >I'm surprised no one is using a cluster though. >With hardware prices so cheap, a 6 node cluster >can be built for less than $1500. I am doing >that right now in fact.

          The latency of a (standard) cluster is too high to make it effective for chessprogramming. Moreover, it doesn't have shared memory, which is another major disadvantage.

          There has been a project to make programs run over a cluser (APHID, find it via google), but as you've already seen it didn't leave a terribly good impression.

          --
          GCP
      • You're completely right -- more optimal algorithms will beat the less optimal ones in this game of chess, probably.

        Just one minor nitpick, regarding your comparison of using the bubblesort and the quicksort...

        >Quick sort will always win, hands down, because it
        >is the far superior algorithm.

        I know what you mean by this, but that particular sentence isn't technically correct. There are in fact real occurrences (more common than we tend to realize, I think) when the bubblesort is in fact the superior algorithm. In certain situations involving semi-sorted data, it's hard to beat a bubblesort. Remember, an O(n) algorithm may only beat an O(n^987293487) algorithm after some particular cutoff point, which *could* be effectively infinite (the age of the universe, say) in some cases.

        Anyway. Carry on, I just had to say something..
      • >While I agree that this is strictly true, the >hardware used does not vary dramatically -- most >every one is a 1 GHz - 2 GHz machine.

        Considering that a doubling of speed is often said to equal about 50-70 elo points, the difference certainly _does_ matter.

        Many of the programs are very close in playing strength. A free 50-70 ELO boost can make quite a difference in where you finish eventually.

        --
        GCP
    • Hardware isn't as important in chess (ok, ASIC's would probably make a big difference) as in other programs. A factor of two in hardware speed difference would not even give one more ply in search depth, it will probably change it's rating by about 50-70 points but no more. Remember, chess has a very high number of branches per node (about 30), and a big factor in the strength of the program is to find smart ways to reduce that branching factor. I agree, though, that is not a good benchmark. This is just one more tournament. There are a lot of these every year (somehow, this one made it to slashdot). For a better attempt at benchmarks, go to the ssdf homepage [telia.com]
    • I can imagine the spam already:
      "Now YOU can help defeat the chess WORLD CHAMPION. All you need to do, is install this little program, send 5 US$ to this account number: Denmark 7656-3924414, juggle three roasted chickens and a frozen turkey. If YOUR computer is the one, to come up with the winning move, you will get ONE FREE TRIP to PARIS, France*.

      So, go download the program, by clicking on this link [www.distributed.chess], and YOU COULD WIN not only A FREE TRIP TO PARIS, but also A FREE PENIS ENLARGEMENT by looking at erotic pictures.

      *only elligible for people living on Champs Elysse Paris, France"
  • I really have to give major props to these guys. Once in school I wrote a basic chess game. The algorithims in it are hard as hell to write. And even harder to get them to win games. These guys must really know there stuff and I just have to say good job and good luck to all who entered!
    • Is it really that hard to make a simple chess engine? I'd imagine it is very complicated to make a good one, but I would also wager there are books with cookie-cutter designs for making a simplistic one.
  • I'd like to see a distributed chess engine. I think it would be fun to pit us against Deep Thought. It's kinda off topic, but something I've been thinking about.
    • It might be quite difficult to do ... how suitable is chess to being calculated in parallel.

      Determining the best move at a single point in the game can't simply be split up among X computers because there are a heirarchy of moves - the first move available can be chosen from a small pool but each of those leads to more and more.

      I suppose a monte-carlo like simulation would work - each machine picks a random move each time and returns the first move and the the final goodness. The master computer picks the best first move from the returned results.
      • Whereas most engines pick moves based on score, not very hard at all. Each machine would be given a move(and perhaps a reply, if enough machines existed), and would come back with the score of that move, with possible followup moves.
        I think it could be done.
        • Thinking about it some more, my initial monte-carlo method would not work because it would favour opponent's bad moves as well as your good ones. You have to assume, really, that your opponent is going to try :-)

          I think you would need a heirarchy of machines, which are handed off tasks when necessary - you can't simply break down the problem once each time it is your turn to move.
        • Well, distributing the computation over several boxes still has its inefficiences. Often programs will for speed's sake store position evaluations in a central hash table, or a history heuristic matrix or somesuch. Some of these techniques can be extremely useful in pruning the tree to be searched. One problem (I would imagine) is finding the tradeoff between communicating enough of this kind of information to nodes that could use it, and the network overhead it takes to do so. A simpler task would be taking advantage of multiple threads on an SMP box, like crafty [uab.edu]can.

          Apparently this hasn't stopped some people from doing the totally distributed approach though; try googling on "zugzwang chess program" for an example.

          • Re:What about this: (Score:2, Interesting)

            by hayne ( 545353 )
            Here's what Robert Hyatt (author of Crafty & Cray Blitz) wrote in the rec.games.chess.computer newsgroup in May of 2000:
            > How are transpositions handled by a distributed engine? Is there a distributed transposition table?
            Good question with multiple answers. Each machine would probably use a local hash table only. As a distributed hash table over the internet would simply not work, even with internet2 speeds. The latency/jitter is too high. But for a local 'beowulf cluster' yes distributed hashing is viable.

      • I don't think it is very hard. Game tree search is inherently parallel, you just need to be able to balance the assignment of subtrees so that you utilize processors well without too much overhead.

        Check out Cilk and Cilk NOW for instance:

        http://supertech.lcs.mit.edu/cilk/home/intro.htm l

        They have a parallel chess implementation.

      • Re:What about this: (Score:2, Informative)

        by Anonymous Coward
        Modern chess engines also do not just plow through every possible move... As that would take far, far too long. They use hash tables, and also do not only search through each line once, once they find moves that greatly change the evaluation of the position, they go back and try them again in other positions, and remember them to try first in future positions.
        They also have algorithms for selecting which candidate moves should be examined first in a given position.

        Also try to remember that the computer can only evaluate a position based on how the programmer told the computer to evaluate it. This depends on the chess strength and understanding of the programmer (well, programming team). And it takes years to aquire the chess knowledge required to evaluate a position accurately.
        I should know, I've devoted a significant portion of my life to playing, studying and teaching chess.
    • Are you sure you meant "Deep Thought"? That is the supercomputer built in "The Hitchhiker's Guide to the Galaxy". Although that would be an interesting computer to play chess against, I believe the computer you meant to refer to was "Deep Blue", the computer which Kasperov played against.
      • No, I meant deep thought. Deep thought will be built eventually, to program the Great Computer. =) But when it's done doing that, I'm sure it could kick the arse of deep blue any day of the week, even thursdays.

        You're right, I meant deep blue. My apologies
        • No need for apologies, the guy who chided you was basically wrong. Deep Thought was what IBM called the first version of Deep Blue. It was later changed (possibly for copyright reasons?) to the much worse name Deep Blue.
          Kasparov played his first match against Deep Thought and his second against Deep Blue.
          • Uh, no.

            This page from IBM [ibm.com] has a timeline of the development of Deep Blue.

            Summarizing -- A group of Carnegie-Mellon doctoral students (Feng-hsiung Hsu, Murray Campbell and Thomas Anantharaman) (mostly hardware guys!) built Chiptest in 1985. Special-purpose hardware with a chip design originally loosely based on Hans Berliner's Hitech. Evolving development leads to "Deep Thought" (someone was a Hitchhiker fan) in 1988, Hsu and Campbell joining IBM in 1989, Deep Thought II in '91, Deep Blue in '93, and Deep Blue II in '97.

            Deep Blue was not a very aesthetic name, but worth millions and millions to IBM in publicity, you can be sure.
      • Deep Thought would, with no problem, know your every thought and motive and predict EXACTLY your next moves till the end of the game.
    • The Deep Blue computer [ibm.com] by IBM was a parallel chess computer. Here is an excerpt from IBM's web page:
      The latest iteration of the Deep Blue computer is a 32-node IBM RS/6000 SP high-performance computer, which utilizes the new Power Two Super Chip processors (P2SC). Each node of the SP employs a single microchannel card containing 8 dedicated VLSI chess processors, for a total of 256 processors working in tandem.
      If you are referring to a geographically distributed system, similar to distributed.net [distributed.net], I don't think that would work in a chess program. Chess computers require fast communication between processors, which the internet does not provide.
      --- Mr Taco, tear down this wall!!! [slashdot.org]
    • Does Hemos really have hemorroids? I was going to switch teams for that guy, but if he's got hemorroids, I probably shouldn't bother. My last girlfriend gave me the clap, so, you know, I'm not into going down that road again, even for a hot stud like Hemos.

      I'm not otherwise gay, though. Not that there's anything wrong with that.

  • chess nerds (Score:4, Flamebait)

    by mr_gerbik ( 122036 ) on Thursday January 17, 2002 @10:14PM (#2859841)
    as if getting picked on for being in this chess club wasn't enough.. they had to go make an internet chess club to insure that nerds will get a good beating by the jocks.
    • I played football in college and I was also in the chess club. So eat that McFly. I guess I should have kicked my own ass?
  • I think it would make it wholly more entertaining if they printed out move-lists and provided a viewer which reproduced the moves, say one or two a second.

    It'd make the games more interesting to those of us who actually play (and don't just code chess), and it would get the public involved (can you picture a CNN short on this without having any sort of visual representation - it's the only way it'll get coverage!)
    • Of course they will. It will most likely be available in the standard PGN-format and a few of the commercial formats. Just use xboard (or winboard, if that's your cup of tea).
      But all the internet chess clubs also support interfaces, so that you can watch the games live on a chessboard with standard diagram pieces. win/xboard can be used for this as well.

  • Shannon and chess programming (Score:3, Interesting)

    by s20451 ( 410424 ) on Thursday January 17, 2002 @10:16PM (#2859848) Journal
    I was reading through the biography of Claude Shannon (information theory guy) and was surprised to read that he also did important research in chess-playing computers. The biographer suggested that his innovations are still in use today. Does anybody know more about this? How do you program a computer to play chess, anyway?

    • Re:Shannon and chess programming (Score:5, Informative)

      by dimator ( 71399 ) on Thursday January 17, 2002 @10:24PM (#2859890) Homepage Journal
      http://www.howstuffworks.com/chess.htm [howstuffworks.com]

      (Is there anything that site doesnt have?)
    • Chess computers are pretty boring. Every single one uses the standard alpha-beta algorithm, used in most games, with modifications for hashing. The difference comes in the evaluation of the leave positions, which position to "extend" (extensions mean that the position is deemed unstable, so you calculate a bit further), in which order the different moves in a position is evaluated, etc.
      • Good point. The reason is simply because alpha-beta is relatively simple and works so damn well.

        It's not very nice to spend hours and hours developing something new and seeing it get torn apart in the next tournament by much simpler things. There was only one attempt that was moderatrely successfull that I know of, and that was UlyssesCNS, using Parallel Controlled Conspiracy Number Search.

        --
        GCP

    • Re:Shannon and chess programming (Score:5, Informative)

      by E-prospero ( 30242 ) on Thursday January 17, 2002 @10:51PM (#2859995) Homepage
      How to program a computer to play chess: ($0.10 version)

      The underlying idea: you try an build an exhaustive tree of every possible move, and every possible response to that move, and every possible response to that response, and so on. This gives you a full tree of all possible games; You then choose a branch on the tree which results in you winning.

      The problem: This tree is huge. After just a few moves, there are literally billions of potential board positions which must be considererd. Even Deep Blue (the recent Kasparov killer) wasn't able to perform full board evaluation, even with all it's specialised chess-playing hardware.

      The solution: Rather than trying to exhaustively search the entire possible move tree, only search those branches which "look promising". This is assessed using a scoring system of some kind.

      It is this scoring system (called a heuristic) which is the source of all the research. This is a source of interest to information theorists as the problem of finding a chess heuristic is easy to understand, but non-trivial to solve. Essentially, the problem is to reduce the "information" describing a board position into a single boolean "this is a winning position"/"this is a losing position".

      If you're interested, seek out an introductory AI textbook (or website), and look up alpha-beta pruning. I can recommend "Artificial Intelligence: A modern approach" by Russell and Norvig. The website for the book is here [berkeley.edu]

      Russ %-)
      • If you think that a tree of all possible moves for chess is huge, you should try Go. There's so many more possible moves in just the first 4 or 5 turns.
        • AFAIK, *no* program designed to play Go has come anywhere close to beating a human that is remotely good at the game. Show me a successful Go AI, and then I'll be impressed. :)
          • I found a Go game for my Palm V. It was supposedly based on GNU Go, but the AI was so poor, that even myself, a beginning Go player could beat it 90% of the time. (It didn't even score right.. ugh.)

            Anyway, GNU Go [gnu.org] is pretty good, scoring 8th in the 21st Century cup.

        • "Go has a high branching factor due to the enormous board size but branches also get pruned a lot faster because there are extensive libraries of patterns known to be bad."

          Umm... Joseki, the patterns you mention, though extensive, do not lead to pruning per se. In Go one is going for a one or two point gain so the Joseki tend to be subtle. Also they are 'localized' patterns and do no guarantee a win. (Tactics vs. strategy.)

          "Scoring a chess position is not as exact."

          I disagree... Chess IMHO (compared to Go) is only tactical. Chess positions have been just as well studied as Go and each position is well known. Merely choosing a Queen side castle vs. a King side castle decides the direction of the whole game of which the repercussions are obvious (e.g. both players choose Queen side tends to lead to attrition, one or the other choose Queen side tends to lead to and 'interesting game', and both King side is rather normal...)

          In Go a certain Joseki pattern in no way guarantees what happens on the other end of the board...


          Just my $.02, from someone who once played on chess and got 'converted' to go...

        • The most successful Go programs primarily use pattern-matching, cellular automata, and neural networks. None of them are really very good.

      • This article [wired.com] at Wired a few months back is an intriguing read on the recent history of attempts to improve chess progams and their performance versus notable humans (such as Gary Kasparov and V Kramnik).

        Particularly notable (if you are a Kasparov fan) is the description of how Kasparov was, from a certain perspective, manipulated into a match setup which he could not win (wrt the Deep Blue match a few years back).

        For example, he never got to view any of Deep Blue's previous games -- whereas in a human match, any world class grandmaster would certainly have studied his opponents games before hand as preparation.

        Secondly, Kasparov didn't actually play the same program through the whole match -- the program was tweaked as the match went along.

        This subject is quite fascinating in that some people have historically treated the 'can a computer play better than a human' question as sort of a low-level Turing test milestone.
        • >For example, he never got to view any of Deep
          >Blue's previous games -- whereas in a human
          >match, any world class grandmaster would
          >certainly have studied his opponents games >before hand as preparation.

          They barely got the machine assembled and tested before the match. He got no games simply because there weren't any yet!

          >Secondly, Kasparov didn't actually play the same >program through the whole match -- the program >was tweaked as the match went along.

          Can you imagine telling Kasparov he's not allowed to learn anything from the previous game? It's not because he learns that he becomes a different man.

          The situation in the Kramnik-Fritz match is just as bad. They aren't even allowed to fix bugs in the program. Is _that_ fair?

          --
          GCP

          • The real unfair part is that Deep Blue could use its opening book, while Kasparov couldn't. Considering that Kasparov lost the final game by playing a known losing opening move, this literally was the differnece.

            If the player has to use only memory for openings, so should the computer.
            • The real unfair part is that Deep Blue could use its opening book, while Kasparov couldn't. Considering that Kasparov lost the final game by playing a known losing opening move, this literally was the differnece.

              If the player has to use only memory for openings, so should the computer.

              Huh? What's the computer equivelent of a human's memory? If it's RAM/ROM, why should it make any difference why it should load it from hard disk or RAM/ROM - it's a difference of cash thrown at the problem.

              Kasparov had no excuse for the final game. From what I understand, had he played that game against a human grandmaster, the human would have savaged him as well. Grandmasters don't mess up the opening game, at least not if they want to stay grandmasters. He was rattled - but that's the way grandmasters lose to other humans, too.
      • AI, huh?

        I think *true* AI would not have the programmer(s) assign the "scoring positions." A system of mixing the programmers "scoring" agenda with permutations of moves still plays to the bias of the programmer. The good/bad position argument should ideally be resolved by the program itself, and the game's own "learned" experience. Obviously the rules themselves dictate which moves are stronger/weaker.

        What about "learning" the opponent? Of studying previously played games? (Which was one of the issues with the Deep Blue match).

        Theoretically two well designed game engines should always end in a draw when playing against each other.

        My Palm has a pretty tough chess game... on the easier settings, it literally lets people win by tossing in a random obviously "dumb" move. At its best level, it is very difficult to beat by most mortals. I wonder how fast that processor is... or how many KB the game is? 15 years ago there were decent chess games on relatively primitive equipment. Not that these will win some fancy tournament... and not that there aren't corners being cut... but these definitely are not AI!
        • As someone with a PhD in AI, who has lectured on the topic at University, allow me to assure you that Yes, this is AI. However, it is not what the public generally thinks of as AI.

          AI research suffers from the major problem that it started out with grand intentions (machines that think like you and me!), and has had some great publicity, but 50 years on, it hasn't delivered on many of its promises.

          Those in the trade generally classify Search, categorisation and optimisation problems like this into the category of Weak AI. They exhibit "intelligent" behaviours - i.e., they are driven by knowledge, and make informed decisions - but they are algorithmic, and cannot adapt, develop or expand upon their original programming.

          The other form of AI - the form promised by movies and books - is referred to as Strong AI. This is a largely untouched problem - mostly because it is extremely difficult to even quantify what it is we mean by "intelligent".

          In some ways, Strong AI defies quantification - if you can clearly define what an intelligent behaviour is, you can define an intelligent algorithm to follow - but this implies that your algorithm isn't intelligent, as it won't move outside its programming.

          As for your Palm chess game - are you sure that on lower settings the program is "letting" people win by throwing in an "obvious dumb move", or is the move selection heuristic for the program just poorly suited to certain game positions?

          Russ %-)

  • Chessmaster? (Score:1, Troll)

    by pgpckt ( 312866 )

    I always wondered why Chessmaster and other well known commonly avaliable commercial chess programs don't compete in these competitions. I would think it would provide:

    1) Great exposure for your program
    2) A great way to motivate your programming staff to work at 100%
    3) A way to show you are number 1

    And for the programmers, if you acutally win, it would seem one of those great things you can put on a resume.

    So why no chessmaster?

    • Re:Chessmaster? (Score:4, Informative)

      by phantumstranger ( 310589 ) on Thursday January 17, 2002 @10:28PM (#2859907) Homepage
      Chessmaster [chessmaster.com] is not a fully functioning chess program. It is really more of a DB full of a shit-load of games (at least with CM 8000) and a teaching program. While I agree with damn near every other player in the world that CM is the best commercial chess program for learing, I have huge doubts with how it would match up in competitive play. I can reguraly beat CM8000 and I'm a tentative ~1500+ rated player. (In comparison the top three players in the world [fide.com] are well above 2700 and two are above 28.

      • I can reguraly beat CM8000 and I'm a tentative ~1500+ rated player.

        Are you sure about this? My ELO is around 2200 and has been so for a few years. For you non-chessplayers, that means that statistically I should score about twice as well against a 1500-player than Kasparov should score against me (although admittedly the system tends to break down when the difference is that large, but you get the picture). When playing against CM6000 on the championship-level (full power, no takebacks, etc) on my K6-II 450 Mhz, I almost always get the snot kicked out of me. I've managed a few draws but that's it.

        I am not saying that you're lying, though. Some people are really good at playing closed positions (Stonewall as white and such) and specialize in beating computers. It just seems unlikely. The CM-engine was even rated #1 at one point (in 1999, I believe) on the SSDF-list (SSDF is the voluntary organization that rates chess programs).

        • Normally from black I play, if given the option, a tight closed game (closed game based on ..1. d4) from white against humans in play-play games I open with the Grob Attack (1. g4) unless I know the strength of my opponent against obscure opennings to which I fall back on the old faithful (1. e4).

          Against computers there are definite ways to play them - look for a book called (by far my favorite book) Why You Lose At Chess [amazon.com] (not that you do or that you need it) - for instance, against a human you can generally throw a monkey-wrench into your opponents good position (or at least the psyche of it) by advancing a pawn on the King side.

          You don't have that option with machines. The only way to play it out is to play out your openning further than you normally do and not make emotional moves. Not to mention machines being extremely predictable.

          As far as my rating goes, I don't play tourney often, actually, I rarely do - school gets in the way. Although it could be and looks like its going to be worse 'cause Chess is starting to get in the way of school again. Ooops.

          Seriously, drop me an email so we can get together and playt some. I always look for new strong players.

      • You are misguided about chessmaster's strength. Chessmaster 8000 regularly plays in these tournaments and does rather well. It may not beat Fritz or Shredder but it's right below them and above Crafty, etc. It's rating is high 2600's.

    • Re:Chessmaster? (Score:5, Informative)

      by CyberDruid ( 201684 ) on Thursday January 17, 2002 @10:36PM (#2859932) Homepage
      Usually they do compete.
      Chessmaster is not an engine per se. It uses "the King", which was written by König. If the King is not in the competition it is probably because it is a bit old and not up to the challenge of beating Fritz, Deep Junior, Shredder, Chess Tiger/Gambit Tiger, Ferret and the other really strong programs.

    • Re:Chessmaster? (Score:3, Funny)

      by hangdog ( 8755 )
      Because this sticker wouldn't help sell copies of the game:

      "Chessmaster 9000. We finished 12th in the All-World Computer Chess Competition!"

      Probably too much risk for them. Maybe they would enter the program under a pseudo-name?

  • USCL (Score:2, Informative)

    by Tuxinatorium ( 463682 )
    USCL [uschesslive.com] is better than ICC, and free for all US Chess Federation members.

  • Related (Score:3, Informative)

    by phantumstranger ( 310589 ) on Thursday January 17, 2002 @10:21PM (#2859877) Homepage
    There were plans to hold The World's Largest [onlineworldchess.com] chess tournament ever (via the 'Net but the record would go beyond "just a 'Net record"). The event has been put on hold due to "The present economic situation and dramatic turn down of internet sales in the aftermath of September 11."

    More details are at the site and at the FIDE's network site [fide.com] (Fédération Internationale des Échecs).

    As far as this tournament is concerened, I welcome it entirely and enthusiastically. Finally there will be a way for the greatest chess programmers (in theory) to be under the "same roof" and possibly get together to swap secrets so that the mid-level bots on-line could actually dish out something other than four variations and stumble the rest of the way through.

    And to any players on /. that are also on USCL [uschesslive.org] drop me an email through my link and we'll see if we can get together for some games.

    See you on board :o)

    • One thing I've noticed about the participants is that there's a lot of machines running the AMD Athlon or Duron CPU's. Let's see if the programmers an wring out the power of the FPU on the Athlon/Duron to get a winner. :-)

  • Gnuchess (Score:3, Insightful)

    by damiam ( 409504 ) on Thursday January 17, 2002 @10:23PM (#2859881)
    Why isn't gnuchess [gnu.org] in this tournament? I'd love to see how it stacks up to all the other engines.
  • So if Kasparov operates an IRC client, would that be cheating?

  • Chess for the Hive Mind (Score:3, Interesting)

    by Tom7 ( 102298 ) on Thursday January 17, 2002 @10:52PM (#2860001) Homepage Journal
    If you want to play your own game of chess against people all over the internet, check out SICO [snoot.org] . People take turns playing a single move in all sorts of wacky variations. It's weird but addicting...

  • ICC history (Score:5, Interesting)

    by Bremen24601 ( 235943 ) on Thursday January 17, 2002 @11:26PM (#2860104)
    It pains me that on a site dedicated to open source that we should entirely ignore the history if ICC. Once there was the Internet Chess Server (ICS) which was free, source could be obtained and all. Then one of the people maintaining the server decided to make it propietary and charge for membership. Of course a splinter group decided they wanted a truly free server and that became the Free Internet Chess Server (www.freechess.org), however their lofty ideals came to an end when they saw others using their ideas and not giving back to the community (GPL does not stipulate you must distribute your software) and since then the version of the server software available to download as not been updated.

    Now I don't mean to rant about percieved evils, whats done is done, but for a site dedicated to open source I believe this must be mentioned.
  • i'm thinking that the best way to win this thing is to use a distributed algorithm running on a large number of machines somewhat like SETI. obvisouly with the time/bandwidth constraints you'd have to have some efficient way of sending out the move information to your network. maybe you could have a tree-like structure with super-nodes having high-bandwidth connections farming out information to subordinates. maybe the brute-force aproach wouldn't work so well against a 'smarter' single-machine solution, due to the exponential nature of the search domain, but i still think it would be cool to see such an entry in a competition like this.
  • ...why isn't IBM entering?

  • Beyond chess... (Score:2, Informative)

    by tangent3 ( 449222 )
    Besides computer chess, Contract Bridge has also held its own Computer Bridge tournaments [3web.ne.jp], of which the strongest has been Gibware [gibware.com]. Would be interesting to see more different type of AI tournaments.... Maybe a tournament between the smartest Quake 3 or Counter-strike bots...
  • Does this competition allow for human players? Is there any way for a human to "cheat" and pretend he is a computer, from the standpoint of the competition?

    I think it would be interesting to see the results of a surprise "black knight" human player thrown into the mix. (Or perhaps even more interestingly, a human/computer team.) We're at a unique point in computational history -- the best human players can still normally beat out the best computer algorithms, though just _barely_. A decent chess player could probably still take home the prize. In 20 years, however, even the best humans will no longer stand a chance against any reasonably serious chess program.

    Bob
    • Does this competition allow for human players? Is there any way for a human to "cheat" and pretend he is a computer, from the standpoint of the competition?

      Sure - if the human can squeeze inside a computer case and still have enough agility to type in the moves! (Best not to use the new iMac for this.)

      • Sure - if the human can squeeze inside a computer case

        No need for the human to be on-site. Anyone within 802.11 (or whatever) range of the stealthly-equipped box would suffice. Or are there wireless lan antenna inspections? ;-)

  • bad choice of words: (Score:3, Funny)

    by Xzzy ( 111297 ) <sether&tru7h,org> on Friday January 18, 2002 @12:04AM (#2860192) Homepage
    > watch the action.

    As interesting as chess is, "action" is a pretty piss-poor word to describe the game.
    Suspense, maybe. Action, not unless steven segal burst in and sprayed the place down with a machine gun.

  • Answers to all your questions... (Score:5, Informative)

    by migstradamus ( 472166 ) on Friday January 18, 2002 @12:26AM (#2860262) Homepage
    Hmm, where to start. My name is Mig Greengard and I run Garry Kasparov's website. I work with Shay Bushinsky, who is one of the programmers of Junior, the current world microcomputer chess champion. Just leaping at a chance to karma whore in my specialty. Let me cruise through the various questions and misperceptions I've seen so far.

    This is an online tournament held in the biggest online chessplaying site, the ICC. The games are "60 + 10" time control, meaning each computer gets 60 minutes on its clock and 10 seconds are added for each move. So games can last up to 2.5 hours, tops. If you think this is long, this is what we call "rapid chess." Classical games can last up to seven hours.

    Uniform hardware has pretty much been given up. They still distinguish between microcomputer and massive machines like those at NASA and Deep Blue, but everything is pretty much wide open these days. The programmers try to get the best hardware they can and usually know very well which platform is best for their program. (There WERE hardware chess accelerator cards, by the way. Back in the 80s when RISC and dedicated chess processors had better cost/chess performance ratios than CPUs. This hasn't been true since the Pentium, although various "Deep Blue on a chip" initiatives exist, including one by a member of the DB team.)

    Anyone with a Slashdot account automatically forfeits the ability to call anyone else a nerd.

    Move lists and online replay are both available on the site in the original post and at the ICC. Move lists are called "PGN" (portable (or player) game notation") which is an ASCII format used in databases but can be printed out and read easily if you know algabraic chess notation. Online java game viewer applets are quite common.

    Both Shannon and Turing spent quite a lot of time on chess algorithms. Shannon actually wrote the first chess program before a computer existed. He 'ran' the program using slips of paper and generated moves this way.

    The chess programming breakdown already posted is pretty good. The key concept these days is brute force speed versus knowledge. 20 years ago most programmers thought you needed to make the thing somehow think like a human because the brute force method was so slow. Intel and Moore won. The "fast searchers" now dominate thanks to the minimax algorithm. It just looks at one line after another and counts the beans to rapidly prune. Programs differ to an extreme degree in the amount of knowledge they apply. (HIARCS, for example, is one of the few "slow" programs at the top. It applies a lot of knowledge and looks at maybe 1% of the number of positions the fast programs like Fritz and Junior check.) A top level program, and the top 5-8 are roughly equal at a given time, will look at over one million positions per second. This sounds like a lot (well, it is a lot), but it only puts the program at a level equal to a top 100 level player at a classical time control. (At faster time controls, particularly blitz games of just minutes per side, computers are lethal. Humans just can't play mistake-free chess at that speed.) A program will look six-eight moves deep on the average, but extension will dive deeply into promising or unclear lines, sometimes up to 20 moves in a middlegame position.

    Those who think chess is solvable should speak only theoretically. The number of positions is one of those great "million times the number of stars times the grains of sand in the world" numbers. The current method of tree and pruning adds less than one full move of search depth when you double processing power (node count). So the diminishing returns are very much here. The game of go is even worse for comps. Top programs still can't touch the human masters. Back-solving chess using massive databases starting with just a few pieces has had a big impact on computer chess in the past decade. Invented by Ken Thompson (yes, that Ken Thompson), endgame tablebases can now play any combination of five pieces (and many combinations of six) perfectly. This leads to humorous situations of a computer making optically stupid moves to reach a tablebase position it knows for sure is a mathematical win. (Tablebases allow the once-fantastical announcements of things like "checkmate in 45 moves.")

    Most of the top commercial programs ARE playing in this event, but most people, particularly chess-ignorant Americans, only know Chessmaster. Fritz, Junior, HIARCS, and Shredder are all top commercial programs. In the chess world, Fritz is almost synonymous with chess program. Chessmaster has a very strong engine (called The King) by a well-known Dutch programmer. Various versions of The King have participated in these competitions and done just fine. Chessmaster has no reason to put its name brand on the line in these bloodbaths. An open tournament like this of only 11 rounds is not at all scientific, for one, but there mostly it's that since all these programs are so strong the power of the engine really isn't the most relevant thing when an amateur buys a chess program. Features like training materials, game databases, GUI, and graphics are much more relevant. Any decent program will kill you on even a low level unless you are an expert.

    There are dozens of places to play online, and most of them have computer players as well. KasparovChess has multiple versions of the champion program Junior running and a new one generates when someone starts a game with one so you can always give it a try. (It's a dumbed-down version or it wouldn't be much fun.) The sites with the most players are, inevitably, Yahoo! and MSN. Their software and community suck, of course. Location, location, location. Of the specialist sites, the ICC, chess.net, and KasparovChess.com (my site, as disclosed above) are the largest and best. They have downloadable client software and administrated communities as well as live events, lessons, etc.

    There have been many attempts at the holy grail of a massive online tournament. The biggest problem is simply cheating using these programs we're talking about. I could go on for a few dozen pages about methods and countermethods for catching cheats, but basically it's impossible at the end of the day. Don't get me started. KasparovChess hosted the first super-tournament to be played online, in the beginning of 2000. We had human observers with each Grandmaster, all over the world. We also hosted the largest online tournament so far, the world school chess championships. Thousands of kids from hundreds of schools around the world played. (Gotta trust the kids and teachers, right? Right? Actually there were several accusations made, but no decent cases.)

    Yes, the ICC used to be free, and that free internet chess server (FICS) is still alive and well, although it is rapidly losing market share. There was a long and bitter battle about that split and the use of the FICS kernel, which is the foundation of just about every chess playing site in the world.

    We cover top computer chess events, of which this one really isn't, but if you want to browse around some start here, at the last world championship. WMCCC [kasparovchess.com]

    It sounds funny, but in the computer championships they have to play face to face and the programmer himself has to make the moves. The worry, of course, is HUMAN cheating, that is, a strong human helping the computer in an online event. The wisdom of a human Grandmaster combined with the accuracy of a computer program would be a devastating combination. (They have competitions of this, with GMs using computers while they play. It's called 'advanced chess' and was introduced by Kasparov. It's interesting, but not always dramatically superior quality chess.)

    You can also stop by and play for free, either with an account and a rating or as a guest. We have a java applet if you don't want to download and install. We also have a lot of "learn to play" materials if you are one of the sad crowd that think it's just another board game.

    Saludos, Mig
    • Back-solving chess using massive databases starting with just a few pieces ... (Tablebases allow the once-fantastical announcements of things like "checkmate in 45 moves.")

      Chess has one flawed rule. 50 moves without a pawn move or a capture is declared a draw. These end-game tables have proven that there are winning positions that require more than 50 moves to force checkmate.

      IIRC, King vs King + Bishop + Knight is one such situation. If you play chess, try it out some time. It *IS* possible to force a mate, but it requires perfect acrobatics and a lot of moves to pull it off.

      -
    • Hello Michael,

      I have some comments. You write:

      "Both Shannon and Turing spent quite a lot of time on chess algorithms. Shannon actually wrote the first chess program before a computer existed. He 'ran' the program using slips of paper and generated moves this way."

      Actually it was Alan Turing, who wrote and operated the "paper machine" -- he played the role of a human CPU. A brief history of computer chess, including the game the poor man played, is available here. [207.158.205.122]

      "The chess programming breakdown already posted is pretty good. The key concept these days is brute force speed versus knowledge. 20 years ago most programmers thought you needed to make the thing somehow think like a human because the brute force method was so slow. Intel and Moore won. The "fast searchers" now dominate thanks to the minimax algorithm. It just looks at one line after another and counts the beans to rapidly prune. Programs differ to an extreme degree in the amount of knowledge they apply. (HIARCS, for example, is one of the few "slow" programs at the top. It applies a lot of knowledge and looks at maybe 1% of the number of positions the fast programs like Fritz and Junior check.)"

      It's more like 20%. On a 666 MHz Pentium this is the speed (in thousands of positions per second) of the current top programs:

      Fritz7: 300 kN/s
      Fritz6: 450 kN/s
      Fritz5: 520 kN/s
      Shredder: 160 kN/s
      Junior7: 250-435 kN/s
      Tiger: 135 kN/s
      Hiarcs7: 65 kN/s

      Note that Fritz7 has slowed down over the years. This is because it now has a lot of general chess knowledge built in. But you cannot measure knowledge by lack of speed. Fritz7 has more knowledge than Hiarcs 7, which is a number of years old. In fact it has more chess knowledge than any other top program available today.

      "Those who think chess is solvable should speak only theoretically. The number of positions is one of those great "million times the number of stars times the grains of sand in the world" numbers."

      Even the number of elementary particles in the universe (10^80) is a trivially small number, silly and insignificant compared to the number of possible games up to move 40 (10^112). But the number of unique positions that can occur on a chessboard is much smaller: 10^40 (just as the number of different words in a language is much smaller than the number of potential messages that can be generated from them). These can be theoretically solved using the Thompson back-solving method you mention. But storing the results would require the matter contained in millions of galaxies, so the game is unsolvable for all practical purposes. Just imagine what Greenpeace would say if they discovered we were dismantling millions of galaxies just to store chess!

      The last part of your posting seems to have been cut off. Pity.

      PS: For the others: I'm Frederic Friedel and part of the Fritz team.

  • Learning chess progs (Score:1, Insightful)

    by Anonymous Coward
    I was recently looking for a customizable chess program which learns. My idea was to have the computer play itself, over and over again, after each game changing the attributes of each of the players(E.G. attacker/defender, peice values etc.). It would result in a very smart program after a couple months of processor time dedicated to it(as a screensaver)..
    • There have been many experiments in learning programs and most of today's top programs have at least a limited form of this.

      Mostly it is simple database modification. Programs play the openings (the first 10-20 moves, usually) from massive databases of hundreds of thousands of games (human games) and variations. This is called the opening book. As bizarre as it might sound, chess programs don't usually 'think' at all in the first dozen moves or so; they simply play what's recommended in their book of human games. (Which sometimes leads to freaky events.)

      When a program with book learning loses a game, or even gets a very negative evaluation during it, it will downgrade the evaluation of that opening line in it's book, so it won't play it again. This is why you can't just repeat an entire winning game against program again and again. (This is very hard to do even if the program doesn't have book learning. The timing has to be perfect and they usually have some randomizing algorythm either in the book, the engine, or both.)

      Having an engine play endlessly against itself to learn and improve works to a certain extent. But remember that you run into a serious time factor. If those are two hour games, say, the quality of the moves will be lower than when the program plays a four-hour game in a tournament. So something it put down as good may turn out to be bad. And at longer time controls you'd need years to produce the quantity of checked variations to produce something practically useful.

      But programmers do do what you say to test and tweak new versions. If your new beta isn't beating your old gold you need to find out why. Remember, however, that this doesn't necessarily produce a program that is much stronger overall, but one that is stronger than the other one. And when you increase the scope by introducing other engines and versions it again becomes very time-consuming.

      This is why they use test suites of chess problems and just check to see which version scores best.

      Most of the top programmers work in conjunction with professional players (Grandmasters) to 'tune' their opening books. This is not only weeding out bad lines but creating a book that will help the program get positions that it plays well. Many openings played by Grandmasters are completely incomprehensible to programs, while the comps play certain types of positions better than any human ever could.

      Saludos, Mig
  • Wired had an article about computer & chess, computers & humans & chess, computers & humans & chess & cheating in the October 2001 issue:

    This time it's personal [wired.com]

    subheader: Humankind battles to reclaim the chess-playing championship of the world.
  • I've heard that the best openings to play against computers are the ones that are positional in nature instead of tactical. That is, computers are clumsy when it comes to general assessments of the board, whereas they are better at direct attack and defense. So human chess adepts generally avoid these tactical situations. Additionally, when chess adepts play computers, they tend to deviate from well-known or standard opening lines to get the computer "out of book" as soon as possible.

    I wonder, though, if there are any particular opening strategies when computers play each other, as opposed to human v computer? It seems to me that chess programs with good opening books would almost never fall into well-documented opening traps like the one that claimed Kasparov in his losing match [cs.vu.nl] against Deeper Blue. Do computers stick to the tried and true main lines when playing against each other, or would employing opening "novelties" work well?

    • My program is participating. What I do is to go through all the games it has played recently at ICC and try to determine which openings it seems to play sensibly. I have a two-level opening book. The "big" book has a load of high-rated GM games in it. The "preferred" book is the list of opening lines I want PostModernist to play.

      For a commercial opponent, I look for games my program has won against it (very few and far between) and try to get it to play the same lines.

      I don't do that for other amateur entrants, although my normal "preferred" book will often include recent novelties to see if PM can handle them.

  • IMPORTANT (Score:3, Informative)

    by baron000 ( 551941 ) on Friday January 18, 2002 @04:46AM (#2860967)
    IMPORTANT: Please read the whole post

    I'm sure many of you are aware of this thread [slashdot.org] already.

    If you are interested in helping against the moderators who have been "editing" the thread, please read this [slashdot.org].

    Please do not moderate this post down. It is good for the long term, but if you still feel like being someone who denies the horrible truth, give me your best shot. You will help hold all of Slashdot users back in the long term.

    For more info, read this piece [kuro5hin.org] from an apparently superior news site.
  • One of the biggest problems when watching someone play chess, is that you think you know what play should be made. When actually playing, this often translates to a mistake. i.e. you can't truly understand or appreciate the game unless you are playing, or getting a commentary from someone who knows whats going on. Now Kasparov himself has said that there isn't much point in strong human players playing strong machine players, because the machines will win (they are better). So ultimately, when watching this tournament, no one will really understand any of the moves!

Slashdot Top Deals

You can not win the game, and you are not allowed to stop playing. -- The Third Law Of Thermodynamics

Close