  In many board games and other abstract games, patterns have been used as
features that can guide automated game-playing agents. Such patterns or
features often represent particular configurations of pieces, empty positions,
etc., which may be relevant for a game's strategies. Their use has been
particularly prevalent in the game of Go, but also many other games used as
benchmarks for AI research. In this paper, we formulate a design and efficient
implementation of spatial state-action features for general games. These are
patterns that can be trained to incentivise or disincentivise actions based on
whether or not they match variables of the state in a local area around action
variables. We provide extensive details on several design and implementation
choices, with a primary focus on achieving a high degree of generality to
support a wide variety of different games using different board geometries or
other graphs. Secondly, we propose an efficient approach for evaluating active
features for any given set of features. In this approach, we take inspiration
from heuristics used in problems such as SAT to optimise the order in which
parts of patterns are matched and prune unnecessary evaluations. This approach
is defined for a highly general and abstract description of the problem --
phrased as optimising the order in which propositions of formulas in
disjunctive normal form are evaluated -- and may therefore also be of interest
to other types of problems than board games. An empirical evaluation on 33
distinct games in the Ludii general game system demonstrates the efficiency of
this approach in comparison to a naive baseline, as well as a baseline based on
prefix trees, and demonstrates that the additional efficiency significantly
improves the playing strength of agents using the features to guide search.
