Slashdot Mirror
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."
pointless comment text
a computer could have beaten me at shogi a long time ago, but it never asked to play.
"National Security is the chief cause of national insecurity." - Celine's First Law
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.
... design and write another computer program to beat a human at chess or shogi - THEN i'll be worried.
Computer Defeats Human At Japanese Chess
Nonsense! A computer beat me at shogi decades ago.
I often don't like the choices people make, but I like the fact that people make choices. That's why I'm a conservative.
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.
He who knows best knows how little he knows. - Thomas Jefferson
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.
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.
Intron: the portion of DNA which expresses nothing useful.
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.
It is no longer uncommon to be uncommon.
I saw Shogi's show in Branson, that guy plays a mean fiddle.
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.
I'm in the process of joining the AGA ... that is, I'm strategically holding off until I get more Go literature under my belt (I can bank life-and-death problems against high level players; but my initial set-up and my capture race performance is weak, so my territory boundaries are not far reaching enough and creating wider ones stretches me thin). Maybe in 2 months.
Support my political activism on Patreon.
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)
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.
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.
The difference is that those games just don't scale.
Analogies don't equal equalities, they are merely somewhat analogous.
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..
'...if only "Jumping to a Conclusion" was an event in the Olympics.'
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.
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.
>>monotonically decreases
http://en.wikipedia.org/wiki/Promotion_(chess)
I don't claim to know any thing about AI, but brute-forcing doesn't sound like a good way to solve problems, and humans obviously don't user brute force when they play so ...
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.
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.
Look up Bughouse.
It was actually Life and Death states of various numbers of pieces. Still huge, but I misrepresented the problem somewhat.
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.
It's precisely because the brute force method can be defeated just by scaling up the board size that go is a better game - humans don't use brute force to play it, which makes it a real game.
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.
Go vs. Chess. RISC vs. CISC all over again.
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.
Just about to say this. It's certainly plausible, though, that Bughouse was inspired by Shogi.
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?
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.
Where would we be if Wheel had hid her round rock in a cave instead of showing everyone how it rolls?
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.
Wake me when we develop a computer that can give me an orgasm without me having to touch myself.
Loading...
3d chess.... "Check mate, Spock."
soylentnews.org Go there to enjoy the people!
You misunderstand what GP was saying..."brute force" in this case means computationally being able to examine every possible path for the game to take, not the play strategy.
There's to worry about until it learns to phrase those final answers in the form of a question.
Let me know when a computer-enhanced corgi wins.
So Go programs are getting there. Not as fast as chess, but they're still getting there.
"The urge to fly from modern systems, instead of moving through them to even greater, fairer things is, I think, an indi
Spoken like someone who doesn't get Go at all.
See Arimaa , a new game 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.
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/ 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.
It is difficult to get a man to understand something when his job depends on not understanding it.
"Akara is apparently a Buddhist term meaning 10^224"
Buddhists have a term for 10^224?
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 know I'm really not very good at it. :)
Bow-ties are cool.
Why is this modded troll? That's exactly what the grandparent post says.
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.
Bow-ties are cool.
We don't know how our minds work well enough to say that we don't use brute force. Obviously, consciously, we're not thinking about it that way, but who knows what kind of processing the brain does to produce those conscious thoughts? When you get a knack of intuition like "ah that move would win" - is that just a brute force algorithm in the subconscious signalling termination with a result?
Jane plays Shogi with pequeninos, now?
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.
xkcd is not in the sudoers file. This incident will be reported.
I played Shogi against a computer and lost in 1996. Sure I didn't know the rules. Still it happened.
A Good Troll is better than a Bad Human.
We are still much better at math than computers. Maybe you're confusing arithmetic with math.
Le français vous intéresse?
Really! I'd thought that chess originated in India and spread to Persia and the Middle East, where it evolved. But hey... whatever.
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.
"A computer has beaten a human at shogi, otherwise known as Japanese chess, for the first time."
I would insert the word "expert" before human. Because I am pretty sure that just about any computer program could beat me at shogi, since I have no idea how to play. Just printing "I won. You loose." would convince me to forfeit thereby losing the game.
how about 36x36 Shogi? Already exists:
http://en.wikipedia.org/wiki/Taikyoku_shogi
Dude's about to lose a rook in that picture.
I wish someone would write a good algorithm for tori shogi, which is played on a 7x7 board. I routinely beat my computer at tori, but it's well known that the program is weak.
She obviously doesn't realise how cold, calculating and ruthless humans can be...
you had me at #!
Nice programming exercise.
you had me at #!
You can be pretty sure we don't brute force in our brain the same way computers does. We tick way too slow.
/J - to know recursion you must first know recursion
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)
If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.
Than their regular 8x8 or 9x9 counterpart? Yes. Than Go? Not even close.
The fact that you can place a piece anywhere, as opposed to along rigidly-defined paths has quite a bit to do with the greater complexity of Go. Even if you bumped Chess or Shogi up to a 19x19 and made them somehow work in that space, Go would still be much more complex to solve due to the fact that there would be vastly more possible moves from any given state.
And they are ALL brute force exercises. That's all they are, really. What makes Go interesting is that it's a much much harder brute force exercise than the others, and not just because of the larger board size (though that is certainly a major contributing factor). That you find it boring is just evidence of the fact that you haven't considered it enough.
Your comment is misleading. While Go rules are quite simple, mastering the game is not easier than mastering chess at all.
its absolutely not "just a large game"
Try to play good players at www.gokgs.com
The argument is that the computer didn't beat you, you beat yourself while playing a computer.
Learn to love Alaska
Don't wait - find a tournament near you soon and sign up so you can go to it. It's fun, and you get serious games under your belt with people whose styles you don't know (if your only face-to-face games so far have been among friends, this is a neat change.)
You can play online, but nothing beats the cold stones in your hand sitting across the board from a well-matched opponent!
If you're in the D.C. area (or driving distance) the next NOVA tournament (the Pumpkin Classic) is at George Mason University in Arlington on the 30th. They like people to pre-register on their website (it's linked to from the tournament list on http://usgo.org )
Go only wins through brute force.
Go doesn't "win" anything. You play Go to win against someone else. In case you didn't know, Go is a game, with extremely simple rules, played between two players. As it happens, Go also pre-dates Chess by about 1000 years.
Sarcasm aside, to somehow suggest there is a "competition" between Go and Chess to the more "complex" is just absurd. I'm pretty sure our ancestors did not have this in mind when they invented Go and Chess.
go is 19x19 shogi is 9x9 chess is 8x8
Simply comparing board sizes between different games is pretty meaningless. The branching factor is governed as much by the board size as the actual rules of the game.
If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.
And it would be vastly harder for the human as well. Assuming you could somehow meaningfully extend the complexed rules of Chess (as compared to rules of Go) to a 19x19 board, it could well be that the resulting mess would be so complex that no humans would be interested in playing. If it's not interesting to humans, than there's no point in writing computer programs to solve it.
Computers playing Go on 9x9 have beaten 9th dan.
In July of 2010, and the human isn't even near top 10 in the world. Also, 9x9 Go isn't Go, it's just that, 9x9 Go. These are two vastly different games. As an analogy, 9x9 Go is like fighting a single battle, where most of decisions are tactical. The normal Go is like fighting a war, with many battles going on at the same time. There are both strategical and tactical decisions to make.
And if it was 8x8 it would be even easier.
And if it was 7x7 Chess with no rooks Deep Blue would have crushed Kasparov.
What makes Go hard isn't anything particularly neat about the game.
What an arrogant statement coming from someone who apparently knows nothing about the game at all.
There has been considerably more research into Chess AI than Go AI, which may be one important contributing factor to the current relative weak status of Go AI. This may change in the coming years as more and more attention are being directed towards tackling Go. However, what we do know at this point is that writing competent AI for Go is very different from that of Chess, both in terms of the search strategy and the evaluation function, and very little of the advancements in Chess AI can be applied directly to Go. To me at least, the fact that Go is such a challenging game made out of such simple rules, is quite fascinating, and certainly qualifies as "neat".
Would you insist on using brute force to solve x=1? Yeah, you could check every possible integer for equality with 1, just to make sure, but a deeper understanding of the problem dramatically reduces the necessary time, while providing as correct answer as the "lazy way".
That's true, the brain's clock works in like, Hz's. However, it's *massively* parallel, and has a feature of gradually reprogramming its hardware to better fit the task - these features give it an overwhelming edge over any existing computer (in a selection of tasks, naturally).
Still I doubt that something as smart as our brain would be using something as dumb as BF.
If a game like shogi or chess was extended to 19x19 it would be vastly harder for a computer.
To illustrate your point...
Sufficiently motivated players could still win in such a setting. Or so I hear.
Ah, arrogance and stupidity, all in the same package. How efficient of you. -- Londo Mollari
Way to waste one's life.
Exactly. Go has more in common with Conway's Game of Life than it does with chess.
Your brain is not a computer.
Another comment that shows no understanding in current AI and Go.
In games like Chess and Shogi piece evaluation is relatively easy as each piece has its specific movement (hence power).
In Go you do not have such thing. Position evaluation is extremely tough. This turn a position may be useless, but next turn it may immediately become critical.
This has nothing to do with board size. It has to do with the nature of the game. 9x9 Go is easy to excel for computer because there is typically no position evaluation (right away in the game you are in combat).
13 x 13 Go, computer still sucks.
I have no doubt that one day we have super computer that can brute force the Go game, but it won't happen any time soon. If we can use heuristics in computer so we don't completely bruce force for computer to be decent at Go, we have a major break through in AI.
Oh, ok then let's just make a bigger board and...
Oh. So yeah, they don't scale but similar games can be formulated. I wasn't disputing this.
Analogies don't equal equalities, they are merely somewhat analogous.