[Computer-go] replacing dynamic komi with a scoring function

[Aja Huang]

Interesting. I have observed a problem in the current dynamic komi scheme 
especially when there is a big semeai/life-and-death:

Playout 1   B+0.5
Playout 2   B+0.5
Playout 3   B+0.5
Playout 4   B+0.5
Playout 5   B+0.5
Playout 6   B+0.5
Playout 7   B+0.5
Playout 8   B+0.5
Playout 9   B+0.5
Playout 10 W+8.5

B has 90% winning rate. How many points should we shift for dynamic komi?

Aja

-----原始郵件----- 
From: Zach Wegner
Sent: Monday, January 09, 2012 11:53 AM
To: computer-go at dvandva.org
Subject: Re: [Computer-go] replacing dynamic komi with a scoring function

On Mon, Jan 9, 2012 at 7:26 AM, Vlad Dumitrescu <vladdu55 at gmail.com> wrote:
> Hi,
>
> On Mon, Jan 9, 2012 at 13:17, Don Dailey <dailey.don at gmail.com> wrote:
>> Summary:
>>
>> I believe a more correct scoring function won't be based on how much you 
>> win
>> by OR how often you win but will incorporate some other more relevant
>> concept and it will be dynamic.    And it will not matter if the game is
>> a handicap game or otherwise because the scoring function will always be
>> relevant.   The goal will be to maximize your winning chances but it
>> will incorporate something more sophisticated that just counting how 
>> often
>> you win or how much you win by.
>
> I hope I may interfere with something that Don's nice description
> revealed to me. It feels rather obvious, but since nobody stated it
> explicitly, maybe it's news for at least some people here.
>
> MCTS is maximizing the chances of winning. These chances are largest
> for a minimal score difference because this allows for making some
> errors. Winning by the largest possible score has rather small chances
> to happen because every move has to be perfect.
>
> The curve describing the probability of ending the game with a certain
> score is bell-shaped and MCTS explores the area beneath it, looking
> for winning moves. With handicap, the disadvantaged side is getting
> less samples explored, making it less likely to discover the really
> good moves. Dynamic komi shifts the bell left or right in order to
> equalize the sampling on both sides, but as mentioned it isn't dynamic
> enough (the curve changes after each move) and also is actually using
> a different shape for the curve than the real "handicap curve".
>
> In theory, I think that the solution for keeping the same level of
> play with handicap as without would be to make sure that the the
> disadvantaged side gets just as many samples with or without handicap.
> That is, use more playouts when playing with handicap. In practice,
> this is probably prohibitive...
>
> I wonder if it might be possible to estimate the shape of this curve
> after each move and use that estimate to dynamically adjust the number
> of playouts. One might have to use higher precision calculations, too,
> so that the noise doesn't get too loud.
>
> Does this make any sense? Has anyone tried something like this?
>
> best regards,
> Vlad
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

This is similar to ideas I've had to solve this. Of course, I'm not a
go programmer, so it's really just idle curiosity for me when reading
this list. Perhaps an ideal scoring function is "highest median
score". You can do this in a slow/memory intensive way by storing a
histogram of final score in each node instead of wins/losses.
Wins/losses can then be computed by summing the histogram buckets
above/below the komi level. Computing the median is simply finding the
bucket where the sum crosses 50%. Other percentages could be used here
as well, though I'm not quite sure what effect this might have.

This solves the problem of getting far less than one bit of
information per playout when the win rate is very high or low, and
also supersedes dynamic komi--if you have the full histogram at any
node, you can compute the exact win rate for any arbitrary komi.

Using this in practice might be fairly difficult, and would probably
involve making the histogram "lossy" in some sense. I would be
interested if somebody here could run tests with this as a limit study
though--keep the number of nodes allocated and playouts per move
constant, and see the effect on strength.

Zach
_______________________________________________
Computer-go mailing list
Computer-go at dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go