Coupon Go computers amp future

  

Back to forum


Thibault de Vassal    (2009-02-17)
Coupon Go, computers & future...

Two articles reported by the AGA (American Go Association) on Monte Carlo simulation, Coupon Go, Computer Go in general :

"Based on predictable advances in computing power, he rockons that a program will beat the best professional Go players on even footing within 28 years."

http://www.newscientist.com/blogs/shortsharpscience/2009/02/computers-get-go.html

"(...) To get around this obstacle, Berlekamp created a version of Go called Coupon Go, in which players have the option of either putting a stone on the board or taking a coupon. The coupons, which have different point values, showed Berlekamp what the most valuable moves were."

http://www.sciencenews.org/view/generic/id/40910/title/Coupons_help_evaluate_game_of_Go


Frightening, what do you think ? :)


Don Groves    (2009-02-18 07:18:52)
28 years

That sounds about right to me. But I still say the best way to keep the game dominated by humans is to make the goban larger. A 23x23 goban will keep the computers at bay for many more years and won't change the game all that much for humans.


Thibault de Vassal    (2009-02-18 14:45:13)
23x23

Are you sure ? Looks like it is not only a question of calculation anymore. In my opinion, if new algorithms can significantly improve computer play on 19x19, at the end it may work on any goban size. This will be the real match to follow during the next years or decades :)


Don Groves    (2009-02-19 05:33:24)
23x23

Even with Monte Carlo simulation, a statistically significant number of games must be played for the result to have high confidence. A 20x20 board size would add 39 points to the board and hence multiply the number of possible games by 2 to the 39th power. So, a simulation would have to run a much longer time to achieve a result with same confidence factor. 23x23 would multiply the possible number of games by an astronomical number. I could be wrong about this, of course, but that's the way the numbers look.


Philip Roe    (2009-02-20 14:36:04)
Complexity of Go

Don, I think the extra complexity may be more than your calculation shows.

On a Go board with 39 extra points, I think you are assuming that each extra point could be occupied by either a white stone or a black stone, giving 2 to the power 39 extra possibilities. Actually, since the extra stones need to be equally of each color, the possibilities are not quite so great. (about 2 to the power 36)

Anyway, what that calculation gives is the number of additional POSITIONS, but in calculating the number of additional GAMES the order of playing the stones must matter. On a board with n points, the number of possible games seems to be just factorial(n). In that case, going from a 19 x 19 board to a 20 x 20 board increases the number of possible games by a factor factorial(400)/factorial(361), which my computer gives as about 2 to the power 334.

I don't know enough about Go to judge how significant these numbers are, and surely various heuristics will cut them down a lot. But I thought that this observation might be worth making.


Don Groves    (2009-02-21 00:30:03)
Thanks...

... for the correction, Philip!

Another thing I wonder is if we should give each point three states: black, white, or empty. This would increase the complexity even further but I'm not certain if it is a correct thing to do.


Nadia Kaif    (2009-03-20 05:10:04)
Not the correct thing to do

Not the correct thing to do