Full Board Search Algorithms

    Keywords: Software

Hash-Algorithm

Calculate a hash-value for each position. Ideas range from adding/subtracting (random but fixed) values for each position. Alternatively, create a 361*2 bit string and calculate a hash (i.e. md5 or sha1). Store hash value and game id in binary tree.

Search: calc hash-value for search pattern. Search in tree.

Search time order:

log2(#games * #moves)
e.g. log2 (20000 * 200) = 22 comparisions of hash values

Memory consumption order:

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

For our scenario the size can be estimated at ca. 50MB if the tree structure (node) is included. Too much for memory, thus would have to be read from disc, which is a large performance hit.

If the tree structure is minimized, or omitted (e.g. sort db by hash values and do an extrapolation search) the size is reduced to about 15MB - which is reasonable (assumption: hash-size < 4 byte).

To be sure (especially in the latter case) we have to verify each result against the search pattern, as different positions may have the same hash value. But that should not be too costly.

End-position search

Idea from Kombilo: only look at end positions. End positions either have empty, black, white or "joker" fields (joker = black or white).

Search: test search pattern against end-position, if match is at all possible, check all moves of the game (i.e. all 200 game positions) if search pattern really occurs.

Search time order:

#games + #matches*#moves
e.g. 20000 + 300*200 = 80000 position matches

Memory resources:

#games * size_of_board_structure
(+ #games * size_of_game_record)

Considerably slower than the hash algorithm, but uses much less memory. By factor of #moves faster than simple brute-force search.

Extension:

The end-position search could be extended to be a tool to reduce the number of moves that need to be checked for a particular game.

Let the "end-position" for each intersection be a sequence of move numbers, that indicate whenever a stone is placed on or removed from that intersection. Now if your pattern requires a stone on a particular intersection and that stone is only on the board between move x and move y (x and y being the first two elements of the sequence saved for that intersection) you could restrict all future search to moves between x and y.

The moves that need to be checked can be tracked in an (ordered) linked list, where each element indicates a range of moves that need to be checked.

Additionally, in a full-board search you can then sort the intersections by the number of the move they were first occupied (you can do that in linear time, because you know the total number of moves). If you then work your way through that list from the end, you only need to check a minimum number of moves in each step.


Implementation ideas

For hash algorithm: split large database over several small files. Access files by most-significant bits directly. E.g. file 1.db contains all hash values where the value starts with '1' (decimal), 2.db all starting with '2', ... you get the idea.

If files are broken down to small enough chunks (e.g. 10-20kb) then reading and parsing the file is fast enough. Overall, the sum of the size of files would not matter (i.e. 50MB as pointed out above would not be a problem).


Full Board Search Algorithms last edited by mdm on July 3, 2005 - 18:36
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