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.
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.
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
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.
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.
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.
"Akara is apparently a Buddhist term meaning 10^224"
Buddhists have a term for 10^224?
"apparently". :)
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?
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.
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
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.
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.