[computer-go] On expanding the UCT tree

[Magnus Persson]

Quoting Chris Fant <chrisfant at gmail.com>:

>> I have been wondering about this: If it pays off not to expand a node
>> until it has been visited 100 times, why not bite the bullet and make
>> those 100 simulations in one go? That should save a bit of time
>> traversing the tree up and down. Of course, it means that they all do
>> get a full 100 simulations, even if the first 90 show a bad result.
>> But it would make it easier to distribute the job to another thread,
>> processor, or even another computer.
>
> Without "biting the bullet", think about what the tree leaves will
> look like at the end of a series of simulations.  The number of visits
> through each will be anything from 1 to 100.  If you change the search
> to "bite the bullet", then your post-search leaves will now all have
> 100 simulations through them -- than means the leaves must be
> distributed in a very different way.  And the leaves comprise a large
> portion of the tree.  So you've completely changed the search.

Just to clarify why "biting the bullet" is problematic. UCT is 
efficient because
after a while bad variations are rarely visited. But with the "biting the
bullet"-approach the search spend 100 times more effort on all really bad
variations every time UCT decides to try that bad move one more time!

-Magnus