Computer Defeats Human At Japanese Chess

Calopteryx writes "A computer has beaten a human at shogi, otherwise known as Japanese chess, for the first time. As New Scientist reports, computers have beaten humans at western chess before, but that game is relatively simple, with only about 10^123 possible games existing that can be played out. Shogi is a *bit* more complex, offering about 10^224 possible games."

Re:Nice headline

[Speare]

"First dan" or shodan is roughly the level of "starting to get serious" or freshman-professional. This goes for karate, shogi, igo (go), language, and pretty much the grading scheme in all other Japanese arts and skills including ikebana and shodo calligraphy. Westerners often think the black belt in karate is the pinnacle, when indeed your first black belt is just the beginning of a lifelong journey. Most schools go to 9-dan (kyuudan) and have an honorary 10-dan or 11-dan ranking for the highest practitioner in the world. Everything below 1-dan is just weeding out the hobbyists and dilettantes.

Re:Buddhists are geniuses

[Intron]

Not sure about large numbers, but they certainly had math geniuses
http://www.cut-the-knot.org/proofs/jap.shtml [cut-the-knot.org]

First professional player

[Chris Pimlott]

The actual accomplishment, not specifically stated until the FOURTH paragraph of the New Scientist article with the same terrible headline, is that it's the first time a computer has beaten a professional human player; in this case, Ichiyo Shimizu, the female shogi champion.

Re:Same Old Song And Dance

[SoVeryTired]

Sorry for replying to my own post, but I guess I meant any non-supercomputer. Apparently they've managed to get clusters to play at amateur Dan level over the last couple of years.

For the record, the go ranking system works out as

30 Kyu ... 1 kyu 1 dan amateur ... 5 dan amateur european ... 9 dan amateur european

5 dan amateur european is about equal to 1 dan professional, due to inconsistencies in rankings between countries.

Re:Same Old Song And Dance

[phantomfive]

Are you referring to Deep Blue? While it is true that Deep Blue was relatively weak, and Kasparov lost because of psychological errors, he later played against Fritz [wikipedia.org], which is a much more powerful chess engine, in a more fair match. Also we now have Rybka, which was created by a team of programming grandmasters, and has a rating several hundred points above the highest human (although no one has ever shelled out the cash necessary to get it to play against the world champion, it would likely win).

Re:That's nothing...

[wagnerrp]

OK. How about... tic-tac-toe cannot be won against an opponent who has simulated every possible move. There is no way to set up a trap that they cannot block.

Re:*yawn*. Call me when we lose at Go.

[jsac]

Computer programs have already beaten Go professionals at 7-stone handicap games. Mogo and Many Faces of Go have both done it for sure, and Zen is very competitive with both of them. If you go to http://gokgs.com/ [gokgs.com] and sign into the Computer Go room you'll see that Zen is ranked 3 dan and ManyFaces is ranked 2 dan, and they routinely win games off strong amateur humans. Both Zen and ManyFaces are single-box SMP programs, and the algorithm they use is a Monte Carlo algorithm so it should scale to hundreds of machines, while Mogo already runs on 600 processors...

So Go programs are getting there. Not as fast as chess, but they're still getting there.

Re:*yawn*. Call me when we lose at Go.

[JohnBailey]

The difference is that nobody would want to play a chess game on a board that size. Go grew to 19x19 by player preference, not as some artificial limit to make it hard to beat the computer.

Don't be so sure.. The most common Shogi is played on a 9x9 board with 40 pieces. True enough.. Just as the most common western chess is played with an 8x8 board and 32 pieces. That is far from the only Shogi though.

Maka-Dai-Dai Shogi has a 19x19 board, with 192 pieces.

There are plenty of variant rules that make for an even more interesting game, one of which has the piece take on the move of the piece in front of it. Others have specific rules about drops, others don't have drops..

There is a Shogi variant, Tai Shogi which has a 25X25 board, and 354 pieces. Something I've wanted to make for years, even if only as a display piece. And there may be bigger I haven't heard of.

Or at the other end of the scale, a 4X5 Micro Shogi board with 10 pieces.

http://trout.customer.netspace.net.au/ [netspace.net.au] Old VB program that works great on Linux under WINE too. So you can try lots of different variants

Chess is a complex game, but there are a huge number of variants. Most are unknown outside the few who play them.

Re:*yawn*. Call me when we lose at Go.

[Anonymous Coward]

The complexity of Go is affected by the board size FAR MORE than chess-like games. If complexity (C) could be represented purely as a function of board size (B), then for Go it would be something like C = B^2 as opposed to chess, which would be more along the lines of C = log(B).

This is because chess-like games are limited by the moves that the various pieces can make, much more so than the actual board size. Think of it this way: how much complexity is added by increasing the board size to 100 x 100 when all you can move is a pawn?

On the other hand the complexity of Go scales up astronomically even with just a 1 x 1 increase in board size because at any given point in time, a stone can be placed anywhere. (And of course the game would become very simple when the board size is reduced)