Re: [computer-go] Pattern Matcher

[Vincent Diepeveen <diep@xxxxxxxxx>]

John, just simply take the chaining for granted.

Also you limit the number of probes to not waste memory bandwidth.
1 cache line = 64 bytes.

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.

Also possible is an iterative deepending approach where you use an
evaluation function.

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
  c) bestmove 6 bits
  d) 6 bits depthleft bound
  e) 48 bits Zobrist key

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.  

At 15:02 9-11-2004 +0100, John Tromp wrote:
>hi Frank,
>
>>>It uses 2 modulo operations per lookup.
>
>> Why don't you use an AND?
>> Vincent already mentioned that.
>> A simple AND is the same as a modulo, n'est-ce pas?
>
>My hashtable size N is a prime, not a 2-power.
>That way I get a nice random-like distribution
>of positions over the hashtable.
>How do you get as good a distibution with
>a 2-power sized hashtable??
>
>Plus, I don't have to store the low-order
>log_2(N) bits of the key in the hashtable.
>
>regards,
>-John
>_______________________________________________
>computer-go mailing list
>computer-go@xxxxxxxxxxxxxxxxx
>http://www.computer-go.org/mailman/listinfo/computer-go/
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/