Solving 7,7,5-game and 8,8,5-game

Abstract

An $m n k$ -game is a kind of k-in-a-row game played on an $m \times n$ chess board, where two players alternatively mark empty squares with their own colors and the first one to get k-consecutive marks wins. This paper solves 7,7,5-game and 8,8,5-game as draws. In the proof, we propose some methods based on pairing strategies and potential weights, and then use a program implementing these methods to solve 7,7,5-game in about one minute and 8,8,5-game in about three days.

Keywords

positional games pairing strategy

1. Introduction

The game k-in-a-row is a kind of positional game (Beck, 2005, 2008), and is defined as follows. Two players, Black and White, alternately mark with their own color an empty square on a board, say a chess board, and Black plays first. The player who firstly gets k-consecutive marks (horizontally, vertically, or diagonally) wins the game. A game ends as a draw if both players cannot reach k-consecutive marks. Such games are also called $m n k$ -games, if it is played on an $m \times n$ chess board (Uiterwijk and van den Herik, 2000; Van den Herik et al., 2002). For example, tic-tac-toe is a 3,3,3-game. Another popular game is the so-called 5-in-a-row game or Go-Moku (in the free style), which is a 15,15,5-game.

It has been shown using the so-called strategy stealing argument (Chiang et al., 2009, 2011; Hales and Jewett, 1963; Wu and Huang, 2005; Wu et al., 2005): either the first player wins or the two players draw in a k-in-a-row game under perfect play. In the past, many $m n k$ -games were solved (Van den Herik et al., 2002). For n,n,5-games, the game with $n = 15$ was solved as a win for Black (Allis, 1994). On the other hand, the game with $n = 6$ and 7 were solved as a draw respectively by Uiterwijk and van den Herik (2000) and Chen (2013). However, the theoretical values for $7 < n < 15$ are still not solved yet, though the game is more likely to be a win when n is near 15 and a draw when n is near 6.

This paper proposes some methods described in Sections 3 to 5, and then solves the games with $n = 7$ and $n = 8$ as draws through a program implementing these methods. These methods are designed based on pairing strategies and potential weights which are first introduced in detail in Section 2. Section 6 reports the results by running a program implementing these methods. The program solves 7,7,5-game as a draw in about one minute.1

¹
We were informed in the conference that 7,7,5-game was claimed to be solved by Chen (2013). As their paper claimed, 7,7,5-game was solved as a draw by their program, and took about 5 days with one thread on machines equipped with CPU @ 3.10 GHz.

After fine-tuning the program, we can solve 8,8,5-game as a draw in about three days.

2. Background

This section reviews background knowledge, including positional games in Section 2.1, pairing strategies in Section 2.2, and potential weights in Section 2.3.

2.1. Positional games

A hypergraph is formally a tuple $(V, E)$ where V is a set of vertices and E is a set of hyperedges, each of which is a non-empty subset of V. A positional game is then defined as a two player game played on a given hypergraph, in which the two players alternatively mark p and q unmarked vertices in V with their own color. A player wins by firstly completing a hyperedge, which means to mark all vertices with her own color in the hyperedge. If all vertices are marked and still none wins, it is a draw game.

In fact, k-in-a-row games can be viewed as a kind of positional games. For a k-in-a-row game, V is the set of all squares on the chess board, E is the set of all groups of horizontal, vertical and diagonal k-consecutive squares on the chess board, and both p and q are 1.

Another version of positional games is called the Maker–Breaker version. In this version, there is no draw and the two players, Maker and Breaker, win under different conditions. More specifically, the first player, Maker, wins by completing a hyperedge. The second player, Breaker, wins by blocking all hyperedges, i.e., Breaker marks at least one vertex in each hyperedge to prevent Maker from completing the hyperedge. Note that Breaker does not win for completing any hyperedge.

For simplicity of discussion in the rest of this paper, we use the Maker–Breaker version and try to solve games by proving a win for Breaker for k-in-a-row games. More specifically, if we can prove Breaker to win a Maker–Breaker game, the game is at least a draw (either draw or win for White) in the original version of positional games, also called strong positional games (Beck, 2005, 2008). Since the second player does not win from the strategy stealing argument for k-in-a-row games from above, a win for Breaker implies a draw in the original version.

2.2. Pairing strategy

