Computer Beats Grandmaster Yoda at Go

Computer Beats Grandmaster Yoda at Go

Go

Computer program beats grandmaster Yoda in a game of Go, with a four-stone handicap.

While computers have been able to beat top human players at Checkers, Chess, Othello, Scrabble, backgammon, and poker, one game remains "the final bastion of human dominance over computers," as Alan Levinovitz puts it in a new article published in Wired. That game is Go, the Eastern version of Chess.

Programmer Rémi Coulom developed a piece of software named Crazy Stone over the course of seven years that has managed to take a significant stride in the battle of man vs. machine by defeating professional Go player Norimoto Yoda at this year's University of Electro-Commuinications Cup.

Invented over 2500 years ago in China, Go is labeled a "deterministic perfect information game," along with tic-tac-toe, chess, checkers, and Othello. But despite decades of attempts, no computer has been able to defeat a Go sage without a handicap. Even Crazy Stone's "victory" against Yoda was only accomplished thanks to a four-stone lead.

To give you an idea of why computers haven't yet cracked Go, consider the opening of a game of Chess. White has 20 possible moves, after which Black also have 20 possible moves. Once both sides have played, there are 400 possible board positions. On the other hand, at the beginning of a game of Go, Black has 361 possible moves, and white can follow with 360 different moves, resulting in 129,960 possible board positions after the first round.

After winning the match against Yoda, Coulom stated that he believes it will be another decade before a computer is able to win without a handicap, adding, "But I do not like to make predictions." Greater processing power likely isn't the solution, but rather a better understanding of the sometimes "mysterious" nature of the moves made by the highest-level players.

"You'll be looking at the board and just know," Professional Go player Michael Redmond said. "It's something subconscious, that you train through years and years of playing. I'll see a move and be sure it's the right one, but won't be able to tell you exactly how I know. I just see it."

Try teaching that to a computer.

Source: Wired

Permalink

Please tell me I'm not the only one who came into this article wondering how someone managed to get a fictional, short, green skinned, three toed alien to play Go? Please?

Pretty sure Go has nothing to do with Chess, apart from one side playing black while the other is white. Anyway, I remember reading a few years back that it'd be at least another decade before a computer would be able to beat a Master, so I guess the technology is progressing faster than expected, even if the victory was due to the handicap.

Rhykker:
That game is Go, the Eastern version of Chess.

Does this make Final Fantasy the Eastern version of Call of Duty? Because seriously, Go is at least 800 years older, and doesn't play at all the same. A better Western comparison would probably be Reversi, which is actually vaguely similar.

P.S. Thanks

Covarr:

Rhykker:
That game is Go, the Eastern version of Chess.

Does this make Final Fantasy the Eastern version of Call of Duty? Because seriously, Go is at least 800 years older, and doesn't play at all the same. A better Western comparison would probably be Reversi, which is actually vaguely similar.

P.S. Thanks

aye, the only similarity there is is in the fact that players take turns.

Guess we can finally put that stupid myth about Go being so fucking complex and awesome that nobody could ever program a computer to play it to rest.

Good riddance! I'm saving this story so I can always keep it close-by in case I run into one of those insufferable people again. You'd be surprised how much computer envy there is in the world.

1337mokro:
Guess we can finally put that stupid myth about Go being so fucking complex and awesome that nobody could ever program a computer to play it to rest.

Good riddance! I'm saving this story so I can always keep it close-by in case I run into one of those insufferable people again. You'd be surprised how much computer envy there is in the world.

ha, thank you. I see someone saying that every time they do an article about Watson or big blue beating someone at chess.

I'm fairly sure the Eastern version of chess is... chess.
https://en.wikipedia.org/wiki/Shougi

MetalheroDamien:
Please tell me I'm not the only one who came into this article wondering how someone managed to get a fictional, short, green skinned, three toed alien to play Go? Please?

You are not sir, I clicked that link for the very same reason.

OT: I'm not sure what the real story is here, the article states: "no computer has been able to defeat a Go sage without a handicap" suggesting this has been done before. So, what's new? Is "computer still can't beat Go sage without a handicap (albeit a smaller one)" newsworthy?

1337mokro:
Guess we can finally put that stupid myth about Go being so fucking complex and awesome that nobody could ever program a computer to play it to rest.

Good riddance! I'm saving this story so I can always keep it close-by in case I run into one of those insufferable people again. You'd be surprised how much computer envy there is in the world.

Fair warning, said envious people will inevitably point out that even this computer could only win with a four stone handicap. xP Be prepared, comrade!

Rhykker:
Computer Beats Grandmaster Yoda at Go

Invented over 2500 years ago in China, Go is labeled a "deterministic perfect information game," along with tic-tac-toe, chess, checkers, and Othello. But despite decades of attempts, no computer has been able to defeat a Go sage without a handicap. Even Crazy Stone's "victory" against Yoda was only accomplished thanks to a four-stone lead.

To give you an idea of why computers haven't yet cracked Go, consider the opening of a game of Chess. White has 20 possible moves, after which Black also have 20 possible moves. Once both sides have played, there are 400 possible board positions. On the other hand, at the beginning of a game of Go, Black has 361 possible moves, and white can follow with 360 different moves, resulting in 129,960 possible board positions after the first round.

After winning the match against Yoda, Coulom stated that he believes it will be another decade before a computer is able to win without a handicap, adding, "But I do not like to make predictions." Greater processing power likely isn't the solution, but rather a better understanding of the sometimes "mysterious" nature of the moves made by the highest-level players.

