Re: Réf?. : Re: [Bug-gnubg] Tutor/Analysis

[Jim Segrave]

On Fri 03 Oct 2003 (13:44 +0200), Nardy Pillards wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> On 3 Oct 2003 at 11:26, Joern Thyssen wrote:
> 
> > On Fri, Oct 03, 2003 at 10:58:36AM +0000, Joern Thyssen wrote
> > > > I don't mind waiting a bit during each move, but waiting 10mins at
> > > > the end of a match really kills me.
> > > 
> > > It has been on the TODO list for quite a while. Bringing it forward
> > > again doesn't help :-)
> > 
> > BTW, my post should be read with a smile :-) Sorry, if it seemed to
> > harsh.
> > 
> > Seeing the same request for the gazillion'th time didn't help my mood
> > on a boring rainy day where my boss is having me write boring
> > documentation :-)
> > 
> > Jørn
> 
> Not to add salt to the wound:
> 
> If (_big_ IF) there would be some kind of Tutor mode for Pl0 (gnubg),
> it would be possible to store the analysis?
> In stead of Tutor Mode, this gnubg 'Tutor' could be called:
> "Keep You Hands Of Every Possible Interfering Function Unless This 
> Match/Game Is Completed"
> 
> Or ... only save the analysis if 100% is done? Then consider it as 
> 'Analyse Move'. Otherwise discard.
> 
> Or...
> just scold at me?
> 
> :-)

There's been lots of discussion of the problem - the gnubg mailing
list is full of such things and Joern even had a sort of during play
analysis when I first added the tutor mode code. I haven't thought all
the issues out by any means, but a some big problems immediately
spring to mind which would require some large scale surgery on gnubg:

The evaluation cache would now be interacting with the background
analysis as well as gnubg's play and any tutor evaluations taking
place. 

The list of moves is being updated as you play, but the same entries
might be having an analysis being added in the background.

I don't know how many occurrences of static structures may exist in
gnubg which reflect the current play situation. I seem to think
(haven't checked at the moment) that the match state itself is a
static structure, in which case you're looking at a lot of changes.

Other items such as the onese Joern just pointed out - analysis
setting and MET are the first things I can think of.

I'm less pessimistic than Joern, I think it's possible that after the
storage of move records has had some rework it may eventually be
possible to do this. 

While writing this, another approach has occurred to me which is
either kind of slick or horribly awful:

[warning - delving off into technical issues here, backgammon players
need not read further]

Suppose one didn't try to thread gnubg, but instead (when auto-analyse
is selected) simply forked when starting a match or session. The child
process would be the analyser and would do whatever's needed to close
any gui or cli interfaces.

Have a shared memory segment for completed moves, so when the playing
side of gnubg was ready to add a move to the list, it obtained a lock,
added the move and released it. Moves are only written by the parent
process except at very specific times when copying the analysis
results back to the parent.

The child process keeps its own move list, in a separate shared memory
segment, to which it can add analysis etc. It simply tries to keep up
with the playing side. Each time it completes analysing a move, it
adds it to its game list. It attempts to get the next move to analyse
by locking the shared move list and walking it from the beginning to
find the next unprocessed move while also walking its own list. If it
finds a move in the parent's list that doesn't match it's local list
of analysed moves, it discards everything in its local list from this
move and onwards. If it reaches the end of its list and there is a
move on the parent's list, it copies that one move, releases the lock
and begins the analysis of that move. The child sets a flag to
indicate there are newly analysed moves available, but does not touch
the parent's list.

The parent checks this flag at times where it can afford to change
it's game list. If it's set, it locks it's game list and the
child's, replaces its moverecords with the corresponding analysed ones
from the child and updates the flag to indicate that this has been
done, then releases the locks.

This should provide up-to-date availability of completed analysis
along with coping with the user going back and replaying from an
earlier position or editing an earlier position.

The parent can always see and display if desired, the percentage of
the analysis which is complete. The parent should be able to set a
flag in shared memory telling the child to stop when it completes
analysis of the current move, so you can elect to save a match with
the analysis only partially completed so you can resume it
later. Similarly the parent should be able to tell the child to resume
analysing if the user then wants to let the analysis complete.

Starting a new game will simply terminate the current child and
re-fork, so any settings changes will then be active.


Advantages:

The interaction between analysis and normal use is limited to the
playing gnubg being almost unchanged and not having to pay any
attention to what the analysing gnubg is up to. 

Any changes made to MET, filters, or whatever on the playing side have
no effect on the analyser, since its settings are a snapshot of what
was chosen at the time of the fork.

Human thinking time is put to use for analysis.


Disadvantages:

Using something like the Sconyer database might get interesting - if
parent and child both want a different DVD, what happens?

Synchronising is a bit more complex, some things may not be obvious to
the user - when they finish a match and want to save a game, they need
to either wait for the background analysis to be complete or end up
with an only partially analysed game.

Any analysis or cached evaluations on the playing side are totally
lost.

Memory usage goes *way* up, since you want a big cache if you are
using tutor mode.

This assumes the presence of a fork() command, pre-emptive
multi-tasking, and SysV like shared memory and semaphores.

These are available for all the Unices I know of, but I don't know
what the situation would be for a Windows or MacOS environment - I'm
pretty sure the Mac is OK for all of this, Windows I just don't know.

Unknowns:

Assume you've been playing a length match so that you're well ahead of
the analyser. You simply *have* to know what the analysis of your last
redouble is and don't want to wait, so you click on the redouble in
the game list and then run Analyse Move or maybe even do a short
rollout. This gets put in the parent game list - what does the child
do when it analyses the same move and goes to copy it back to the
parent? Does it use the parent's analysis or its own?

Minor implementation details - every move record gets a sequence
number starting at 0 for a new match or session and going up by 2 in
the parent. When the number is even, the move has not been
analysed. The child puts the records in its list when they've been
analysed, but increments the sequence number. The parent keeps the
highest (even) sequence number of plays made in its shared memory
segment, the child puts the sequence number of the last analysed move
in its shared segment. So the parent has a simple check if the child
has caught up or if the child has completed analysis of some moves
which can now be copied back to the parent.

I think this scheme could acutally be implemented and would not be
nearly the massive amount of work that trying to do background
analysis in the same context would involve.



-- 
Jim Segrave           address@hidden