Kramnik Ties Fritz; Machines Not Yet Our Masters

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

Comments

Is it just me...

[strredwolf]

or are we going to start getting The Onion inspired subject titles?

Related older link...

[TheGreenGoogler]

This story appeared 8 hours ago here...

Dateline

[Anonymous Coward]

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"

Re:Dateline

[Anonymous Coward]

France is a big Wimp. They let everybody else walk all over them, yet complain when somebody wants to get rid of the potential tramplers, like Saddam.

Wimps!

Re:Dateline

[Anonymous Coward]

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"

In a related news, US declared they were neutral. They might consider freezing Machines assets in one year or two.

We can at best hope a tie..

[Tester]

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

Re:We can at best hope a tie..

[Kircle]

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

Re:We can at best hope a tie..

[pVoid]

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

Re:We can at best hope a tie..

[wwwojtek]

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

Re:We can at best hope a tie..

[targo]

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.

Re:We can at best hope a tie..

[Anonymous Coward]

That's not known to be true. For a particular game, either the one moves first, or the one who moves second might (if the combinatorics are fully worked out) always win in perfect play.

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

Re:We can at best hope a tie..

[Nigel Stepp]

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.

Re:We can at best hope a tie..

[HeghmoH]

I seem to recall something from game theory where in a game like Chess, where the game is deterministic, the players move sequentially, and it's illegal to draw, then if both sides play a perfect game, the side that goes first will always win. Or something like that. Does anybody know what I'm talking about, and is this right?

Re:We can at best hope a tie..

[Anonymous Coward]

If both become too good, they will tie all the time

More realistically, "man" will stay more or less the same strength, and "machine" will continue improving. We'll see machines either winning or tieing, never losing. Actually if man doesn't improve at all we will start to see *less* drawn games as the ELO gap widens between man and machine.

Re:We can at best hope a tie..

[Anonymous Coward]

It has not yet been proven that with perfect play a game of chess will always result in a draw.

Given the truly vast number of positions that make up the finite number of moves available under the normal rules for chess, and, assuming that such a mapping did exist, the difficulties inherent in calculating which precise moves happen to constitute 'perfect', this is likely to remain true for some time.

Re:We can at best hope a tie..

[piscine]

I seem to recall something from game theory where in a game like Chess, where the game is deterministic, the players move sequentially, and it's illegal to draw, then if both sides play a perfect game, the side that goes first will always win

Incorrect, as the starting position could be a reciprocal zugzwang (not uncommon in chess endings).

Re:We can at best hope a tie..

[zulux]

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.

Re:We can at best hope a tie..

[GigsVT]

What is this effect? "Post about 'Go' in a chess thread for +5 syndrome?" It's funny that this exact same message, more or less, has made +5 in the last 4 or 5 chess stories.

Re:We can at best hope a tie..

[yeOldeSkeptic]

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.

Re:We can at best hope a tie..

[Moridineas]

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.

Re:We can at best hope a tie..

[ImaLamer]

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.

Re:We can at best hope a tie..

[aminorex]

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

Re:We can at best hope a tie..

[SeverianDragon]

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

Re:We can at best hope a tie..

[harlows_monkeys]

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.

Re:We can at best hope a tie..

[harlows_monkeys]

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.

Re:We can at best hope a tie..

[harlows_monkeys]

Counterexample. We have a counter that starts at 0. Each player on his turn adds an integer from 1 to 9 to the counter. The winner is the player whose turn puts the counter over 99.

That game is deterministic, sequential, no draws are possible, and with perfect play the second player wins.

Re:We can at best hope a tie..

[Anonymous Coward]

You're so funny... you first declare you know almost nothing about Go (well, you do know there are some 9x9 boards for kids) then you give us your definitive sounding conclusion about which game is harder... Maybe you should first try to play a few Go games before being so categoric about your wisdom. On a real 19x19 board.

Re:We can at best hope a tie..

[quintessent]

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.

Re:We can at best hope a tie..

[crulx]

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

Re:We can at best hope a tie..

[Order]

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

For a single game, yes; but for a match of 8 games, where players alternate colours, perfect game will always result in a tie, no matter what it is.

Re:We can at best hope a tie..

[Anonymous Coward]

Posting anonymously since you did. The reason I discussed the 9x9 board is that that's the only experience I've had. Since you actually added nothing to the discussion other than an ad hominem attack, do you have any evidence that Go is a "harder" game? I put the game in the only exact terms I can in, in an AI context--branching factor. thanks

Re:We can at best hope a tie..

[Nea Ciupala]

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.

Not so. The "theory" has not advanced signifiantly for chess-playing software in the last 30 years or so, it's still the brute-force approach most programs use. It's only faster hardware that made all this possible. For Go, a brute force approach simply does not work. Not only is the branching factor a lot larger, and this *is* important, but more importantly you cannot write a position evaluation function as easy as for chess.

