6 ms·

Combinatorically, Go is considered pretty much the most complex game in existence, and computer go programs have been historically weak, so this seems to be qui

Combinatorically, Go is considered pretty much the most complex game in existence, and computer go programs have been historically weak, so this seems to be quite an achievement (despite that it was against 4-stone-handicapped master passed his prime). 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.

rememberlenny 13y ago
Interesting question. As a go lover I believe it would hinder the person more than the computer. 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.
- gcp 13y ago
  Some go programs (e.g. Leela) support playing on large boards, up to 37x37. 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.
  - thinkpad20 13y ago
    Yeah, this is my thought. It seems, for example, that precisely calculating the optimal strategy would be quite tenable on a 9x9 board, because the problem space is so small. On a 19x19 board, the space is absolutely immense. It doesn't seem to make a huge difference with humans, though, because we are so adept at pattern-matching. So it seems like while a larger board would certainly make things more difficult to a human, they wouldn't really have to make many adjustments in their fundamental strategy. On the other hand, it could dramatically weaken a computer player. 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.
    - Retric 13y ago
      Solving go on a 5x5 board takes something like 2hours on a modern PC. So, optimal play for 7x7 may be within reach but 9x9 is much much harder. PS: "Center opening results in Black taking the entire board. First play on the edge results in White taking the entire board."
      - deleted 13y ago
        [deleted]
      - thinkpad20 13y ago
        Interesting, no idea! Thanks, learned something.
baddox 13y ago
> Combinatorically, Go is considered pretty much the most complex game in existence 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.
- wtallis 13y ago
  There are plenty of deterministic games more complex than Go, even turn-based ones. But Go is still a clear outlier due to its age and the simplicity of its rules - it's completely obvious how to enumerate the game tree. 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.
  - baddox 13y ago
    > 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.
    - jim-greer 13y ago
      Hmm, would you say that poker is harder if you can raise from $10 to $50.00001 instead of $50?
      - baddox 13y ago
        I don't know. I've never played poker and don't really know how it works.
        jim-greer 13y ago
IvyMike 13y ago
I remember watching a game around 15 years ago, Go professional (I forget who) vs a highly-ranked computer program. 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.
- thangalin 13y ago
  In 1997, Janice Kim (1p) gave HandTalk a 25-stone handicap: she won.[0] 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/ http://mechner.com/david/compgo/sciences/ [1] http://www.wired.com/science/discoveries/news/2006/09/71804 http://www.wired.com/science/discoveries/news/2006/09/71804 [2] http://comments.gmane.org/gmane.games.devel.go/26670 http://comments.gmane.org/gmane.games.devel.go/26670 [3] http://en.wikipedia.org/wiki/Computer_Go http://en.wikipedia.org/wiki/Computer_Go [4] http://www.amd.com/us/Documents/6000_Series_product_brief.pdf http://www.amd.com/us/Documents/6000_Series_product_brief.pd... [5] http://www.top500.org/list/2013/11/?page=5 http://www.top500.org/list/2013/11/?page=5 [6] http://phys.org/news/2013-05-nanowire-transistors-law-alive.html http://phys.org/news/2013-05-nanowire-transistors-law-alive.... [7] http://www.advancedsubstratenews.com/2014/02/fd-soi-keeps-moores-law-on-track/ http://www.advancedsubstratenews.com/2014/02/fd-soi-keeps-mo... [8] http://www.economist.com/news/21589080-golden-rule-microchips-appears-be-coming-end-no-moore http://www.economist.com/news/21589080-golden-rule-microchip...
hosh 13y ago
There's a lot of value for a human to get good at Go, regardless of the strength of computer opponents.
- MichaelGG 13y ago
  What is the value of getting good at Go?
  - CocaKoala 13y ago
    It's fun and personally rewarding.
  - hosh 13y ago
    Strategic thinking. Being able to fluidly use both linear and intuitive thought processes. Being able to apply strategic concepts learned on Go (Territory vs. Influence, life-and-death, good shapes, urgency vs. big moves, move order, etc.) 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.
