[computer-go] Caching of local search

[Eric Boesch]

I use a cache that is a set of keys (hashes of both the position and the 
problem to be solved) and the search results corresponding to the key. For 
Boolean local searches, that's an alpha value and a beta value, both of 
which consist of two fields -- who wins, and in how many ply.

The hashes are computed as follows (hopefully mostly common sense):

-- hash only the portion of the board that is relevant. This means empty but 
relevant intersections are assigned nonzero hash values, to distinguish them 
from irrelevant intersections. (I'm pretty much ignoring GHI here, not 
because I discount GHI as a problem in go, but because just as someone else 
said, my program has worse problems that need fixing, and a mediocre GHI 
solution could easiliy lead to worse performance -- by reducing the cache 
hit rate too much -- instead of better.) The tricky part would presumably be 
keeping track of the dirty bits, not computing the hash based on those bits.

-- hash the ko ban point (if any -- there will be at most one such point in 
Japanese rules), who moves next, and possibly whether the last move was 
"pass" or not (which may matter if e.g. two passes cause the game to end and 
all stones to be presumed alive).

-- hash a description of the problem. I use a unique code for each search 
class, and then depending on the class particulars, there may be additional 
values such as a hash that says "save chain A3-B3-C3". Obviously, materially 
different problems must hash differently to get correct results, while it 
improves performance but is not absolutely required that superficially 
different but materially equivalent problems (such as "save A3" and "save 
B3" if A3 and B3 are part of the same chain) hash the same.

-- hash any additional exterior conditions, such as "assume the E5-F5 chain 
is alive" or "the E5-F5 chain has 3 external (outside the search space) 
liberties" or "the G7 and H3 stones are linked externally into a single 
chain, so they live and die together, and the E9 and F9 stones are also 
linked into a chain".

-- and then XOR all these hashes together to get an overall local search 
hash key. The point of hashing both the position (which is fast to do 
incrementally) and the problem (which is mostly a one-time computation at 
the beginning of each search) is that it creates cache entries that are 
absolutely (as opposed to relatively, only in the context of the current 
search) valid, so there is no reason to throw them away once the search is 
done. You could put all cache entries, for all kinds of searches, into a 
single global cache that is never emptied except when you run out of memory 
(though then you'd probably end up with heterogeneous value fields). And 
because the question "Are these two problems and positions alike?" is 
answered at a low level, it does not need to be addressed at any other level 
-- there is little inefficiency in repeating searches, because the repeat 
will trigger a cache hit and return immediately. Hardly a new idea, I'm 
sure. It seems to work pretty well, though the program as a whole is 
incomplete so I can't be too definitive about that.

Zobrist hashing is about identifying state data that you will need ahead of 
time and generating random hash values to uniquely identify them. This works 
for describing the board state (3 * 361 precomputed pseudorandom values), ko 
ban points (361 more), and which player moves next (1 or 2 more, depending 
on how you do it). But some kinds of state data cannot be precomputed 
because there are too many combinations. (Not all programs will have state 
data of this kind, so this might not be a problem, in which case the rest of 
this email probably would not be of interest.) So you need a repeatable, but 
not precomputed, way of turning these state data into a random hash. So you 
serialize the data in a globally unique way, and use a stream hash -- a very 
good one, preferably -- to turn the serialized data into an 
almost-certainly-unique 64-bit number.  For example, "E5-F5 share 3 external 
liberties" might be encoded as something like (I hope this code is 
comprehensible, because the concept is pretty straightforward)

// Random unique 64-bit ID (sufficient for any 64-bit final hash), 
hard-coded for all time
uint64_t EXTERNAL_LIB_CODE = 0xfe91473214256843ULL;

sha1_t sha1;

// "Seeding" the hash with EXTERNAL_LIB_CODE guarantees that external lib
// serializations will not equal any other kinds of serializations, even if 
the "data"
// part is the same, because other kinds of serializations will start
// with their own, different, codes. (Of course, different serializations 
still have
// a tiny chance of hashing to the same value.)

sha1.hash(EXTERNAL_LIB_CODE);
char *data = "3=e5f5"; // 3 liberties shared by e5 and f5
sha1.hash(data);
unsigned char sha1_output[SHA1_HASH_SIZE];
sha1.finalize(sha1_output);

// sha1_output now contains the 160-bit hash of the EXTERNAL_LIB_CODE
// concatenated with these_libs_string, but we only need 64 bits. Any 64 
bits
// of the sha1 value should do. Take those bits and XOR them with our
// hash code for this local position so far.

uint64_t ext_libs_hash = *((uint64_t *) sha1_output);
local_position_hash ^= ext_libs_hash;

I use a secure hash (sha1) because, from a performance standpoint, overkill 
(which it probably is) costs me almost nothing (the longer computations are 
done rarely) and because I could not afford spurious hash value collisions. 
Spurious hash collisions are a correctness issue, not just a performance 
issue, for my program, because I throw out the data that would be needed to 
distinguish spurious collisions from legitimate ones.

>From: "Chrilly" <c.donninger at wavenet.at>
>Reply-To: computer-go <computer-go at computer-go.org>
>To: "computer-go" <computer-go at computer-go.org>
>Subject: Re: [computer-go] Caching of local search in NeuroGo?
>Date: Wed, 9 Aug 2006 05:58:10 +0200
>
>
>----- Original Message ----- From: "Markus Enzenberger" 
><compgo at markus-enzenberger.de>
>To: <computer-go at computer-go.org>
>Sent: Wednesday, August 09, 2006 2:37 AM
>Subject: Re: [computer-go] Caching of local search in NeuroGo?
>
>
>>On Tuesday 08 August 2006 12:08, Chrilly wrote:
>>>I would also prefer a discussion about caching of local search in 
>>>NeuroGo.
>>>Up to my knowledge NeuroGo is also one of the few conventional searchers 
>>>in
>>>Computer-Go. Would be interesting to hear about it.
>>
>>there is not much I can contribute. The only local searches NeuroGo does 
>>for
>>its input features are ladders, which are not worth caching, because they 
>>are
>>fast and have a branching factor of close to 1. The search, that NeuroGo 
>>does
>>using the neural network as an evaluation function, is a global search.
>>
>>- Markus
>>_______
>Suzie searches at the moment also only ladders. But somewhat generalized, 
>there can be a branching. The criterion is that the prey has 2 liberties if 
>the attacker is to move. In a classical ladder there is one liberty which - 
>if the prey would move there - the prey would get more than 2 libs. So 
>there is no branching. But on 19x19 even under this restriction one gets a 
>considerable amount of moves. Additionally I have a fast recognition which 
>does not make the moves, but tries to decide statically if the prey dies or 
>lives. Only if this fast recognition returns unknown (e.g. the 
>ladder-breaker has only 2 libs or is near the edge of -the board) the full 
>ladder is run. But even with this restrictions the ladder routine generates 
>10-20 nodes per evaluation. The ladder code runs at about 1.5 MegaPos/sec 
>on a 3 GHz Pentum. So the ladder code alone reduces the speed of the eval 
>to 75-150 KNodes. A more evolved local search which handles also 3-Liberty 
>problems would make things worse.
>Currently Suzie makes 20KNodes/sec. This is very far away from my initial 
>goal of 100KNodes and already quite close to the 10KNodes mentioned by Mark 
>Boon some time ago. But there are currently no optimizations like the local 
>cache.
>
>I assume in case of a Neural Net the relations are different and the local 
>search consumes only a small fraction of the time.
>
>Chrilly
>
>_______________________________________________
>computer-go mailing list
>computer-go at computer-go.org
>http://www.computer-go.org/mailman/listinfo/computer-go/