Re:We can at best hope a tie..

[legLess]

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:

• NYT article (archived offsite - no pwd) from 1997
• AI-Depot article comparing chess and go.
• Google cache of chess vs. go article (slightly fluffy and biased towards go)
• The Sciences article

Note that I'm not saying go is better than chess. I think such arguments are foolish. But, to quote myself, from a computer's perspective go makes chess look like tic-tac-toe.

Re:We can at best hope a tie..

[Anonymous Coward]

Ha ha ha ha. Your post is so clueless it makes me laugh. I chuckle thinking of you, going home your duty accomplished, confident you have written a good post, comforted by the Slashdot moderators, who were impressed by your thoughful prose.

Thoughtful, but clueless.

(moderators, i'm serious; had i some points myself today, i would have immediately moderated his post [-1] Overrated)

Re:We can at best hope a tie..

[cheezehead]

Hmmm. Take tic-tac-toe: it's deterministic, the players move sequentially, and it's always a draw with perfect play (it's quite easy to write down every possible game). I'm a bit puzzled by 'it's illegal to draw'. Do you mean it's illegal to pass a turn (i.e. not move), or do you mean that a drawn game is not allowed? In the latter case, that does not apply to chess.

Re:We can at best hope a tie..

[cheezehead]

Go does have a much bigger game tree, due to its much large branching factor.

True, although there is only one type of piece in Go, and the branching becomes less as the game progresses. Not that it matters, both the game trees of chess and go are way beyond current computational means. I think I read somewhere that chess has an average of 40 possible moves per ply (half-move). Let's assume that a chess game takes 40 moves, or 80 ply per game (a rather conservative estimate). Then the number of possible games is in the order of 40^80, which is something like 1.46*10^128. The estimated number of atoms in the universe is something like 10^76.

Re:We can at best hope a tie..

[Anonymous Coward]

I agree that my post did not add much to the topic. I was just offended to see someone that only had contact with Go through a few games on a children board draw such categoric conclusions as you did. And the fact that your post was moderated +3 did not help either :) Now I do not have "evidence" about Go being "harder" except for the million-dollar prize for the first dan-playing Go program (and 1 dan is far, far, from the strongest human players) that is still unclaimed. The main reason Go is much harder (for computers, for humans it might be only slighty harder) is the tremendous role intuition plays in Go as opposed to chess. In go, you need a lot of intuition to evaluate a position (so brute-force approaches do not work) and you also need intuition to prune the much larger search space. (average branching factor about 150-200) And intuition is a hard concept for AI.

Re:We can at best hope a tie..

[legLess]

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.

Re:We can at best hope a tie..

[cheezehead]

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.

This is true. But the same goes for chess. Contrary to popular misconception, chess programs do not calculate every possible move, most branches are pruned based on early evaluation (an exception is where a computer program is trying to solve a mate-in-x-moves problem).
For example, a branch where the computer loses a queen will only be evaluated a few moves deep. The more promising branches will be evaluated more deeply.
The fact that computers cannot beat humans in Go (yet), has also to do with the limited amount of research invested in Go playing programs (compared to chess programs). This is simply because chess is a lot more popular than Go (I'm not saying it's "better", or anything like that).

Re:We can at best hope a tie..

[s1234d]

It is the large size of the Go board (19 x 19) that makes the game so difficult for computers. Attempts to use brute force searches have to deal with the number of possible positions skyrocketing much more than chess with its 8 x 8 board.

Re:We can at best hope a tie..

[Anonymous Coward]

The fact that computers cannot beat humans in Go (yet), has also to do with the limited amount of research invested in Go playing programs (compared to chess programs).

You can of course provide support for this bold affirmation?

This is simply because chess is a lot more popular than Go

Oh yes? If you say "popular", you also have to say where. Go is much more popular than chess in Asia. There's a lot of people living in Asia, by the way. Clearly, Go is more popular than chess. :)

Re:We can at best hope a tie..

[cheezehead]

Chess has at most 40 legal moves possible for the first move;...

20 for white and 20 for black, to be exact. It becomes more after the first moves, of course...

Re:We can at best hope a tie..

[casret]

Or to make it even more obvious, counter starts at 0, each player adds 1 to the counter, and the winner is the player who puts the counter over 1.

Re:We can at best hope a tie..

[tunah]

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.

Re:We can at best hope a tie..

[Melex]

If two chess players play perfectly, then the game will always result in a tie I dont think this is true. White has always got a slight advvantage as he starts. If white has even got a slight advantage with perfect play he should win.

Re:We can at best hope a tie..

[Anonymous Coward]

two interesting quotes from the above link;

When a player fills the penultimate liberty of a stone or string, it is courtesy to declare "Atari!" which alerts the owner of the stone or string of its impending capture.

;

... Mr Ing, he was offering 40 million Taiwanese dollars (over 1 million dollars US) to anyone who could write a program that can beat a Taiwanese professional. Sadly Mr Ing died on August 27, 1997 at the age of 84. The prize was still valid until the year 2000.

Re:We can at best hope a tie..

[jericho4.0]

moderators, i'm serious; had i some points myself today, i would have immediately moderated his post [-1] Overrated)

People tend not to take AC's too seriously, loser.

Re:We can at best hope a tie..

[yeOldeSkeptic]

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.

Re:We can at best hope a tie..

[TerryAtWork]

You know what? I bet computers are BETTER at fischer-random chess then people!

Why? Because when you scramble the back row, 100,000 games of chess knowledge that the grandmaster has go right out the window! It's tactics all the way and computers are better at tactics than people!

Re:We can at best hope a tie..

[boa13]

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

Re:We can at best hope a tie..

[Anonymous Coward]

Ha ha ha, welcome to the club! Remorseless, ha!

Re:We can at best hope a tie..

[JordanH]

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

Re:We can at best hope a tie..

[Rademir]

What is this effect? "Post about 'Go' in a chess thread for +5 syndrome?" It's funny that this exact same message, more or less, has made +5 in the last 4 or 5 chess stories.

Combinatorics envy.

Re:We can at best hope a tie..

[Cryogenes]

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?

Re:We can at best hope a tie..

[Anonymous Coward]

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!

That sounds like an algorithm NOBODY would use for chess, as exchanges are normal (and not called sacrifice even if you lose a piece first). I suggest you study some of the algorithms, and chess, AND Go, before you open your mouth. I cannot believe any researcher would seriously consider this..

A kickass non-brute approach to Go would probably have to COMBINE neural networks and/or shape-recognition algorithms and search-trees. Not a trivial task at all! I believe this because if a trivial algorithm could solve Go as has happened with chess, then it would have been found by now.

Re:We can at best hope a tie..

[moonbender]

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.

Re:We can at best hope a tie..

[Namtar]

This article [slashdot] is the reason I started playing Go this summer. It is truly a beautiful game. When playing chess I'm trying to crush an opponent, when playing Go I feel more like I'm painting a picture with them. Plus I love that two players of uneven skill can play an even game because of the way the rating system is set up.

Re:We can at best hope a tie..

[photon317]

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.

Re:We can at best hope a tie..

[Anonymous Coward]

And yet we have ONE world champion....

It is widely believed that no human will ever play perfect chess, so the drawing issue is not a problem, I think.

Re:We can at best hope a tie..

[markk]

Just a note: If you can prove that " If two chess players play perfectly, then the game will always result in a tie" you are way beyond current computational or mathematical power. We don't know the full playbook of chess. It might not be that perfect players result in a tie. It could be that white always wins - or black - which would be very interesting because it would be counter-intuitive.

Re:We can at best hope a tie..

[skeptikos]

How do you know the result will be always a tie?

This has been said many times but here we go again. Given the nature of chess it is not hard to see that there exist a perfect way of playing and if two perfect players meet the outcame will be always the same. This means: white will always win or black will always win or the game will be always a draw.

AFAIK nowbody has proved which one of the three cases is the answer. Having only ties is a reasonable conjecture, but it does not seem far more possible than the other two.

Re:We can at best hope a tie..

[Moridineas]

That sounds like an algorithm NOBODY would use for chess, as exchanges are normal (and not called sacrifice even if you lose a piece first).

You know, maybe that's why they called them sacrifices as OPPOSED to swaps? Sacrifice, ie, losing a piece to come into a better position--eventually. It doesn't have to mean a queen-for-queen trade, and the superiority of the position might not be immediately visible.

I believe this because if a trivial algorithm could solve Go as has happened with chess, then it would have been found by now.

Yow, did you entirely miss the discussion of the intense AI research put into chess starting in the 60's? "Breaking" chess (if indeed it has been broken) has been a product of MUCH research and ultimately of specially built supercomputers, no trivial task. I really wonder if the past 4 decades had been spent with as much effort being put into studying Go and specially built computers were being made all the time, would Go have fallen?

Re:We can at best hope a tie..

[Jerf]

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.

Re:We can at best hope a tie..

[rollingcalf]

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

Not necessarily so. Both players do not start out on exactly equal standing, because white moves first and the king/queen positions are mirror images of the other player's setup. Currently there is no definite proof that either side has an advantage. But with perfect play, it may turn out that one particular color will always win if both play perfectly.

Still, that refers only to an individual game. With a multi-game matchup of an even number of games, and players alternating between black and white, either all games will draw or the same color will win all games, thus leaving the overall result as a draw.

Re:We can at best hope a tie..

[Anonymous Coward]

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.

Wrong. Go is incredibly more difficult to program then Chess. It would take a week for me to make a Chess program that would crush me. It takes one year to write an average Go program. And, yes, there is much research about it, since there was a $1,000,000 prize for any program that would beat a professional Go player.

Go pieces, once placed on the board, cannot move anymore.

Totally wrong again. Once you have placed a stone, you cannot move it, that's what makes go tremedously more difficult: how it is placed will have a sure impact on the final result of the game: a bit above, it might have given you one point more of territory (but you could be attacked more easily), a bit lower it would be safer but give you less territory. Each move is vital, has a direct impact on the score, an impact that cannot be evaluated by any easy mean until the endgame.

Re:We can at best hope a tie..

[Anonymous Coward]

If one player in a more-or-less evenly-contested go game captures all 4 corners his victory is assured.

No!

"Win 4 corners and resign" -- Japanese proverb.

Re:We can at best hope a tie..

[2short]

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

This point, that the full game tree of chess exceeds the number of atomes in the universe, comes up a lot. This is true, but misses the point that you don't need to store (or even compute) the entire game tree to solve chess. Once you know that a particular move leads to certain victory, you don't need to calculate any more moves from that position. Furthermore, you don't even need to store all the moves onward from that one if you can identify an algorithm that will produce them. Once solved, the vast, vast majority of positions can simply be marked "Deep Fritz can take it from here" (for example). Chess may well be solvable in the future, with the solution stored as a big opening book, some good heuristics to be applied to a reasonable-depth min-max tree, and a few million special cases.

Re:We can at best hope a tie..

[Anonymous Coward]

Hi, I'm meta-modding right now. I gave an "unfair" to the mod who modded that as off-topic. The topic is chess. You are less likely to moderate now. Please learn to read in the future; either the article or the mod rules.

Re:We can at best hope a tie..

[BCGlorfindel]

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.

I think it's a bit insulting to the grand master level players of go to claim so certainly that there exists an Eval(p) function for the board. Not to mention how many generations of Korean/Chinese mathematicians who have likely attempted to find such an algorithm.

Re:We can at best hope a tie..

[Transcendent]

10^720 distinct games that you can play in go

Actually, the number is infinite. It is possible to set up an endless series of Ko's (...literally translated "eternity") that will keep the game going for ever.

...worried about running out of stones? Just trade prisioners when it gets low...

Re:We can at best hope a tie..

[Transcendent]

hahahah...

You seriously underestimate the history and complexity of Go.

The number of possible moves in go has nothing to do with its difficulty.

Not for a human, but to brute force it (like a computer does with Chess) would be impossible with Go.... there are an infinite number of games to be played. (It's possible to set up an endless combination of Ko... allowing the game to be played infinitely)

Go has not been analyzed and picked apart enough for us to say that it us much more difficult than chess.

Go has been around for over a thousand years. It has been studied like a religion in Asia for those thousand years, with strategy constantly evolving. It is still played with great enthusiasm there today with professional players recieving yearly sallary comparable to US professional football players.... I'd say that Go has been picked apart pretty well...

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.

True, but the stones (go pieces) can be removed... If you've ever played Go (which I don't think you seriously have) you would know that the endgame situations, although tricky at times, have a comparible number of logical possibilities of movement as chess.

Re:We can at best hope a tie..

[Transcendent]

E.g., Gnu Go has become much better this past year, and so have others, probably.

The best computer Go program to date (The Many Faces of Go) can be easily beaten by a beginner. I play on KGS often and have talked to 20k's that have beaten it...

Play some Go seriously, you'll understand better why computers still have a long way to Go...

Amen...

Re:We can at best hope a tie..

[wwwojtek]

This is illegal under any set of go rules

Re:We can at best hope a tie..

[Transcendent]

The only set of rules I know of that enforce any other repetition besides a single Ko situation is the chinese ruleset which says that the same situation can not occur twice in a single game. The AGA and Japanese ruleset don't have anything like.

Re:We can at best hope a tie..

[Transcendent]

maybe you didn't understand my setup of Ko....

Just set up 3 different Ko's on a single board... if you do it right, you can rotate through the different Kos forever...

Machines Not Yet Our Masters?

[skydude_20]

Is it just me, or did someone forget the current score: Machines (1-0-1), Humans (0-1-1).

Re:Machines Not Yet Our Masters?

[Namtar]

Chess is nothing. I'll be impressed when an A.I. chat bot can talk a girl into a date. This would be a tool every slashdotter could appreciate.

Re:Machines Not Yet Our Masters?

[Anonymous Coward]

That depends... Are we talking intelligent girls, or a/s/l? girls?

Re:Machines Not Yet Our Masters?

[bdesham]

I'll be impressed when an A.I. chat bot can talk a girl into a date. This would be a tool every slashdotter could appreciate.

So I could be dumped for an A.I. chat bot. And I thought I couldn't get any lower...

Re:Machines Not Yet Our Masters?

[agentZ]

Are we going to do Turing tests on #hotsex?

Re:Machines Not Yet Our Masters?

[Anonymous Coward]

i thought the score was even: 1W-1L-1T for man and machine. didn't kasparov beat the computer in the first game?

Re:Machines Not Yet Our Masters?

[EggplantMan]

Most participants in #hotsex would fail the Turing test regardless.

Re:Machines Not Yet Our Masters?

[Bastian]

Hey, at least you would't be the poor sap who has to get dumped for the A.I. chat bot that HE WROTE.

Re:Machines Not Yet Our Masters?

[Cyno01]

hey, thats not funny, SMARTERCHILD stole my girlfriend!

Re:Machines Not Yet Our Masters?

[PacoTaco]

Yeah, the bot would know not to mention Linux on the first date.

Re:Machines Not Yet Our Masters?

[PacoTaco]

The real test would be BSD-related Slashdot posts.

Re:Machines Not Yet Our Masters?

[Dagheti]

No, Kasparov defeated Deep Blue in the first computer vs. world champion match. So the score is actually (1-1-1). This match just again proved from inspection of the games that grandmasters are far better at chess then computers, they just get tired, make mistakes, and take too much pleasure in beauty.

Re:Machines Not Yet Our Masters?

[Tablizer]

Chess is nothing. I'll be impressed when an A.I. chat bot can talk a girl into a date.

1. Buy the books listed below
2. Extract and codify the rules
3. Program them into a chat-box
4. SCORE!

"How To Pick Up Girls 2000!" by Eric Weber

"The Rules for Getting Laid" by David Graff, et al.

"How to Succeed With Women" by Ron Louis, et al.

(I really dig the cover of the "Laid" book.)

Re:Machines Not Yet Our Masters?

[Anonymous Coward]

No No

The score is

Machines 1-1-1 Humans 1-1-1

Kasparov won the first match against Deep Blue.

Actually, he's right

[etymxris]

It doesn't matter. Only one of two outcomes is possible:

1. White can force a win or
2. Black can force a draw

If White can force a win, then, in a match of 8 games, each side will have four wins. If Black can force a draw, then in a match of 8 games there will be eight draws.

But as other people have said, determining whether a draw or win can be forced is computationally infeasible. So the game will be interesting for a while.

Re:Actually, he's right

[harlows_monkeys]

Why do you assume that "Black can force a win" is not possible? I have not heard of anyone proving that chess with perfect play is not a loss for white.

Re:Actually, he's right

[Anonymous Coward]

First can you provide a link explaining the two outcomes. Everything that I know about chess says that those outcomes are expectations but not the only two outcomes. Maybe you and the original poster are being loose with your terminology.

If white can force a win, then white always wins. Maybe you don't understand what forcing means. If Black can force a draw, then how could White evern win?

Re:Actually, he's right

[Chandon Seldon]

Black has the first win on the tree...

Re:Actually, he's right

[Anonymous Coward]

So what's your point? What does this have to do with forcing and perfect play?

Re:Actually, he's right

[etymxris]

Why do you assume that "Black can force a win" is not possible? I have not heard of anyone proving that chess with perfect play is not a loss for white.

Perhaps I was being sloppy. I was thinking that since the board is roughly symmetrical, if either could win, it would be the one with the first move.

In any case, it doesn't matter. As long as the outcome is always one of the following possibilities, any fair match of an even number of games will ultimately result in a draw:

1. White can force win
   
2. Black can force win
   
3. Both sides can force a draw
   

Even allowing for a strange state of affairs where Black can force a win, the above three possibilities absolutely limit any deterministic board game like chess, go, tic-tac-toe, etc. Either one of the sides can force a win, or both sides can force a draw. If e.g. Black can't force a draw, then either Black or White can force a win.

If White can always force a win, then every match of eight games will end 4-4. If Black can force a win, it will also be the case that every match of 8 games will end 4-4. If either side can force a draw, then every match of 8 games will end in 8 draws.

Realizing this is very simple if you just imagine that chess was as easy as tic-tac-toe. Adults don't play tic-tac-toe because they know a game played perfectly on both sides always results in a draw, and the perfect game is really easy to play.

Re:Actually, he's right

[alexo]

Why do you assume that "Black can force a win" is not possible? I have not heard of anyone proving that chess with perfect play is not a loss for white.

While I am not aware of any rigorous mathematical proof that chess is not a forced win for black, it is highly likely that strategy-stealing by white is possible (e.g., by wasting moves).

Re:Actually, he's right

[Chandon Seldon]

Black may have the only forcable win on the tree as well.

Was the match 'fair' this time?

[Ryu2]

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?

Re:Was the match 'fair' this time?

[heychris]

If I recall correctly, yes, Kramnik did have access to games that Fritz had played previously. Also, Fritz is actually a commercial program that elite chess players can buy for training. Of course, I'd love to know what hardware Fritz is running on...

CC

Re:Was the match 'fair' this time?

[dasheiff]

Kramnik was allowed to play with the Fritz Engine before hand. That's part of the reason he knew it would take a draw when it did.

comparing apples to oranges

[jacquesm]

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.

Re:comparing apples to oranges

[Anonymous Coward]

In the qualifying tournament to decide which program would fight Kramnik, they had all programs run on the same hardware. What more can you ask for?

In other words, the "apples only" match shows the advance in the state of the art in computing. The apple and orange match is just spectacular fun.

Re:comparing apples to oranges

[evilWurst]

True, all true.

But the more elegant human algorithm still demands more computational power than we can put together in a computer, so the advancement of the computer is still important. When we have the powerful enough computer, maybe then we'll be able to figure out the more elegant algorithm and implement it. Maybe we'll need ten or a hundred times that power, even...after all, the human chess skills are also partly the sum of knowledge passed down from hundreds of years of earlier chess players.

Re:comparing apples to oranges

[NBarnes]

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.

Re:comparing apples to oranges

[Rubyflame]

You are comparing apples to oranges

Dude, Fritz runs on a Compaq, not an Apple!

Hardware and OS it was running on?

[Ryu2]

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.

Computers playing with humans

[Anonymous Coward]

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?

It's not Man vs. Machine...

[Will_Malverson]

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

Re:It's not Man vs. Machine...

[euxneks]

If you put it that way, then it's nature vs. nature, as the men who make deep fritz are just the same as Kasparov and Kramnik.

Even still, it should be man vs. man. =)

