www.delorie.com/gnu/docs/gnugo/gnugo_174.html

search

	Buy GNU books!

GNU Go Documentation

14.2.5 Persistent Reading Cache

Some reading calculations can be safely saved from move to move.

The function store_persistent_cache() is called only by attack and find_defense, never from their static recursive counterparts do_attack and do_defend. The function store_persistent_reading_cache() attempts to cache the most expensive reading results. The function search_persistent_reading_cache attempts to retrieve a result from the cache.

If all cache entries are occupied, we try to replace the least useful one. This is indicated by the score field, which is initially the number of nodes expended by this particular reading, and later multiplied by the number of times it has been retrieved from the cache.

Once a (permanent) move is made, a number of cache entries immediately become invalid. These are cleaned away by the function purge_persistent_reading_cache(). To have a criterion for when a result may be purged, the function store_persistent_cache() computes the reading shadow and active area. If a permanent move is subsequently played in the active area, the cached result is invalidated. We now explain this algorithm in detail.

The reading shadow is the concatenation of all moves in all variations, as well as locations where an illegal move has been tried.

Once the read is finished, the reading shadow is expanded to the active area which may be cached. The intention is that as long as no stones are played in the active area, the cached value may safely be used.

Here is the algorithm used to compute the active area. This algorithm is in the function store_persistent_reading_cache(). The most expensive readings so far are stored in the persistent cache.

• The reading shadow and the string under attack are marked with the character `1'. We also include the successful move, which is most often a part of the reading shadow, but sometimes not, for example with the function attack1().

• Next the reading shadow is expanded by marking strings and empty vertices adjacent to the area marked `1' with the character `2'.

• Next vertices adjacent to empty vertices marked `2' are labelled with the character `3'.

• Next all vertices adjacent to previously marked vertices. These are marked `-1' instead of the more logical `4' because it is slightly faster to code this way.

• If the stack pointer is >0 we add the moves already played from the moves stack with mark 4.