Have read the paper just now. In the paper, the growth function (of ELO score
for single thread program) is with the shape of -T^{-0.265} where T is the
total time available in one game -- so doubling doesn't bring constant ELO
score; the loss function (due to multi-threading) is almost zero when the
number of threads is less than 64 -- so adding a thread doesn't take away
constant ELO score.
I think the facts that UCT converges to the optimum in theory and that it
converges to a non-optimum in practice maybe just imply that the growth
function is not smooth (for example, we could expect a stair-case function).
Afterall, the convergence of UCT is simply due to the finite number of game
tree nodes, so it does not necessarily imply anything about the growth
function, even for the pure UCT algorithm without any heuristics.
Bojun
>On Tue, Jun 7, 2011 at 6:59 PM, Darren Cook <[email protected]> wrote:
>
>> > The math escapes me here. I think doubling the playouts gains in the
>> > neighborhood of 70 ELO points. If adding a thread costs 10 ELO,
>> > adding more threads would stop being beneficial after about 14
>> > threads. Doubling from 7 to 14 would lose 7*10 ELO, equaling the gain
>> > of the extra playouts. After that, adding threads should actually
>> > lose ELO. Yet we see people trying to put together systems with 100s
>> > of CPUs. What am I missing?
>>
>> Richard Segal (who operates Blue Fuego) has a paper on the upper limit
>> for scaling:
>> http://www.springerlink.com/content/b8p81h40129116kl/
>> (Sorry, I couldn't find an author's download link for the paper; Richard
>> is on the Fuego list but I'm not sure he is even a lurker here.)
>>
>> I didn't fully understand the methodology, but what I did take away from
>> it (and discussions with Richard) was that though we're satisfied that
>> pure UCT eventually expands all nodes and can solve a position just like
>> minimax, this is not the case once you start adding enhancements such as
>> rave and virtual loss and *parallelizing the algorithm*.
>>
>>
>I did not read the paper either, but my guess is that scalability has not
>been proved in the presence of certain heuristics. But that may not mean
>that it's not scalable. I'm only guessing here.
>
>However, if it can be shown that Rave or something else has a limit, then
>it's still possible to construct hybrid algorithms that do the right thing.
> You do what works best given a certain amount of target CPU and memory
>resources. If some heuristic that works great at low numbers of nodes
>holds you back at a higher number of nodes, you can fix that.
>
>Don
>
>
>
>
>> Darren
>>
>>
>> --
>> Darren Cook, Software Researcher/Developer
>>
>> http://dcook.org/work/ (About me and my work)
>> http://dcook.org/blogs.html (My blogs and articles)
>> _______________________________________________
>> Computer-go mailing list
>> [email protected]
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