Re:It's not Man vs. Machine...

[The_dev0]

Ahhh yes... Man Vs. Nature: The Road to Victory!

(Thanks Troy McClure)

Re:It's not Man vs. Machine...

[BCGlorfindel]

We're in the process of beating nature.

Oh, so mother nature needs a favor? Well, maybe she should have thought of that when she was bestting us with droughts and floods and poison monkeys.

Re:It's not Man vs. Machine...

[Anonymous Coward]

Poison monkeys? Mine taste like chicken...

Fritz runs on an eight-processor Compaq machine

[Anonymous Coward]

They have a picture on their website.

+1 Funny

[schlach]

lol =p

Hm, a draw...

[travdaddy]

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

[Tablizer]

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.

Not True

[DougJohnson]

There's a lot of speculation about this in the AI world. I'm currently in a graduate ai course that was following this reasonably closely, and we believe that given perfect play, it is quite likely that white will win every time.

The problem is that the amount of moves is extremely large, so the time when a "perfect" player comes up is probably a LONG way away.

Most games with perfect information (where each side knows the entire set of information) and without randomness are likely to have a perfect solution.... ie White can force a win in 97 moves.. or something

Soon: Kasparov vs "Junior" in Jerusalem

[eyal_bd]

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

Kramnick Limerick

