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.
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.
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.
- Don
Álvaro Begué wrote:
> 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]
> <mailto:[EMAIL PROTECTED]>> wrote:
>
>
>
> Petri Pitkanen wrote:
> > 2007/12/4, Don Dailey <[EMAIL PROTECTED] <mailto:[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 <mailto:computer-go@computer-go.org>
> http://www.computer-go.org/mailman/listinfo/computer-go/
> <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/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