Pairing strategies were mentioned by Beck (1981), Gyorffy et al. (2016), Uiterwijk and van den Herik (2000), Uiterwijk (2017), where a win is proved for Breaker in 5,5,5-game by Uiterwijk and van den Herik (2000) and in ∞,∞,9-game by Gyorffy et al. (2016). In a pairing strategy, some unmarked vertices are assigned into disjoint pairs such that every hyperedge contains at least one pair. Breaker can prevent Maker from completing any hyperedge by responding immediately at another vertex in the same pair. A pairing strategy for the initial of 5,5,5-game is illustrated in Fig. 1(a) where vertices with the same lower-case letters are assigned into the same pairs. Note that it is possible to find multiple pairing strategies for a game.

To be more general, pairing strategies are extended to middle games where some vertices are already marked. If a hyperedge e contains at least one vertex marked by Breaker, the theoretical value of the game $(V, E - e)$ is the same as the that of $(V, E)$ . Such hyperedges are said to be redundant. Thus, pairing strategies can also be applied to middle games by assigning some unmarked vertices into disjoint pairs such that every hyperedge either contains at least one pair or is redundant. We give an example of a pairing strategy for a middle game in Fig. 1(b). Note that no pairs are needed for hyperedges containing the white mark at C4 (A4–E4, B4–F4, C1–C5, C2–C6, A2–E6, F1–B5 and E2–A6). Also, note that hyperedges can share the same pair in a pairing strategy. For example, in Fig. 1(b), the pair (C1, D1) is shared by the two hyperedges in row 1 (A1–E1 and B1–F1).

Fig. 1.

Examples of pairing strategies.

2.3. Potential weights