[mtec]

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)

Mod the parent up!

[still_sick]

I couldn't agree with you more.

I still recall one comment posted a while ago along the lines of "If Chess is the thinking man's Checkers, surely Go is the thinking man's Chess.". ???. Ok, dude.

Folks, they're two different animals. The fact that Go contains a massively larger tree and is harder for a computer to play is mostly irrelevant in terms of human players. Both are (for the foreseeable future) too large to even consider calculating. Both trees would contain more nodes than the number of particles in the entire universe.

Imagine it this way. Take two rich people - one has 400 Billion dollars, and one has 500 billion dollars. Clearly the second one is much richer than the first, but that's in no way a slight to the less wealthy person. Both have more money than they'll ever reasonably be able to spend in a hundred years. It would take extraordinary circumstances for the second persons extra hundred billion to be felt at all.

Re:Mod the parent up!

[Anonymous Coward]

How the FUCK did you get modded down? If I had M2, I would've been using it on this! Fuckin' moderators!

(+1; Insightful) is a more appropriate moderation, or even (+1; Underrated)

Not correct

[ucblockhead]

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.

who knew

[Aleph Yin]

i for one welcome our new chess-playing overlords.

Hikaru no Go

[gedanken]

For those who aren't familiar with Go, I highly recommend you check out HnG It's an immensely popular story about an ancient Go master,his young pupil, and the world of Go.

