Set Matching with applications: An enhancement of the Hales

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.

1. Introduction

Playing k-in-a-Row games is a popular pastime activity (Gardner, 1983). They are played by two players alternately claiming a square, trying to form k consecutive squares of their color in a straight line on some rectangular $m \times n$ board. Therefore, these games are also denoted as $m n k$ -games (Uiterwijk and van den Herik, 2000). By convention the first player in an $m n k$ -game is denoted by Black, putting a black stone on a claimed square, the second player by White, using white stones to occupy claimed squares.

The $m n k$ -games are a subset of positional games (Beck, 2005; 2008, Hefetz et al., 2014). A useful tool in solving positional games is the Hales–Jewett (HJ)-pairing strategy (Hales and Jewett, 1963), by which certain positions can be proven to be at most a draw for Black. The disadvantage is that the basic HJ-strategy (ignoring overlapping groups, see Definition 2) needs two distinct empty squares for every group involved.

In this paper we present results of a study to transform the pairing strategy into a method where a set of groups can be proven to be at most a draw using less than two empty squares per group. We denote this strategy as Set Matching. In Section 2 we give some background theory. Then three classes of matching sets using one, two, and more cycles are presented in Sections 3–5. The configurations are exemplified by positions from 4-in-a-Row games. In Section 6 we provide an overview of the configurations and their efficiencies, and give some experimental results. Two more elaborate applications are given in Section 7. Here we show proofs based on matching sets that 9-in-a-Row and 8-in-a-Row on arbitrary boards are game-theoretical draws. Conclusions and an outlook to future research are given in Section 8.

2. Background

We first give a theoretical framework for $m n k$ -games and provide some useful notions. We then explain the Hales–Jewett pairing strategy and introduce our new method of Set Matching.

Definition 1 (Taken from Beck (2005; 2008), Hefetz et al. (2014)).

A positional game is played on a hypergraph (V, $F$ ), where the set V contains nodes forming the game board and $F \subseteq 2^{V}$ is a family of target subsets of V called the winning sets. During the game, two players alternately occupy previously unoccupied nodes of the board. When the goal of the game for both players is to be the first to occupy all nodes of a winning set, the game is a strong positional game.

Examples of strong positional games are

m n k

-games. The board consists of a rectangular

m \times n

array of nodes (also called squares). The target subsets then are all the possible winning lines (also called groups) of k adjacent squares in a straight line. The first player who occupies all squares of a group wins the game. If no player achieves a win, the game is a draw. A useful theorem for strong positional games, due to John Nash, but probably first published in Hales and Jewett (1963), is known as the strategy-stealing argument, which results in an

m n k

-game being either a black win or a draw, so the best White can achieve is a draw. Informally this theorem can be proven as follows. Assume that White has a winning strategy for some

m n k

-game. Then Black could “steal” this strategy by making an arbitrary move and then pretending to be the second player, using White’s winning strategy. When the strategy requires to make a move claimed before, an arbitrary move can be made. Since an additional move never hurts in

m n k

-games, this means that Black wins, contradicting the assumption. Consequently, White cannot have a winning strategy for an

m n k

-game.

Groups can interact in several ways. We formalize this as depending on the number of common nodes that pairs of groups can have.

Definition 2.
Two groups without common nodes are called non-intersecting. When two groups have common nodes, they are called intersecting. The common nodes are denoted as intersections or corner nodes. Nodes in a group not being intersections are called edge nodes. Two groups with more than one intersection is called overlapping.
In the remainder of this paper we only consider sets of intersecting but not overlapping groups. To prove that a set of non-overlapping groups is at most a draw for Black, the well-known HJ-pairing strategy can be used. Definition 3.
A Hales–Jewett (HJ)-pairing for a set of groups is an assignment of pairs of unoccupied nodes (markers) to all groups, such that every group is covered by a marker pair, i.e., both nodes of such pair are elements of the group. White hereby guarantees for every marker of a pair occupied by Black to respond immediately by occupying the second marker of the pair. As a consequence, White will obtain at least one white stone in every group, preventing a possible win by Black in that group.
Note that markers thus refer to unoccupied nodes as used in a HJ-pairing (or in a matching set from Definition 4 onwards).

As an easy example we consider the 555-game. In the initial position (the empty $5 \times 5$ board) there are 12 groups, none of them overlapping, and 25 unoccupied squares. A HJ-pairing for this board is demonstrated in Fig. 1.

In this figure every group is covered by a pair of nodes marked by a symbol indicating the direction of the group. Using the HJ-pairing strategy White now can always occupy at least one square of every group, thereby preventing Black from occupying a complete group. Since Black thus cannot win the 555-game, the game-theoretical result is a draw. Definition 4.
The coverage ratio of a HJ-pairing or set matching (see below) for a set of groups is defined as the number of marker nodes used to prove that Black cannot obtain a win in a group of the set, divided by the number of groups in the set.
A HJ-pairing for a set of non-overlapping groups always needs exactly two markers per group, so the coverage ratio then is 2.0. As an enhancement we introduce matching sets, needing less markers than 2 per group to cover the whole set of groups. A formal notation for a matching set M is as follows. Definition 5.
A matching set M is a triple $(N, G, C)$ , where N denotes the set of marker nodes used for the matching, G the set of groups, and C the set of coverings guaranteeing that Black cannot achieve a win in any group of the set. A covering consists of a black move followed (→) by the white response, followed by a HJ-pairing or a matching set for the remaining groups not containing the white response.
Note that a successful matching requires for each black move taken from the marker node set a white response followed by a covering guaranteeing a draw. This can either be a successful HJ-pairing (base case) or a successful set matching (recursively) for the remaining groups concerned.