"You'll be looking at the board and just know," Professional Go player Michael Redmond said. "It's something subconscious, that you train through years and years of playing. I'll see a move and be sure it's the right one, but won't be able to tell you exactly how I know. I just see it."

Try teaching that to a computer.

Source: Wired

Permalink

Snipped to the relevant bits. Sounds to me like it's not a problem of /processing/ power at all, but a question of storage. High level Go players apparently have a /lot/ of information crammed into their heads, and can access it in a way that's not always conscious -- best guess as to why is because it's such a huge amount of data that even humans can't keep track of it without accessing the hard drive, to use a metaphor. To me it sounds like what needs to be improved here is RAM, along with the programming (mainly in the way of having a comprehensive set of possible moves in RAM at all times, but also having decent algorithms to pare things down to what the best move out of those possibilities are going to be, with predictions multiple moves in advance.)

I am disappointed but the lack of Star Wars jokes in the OP. Come on, the guy's title is Grandmaster Yoda for crying out load.

Oh the actual story? Pretty cool I guess, I just surprised it took this long to crack Go. Well I for one welcome our Go playing overlords.

SeventhSigil:

1337mokro:
Guess we can finally put that stupid myth about Go being so fucking complex and awesome that nobody could ever program a computer to play it to rest.

Good riddance! I'm saving this story so I can always keep it close-by in case I run into one of those insufferable people again. You'd be surprised how much computer envy there is in the world.

Fair warning, said envious people will inevitably point out that even this computer could only win with a four stone handicap. xP Be prepared, comrade!

And they would be making a good point.

Though I am sure that program will be able to beat any average Joe playing the game. Give it a couple of years before this program will be able to beat Norimoto Yoda. Alternatively they could wait until he dies of old age. Then the program would win by default.

Although people being somehow completely against the idea that computers could play this game strike me as weird.

1337mokro:
Guess we can finally put that stupid myth about Go being so fucking complex and awesome that nobody could ever program a computer to play it to rest.

One thing to bear in mind is that there's a very big difference between "can play game" and "can play game better than every single human in the entire world". Anyone claiming that Go is so complex a computer can never be programmed to play it is just an idiot, plain and simple. I have Go on my tablet, and it beats me every single time. Clearly a computer playing to a somewhat reasonable level has been possible for quite a while now. Claiming that a computer can't play Go because it can't beat a grandmaster is like claiming that robots can't walk because none can beat Usain Bolt in a sprint.

One interesting things to note though - beating a grandmaster at chess was done with a dedicated supercomputer (ranked 259 in the top500 list at the time, with a now somewhat amusing 15.4 Gflops peak). This game of Go was won with a laptop.

Well computers don't have midichlorians.

Vareoth:

Although people being somehow completely against the idea that computers could play this game strike me as weird.

But that is absurd.
It's only a matter of time before a computer can beat anyone, always.

EDIT:
Are Go games recorded, as is normal in chess?

Tengokujin:
I'm fairly sure the Eastern version of chess is... chess.
https://en.wikipedia.org/wiki/Shougi

Credit to you for linking to shogi, but the pedant in me needs to point out that while it is an analogue of chess (in a way that Go absolutely isn't, so good on you for the comparison) it's not just 'chess' by another name, it's a distinct game. Also it rocks and I wish it was more popular outside of Japan. As if the piece variation and promotion of pieces weren't enough (yup, pieces evolve like Pokemon), you get to play captured pieces as your own in lieu of moving.

Go is great, too. I've had a harder time learning and teaching Go, myself, but it was great to throw at the kids in my games club who felt they'd mastered chess.

fenrizz:

Are Go games recorded, as is normal in chess?

They can be. I remember seeing a tv channel in Japan devoted to the game, sometimes offering tips, other times walking through games that others had played. Why do you ask?

SeventhSigil:

1337mokro:
Guess we can finally put that stupid myth about Go being so fucking complex and awesome that nobody could ever program a computer to play it to rest.

Good riddance! I'm saving this story so I can always keep it close-by in case I run into one of those insufferable people again. You'd be surprised how much computer envy there is in the world.

Fair warning, said envious people will inevitably point out that even this computer could only win with a four stone handicap. xP Be prepared, comrade!

That's a different matter. What they usually say is NO COMPUTER could ever beat ANY HUMAN at go because of how complex it is. Beating a grand master is a different story and has already been done using super computers. This computer right here is just using a program that could be done on a laptop.

1337mokro:
Guess we can finally put that stupid myth about Go being so fucking complex and awesome that nobody could ever program a computer to play it to rest.

Good riddance! I'm saving this story so I can always keep it close-by in case I run into one of those insufferable people again. You'd be surprised how much computer envy there is in the world.

Yea sure... if anything, computer "worshipers" are envious. Go is FAR MORE complex than chess with more possible games than there are atoms in the universe. So yea computers will take a while before they beat the TOP Go player with NO handicap, perhaps far more than a decade (not to mention each generation of players is better at the game), which is AMAZING for the human intellect.

MetalheroDamien:
Please tell me I'm not the only one who came into this article wondering how someone managed to get a fictional, short, green skinned, three toed alien to play Go? Please?

I assumed Yoda was a nickname or even another computer. This was also wrong.

OT: Go is incredibly complex and frigging ancient. Go technology for making a computer capable of playing such a masterful game.

 

Reply to Thread

Log in or Register to Comment
Have an account? Login below:
With Facebook:Login With Facebook
or
Username:  
Password:  
  
Not registered? To sign up for an account with The Escapist:
Register With Facebook
Register With Facebook
or
Register for a free account here