Re:Hikaru no Go

[euxneks]

If you don't want to be stuck inside reading "just that next episode" I wouldn't recommend HnG. It's more addictive than Everquest and Astroboy!

Has anyone actually seen the games?

[Anonymous Coward]

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.

AMD sponsorship

[Anonymous Coward]

If AMD was smart, they'd sponsor a rematch next summer, and use Operton servers to run Fritz. That'd be a great way to get publicity for their new hardware, and Deep Fritz would be more powerful as a result. OK, systems running Intel would be too, but the general public would still be impressed by ads touting "Deep Fritz running on AMD Operton(TM) systems 50% faster than the Intel Pentium 4(TM) systems in last fall's match!"

re: hardware

[dollargonzo]

an 8 cpu compaq for the tournament.

Westerner alert!

[thefirelane]

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

Re:Westerner alert!

[cheezehead]

Umm...

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)

I don't follow that math. Possible moves? No, only 19x19 (max) per move, right? Possible positions? That would be 3^(19x19), right? Possible games? Harder to calculate (too lazy). I still don't see the (19x19)!

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

Yes, correct. But, I think both in Chess and Go, most moves are non-capturing. So, a non-capturing move in Go reduces the number of possibilities, where a non-capturing move in chess probably keeps the number of possibilities the same (on average). Please correct me if I'm missing something.