Fig. 1.
A HJ-pairing for the 555-game.

By its definition a matching set is a generalization of a HJ-pairing, where each covering directly or indirectly terminates in one or more HJ-pairings. The coverage ratio of a matching set $(N, G, C)$ is by definition $| N | / | G |$ .

When showing matching sets we will use the following conventions in the remainder of this paper. 1) Common abbreviations will be used, like a–h for the markers a to h. 2) Every group is denoted by all the markers in the group, where for brevity reasons we omit parentheses and commas. For instance, the group containing markers a and b is denoted by just $a b$ . 3) We omit coverings that are equivalent to other mentioned coverings (mostly symmetric in the configuration sketch). 4) In case a matching set just consists of a naive HJ-pairing, we just give a set with marker pairs.
3. Set matching using cycle configurations

In this section we give several configurations that need less than 2 markers per group. For each such configuration we give a sketch and a diagram of an example board position taken from a 4-in-a-Row game. We always assume that the positions are with Black as first player to move and that White as second player shows that Black cannot win the position. The example positions are chosen such that no other groups without white stones are present (where Black could possibly win) except those in the matching set, that all non-marker squares in the groups are occupied by Black (to prevent simple HJ-pairings), that there are as many white as black stones (i.e., legal positions), and that there are no black threats outside the groups (so White needs only address the local situation). Note that we ignore possible wins for White in a specific example position, since we only are showing that the position is at least a draw for White.

When referring to specific squares in a position we will use chess-like notation, where columns are labelled from left to right by ‘a’, ‘b’, etc, and rows from bottom to top by ‘1’, ‘2’, etc. Further we denote squares that are unoccupied, occupied by a black stone, or occupied by a white stone simply as empty, black, or white squares, respectively.

3.1. The Triangle Configuration

To achieve a reduction of the number of markers needed, we investigated the idea that the groups intersect in a cyclic way. The smallest such set of groups is when three groups are involved. The Triangle Configuration is formed by three pair-wise intersecting groups. All three intersections are markers. Further two of the three groups have one additional (edge) marker. See Fig. 2 (left) for a sketch. Markers are required to be unoccupied. Non-marker nodes can be unoccupied or black.

In this configuration White always responds with a or b after any black marker move. We denote a and b as the main markers, i.e., the set of white follow-ups to Black’s initial play. By doing this, two of the three groups will be covered and the third group then can be covered by two unused markers in that group using a naive HJ-pairing. The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - e}, {a b, a d c, b e c}, \\ {a \to b {(c, d)}, c \to a {(b, e)}, d \to a {(b, c)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b or e. As a result, this configuration of 3 groups is covered with just 5 markers, a reduction of 1 node compared to a naive HJ-pairing. Note that the matching set needs not be unique. For instance, in this configuration after Black chose c White could equally well respond with b with as following HJ-pairing set ${(a, d)}$ . Similarly, after Black’s move d White has several other drawing strategies. However, since a single drawing strategy sufficies to show that a position is at most a draw for Black, it is sufficient for a drawing configuration to give just one matching set.

Fig. 2.

Sketch and example position illustrating the Triangle Configuration.

The diagram in Fig. 2 shows an example position. Black has only three groups left (indicated by the dashed lines). A naive HJ-pairing fails. However, recognizing that this position contains a Triangle Configuration (for instance with a, b, c, d, and e corresponding to a1, a4, d1, c1, and c2), we see that these five squares form a matching set for these three groups, proving that this position is (at most) a draw for Black.

3.2. The Square Configuration

We can easily define a similar configuration using a Square, with one side having two marker nodes (the main markers), the other three sides with three markers, see Fig. 3.

This covering is rather similar to the Triangle Configuration, just prolonging the naive HJ-pairing for one more group along the cycle after Black’s first move and White’s response to that. Therefore, the formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - g}, {a b, a e d, b f c, c g d}, \\ {a \to b {(c, g), (d, e)}, c \to a {(b, f), (d, g)}, e \to a {(b, c), (d, g)}, \\ g \to a {(b, f), (c, d)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, d, or f. As a result, this configuration of 4 groups is covered with just 7 markers, again a reduction of 1 node. An example position is given in the diagram in Fig. 3.

Fig. 3.

Sketch and example position illustrating the Square Configuration.

3.3. Arbitrary Cycle Configurations

Closer examination shows that we can generalize this to any cycle of size n ( $C_{n}$ ), with all corners as markers and all sides but one having one additional edge marker. For $C_{3}$ and $C_{4}$ this yields the Triangle and the Square Configurations above. Note that the relative gain decreases with increasing n, as the number of nodes reduction per cycle is just 1, irrespective of cycle size. Of course it is possible to have multiple independent cycle configurations simultaneously, where independent means that the configurations have disjoint marker node sets. As an example we refer to Fig. 7, where in one position (the empty $4 \times 4$ board) two independent matching configurations are shown with many intersecting groups, but fully disjoint marker node sets.

4. Set matching using BiCycle configurations

The single-cycle configurations in Section 3 just give a reduction of 1 node per independent cycle. It therefore would be advantageous when multiple cycles interact in such a way that they can be used in a more efficient matching set. For this we need overlapping node sets and possibly group sets overlapping as well. We need at least two common nodes in the node sets, since otherwise Black can start with the single common node, after which we have two disjoint group fragments without any reduction at all.

In this section we will investigate configurations consisting of two interacting triangles, starting with one triangle and reusing up to two sides for a second triangle. When the two triangles have three common sides, they necessarily coincide, and no gain can be obtained. In the next subsections we therefore consider the following 3 cases: 1) two triangles with two common sides; 2) two triangles with one common side; and 3) two triangles without common sides.

