The experiments did not show improvement over first-order heuristics. This might be due to a larger need for samples, or perhaps the criteria for selecting new patterns were unoptimal. There is room for improvement in general and in reducing computational complexity as well as taking into use application-specific heuristics.
The applicability of the proposed approach is limited to games where the order of moves is not very important as long as all of them are made. In Hex and Y this applies exactly, whereas in games of Havannah and Go, it applies approximatively. Perhaps patterns with more complicated structure could be introduced, such as any boolean formula over moves and order relations among moves.
The random filling heuristic in the game of Hex corresponds to communication reliability in graph theory. Two-terminal network reliablity Brecht88twoterminal, or probabilistic connectedness, is the probability that two nodes in a network can communicate. Edges are assumed to have statistically independent probabilities of failing but nodes are assumed reliable. The studies in graph theory have brought results such as that the exact calculation of two-terminal reliability requires exponential computations.
The random filling heuristic for the game of Y is used by Rijswijck02hex. He uses implicit random colouring of empty cells but instead of sampling from the distribution, he uses micro reduction repeatedly until the single value on the size-1 board can be directly used as a heuristic. At each step of the reduction, all the probabilities are assumed to be independent, which makes the heuristic quick and dirty. The transformation in Figure 2 allows the usage of this heuristic also on the bent board. It would be interesting to test this against the proposed approach.
The proposed method generalises trivially to all 1-or-more-player games and to other rewards than win/loss. The 1 player version has a connection to nonlinear planning [see book by][]mcallester91planning. Planning aims at finding a sequence of actions that lead to some goal. Sometimes plan involves non-interacting steps that can be reordered. This is taken into account in a nonlinear plan which only contains a partial order among actions. The set of patterns and statistics can be interpreted as a nonlinear plan.
The idea of estimating statistics for growing patterns is also used in
natural language processing by Siivola05. The model
probabilistically predicts the next word given a context or pattern of
previous words. New patterns are generated by adding a word to an
existing pattern. For the final model, some of the patterns are pruned.
Currently all the patterns and statistics are forgotten after each move, while they could still be used. Also, the proposed system could be used with machine learning. Patterns reappear from game to game so life-long learning should be possible. Games such as Hex, Y, Go, and Havannah all have also limited translational invariance which could be used for generalisation. Machine learning in this setting is left as future work.