Re:Westerner alert!

[octalc0de]

I don't follow that math. Possible moves? No, only 19x19 (max) per move, right? Possible positions? That would be 3^(19x19), right? Possible games? Harder to calculate (too lazy). I still don't see the (19x19)!

They meant 19x19, and then a ! for emphasis, not 19x19 factorial, which would be Error- stupid kcalc!

As I see it, there's no way to be (19x19)! possibilities. The number skyrockets and there is no rationale for the !. Therefore, I reach my conclusion above.

I'll stop rambling now.

Re:Westerner alert!

[comic-not]

It is the factorial. See, the first stone has 19x19 = 361 possible places, the second has one less (because of the previous stone occupied that) so two moves has 361*360. Repeat this until the board is full and you get 361! possible plays (this assuming that no pieces are removed and no positions are unplayable). For calculating large factorials just remember that

x! = exp(sum(i=1,x)ln(i))

so the above number is about exp(1768.75) is about 1.438e768 which means that we need a quantum computer with 2552 qubits to represent all the possible states of Go. Now imagine a Beowulf cluster of those ...

OT: Go Japan Korea

[zenyu]

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.

Re:OT: Go Japan Korea

[NortWind]

...that's just to pedantic.

Perhaps you meant "that's just too pedantic."?

machines will never be our masters...

