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

[Sylvain Gelly]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070410/3a991895/attachment.htm