Re: [computer-go] Pattern Matcher

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 15:35 9-11-2004 +0100, John Tromp wrote:
>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

Yeah, but now speed it up a factor 20 and get it within 128KB including the
entire program. Sequential reads go faster for hashtables so sequential
storing n entires after each other is most clever.

For others not informed here i'm referring above to the very well known
hashtable chaining. Don's pal Leierson mentions it also in his big book.

>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/