[mraymer]

...as long as people like Seanbaby are around to teach them a lesson!

Chess is a game

[Anonymous Coward]

This is dumb. People play chess to interact with other people. To test eachother's strength, powers of concentration, and to just have a good time.

The computer will have beaten us at chess when it becomes a more interesting person to be around than a human (some geeks may think this is already the case; they will discover, to their detriment, that they are wrong).

It isn't relevant anymore

[Omkar]

A chess master playing a computer is like a black belt facing Rambo. Both are lethal, but one is infinitely more skillful. The smartest person, though, is the desgner of the guns. These chess matches are only tests of efficient algorithms.

Butlerian Jihad

[Anonymous Coward]

I'll let that speak for itself :)

Chess vs. Magic....

[wowbagger]

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.

Re:Chess vs. Magic....

[MadBabbler]

While my software is still under developement the genetic algorithm and associated fitness function (the real meat of the thing) do what you propose on a limited scale pretty well. At this time my program can optimize a deck (it need not be given a starting deck, it can turn 60 forests into a pretty mean stompy deck) to handle a specific strategy. Often the GA returns a deck that is a bit better than my best shot. However, it doesn't generalize very well quite yet. Since Magic is a nondetirministic game, searching for the "optimal" stragegy is unreasonable. I can actually get very good results from a magic player without any play ahead (the branching factor for a game of magic is insane). One funny thing is that the GA will change a deck to limit the bad strategy of the player. For example (if you don't play magic good luck with this): Everyone knows that when playing against a black deck in OBC you should not cast any more creatures than you need due to Mutilate. My player at this point doesn't associate early game swamps with the possiblity of Mutilate. So the GA will create a deck that relies on fewer heavy hitters or on non-creature threats. Its really quite interesting to see what it develops. I am not quite ready to send my computer to a tourney instead of me, but I have used it extensively in deck building and testing with very good results.

Re:Chess vs. Magic....

[spress]

If we can do this I can imagine a new form of the Turing Test. Put a Magic player and a Magic playing computer together. Then see if an observer can determine who the biggest loser is.

Re:Chess vs. Magic....

[Eeeeegon]

