Set Matching with applications: An enhancement of the Hales–Jewett pairing strategy

Abstract

When solving k-in-a-Row games, the Hales–Jewett pairing strategy [Trans. Amer. Math. Soc. 106 (1963), 222–229] is a well-known strategy to prove that specific positions are (at most) a draw for the first player. For non-overlapping possible winning lines (groups) it requires two empty squares per group to be marked, i.e., with a coverage ratio of 2.0.

In this paper we present a new strategy, called Set Matching.1

¹

This work is an extension of research presented at the ACG 2017 conference, which was published [in: Advances in Computer Games: 15th International Conference, ACG 2017, Springer, 2017, pp. 38–50].

A matching set consists of a set of nodes (the markers), a set of possible winning lines (the groups), and a coverage set indicating how all groups are covered after every first black move. This strategy needs less than two markers per group. As such it is able to prove positions in k-in-a-Row games to be draws, which cannot be proven using the Hales–Jewett pairing strategy.

We show several efficient configurations with their matching sets. These include Cycle Configurations, BiCycle Configurations, and PolyCycle Configurations involving more than two cycles. Depending on configuration, the coverage ratio can be reduced to as low as 1.14.

Many examples in the domain of solving k-in-a-Row games are given, including the direct proof (not based on search) that the empty $4\times 4$ board is a draw for 4-in-a-Row.

To illustrate the power of the method we also show two applications, which prove that 9-in-a-Row and 8-in-a-Row on infinite boards (and hence on any finite board as well) are draws, in a much more rigid way than by case analysis.