Computer Defeats Human At Japanese Chess 178
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."
Best use of the word "only" ever. (Score:3, Funny)
pointless comment text
Re:Best use of the word "only" ever. (Score:4, Funny)
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)
Re: (Score:2)
Re:That's nothing... (Score:5, Funny)
its totally winnable. you just have to get three in a row! (do you not even know the rules!?) :)
Re: (Score:3, Informative)
Re: (Score:2)
Re: (Score:3, Funny)
Kobayashi maru anyone?
Re:That's nothing... (Score:4, Funny)
No thank you, I already ate.
Re: (Score:2)
Gtw is a lot more fun. It allows me to take out my aggressions in ways previously unfathomable.
Nice headline (Score:4, Insightful)
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)
Re: (Score:2)
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)
Re: (Score:2)
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)
Re:Nice headline (Score:5, Funny)
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)
Re: (Score:2)
Of course, since draughts is now solved, a really high level program will never be defeated.
Re: (Score:2)
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:
The other factors you bring up are irrelevant if the number of possible games is small.
Re: (Score:2)
I would almost agree with you if we were talking about chess, where players are meaningfully distinguished by the rules of the game, but we're not talking about a game in which that happens. There are exactly six different games in rock-paper-scissors. A computer doesn't have to do anything differently to account for which player is which in analyzing this game.
Even if I agreed with you, you're missing the point. The OP stated that there are an infinite number of rock-paper-scissors games. Either one is sub
Search tree reductions (Score:2)
Technically there are 9 different games between 2 people
the outcome is different if Player A chooses Paper and Player B chooses Scissors than if Player A chooses Scissors and Player B chooses Paper
But to avoid needless computational overhead, we can consider games where player A chooses X and player B chooses Y to be equivalent to games where player A chooses Y and player B chooses X - it's the same combination of states... So if I choose paper and you choose scissors, we can just go ahead and call that a win for me.
First professional player (Score:5, Informative)
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:Nice headline (Score:4, Funny)
"The Mainichi Daily News reports that TOP WOMEN'S shogi player Ichiyo Shimizu took part in a match staged at the University of Tokyo..." Let's see it beat a man!
Yes, that'll be a different challenge entirely. There's a whole set of valid moves in Shogi that involve shifting game pieces around with one's penis - in informal matches women will sometimes use their boobs instead, but no such equivalent has yet been accepted as part of a professional tournament.
When a computer program can... (Score:3, Interesting)
... 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)
Try rereading, you missed the actual bit to be worried about...
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)
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)
Nonsense! A computer beat me at shogi decades ago.
Re:Nonsense (Score:4, Funny)
Human, my friend. Human.
Re: (Score:2)
Buddhists are geniuses (Score:2)
I never knew those Buddhists were secretly genius mathematicians with specific words for abstract numbers.
Re: (Score:3, Informative)
Not sure about large numbers, but they certainly had math geniuses
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)
First move (Score:3, Interesting)
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)
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)
Shogi - chess on steroids (Score:2)
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)
Re: (Score:2)
That's Bughouse. It's a very chaotic game because of timing issues.
Re: (Score:2)
Just about to say this. It's certainly plausible, though, that Bughouse was inspired by Shogi.
Same Old Song And Dance (Score:3, Insightful)
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)
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.
Re: (Score:2)
As long as the algorithm is rather simple and it's achieved just with more bruteforce (=more processing power), it's all rather pointless. Things get interesting, when computers analyze problems themselves, the rules, and come up with their own approach, learn and modify their strategies. This is what I'd call true AI.
I think things get interesting well before you meet that definition of "true AI". I once wrote an evolutionary algorithm to develop a Reversi/Othello AI as a final project for a graduate class. It didn't analyze problems, and it didn't analyze the rules; following the rules was built into the AI framework I developed. The framework also didn't allow the AI to think more than a fixed number of moves in advance -- I eventually settled on 3, because I didn't want it to rely on brute force computation. With
Re: (Score:2)
And when I say it developed its own approach, I mean it surprised me with its technique. Once the best AIs in the population were at the point where they trounce me consistently, I took a look at the AI's program genome to reverse-engineer its strategy. It turns out that early game, it would put a high priority on letting me take pieces. It also prioritized controlling side and corner pieces (not surprising), and ensuring it maintained flexible play options. Then, at a certain point in the game, it would change its strategy, and use its flexible position to take back the ground it gave initially. I'm no expert at Reversi, but this struck me as a very interesting and unexpected (to me) strategy.
Long story short, Reversi is dominated by the fact that there are 12 horribly bad moves (the three adjacent squares to every corner) and bad moves only tends to lead to an even more screwed position. "Ok I have to give the corner." "Ok he took the corner... now my choices are even worse." It would have been easier to see with a brute-forcing AI, but the general idea is to minimize your edge stones to limit the opponents' moves and force him into a line of play, not so much for your own flexibility. You don'
Re: (Score:2)
It doesn't quite sound like your AI would become a champ any time soon
Nor would I expect it to -- that was what evolved after about 4 days of evolution on a PC (at processor speeds from about 6 years ago). And of course it started with total random AIs -- ones that would lose to even a simple greedy algorithm. So some of that 4 days was spent just figuring out how to play well in the most rudimentary sense, much less developing anything resembling a strategy. I still have the code, because I always wanted to go back and tweak the mutation algorithm. As the code is, I feel
Re: (Score:2)
You sound surprised, but this is very basic Othello strategy. You don't seek "material advantage" except when you're confident you can get a wipeout win.
Forget Shogi - The real story is this (Score:4, Interesting)
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)
Arimaa : the next 8x8 programing challenge (Score:3, Interesting)
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:
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...
Re: (Score:2)
We can lose at Go. It's just not computers don't typically beat a person who tries and knows how to play. Here we see that this is the first time in human history that a human has managed to lose at this game. It seems like even random moves should be able to happen into defeating some human some time. Human takes dive against random algorithm.
Re: (Score:2)
Re:*yawn*. Call me when we lose at Go. (Score:5, Insightful)
soooo irritating whenever a go player brings this up.
Go only wins through brute force.
go is 19x19
shogi is 9x9
chess is 8x8
If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.
Computers playing Go on 9x9 have beaten 9th dan.
And if it was 8x8 it would be even easier.
What makes Go hard isn't anything particularly neat about the game.
Is just a boring brute force exercise.
Re: (Score:2, Troll)
The difference is that those games just don't scale.
Re: (Score:2, Insightful)
Sure they can.
The rules just need extending.
Is no different than fischer random chess dramatically increasing chess complexity for an AI.
That's the problem for me with go. It is a simplistic game that, yes, takes a lot of skill for a human. No doubt.
But the number of varying interactions is, well, limited by the tiny ruleset.
Re: (Score:3, Insightful)
Re: (Score:2)
Re: (Score:3, Insightful)
Depends on what your definition of "good" is. Efficient? Easy? Fast? etc
If you can map out every possible outcome of a game given every possible move (calculate every ply), you can play optimally. You might need multiple super computers, lots of time, etc (for now!), but if you can do that, you can pretty much guarantee optimal play. Other "smarter" methods are of course faster, more resource efficient, etc, but not as optimal if you know every possible outcome.
Re: (Score:3, Insightful)
Re: (Score:2, Interesting)
If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.
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.
What makes Go hard isn't anything particularly neat about the game.
Concepts and patterns are more important in Go. There isn't a simple piece count that dominates the evaluation.
Re: (Score:3, Informative)
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,
Re: (Score:2)
What makes Go hard isn't anything particularly neat about the game. Is just a boring brute force exercise.
I'm curious why you think Go is a brute force game. I'm not sure you've actually played the game before, maybe you're thinking of Atari Go [xmp.net]?
A real game of Go has very subtle strategies. Using brute force tactics against a strong player usually ends in a loss, which is why computers have only been able to win against Dan level players on very small boards or with very large handicaps.
Re: (Score:2)
Re:*yawn*. Call me when we lose at Go. (Score:4, Interesting)
What makes Go hard isn't anything particularly neat about the game.
Incorrect. There are many things that make go difficult for a computer to play: positional evaluation is tough. The branching factor is huge (unlike Chess and similar games, the number of available moves in a given board configuration is very large, as a stone can be played virtually anywhere on the board). Life-and-death is difficult to calculate. There are interactions between local and global play...
Go's board size is certainly a factor, yes, but if it were the only one, computers should excel at 13x13 or 9x9 games, and yet they don't.
Re: (Score:3, Interesting)
Re:*yawn*. Call me when we lose at Go. (Score:5, Interesting)
I spent a summer once working for a professor who has spent his life trying to develop an AI for Go!
In particular I was compressing read-only hash tables of end states. He was basing his approach on the work of someone who had developed AI for checkers but I think it's obvious that Go is a little bit bigger problem.
(To be specific: http://lie.math.brocku.ca/twolf/home/publications.html#3 [brocku.ca])
Re: (Score:2)
In particular I was compressing read-only hash tables of end states.
*cringe* so basically of all possible states? as in GO the game is over when both players pass twice in succession. their is no end game board layout(s).
i fee sorry for you especially if that guy was trying to go for a full 19x19..
Re: (Score:2)
It was actually Life and Death states of various numbers of pieces. Still huge, but I misrepresented the problem somewhat.
Re: (Score:3, Informative)
Re: (Score:2)
Yes. 3 dan on KGS is above what most of us can ever hope to reach at go - certainly, if someone doesn't know any go today, they wouldn't reach it until the programs have moved on.
Re: (Score:3, Insightful)
Go is a simple game.
Mind numbingly simple, in fact.
It's just a LARGE game.
Chess has actual complex rules. It is a hard game.
Mind-numbingly hard, in fact.
It's just a relatively SMALL game.
Re: (Score:2)
Chess has actual complex rules.
It really doesn't.
I mean, think about it. Six different types of pieces, most of which only have one particular type of movement they execute. Pawns and kings are the only exception - with pawns having the two-rank initial advancement, en passant, and promotion, and kings being able to castle... The rules really aren't complex. It's just the depth of possible game combinations, and the strategies that can emerge as a result, that make it a complex game..
I haven't played Go a whole lot, just enough to kn
Re: (Score:2)
Go is a simple game.
Mind numbingly simple, in fact.
The rules that create and define the game are starkly simple. The "rules" that emerge and operate during the game are mind-boggling difficult. For instance, simply knowing when a game is functionally over can be very difficult for a beginner.
Re:*yawn*. Call me when we lose at Go. (Score:5, Funny)
You're bored by the relatively fast advance of computer intelligence? Humans have for the first time in recorded history lost their title of "Best at Shogi" to computers (and orangutangs have presumably been bumped down to 3rd). That may not have any real-world significance, but in the grand scheme of things, it wasn't too long ago that computers couldn't beat us at math.
You're on a forum with a focus on computers, and you say that's boring? Jesus, what WOULD interest you? If it ran linux using a beowulf cluster? Simpsons quotes?
Well fine, I for one welcome our new shogi-playing computer overlords.
Re: (Score:2)
We are still much better at math than computers. Maybe you're confusing arithmetic with math.
Re: (Score:2)
According to TFA,
There's to worry about until it learns to phrase those final answers in the form of a question.
s = "What is " + s + "?";
Re: (Score:2)
"Akara is apparently a Buddhist term meaning 10^224"
Buddhists have a term for 10^224?
"apparently". :)