[computer-go] Depth dependent evaluation effects on monte carlo searches

[Jason House]

Darren Cook wrote:
> Hi Jason,
> In UCT the monte carlo searches (I find it clearer to call them "the
> playouts") are always run to the end of the game. So they always
> accurately (well, as accurate as a random playout can be!) take sente in
> account. Therefore my understanding is that it does not matter whether
> they start at an even or odd ply in the UCT part of the tree.
>
> Darren
>   

Let's take a basic example of a leaf node in an MC search tree that 
hasn't been expanded, but has 4 children.  Let's say that random 
simulation through the children have winning percentages of {46%, 51%, 
47%, 48%}.  Assuming a uniform simulation policy, the winning percentage 
would be the average of the four, or 48%... but when that node gets 
expanded, it'll start discovering the winning percentages of the 
children nodes.  Now when we look at the node that used to be our leaf 
node and ask what it's winning percentage would be, we come to a 
different conclusion...  The winning percentage is either 46% or 51% 
depending on if the color to move.

In this example, the difference between the 0-ply and the 1-play is 3% 
(51%-48%) or 2% (48%-46%) depending on what the color to move was.  Does 
that help?


>
> Jason House wrote:
>   
>> For simplicities sake, let's say I do a pure 0-ply and 1-ply monte carlo
>> search.  If the color to move is my color, I'd expect the 0-ply search to
>> give me a more conservative winning percentage than the 1-ply search (since
>> I'd pick the best child rather than average the children together).
>> Similarly, if the color to move is the enemy color, I'd expect the 0-ply
>> results to be optimistic relative to the 1-ply results.
>>
>>     
>>> From what I understand of how everyone does UCT, the depth of leaves
>>> are not the same and percentages are compared anyway. ...
>>>       
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>