On Dec 5, 2007 1:35 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > Yes, I think there is a lot to this. Searching by depth is rather > arbitrary. > > I think this basic idea is called "realization probabilities" and I > thought of doing it with the Bradley Terry model. > > It also occurred to me that if a move with low probability turns out to > be the best move at some node, what do you do about it? You could > just ignore this factor, or you could upgrade this node and research. > What do you upgrade it to? One idea is to give it the same > probability as the previous best move. Lot's of complications but > I've been meaning to get around to trying this.
This is basically identical to my plan. If you are using some null-window to check whether a move is better than the first move (expected best), you can increase the probability of the move in the re-search with full window. I have always thought of doing this only for the top part of the tree, using some other form of search as evaluation function, so one can make things quite expensive at this level without impacting overall performance much. With that in mind, I would try to remember which moves have been selected as best in any prior search, and put them all at the same probability as the best move, so when we revisit this node we don't make the mistake of thinking that those moves are unlikely. I would probably re-normalize so I still have a proper probability distribution. Quiescence is another issue. It seems to be handled arbitrarily and in > a domain specific way. In chess the classic algorithm is to consider > just captures and a "pass" move, but the pass move is considered an end > node and scored. In chess it's not called a "pass" but "stand pat." > > I would like to see a general theory of quiescence developed for all > games. Even with the idea of realization probabilities one must make a > choice of how to "end" the search gracefully with a reasonable score. > Sometimes it's simply not reasonable to stop cold. I see this as a somewhat orthogonal issue. I think Don Beal's idea of adding null-move to the quiescence search intended to be game independent, but I haven't read his paper in a long time and I don't think it would apply to go very well. I am planning on using something like UCT as an "evaluation function", so I should be able to avoid this problem (I have a whole bag of them, though). On top of all of this, it's difficult to compare scores of even depth > with odd depth scores. In some games the effect is major. I guess > the evaluation function itself is largely to blame for this, in theory > if you do a 1 ply search it should return the same exact score as a 2 > ply search but in practice if you score a position after a black move, > you will tend to get a higher score for black and the same with white. > When you have this, it's a bad idea to compare scores obtained at > an even node with a score obtained at an odd node. This would have an > impact on realization probabilities too - but no more so than any other > method. A high-quality evaluation function shouldn't suffer from this effect. If one cannot get an evaluation function without this problem, it can be fixed easily (although perhaps expensively) by saying that the termination condition requires it to be black's turn to play. Álvaro.
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