Beck (1981) introduced functions of potential weights for solving Maker–Breaker positional games, which can also help solve k-in-a-row game. If the potential value of a game calculated based on potential weight functions (below) is lower than some threshold, a win for Breaker can be proven. A potential weight function used in this paper is defined as follows. Given a k-in-a-row game $(V, E)$ , let e be a hyperedge in E, and $M (e)$ the number of vertices marked by Maker in e. The potential weight function of e is then defined as $\begin{matrix} (1) & w (e) = \{\begin{matrix} 0, & if there exists at least one Breaker’s mark in e, and \\ 2^{M (e)}, & otherwise . \end{matrix} \end{matrix}$

The potential value of a game is defined as $\begin{matrix} (2) & P = \sum_{e \in E} w (e) . \end{matrix}$

Assume that Maker wins by marking all vertices of some hyperedge e. Then, $w (e) = 2^{k}$ and P must be at least $2^{k}$ . Let $E (v) \subseteq E$ be the set of all hyperedges which contain the vertex $v \in V$ . The potential weight of a vertex v is defined as $\begin{matrix} (3) & w (v) = \sum_{e \in E (v)} w (e) . \end{matrix}$

Let $P_{t}$ denote the potential value right after the t^th move (indicating the time after the move and before its next move). Namely, $P_{0}$ denotes the initial potential value, $P_{2 n - 1}$ denotes the potential value right after Maker’s n^th move, and $P_{2 n}$ denotes the potential value right after Breaker’s n^th move for all positive integers n. The following is an important property used in this paper.

Property 1.
During a Maker–Breaker k-in-a-row game, if $P_{2 n - 1} < 2^{k}$ , then Breaker wins right after the $(2 n - 1)$ ^st move.
Beck (1981) and Pluhar (2002) discuss many kinds of positional games, and Property 1 is one of the cases. For the sake of self-contained, we give a simple proof for Property 1 as follows. Proof of Property 1.
Let $w_{t} (v)$ denote $w (v)$ right after the t^th move, and $v_{t}$ denote the vertex played at the t^th move. Since Breaker’s move does not increase Maker’s marks and thus the potential weights for all v, we have $\begin{matrix} (4) & \begin{array}{l} w_{2 n} (v) ⩽ w_{2 n - 1} (v), \\ P_{2 n} (v) ⩽ P_{2 n - 1} (v) \end{array} \end{matrix}$ By choosing $v_{2 n}$ with maximum $w_{2 n - 1} (v)$ among all vertices, Breaker can enforce $\begin{matrix} (5) & w_{2 n - 1} (v_{2 n + 1}) ⩽ w_{2 n - 1} (v_{2 n}) . \end{matrix}$

Thus, we can prove $P_{2 n + 1} ⩽ P_{2 n - 1}$ by $\begin{array}{rcl} P_{2 n + 1} & = & P_{2 n} + (2 - 1) \times w_{2 n} (v_{2 n + 1}) = P_{2 n} + w_{2 n} (v_{2 n + 1}) \\ = & P_{2 n - 1} - w_{2 n - 1} (v_{2 n}) + w_{2 n} (v_{2 n + 1}) \\ ⩽ & P_{2 n - 1} - w_{2 n - 1} (v_{2 n}) + w_{2 n - 1} (v_{2 n + 1}) from (4) \\ (6) & ⩽ & P_{2 n - 1} from (5) \end{array}$ Since $P_{2 n - 1} < 2^{k}$ , we obtain by induction $P_{2 i - 1} < 2^{k}$ for all $i > n$ . From (4), $P_{2 i} ⩽ P_{2 i - 1} < 2^{k}$ for all $i > n$ . Thus, $P_{t} < 2^{k}$ for all $t > 2 n - 1$ . From above, Maker has no chance to win the game after the $(2 n - 1)$ ^st move. Thus, Property 1 is proven. □
To prove Breaker’s wins for k-in-a-row games, Property 1 provides another way other than paring strategies. For example, the 5,5,5-game can be directly solved by Property 1, which we show $P_{1} < 2^{5} = 32$ for all the first moves as follows. Consider the case that Maker marks C3 as the first move as shown in Fig. 2(a). The potential value is 16 in total, 8 for 8 hyperedges each with a weight of 1 and 8 for 4 hyperedges (passing the center C3) each with a weight of 2. Similarly, we can calculate the potential values for all the other first moves which are apparently less than 16. Thus, Maker must loss the game from Property 1.

Fig. 2.
Potential weights and Property 1 in different games.

In some cases, it is more suitable to solve games by using Property 1 than pairing strategies. An example is the initial of 4,4,4-game that can be solved by Property 1 – simply check all Maker’s first moves and find out the highest potential value is $13 < 2^{4}$ , as shown in Fig. 2(b). On the contrary, it is impossible to find a pairing strategy for the initial of 4,4,4-game as explained as follows. To pair 10 hyperedges, 20 vertices are required since two hyperedges share at most one vertex and thus cannot share a pair. However, there are only 16 vertices in the 4,4,4-game, thus, no pairing strategies exist.

In other cases, it is more suitable to use pairing strategies. An example is the game in Fig. 1(b), which can be solved by a pairing strategy but not Property 1. A pairing strategy is shown in Fig. 1(b) to prove Breaker’s win. However, Property 1 cannot solve this middle game since Maker still has choices of the next move (e.g., D3) that can make the potential value greater than $2^{5}$ , as shown in Fig. 2(c).
3. Theoretical methods for k-in-a-row games

In this paper, we propose the partial pairing method in Section 3.1 and the vertex domination method in Section 3.2.

3.1. Partial pairing

In this subsection, we propose the partial pairing method to efficiently remove some vertices and hyperedges in a Maker–Breaker game $(V, E)$ without changing the theoretical value. For simplicity of discussion, we assume that redundant hyperedges are removed from E.

A set of unmarked vertices $V_{pair} \subseteq V$ is a partial pairing set if the vertices can be partially assigned into disjoint pairs which satisfies the following condition. The disjoint pairs partially assigned in $V_{pair}$ is called partial pairs in $V_{pair}$ . Let $E_{pair}$ be the set of all hyperedges containing at least one vertex in $V_{pair}$ . The condition is that each hyperedge in $E_{pair}$ , if any, must contain at least one partial pair. An example of a partial pairing is shown in Fig. 3(a), where $V_{pair}$ contains the vertices C7, D7, D6 and E7, and the corresponding $E_{pair}$ is the set of the hyperedges depicted by dotted lines.

Theorem 1.
For a partial paring $V_{pair}$ in $(V, E)$ and the corresponding $E_{pair}$ , the theoretical value of $(V, E)$ is the same as that of $(V - V_{pair}, E - E_{pair})$ .
Proof of Theorem 1.
Assume that Maker has a winning strategy to win the reduced game $(V - V_{pair}, E - E_{pair})$ . Then, it is quite straightforward that Maker wins in the original game $(V, E)$ by following Maker’s moves in the strategy, since Breaker’s marks in $V_{pair}$ cannot stop Maker from completing a hyperedge in $E - E_{pair}$ .

Assume that Breaker has a winning strategy s to win the reduced game $(V - V_{pair}, E - E_{pair})$ . Since Breaker wins the game $(V - V_{pair}, E - E_{pair})$ , the strategy s ensures that Breaker blocks all hyperedges in $E - E_{pair}$ . To win the original game $(V, E)$ , Breaker needs to block all hyperedges in $E_{pair}$ as well. In the case that Maker marks on one vertex in some partial pair, then Breaker marks the other. This ensures to block all hyperedges in $E_{pair}$ . In the case that Maker marks on one vertex in $V_{pair}$ , but not in any partial pairs, Breaker can simply mark any arbitrary vertex, since it has been ensured that all hyperedges can be blocked by the above. □
For a vertex v which is not contained in any hyperedge, we can simply remove it for the following reason. Let $V_{pair} = {v}$ . The corresponding $E_{pair} = \emptyset$ satisfies the condition of partial pairing. Thus, removing the vertex results in the same theoretical value of the game based on Theorem 1. Such a vertex is said to be redundant. Illustrated by Fig. 3(b), the vertex F5 becomes redundant after removing the partial pairing containing the vertices F3 and F4 and the hyperedges in column F. Thus, F5 can be removed. Besides, $V_{pair} = {F 3, F 4, F 5}$ in Fig. 3(b) also satisfies Theorem 1.

Fig. 3.
Examples of partial pairing in 7,7,5 games.
3.2. Vertex domination

Fig. 4.

F5 is dominated by F3 in the 7,7,5-game.

In this subsection, we propose a method to ignore the choices of certain vertices. A player can safely ignore these vertices for the next move without changing the theoretical value of the game. For a Maker–Breaker game $(V, E)$ , a vertex $v_{1} \in V$ is said to be dominated by another vertex $v_{2} \in V$ if both $v_{1}$ and $v_{2}$ are unmarked and $E (v_{1}) \subseteq E (v_{2})$ holds, where $E (v) \subseteq E$ is the set of all hyperedges containing v. We call $v_{1}$ a dominated vertex and $v_{2}$ a dominating vertex. An example is shown in Fig. 4 that the vertex F5 is dominated by the vertex F3 since $E (F 5)$ , the dotted lines, is contained in $E (F 3)$ , both the solid and dotted lines. Intuitively, for both Maker and Breaker, marking $F 3$ is better than marking $F 5$ . From Theorem 2 (below), if a player can win by marking $F 5$ , then she can also win by marking $F 3$ . Therefore, we only need to consider whether $F 3$ is a win. Theorem 2.

For a vertex $v_{1} \in V$ dominated by $v_{2} \in V$ in the game $(V, E)$ , if a player can win by marking $v_{1}$ as the next move, then she can win by marking $v_{2}$ as the next move as well.

The proof is omitted in the version of this paper due to the limitation of page size.

Theorem 2 implies that a player needs not to consider marking dominated vertices as the next move. A special case is that vertex $v_{1}$ is dominated by vertex $v_{2}$ while $v_{2}$ is also dominated by $v_{1}$ in $(V, E)$ . In this case, the two vertices are said to be mutually dominated. Two mutually dominated vertices form a partial paring. Thus, the vertices and the corresponding hyperedges can then be removed according to Theorem 1. An example of mutually dominated vertices is shown in Fig. 3(b). All of the vertices F3, F4 and F5 are mutually dominated, since $E (F 3)$ , $E (F 4)$ and $E (F 5)$ are the same, as depicted in dotted lines.

4. Pairing algorithm

According to Theorem 1, partial pairing can be used to reduce Maker–Breaker games and thus speed up solving the games. In this section, we propose a pairing algorithm, as shown in Algorithm 1, to identify a partial pairing $V_{pair}$ as large as possible given a game $(V, E)$ . Under the best case, the corresponding $E_{pair}$ is the same as E. Such a partial pairing is actually a pairing strategy, which can directly prove Breaker’s win.

To make our algorithm feasible to middle games, we first remove all hyperedges that contain Breaker’s marks from E. We then try to find simple cases of partial pairing sets based on mutually dominated vertices, as shown in Algorithm 2. Finally, we enter a loop to find partial pairing sets by Algorithm 3.

Algorithm 1

Find partial pairing sets

In Algorithm 2, we repeatedly find mutually dominated vertices in a game $(V, E)$ . Once two mutually dominated vertices are found, they are collected as a partial pairing. Thus, the vertices and the corresponding hyperedges are removed from the game. We then continue to find mutually dominated vertices in the reduced game until none can be further found. Finally, we return all the collected vertices as one partial pairing.

Algorithm 2

Find simple partial pairing sets

Algorithm 3 is a recursive function which aims to find a partial pairing for a game $(V, E)$ and a specified pair assignment $PA$ . We first use two greedy rules to assign new pairs into $PA$ and return the vertices in $PA$ if they form a partial pairing. We then use an evaluation function to choose vertices to assign into pairs. For simplicity of discussion, unmarked vertices that are not assigned into pairs are called unassigned vertices, and hyperedges that do not contain any pair are called free hyperedges.

Greedy Rule 1.

If two unassigned vertices are mutually dominated in the given game $(V, E)$ , assign them into a pair. This rule is similar to Algorithm 2. However, the greedy rule here is only used to assign pairs into $PA$ , and vertices in $PA$ are not guaranteed to be a partial pairing.

Greedy Rule 2.

If a free hyperedge only contains two unassigned vertices, assign them into a pair. This is the only possible assignment to make the hyperedge contain a pair.

Evaluation function. For unassigned vertices that cannot be paired by the greedy rules, we design an evaluation function to choose two unassigned vertices. First, we define the score for each hyperedge e as the difference between k and the number of unassigned vertices in e. Second, we find out the hyperedges with the highest score and choose one of them as

e_{highest}

. Finally, we define the pair score for two unassigned vertices

v_{1}

and

v_{2}

e_{highest}

as the difference between the number of free hyperedges that contain both

v_{1}

and

v_{2}

and the number of free hyperedges that contain at least one of

v_{1}

and

v_{2}

. We assign two unassigned vertices with the highest pair score into a pair on

e_{highest}

, and do recursive function call. If the result of the function call fails to find a partial pairing, we allow backtracking and assign another pair with the next highest score at most N times. In addition, we set an upper bound for backtracking to limit the total amount of function calls. This part is not explicitly shown in Algorithm 3.

Algorithm 3

Find a partial pairing set

5. Improving And–Or tree search in k-in-a-row games

In this section, we present a new And–Or Search algorithm for Maker–Breaker k-in-a-row Games, which is mainly based on potential weights as described in Section 2.3, the proposed theorems as described in Section 3, and the pairing algorithm as described in Section 4. The And–Or Search algorithm features problem reduction, branch pruning, move ordering, and early return.

Algorithm 4 illustrates And–Or Search on a game $(V, E)$ where it is Maker’s turn to move. We first try to find partial pairing sets and then redundant vertices and hyperedges to help reduce the game. Partial pairing sets are found by Algorithm 1 and redundant vertices and hyperedges are found by Algorithm 6. If the reduced E becomes empty, which means a pairing strategy is found or Breaker blocks all hyperedges, Breaker is proven to win the game and thus the result of Breaker’s win is returned. Otherwise, we continue to consider unmarked vertices. We remove all dominated vertices and then sort the remaining vertices by their potential weights. Vertices with higher potential weights are searched earlier.

Algorithm 4

And–Or Search (Maker’s part)

Algorithm 5 illustrates And–Or Search on a game $(V, E)$ where it is Breaker’s turn to move. If Maker already completes any hyperedge, the result of Maker’s win is returned. Or if the potential value of the game is already less than $2^{k}$ , the result of Breaker’s win is returned according to Property 1. Otherwise, unmarked vertices are dealt in a way similar to Algorithm 4.

Algorithm 5

And–Or Search (Breaker’s part)

Problem reduction. As mentioned in Section 3.1 and Section 4, a k-in-a-row game can be reduced by partial pairing. In our And–Or Search algorithm, we try to find partial pairing sets to reduce the games at the beginning of Algorithm 4. Furthermore, we also remove redundant vertices and hyperedges. Since Maker’s marks never help reduce games, we only perform these reductions before Maker marks a vertex.

Algorithm 6

Find redundant hyperedges and vertices

Branch pruning. As mentioned in Section 3.2, a player needs not to mark dominated vertices. Thus, this is used to prune branches to speed up the search.

Move ordering. Although potential weights are originally used to directly prove Breaker’s wins, we use them to order moves during search. All unmarked vertices are evaluated by their potential weights as shown in Formula (3), and then sorted accordingly in decreasing order. That is, an unmarked vertex with the highest potential weight is considered as the most promising one for the player to move.

Early return. According to the definition of Maker–Breaker games, a Breaker’s win can only be claimed after all vertices in the game are marked, which may slow down the proofs of Breaker’s wins by tree search. To solve this problem, we take advantage of potential weights and pairing strategies to claim Breaker’s wins earlier. If the potential value of the game is lower than $2^{k}$ or a pairing strategy can be found during the search, then Breaker’s wins are returned without further searches.

6. Results

We first solve 7,7,5-games by a program implementing the above algorithms in Sections 4 and 5. For Algorithm 3, we set the loop count N to 2 and the upper bound for backtracking to ∞ respectively. It took 65 seconds (about one minute) to solve the Maker–Breaker version of 7,7,5-game as Breaker’s win with one thread on machines equipped with Intel(R) Core(TM) i7-7700 CPU @ 3.60 GHz. With more fine tunings, it took about 3 days to solve the Maker–Breaker 8,8,5-game as Breaker’s win. The details of the fine tunings are not discussed in this paper.

7. Conclusion

To our knowledge, this paper is the first to solve the 8,8,5-game as a draw. In this paper, we propose two methods based on partial pairing and vertex domination respectively to reduce games. The methods are incorporated into the proposed And–Or Search to speed up the proof. We also use potential weights to order moves in the search to speed up the proof. The program implementing these methods proves a draw for 7,7,5-game in about one minute. It can also prove a draw for 8,8,5-game in 3 days with more fine tunings.

Footnotes

Acknowledgements

The authors would like to thank the Ministry of Science and Technology of the Republic of China (Taiwan) for financial support of this research under contract numbers MOST 107-2634-F-009-011 and MOST 106-2221-E-009-139-MY2.

References

Allis, L.V. (1994). Searching for solutions in games and artificial intelligence. PhD thesis, Univ. Limburg, Maastricht, The Netherlands.

Beck, J. (1981). On positional games. J. Combin. Theory Ser. A, 30, 117–133. doi:10.1016/0097-3165(81)90001-7.

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.

Chen, C. (2013). The research of new rules for Gomoku and the results of solving Gomoku with 5 × 5, 6 × 6, 7 × 7 board size. Master thesis (in Chinese). Also available at: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22GN060047016S%22.&searchmode=basic.

Chiang, S.-H., Wu, I.-C. & Lin, P.-H. (2009). On drawn K-in-a-row games. In The 12th Advances in Computer Games Conference (ACG12), Pamplon, Spain.

Chiang, S.-H., Wu, I.-C. & Lin, P.-H. (2011). Drawn K-in-a-row games. Theoretical Computer Science, 412(35), 4558–4569. doi:10.1016/j.tcs.2011.04.033.

Gyorffy, L., Makay, G. & Pluhar, A. (2016). Pairing strategies for 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.

10.

Pluhar, A. (2002). The accelerated k-in-a-row game. Theoretical Computer Science, 271(1–2), 865–875. doi:10.1016/S0304-3975(01)00115-3.

11.

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

Winands ,

H.J.

van den Herik and

Kosters (Eds.), Advances in Computer Games. ACG 2017. Lecture Notes in Computer Science (Vol. 10664). Cham: Springer.

12.

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.

13.

Van den Herik, H.J., Uiterwijk, J.W.H.M. & van Rijswijck, J. (2002). Games solved: Now and in the future. Artificial Intelligence, 134, 277–311. doi:10.1016/S0004-3702(01)00152-7.

14.

Wu, I.-C. & Huang, D.-Y. (2005). A new family of k-in-a-row games. In The 11th Advances in Computer Games Conference (ACG’11), Taipei, Taiwan.

15.

Wu, I.-C., Huang, D.-Y. & Chang, H.-C. (2005). Connect6. ICGA Journal, 28(4), 235–242.