Pat, I have the same questions as you do on this. I did not fully understand his proposal but would like to. I hope Leon expands on it.
comments below : On Mon, Jul 4, 2011 at 11:27 AM, Petr Baudis <[email protected]> wrote: > 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. > I think there is a semi-successful program that uses (or did use) traditional alpha/beta pruning. Was it Aya? I played with the idea of using playouts as the evaluation function of a traditional chess-like search. I did not develop the idea but I think there could be merit. One key insight here is that you do not need to always do a lot of playouts. In a traditional PVS style chess search you are trying to prove a node is above or below beta and that's all, so the playouts can stop as soon as you have some confidence one way or the other. Another insight is that modern chess programs have a pretty narrow tree, the branching factor of my very strong program Komodo is less than 2. You can still have a pretty low branching factor go program. I'm pretty much convinced that MCTS and modern chess programs have less differences that we imagine. I have not proved this but I believe the pruning can be more severe in GO when it comes to techniques like late move reductions, but on the other hand a very powerful technique in chess is null move pruning which I don't think will work well in go. There is a substitute that might however which is called "multi-cut" which is very nearly as effective in chess and might work in go. Don > > 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 >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
