[computer-go] The dominance of search (Suzie v. GnuGo)

[dhillismail at netscape.net]

I also find this kind of information very interesting and useful. Now I have a better feel for what kind of scaling is realistic to try for and how to measure it.
 
Putting some recent data points together, it look like giving Mogo 2 orders of magnitude more computer power would result in low dan level 19x19 play? Not the sort of thing one can pull out of a back pocket, but tantalizing.
 
I would be very interested to see equivalent scaling numbers from CrazyStone, if Remi would be so kind.
 
- Dave Hillis
 
  -----Original Message-----
From: sylvain.gelly at m4x.org
To: computer-go at computer-go.org
Sent: Tue, 10 Apr 2007 4:12 PM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


Hello,


2007/4/6, Tom Cooper <main at astrolabe.plus.com>: 
My guess is that the complexity of achieving a fixed standard of play
(eg 1 dan) using a global alpha-beta or MC search is an exponential
function of the board size. 


(...)
To some extent, this is testable today by finding how a global search
program's strength scales with board size and with thinking
time

I have experiments of MoGo's playing strength against a fixed player (Gnugo 3.7.10 level 8) on different board sizes and different thinking times.
Of course, to meet your statement we have here to assume that the level of gnugo level 8 is a constant with the board size.

The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the "same play level" (always defined as winning rate against gnugo). 
This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go).

Sylvain


-----Original Message-----
From: alvaro.begue at gmail.com
To: computer-go at computer-go.org
Sent: Wed, 11 Apr 2007 7:43 AM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)

... 
In case it matters, I think your experiment was interesting, relevant 
and well designed. Once we get dimwit to a decent level of play I'll 
probably try to produce similar data. 
 
Álvaro. 
________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070411/f30dad75/attachment.htm