Crazy Stone computer Go program defeats Ishida Yoshio 9 dan with 4 stones
gogameguru.com
gogameguru.com
A 4 stone handicap between master's is massive. The difference between a 9d (dan) and 1d isn't actually 8 stones. With an 8 stone handicap a 1d will play a 9d off the board (provided both are profession dans not amateur). Source http://www.amazon.com/Kages-Secret-Chronicles-Handicap-Go/dp...
Generally I would say that this should put it around US 2-4d (for US Go Association, or KGS online). Maybe 2k-1d in professional amateur circles. I doubt it work warrant a 1-3p 'professional ranking'.
Also, Crazy Stone is 6d on KGS.
The normal conversion I hear is a 3d on KGS is around a 1k on Eastern Servers. Or that's my experience for people who play on KGS and eastern servers. I'm a 4k on KGS, but I know my knowledge is a bit amateur or a South Korean 4k.
For reference, you probably have to be at least 7-8 dan on KGS to be close to being professional.
Here is a rank comparison of various amateur systems:
http://senseis.xmp.net/?RankWorldwideComparison
All of those systems will be weaker than any professional system.
It's inaccurate to say that KGS is "very inflated" since it's measuring amateurs instead of professionals.
An above average amateur chess player around ELO 2000 should regularly beat the world champion with two extra bishops.
I think a more accurate analogy would be playing a game of chess without a pawn, or two, maybe, but the game is so heavily based on opening lines that some might argue if you have a pawn handicap, it shouldn't be called chess.
Also, I think some part of the difference in strength between Carlsen and I lies in his massive knowledge of the openings, which will be gone if I start the game with a two bishops handicap.
Either your rating is wrong, your are not actually playing the strongest computers, you're arguing from a too small sample size, or your definition of "crush" means "I win half of the games but those that I do win I do so convincingly".
4 stones is more like a pawn
This is completely and utterly wrong. The winning odds of having a 4 stone headstart are an order of magnitude higher than those of being up a pawn.
There is huge difference between a bishop and two pawns.
Yes. About 150 ELO - equivalent. More than being another pawn up.
At any rate I'm also a decent amateur (2350 ELO) and it's absolutely unsurprising that a (2200+) player easily beats very strong computers with bishop odds.
>>Yes. About 150 ELO - equivalent. More than being another pawn up.
You can't quantify it like that. Strong chess player is going to win with bishop odds vs any entity on the other side: 2500GM, elite GM or Houdini on 32 cores. It's just a win starting from certain level and "150ELO" doesn't convey it. On the other hand there are a lot of entities which would beat me (and even some stronger players) with 2 or 3 pawn odds.
ELO, Material Difference and Winning percentage are directly correlated.
You can't quantify it like that
Of course you can. A material advantage increases the average winning probability, and does so in a way that corresponds reasonably close to the ELO formulas. No more and no less.
Strong chess player is going to win with bishop odds vs any entity on the other side: 2500GM, elite GM or Houdini on 32 cores. It's just a win starting from certain level and "150ELO" doesn't convey it.
You have no argument to support this, and there's evidence to the contrary. (See the above study). "Strong chess player" is totally meaningless, ELO is a relative scale. A 2500 player loses just as hard against a 2850 one as a 1600 does to an 1950. That's the definition of ELO.
I'm sorry but you're just not going to beat Magnus Carlsen in a long match even if he gives you bishop odds. That's exactly what him being 2880 ELO means. You would beat Karpov (!) though.
The main point is that Bishop odds are different from 3 pawn odds. It tilts the game too much in the favor of the odds taker taking away most of the advantages(positional considerations, openings, etc) that a 2850 player enjoys over a 2350 player.
What happens playing against a strong computer given a bishop odds, is that computer will slowly succumb to the negative eval.
Instead a better strategy for a computer would be to try something very speculative like in old Tarrasch games with odds against amateurs.
That is computer should be on the lookout for eval -20.00 with perfect play by opponent(me) but possibility of 0.00 or even +10 when I make a wrong move. That is computer would have to try hard to create high volatility situations and hope that the 2350 player would misplay them.
I suppose that Magnus would try something similar(especially given his penchant for grinding).
Professional dan denotes past achievements, not playing strength. Young 1p is actually more likely to be about half a stone to a stone stronger than some older pros.
It's fairly hard to quantify how strong 9d KGS or AGA are, since there are too fews of them. But if 9d KGS is ~1 stones weaker than the pro, add on 3 more stones and Crazy Stone would be ~ 5d-6d KGS, which would be 95-98% percentile or more! That would make the computer about ~2100-2300 Elo for chess. Correct me if I'm wrong, but 10 years ago, no go program would have even come close to a mid rank kyu players.
Sorry, I know that the ranges given in the post are quite broad and might look silly, it's just hard to make any direct comparison between the system
That is, students striving to become professional.
> To put in more westernized chess terms, this would be like beating a
> 2100 Elo master without bishops.
|------------+---------+------------------------+-----------|
| Underdog | Result | Favorite | Handicap |
|------------+---------+------------------------+-----------|
| CrazyStone | defeats | Ishida Yoshio | 4 Stones |
| ?????????? | defeats | 2100 ELO Ranked Player | 2 Bishops |
|------------+---------+------------------------+-----------|Crazy Stone computer Go program.
Having said that I suspect there are problems with the two bishops and the 2100 Elo. Reading other posts, maybe it is 2 pawns or so and maybe 2600 Elo.
Ishida first: while he is certainly not top 100 in the world anymore, he is quite probably top 1000 (there are something like 1500 professionals out there, and he is probably above average for Japanese professionals, maybe above average for all the countries (see https://www.google.com/search?q=yoshio+site%3Ahttp%3A%2F%2Fi...). So he's closer to a grandmaster than a master. And in any case, other professionals have lost at four stones (see http://www.computer-go.info/h-c/index.html).
Second, regarding the handicap: I am not knowledge enough about chess to say, but it sounds high. In Go, I have beaten players who officially should give me three stones (though as you approach professional strength, it is true that players would be better at preserving that advantage and converting it into a win). I'd estimate the handicap as somewhere between 400 and 600 GoR points (which are similar in spirit to ELO ratings--http://senseis.xmp.net/?EGFRatingSystem). It is worth noting that the best European players take two to three stones from strong Asian professionals.
tournament?
http://translate.google.com/translate?hl=en&sl=ja&tl=en&u=ht...
One thing I wonder, though, if computers ever catch up to humans at Go, could we simply expand the board size a few spaces, thus dramatically increasing the problem space and setting computers back a while? I guess that would depend on what kind of techniques were being used by the computers to solve the games.
You wouldn't be able to expand the board, because then its no longer Go. There are three commonly used board sizes (9x9, 13x13, and 19x19). Other than that, it wouldn't be Go.
The computer would have an easier time playing with a larger board because its algorithmically making moves. The experience go player wouldn't have their experience behind them.
Algorithmically, there are two issues: Go programs use Monte Carlo estimation by doing semi-random playouts to determine the game theoretic value of a position. The longer the game is from its end, the more noise in the estimate, which worsens the playing strength. Secondly, the longer the game is from its end, the longer the computation of a playout takes, which reduces the number of positions that can be considered in the tree search part.
So in fact, no, moving up in board size does hurt the program substantially. Experience with programs like the above shows it hurts the computer more than the human.
As to the other point raised, there doesn't seem to be any reason why it would suddenly cease to become Go if you increase the board past 19x19. The rules of Go are independent of board size, and I'm sure it took quite a long time before the "standard sizes" of 9, 13, and 19 were fixed.
PS: "Center opening results in Black taking the entire board. First play on the edge results in White taking the entire board."
Is that considering "game" to include only traditional turn-based board games? Presumably it would be trivial to make a video game that's vastly more complex (at least in terms of tree or state space complexity) than Go. Any real-time strategy game should quality.
Things like a real-time strategy game aren't really a fair comparison, since they are designed to approximate a continuous game space-time as opposed to the discrete board and moves of Go. You can inflate the game tree complexity just by switching from single-precision to double-precision, but that doesn't really make the game any harder.
I think that absolutely makes the game significantly harder, just like playing Go on a smaller board is easier than Go on a larger board.
It's actually a similar problem to computer vision. Identifying a battle front from the current state of a war game and recognizing the tactical possibilities is similar to edge detection in a photograph and recognizing objects. Humans do that essentially with highly parallel computations and lookups by billions of neurons. Until we get billion-core CPUs and billion-ported RAM, AIs will not have the same capability.
Source: I've done some development on AI for Civilization. It sits somewhere between Go and Starcraft in AI capabilities. Civilization is turn-based like Go, but the state space explodes far more quickly like Starcraft when you have 100 units which can each make a dozen moves in 100! different orders on a turn. (In Civ, the order on which units act each turn is extremely important, where workers lay down railroads for other units to move, or where you attack a city with artillery before the ground pounders.)
The computer got a 27 stone handicap, and the pro still won by more than 361 stones. Both of those numbers are crazy.
The fact that computer programs are getting competitive is pretty awesome. 15 year ago, I wasn't sure they'd ever beat a competent human. But now I anticipate that 15 years from now (if not sooner) they'll be better than pretty much everyone.
In 2006, Crazy Stone ran on a 4 x 2-core CPU at 2.2 GHz and won gold in a tournament.[1] In 2013, the author purchased a 4 x 16-core CPU at 2.8 GHz for tournament play.[2] I would imagine that that was the hardware used for this game.
For such a slow machine the Monte Carlo method has proved devastating.[3] Consider that the the author's computer can reach 332.8 GFLOPs per 2P node[4] and the slowest supercomputer in the world's Top 500 list can reach 236,300 GFLOPs,[5] which is ~710 times faster. The Tianhe-2, for giggles, can peak at 54,902,000 GFLOPs, or ~164,970 times faster.
In theory, the Tianhe-2 could demolish a 9p, today. If Moore's Law holds out,[6][7][8] Crazy Stone will likely reach 9p in under 7 years, by virtue of hardware improvements alone. Were IBM to dedicate resources to Computer Go, a machine would be awarded a 9p rank in as few as 3 years.
[0] http://mechner.com/david/compgo/sciences/
[1] http://www.wired.com/science/discoveries/news/2006/09/71804
[2] http://comments.gmane.org/gmane.games.devel.go/26670
[3] http://en.wikipedia.org/wiki/Computer_Go
[4] http://www.amd.com/us/Documents/6000_Series_product_brief.pd...
[5] http://www.top500.org/list/2013/11/?page=5
[6] http://phys.org/news/2013-05-nanowire-transistors-law-alive....
[7] http://www.advancedsubstratenews.com/2014/02/fd-soi-keeps-mo...
[8] http://www.economist.com/news/21589080-golden-rule-microchip...
It's not out of the question that the engines could be tweaked to improve their performance more with better/more hardware, but right now, they have disappointing results.
You should post it. I suspect you misunderstood. Additional computing power doesn't help some problematic situations, but the overall strength still goes up nicely.
There are also some problems with parallel scaling not actually improving raw performance, but this is equivalent to the speed not actually going up.
Also, just to be clear, the claim that I'm considering is that around 4-6 dan KGS, you start getting markedly lower payoff in Go strength for increasing the number of playouts. The big concern seems to be capturing races.
I think the assumption holds: we won't have to wait 15 years; in ~7 years (or fewer) we will have 9p Computer Go players.
[1] https://webdocs.cs.ualberta.ca/~mmueller/publications.html
[2] https://webdocs.cs.ualberta.ca/~mmueller/ps/2013-CG-MCTS-Go-...
[3] http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_fil...
Go is a game that is abstract enough, you can easily see the same kind of patterns emerging in day-to-day life. Thus, it helps hone your ability to make decisions in face of uncertainty.
For example, a classic decision: you have a startup. Google offers an acquihire deal with you. Do you take this deal and run with the money? Do you hold out for a better acquisition deal where your product might see the light of day, or do you try to realize the potential of the company on your own? This is essentially the same decision you make when you play territorial vs. influence style, that is, realizing gains now vs. potential gains later.
Each concept in Go you learn can help you be a better Go player, but the real value is in how each of those concepts help you make decisions in your life.
You might use a computer to help you analyze things, but ultimately, the entity making the decisions for your life is you, not the computer.
Yeah. If the computer uses mostly brute force, then making the board bigger would again tilt the balance in favor of human players.
But if the program is smarter than that, well, then I don't know.
“4-stone handicap” can seem odd or artificial to non-Go players, but it is a classic way of balancing a game between players with known different levels: because of the complexity of the game, mastery expands wide, and it is rare to find a player exactly at one’s level. The gameplay changes a bit when starting at an advantage, but not significantly. For PR reasons, AI advances are usually measured with matches against star players; that handicap tradition allows AI advances to be measured more finely -- and I guess have a count-down, more appealing that the ‘not beaten yet/OK, we are done’ dichotomy of Deep Blue vs. Kasparov.
People occasionally experiment with other sizes, such as 21x21 boards. The size of the board has a strong impact on the nature of the game, though.
The obvious change is that larger boards take longer to complete, putting humans at a disadvantage if fatigue comes into play. Less obvious is that 21x21 changes the value of tradition strategies. It is generally considered equivalent to play for board-edge territory as for central influence on a 19x19 board, but on 21x21 playing for the easily-defended outer regions is too small. The value of the center means that it's more valuable to play for central influence instead.
To answer your question in short: it's possible, but expanding the board size could make the game unfamiliar and decrease the effective ranking of pros.
The new Monte Carlo search technique (used by Crazy Stone) basically blows all previous approaches out of the water. I bought the "Championship Go" app for my android phone, it uses Monte Carlo, and plays well.
For the benefit of readers who aren’t necessarily Go players, a four stone handicap means that black (the computer) was allowed to place four stones on the board before white (Ishida) made any moves. This may sound like a lot but, while it is a significant handicap, it’s not really as big as it sounds.
[1] Professionals usually play amateurs simultaneous games. That is, 1 vs. many. The quality of play improves dramatically if they are playing a single game. In this case, a single game Ishida probably wanted to win.
As a back-of-the-envelope calculation, one pawn is 1/43 of your starting material in chess if the king is included as a four-point fighting piece. Four stones in Go comes to 1/45 of your expected endgame material as half of a 19x19 board.
In contrast, Go is about capturing territory by fencing it in. Placing four stones on the board is like placing four free fenceposts; you can't really call it a tangible resource like a pawn, but it gives you more of a structure and gives you some influence over the rest of the board.
It's possible to remove resources from your opponent in go, since you can surround pieces and capture them. But it's not really an attrition thing like in chess; it's more about territory and control.
Trying to make it a numbers game and saying "four stones is 1/45 of your expected endgame material" isn't really relevant to go, because the position of the stones matters so much more than the number. If you have four more pawns than your opponent in a game of chess, that's pretty clearly an advantage; if you have four stones in a totally useless area of the board, or four stones in a really useless configuration, then they're not helpful at all.
It is very easy. The nature of the game is completely irrelevant. The question is what expectation of winning rate a 4 stone advantage gives to a Go player. For middle ranks, one stone is about 100 ELO-equivalent, or 64% winning rate. (I think it's closer at top dan ranks, would have to look up the statistics). 4 Stones is about 92% chance of winning between equal players.
The equivalent in chess is slightly more than 4 pawns advantage, or about a minor piece.
Four stones in Go sounds like a lot less than four pawns in chess, but if that's what the math says by each resulting in the same winning percentage, then the equivalency is true.
edit: Apparently kasparov gave a ~2200 guy 2 pawn handicap once, ended up winning 2.5-1.5 http://www.telegraph.co.uk/news/uknews/1317037/Kasparov-make....
You'd only break even starting from opponents at around 2400 ELO, and would start losing about 2 out of 3 games when facing a top rank grandmaster.
Being a single pawn up is usually decisive in chess.
It only gives you slighly less than a 66% chance of winning (a bit more close to the endgame).
There's no point in arguing from your personal beliefs here. You're vastly and utterly overconfident in your own ability. The definition of the rating system and a few million games of evidence are against you.
The value of each stone (as an ability to stake out territory -- sometimes called the "temperature of the board" in game theory) decreases as the game goes on. A stone in each corner is huge, probably worth about 80pts of potential territory. In the middle game, the temperature might drop from 20pts to 10pts per move. So your averaging method doesn't quite work. :)
Four stones is sort of like giving a child a knight off the board starting advantage in chess.
BTW, my older brother taught me Go when I was eight. We played fairly equally for many years, then suddenly within a one year period I was able to give him nine stones, a handicap I have now been giving him for decades. Not saying I am good, just that my brother is a bad Go player :-)
This is a major advancement for Go AI, no matter how you slice it.
I would like to try my hand at playing but I can't find anything along the lines of FICS, or even a decent-looking client for Android.
There is also online-go.com, which is web-based. It has real-time games, but the majority of games on the server are correspondance.
Resources: senseis.xmp.net (an old wiki that has lots of content, but few active contributors), and lifein19x19.com/forum, a forum dedicated to Go.
Can someone recommend a decent board and set of stones, that don't feel too shabby yet don't cost an arm and a leg?
I went to the local go club a few times before picking up my own go equipment. I wanted to get some "hands on" feel for the board and stones, to pick the brain of people who have played longer than me on a greater variety of equipment, and to find out how genuinely terrible I am at go. I live in a town where there is a decent sized Asian market area. While some of the shops had go equipment, it was subpar and way too expensive for my blood.
The set MichaelGG is talking about is the first set that I picked up for myself. It was the centerpiece of my living room for several years, and has taken all of the abuse I can throw at it (over eager new players, drunk friends, young kids, pets, the go club) in stride.
As I was still learning and teaching the game I picked up a smaller, reversible 9x9 and 13x13 board with plastic stones, and that set never sees the light of day. It's far too light and chintzy to play on now. If you're sure you want go equipment, I would take at least a bamboo board and single convex yunzi stones. The upfront cost might seem like much, but the set from YMI will last at least a generation if not longer.
Someday I'd like to make it more feature complete, such as adding accounts and multiple rooms, but since I just started a new job I won't have time for a while!
Now I just feel like I'm being punk'd.
http://www.gokgs.com/graphPage.jsp?user=crazystone
That AI is 6d on KGS.
CrazyStone isn't too far behind.
http://blog.printf.net/articles/2012/02/23/computers-are-ver...
The handicap of 4 stones seems to be very accurate. This means that crazy stones has the same level than top amateur players.
Generally, in Go, fast games are an advantage for computer. I wonder what would give a slower game.
congratulation to crazy stones.