Chess: Man vs. Machine Debate Continues

Frederic Friedel sent in an interesting submission. It's an interview with the current world's chess champion, Vladimir Kramnik, in which they talk about the upcoming year in chess competitions, but also get into [Deep Blue] and where computer chess playing is versus several years ago, with a comparison between Deep Blue and Fritz. If you want more info, check out Chessbase for additional news.

Comments

Re:hm

[Skuto]

>From someone who has played them, how does Chess
>compare to Go or Shogi in terms of depth and
>style of play?

I've played all three and written strong programs to play two of them, but this still is a hard question.

Go is by far the deepest. The current top programs play at the level of a (rather weak) club player. It's got a huge branching factor (number of possible moves) which makes any brute or semi-brute force appraoch (what is used for chess) impossible. Most programs around right now are based on pattern recognition.

Funny thing is, the game is by far the simplest. John Tromp (the guy that wrote the 'shorter turing machine' that was posted to /. a few weeks ago) designed a complete ruleset that's only a few lines long. In practise, there are many rulesets, most of them because of tradition. This is somewhat problematic when making a program, because some rulesets are simply not complete.

Playing go is a very nice mixture of tactics and strategy. One other thing that's very nice about it is that there is a very good handicap system. The games can always be close, even against much stronger players.

Chess, well, it's mostly about tactics. Of course positional understanding matters a lot, but it's actually rather insignificant compared to the tactical part. Mostly due to continious small advances in technique and hardware, we've now got programs that are able to search about 16 half-moves (move by one side) deep. That'll nearly always take care of the tactical part. Programming strategical understanding is much harder, but a lot of progress is being made in the latter. Especially the latest generation of programs took a big step forward. We've got computers that can successfully compete with the very best humans.

Shogi I've only played once, but I've been working a lot on a chess variant that behaves like Shogi in the past. (captured pieces can be dropped) It's got almost double the branching factor of chess, and hence is somewhere halfway between go and chess. The big issue with it is that it is also very tactical, unlike go. Even though the brute force depth of current programs isn't great, they can extend mating lines very well. And mates are important in shogi/dropchess :) I would have to check for the current state of the art, but I believe the top programs are quite competitive here.

--
GCP

Re:Limits of computers?

[sphealey]

There's only a limited number of positions. You can enumerate them and then 'solve' the game in the same way we generate endgame tablebases. But we lack storage and processing power for many many many years to come.

The number of possible chess games isn't known excatly, but since even the lower estimates approach the number of atoms in the known universe we will be waiting a long time for enough processing power and memory to enumerate every possible game!

sPh