typodupeerror

## Computer Defeats Human At Japanese Chess178

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."
This discussion has been archived. No new comments can be posted.

## Computer Defeats Human At Japanese Chess

• #### Best use of the word "only" ever. (Score:3, Funny)

on Tuesday October 12, 2010 @11:58AM (#33871052)

pointless comment text

• #### Re:Best use of the word "only" ever. (Score:4, Funny)

on Tuesday October 12, 2010 @05:40PM (#33876550) Journal

It is only a "bit" more complex than western chess; exactly one bit more complex. The exponent 123 can be stored in 7 bits. The exponent 224 requires 8, a full byte.

See what I did there? -puffs chest out proudly-

• #### That's nothing... (Score:3, Funny)

on Tuesday October 12, 2010 @11:59AM (#33871086)
a computer could have beaten me at shogi a long time ago, but it never asked to play.
• #### Nice headline (Score:4, Insightful)

on Tuesday October 12, 2010 @12:01PM (#33871114)

First time "a computer" has beaten "a human", eh?

I'm sure they mean: first time a computer has beaten a 1st dan (or whatever shogi ranks are called) grandmaster in an offical tournament setting...

Also, I don't think the theoretical number of games is very relevant. Paper-scissor-rocks has an infinite amount of possible games, ie 1 draw followed by a win, 2 draws ... inf draws. Much more relevant would be branching factor, difficulty of estimating positional strength, horizon problems, long term dependencies etc.

• #### Re: (Score:3, Funny)

Yeah, I'm pretty sure a computer could beat me at shogi all day long, seeing as I have no idea how it's played.
• #### Re: (Score:2)

Chess can also be considered to have an infinite number of games where both players simply move a single piece back and forth forever. But it would seem pointless to track those.
• #### Re: (Score:2)

Actually no you can't, 50 move rule. But yes, there are far more possible games than there are possible positions.

• #### Re: (Score:2)

Even more-so than compression algorithms, moving pieces like this adds no complexity to the game outcomes at all.
• #### Re: (Score:2)

Chess can also be considered to have an infinite number of games where both players simply move a single piece back and forth forever. But it would seem pointless to track those.

Wrong, because chess has a rule that if you have the same position three times, the game is a draw.

• #### Re:Nice headline (Score:5, Informative)

on Tuesday October 12, 2010 @12:08PM (#33871254) Homepage Journal
"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:Nice headline (Score:5, Funny)

on Tuesday October 12, 2010 @12:23PM (#33871494)

11-dan ranking for the highest practitioner in the world.

+11 Funny

• #### Re: (Score:2)

Black belt in calligraphy, that would be something to have.

• #### Re:Nice headline (Score:5, Interesting)

on Tuesday October 12, 2010 @12:13PM (#33871348) Homepage Journal
Actually, I used to routinely thrash the top level in typical Checkers programs. Shogi is interesting because if you can hold your own enough to start capturing pieces, you can become a huge nuisance. Every piece you capture can be played back on the board on your side on any turn; this makes Shogi a little complicated for a computer, since suddenly you have no checkmate on the board but there's 10 ways I can play a Horse or Rook and trap you in a checkmate.
• #### Re: (Score:2)

Of course, since draughts is now solved, a really high level program will never be defeated.

• #### Re: (Score:2)

Of course; but Shogi isn't, and it suffers the same problem as any unsolved program: determining the absolute best move is hard. Shogi only becomes more complex during play, not simpler.
• #### Re: (Score:2)

Draughts has only been solved on the 8x8 board, and the best programmes for the 10x10 version caught up with the top humans a few years back.

It's interesting to speculate about how the advancement of playing software might hint at how tactics and strategy are balanced for the various board games. I mean, a chess computer has no concept of a plan, and even Kasparov or Topalov or whoever can only calculate a handful of positions a second. Of course, the most interesting part of that problem is how to pose the

• #### Re: (Score:2)

Checkers, aka Anglo-American Draughts, is solved. The Draughts played in continental Europe is not solved.

• #### Re: (Score:2)

There are exactly 6 different rock-paper-scissors games:

1. Rock-Rock
2. Rock-Paper
3. Rock-Scissors
4. Paper-Paper
5. Paper-Scissors
6. Scissors-Scissors

The other factors you bring up are irrelevant if the number of possible games is small.

• #### First professional player (Score:5, Informative)

on Tuesday October 12, 2010 @01:04PM (#33872418)

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.

• #### When a computer program can... (Score:3, Interesting)

on Tuesday October 12, 2010 @12:01PM (#33871130) Homepage

... design and write another computer program to beat a human at chess or shogi - THEN i'll be worried.

• #### Re: (Score:2)

Well get worried then, because combining two programs is pretty easy.

• #### Re: (Score:2)

... design and build another human being which can design and write another computer program which can design and build another human being which can post on Slashdot - THEN I'll be worried.

• #### Re: (Score:2)

... write a critical part of its message somewhere other than the message body, so that people misread the message - THEN I'll be... rather unsurprised, really. It's easy to do. The question is, why would you do it?

• #### Nonsense (Score:2)

Computer Defeats Human At Japanese Chess

Nonsense! A computer beat me at shogi decades ago.
• #### Re:Nonsense (Score:4, Funny)

on Tuesday October 12, 2010 @12:05PM (#33871200)
Computer Defeats Human At Japanese Chess

Human, my friend. Human.
• #### Re: (Score:2)

Are you implying parent is a furry?
• #### Buddhists are geniuses (Score:2)

FTA: "Akara is apparently a Buddhist term meaning 10^224"

I never knew those Buddhists were secretly genius mathematicians with specific words for abstract numbers.
• #### Re: (Score:3, Informative)

http://www.cut-the-knot.org/proofs/jap.shtml [cut-the-knot.org]

• #### Re: (Score:2)

Since they once represented the intellectual elite of the world's first great civilisations, that alone should tell you that they might have. If you had studied buddhist teachings at all, you might have discovered that, far from being fanciful accounts of Noahs and arks, much of their teachings are cold hard logic (including a lot of math), which is easily comparable to "modern" western science.

• #### The first time... (Score:2)

<nitpick>He won the first time *against a skilled opponent*. The prototype has probably won against a lot of humans during the development process. I guess I would lose frequently against any random algorithm, as I don't even know the rules of shogi; winning agains some arbitrary human would not be anthing newsworthy.</nitpick>
• #### First move (Score:3, Interesting)

on Tuesday October 12, 2010 @12:06PM (#33871232)

Chess has a natural limit since the number of pieces monotonically decreases during the game. Shogi lets you drop (add) pieces that you capture, so a game can go on for a long time.

• #### Pawn promotion? (Score:2)

>>monotonically decreases

http://en.wikipedia.org/wiki/Promotion_(chess) [wikipedia.org]

• #### Re: (Score:2)

Nevermind -- should have thought about it for 10 seconds before posting...
• #### Re: (Score:2)

Which, if the criteria is just "Number of pieces" still qualifies as monotonically decreasing.

• #### Re: (Score:2)

Chess has a natural limit since the number of pieces monotonically decreases during the game. Shogi lets you drop (add) pieces that you capture, so a game can go on for a long time.

Um no.... The thing that makes computers so good at chess is that it's a game of perfect information. Shogi the same it just has more permutations, specifically because of the drop rule. But there are still only a finite number of plays, Therefore using a lookup table is possible and I would argue even practical.

http://www.en.wikipedia.com/wiki/game_theory [wikipedia.com]

• #### Re: (Score:2)

Nope, your lookup table would probably have to be bigger than the universe. Computers may win at Shogi, but not that way.

• #### Shogi (Score:3, Funny)

on Tuesday October 12, 2010 @12:08PM (#33871262)
I saw Shogi's show in Branson, that guy plays a mean fiddle.
• #### Shogi - chess on steroids (Score:2)

1. Kill enemy soldier
2. Turn him into a zombie with a necromancy spell
3. Train said zombie in air-borne assault tactics
4. HALO drop him behind enemy lines
5. ???
6. PROFIT!!!

AFAIK, Shogi is the only game I know that allows you to do this.
• #### Re: (Score:2)

chess is politics, not warfare .

• #### Re: (Score:2)

Swap chess, a minor variant of chess, has a similar concept. Two pairs of players face off. On each team is one player with white pieces, and one with black pieces. Any piece they capture, they hand to their team mate, who can place it on the board at any time in lieu of a move.
• #### Re: (Score:2)

That's Bughouse. It's a very chaotic game because of timing issues.

• #### Same Old Song And Dance (Score:3, Insightful)

on Tuesday October 12, 2010 @12:16PM (#33871380)

Ugh. What's with perpetuating this nonsense? A computer did not beat the top ranked Western chess player. Rather, a group of people _reprogrammed the computer after each match_ to beat the top ranked Western chess player.

TFA, it is annoyingly vague on an important point: What is the rank of the Japanese player that lost?

And as others have pointed out, let see a computer take down a top ranked (10th Dan) player at Go. The best a machine has done (I think) is winning against a 5th Dan.

• #### Re: (Score:2)

And as others have pointed out, let see a computer take down a top ranked (10th Dan) player at Go. The best a machine has done (I think) is winning against a 5th Dan.

I think that would be a 5 dan amateur, not a 5 dan pro, which is a lot stronger. But to me that's still impressive enough that nothing would surprise me now.

• #### Re: (Score:2)

Ugh. What's with perpetuating this nonsense? A computer did not beat the top ranked Western chess player. Rather, a group of people _reprogrammed the computer after each match_ to beat the top ranked Western chess player.

TFA, it is annoyingly vague on an important point: What is the rank of the Japanese player that lost?

And as others have pointed out, let see a computer take down a top ranked (10th Dan) player at Go. The best a machine has done (I think) is winning against a 5th Dan.

That's only on a 9x9 board. A competent low Kyu or Dan player could crush any computer on a 19x19 board.

For people who don't play go: the difference between 9x9 and 19x19 is a bit like the difference between ping-pong and tennis.

• #### Re: (Score:3, Informative)

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: (Score:2)

I think that's exactly the GP's point.

Decades ago many people thought a computer could never beat a human at chess. Many millions of dollars have been spent on specialized hardware, computer-human tournaments, and AI research, we now have computers that can beat the best human players some of the time. Chess is admittedly, in turns of branching and possible moves, much simpler than Go. Far more able to be bruteforced, or to have lookup tables of millions of board positions.

But...

Isn't it obvious that the sa

• #### Re: (Score:2)

You're still underestimating computers. Look up Zen19 on KGS - it runs on an ordinary SMP system, hardly a supercomputer. It's stable at 3 dan.

• #### Re:Same Old Song And Dance (Score:5, Informative)

on Tuesday October 12, 2010 @01:40PM (#33873120) Journal
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: (Score:2)

Yes, a computer did beat the top ranked Western Chess player. At worst, deep blue did not beat the top ranked chess player.

Programs running on a regular notebook computer can these days beat grandmasters even giving pawn odds.

• #### Forget Shogi - The real story is this (Score:4, Interesting)

on Tuesday October 12, 2010 @12:42PM (#33871926)

If you bother to read the article:

"IBM say they have improved artificial intelligence enough that Watson will be able to challenge Jeopardy champions, and they'll put their boast to the test soon, says The New York Times. "

Do you realize what this means? Ken Jennings versus robots. They could make an entire new show out of this and I'd watch it religiously.

• #### Re: (Score:2)

Do you realize what this means? Ken Jennings versus robots. They could make an entire new show out of this and I'd watch it religiously.

I'd watch it, too. Especially if the competition had nothing to do with trivia.

• #### *Yawn* (Score:2)

Wake me when we develop a computer that can give me an orgasm without me having to touch myself.
• #### Arimaa : the next 8x8 programing challenge (Score:3, Interesting)

<slashdot@NosPam.advid.net> on Tuesday October 12, 2010 @03:22PM (#33874734) Journal

See Arimaa [arimaa.com], a new game [wikipedia.org] with a board and set similar to Chess *but* with specific rules made to be difficult for a computer to play, and easy for a child.

How many options do you have when it's your turn to play with chess ? The average branching factor in a game of Chess is about 35, whereas in Arimaa it is about 17281 !
This is why a computer which can search to a depth of eight turns for each player in chess, can only search about three turns deep for each player in Arimaa...

This game is the new challenge for IA, easy for a child, difficult for a computer. A average human player wins against best programs.

• #### Re: (Score:3, Interesting)

This game is the new challenge for IA, easy for a child, difficult for a computer.

I looked at Arimaa a long time ago and keep tabs on it's progress occasionally. It's still very much a niche game after all these years. The two biggest problems with it:

• I don't find it much fun. I can't be in the minority considering the number of people who try out Arimaa and don't stick with it.
• There was never a need for a new, artificial challenge. Go was already the next challenge, recognized by the AI community for decades. It's a mainstream game that's already hard for computers.

A average human player wins against best programs.

Actually, the top pro

• #### Western Chess? (Score:2)

Really! I'd thought that chess originated in India and spread to Persia and the Middle East, where it evolved [wikipedia.org]. But hey... whatever.

• #### "Friendly competition"??? (Score:2)

She obviously doesn't realise how cold, calculating and ruthless humans can be...

#### Related LinksTop of the: day, week, month.

In seeking the unattainable, simplicity only gets in the way. -- Epigrams in Programming, ACM SIGPLAN Sept. 1982

Working...