Re: [computer-go] Pattern Matcher

[John Tromp <John.Tromp@xxxxxx>]

Vincent Diepeveen wrote:
> John, just simply take the chaining for granted.
I don't do any chaining, as you'd have noticed if you had
read the code:(   It's quite small, only 485 lines...

> Also you limit the number of probes to not waste memory bandwidth.
> 1 cache line = 64 bytes.
I probe the hashtable in
  public final int PROBES = 8;
places for each position. It only stores the results of
an evaluated position if more work is involved than in any
of the 8 positions already stored.

> So you want to put the hashtable at the start of a cacheline and just probe
> each time at most 1 cache line, or if you're lazy just be sure you make a
> chance to get within 1 cache line.
> Store in 8 bytes of course, multiple of 2 needed. Memory lookups to odd
> bytes are way slower.
> What you're doing is win/draw/loss.
A little bit more, also upper/lower bounds:
  public final int UNK = -4;
  public final int LOSE = -2;
  public final int DRAWLOSE = -1;
  public final int DRAW = 0;
  public final int DRAWWIN = 1;
  public final int WIN = 2;

> Also possible is an iterative deepending approach where you use an
> evaluation function.
It's a solver. It searches exhaustively, 42 plies deep.
With the help of a 12Kb database of all 8ply openings,
my program playes perfectly under tournament time conditions.

What exactly is it that you wrote for connect-4?

Evaluating connect-4 positions is very hard, as
http://www.cwi.nl/~tromp/c4.html
demonstrates.

> So for example you store :
>   a) 2 bits win/draw/loss value 
>   b) 2 bits bound (alfa,beta,true) // or more confusing
> truebound,upperbound,lower bound
I already fit that in 3 bits.

>   c) bestmove 6 bits
I don't need bestmove for exhaustive search, which only cares for the result.

>   d) 6 bits depthleft bound
Again, redundant.

>   e) 48 bits Zobrist key
My keys are 49 bits which describe a connect-4 position *exactly*.
Of those I only need to store 32 in the hashtable, as 17 bits are
subsumed by the index.

> Now you overwrite from the 4 probes the probe that has smallest 'depthleft'.
> In a go program better idea is to overwrite based upon number of moves made
> in game + depthleft. So that's extra field. Though possible to store things
> in 8 bytes, better idea in Go is 16 bytes.  
It's best to overwrite the entry which takes the least amount of work to
recompute. I use 5 bits for that.

Alltogether, 3 bits score + 5 bits work + 4 bytes key = 5 bytes.
If I only probe once I can fit the whole hashtable in 1.25Mb

regards,
-John
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/