Re: [Bug-gnubg] Some results from my 'Dice' game

[Jim Segrave]

On Thu 14 Aug 2003 (12:12 -0600), Thomas Hauk wrote:
> Attempt #3 to send this! Argh!
> 
[snip]

> In terms of profiling, my evaluation function is very "heavy". (As 
> relatively heavy as your NN is with your game? I'm not sure). Most of the 
> CPU time used (>90%) goes strictly to the evaluation function. In 
> comparision, my term_board() function probably uses ~1% of total time, and 
> the various search routines ~3% of total time. Even my routines for 
> storing and looking up entries in my transposition table are in the single 
> digits.

I'm not sure how comparable the eval functions are. I believe the NN
is dominated by the large numbers of floating multiplies and
summations in generating the node values and putting them through the
sigmoid function. But, assuming you are testing on hardware and an OS
which can run gnubg, then you can get a reasonable estimate of NN time
by using the Calibrate function. A 700MHz Pentium does about 7700
evals/sec, a 1.8Ghz is about 21,000. Perhaps you can run an 'average' 
evaluation for your program repeatedly to get a comparison figure.

[snip]

> To reiterate what was mentioned before, star2 (the 2nd version of the 
> *-minimax algorithm) is dependent on a good, FAST method for ordering 
> moves (and used for choosing nodes to "Probe"... what "probing" means in 
> the *-minimax context, I will leave aside for now, because you'll need a 
> copy of the paper to follow along). However, I am confident I can achieve 
> a good method for doing so without resorting to the NN for ordering. I 
> will probably start with using the NN anyway, just to use as another data 
> point.
 
> Hopefully the data structure you are using to represent the current game 
> "state" is good/easy to understand, and the calls to the evaluation 
> function relatively straightforward. That way I can just "rip out"
> the 

I think Joern, Oystein or Joseph can give you definitive answers, but
I believe what you'll find is:

You've got two ways to represent the board and functions to convert
one to the other.

The board is represented as two arrays of ints, one being the count of
player 0 checquers on each point (ace point being element 0, bar
element 24). 

or as a position ID, which is a compact bit string (10 bytes)
containing the full position for both sides.

See http://www.cs.arizona.edu/~gary/backgammon/positionid.html for how
it's formed. 

> search routine, plop in my implementation of star1 and star2, and just 
> call your NN to evaluate a position when required. Is there also a way to 
> generate moves, and apply those moves to a game state? That's how my
> Dice 

There is a routine eval.c:GenerateMoves which takes a board in array
form, an array of 2 ints for the dice. It returns a count of the
number of moves and fills in a movelist struct with move records. Move
records use the position IDs rather than the arrays. See the
definitions in eval.h

For getting an evaluation, look at eval.c:ScoreMove() in the context
of 0 ply to see how the NN is called and other things related to evals
= cubes in particular.


-- 
Jim Segrave           address@hidden