4.1. Configurations of two triangles with two common sides

When the two triangles have two common sides, we have several possibilities for the non-common side of the second triangle. We just give one case, namely where this side uses the two edge markers of the first triangle. Since this configuration can be equally well seen as a triangle with an intersecting line, we denote this configuration as a Triangle/Line Configuration, see Fig. 4. The thick dashed lines denote the common sides of the triangles.

In this configuration, the main markers are a and b, like in the simple Triangle Configuration with triangle $a b c$ . Since depending on the moves played in this triangle either d or e will not be used for covering the sides of the first triangle, they may be used profitably with one additional edge marker for a new side $d f e$ of the second triangle $d e c$ . The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - f}, {a b, a d c, b e c, d f e}, \\ {a \to b {(c, d), (e, f)}, c \to a {(b, e), (d, f)}, d \to a {(b, c), (e, f)}, \\ f \to a {(b, c), (d, e)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b or e. As a result, this configuration of 4 groups is covered with just 6 markers, a reduction of 2 nodes. An example position is given in the diagram in Fig. 4. Note that edge markers need not be physically situated between the corner markers in a group, as illustrated by edge marker c4 of group c1-c4.

Fig. 4.

Sketch and example position illustrating a Triangle/Line Configuration.

The idea of two cycles with one new side also works with other cycles. We just give one example, see Fig. 5.

Here we have two overlapping squares with three common sides (a Square/Line Configuration), where the not-common side of the second square using one additional marker intersects the first square in two edge markers. The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - h}, {a b, a e d, b f c, c g d, e h f}, \\ {a \to b {(c, g), (d, e), (f, h)}, c \to a {(b, f), (d, g), (e, h)}, \\ e \to a {(b, c), (d, g), (f, h)}, g \to a {(b, f), (c, d), (e, h)}, \\ h \to a {(b, c), (d, g), (e, f)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, d, or f. As a result, this configuration of 5 groups is covered with just 8 markers, again a reduction of 2 nodes. The diagram in Fig. 5 shows an example position using this configuration.

Fig. 5.

Sketch and example position illustrating the Square/Line Configuration.

Of course we again can generalize this to two cycles of any size n ( $C_{n}$ ) with all but one common sides, leading to Cycle $C_{n}$ /Line Configurations. The reduction always will be 2 nodes.

4.2. Configurations of two triangles with one common side

When the two triangles have one side in common, the common side should be the side with just two markers of the first triangle. If not, Black could choose one of the main markers such that White has to respond outside the second triangle, which does not give a useful situation. When the two triangles share this side, we have two subcases. The first is when no other nodes are shared, leading to a BiTriangle Configuration, see Fig. 6. Responses by White in these two cycles are related by mirror symmetry.

The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - h}, {a b, a d c, a g f, b e c, b h f}, \\ {a \to b {(c, d), (f, g)}, c \to a {(b, e), (f, h)}, d \to a {(b, c), (f, h)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, e, f, g, or h. In this configuration 8 markers cover 5 groups, a reduction of 2 nodes. An example position is given in the diagram in Fig. 6.

Fig. 6.

Sketch and example position illustrating the BiTriangle Configuration.

Note that several independent configurations may be used simultaneously. As a notorious example, consider the empty $4 \times 4$ board. We can apply a BiTriangle Configuration as in Fig. 7 (left) with main markers a1 and d4, or alternatively apply another BiTriangle Configuration as in Fig. 7 (middle) with main markers b3 and c2.

Since these two matching sets do not interact (their node sets are disjoint), we may combine the two configurations for the empty $4 \times 4$ board (they just fit “into” each other), resulting in Fig. 7 (right). As a consequence all 10 groups are matched by the 16 empty squares. So this new pairing method proves that the $4 \times 4$ board is a draw, investigating just 1 node (a kind of perfect solving (Uiterwijk, 2014)).

Fig. 7.

Example positions illustrating two BiTriangle Configurations (left and middle) and their combination (right) on the empty $4 \times 4$ board.

As the second subcase we consider the possibility that the two triangles also share another edge marker, see Fig. 8. We denote this configuration as the BiTriangleX Configuration.

The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - g}, {a b, a d c, a e f, b e c, b g f}, \\ {a \to b {(c, d), (e, f)}, c \to a {(b, e), (f, g)}, d \to a {(b, c), (f, g)}, \\ e \to a {(b, c), (f, g)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, f, or g. In this configuration 7 markers cover 5 groups, a reduction of 3 nodes. An example position is given in the diagram in Fig. 8.

Fig. 8.

Sketch and example position illustrating the BiTriangleX Configuration.

4.3. Configurations of two triangles without common sides

Another idea is to use the triangles without reduction, but sharing common markers. There are many ways to do this. We just give one useful case, see Fig. 9. We call this configuration the FlatStar Configuration.

In this configuration the marker set consists of the eight nodes a–h. It is easy to verify that after every first black move on a marker, White has a suitable response by b or g (the two main markers), leaving a situation were all remaining groups can be covered with a naive HJ-pairing. As a result the markers a–h covers all 6 groups. The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - h}, {a b c, a d g, b d f, b e h, c e g, f g h}, \\ {a \to b {(c, e), (d, g), (f, h)}, b \to g {(a, c), (d, f), (e, h)}, \\ d \to b {(a, g), (c, e), (f, h)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with c, e, f, g, or h. This configuration is particularly efficient, needing just 8 markers for 6 groups, a reduction of 4 nodes. An example position is given in the diagram in Fig. 9.

Fig. 9.

Sketch and example position illustrating the FlatStar Configuration.

5. Set matching using PolyCycle configurations

When more than two cycles are involved (further denoted as PolyCycles), the number of possible cases grows considerably. We just give two possibilities. The first possibility is to form an additional cycle using all-but-one common sides with one cycle, leading to PolyCycle/Line Configurations, see Section 5.1. The second possibility is when more than two cycles share one common edge, see Section 5.2.

5.1. PolyCycle/Line Configurations

If the configuration permits it may be possible to combine PolyCycles with Lines. Again, there are many ways to do this. A first possibility is shown using a BiTriangle. From Fig. 6 and the accompanying matching set we see that in all move sequences in this configuration node d or e and node g or h are not used. This gives the opportunity for adding one more group through for instance d and e with one additional edge marker. This leads to the BiTriangle/Line Configuration, see Fig. 10.

The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - i}, {a b, a d c, a g f, b e c, b h f, d i e}, \\ {a \to b {(c, d), (e, i), (f, g)}, c \to a {(b, e), (d, i), (f, h)}, \\ d \to a {(b, c), (e, i), (f, h)}, f \to a {(b, h), (c, e), (d, i)}, \\ g \to a {(b, c), (e, i), (f, h)}, i \to a {(b, c), (d, e), (f, h)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, e, or h. In this configuration 9 markers cover 6 groups, a reduction of 3 nodes. An example position is given in the diagram in Fig. 10.

Fig. 10.

Sketch and example position illustrating the BiTriangle/Line Configuration.

We may even add a second group, through g and h with one additional edge marker. This leads to the BiTriangle/BiLine Configuration, see Fig. 11.

The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - j}, {a b, a d c, a g f, b e c, b h f, d i e, g j h}, \\ {a \to b {(c, d), (e, i), (f, g), (h, j)}, c \to a {(b, e), (d, i), (f, h), (g, j)}, \\ d \to a {(b, c), (e, i), (f, h), (g, j)}, i \to a {(b, c), (d, e), (f, h), (g, j)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, e, f, g, h, or j. In this configuration 10 markers cover 7 groups, a reduction of 4 nodes. An example position is given in the diagram in Fig. 11.

Fig. 11.

Sketch and example position illustrating the BiTriangle/BiLine Configuration.

Also the BiTriangleX Configuration of Fig. 8 lends itself for adding an additional group. Since in the matching set either node d or g need not be used, adding an additional group through d and g with one additional edge marker leads to a BiTriangleX/Line Configuration, see Fig. 12. Note that marker e need not be on the group through d and h (althoug it might be), which is the reason why markers d and g are shifted to the right compared with Fig. 8.

The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - h}, {a b, a d c, a e f, b e c, b g f, d h g}, \\ {a \to b {(c, d), (e, f), (g, h)}, c \to a {(b, e), (d, h), (f, g)}, \\ d \to a {(b, f), (c, e), (g, h)}, e \to a {(b, c), (d, h), (f, g)}, \\ h \to a {(b, f), (c, e), (d, g)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, f, or g. In this configuration 8 markers cover 6 groups, a reduction of 4 nodes. An example position is given in the diagram in Fig. 12. Note that in this diagram c2 representing marker e is “accidentally” on the c1-c4 group, but is not used in covering this group.

Fig. 12.

Sketch and example position illustrating the BiTriangleX/Line Configuration.

A last useful line configuration is the FlatStar/Line Configuration, were we have connected the two main markers b and g in Fig. 9 (left) with an additional group. Since White always plays b or g, we even do not need an additional marker for this group. A sketch is given in Fig. 13.

The formal notation of a matching set of this configuration is: $\begin{array}{l} M = & ({a - h}, {a b c, a d g, b d f, b e h, b g, c e g, f g h}, \\ {a \to b {(c, e), (d, g), (f, h)}, b \to g {(a, c), (d, f), (e, h)}, \\ d \to b {(a, g), (c, e), (f, h)}}) \end{array}$ where we again have omitted the equivalent coverings when Black starts with c, e, f, g, or h. This configuration is consequently even more efficient, needing just 8 markers to cover 7 groups, a reduction of 6 nodes. An example position is given in the diagram in Fig. 13.

Fig. 13.

Sketch and example position illustrating the FlatStar/Line Configuration.

5.2. PolyCycle configurations with one common side

It is possible to include more than two cycles in a configuration with all cycles having one common side. One such example with three triangles with one common side combines the BiTriangle and BiTriangleX Configurations, and is denoted as a TriTriangleX Configuration. A sketch is given in Fig. 14.

The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - j}, {a b, a d c, a e f, a i h, b e c, b g f, b j h}, \\ {a \to b {(c, d), (e, f), (h, i)}, c \to a {(b, e), (f, g), (h, j)}, \\ d \to a {(b, c), (f, g), (h, j)}, e \to a {(b, c), (f, g), (h, j)}, \\ h \to a {(b, j), (c, e), (f, g)}, i \to a {(b, c), (f, g), (h, j)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with b, f, g, or j. In this configuration the 10 markers cover 7 groups, a reduction of 4 nodes. An example position is given in the diagram in Fig. 14.

Fig. 14.

Sketch and example position illustrating the TriTriangleX Configuration.

In theory the TriTriangleX configuration permits the combination with a Line through nodes i and j with one additional edge marker, leading to a TriTriangleX/Line Configuration, which is a possible configuration on arbitrary graphs. However, due to the nature of $m n k$ -games this configuration is impossible in such games (at least we were no able to come up with example positions for such configurations in the $m n k$ -game framework) and therefore we have refrained from considering this or similar configurations further.

6. Overview of reductions for configurations

In Table 1 we show the requirements and reductions for all configurations given in Sections 3–5. Moreover, we give the results of a small experiment on the example positions. Note that all example positions occur in the search tree investigated when solving the game associated with the given position (i.e., the empty board for that position).

The first column gives the configuration, the next two columns the number of markers required and the number of groups covered. Next, the reductions in nodes required compared to HJ-pairings are given and the coverage ratios (number of markers / number of groups). In the last two columns we give the example positions used and the number of nodes that our 4-in-a-Row program (Uiterwijk, 2018) needs to prove them to be draws, using naive HJ-pairings.

Table 1
Some drawing configurations

Configuration # markers # groups # reduction Coverage ratio Diagram # nodes

Single cycles

Triangle 5 3 1 1.67 Fig. 2 17

Square 7 4 1 1.75 Fig. 3 40

Cycle $C_{n}$ $2 n - 1$ n 1 $(2 n - 1) / n$ – –

BiCycles with all but one common sides

Triangle/Line 6 4 2 1.50 Fig. 4 26

Square/Line 8 5 2 1.60 Fig. 5 67

Cycle $C_{n}$ /Line $2 n$ $n + 1$ 2 $2 n / (n + 1)$ – –

BiCycles with 1 common side

BiTriangle 8 5 2 1.60 Fig. 6 25

BiTriangleX 7 5 3 1.40 Fig. 8 17

BiCycles without common sides

FlatStar 8 6 4 1.33 Fig. 9 17

PolyCycles

BiTriangle/Line 9 6 3 1.50 Fig. 10 25

BiTriangle/BiLine 10 7 4 1.43 Fig. 11 25

BiTriangleX/Line 8 6 4 1.33 Fig. 12 51

FlatStar/Line 8 7 6 1.14 Fig. 13 17

TriTriangleX 10 7 4 1.43 Fig. 14 23

Configuration	# markers	# groups	# reduction	Coverage ratio	Diagram	# nodes
Single cycles
Triangle	5	3	1	1.67	Fig. 2	17
Square	7	4	1	1.75	Fig. 3	40
Cycle $C_{n}$	$2 n - 1$	n	1	$(2 n - 1) / n$	–	–
BiCycles with all but one common sides
Triangle/Line	6	4	2	1.50	Fig. 4	26
Square/Line	8	5	2	1.60	Fig. 5	67
Cycle $C_{n}$ /Line	$2 n$	$n + 1$	2	$2 n / (n + 1)$	–	–
BiCycles with 1 common side
BiTriangle	8	5	2	1.60	Fig. 6	25
BiTriangleX	7	5	3	1.40	Fig. 8	17
BiCycles without common sides
FlatStar	8	6	4	1.33	Fig. 9	17
PolyCycles
BiTriangle/Line	9	6	3	1.50	Fig. 10	25
BiTriangle/BiLine	10	7	4	1.43	Fig. 11	25
BiTriangleX/Line	8	6	4	1.33	Fig. 12	51
FlatStar/Line	8	7	6	1.14	Fig. 13	17
TriTriangleX	10	7	4	1.43	Fig. 14	23

We see that all configurations need less than 2 markers per group, with 1 marker reduction for the simplest configurations up to even 6 for the FlatStar/Line Configuration. Most informative for the efficiency of the Set Matching method are the coverage ratios of the configurations, always being smaller than 2.0 (the coverage ratio of a HJ-pairing for an arbitrary number of groups), and improving up to 1.14 for the FlatStar/Line Configuration.

The small experiment conducted gives a rough indication of the performance improvement that might be expected in a “real” application (solving the games), where every occurrence of a configuration shown reduces the number of positions investigated by the number in the rightmost column minus 1 (needing no further search). Of course the overall performance improvement depends on the frequencies of the occurrences of these configurations during solving the games. This will be subject of future research.

7. Two applications of set matching

To illustrate the applicability of Set Matching further we provide two examples showing how Set Matching can give much more rigid proofs in some applications.

7.1. 9-in-a-Row is a draw

A first proof that 9-in-a-Row is a draw on an infinite board was given already in 1954 by Pollak and Shannon.2

²
This proof is mentioned at several places, such as Berlekamp et al. (1982), Beck (2008), though no direct reference is found.

It uses the idea of a tiling of the board with H-shaped heptominoes, where Black’s goal is to obtain a 3-in-a-Row on a diagonal line, the horizontal line or the right vertical line in the heptomino, see Fig. 15 (left). “It is easy to see that the second player [White] can achieve his ‘blocking goal’ in every heptomino” (Beck, 2008). The proof is by search. Using Set Matching the proof can be given directly.

In this configuration, we have a triangle $a b c$ covered by 6 markers, the three intersections a–c and three edge markers d–f. In addition, we have a bisecting line from 1 intersection (a) to the opposite edge marker (f), without additional markers. The main markers are a and f. The formal notation for a matching set of this configuration is: $\begin{array}{l} M = & ({a - f}, {a f, b a e, b f c, c a d}, \\ {a \to f {(b, e), (c, d)}, b \to a {(c, f)}, d \to a {(b, c)}, f \to a {(b, c)}}) \end{array}$ where we have omitted the equivalent coverings when Black starts with c or e. As a result, this configuration of 4 groups is covered with just 6 markers, a reduction of 2 nodes.

Fig. 15.

H-heptomino with winning sets and sketch of the matching set.

The sketch in Fig. 15 illustrates that this matching set covers four of the five groups of size 3 in an H-shaped heptomino (the two diagonal groups, the horizontal one and the rightmost vertical one). Pollak and Shannon showed that if we cover the infinite plane with an H-heptomino tiling (see Fig. 16), and White uses this blocking strategy in each H-heptomino in which Black plays, then the strategy guarantees that Black will not be able to claim any straight line larger than 8 squares, showing that 9-in-a-Row is a draw on the infinite board. The markers and dashed lines in Fig. 16 denote maximal-length lines that Black can achieve in each of the four directions when White uses this drawing strategy. Since White’s strategy only involves blocking black groups, the same strategy can also be used to prevent black lines longer than 8 squares on a finite board (if the strategy demands White to play outside the board, he just makes an arbitrary move). Hence 9-in-a-Row is a draw on any board.

Fig. 16.

A tiling of the plane with H-shaped heptominoes with maximum-length black lines in all four directions.

We note that when Hales and Jewett published their paper explaining the pairing strategy (Hales and Jewett, 1963), they also gave a pairing strategy on the infinite board proving that 9-in-a-Row on the infinite board (and hence on any finite board) is a draw, see Fig. 17.3

The literature is vague on this fact as well. Whereas it was mentioned at several places like Berlekamp et al. (1982), Beck (2005; 2008) that this pairing strategy was due to Hales and Jewett, it is not in their 1963 (Hales and Jewett, 1963) paper nor in any other source we have found.

According to the characterisations in Győrffy et al. (2016; 2017) this pairing can be denoted as an optimal and good pairing for 9-in-a-Row. A pairing is good if it is successful, i.e., it guarantees the second player at least a draw. A pairing is optimal for k-in-a-Row if 1) every pair blocks exactly $k - 1$ groups, 2) every group is blocked by exactly one pair, and 3) every square is contained in a pair. Due to the first condition an optimal pairing is necessarily a domino pairing, which is a pairing where each pair contains two neighbouring squares. By the optimality it also follows that all domino pairs have 8-periodicity. Moreover, every good pairing of the inifinite board is either 8-toric (a repetition of an $8 \times 8$ board) or 16-toric (which is a combination of four $8 \times 8$ tori). The HJ-pairing given is not unique, in fact far from, since in Győrffy et al. (2016; 2017) it was also shown that there are no less than 194,543 non-isomorphic good $8 \times 8$ torus pairings. From some of those it is possible to construct 16-toric pairings.

Fig. 17.

The Hales–Jewett pairing on an infinite board proving that 9-in-a-Row is a draw.

7.2. 8-in-a-Row is a draw

Although at first sight it seems challenging to find a Hales–Jewett type of pairing for 8-in-a-Row on the infinite plane also, it was shown a few years ago that no such pairing exists. First, Kruczek and Sundberg (2008) proved that for a k-in-a-Row game a pairing strategy exists when $k ⩾ 3 | S |$ , with S the set of direction vectors. For the integer lattice with four directional vectors ( $(0, 1)$ , $(1, 0)$ , $(1, 1)$ , and $(1, - 1)$ ) this just shows that k-in-a-Row for $k ⩾ 12$ are draws. Continuing on this Mukkamala and Pálvölgyi (2010) showed that for a pairing strategy to exist for a k-in-a-Row game k should be at least $2 | S | + 1$ . This implies that for k-in-a-Row with $k ⩽ 2 | S |$ no such pairing strategy exists (i.e., there is no pairing strategy for k-in-a-row games with $k ⩽ 8$ ).

Of course the above argument only shows that there is no pairing strategy proving that 8-in-a-Row is a draw, but not that there cannot be another blocking strategy to guarantee a draw. Indeed, a first proof that 8-in-a-Row is a draw on an infinite board was given by Zetters (Guy et al., 1980). This proof also involves tiling the infinite board. The tile used (the Zetters’ block) was a “ragged” piece of 12 squares (3 times 4). The Zetters’ block is given in Fig. 18 (left). It can be shown that Black cannot fully claim one of the three horizontal lines of length 4, nor one of the four diagonal lines of length 3, nor one of the two vertical lines of length 2. These groups are the winning sets in the Zetters’ block. Note that all nodes are member of 2 groups, except the nodes on the two vertical lines (b, e, h, and k), being member of 3 groups.

The proof that Black is unable to claim any of the indicated groups fully was also by search (though not a trivial case analysis). As an alternative proof we here provide a matching set doing the job, according to the sketch in Fig. 18 (right). $\begin{array}{l} M = & {{a - l}, {a b c d, e f g h, i j k l, a e i, b f j, c g k, d h l, b e, h k}, \\ {a \to e M_{a e}, b \to e M_{b e}, c \to k M_{c k}, d \to h M_{d h}, e \to b M_{e b}, f \to b M_{f b}}} \end{array}$ with $\begin{array}{l} M_{a e} = & {{b - d, f - l}, {b c d, i j k l, b f j, c g k, d h l, h k}, \\ {b \to k P_{c d, f j, h l}, c \to k P_{b d, f j, h l}, d \to k P_{b c, f j, h l}, f \to k P_{b j, c d, h l}, g \to k P_{b c, d h, f j}, \\ h \to k P_{b c, d l, f j}, i \to k P_{b c, d h, f j}, j \to k P_{b f, c d, h l}, k \to h P_{b d, c g, f j, i l}, l \to k P_{b c, d h, f j}}} \\ M_{b e} = & {{a, c - d, f - l}, {a c d, i j k l, f j, c g k, d h l, h k}, \\ {a \to k P_{c d, f j, h l}, c \to k P_{a d, f j, h l}, d \to k P_{a c, f j, h l}, f \to j M_{b e, f j}, g \to k P_{a c, d h, f j}, \\ h \to k P_{a c, d l, f j}, i \to k P_{a c, d h, f j}, j \to f M_{b e, j f}, k \to h P_{a d, c g, f j, i l}, l \to k P_{a c, d h, f j}}} \\ M_{b e, f j} = & {{a, c - d, g - i, k - l}, {a c d, c g k, d h l, h k}, \\ {a \to k P_{c d, h l}, c \to k P_{a d, h l}, d \to k P_{a c, h l}, g \to k P_{a c, d h}, \\ h \to k P_{a c, d l}, i \to k P_{a c, d h}, k \to h P_{a d, c g}, l \to k P_{a c, d h}}} \\ M_{b e, j f} = & {{a, c - d, g - i, k - l}, {a c d, i k l, c g k, d h l, h k}, \\ {a \to k P_{c d, h l}, c \to k P_{a d, h l}, d \to k P_{a c, h l}, g \to k P_{a c, d h}, \\ h \to k P_{a c, d l}, i \to k P_{a c, d h}, k \to h P_{a d, c g, i l}, l \to k P_{a c, d h}}} \\ M_{c k} = & {{a - b, d - j, l}, {a b d, e f g h, a e i, b f j, d h l, b e}, \\ {a \to e P_{b d, f j, h l}, b \to e P_{a d, f j, h l}, d \to b P_{a e, f g, h l}, e \to b P_{a i, d h, f g}, f \to b P_{a e, d l, g h}, \\ g \to b P_{a e, d l, f h}, h \to b P_{a e, d l, f g}, i \to e P_{a b, d h, f j}, j \to b P_{a e, d h, f g}, l \to b P_{a e, d h, f g}}} \\ M_{d h} = & {{a - c, e - g, i - l}, {a b c, i j k l, a e i, b f j, c g k, b e}, \\ {a \to b P_{c g, e i, j k}, b \to e P_{a c, f j, g k, i l}, c \to b P_{a e, g k, i j}, e \to b P_{a i, c g, j k}, f \to b P_{a e, c g, i j}, \\ g \to b P_{a e, c k, i j}, i \to e P_{a b, c g, f j, k l}, j \to b P_{a e, c g, i k}, k \to b P_{a e, c g, i j}, l \to b P_{a e, c g, i j}}} \\ M_{e b} = & {{a, c - d, f - l}, {f g h, i j k l, a i, c g k, d h l, h k}, \\ {a \to i M_{e b, a i}, c \to h P_{a i, g k, j l}, d \to h P_{a i, c g, j k}, f \to h P_{a i, c g, j k}, g \to h P_{a i, c k, j l}, \\ h \to k P_{a i, d l, f g}, i \to a M_{e b, i a}, j \to h P_{a i, c g, k l}, k \to h P_{a i, c g, j l}, l \to h P_{a i, c g, j k}}} \\ M_{e b, a i} = & {{c - d, f - h, j - l}, {f g h, c g k, d h l, h k}, \\ {c \to h P_{g k}, d \to h P_{c g}, f \to h P_{c g}, g \to h P_{c k}, \\ h \to k P_{d l, f g}, j \to h P_{c g}, k \to h P_{c g}, l \to h P_{c g}}} \\ M_{e b, i a} = & {{c - d, f - h, j - l}, {f g h, j k l, c g k, d h l, h k}, \\ {c \to h P_{g k, j l}, d \to h P_{c g, j k}, f \to h P_{c g, j k}, g \to h P_{c k, j l}, \\ h \to k P_{d l, f g}, j \to h P_{c g, k l}, k \to h P_{c g, j l}, l \to h P_{c g, j k}}} \\ M_{f b} = & {{a, c - e, g - l}, {e g h, i j k l, a e i, c g k, d h l, h k}, \\ {a \to k P_{d l, e i, g h}, c \to k P_{a e, d l, g h}, d \to h P_{a e, c g, i j}, e \to h P_{a i, c g, j k}, g \to h P_{a e, c k, i j}, \\ h \to k P_{a i, d l, e g}, i \to h P_{a e, c g, j k}, j \to h P_{a e, c g, i k}, k \to h P_{a e, c g, i j}, l \to h P_{a e, c g, i j}}} \end{array}$ where we have omitted the equivalent coverings when Black starts with g to l. In this $M_{u v}$ stands for a matching set after Black played u and White responded with v, and $M_{u v, x y}$ for a matching set after Black played u, White responded with v, then Black played x and White responded with y. $P_{u v, x y, \dots}$ stands for a simple HJ-pairing set with pairs (u,v), (x,y), etc.

Fig. 18.

The Zetters’ block with winning sets and sketch of the matching set.

We see that the matching set M is defined recursively, but always terminates with simple HJ-pairings. In this example we need a two-level deep recursion. As a result, this configuration of 9 groups is covered with just 12 markers, a reduction of 6 nodes.

The proof that 8-in-a-Row is a draw is done by tiling the infinite plane with Zetters’ blocks, see Fig. 19. The markers and dashed lines denote maximal-length lines that Black can achieve in each direction when White uses this drawing strategy. From this figure it is immediately evident that Black will never get a horizontal or vertical line with more than 6 black stones in a row, nor a diagonal line with more than 7 black stones in a row, hence 8-in-a-Row is a draw on the infinite board and hence on any finite board as well.

Fig. 19.

A tiling of the plane with Zetters’ blocks with maximum-length black lines in all four directions.

8. Conclusions and future research

In this paper we have presented an enhancement of the Hales–Jewett pairing strategy, called Set Matching. This strategy needs less than 2 squares per group. We have given several configurations with their matching sets, including Cycle, BiCycle, and PolyCycle Configurations. Depending on the configuration, the coverage ratio is reduced to as low as 1.14, compared to 2.0 for HJ-pairings.

Many example positions for 4-in-a-Row games are given, including the direct proof (without further search) that the $4 \times 4$ board is a draw. As additional applications we showed that Set Matching can be used to prove that 9-in-a-Row and 8-in-a-Row on the infinite board (and hence on arbitrary finite boards as well) are draws. Previous proofs of these were based on search. With Set Matching we provide more rigorous proofs. The proof for 8-in-a-Row is also an example demonstrating that Set Matching can be used recursively.

As future research we first will fully implement Set Matching in our k-in-a-Row solver (Uiterwijk, 2018) to investigate its effectiveness compared to naive HJ-pairings for solving games. Some related work has been done by Kutz (2005). He shows based on graph decomposition how to find optimal strategies in polynomial time for deciding if the second player can prevent the first player from winning, but this is strictly done for the class of almost-disjoint (edge intersections in at most one node) graphs of rank three (groups with at most three nodes). For more complicated situations like our $m n k$ -games there is no hope for such effectiveness, however. Further, Hsu et al. (2018) showed an improvement of HJ-pairings, called partial pairing. This idea is surely also applicable to Set Matching and will be pursued further.

Secondly, we will further look for other interesting configurations, a main challenge for non-overlapping groups being one with a matching set (N, G, C) with $| N | ⩽ | G |$ , i.e., a coverage factor of 1.0 or lower, or a proof that such matching sets for non-overlapping groups do not exist.

Thirdly, we will investigate how well Set Matching will perform in case of overlapping groups. Already for standard HJ-pairings we face the difficulty that marker pairs can cover multiple groups simultaneously, but it is no sinecure to find the best marker pair to cover overlapping groups. Using Set Matching this problem will even become more difficult.

References

Beck, J. (2005). Positional games. Combinatorics, Probability and Computing, 14, 649–696. doi:10.1017/S0963548305007078.

Beck, J. (2008). Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press.

Berlekamp, E.R., Conway, J.H. & Guy, R.K. (1982). Winning Ways for your Mathematical Plays, volumes 1–2. Academic Press, London; 2^nd edition, in four volumes: vol. 1 (2001), vols. 2, 3 (2003), vol. 4 (2004). A K Peters, Wellesley, MA.

Gardner, M. (1983). Ticktacktoe games. Ch. 9. In Wheels, Life, and Other Mathematical Amusements (pp. 94–105). W.H. Freeman.

Guy, R.K., Selfridge, J.L. & Zetters, T.G.L. (1980). 8 (or more) in a row. The American Mathematical Monthly, 87(7), 575–576. doi:10.2307/2321433.

Győrffy, L., London, A. & Makay, G. (2017). The structure of pairing strategies for k-in-a-row type games. Acta Cybernetica, 23, 561–572. doi:10.14232/actacyb.23.2.2017.8.

Győrffy, L., Makay, G. & Pluhár, A. (2016). Pairing Strategies of the 9-in-a-Row Game. Submitted.

Hales, A.W. & Jewett, R.I. (1963). Regularity and positional games. Trans. Amer. Math. Soc., 106, 222–229. doi:10.1090/S0002-9947-1963-0143712-1.

Hefetz, D., Krivelevich, M., Stojaković, M. & Szabó, T. (2014). Positional Games. Basel: Springer.

10.

Hsu, W.-Y., Ko, C.-L., Hsueh, C.-H. & Wu, I-C. (2018). Solving 7,7,5-game and 8,8,5-game. In Proceedings of the 10th International Conference on Computers and Games, New Taipei City, Taiwan: National Taipei University.

11.

Kruczek, K. & Sundberg, E. (2008). A pairing strategy for tic-tac-toe on the integer lattice with numerous directions. The Electronic Journal of Combinatorics, 15, Note # N33 (6 pages).

12.

Kutz, M. (2005). Positional games on hypergraphs of rank three. In

Felsner (Ed.), European Conference on Combinatorics, Graph Theory and Applications (EuroComb ’05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science AE (pp. 31–36). DMTCS Proceedings.

13.

Mukkamala, P. & Pálvölgyi, D. (2010). Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions. The Electronic Journal of Combinatorics, 17. Note #N42 (6 pages).

14.

Uiterwijk, J.W.H.M. (2014). Perfectly solving Domineering boards. In

Cazenave ,

M.H.M.

Winands and

Iida (Eds.), Computer Games. Workshop on Computer Games, CGW 2013, Beijing, China. Revised Selected Papers. Communications in Computer and Information Science (Vol. 408, pp. 97–121). Springer Int. Publ. AG.

15.

Uiterwijk, J.W.H.M. (2017). Set Matching: An enhancement of the Hales–Jewett pairing strategy. In

M.H.M.

Winands ,

H.J.

van den Herik and

W.A.

Kosters (Eds.), Advances in Computer Games: 15th International Conference, ACG 2017. Lecture Notes in Computer Science (Vol. 10664, pp. 38–50). Springer. doi:10.1007/978-3-319-71649-7_4.

16.

Uiterwijk, J.W.H.M. (2018). Everything You Always Wanted to Know about 4-in-a-Row. Submitted.

17.

Uiterwijk, J.W.H.M. & van den Herik, H.J. (2000). The advantage of the initiative. Information Sciences, 122(1), 43–58. doi:10.1016/S0020-0255(99)00095-X.

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