Florin_Andrei 13y ago
> 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. 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.
bertil 13y ago
I really appreciate that you put that in context -- i.e. the position of that result in regards to AI history. “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.
pentapus 13y ago
> ... could we simply expand the board size a few spaces... 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.

rememberlenny 13y ago

Interesting question. As a go lover I believe it would hinder the person more than the computer. 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.

gcp 13y ago
Some go programs (e.g. Leela) support playing on large boards, up to 37x37. 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.
- thinkpad20 13y ago
  Yeah, this is my thought. It seems, for example, that precisely calculating the optimal strategy would be quite tenable on a 9x9 board, because the problem space is so small. On a 19x19 board, the space is absolutely immense. It doesn't seem to make a huge difference with humans, though, because we are so adept at pattern-matching. So it seems like while a larger board would certainly make things more difficult to a human, they wouldn't really have to make many adjustments in their fundamental strategy. On the other hand, it could dramatically weaken a computer player. 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.
  - Retric 13y ago
    Solving go on a 5x5 board takes something like 2hours on a modern PC. So, optimal play for 7x7 may be within reach but 9x9 is much much harder. PS: "Center opening results in Black taking the entire board. First play on the edge results in White taking the entire board."
    - deleted 13y ago
      [deleted]
    - thinkpad20 13y ago
      Interesting, no idea! Thanks, learned something.

baddox 13y ago

> Combinatorically, Go is considered pretty much the most complex game in existence 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.

wtallis 13y ago
There are plenty of deterministic games more complex than Go, even turn-based ones. But Go is still a clear outlier due to its age and the simplicity of its rules - it's completely obvious how to enumerate the game tree. 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.
- baddox 13y ago
  > 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.
  - jim-greer 13y ago
    Hmm, would you say that poker is harder if you can raise from $10 to $50.00001 instead of $50?
    - baddox 13y ago
      I don't know. I've never played poker and don't really know how it works.
      - jim-greer 13y ago

IvyMike 13y ago

I remember watching a game around 15 years ago, Go professional (I forget who) vs a highly-ranked computer program. 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.

thangalin 13y ago
In 1997, Janice Kim (1p) gave HandTalk a 25-stone handicap: she won.[0] 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/ http://mechner.com/david/compgo/sciences/ [1] http://www.wired.com/science/discoveries/news/2006/09/71804 http://www.wired.com/science/discoveries/news/2006/09/71804 [2] http://comments.gmane.org/gmane.games.devel.go/26670 http://comments.gmane.org/gmane.games.devel.go/26670 [3] http://en.wikipedia.org/wiki/Computer_Go http://en.wikipedia.org/wiki/Computer_Go [4] http://www.amd.com/us/Documents/6000_Series_product_brief.pdf http://www.amd.com/us/Documents/6000_Series_product_brief.pd... [5] http://www.top500.org/list/2013/11/?page=5 http://www.top500.org/list/2013/11/?page=5 [6] http://phys.org/news/2013-05-nanowire-transistors-law-alive.html http://phys.org/news/2013-05-nanowire-transistors-law-alive.... [7] http://www.advancedsubstratenews.com/2014/02/fd-soi-keeps-moores-law-on-track/ http://www.advancedsubstratenews.com/2014/02/fd-soi-keeps-mo... [8] http://www.economist.com/news/21589080-golden-rule-microchips-appears-be-coming-end-no-moore http://www.economist.com/news/21589080-golden-rule-microchip...

hosh 13y ago

There's a lot of value for a human to get good at Go, regardless of the strength of computer opponents.

MichaelGG 13y ago
What is the value of getting good at Go?
- CocaKoala 13y ago
  It's fun and personally rewarding.
- hosh 13y ago
  Strategic thinking. Being able to fluidly use both linear and intuitive thought processes. Being able to apply strategic concepts learned on Go (Territory vs. Influence, life-and-death, good shapes, urgency vs. big moves, move order, etc.) 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.

Florin_Andrei 13y ago

> 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. 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.

bertil 13y ago

I really appreciate that you put that in context -- i.e. the position of that result in regards to AI history. “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.

pentapus 13y ago

> ... could we simply expand the board size a few spaces... 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.