This research, originally published in 2004, addresses the pervasive "state-space explosion" problem in solitaire games. By shifting focus from traditional heuristics to the inherent independence of game sub-problems, the authors developed an algorithm capable of outperforming standard search techniques by an order of magnitude.
The Challenge of Heuristics in Gaps
In many solitaire games, the number of possible move sequences is astronomical. Standard search algorithms like Depth-First Search (DFS) or IDA typically rely on heuristics—rules of thumb that estimate the distance to a goal state. However, in the game of Gaps (also known as Montana*), traditional heuristics, such as counting the number of cards in their final destination, are notoriously weak. A player might have 90% of the cards correctly placed but be completely blocked, or have very few in place while being on the verge of a rapid sequence of winning moves.
The authors recognized that the primary challenge in Gaps is not estimating "closeness" to a goal, but rather the redundant effort spent searching move sequences that do not interact with one another.
Methodology: Block Search
The core innovation presented is Block Search, a technique that exploits the independence between different parts of a single-player game to accelerate state-space exploration. The process involves several key steps:
- Subgame Decomposition: The game is divided into four subgames, each corresponding to one of the four "gaps" (empty spaces) on the board.
- Defining a Block: If moves in Subgame A do not affect the legality of moves in Subgame B, they are considered independent. A "block" is the set of all positions reachable by interleaving these independent sequences. Geometrically, if four independent sequences exist, the block represents a 4D hyper-rectangle in the search space.
- Interaction Detection: The algorithm utilizes a "trace" (a 4x13 array) to track the trajectory of gaps. It monitors whether a move in one subgame requires a card that another subgame is planning to move. If an interaction is detected (a "bifurcation"), the block is split, and the search handles the dependency precisely.
- Optimized Transposition Tables: To avoid redundant searches, the authors use a transposition table. However, since a block contains many positions, hashing every single one is inefficient. The authors found a "sweet spot" by hashing only the positions on the edges of the 4D block, significantly reducing memory overhead.
Key Results and Variant Analysis
The authors evaluated Block Search against standard DFS and iterative sampling methods across different game variants.
- Speedup: For the standard 4-suit game, Block Search provided a modest 11% speedup. However, as complexity increased in a 6-suit variant (78 cards), the advantage became massive, achieving a 10x speedup (44 seconds compared to 437 seconds for DFS).
- Completeness: Unlike sampling methods, Block Search is a complete search. It visits every reachable state, ensuring that if it identifies a game as unwinnable, that conclusion is definitive.
- Variant Difficulty: The research highlighted that the "common" version of Gaps (where any '2' can be placed in the first column) is significantly easier for computers to solve than the "basic" version.
As shown in the table above, the success rate for the common variant reaches nearly 67% with $10^8$ probes, whereas the basic variant remains much more difficult at approximately 16.4%.
Conclusion and Future Work
Block Search demonstrates that independence analysis can be a powerful shortcut in state-space search. By treating entire multi-dimensional spaces of positions as a single unit, the algorithm avoids the wasted effort of permuting non-interacting moves.
Future work aims to generalize this approach. Currently, the interaction detection is specific to the rules of Gaps. Developing an algorithm that can automatically detect independent sub-problems in any state-space graph would allow this technique to be applied to a wider variety of games and planning problems, such as Sokoban.
Summary updated