www.delorie.com/gnu/docs/gnugo/gnugo_174.html   search  
 
Buy GNU books!


GNU Go Documentation

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003