> 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[s] (where M compose a new deck from the same N cards that answers the strategy of the opposing player.

Warning; this post is Tangental, not off-topic, since these theories can be applied to any game of skill where there's an element of chance (poker, bridge, backgammon, magic).

I would agree having a program that plays magic and is able to mutate its own deck (which i assume is what you are referring to) would be a great exercise in AI and genetic programming. But, before you can create this program, you'll need a program that's able to PLAY the game. This, of course, is no trivial task; there's only two programs that do this that I'm aware of (magiconline and the old Microprose magic game; and the Microprose game really does a half-assed job, since they hardcode every card instead of using a grammar parser on the card text).

Let's assume you have a program that lets you play a game of Magic (or a best-of-3 or 5 match) against the computer. (This CAN be done, since magiconline exists currently.) The computer will know which deck is 'better', since one of them will win the match. If the computer loses this match, it could look at the available cardpool and add / remove cards to make it a better deck, as necessary. This could be done by seeing how the deck lost, which cards won the game when they were played, and so on.

Taking this one step further, you could run the program against itself, and it will find the better deck. Then the losing deck could again be 'mutated' to make it a better competitor against that deck.

Taking THIS even further, you could create a set of random decks, and play all decks against each other, making all losing decks mutate appropriately. Repeating this a couple million times, you would eventually get a few decks (tier 1) that would beat all non-tier1 (which includes randomly-generated decks) about 95% of the time, and the tier-1 decks all win/lose in a rock-paper-scissors relationship.

You could, with this program, let it run for a few days (weeks, months, etc) and it will crank out decks that will just Beat everything else, given a cardpool of N cards.

This can be applied to bridge, poker, and to an extent, chess. (the computer will note 'If I move to A8, and I lose 90% of the time, I probably shouldn't move there anymore. Next time I play, I won't make this move.')

Also, as a side note, IF you are a fan of constructed Magic tournaments, you DO NOT want to see this program, since it will remove one of the crucial elements that bring people to tournaments in the first place: Fun. If everybody played one of the true tier-1 decks, then people wouldn't bother playing their fun decks, since they'd most likely lose. This isn't the case with chess, of course.

Re:Chess vs. Magic....

[Eeeeegon]

Hey, I have some ideas of my own, and I'm interested in this research. You should email me at requests at vt dot edu, and check out my earlier post about this, too. I've been working in C++, btw.

Go and Chess programs: its the branching factor

[MarkWatson]

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

Sigh.. must be a slashdot myth or something.

[Kjella]

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

Theoretically not much harder....

[Kjella]

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

Interesting note on Kramnik

[dh003i]

Kramnick is certainly a great chess player -- perhaps the best in the world -- but he is lacking in one important quality regarding a champion. And while former Champion Kasparov is arrogant and brass, he never fibbed on a challenge. During Kasparov's 15-year reign as chess-champion, he actively sought the most difficult challenger, and regularly played games in which he was disadvantaged.

This is quite contrary to what Kramnik has been doing, which is actively avoiding the strongest challenger -- Kasparov, and then after him Anand. Kasparov is still the highest ranked player in the world, and that margin has increased since after Kramnik took the crown from him, as Kasparov recently defeated Kramnik's Berlin Wall in 2001.

Kramnik appears to be not-so-subtly avoiding a rematch with Kramnik, quite the opposite of what Kramnik did when he was champion. He welcomed rematches from Karpov when Karpov was widely renowned as the best and most dangerous challenger.

Re:Interesting note on Kramnik

[Godwin O'Hitler]

Wait a minute, how many frigging Kramniks are there out there??

Are you kidding me?

[Anonymous Coward]

So when do you plan to have all of this implemented? What have you been developing in? Can you play against the computer? This is awesome man!

Re:Are you kidding me?

[MadBabbler]

Seems like email would be the proper place for this discussion but as you are an Anonymous Coward...

As you can well imagine this is a very large project and I am kept somewhat busy by my studies (Ph.D. AI) so it is hard to nail down a "release date".

I have been developing in python for its ease of use and the script like nature of the deck player works in nicely. Due to the very low speed of python I am planning on converting to c or c++ when I have some more of the implementation issues sorted out.

Just now you can't play against the computer as I have not written out a command set (for referencing targets and priority resolution) once I sit down and write this I plan on using the same protocol as Apprentice for playing. This will allow you to play against the computer via Apprentice as well as watch two computers battle it out. (seemed silly to write my own gui, especially since I have already written an interface to Apprentice for another piece of software).

In any case thanks for the enthusiasm.

Re:Are you kidding me?

[ChrisNowinski]

The last time you talked about this BS genetic algorithm you were 13 years old. I specifically remember you discussing the exact same thing Somewhere else. However, then you were more clear that what you did was play a deck BY HAND, change a card from that deck to another random card and play more BY HAND. Summary - you lie.

PS - There is no course of study called "AI". Hope that helps in your quest to make people think that you are older than 12.

More coverage here

[pjgeer]

http://www.therockalltimes.co.uk/2002/10/21/chess- excitement.html has more details.

Last Post!

[alpg]

FORTRAN, "the infantile disorder", by now nearly 20 years old, is hopelessly
inadequate for whatever computer application you have in mind today: it is
too clumsy, too risky, and too expensive to use.
-- Edsger W. Dijkstra, SIGPLAN Notices, Volume 17, Number 5

- this post brought to you by the Automated Last Post Generator...