Algo Finalpos

Description

The basic idea of this algorithm is to compare a given pattern with the final position of the game in order to find all positions on the board where the given pattern could possibly occur. "Final position" has to be understood in the right sense. More precisely, when creating the corresponding database, we record, for each point on the board, whether at some time during the game, a black stone or a white stone is placed there. Of course, with captures and under the stones play, it can happen that at a certain point there is a black as well as a white stone at some time.

The output of the finalpos algorithm is a list of candidates which have then to be checked using another algorithm (see AlgoMovelist, AlgoIntervals?).

This comparison against the "final position" of course gives us information only from those points in the search pattern which are non-empty. Hence to reduce the time needed for these comparisons, we use the smallest rectangle inside the original pattern which contains all of its stones, i.e. we cut off the exterior rows/columns which are empty.

Further improvements

There is one obvious improvement which should be made to the algorithm: currently, the program uses a brute force algorithm: it takes each pattern (i.e. the original one and its reflections, rotations etc.) separately and goes through the "final position" in order to find all the matches. There are a number of smarter algorithms which can in a sense search for all the patterns simultaneously. The Knuth-Morris-Pratt algorithm is one among those, but there are several variants. There is also the Karp-Rabin algorithm which might be a good alternative.