Follow Slashdot stories on Twitter

 



Forgot your password?
typodupeerror
Technology

Kramnik Ties Fritz; Machines Not Yet Our Masters 241

Posted by michael
from the gnuchess-has-got-my-number-though dept.
Maltov writes "World Chess Champion V. Kramnik ties his match against the software Fritz. Details here. You can also check out a picture gallery and a short history of computer chess."
This discussion has been archived. No new comments can be posted.

Kramnik Ties Fritz; Machines Not Yet Our Masters

Comments Filter:
  • by strredwolf (532) on Saturday October 19, 2002 @10:44PM (#4488139) Homepage Journal
    or are we going to start getting The Onion [theonion.com] inspired subject titles?

  • by TheGreenGoogler (618700) on Saturday October 19, 2002 @10:48PM (#4488160) Journal
    This story appeared 8 hours ago here... [globeandmail.com]
  • Dateline (Score:4, Funny)

    by Anonymous Coward on Saturday October 19, 2002 @10:50PM (#4488168)
    PARIS, FRANCE. Upon hearing news that "Kramnik Ties Fritz; Machines Not Yet Our Masters" France surrendered all cash assets and welcomed their new overlords. France was quoted as saying, "please be gentle"
  • by Tester (591) <olivier.crete@[ ]ete.ca ['ocr' in gap]> on Saturday October 19, 2002 @10:50PM (#4488169) Homepage
    If two chess players play perfectly, then the game will always result in a tie. That's one of the big problems with chess as a man-vs-machine benchmark... If both become too good, they will tie all the time.. We might have to move to another game that might be much harder from a computational point of view. (I've been told that the Japanese (or is it Chinese) game of Go is one such game)...
    • by Kircle (564389) on Saturday October 19, 2002 @10:57PM (#4488197)
      If two chess players play perfectly, then the game will always result in a tie

      Here's an interesting quote from MSNBC:

      Friedel pointed to two weaknesses in Kramnik's play characteristic of humans. "Once in 200 moves a human will make a blunder, and that's all Fritz needs. And [Kramnik] was seduced by beauty." He added that Kramnik "understands 100 times more about chess than any computer, but tactically Fritz is a monster."
    • The combinatorics behind chess, ie the number of distinct games is so high it would make a 128 bit UUID blush... and UUIDs are unique in time and space...

      I wouldn't hold my breath for the "guaranteed tie" level of gameplay to come any time soon...
    • by wwwojtek (246402) on Saturday October 19, 2002 @11:05PM (#4488221)
      (I've been told that the Japanese (or is it Chinese) game of Go is one such game)

      If you ask a Korean, you'll be told that it's Korean (he might call it "baduk" though). Anyway, the point is that we are still years from seeing a machine that can beat a human with a few years of experience (not to mention a professional). The game has much more combinations than chess. The numbers I remember is something of the order of 10^720 distinct games that you can play in go vs. 10^120 in chess - they may be off by a bit but that's roughly the order of magnitude. On top of it, it is not that easy to prune unreasonable moves - in chess you can in most cases easily go down to a few moves to consider while in go it is easily 20 or more in the opening game. You cannot just rely on the brute force but rather on hard to formalize concepts of "shape" and "influence". That's what also makes the game fun.

      • Go is an interesting way to spend time - you can relax your anylitical mind and just let the tactical beauty of the game influance your next move. It's also not as comptetive as Chess - I remember chess wins and losses, but my games of Go are catagoriesed as either fun or bland.

        Chess, to me, is a General mashaling troops to battle. Go is like a child playing in the sandbox - having fun, exploring, trying new ideas, making castles.

      • by yeOldeSkeptic (547343) on Sunday October 20, 2002 @12:31AM (#4488523)
        I've been told that the Japanese (or is it Chinese) game of Go is one such game.

        I keep hearing about how go is much more difficult for a computer to play than is chess. The number of possible moves in go has nothing to do with its difficulty. Computer scientists have been trying to teach computers to play chess for at least half a century and it is only now that computers have become powerful enough and for the theory to advance enough that computers can hold the world chess champion to a tie. Go has not been analyzed and picked apart enough for us to say that it us much more difficult than chess.

        Go has the advantage that you start with a bare board. In chess, the game always starts the same way. A computer that has in its memory a century's worth of master games should be at a distinct advantage. The fact that chess engines with million game databases can only manage a tie against a good human champion means computers have barely scratched the surface of chess. When a computer can beat Kasparov at fischer-random chess, I will concede.

        Perhaps with the belief among computer chess researchers that chess has been solved will Go soon undergo the same nitpicking that chess has. My bet is that it will prove to be even easier than chess.

        Here's why I think so.

        • Go pieces, once placed on the board, cannot move anymore. Chess pieces can still move from one place to the other. This means that as more and more Go pieces are placed on the board, there are less and less positions the computer has to consider.
        • Go requires the ability to look at patterns rather than combinations. Sure, the Go board is larger and the possible positions are greater but then there are only three possible ``cells'' to consider: the first player's stone, the second player's stone and an empty cell. That should be easier to manage than the job we are asking computer's nowadays to do: recognize people from their faces. I believe computers can match fingerprints easily today. Go should be a walk in the park.
        • by Moridineas (213502) on Sunday October 20, 2002 @12:46AM (#4488560) Journal
          Very well said. To add a couple things:

          On the average chess has a branching factor of about 40 (or 35--reports vary). This means that on average for each players turn there are that many possible moves. So to build a game tree, that's how fast the tree will grow.

          Go on the other hand as you state, starts with an empty board, and so even if you're playing on a child sized board of 9x9 (standard sized boards are a good bit bigger than this, I forget the size, at least 13x13 i believe) you have 81 possible moves at first. And you do make a good point that this branching factor drops dramatically as the game advances.

          there's nothing inherent to Go that makes it a better game, "harder", or anything of the sort--no magic reason for why computer AI's suck. It's simply a ton less energy being put into Go (when was the last time you heard of a MASSIVE super computer being built for Go?) and the massive branching factor.

          My personal feeling is that within 20 years Go AI with be at a similiar level as we are at with chess today--just my own guess.
          • by crulx (3223) on Sunday October 20, 2002 @01:57AM (#4488748)
            While I personally would love harder Go opponents to play against on the computer, I don't feel that Go will get anywhere near the level of Chess for a long time. Jay Burmeister wrote an excellent paper on the topic of computational Go [uq.edu.au] and I'll use some of his points to show why many Computer Scientists feel that Go will take significantly more work than Chess to acheieve a grandmaster level of play.

            Features | Chess | Go
            # moves in a game | ~80 | ~300
            Branching factor | ~35 | ~200
            Horizion effect | Applies basically at Grandmaster level | Applies at beginner level
            End of game | Strictly defined checkmate | Loosely defined territory conquest(see seki and ko fights)
            Evaluation of board position | Correlates to number and quality of pieces on board | Poor correlation with either pieces or territory

            A quote from his paper may also help,

            "3.3 Why Go Cannot be Programmed Like Chess

            Chess programs typically use a heuristic search and evaluation technique. Search trees of board positions are generated to a fixed depth and are heuristically pruned according to an evaluation of the merit of the board positions. This approach works well in Chess because the board size is sufficiently small and the nature of Chess is more tactical than strategic.

            Evaluation of a board position in Go presents problems not encountered in Chess. Go is a much more strategic game in comparison to Chess. Unlike Chess, Go does not focus around the capture of a single piece. Positional advantages are slowly built up in achieving the long term goal of acquiring more territory than the opponent. There are many direct and indirect ways to achieve this goal such as making territory, building influence, attacking weak enemy groups, securing friendly groups, destroying enemy territory etc. Due to the large size of the board, a Go game is comprised of many small local skirmishes. If a game of Chess were described as a battle, a game of Go could be described as a war. Many good tactical moves at the local level must all compete for selection in the context of strategic global considerations. Thus a player must balance resources to achieve local goals at many locations whilst trying to pursue an overall global objective."

            Read more about computer Go at Mike's Computer Go. [demon.co.uk] Sit down and try a game of Go for yourself and you will see why computers won't get to the same level anytime soon.

            crulx

            • by yeOldeSkeptic (547343) on Sunday October 20, 2002 @05:15AM (#4489124)
              Jay Burmeister wrote an excellent paper on the topic of computational Go [uq.edu.au] and I'll use some of his points to show why many Computer Scientists feel that Go will take significantly more work than Chess to acheieve a grandmaster level of play.

              The paper cited above is interesting as it shows what some computer scientists think about the difficulty of a computer playing ever playing go. However, to put it in proper perspective it should also be remembered that before the 1980's computer scientists and chess players are also of the belief that computers cannot be made to play chess. What a difference two decades make!

              However, let me point out the following two quotes from Burmeister and my personal opinion on these.

              Compared to the Chess programming field, the Go programming field is not well developed. A strong commitment to research on programming Chess in the 1960's and 70's has not been replicated in the Go field.

              8. For all the reasons discussed above, programming approaches to chess are amenable to tree searches, with good evaluation criteria. Such approaches have not succeeded in Go, because the branching factor is too large for brute force search techniques, and pruning is not a viable option without good evaluation measures.

              These two quotes show the state of Go programming today:

              • research in go lags behind that of chess.
              • what works in chess will not necessarily work in go.

              Point two is what most people who have an opinion on the computer chess vs computer go debate fail to consider. The fact that computers play chess by brute force searching of tries does not mean that that approach is, ergo, the only possible approach to computer go.

              In fact a bit of computer chess history should dispel that notion. When researchers first tried to tackle the problem of computer chess, it was rather obvious that a brute force approach is not the ideal way to do it. The number of possible positions in chess is so huge that it is not possible to solve chess using the technology available at that time. Instead they went for the heuristic approach.

              In this approach researches looked for a function Eval(p) such that given a position p, Eval(p) will evaluate whether one side is ahead or not. If Eval(p) is found, so they think, then it is possible to use a greedy algorithm to chess. The computer simply picks that position p_n where Eval(p_n) is a maximum. No need for brute force! Unfortunately Eval(p) proved intractable because of one aspect of chess: sacrifice. In a chess sacrifice, Eval(p) is screwed up by the temporary giving up of an advantage (material, or position) in order to gain a future advantage. It turned out that there is no way to program a chess computer without look-ahead. And that is essentially how all computer's today play chess, by brute force lookahead coupled with other heuristics.

              The state of computer go is not yet that advanced for either me or anyone to say for certainty that there is no Eval(p) for go. But if, as I suspect (let's just say it's a gambler's gut-feeling reinforced, in fact, by a reading of Burmeister plus the fact that go stones cannot move and thus their present fixed position must contribute to Eval(p)) there is in fact an Eval(p) for go, then go will prove to be easier to program than chess.

              All the above is my opinion only. There goes my karma.

              • Plenty of stones die and are removed from the board, plenty of stones are sacrificed during a game... Won't this screw your mythical Eval(p)?

                By the way, the article you refer to is six-years old; perhaps things have slightly changed in the computer Go world since then? E.g., Gnu Go has become much better this past year, and so have others, probably.

                Play some Go seriously, you'll understand better why computers still have a long way to Go...
                • Plenty of stones die and are removed from the board, plenty of stones are sacrificed during a game... Won't this screw your mythical Eval(p)?

                  Only through programmer error. Eval(p) by definition must 'understand' the game it is being applied to; thus, anything within the rules will not 'screw' it, by definition. The Eval(p) that is screwed by legal moves is not the true Eval(p).

                  Just as in chess; the computers are not surprised when pieces are removed from the board. But if in the middle of the endgame of one of Kramnik's matches, we suddenly plunked a queen for Kramnik right in the middle of the board, we'd expect Fritz to handle that poorly; he wasn't ready for the rules to be broken.

                  To be fair, neither was Kramnik, unless we told him we were going to do this. Both players would still have to deal with this violation, and they'd handle it about the same. In fact, the computer might have the advantage since it is much easier for the computer to discard its preconceived notions about the game at that point, what with it not having any.

              • Just my gambler's gut-feeling here, but I think finding an Eval(p) function that works for Go is gonna be about as hard as finding the question for 42.
        • Not correct (Score:3, Interesting)

          by ucblockhead (63650)
          The number of possible moves in go has nothing to do with its difficulty.
          It has everything to do with difficulty. Nearly all game playing programs use some variation on the min-max algorithm, which creates a tree of possible moves for some number of moves ahead. More possibilities per move means a larger tree, means more computation per each move of lookahead.
        • "Go pieces, once placed on the board, cannot move anymore. Chess pieces can still move from one place to the other. This means that as more and more Go pieces are placed on the board, there are less and less positions the computer has to consider."

          "Go requires the ability to look at patterns rather than combinations. Sure, the Go board is larger and the possible positions are greater but then there are only three possible ``cells'' to consider: the first player's stone, the second player's stone and an empty cell. That should be easier to manage than the job we are asking computer's nowadays to do: recognize people from their faces. I believe computers can match fingerprints easily today. Go should be a walk in the park."

          Ok, I think you've got the right theory, however you missed a few items in your assesment of Go.

          • Randomness:
          In the begining two-thirds of a game of Go most of the stone placements are "random". Yes some players attempt to mark out a territory but that can be self-defeating, reason being: when all the stones are played the game is over and the player with the largest total areas under his control wins. Sure, you're right that as the game progresses randomness drops. However, how does a computer deal with a human player who decides to give up on an area that is contested? And how will a computer decide when a contested area needs to be given up on?

          • Patterns:
          In Go there are only a few "true" patterns to worry about. The Line (easy to deal with if you know the rules). The Box (a way to control an area). And The Spiral, when a contested area "spirals" out of control. The Go game becomes a miniture Mandlebrodt set that can loop off into infinity, if we had infinite stones to play with on an infinitely large 2D surface. Past that, all "patterns" should be treated as forms with a tactical value. One method of playing Go is to work your opponent into a corner that he cannot leave, a pattern and strategy that he cannot give up or he loses (or thinks he'll lose), which in the end will make him lose.

          • The Stones:
          The player actually has more than 3 states to consider with his game peices. For each of his solitary pieces there are 4 possible ways that it can be surrounded and taken. If there are pieces in contiguous strings or blocks the player must see how many sides are open to attack from an enemy. And if he happens to have a hole in the middle of his string (shape) or block, the player has to consider if that hole is large enough to allow an enemy to capture his pieces.

          IMHO Go will be harder to program than chess. Even considering the exponentially decreasing randomness there is still that first random placement, and as we all know... there is no true random-number generator program yet devised.

          • by legLess (127550) on Sunday October 20, 2002 @02:23AM (#4488803) Journal
            Blockquothe the poster:
            In the begining two-thirds of a game of Go most of the stone placements are "random". Yes some players attempt to mark out a territory but that can be self-defeating,
            100% pure bullshit. Strong players make no random moves, period, especially in the opening. Professional games are sometimes decided by 1/2 stone (black moves first, and in an even game - i.e. no handicap - the territory advantage of this move - 5.5 points - is added to white's score at the end of the game; this also prevents ties); a botched or "random" opening move is suicide.
            In Go there are only a few "true" patterns to worry about.
            Incorrect. If this were even remotely true the game would be trivial.
            The Line (easy to deal with if you know the rules). The Box (a way to control an area).
            Lines of stones are tremendously strong, if inflexible. Boxes are a very inefficient way to surround territory, open to many attacks, and very limited in possibilities.
            And The Spiral, when a contested area "spirals" out of control. The Go game becomes a miniture Mandlebrodt set that can loop off into infinity,
            Is this a concept of your own invention? I've yet to encounter it myself.
            One method of playing Go is to work your opponent into a corner that he cannot leave
            Yeah, this is the time-honored "shooting yourself in the fucking forehead" technique. The corners are by far the easiest territory to surround and control, because you don't need to defend at the edges. If one player in a more-or-less evenly-contested go game captures all 4 corners his victory is assured.

            You need to learn more about the game, I think, before you try to explain it to others.
        • Go pieces, once placed on the board, cannot move anymore. Chess pieces can still move from one place to the other. This means that as more and more Go pieces are placed on the board, there are less and less positions the computer has to consider

          Uhm...so after 100 moves per side, Go is down to ~160 possible moves per ply...still way higher than Chess.

        • by legLess (127550) on Sunday October 20, 2002 @02:06AM (#4488761) Journal
          Blockquothe the poster:
          My bet is that [go] will prove to be even easier than chess.
          Yowza. I believe you're sincere, but you should do much more research before spouting off. You're flat-out wrong.
          Go pieces, once placed on the board, cannot move anymore. Chess pieces can still move from one place to the other. This means that as more and more Go pieces are placed on the board, there are less and less positions the computer has to consider.
          Chess has at most 40 legal moves possible for the first move; go has 361. The average chess game has 40 moves; the average go game has 6 to 8 times that.

          So yes, after each move there are fewer go positions, but after 80 stones have been placed (the average number of chess moves), there are still 281 moves possible. You have to play more than 200 moves into a go game before you have as few move possibilities as you do for your first move in chess.
          Go requires the ability to look at patterns rather than combinations.
          If by "combinations" you mean "tacics," you're incorrect. Tactics are crucial in go, and it's only by a solid understanding of tactics that strategic thinking is possible. It's true that the rules of chess tactics are more complex than go, but it's precisely this lack of rules and formulae that make go so hard for computers.

          Go's not nearly as easily quantifiable. You can tell a chess computer that the king is worth 10,000,000 pawns, the queen 9, bishops and knights 3 or 3.5. In go, however, the only thing giving value to a stone is its position on the board and its relation to other stones ... sometimes all the other stones.
          Sure, the Go board is larger and the possible positions are greater but then there are only three possible ``cells'' to consider: the first player's stone, the second player's stone and an empty cell. That should be easier to manage than the job we are asking computer's nowadays to do: recognize people from their faces. I believe computers can match fingerprints easily today. Go should be a walk in the park.
          Um ... this is a sad series of non-sequiturs. Computers are stunningly bad at facial recognition, even in best-case scenarios. Humans, on the other hand, can recognize someone they haven't seen for 20 years based on a casual glance. Being social animals, there's literally nothing humans do better than pattern recognition, and go is all about pattern recognition.

          I think I realize what you're trying to say, though - that there are only three states for one position on a go board, while there are many more for a chess board. This is immaterial to the game. The problem computer programmers have with go is that there's no algorithm that will reliably determine if a group of stones is alive or dead without brute-forcing the entire game. Many groups can be correctly evaluated, and computers are good at scoring finished games, but computers will happily slog ahead (and lose horribly) in games that professionals would resign in disgust.

          Read a few of these pages and then reconsider your viewpoint: Note that I'm not saying go is better than chess. I think such arguments are foolish [slashdot.org]. But, to quote myself, from a computer's perspective go makes chess look like tic-tac-toe.
        • Westerner alert! (Score:5, Interesting)

          by thefirelane (586885) on Sunday October 20, 2002 @02:17AM (#4488789)
          Hello, sorry, but... Go has not been analyzed and picked apart enough for us to say that it us much more difficult than chess.

          Perhaps with the belief among computer chess researchers that chess has been solved will Go soon undergo the same nitpicking that chess has

          This game is much more popular than chess in China, Japan, and Korea. Somehow, you seem to assume that these regions are all completely deviod of any programming, AI, or mathematical talent.

          These people are obviously just sitting around waiting for us Westerners to solve chess so we can move onto their little problem.

          As for your 'points'... they cry of a lack of deep understanding of both Go, and AI
          1. Go pieces can be removed from the board, by capturing. Thus opening up more combinations

          2. Even if it weren't possible, and a stone was plunked down each time, you'd still have (19x19)! possible moves (a lot, as stated earlier)

          3. When chess pieces are removed from the board, it collapses the search tree. On a Go board, it expands it.

          4. There are 4 'cells' Remember, in a Ko battle, a space can be empty, but unplayable.

          5. The whole cells argument is pretty nonsensical anyway? You are basically discussing bit-depth... in which case, would a black and white face be easier for a computer to recognize than a grayscale, how about color?

          6. Facial recognition really has nothing to do with Go in a practical sense. Facial recognition is categorization based on large differences. In go, you have to select the best move based on extremely small differences in extremely similiar layouts.

          7. As far as the "million game database" This just will not work, as playing against a human, they'll just do a profitable, but nonsensical move. It is the same thing that happens when studying Joseki. People will know the Joseki, but without an understanding of the principles behind it, it will be useless to them as they will not be able to respond to non-standard moves (GNU Go has a Joseki database I believe).


          ---Lane
        • The fundamental difference between computer Go and computer chess is that Go positions cannot be evaluated statically. The chess approach fails for go.

          The core of the success of computer chess is a game tree search (with optimizations such as alpha-beta cutoffs and hash tables of previously encountered positions). The game tree can only be searched to a certain depth where it is cut off. At the cut off point, static evaluation is applied. In chess you count material and mobility.
          Counting the stones in Go reveals nothing and they don't move. To evaluate a Go position you need to think in terms of influence and stability. Nobody knows how to compute a number between -10 an +10 for a Go position like Fritz does for chess. Without a good evaluation function, search cannot function.

          Even on a 9*9 board, where the game tree is smaller than for chess, go programs perform dismally.

          Chess programs have become as strong as they are mainly because computers got as fast they are. A second-year computer science student can whip up a chess program in half a year that will, given a powerful machine, beat 95% of all chess players.

          Fritz has huge opening and end game libraries. But take them away and Fritz will still play at grandmaster level. But without the search algorithm , Fritz is nothing.

          Do not think that computer Go is weak, because we haven't tried enough. Go is very popular in China and Korea and it is a cornerstone of japanese culture. If someone wrote a strong go program, there would be a huge market for it, but so far all programs are too weak to be of interest to anyone but a beginner.

          Human strength in chess as in Go is based on pattern recognition, but pattern recognition is not promising for computer Go. Former chess world champion Botvinnik tried to make it work for chess. He spent half a lifetime trying to make it work but in the end it was just failure.

          Computers are very sad at pattern recognitions. OK, so they can do fingerprints, but so can any idiot and it took an enormous amount of research to even get there. Same for speech and image recognition. Computers have not reached the abilities of a four-year old, so what are their chances at beating Go professionals?
      • If you ask a Korean, you'll be told that it's Korean

        Well, technically... Japan is Korean.

        Japan was settled by peoples who slowly moved up onto the islands via migration from Korea.

        • According to the Chinese historians, Chin Shih Huang-Ti sent an expedition to seek out legendary
          eastern islands shortly before the birth of Christ.
          They never came back, and hence Japan was populated. I suppose that differential genetic analysis could resolve the conflicting accounts, if you accepted
          the results, but given the absymmal record of
          phylogenetic morphology, I can't consider any such
          results to be clearly determinative.

          This is tangential, not offtopic:P

        • I'm not going to say anything about the direction of "up" that's just to pedantic.

          But the history of Japan is not that simple. There are 'native' Japanese that actually look kind of European, though probably not any closer to Europeans genetically since that bog man from Washington state is thought by some to look similar to the native Japanese. The general populace is probably mostly of Chinese/Korean/native mixed ancenstry, and then there are people that are from relatively recent Chinese, Korean, and Brazilian extraction. Recent enough that they are descriminated against. Of course, there are even more recent American, European, Pacific Islanders; most recent immigrants don't have sufferage even if born in Japan, though there tenative moves to fix this on occasion, the "ethnic Japanese" constititute 99% of the population, though what this means outside the main 4 islands... Japan has a reputation for being very homogenous and intolerant of outsiders, but then again America only abandoned de jure apartite in most of our lifetimes, and has yet to actually get de facto integration in many places.

          But then how seperate are China and Korea, people move, people mix, sometimes with the borders, sometimes not. Not that this clarifies the GO question... Unless you just say it was probably invented by humans, no one's gonna refute that.
    • by targo (409974) <<moc.liamtoh> <ta> <t_ograt>> on Saturday October 19, 2002 @11:05PM (#4488223) Homepage
      The problem with this is that defining "perfect play" is next to impossible in chess. Different players have very different playing styles, and if player A is strong against player B, and B is strong against C then it doesn't necessarily mean that A could defeat C.
      Computers are strong in tactical play, humans in positional; people have argued for ages, which is better, so far both styles have their proponents among grandmasters.
      And we can't really find an answer to this question unless we compute the entire game tree of chess, but this is impossible, even if you used all the atoms in the Universe to track the nodes in your tree.

      Btw, the concern that chess as a game will exhaust itself and in the future grandmasters will always tie, has been expressed many times in the past. So far they have all been proven wrong, usually when some prodigy (Tal, Fischer, Kasparov) has come forward and brought new innovations with him. Computer chess is in a similar position, bringing many new ideas to the chess world, and countless new chess theories have been created by analyzing how computers play.
      So I am quite optimistic about the future of chess, there is certainly no end in sight for now.
      • It's easy to define perfect play in chess, just not easy to achieve it. All you need is the ideal minimax sequence of moves for every move the opponent can make.

        But, I agree, the end is definitely not in sight.
      • But this is impossible, even if you used all the atoms in the Universe to track the nodes in your tree.

        This point comes up a lot, and is true but misleading. To solve chess using a minimax tree, the storage space required is proportional to the length of the longest game (which is bounded above by 4050 due to the 50-move rule), and which is likely to be on the order of log of the number of games. It is the *time* that is proportional to the number of games. Still not in sight, but not impossible.

    • by Nigel Stepp (446) on Saturday October 19, 2002 @11:09PM (#4488237) Homepage
      I believe that this is just a conjecture. That is, no one knows whether or not is possible to force a draw, or whether it is possible to force a win. To really know this answer, one would have to know the game tree (or some equivalent).

      Go does have a much bigger game tree, due to its much large branching factor. It was Chinese by origin.

    • If two chess players play perfectly, then the game will always result in a tie


      Correction: it is believed that perfect play leads to a draw. It has not been proven.

    • Actually, it's an open question. Nobody knows if Chess is a draw with best play on the part of both players, a win for White or a win for Black (! White makes the first weakness).
    • If two chess players play perfectly, then the game will always result in a tie.
      Not true, or rather, not proven yet. If both players started out equally, it'd be true, but since one player moves first, it isn't necessarily true. Once the computational power is there to solve chess we will know whether a perfectly played game will always result in a tie, a white win or a black win.
    • The game of chess in fundamentally undecided, and the outcome of perfect play can be both win for white, win for black and a tie.

      White has 20 choices of opening moves. If *one* of those moves with perfect play will lead to win for white, white has won.

      Upon those 20 white moves, no matter which one, the position will be different from the starting position white had, so even if white could not force a win on the opening movie, there's a chance that black can. If black has, for each of those 20 opening moves, a response that will force a black win, he has won.

      If neither is the case, the game is a draw with perfect play.

      There's no way of deterministicly deciding that short of calculating the entire game tree, which is far too great even for chess.

      Of course we can make some pseduoscientific "guesswork". If we make this into a game of statistics, let's *assume* that all moves are "equal" (no big first or second-mover advantage, no clear advantage of any specific moves, not all bad assumption) and will win with a probability of 1% (yes, that one is pulled out of my ass).

      White chances of winning are (1-.99^20) = 0.182
      Blacks chances of winning are (1-0.182)(0.182^20) = 1.3 * 10^-15
      Chance of draw 1-0.182-1.3*10-15 = 0.818

      You'll see that the chances of black winning are astronomically small compared to that of white, no matter for what win probability one chooses. But since the moves in a chess game are *not* exactly identical, it's still undecided. I'd give good odds to whoever is willing to bet that black would win, though.

      Kjella
  • by skydude_20 (307538) on Saturday October 19, 2002 @10:50PM (#4488172) Journal
    Is it just me, or did someone forget the current score: Machines (1-0-1), Humans (0-1-1).
  • by phorm (591458) on Saturday October 19, 2002 @10:55PM (#4488189) Journal
    At least in the chess arena, that is. And chances are the Fritz can get smarter after a few new upgrades whereas Kramnik gets slower over the years.

    Machines won't be nearly our equals in life for some time though, as the fixed-rules of a chess tournament bears little resemblance to the forsight, logic, and sometimes blind chance of human life.

    Too many people seem to think of Terminator2-esque type scenarios with intelligent machines when talking about this, but Chess is just a little sandbox in a big beach.
    • Machines aren't ruled by emotion, which gives them a distinct advantage over humans.

      Think, it means they don't get scared, intimidated. They never make a mistake due to hasty judgement, or the pressure of the situation.

      And to counter the Terminator 2 arguments, machines would not get jealous at being sub-serviant, they would not care about being controlled by humans... Unless some human programmed them to act like that.

      But how logical would it be for someone to do that? Ummm... err... humans not logical, erm... doh
    • Machines won't EVER EVER be our equal's in life. Even the simplest of organisms (E. coli, for example) are trillions of times more complex and sophisticated than our most advanced computers.

      You seem to imply that eventually computers will equal human being's in life. Trying to say that a computer could ever equal a human being is silly and ignorant. The human brain is infinitely more complex than any computer could ever be; a single neuron is more complex than a computer could ever be.

      You simply cannot do in the time that humans have, what took evolution over a billion years to accomplish.
      • Machines won't EVER EVER be our equal's in life. Even the simplest of organisms (E. coli, for example) are trillions of times more complex and sophisticated than our most advanced computers.

        An E. coli bacterium doesn't even have trillions of working parts, or even billions or millions. Junk DNA doesn't count here.

        As opposed to our most powerful computers, where any of trillions (this time literally) of transistors (which in and of themselves aren't the simplest devices on Earth) can potentially affect any other transistor in the system a few hundred steps down the road, going at a billion steps a second.

        Just because we can't replicate all of the steps to reconstruct a bacterium doesn't mean we haven't made anything more complex than it.
        • by dh003i (203189) <(moc.liamg) (ta) (i300hd)> on Sunday October 20, 2002 @12:13AM (#4488476) Homepage Journal
          Have you ever taken a college biology course?

          Sure, a bacteria doesn't have trillions of individual parts. Neither do human beings; there are only 30,000 - 100,000 genes.

          But E. coli are trillions of times more complex than our most complex computers, and human beings are trillions of times more complicated than E. coli.

          E. coli may not have many different "working parts" in your layman terms, but the way in which those finite parts interact and are regulated and modulated are infinitely complex; far more complex than any computer system we have -- more complex than the entire internet, basically a set of interconnected computer systems.

          Take a look at the 3D structure of one protein. It's pretty complicated; so complicated, in fact, that the most powerful computers we have can't accurately predict how a protein sequence will fold. That's just one protein. Proteins synthesis is regulated by both transcription (DNA -> RNA) and translation (RNA -> protein), as well as by post-translational factors, such as other proteins which bind to and modify the activity of your protein. A kinase is a protein which phosphorylates other proteins; depending on which cyclin a cyclin-dependant kinase is bound to, it may phosphorylate different proteins.

          Sure, the number of parts of even the most complicated living systems (human beings) are very finite (100,000 genes max). But they way in which they interact and are regulated is infinitely complex.

          Computers may be great, but they're simple -- very simple. Even a layman can, with a little bit of education, understand exactly how a computer works. But the most intelligent biologist alive isn't anywhere near understanding how a single cell works in its entirity.

          Before you go about demeaning any form of life to being simpler than a computer, perhaps you should try to gain some understanding of the complexity of even the most "simple" life.

          • Before you go about demeaning any form of life to being simpler than a computer, perhaps you should try to gain some understanding of the complexity of even the most "simple" life.


            I'm certainly not going to get into a long drawn out discussion over this, however. Your claims are groundless. Life boils down to a process, regardless of the complication of the process it CAN be reproduced. "Never" is a strong word, and you should be more careful how you throw it around. The fact that we don't currently know how a single cell works in it's entirety, that is no argument for the stance that we will never know. More importantly, it's not even necessary for an artificial intelligence to function in the same manner as human intelligence, or anumal intelligence for that matter. You're confusing function with form. It is entirely possible that an idea, could come about that allows a computer to think in a radically different way, process wise, than a living creature, but it could still be said to think.


            It simply does not matter how a machine performs it's job. Whether it's a wetware computer, or a silicon brain, the determining factor is behavioral in nature. Meaning that only through analysis of something's behavior can we determine whether or not it has intelligence, there is no other way. Arguments that focus on the material makeup up the subject being examined, not only miss the point entirely, they are an exercise in futility.

            • If humans had all of eternity to figure out how a cell works in its entirity, we might be able to do it. But we don't. At the best, we have about 5 billion years until the sun nova's. A more realistic conception is that we have about a million years or so -- until we go extinct.

              That's not enough time to unravel the complexity of life in its entirity.

              I'm not confusing function with form. I'm simply saying that human being's aren't going to be able to reproduce in a few years, decades, centuries, milleniums, etc, what took evolution approximately a billion years to produce. We aren't even close to understanding how our own minds work; how can we possibly make a machine which can truely think if we don't even know how we think? That's just thinking. There are other things as well.
          • Simpler explanation: E. coli's complexity comes from it's "software", not the hardware. Basically, you can have a computer with 10^10000000^400 transistors. But the software it runs is what makes it complex or simple.

  • First Chess machine (Score:5, Interesting)

    by acehole (174372) on Saturday October 19, 2002 @10:56PM (#4488191) Homepage
    Slightly diverting from the topic, the first Chess Machine (not computer) was a box that was carted around the country (england), didnt actually have any mechanical parts, just a little midget inside the box moving the peices.

    Mainly it was used by con artists selling the machine to the rich (without the midget inside).

    Thankfully things have come a little way since then...
  • Too bad... (Score:4, Interesting)

    by 403Forbidden (610018) on Saturday October 19, 2002 @10:56PM (#4488192)
    Too bad Deep Blue is in pieces now, I would have really liked to see the two go against eachother.
    • Fritz beat Deep Blue awhile ago. You can buy Deep Fritz software, which is just a multiprocessor version of Fritz, and supports up to 32 processors. A second processor improves performance by about 86%.

      -Adam
      • Re:Too bad... (Score:4, Informative)

        by stienman (51024) <adavis AT ubasics DOT com> on Saturday October 19, 2002 @11:39PM (#4488358) Homepage Journal
        I should qualify this. On the Fritz software page [chessbase.com] you'll see this statement under FRITZ 6 The talking chess program

        Fritz is very easy to use but very difficult to beat. Since 1993 the program has been the enfant terrible of the chess scene. In Munich it won the strongest blitz tournament of all times, together with world champion Garry Kasparov; in 1995 it won the world computer chess championship in Hong Kong, ahead of Deep Blue; in July 1999 it won the super-strong Frankfurt Masters and thus qualified to play against the world champion next year. Fritz is used by all top players in the world and is the most popular chess program amongst tournament players.

        Winning the world computer chess championship ahead of deep blue is not the same as playing against deep blue. It could easily be said that Fritz found a particular weakness in another program which found a particular weakness in Deep Blue. That Fritz might find that same weakness or another one against deep blue itself is unknown unless they did play against each other. But this is how most sporting games are held in modern times. Computers, however, are less susceptable to time, weather, and other variations humans are so subject to that make us play 'a bad game'.

        -Adam
        • Re:Too bad... (Score:2, Informative)

          by RoryBBellows (472821)
          It did not beat Deep Blue. It beat Deep Thought.
          An older slower machine. This match is a crock because the computer used is substantially slower and weaker than the one that beat Kasparov. They're jerking us around. Deep Blue type machines are now as strong as the strongest players. They're just milking this for all it's worth. Hyping it into something it can't be. The best chess playing machine has been disassembled. Do this for info about deep blue:

          Go to Google groups, restrict your search to the *chess* newsgroups and type in "crazybird" for the search term. The 2nd and 3rd hits are interviews with the creator of deep blue. It's good stuff, read it.

          These articles make me wonder how much misinformation goes into my head thru slashdot. I just don't know enough to discredit it in most other topics.
    • Re:Too bad... (Score:3, Informative)

      by ramzak2k (596734)
      now that you compare the two, you remind me of a good article [msnbc.com] I read on msnbc a while ago.

      The Comparison:
      Deep Blue could analyze 200 million possible moves per second, while Deep Fritz looked at a paltry 3 million moves a second. However, programmers said Fritz was designed to look more intelligently at the moves ahead, rather than using Deep Blue's brute-force method.

      And What happened to Deep Blue:
      Back in 1997, IBM created Deep Blue specifically for the Kasparov challenge, using 200 special-purpose chess chips, 32 processors and a score of programmers. Since the system didn't have commercial value, it was broken down after the match. In contrast, Deep Fritz is a souped-up version of a commercially available product published by the German company Chessbase, running on eight 900mHz Pentium chips.
  • by sssmashy (612587) on Saturday October 19, 2002 @10:56PM (#4488193)

    "We've learned a lot from this, and there is much we can do to increase Fritz's playing strength." Frans Morsch, creator of Fritz

    For instance, they could install louder speakers to increase the effectiveness of Fritz's Shakespearian heckling ...

  • by WolfWithoutAClause (162946) on Saturday October 19, 2002 @10:56PM (#4488194) Homepage
    Deep Blue kicked Fritz's ass, and Kasparov; and there are good reasons for thinking that Kramnik would lose too. It's a real shame that IBM dismantled it...
    • "Deep Blue kicked Fritz's ass, and Kasparov; and there are good reasons for thinking that Kramnik would lose too. It's a real shame that IBM dismantled it.."

      Fritz beat Deep Blue, mainly because Blue's program wasn't very optimized; it calculated for the same positions multiple times, thereby erasing any advantage it had in the number of moves it could process per second.

  • by russellh (547685) on Saturday October 19, 2002 @11:20PM (#4488281) Homepage
    Oh I think machines have been our master for a long time. Especially during the floppy era (Please insert disk #18, press any key to continue...). Can we ignore their requests? I think not. Do they ignore ours? They don't even listen! No amount of threats or yelling at the computer will change their behavior, and yet their simple, calm request for the any key causes fear and panic throughout humanity. In addition, we have served the machines very well by evolving them quite rapidly, and they have returned the favor with addictive mind-numbing games for us. They get smarter while we get dumber. Hmm..
  • How about letting Bill Gates play russian roulette against a Linux machine? It would be cool if it was
    going to be featured on a reality show on TV. :)
  • by mtec (572168) on Saturday October 19, 2002 @11:23PM (#4488302)
    A game of checkers.
  • What's the big deal? (Score:2, Interesting)

    by Anonymous Coward
    Machines have been better than us at quite a few things for a number of years. They are all unsophisticated stuff. No matter what many would have us believe, chess is another of those unsophisticated undertakings where brute force goes a long way.

    Just as people carry on competing against each other to see who is the fastest runner, despite of the fact that even a 50cc motorbike would beat them hands down, they will carry on competing at chess - despite the fact that machines are already probably better at it. The time has come to put chess where it belongs: a more or less interesting game, but very, very far from the pinnacle of human intellectual achievement.
  • by targo (409974) <<moc.liamtoh> <ta> <t_ograt>> on Saturday October 19, 2002 @11:25PM (#4488310) Homepage
    I would still say that Kramnik is probably the stronger player when it comes to pure chess knowledge but there was more to the match than just that.
    In the first games, Kramnik played very solid, positional chess, and slowly but surely, just walked over Fritz.
    In game 5, Kramnik made his first human error, blundering in a difficult position, and losing immediately because of this. It might have been because he was tired or for thousand other reasons, we don't know.

    But we know human weakness #1: we make mistakes, and can't handle every similar situation perfectly, computers can.

    In game 6, Kramnik went for a gamble, sacrificing material to get a decisive attack. Kasparov had made the same mistake when playing against Deep Blue - his attack would have been devastating against any human, but one should never, ever attempt a tactical gamble against a computer because that's where they are strongest.

    Human weakness #2: we underestimate our partners, computers don't.

    In games 7 and 8, the score was tied, and Kramnik played very cautiously, clearly being afraid of a loss. If he had played at his best and avoided mistakes that he had made in games 5 and 6, he might have won, but he decided not to go for it.

    Human weakness #3: we get scared, computers don't.
    • by Omega Hacker (6676) <omega@nospaM.omegacs.net> on Saturday October 19, 2002 @11:42PM (#4488373)

      > Human weakness #3: we get scared, computers don't.

      You had a pretty good set of arguments going there, until this last one. And I quote:

      "No disassemble Johnny Five!"


      • > Human weakness #3: we get scared, computers don't.

        You had a pretty good set of arguments going there, until this last one. And I quote:

        "No disassemble Johnny Five!"


        You just wait until Deep Punch kicks Lennox Lewis' ass. Then we will all be very, very scared.
    • by Anonymous Coward
      Human weakness #4: we cannot scale by Beowulf clustering, computers can.
    • > If he had played at his best and avoided mistakes that he had made in games 5 and 6, he might have won, but he decided not to go for it.

      Except that Fritz was playing black in 6, and at this level, drawing with black is a win. Kranmik was trying not to lose the tournament in 5 and 6, but he sure lost game 6.
    • I believe that you made the point quite well why humans are and (for now at least) will be always better. Kramnik lost only through mistakes, most inteligent people dont make the same mistake twice, that is our biggest strength, that we learn quickly, and in this case why he should have won.

      Kramnik walked over the computer in the first games because he played "against a computer" not like Kasparov who played "against a human" in tactics that is. He played a completly different game to his usual tactics, tactics designed to beat Fritz and only Fritz, that's where Kasparov lost. Unfortunatly the mistakes Kramnik made later, (maybe he got cockey?) cost him the out-right win.

      Of course in the future the programmers will take this into account, as will Kramnik or Kasparov or whoever..
    • Kasparov had made the same mistake when playing against Deep Blue - his attack would have been devastating against any human, but one should never, ever attempt a tactical gamble against a computer because that's where they are strongest.

      Agree. I think in future human-computer matches, the human opponent should get some coaching on how the computer program fundamentally works. I had to explain this to my g/f just the other day, when she was getting frustrated that the machine kept seeing around her traps.

      You cannot fool a computer chess program with a two- or three-move trap. Provided the computer's evaluation function is not brain-dead (causing pruning of good branches), the computer can and will see every possible combination of moves you can make, that far ahead. The computer is not going to "miss" some killer move. It sees it.

      You have to play strategy against the machine. That's why I can never win against computer chess programs -- I'm a very unbalanced player (and not a very good one) and I can't think ahead further than the machine. It also explains why I can beat computer Go programs, which can't look more than about two or three ply ahead.

  • Tie?!? WTF (Score:4, Funny)

    by bobdotorg (598873) on Saturday October 19, 2002 @11:27PM (#4488320)
    WTF! No overtime? No sudden death chess?

    A Tie?!? How unAmerican is that?

    Oh, wait.
  • by Ryu2 (89645) on Saturday October 19, 2002 @11:44PM (#4488384) Homepage Journal
    One oft-quoted complaint by Kasaarov, of the last man-vs-machine match against Deep Blue, was that Deep Blue was programmed with the moves of all of Kasparov's past championship games so it could ostensibly analyze the strategies used by Kasparov beforehand, while Kasparov was not allowed to look at Deep Blue's previous games.

    Anyone know if this was ever an issue in this current tournament?
  • by jacquesm (154384) <j@SLACKWAREww.com minus distro> on Saturday October 19, 2002 @11:44PM (#4488385) Homepage
    There was a time when people put a lot of weight on a computer being able to play a high level of chess, but that was before the advent of a strategy that is best characterised as massive parallel brute force solution of a game with a very large tree of possible moves.

    Nowadays, there really is very little point. You are comparing apples to oranges when you allow the one party a nearly infinite budget of cycles and power and allow the other party 18 cycles per second on a biological processor that is running on a couple of oranges for a whole games' worth of computation.

    I we want to make this kind of competition interesting again I think there really should be limits on the power and cycle budget of the machine involved in order to get back to the essence of the whole game theory thing, which is not going flat out for the maximum number of ply you can look ahead but to try to quantify a strategic advantage.

    Unfortunately that will not make for interesting press releases.

    To me the current 'matches' look a little bit like sledgehammers being used to crack nuts. It does work, but there is no real output. All this stuff proves is that if you throw enough money at a problem you can force the outcome of something as trivial as a game of chess.

    It does not advance the state of the art in computing at all.

    • I think you're missing part of the point of this entire affair. It's not necessarily about computer science, and many people that are looking for the CS value in this may well be bored. But as a story about _chess_, this is facinating.

      While your points about how brute forcing the issue may not be very interesting technically, I have found, following this story and the previous iterations of the same, that I am facinated the diffrences between human chess and computer chess. Clearly, Kramnik is playing a very different sort of chess than the one that Fritz plays. Where human chess is intuitive and often highly psychological (Kramnik may well have won this match if he hadn't resigned a possible drawn position), computer chess is calculated and totally passionless. The brute-force approach being taken to teach computers to play better chess produces chess players that won't often make interesting sacrifices; computers are notoriously materialistic in chess. But computer defence is appalingly good; Kasparov could often scare opponents into lost positions with an aggressive attack, and the linked story on this match mentions a similar circumstance , but computers play a frightening defence. Computers never get scared, never make a mistake, and know exactly what's going on in the next five turns. If there's a bizzare line of play that produces a strange but favorable board, humans will often overlook it, as human intuition often passes outre solutions by, but a computer player will take the game places that a human might never. On the other hand, a computer cannot see fifteen turns into the future, with perfect accuracy but no hard data, the way a human player can.
  • by Ryu2 (89645) on Saturday October 19, 2002 @11:55PM (#4488413) Homepage Journal
    Anyone know? Not trying to start a flame war here, rather, just curious.

    I know that Fritz is supposed to be much more intelligent in its search-tree pruning than Deep Blue was, and not require so much computational power.
  • by Anonymous Coward on Sunday October 20, 2002 @12:05AM (#4488451)
    One kind of chess that has been experimented with a bit is where humans play each other, but each has the aid of a computer during the game. Shirov and Anand played a short match like this last year (or the year before), and it seems like an interesting concept. You have the normal human strenghts in judgement, strategy, and intuition coupled with a tool that can process millions of tactical possibilities.

    The average slashdotter seems pretty certain of the day when programs, these unbeatable machines, will be able to simply trounce the best humans in one on one competition. But what about a future match with the best chess computer against a top notch grandmaster with his own pc, even a weaker program? Do you people honestly think that human knowledge will simply be obviated by brute force processing power?
  • by Will_Malverson (105796) on Sunday October 20, 2002 @12:10AM (#4488467) Journal
    ...It's Man vs. Nature.

    Kramnik and Kasparov are the best chess players that nature can produce. Meanwhile, humans have built Fritz and Deep Blue. We aren't in the process of losing to machines. We're in the process of beating nature.
  • Hm, a draw... (Score:2, Insightful)

    by travdaddy (527149)
    There's always something disappointing about a draw. I would have liked to see a clear winner, either man or machine, but it wasn't meant to be. That being said, I am not disappointed with the overall match. I think it showed human innovation in two ways, one in the powerful AI technology developed over the years used by Deep Fritz, and one in Kramnik being able to attack Fritz's weaknesses.

    What's more disappointing than the draw, however, is that this match was not nearly as publicized as Deep Blue vs. Kasparov.
    • Re:Hm, a draw... (Score:3, Insightful)

      by Tablizer (95088)
      What's more disappointing than the draw, however, is that this match was not nearly as publicized as Deep Blue vs. Kasparov.

      Well, that is because it is old news. The Deep Blue game showed that computerized chess *can* beat top humans. This new game did not tell us anything much different, except that maybe it might be a while before computers completely dominate rather than play close games.

      If the score was very lopsided, then it may have made news. However, the way it did come out it did NOT make the Deep Blue episode look like a fluke, and that is why it is ignored, more or less.

      The Deep Blue game was THE coming out party for the machine. One party is enough. Nobody wants to christen a ship twice.
  • "Junior" is world champion for computers.
    Kasparov is (still) the best player in the world.

    Kasparov will have to reduce the heat on the board. He does it successfully against human players but computers are more accurate in complicated positions.

    I think that Kasparov has a good chance to win.
  • by mtec (572168) on Sunday October 20, 2002 @12:57AM (#4488595)
    There was a young Russian named Kramnick
    Who at chess was just real frickin' slick,
    He came back in a blitz
    But could only tie Fritz
    he exclaimed "just a tie, and my wallet's so thick!"

    (sorry)
  • who knew (Score:2, Funny)

    by Aleph Yin (523644)
    i for one welcome our new chess-playing overlords.
  • by Anonymous Coward on Sunday October 20, 2002 @01:41AM (#4488704)
    Anyone who has seen the games and knows even a little of chess and computer chess can tell that Kramnik won this match. The first three games he steers brilliantly, forcing the computer to play positions it doesn't understand and beating it twice. He then changes his strategy to aim for more computer-oriented positions and loses two games to draw the match? Gimme a break. His losses to the machine were his own choice -- he had already proven he could force it into positions that modern computer chess programs can't hope to understand. Whether he chose to wander into such unfriendly waters as a show of confidence or because of monetary...issues is a question for the philosophers.
  • Chess vs. Magic.... (Score:3, Interesting)

    by wowbagger (69688) on Sunday October 20, 2002 @09:31AM (#4489579) Homepage Journal
    Go and chess are both computations: In both games there are no unknowns but the strategy of the other player. You may not know that the other guy is going to castle, but you know that he CAN castle. Therefor, you can theoretically work out the optimal series of moves from any given state.

    Games like backgammon and poker have unknowns - you may know what is in your hand, but you don't know what is next up, nor do you know what the other player has. As a result, given the state you can see, you CANNOT compute a single optimal set of moves - all you can do is probablistically state "most of the time, this would be the best move".

    Add to that bluffing - in poker you can bluff the other guy into losing when he should have won.

    Now, consider card games like Magic: The Gathering . Not only do you not know what the other guy's next draw is, nor what he has in his hand, you cannot even for certain limit the set of what he can draw very much - "Does he have a Force Of Nature? He might, or he might not."

    In addtion, since each card can change the behavior of the other cards, the combinatorial growth of the game state is extremely large. You might be winning, then the other guy plays a card that completely changes how your cards act.

    Given the above, much of the game is decided before you even sit at the table - how you construct your deck may decide the game, even before you see your opponent. AND you might change your deck, based on what you observe of the opponent's strategy.

    Given the above, what I would like to see would be a computer program that could, given a set of N cards, compose a deck of M card (where M < N), play that deck against an opponent, then compose a new deck from the same N cards that answers the strategy of the opposing player.

    When we can do that, THEN I'll believe we have real A.I.
    • In game theory, the solution would be a mixed strategy under the condition of limited information. Instead of responses, you have a set of responses with a probability attached. However, this does not find an *optimal* strategy given an opponents *inoptimal* strategy, only a superior (or at worst identical good) strategy given any strategy from your opponent. For the simple case of rock-paper-scissors, the optimal mixed strategy is to pick one at random, no matter what the opponent chooses.

      If the other guy picks rock every time, you still pick at random. If you try to adapt to his strategy (picking paper) you give your opponent an strategy that is better than the optimal equilibrium, namely scissors.

      Same goes for e.g. poker. The optimal solution is a set of options (fold, bet x, bet X, call) with probabilities given any specific hand. Numerically it's a lot more work, but the theoretics behind it are not much harder.

      Kjella
  • by MarkWatson (189759) on Sunday October 20, 2002 @11:32AM (#4489998) Homepage
    Sorry if this is a little off topic, but I have written two fairly widely used Go and Chess programs (the free chess program that Apple distributed on their demo cassette tape the first year or so they sold the Apple II, and my ancient commercial Go program Honnibo Warrior).

    Anyway, the other posts concerning the search branching factor difference in the two games are right on.

    Typically, there are a few hundred possible legal moves in any Go position. It is simple to write an alpha-beta search that does well in chess because of the relatively small branching factor (the free Java AI web book on my site has an example).

    Really, Go is an ideal testbed for AI, but currently the best Go programs are good engineering projects, but not really good AI projects. I would consider a great Go project to include these features:

    • Have a library of all available historical games (lots! I have a book of ancient famous Go games - very cool!!!) and the ability to search for opening patterns, etc. - the ability for both self analysis and the analysis of other games)
    • ability to play off-line training games against all available Go programs
    • use genetic programming to evolve new operators for statically ranking moves based on pattern matching
    • tutoring mode where a human player could criticize the program's moves - these criticisms would become a permanent part of the data maintained by the program and be used for off line machine learning

    -Mark

3500 Calories = 1 Food Pound

Working...