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?

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"

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

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

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

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

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

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

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

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

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?

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

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?

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.

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.

Fritz runs on an eight-processor Compaq machine

[Anonymous Coward]

They have a picture on their website.

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)

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

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