Corner Search Algorithms

    Keywords: Software

Let's define the problem better: corner search means that the search pattern is anchored in one corner. It can have any size, from 1x1 to 19x19 (the latter case is the special case FullBoardSearchAlgorithms). There are 181 (361/2) possible search pattern sizes (the other sizes are mirrors of those 181 pattern sizes).

Hash for every pattern size

Same idea as in FullBoardSearchAlgorithms, but make a separate hash table for each pattern size.

Memory resources:

#pattern * #games * #moves * (hash-size + gameid-size + node-size)

Ouch. That would be somewhere around 50MB*181 = 9GB.

Hash for selected pattern sizes

Don't make hash tables for every pattern size, but only for a selected few. E.g. 7x7, 7x10, 7x19, 10x10, 10x19 - size is then reduced to about 250MB on disc.

For other patterns use the smaller stored pattern and verify result positions with search pattern. Incures a performance hit, as a result set has to be searched. On the other hand, only search results are compared and signal/noise ratio should be high.

Problem: patterns smaller than 7x7 would need a full search over all positions -> slow. Even when combined with end-position search, the speed target of <1sec cannot be reached.

UlrichGoertz: Another reduction which seems to be sensible for all practical purposes is to compute hash values only for positions where the number of stones on the board does not exceed a certain number (say 30). Search patterns with more than 30 stones are quite rare, and furthermore in such cases the end position comparison works very well.


Corner Search Algorithms last edited by CharlesMatthews on May 31, 2003 - 11:53
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library