Re: [Bug-gnubg] Even, odd and half plies (WAS: New Contact Net Error Rates)

[Nis]

--On Wednesday, February 26, 2003 09:53 +1300 Joseph Heled 
<address@hidden> wrote:

> Nis wrote:
> > ALERT: Long and boring article ahead. Includes math.
>
> Not boring at all (for me).

Good to hear.

> > The 1-ply evaluation is the result of:
> >
> > 1. Finding the best move on one ply for each of the 21 possible rolls
> > 2. Averaging the resulting positions, as evaluated on 1-ply (with the
> > other player on roll)
> >
> > Thus 1-ply evaluation is the average of 21 OTHER positions with the
> > opponent on roll. However, a lot of these positions will be similar to
> > the current one (see the example in the link above)
>
> I think it is not that "they will be similar to the current one", but
> than many of the 21 positions are similar, and so the error is
> "multiplied".

Yes, this is a more precise description of what happens. My point was that 
both the original position and the 21 new ones will be in the same "family" 
- having similar board positions, only seen from different sides. The point 
is exactly this - that a "family" of positions, like "2-3 backgames with 
crunched board" actually consists of 2 sets of positions, which do not look 
similar to the neural net.

I apologize for my naive way of refering to the neural net above.

> See just above
> (http://pages.quicksilver.net.nz/pepe/ngb/index-top.html#Benchmark update
> using the large 12 point database) for an example.

Yes, very interesting indeed.


> > The basic idea is to introduce the half-ply: The average between 0 and 1
> > ply. or in general between n and (n-1) ply. This would decrease the
> > average square of the error for the kind of position - since the "true"
> > equity for the position is most likely to be somewhere between these two
> > evaluations.
>
> I will check that.

Just out of curiosity: How?

> Obviously it is a little more expensive than 1ply, but
> the hope is to get a better result than 1ply. Personally I don't think it
> will work, but it is worth a check.

If possible, could you also check the "weighted average" model for a couple 
of weights - like 2/3 and 3/4 ?

> > At the same time, however, we loose something - since hopefully the
> > evaluation at n-ply should be better on average than the one at (n-1).
> > After all, that is why we evaluate at higher plies.
> >
> > An obvious way of correcting for this fact would be to use a weighted
> > average of the n and (n-1) evaluations - with a weighing factor
> > determined by empiric research. Does anyone have a large database of
> > rolled out positions lying around - if possible including at 0 and 1-ply
> > evaluations from the current net as well.
> >
> > My idea would be to find the average of (rollout - 0-ply)/(1-ply -
> > 0-ply) and use this as the weight given to the n-ply evaluation.
> >
> > Another way to make a half-ply evaluation would be to evaluate some of
> > the rolls at 0-ply, some at 1-ply.

The above wording is rubbish. You cannot "evaluate a roll at 0-ply". Please 
change to "some of the rolls at 1-ply, some at 2-ply".

> > This can be extended to (n+1/2)-ply
> > by recursion, just like it is done with the integer plays today.

With the above in mind, the algorithm for doing (n+1/2)ply is:

If n=0: We can't do it :-(
If n=1: Partition rolls into sets R1 and R2
       Evaluate R1 at 1-ply (E1), R2 at 2-ply (E2)
       Take the average of E1 and E2, weighted if |R1| <> |R2|
If n=2: Evaluate all rolls on (n-1/2)-ply

The important point, as far as I can see, is that this is the "obious" way 
to do reduced 2-ply evaluation - but not how it is done today ...

> > When I got this idea, I thought to myself: "So THAT must be how reduced
> > evaluation works". Looking in the list archives and then into the source
> > code, it seems like this is not the case. Gnubg actually only evaluates
> > some of the rolls at each leaf in the ply-tree. This does however mean,
> > that we have an existing framework in eval.c for doing the half-ply
> > evaluation.

And it was exactly when reading this source code that I realized that my 
idea had been a little imprecise.

> > I have more ideas than the ones given here - but let me hear the
> > reactions of the rest of you before I "go wild".
>
> I want to hear them!

Estimate the difference between odd and even plies as

E1 - (E2+E0)/2

Add half of this amount to the E2 evaluation, to get this formula for E2':

3/4*E2 + 1/2*E1 - 1/4*E0

This can possibly be combined with the reduced evaluation approach:

E2'' = 3/2*E(1 2/3)-1/2*E0

or on higher plies by using more lower plies in the estimate of the 
ply-dependant difference.

--
Nis Jorgensen
Greenpeace
Amsterdam