A long time ago I thought of how to organize what to prune The Right Way (tm). I initially thought about it in the context of computer chess, but I think it is even more relevant for computer go. Instead of doing global search where you say "a node will be considered a leaf if it is n moves away from the root", you can say "a node will be considered a leaf if the probability of the game actually going through it is less than p". Now you need a model for the probability distribution of moves at any given node (maybe in the style Remi did it, maybe using prior search results...). If you are 4 moves away from the root, you can multiply the probabilities of those moves to get the probability of the branch.
If you want to recover an additive notion of "depth", so you start with a fixed quantity and you subtract something until you get to 0 and your code looks more like traditional alpha-beta, you can use -log2(probability_of_the_move), and then your depths are measured in bits (see http://en.wikipedia.org/wiki/Information_content ). I would prefer to not take logs and work with probabilities because then transposition can be dealt with correctly by adding the probabilities of the converging branches. This may or may not be important. Probably other people have thought of this, but I have never seen the idea expressed concisely before. I hope it gives people something to think about. Álvaro. On Dec 5, 2007 8:21 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > Petri Pitkanen wrote: > > 2007/12/4, Don Dailey <[EMAIL PROTECTED]>: > > > > > >> I'm not claiming this is a "good" way to proceed, I'm just trying to > refute > >> the idea that it would play worse with depth - this is clearly not > true. Of > >> course it's possible to refine this evaluation considerably - it's > pretty > >> lousy as I described it but I used it as an example because it's easy > to > >> understand and describe. > >> > >> > > But let us assume that you make that simplistic eval BUT instead of > > trying every move you would try only moves that are created by say > > GnuGo or ManyfacesOfGo. It would play a decent game with lot less > > plies. And you could safely say that considering all of the moves made > > the program weaker > > > > > If only good moves were included it would play stronger at low levels, > but it wouldn't be scalable at all unless the best move was always > included. > > > So given enough hardware, it would not improve. It would be like > SlugGo, very strong relative to it's parent program but not scalable. > > - Don > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
