RE: [Bug-gnubg] Feature Request: Gnu to use rollouts for playing

[Ian Shaw]

I've finally got around to running some tests.

Test Environment:
Intel Core2 Duo T8100 @ 2.10 GHz, 2 GB RAM Windows XP Professional GNU
Backgammon 0.90-mingw 20090914 Cache 5 MB


The test position was opening 43: 13/9 13/10 in a money game
1296 trials, cubeful evaluation, truncation at database (default
databases installed)

Thr     VR      Plies   Trials/min      Time
======================================
2       No      0       7776            00:00:09
2       Yes     0       390             00:03:30
1       No      0       4860            00:00:16
1       Yes     0       205             00:06:22
2       No      1       200             00:06:20
2       Yes     1       131             00:08:59
1       No      1       103             00:12:04
1       Yes     1       74              00:18:18
2       No      XGR     15552           00:00:05
2       Yes     XGR     1897            00:00:41

Thr = number of threads
XGR = Extreme Gammon XGRoller emulation: 0 ply rollouts truncated at 6
moves, first two cube decisions at 1-ply.
Extreme Gammon does not use VR for XGRoller, but I have repeated the
test with VR on.

It is clear that the speed hit is enormous when using VR for 0-ply
rollouts, by a factor of around 20.

At 1-ply, the speed hit is still noticeable, but only by a factor of
around 1.5.

At 5 seconds per move, the XGR setting is certainly viable for play and
analysis. And reading the BGOnline forums, there certainly seems to be a
demand for this feature. (There is no reason for gnubg to copy XG's
exact settings, if we think something else is superior. In fact, I think
it should be possible to specify a .rol file to use so that people can
choose. The default option, though, should be FAST.)

High speed is great, but the reliability of the result is also important
(though oft overlooked). I also tested the Standard Error reported after
one minute for various settings. All tests used two threads.

VR      Plies   Trials  SE
=============================
Yes     1       136             0.016
No      1       206             0.088
Yes     0       373             0.016
No      0       8836            0.002

It appears that to achieve a low SE in a given time, VR is worthwhile
for 1-ply rollouts, but for 0-ply rollouts it is better to specify a
much larger number of trials and switch off VR.


-- Ian

> -----Original Message-----
> From: Christian Anthon [mailto:address@hidden
> Sent: 21 August 2009 22:33
> To: Ian Shaw
> Cc: address@hidden
> Subject: Re: [Bug-gnubg] Feature Request: Gnu to use rollouts for 
> playing
> 
> Can you check the speed of the threaded/non-threaded rollouts (say 
> 0ply eval 6ply truncation).
> 
> Christian.
> 
> On Fri, Aug 21, 2009 at 6:54 PM, Ian
> Shaw<address@hidden> wrote:
> >
> >
> >> -----Original Message-----
> >> From: Christian Anthon [mailto:address@hidden
> >> Sent: 20 August 2009 07:28
> >> To: Ian Shaw
> >> Cc: address@hidden
> >> Subject: Re: [Bug-gnubg] Feature Request: Gnu to use rollouts for 
> >> playing
> >>
> >> Most of the code is already in place. Things to consider:
> >>
> >> a) move filter - i.e. which positions to roll out
> >
> > I would expect to be able to specify these, possibly by
> loading a .rol
> > file.
> >
> >> b) using GNURoller for plays and cubes in rollouts
> >
> > I have to think about this some more. In theory, why not? 
> However, I
> > do wonder whether it is equivalent to a normal rollout of
> certain settings.
> > As I said, I haven't considered this.
> >
> >> c) efficiency of the current mt code for fast games in
> roll outs - we
> >> lock all threads during accounting
> >
> > I'm not up with the mt. Isn't it only active in rollouts? 
> It might be
> > worth investigating whether you can multithread at the
> level of the nn
> > evaluation of a single position, which with all those SSE
> calls surely
> > takes up the most time. This would speed up play, analyses and 
> > rollouts to the same degree. You'd have to get an opinion
> from the mt
> > guru's as to whether this is feasible and wouldn't incur
> too much overhead.
> >
> >> d) variance reduction - my limited experience tells me that 
> >> variance/time is more or less independent of turning it
> on/off for 0
> >> ply rollouts
> >>
> > I've just run a simple test on a single position using a 0
> ply rollout.
> > Without VR I recorded 589 moves in 1 minute; with VR it was
> 34 moves.
> >
> > It stands to reason that VR would slow things down. With no
> VR gnubg
> > only needs to evaluate the actual roll. For VR, gnubg must evaluate 
> > the outcome all possible rolls to see how lucky the actual roll was 
> > compared to the others. This must be roughly equivalent to a 1-ply 
> > lookahead in cost.
> >
> > On a 1-ply rollout, the difference is less pronounced: 21
> trials in 1
> > minute with VR and 30 without VR. I suppose this is the effect of 
> > caching.
> >
> > -- Ian
> >
>