Hi!
On Mon, Jul 04, 2011 at 04:27:00PM +0200, Leon Matoh wrote:
> Go is not much different from chess - 0.1
>
> For long time it was impossible to correctly evaluate move values in the
> game of go.
>
> With applied statistics there is an elegant solution. With help of
> statistics and semi random play first you normalize the winrates in [0.2,08]
> with properly sized window that possible outcomes fall into, and next move
> values are easily calculated from winrates.
>
> When searching from terminal node (as in game tree) created with
> known techniques you can estimate point value, standard deviation, and
> other ...
>
> Basic idea is to create a window a little larger of possible
> outcomes [a,b] such that a < result < b. For each possible
> moves (you can use expert knowledge), you semi-randomly play enough
> games to be statistically significant. In each playout when you
> reach final state you count the game and get result r. Pick a random x
> number between a and b. If x>r it is a win, if r<x it is a loss. If play-out
> is done with confidence (better engine winrate will be close to best play
> (random engine gives average). With proper windows size winrate is always in
> [0.2,0.8] or similar, as in the middle there is smallest noise.
AIUI from previous discussion, you pick x randomly for each tree node
separately? Or for each random simulation? How do you determine the a,b
window? How do you determine statistical significance and in which
context? (Statistical significance for "better/worse than some
sibling"? In that case you )
It would be helpful if you could write some pseudo-code of your
algorithm as a whole.
> From window and winrate you can calculate expected best play from
> that node. From standard deviation you can see if results vary. From
> statistics about removable/unremovable string you can see strenght of
> strings. In that light you decide either to explore further or apply result
> upstrem.
>
> Creating the tree is matter either of brute force or use of
> expert knowledge. Depth is limited with memory and speed. Prunning
> the tree and adding nodes are well known techniques from chess.
Hmm, so essentially you are proposing a new evaluation function for
traditionally expanded/pruned minimax trees, do I understand it right?
Before starting work on Pachi, I was trying to pick and fix various
positions and fights GNUGo was getting wrong. In most of the cases, the
problem was not really the evaluation function, but wrong pruning
decisions in its tactical search. Exploring efficiently, yet not
overpruning, seems like very hard problem in Go to me, something MCTS
where is exceptionally effective.
So just sweeping away the problem by claiming that these are "well
known techniques from chess" is not very satisfactory for me. I have no
experience with chess programming, but others here do and I assume they
tried to apply these techniques already.
So I have two questions. Why do you think chess pruning techniques
will be effective for your tree search approach if attempts to apply
them in the past failed? And why do you think your tree search approach
will be more effective than RAVE MCTS?
Kind regards,
--
Petr "Pasky" Baudis
UNIX is user friendly, it's just picky about who its friends are.
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
