[Bug-gnubg] Re: Different rollouts are good

[Øystein O Johansen]

Hello list!

I'm forwarding this messages from the GammOnLine bulletin board. It is
basically a suggestion for rollouts from Kit Woolsey. I got his permission
to forward these messages.

I think we need some discussion about this. How do we want this, how to
make it available from the user interface, is it at all possible, etc.

-Øystein


-----8<-----

Re: Different rollouts are good


Posted By: Kit Woolsey <address@hidden>
Date: Saturday, 28 September 2002, at 1:07 p.m.



Search space can be important. Most of the time it won't make much
difference, but occasionally it is critical. I have seen examples of some
very simple positions where a small search space produced totally
ridiculous results from a 3-ply rollout. What happens is that the bot has a
misconception of how to play an early roll in the rollout on its 1 and 2
play analysis, and there are several similar plays available. When this
happens the bot won't see the best play as a candidate with a small search
space, and this can distort rollout results. Unfortunately, it is difficult
to predict in advance which positions are search space sensitive.


The problem with using a huge search space is that it takes time. If 15 or
so candidates are examined for every 3-ply decision, that is going to slow
the rollout up considerably, and we will then either have to cut down on
the number of samples or spend more computer time on a single rollout than
we wish.


Is there a compromise solution which will give us the accurate rollout we
desire without gobbling up a ton of computer time? Yes, there is. The key
is that rollout disasters due to search space occur only on the first
couple of rolls for the position, when the same situation will be arising
again and again. If the bot blunders six or seven rolls from the initial
position due to inadequate search space, the effect on the rollout results
will be tiny because that position isn't going to come up again. It is on
the very early part of the rollout where it is vital to make sure the bot
is looking at all the candidates properly, since that is where the greatest
effect will be because the same problem will be coming up over and over.


My suggestion is as follows: Program the bot to use a huge search space for
the first couple of rolls in the rollout, but after that have the search
space diminish as we get farther into the rollout. Once we are a half a
dozen rolls into the rollout, a super-tiny search space will be quite
adequate for our needs. It is only the first couple of rolls which require
a huge search space to avoid disastrous rollout results due to missed
candidates.


This will take a bit of reprogramming of the bots. I don't expect the
Snowie group to do this. However, the GNU group is willing to make
improvements and is responsive to our suggestions. So how about it guys.
Let's give this a try. This approach will cut down on the computer time
need for the rollouts, yet still give us the accuracy we would get with the
huge search space.


Kit

-----8<-----
Re: Different rollouts are good
Posted By: Øystein Johansen <address@hidden>
Date: Sunday, 29 September 2002, at 7:54 a.m.

In Response To: Re: Different rollouts are good (Kit Woolsey)

Implementing such feature has been on the TODO list for the GNU Backgammon
project for 17 months -- so I guess nobody is working on this right now.
Maybe someone (not me I guess), will start working of such feature just
because of your posting.

-Øystein

-----8<-----
Re: Different rollouts are good
Posted By: jim segrave <address@hidden>
Date: Sunday, 29 September 2002, at 11:41 a.m.

In Response To: Re: Different rollouts are good (Øystein Johansen)

OK - who's going to give a brief overview of how rollouts are implemented?

This sounds simple in principle - at the outermost level of a rollout set
the search space to large, on the iterations of a given rollout, increment
a level count and when it crosses the threshold, reset the search space.

I'd be willing to take it on if someone gives me a bit of insight into how
the rollout code is set up. It's a lot harder if one has to find it all
reading code.

-----8<-----
Re: Different rollouts are good
Posted By: Robert-Jan Veldhuizen (Zorba) <address@hidden>
Date: Sunday, 29 September 2002, at 12:03 p.m.

In Response To: Re: Different rollouts are good (jim segrave)

It might be worth setting up some sort of flexible system for this, so that
one can also use f.i. higher ply lookahead settings for the first n-plies
of the trials. I think it might be very useful to use 2-ply for the first
four moves f.i. and then 0-ply after that. You might gain quite a bit of
accuracy, especially with cube decisions, with much less extra time than
full 2-ply rollouts.

So, maybe split rollout settings in two: first part of trials upto n-th ply
settings, and second part n+1th ply to end settings. Maybe under an
advanced settings button so it won't scare beginners away?

-----8<-----
Re: Different rollouts are good
Posted By: Neil Kazaross <address@hidden>
Date: Sunday, 29 September 2002, at 2:34 p.m.

In Response To: Re: Different rollouts are good (Robert-Jan Veldhuizen
(Zorba))

I'd hesitate to use 0-ply for anything, but I am fortunate enough to have a
fast computer. However, and taking GNU plys now. Kit's suggestion to use
lower plys several roll down the road can often, IMHO, save computer time
and sacrifice little accuracy.

Yet there will be positions which may feature difficult checker play
decisions mostly only for one side, like containing a late hit checker when
you have a broken prime, and for those I'd want to use the higher ply for
more rolls.

Others, like holding games which will become races or be clear enough if
the leader is hit in a short number of rolls, can clearly use a lower play
after several rolls.

With this in mind, I'd suggest making the rollout module in a later GNU
build adjustable. All that needs to be done is to allow the user to be able
to specify the point at which (number of rolls into the rollout) the play
settings will be reduced and what they will be reduced to. This would seem
rather easy with GNU since there are several default rollout settings that
can be selected.

Thus, the user will be able to, depending on comp speed and time
constraints, set the change in ply to what ever point he feels adequate.

GNU is marvelous software and hopefully thru the discussions of many of us
here, it will become even better. I am still learning the current UI.

..neilkaz..

-----8<-----
Re: Different rollouts are good
Posted By: jim segrave <address@hidden>
Date: Sunday, 29 September 2002, at 1:48 p.m.

In Response To: Re: Different rollouts are good (Robert-Jan Veldhuizen
(Zorba))

Agreed, the setting of when the rollout should change parameters and what
settings it should use have to be selectable (at least until the feature
has been present for a while and people have had a chance to try the
feature and look at where it helps and where it goes horribly wrong).

But this is probably not the place for prgramming discussions. I'll take
this up on the gnubg mailing lists and see if it's something which I could
take on and add to the code.

I'd like to also add an easy way of doing rollouts of the top n moves of
every selected move of a game/match (where you could either select all the
plays, all the ones where the selected move was different from the top move
by some amount, etc.) Handy for verifying a match analysis.

-----8<-----

-------------------------------------------------------------------
The information contained in this message may be CONFIDENTIAL and is
intended for the addressee only. Any unauthorised use, dissemination of the
information or copying of this message is prohibited. If you are not the
addressee, please notify the sender immediately by return e-mail and delete
this message.
Thank you.