Solving narrow Konane boards

Abstract

In this paper we investigate the game of Konane, using Combinatorial Game Theory and game-specific solving strategies. We focus on narrow rectangular boards ( $m \times n$ boards with $m ⩽ 4$ ). These are dubbed as Linear Konane, Double Konane, Triple Konane, and Quadruple Konane, respectively.

The initial board contains black and white stones in a checkered pattern, with a gap of two adjacent empty squares to enable moving. Only capture moves are possible. Depending on the exact location of the initial gap (the setup) we have four classes of initial Konane boards (two for Linear Konane), namely all combinations of a horizontal or vertical setup in the middle of the board or at a corner.

For solving narrow Konane boards two notions proved very useful. First, we define moves that cannot be prevented by the opponent as safe moves of a player. Second, two fragments are independent if there is no way they can ever interact.

Using these two notions Linear and Double Konane have been completely solved. Triple Konane was solved except for the horizontal corner setup. For Quadruple Konane only the vertical setup in the middle of the board was solved.

Keywords

Konane Hawaiian Checkers solving games combinatorial game theory

1. Introduction

Konane, also known under the name Hawaiian Checkers, is a traditional two-player game invented by the Hawaiian Polynesians. It is played on a rectangular board, by two players governing the black and the white stones. Every move is a capturing move diminishing the number of opponent stones. The first player unable to move loses the game, the opponent being the winner. The game is a perfect-information game with no chance involved. By these characteristics it is a combinatorial game (Albert et al. (2007); Berlekamp et al. (1982); Conway (1976); Siegel (2013)). Hearn (2009) has shown that Konane is PSPACE-complete.1

¹
Note that this paper has two contradicting rules for determining the winner in Konane (Hearn (2009), pages 288 and 297), i.e. that the first player unable to move wins or loses the game, respectively. In fact these two definitions denote the normal and misère play condition in combinatorial games. All other literature on Konane inspected uses the normal play condition, and we stick to this convention. However, the proof of the PSPACE-completeness does not depend on the play condition and hence applies to either Konane variant.

According to him this makes the game interesting: “Showing a game to be hard is an indication that the game is interesting!” (Hearn (2009), page 288).

1.1. The Konane game

Traditionally the game was played on rectangular boards with 8 to 13 rows and 8 to 20 columns, though other sizes were also reported, like a $14 \times 17$ board (Cook and King (1784)). In this paper we will not restrict the board size, except that we arbitrarily will chose the number of rows m ⩽ the number of columns n. Before the start of the game the board is filled with black and white stones in a checkerboard fashion (arbitrarily we choose the left-down corner filled with a black stone).2

²
We can view the board as consisting of two sets of squares, the dark squares that only can contain black stones and the light squares reserved for white stones. For illustrative purposes in all diagrams in this paper we use gray cells for dark squares and white cells for light squares.

Then two orthogonally adjacent stones (i.e. one black and one white stone) are removed either from the middle of the board or from a corner. Play then proceeds, traditionally starting with Black, by capturing. A capture means jumping with a stone of the own color over an orthogonally adjacent opponent stone, provided that the space immediately after the captured stone is empty. In traditional Konane the same player may continue capturing with the same stone, but only in the same direction (a multi-jump), but this is not obliged (in the variant called Modern Konane multi-jumps are forbidden). We adopt the traditional rule.3

Note that (multi-)jumping does not change the type of squares (dark or light) of jumping stones.

Fig. 1 illustrates a simple move (single capture) and a multi-jump move (multi-capture) in Konane.

The literature is vague about the exact initial removal of the two stones (the setup), except that they must be removed either from the middle of the board or from a corner and that they should be orthogonally adjacent. Sometimes the setup is part of the game, where Black starts by choosing to remove a black stone from the middle of the board or from a corner, followed by White choosing to remove a white stone horizontally or vertically adjacent to the black stone removed. After that the actual game starts. We will describe the exact setups used in Section 3.

Fig. 1.

A single-capture move (above) and a multi-capture move (below) in Konane.

1.2. Previous research

The literature on Konane is scarce. In 1976 a short introductory paper appeared suggesting Konane as a suitable vehicle for teaching AI methods (Gyllenskog (1976)). A few papers deal with building Konane playing programs, based on neural networks (Thompson (2005)) or based on a plain $α β$ framework (Hendrick (2018)). Regarding our purpose of solving Konane there are only four relevant scientific papers to date.

Ernst (1995) in Playing Konane Mathematically gives a first and most appropriate research on Konane for our purpose. Ernst first gives values of positions and patterns; however, unlike our analysis the Konane positions he investigated are on infinite strings. He next investigates the notion of penetration of a fragment, being the largest distance a piece within a fragment can reach with any sequence of legal moves outside the boundary box of the fragment in some direction. The idea is that when the orthogonal distance between two fragments is larger than the sum of their penetrations towards each other, they never can interact, and consequently the component value is the disjunctive sum of the values of the fragments (see further Section 3.2).

Chan and Tsai (2002) in $1 \times n$ Konane – A Summary of Results further analyze $1 \times n$ Konane patterns, but still no full analysis is obtained.

Dos Santos and Silva (2008) show in Konane has Infinite NIM-Dimension that in Konane any nimber $* n$ can occur by giving an algorithm to construct a $* n$ position from a $* (n - 1)$ position.

Finally a recent bachelor thesis by Kirk (2020) reports solving many Konane boards based on $α β$ search. Experiments were done in two runs for each board, namely one where Black starts and one with White starting. Although no CGT values are obtained, the combination of two runs determines the outcome classes (see Section 2.1) of the boards. Besides the outcome classes of many Linear, Double and Triple Konane boards, she provides outcome classes for several larger boards up to $4 \times 9$ , $5 \times 7$ , and $6 \times 6$ .

2. Combinatorial game theory for Konane

Konane is a two-player, perfect-information game without chance. The game necessarily ends due to the fact that every move is a capturing move, lowering the number of stones on the board by at least 1. By these rules Konane belongs to the class of combinatorial games, for which a whole theory has been established, the Combinatorial Game Theory (further CGT in short) (Berlekamp et al. (1982); Conway (1976)). Under the usual win condition for combinatorial games the last player able to move wins the game, i.e., as soon as a player is unable to move they lose. Both players have different moves, so Konane belongs to the category of partizan combinatorial games.

In this section we give a small introduction to the CGT as applicable to Konane. For a more thorough introduction we refer to several text books on CGT, like the notorious On Numbers and Games by Conway (1976) and the magnificient Winning Ways series (Berlekamp et al. (1982)). More recently (Albert et al. (2007)) and (Siegel (2013)) are good introductory texts. In the following we show values for several Konane positions, that are helpful in solving larger Konane positions in the remainder of the paper. Whereever we give CGT values for Konane positions we have checked them using the CGSUITE software package (Siegel (2020)). Moreover, with the help of Kirk’s 2020 solving program it was checked if our values belong to the outcome classes found by her program.

2.1. Konane and CGT

Like all partizan combinatorial games Konane positions are represented by their options, which are the positions which can be reached in one move, separately for the left player (Black) and the right player (White). Formally, a position G is represented as $G = {G^{L} | G^{R}}$ , where $G^{L}$ and $G^{R}$ are the sets of left and right options, respectively. Then there are four possible outcome classes.

The class $L$ consists of all positions where Left wins, irrespective of who moves first. These positions have strictly positive values.

The class $R$ consists of all positions where Right wins, irrespective of who moves first. These positions have strictly negative values.

The class $N$ consists of all positions where the player to move (the Next player) wins. These positions have fuzzy values (incomparable with 0).

The class $P$ consists of all positions where the player to move loses, so the Previous player wins. These positions all have value 0.

2.2. Konane positions with integer values

For Linear Konane positions consisting of alternate pairs of a black stone and a white stone starting with a black stone at a corner we show that they have zero (outcome class $P$ ) or positive (outcome class $L$ ) integer values, as exemplified in Fig. 2.

If there are k such pairs with $k ⩾ 0$ , the value of the position is k. This value gives the number of free steps Black can make, without White ever being able to move. Similarly, for Konane positions with such a pattern starting with a white stone at the corner, the values are their negatives $- k$ (belonging to outcome class $R$ ), giving the number of free white steps.

Fig. 2.

Linear Konane positions with zero or positive integer values.

Another type of positions with negative values is obtained from the ones in Fig. 2 by adding one additional black stone directly to the right of the chain. Then it is White that can move, without Black being able to interfere, so the values are the negatives of the ones from Fig. 2, as shown in Fig. 3.

Note that any position without possible moves for either player has value ${|} = 0$ , denoted as the endgame. However, all positions where the second player to move wins (like ${- 1 | 1}$ ) are equivalent to the endgame and thus also have value 0.

Fig. 3.

Linear Konane positions with zero or negative integer values.

These examples show that Konane positions can have any integer CGT value.

2.3. Konane positions with fractional values

Apart from integer values Konane positions can also have fractional numeric values, as exemplified in Fig. 4.

Of course symmetrical positions with reversed roles for Black and White have negative fractional values. By combining Konane positions with appropriate numeric values it is evident that positions can have any value of the form $\frac{a}{2^{b}}$ with a an integer and b a natural number. As a consequence, all dyadic rational numbers are possible in Konane.

Fig. 4.

Linear Konane positions with positive fractional values.

2.4. Konane positions with infinitesimal values

Konane positions also can have infinitesimal values (which are values smaller than any positive number and larger than any negative number). Some of these are exemplified in Fig. 5.

All Konane positions in Fig. 5 have infinitely small values, incomparable with 0, where the first player to move wins (so belong to outcome class $N$ ). From top to bottom they denote an increasing (but still infinitely small) advantage for Black. Note that $* = ↑^{[0]}$ ∗ and ↑∗ $= ↑^{[1]}$ ∗. The pattern then continues with values $↑^{[3]}$ ∗, $↑^{[4]}$ ∗, $↑^{[5]}$ ∗, etc, leading to a general formula for the value of a single Black/White pair with k additional white stones every second square to the right without end limitations as $↑^{[k]}$ ∗. Similarly, positions like the ones in Fig. 5 with a single white stone and one or more black stones have values $↓^{[k]}$ ∗.

Fig. 5.

Linear Konane positions with infinitesimal values.

The value $* = * 1$ is the most well-known (and most occurring) nimber value (though formally $0 = * 0$ is also a nimber, the only game being both a number and nimber). Nimbers other than $* 0$ are fuzzy values (outcome class $N$ ) incomparable with 0 and with each other. They take their name from the values that can occur in the Nim game (Bouton (1902)), where each player has the same options (such games are called impartial). They are formally defined as $* n = {* 0, * 1, * 2, \dots, * (n - 1) | * 0, * 1, * 2, \dots, * (n - 1)}$ . Besides $* 0$ and $* 1$ the only frequently encountered nimber values in Konane are $* 2$ and $* 3$ , as mentioned by Ernst (1995) and given in Fig. 6.

It is easy to prove that for Konane a position with value $* k$ needs at least k black stones and k white stones, as expressed in Theorem 1. Theorem 1.

In Konane any position with value $* k$ , $k ⩾ 0$ , contains at least k black stones and k white stones.

Proof.

The proof is done by induction. The base case is any position with value $* 0$ , for which it trivially holds that such a position contains at least 0 black stones and 0 white stones. Now suppose the induction hypothesis holds for any position with nimber value up to some $* n$ and consider a position with value $* (n + 1)$ . According to the definition of a nimber Black must have a move (capturing at least one white stone) leading to a position with value $* n$ , which contains at least n white stones, meaning the $* (n + 1)$ position contains at least $* (n + 1)$ white stones. Similarly, since White has a move (capturing at least one black stone) leading to a position with value $* n$ , the $* (n + 1)$ position also contains at least $(n + 1)$ black stones. By the induction principle it therefore holds that any position with value $* k$ contains at least k black stones and k white stones for all $k ⩾ 0$ . □

According to Theorem 1 the two positions in Fig. 6 are “smallest” in the number of black and white stones on the board. However, they are not “smallest” in the size of the board needed. In fact both nimbers can be found in Linear Konane, needing a

1 \times 8

and

1 \times 13

board, respectively, as shown in Fig. 7.

Fig. 6.

Examples of $* 2$ (left) and $* 3$ (right) Konane positions.

Larger nimbers rarely occur in Konane, though Dos Santos and Silva (2008) give a construction to build a Konane position with an arbitrary nimber value, which means that Konane is a game with infinite Nim-dimension.

Fig. 7.

Examples of linear $* 2$ (up) and $* 3$ (down) Konane positions.

3. Preliminaries

In this section we define some preliminary notions used throughout the remainder of this paper. As a convention, when an $m \times n$ Konane board is used, we arbitrarily always assume that $m ⩽ n$ , i.e., for non-square boards there are more columns than rows (the boards are wide). Obviously, high boards (so with $m > n$ ) have the same CGT-values as their wide counterparts (applying rotation and/or mirror symmetry operations). With narrow boards as used in the title we denote boards where the smallest dimension is at most 4.

3.1. Setups of starting positions

As already mentioned in the introduction, there are several possibilities for the starting position on a given rectangular board. We define four initial setups, two at the middle of the board (denoted as M-setups) and two at a corner (denoted as C-setups). These setups mark which two stones are removed from a rectangular board completely filled with black and white stones in checkered pattern to enable the players to start moving.

The setups defined below are the ones most often used, though rarely other setups are mentioned. We note that the solving techniques described in this paper mostly can be applied to such setups as well (but possibly leading to other outcomes).

3.1.1. Setups at the middle of the board

As said the precise rules of the game are not completely clear on which two squares should be emptied before the game starts when the middle of the board is chosen. We fix these in the following definitions, depending on the number of rows and columns being odd or even.

Definition 1.
The Horizontal-Middle setup (H-M-setup) consists of removing two horizontally adjacent stones from the board as follows. If the number of rows is odd, this removal occurs at the middle row, otherwise from the row immediately below the horizontal middle of the board. From this row, if the number of columns is odd, the middle stone is removed plus the stone immediately to the left of it, otherwise the two stones adjacent to the centre of the board are removed.
Definition 2.
The Vertical-Middle setup (V-M-setup) consists of removing two vertically adjacent stones from the board as follows. If the number of columns is odd, this removal occurs at the middle column, otherwise from the column immediately to the left of the vertical middle of the board. From this column, if the number of rows is odd, the middle stone is removed plus the stone immediately below it, otherwise the two stones adjacent to the centre of the board are removed.
For ease of brevity, we further denote an $m \times n$ board using the H-M- and the V-M-setup as an $(m \times n)$ -H-M and $(m \times n)$ -V-M board, respectively. Note that for $1 \times n$ boards obviously only the H-M-setup is possible.
3.1.2. Setups at a corner of the board

If a corner is chosen to start a game, we again have some freedom in the exact setups. We fix these setups in the following definitions.

Definition 3.
The Horizontal-Corner setup (H-C-setup) consists of removing two horizontally adjacent stones from the left-down corner.
Definition 4.
The Vertical-Corner setup (V-C-setup) consists of removing two vertically adjacent stones from the left-down corner.
Similar as for the M-setups, we further denote an $m \times n$ board using the H-C- and the V-C-setup as an $(m \times n)$ -H-C and $(m \times n)$ -V-C board, respectively. Note that for $1 \times n$ boards obviously only the H-C-setup is possible.

To enhance legibility we will sometimes omit the exact setup used from the board notation when it is clear from the context.
3.2. Independence of fragments

Konane fragments can possibly interfere or they are definitely unable to interfere. To describe this more precisely we use the notion of independence of fragments.

Definition 5.
Two Konane fragments are called independent if there is no sequence of legal moves such that any stone in one fragment ever can capture any stone in the other fragment.
In general it is quite hard to determine if two Konane fragments are independent or not. Ernst used the notion of orthogonal penetration of a fragment for this purpose (the maximum distance out of a fragment that a stone can reach by any move sequence (Ernst (1995))). Two fragments are then independent if they are separated by more than the sum of their penetrations in the shortest orthogonal distance between them. It then follows from CGT that the value of the two fragments together is the disjunctive sum of the fragment values.

We give an example position on the $3 \times 15$ board in Fig. 8.

Though rather complicated at first sight, closer inspection reveals that all fragments are independent. There are five fragments (within the dashed boxes), three in the upper row and two in the lower row. Since the middle row is empty the fragments in the upper row cannot interfere with those in the lower row. Moreover, since the fragments within a row are always separated by (at least) 3 empty squares, they also cannot interfere (see Theorem 2 in Section 4.1 for a formal proof). The fragments in the upper row, from left to right, have values $- 1$ , ∗, and ½, those in the lower row from left to right ½ and ↓∗. Since numeric CGT values add like in mathematical summation, ↓∗ is equal to $↓ +$ ∗, and $* + * = 0$ (any nimber is its own negative), the total CGT value of the position is ↓, which is infinitesimal, but strictly negative, meaning that White wins irrespective of who starts.4
⁴
If White starts, the single capture in the ↓∗ fragment leads to a sum value of 0, losing for Black. If Black starts there are two sensible moves: the black move in the ∗ fragment is countered by White multi-jumping in the ↓∗ fragment, while the black move in the ↓∗ fragment is countered by White moving in the ∗ fragment, both leading to a position with value 0, so losing for Black. Other Black moves are even worse.

Fig. 8.
A position with five independent fragments.
3.3. Safe moves

In partizan combinatorial games, where players can build a reserve of moves, called safe moves, the number of safe moves often plays a pivotal role in solving the game. This is, e.g., the case for the well-known game of Domineering (Uiterwijk (2014)), but as will be shown this also holds for Konane, especially for narrow boards.

A safe move in a Konane position is defined as follows.

Definition 6.
A move in Konane is safe if the opponent cannot prevent this move. This means that there is no way that the opponent can remove the capturing stone of the safe move nor can move the stone to be captured by the safe move.
Note that if a stone can be used for multiple safe moves, this is counted as one safe move, since obviously only one of them can be chosen. Note further that the above definition does not imply that all safe moves of a player can be played in the current position. So safe moves can be “future” moves, which only come into play after the player first makes one or more safe moves making room for the future safe move to be played. It still holds that the opponent cannot prevent any of the safe moves chosen. As will be shown in the following sections the number of safe moves the players “own” will be the main concept in determining values in narrow Konane boards, especially in Linear Konane.

Examples of safe moves in Linear Konane are given in Figs 2 and 3. Note that in the third position from above in both figures the number of safe moves of Black/White is two, of which one is a future safe move (becoming available after the first safe move is played). Likewise, in the fourth position from above in both figures the number of safe moves of Black/White is three, of which two are future safe moves.

According to the Combinatorial Game Theory, the number of black safe moves is added as positive integer to the total CGT value of the position, the number of white safe moves as negative integer.
4. Linear Konane

$1 \times n$ Konane is also known as Linear Konane. So far no investigation of such boards has been given. Note that there is an important difference with the $1 \times n$ strips as analyzed by Ernst (1995) and Chan and Tsai (2002), since these concern positions with an infinite number of empty squares on both sides of the Konane fragments, whereas in our case the positions are finite with 2 edges.

Obviously only the H-setups apply to Linear Konane. In this section we first give a better specification of independence of fragments for $1 \times n$ boards. We then investigate CGT values and outcome classes of Linear Konane with H-M- and H-C-setups, combining the concepts of independence and safe moves.

4.1. Independence of Linear Konane fragments

For $1 \times n$ boards it holds that fragments are independent when they are separated by a gap of at least three squares, see Theorem 2.

Theorem 2.
If a $1 \times n$ Konane board contains a sequence of three or more empty squares, the two parts separated by this sequence are independent.
Proof.
Suppose arbitrarily that the separation of three empty squares involve from left to right a dark, a light and a dark square, indexed by integers i, $i + 1$ , and $i + 2$ . In order to interfere there must be a move sequence by which a Black stone is placed on square i or $i + 2$ and a White stone on square $i + 1$ . The latter stone can only reach square $i + 1$ from the left, i.e. from square $i - 1$ , by capturing a black stone at square i, or from the right, i.e. from square $i + 3$ , by capturing a black stone at square $i + 2$ . However, in the first case the black stone can only reach square i before by capturing a white stone at square $i - 1$ , which means that there is no white stone at $i - 1$ anymore that can reach square $i + 1$ , in the second case the black stone can only reach square i+2 before by capturing a white stone at square $i + 3$ , which means that there is no white stone at $i + 3$ anymore that can reach square $i + 1$ . Consequently there is no way for a white stone to reach square $i + 1$ and therefore no capture between one stone of the left fragment with one stone of the right fragment is ever possible. The two components therefore necessarily are independent. □
Note that this theorem is in agreement with Ernst’s (1995) finding that two components are independent if their separation is larger than the sum of the penetration values of the two components. Since a linear component has penetration value 1 in the horizontal direction, two linear Konane fragments are independent if their separation is at least 3.

For starting positions of Linear Konane we can even do better, as expressed in the following theorem. Theorem 3.
If a $1 \times n$ Konane board contains a sequence of exactly two empty squares and is further completely filled, the CGT value of the position is the sum of the CGT values of the two parts.
Proof.
First note that if there is a gap of exactly two neighbouring squares, the gap is bordered by one black stone at one side and one white stone at the other side. On the black-border side only White can move and all his moves are safe. On the other side only Black can move and all his moves are also safe. Further, when a player is able to make a multi-jump, the longest multi-jump is always best.5
⁵
This can be proven using CGT, since refraining from making a longest multi-jump grants the opponent the opportunity to use a stone, that could have been captured. Since this will never hurt the opponent (delaying the use of any safe moves as long as possible is always beneficial), they will gratefully accept this opportunity. As a consequence, the longest multi-jump is always dominating shorter jumps with that stone and we know from CGT that such dominated options can be neglected.

Now suppose that there are k safe black moves in the position each adding $+ 1$ to the value of the position and l white safe moves each adding $- 1$ to the value of the position. Then the value of the position is $k - l$ , being the sum of the two parts. □
Note that Theorem 3 does not hold when the two parts at the sides of the gap are not completely filled. This is proven by the following counterexample. Consider again the lower position in Fig. 7. This position contains a sequence of three empty squares and thus has according to Theorem 1 as value the sum of the values of the left fragment ( $* 2$ ) and the right fragment (∗), i.e. $* 3$ . If we modify the position by shifting the rightmost white stone two squares to the left (narrowing the gap between the two fragments to two squares), we obtain a position with value ${0, * | 0, * 2}$ , as found by analysing all options and confirmed by CGSUITE (Siegel (2020)), which clearly differs from the sum of the fragment values.

Note that due to Theorem 3 the CGT values of the starting positions of Linear Konane are easy to determine, since every $1 \times n$ board starts with a sequence of two empty squares somewhere on the board.
4.2. CGT values of $(1 \times n)$ -H-M Konane boards

Using Theorem 3 we are able to provide values for arbitrary $1 \times n$ Konane boards. Remember that black stones can only occupy dark squares (starting from the left-most square of the board). The initial setup of the board is such that all squares are occupied by an appropriate-colored stone, except the two middle squares for even-sized boards, and the middle and left-of-middle squares for odd-sized boards. We first treat the 4 simplest boards as base cases.

4.2.1. $1 \times n$ boards for $4 ⩽ n ⩽ 7$

In Fig. 9 we give CGT values for the four smallest non-trivial $1 \times n$ boards.

We now distinguish four cases for larger linear boards, always applying Theorem 3 to determine the CGT values.

Fig. 9.

The initial boards and values for the $1 \times 4$ to $1 \times 7$ Konane boards.

4.2.2.

1 \times 4 k

boards with

k > 1

In Fig. 10 we give the starting positions for the $1 \times 8$ board ( $k = 2$ ), the $1 \times 12$ board ( $k = 3$ ), and the $1 \times 16$ board ( $k = 4$ ).

In the upper position the left part has value $- 1$ and the right part has value $+ 1$ , with sum value 0; in the middle position the left part has value $- 2$ , the right part value $+ 2$ , with sum value 0; in the lower position the left part has value $- 3$ , the right part value $+ 3$ , also with sum value 0. This pattern continues for larger values of k, always with a left part with value $- (k - 1)$ and a right part with value $+ (k - 1)$ , so sum value 0. Concludingly, every $1 \times 4 k$ board with $k > 0$ has value 0, thus is a second-player win.

Fig. 10.

The starting positions for the $1 \times 8$ board (above), the $1 \times 12$ board (middle), and the $1 \times 16$ board (below).

4.2.3.

1 \times (4 k + 1)

boards with

k > 1

In analogy with Fig. 10 we give in Fig. 11 the starting positions for the $1 \times 9$ board ( $k = 2$ ), the $1 \times 13$ board ( $k = 3$ ), and the $1 \times 17$ board ( $k = 4$ ).

In the upper position the left part has value $- 1$ and the right part value $+ 2$ , with sum value $+ 1$ ; in the middle position the left part has value $- 2$ , the right part value $+ 3$ , with sum value $+ 1$ also; in the lower position the left part has value $- 3$ , the right part value $+ 4$ , again with sum value $+ 1$ . So all boards in Fig. 11 have value $+ 1$ . This pattern continues for larger values of k, always with a left part with value $- (k - 1)$ and a right part with value $+ k$ , so sum value $+ 1$ . Concludingly, every $1 \times (4 k + 1)$ board with $k > 0$ has value $+ 1$ and thus is a win for Black irrespective of who starts.

Fig. 11.

The starting positions for the $1 \times 9$ board (above), the $1 \times 13$ board (middle), and the $1 \times 17$ board (below).

4.2.4.

1 \times (4 k + 2)

boards with

k > 1

We give in Fig. 12 the starting positions for the $1 \times 10$ board ( $k = 2$ ), the $1 \times 14$ board ( $k = 3$ ), and the $1 \times 18$ board ( $k = 4$ ).

In the upper position the left part has value $+ 2$ and the right part value $- 2$ , with sum value 0; in the middle position the left part has value $+ 3$ , the right part value $- 3$ , with sum value 0 also; in the lower position the left part has value $+ 4$ , the right part value $- 4$ , with sum value 0 again. This pattern continues for larger values of k, always with a left part with value $+ k$ and a right part with value $- k$ , so sum value 0. Concludingly, every $1 \times (4 k + 2)$ board with $k > 0$ has value 0 and thus is a second-player win.

Fig. 12.

The starting positions for the $1 \times 10$ board (above), the $1 \times 14$ board (middle), and the $1 \times 18$ board (below).

4.2.5.

1 \times (4 k + 3)

boards with

k > 1

We give in Fig. 13 the starting positions for the $1 \times 11$ board ( $k = 2$ ), the $1 \times 15$ board ( $k = 3$ ), and the $1 \times 19$ board ( $k = 4$ ).

In the upper position the left part has value $+ 2$ and the right part value $- 2$ , with sum value 0; in the middle position the left part has value $+ 3$ , the right part value $- 3$ , with sum value 0 also; in the lower position the left part has value $+ 4$ , the right part value $- 4$ , with sum value 0 again. This pattern continues for larger values of k, always with a left part with value $+ k$ and a right part with value $- k$ , so sum value 0. Concludingly, every $1 \times (4 k + 3)$ board with $k > 0$ has value 0 and thus is a second-player win.

Fig. 13.

The starting positions for the $1 \times 11$ board (above), the $1 \times 15$ board (middle), and the $1 \times 19$ board (below).

We summarize our results in the following Theorem 4.

Theorem 4.

$(1 \times n)$ -H-M Konane boards with $n > 3$ have values 0 in case $n = 4 k$ , $(4 k + 2)$ , and $(4 k + 3)$ , thus being second-player wins, and have value $+ 1$ for $n = (4 k + 1)$ , i.e., wins for Black.

Proof.

This follows directly from the base cases ( $k = 1$ ) and the four cases with $k > 1$ above. □

4.3. CGT values of

(1 \times n)

-H-C Konane boards

The smallest $(1 \times n)$ -H-C Konane boards with at least one legal move are the $1 \times 4$ and $1 \times 5$ boards, where only White has a legal move terminating the game (see Fig. 14, first and second position). These are safe moves, so these positions have values $- 1$ . The next two boards in this series are the $1 \times 6$ and $1 \times 7$ boards (Fig. 14, third and fourth position), each with two safe moves for White, hence having values $- 2$ .

Obviously this pattern continues, leading to Theorem 5.

Theorem 5.
The CGT value of an $(1 \times n)$ -H-C Konane board is $- ⌊ \frac{(n - 2)}{2} ⌋$ .
Proof.
This follows directly from the pattern depicted above. □
As a result of the theorems in this section it follows that Linear Konane is completely solved. By this term we mean that for every member of some specified class of Konane boards the CGT value is known.6
⁶
As defined here the term “completely solved” is not the same as “strongly solved” as proposed by Allis (1994). The latter means that the value of any position resulting from legal play is known, whereas the first term only concerns the starting position of a board.

In this particular case it means that we have determined the CGT value of every $1 \times n$ board with the setup either in the middle of the board or at the corner.

Fig. 14.
The initial boards and values for some $1 \times n$ -H-C Konane boards.
5. Double Konane

With Double Konane we denote finite $2 \times n$ Konane boards. So far no investigation of such boards has been given.

5.1. CGT values of $(2 \times n)$ -V-M Konane boards

Using the Vertical setup we always start with a completely filled board, except that one column (so two vertically adjacent squares) in the middle of the board is empty.

On further investigation Double Konane appears to be a trivial game. The underlying cause is that on a $2 \times n$ board no vertical moves are possible (needing at least three rows), with as consequence that both rows act as independent linear strips. Of course the results of the previous section are not applicable, since in Linear Konane we always start with a board with two horizontally adjacent empty squares, whereas in Double Konane with Vertical setup both independent strips start with just one empty square. However, the second player has a simple winning strategy, as expressed in Theorem 6.

Theorem 6.
Every $(2 \times n)$ -V-M Konane board is a win for the second player (so has CGT value 0).
Proof.
If Black starts, after every black move White has the option to “copy” this move in the other row, maintaining exact opposite-color symmetry of the two rows. This guarantees White to make the last move and win. If White starts, Black wins using the same strategy. So the board is a second-player win with CGT value 0. □
We further denote this strategy as the opposite-color strategy and illustrate this with an example game in Fig. 15.

In Fig. 15 (upper position) we see that whoever plays first (suppose Black) has only two (symmetric) options. Choosing the left-to-right move the second position in Fig. 15 is reached. According to the strategy White, having three options, can choose the symmetric one in the other row, leading to the third position in Fig. 15. White can always use this strategy, guaranteeing him the last move and win (in this example leading to the final position in Fig. 15). Of course when White starts, Black can follow similarly, leading to a black win. Note that this strategy can be applied to any $(2 \times n)$ -V-M Konane board, irrespective of n.

Fig. 15.
Example game on the $(2 \times 7)$ -V-M Konane board.

Although this strategy guarantees the second player a win, it does not necessarily lead to the shortest win. Note that in the starting position, in one row only Black can play, in the other row only White. Suppose again that Black starts. After every black move in one row, White can respond in the same row, until Black is out of moves and White wins. Since Black never can play in the other row, this game necessarily is shorter. Applying this to the $(2 \times 7)$ -V-M board, after only one black and one white move the game is over and White has won. Although it is not easy to prove that this strategy for White is always possible, the opposite-color strategy always is applicable as proven in Theorem 6, which makes Double Konane with V-M-setup completely solved.
5.2. CGT values of $(2 \times n)$ -H-M Konane boards

Using the Horizontal setup, a Double Konane board contains one fully filled row, whereas the second row has 2 horizontally adjacent empty squares in the middle of the row.

Double Konane with this setup is also trivial. The underlying cause is that again no vertical moves are possible, but also that no moves in the completely filled row are possible. As a consequence Double Konane using the Horizontal setup essentially is a Linear Konane game with an adjacent full row not interacting with the game. This is expressed in Theorem 7.

Theorem 7.
Every $(2 \times n)$ -H-M Konane board has the same value as the $(1 \times n)$ -H-M Konane board.
Proof.
The proof trivially follows from the upper row being unable to interact with the game, since neither vertical moves are possible using this row nor horizontal moves in this row. □
We illustrate this theorem with an example position in Fig. 16.

It is evident that the upper row has no influence whatsoever on the possible moves, and that the lower row is just a Linear Konane board (in this specific case the $(1 \times 7)$ -H-M board, with CGT value 0).

Fig. 16.
The initial position of the $(2 \times 7)$ -H-M Konane board.
5.3. CGT values of $(2 \times n)$ -V-C Konane boards

For Double Konane with V-C-setup the second player can again use the opposite-colory strategy as in Double Konane with V-M-setup to secure the win. This is expressed in Theorem 8 and exemplified by Fig. 17.

Theorem 8.
Every $(2 \times n)$ -V-C Konane board is a win for the second player (so has CGT value 0).
Proof.
The proof is identical as the proof of Theorem 6. □
In this case White cannot play in the same row as Black and all moves in a play are forced. This yields the opposite-color strategy automatically, always leading to a win for the second player. This makes Double Konane with V-C-setup also completely solved.

Fig. 17.
Example game on the $(2 \times 7)$ -V-C Konane board.
5.4. CGT values of $(2 \times n)$ -H-C Konane boards

Regarding Double Konane boards with the H-C-setup the same reasoning as in Double Konane with the H-M-setup reveals their CGT values as expressed in Theorem 9 and exemplified in Fig. 18.

Theorem 9.
Every $(2 \times n)$ -H-C Konane board has the same values as the $(1 \times n)$ -H-C Konane board.
Proof.
The proof is identical as the proof of Theorem 7. □
We illustrate this theorem with an example position in Fig. 18.

This position is equivalent with the $(1 \times 7)$ -H-C board (with value $- 2$ ). This similarly holds for any $(2 \times n)$ -H-C board, irrespective of n, which makes Double Konane with H-C-setup also completely solved.

Fig. 18.
The initial position of the $(2 \times 7)$ -H-C Konane board.

As a consequence of the theorems in this section, Double Konane with either Horizontal or Vertical setup in the middle of the board or at a corner is also completely solved.
6. Triple Konane

In this section we investigate $3 \times n$ Konane boards, dubbed Triple Konane. So far also no investigation of such boards has been given.

6.1. CGT values of $(3 \times n)$ -V-M Konane boards

Using the V-M-setup we always start with a completely filled board in a checkered fashion, except that one column contains a single stone at the upper row (so two vertically adjacent squares below it are empty) in the middle of the board.

On further investigation Triple Konane with V-M-setup also is trivial. The underlying cause is that on a $3 \times n$ board with V-M-setup one row is completely filled, so both players can only start in one of the other two rows with a horizontal starting move. Now the second player can adopt the opposite-color strategy to secure the win, as expressed in Theorem 10.

Theorem 10.
Every $(3 \times n)$ -V-M Konane board is a win for the second player (so has CGT value 0).
Proof.
The proof is identical as the proof of Theorem 6. □
Note that as a result of White’s strategy Black can never make a vertical move. We illustrate this theorem with an example position in Fig. 19.

Although this board is not equivalent with the $(2 \times 7)$ -V-M Konane board (Vertical moves are possible during game play), Fig. 19 shows that White using the opposite-color strategy can prevent the upper row from coming into play, and consequently wins.

Fig. 19.
The initial position of the $(3 \times 7)$ -V-M Konane board.

Like in Double Konane this strategy not necessarily results in a shortest win for White. However, Theorem 10 guarantees that the second player can always win Triple Konane boards with V-M-setup.
6.2. CGT values of $(3 \times n)$ -H-M Konane boards

Using the H-M-setup we always start with a completely filled board, except that the middle row contains two adjacent empty squares in the middle of the board.

On further investigation Triple Konane with the H-M-setup also is trivial. The underlying cause now is that on a $(3 \times n)$ -H-M board both the lower and the upper row are completely filled, so both players at the start can only play in the middle row. Moreover, since after any move in the middle row the lower and upper row are still always filled, only horizontal moves in the middle row are possible. As a consequence Triple Konane using the H-M-setup essentially is a Linear Konane game with two adjacent full rows not interacting with the game. This is expressed in Theorem 11.

Theorem 11.
Every $(3 \times n)$ -H-M Konane board has as value the negation of the value of the corresponding $(1 \times n)$ -H-M Konane board.
Proof.
The proof trivially follows from both the lower and the upper row being unable to interact with the game, since neither vertical moves are possible using these rows nor horizontal moves in these rows. Since the middle row starts with a white stone at the left side, the value of a $(3 \times n)$ -H-M Konane board therefore is the negation of the value of the corresponding $(1 \times n)$ -H-M Konane board. □
We illustrate this theorem with an example position in Fig. 20.

This position shows that any $(3 \times n)$ -H-M board is equivalent with the negation of the $(1 \times n)$ -H-M board. In particular, all $(3 \times n)$ -H-M boards are second-player wins with value 0, except the $(3 \times (4 k + 1))$ -H-M boards being wins for White, with value $- 1$ .

Fig. 20.
The initial position of the $(3 \times 7)$ -H-M Konane board.
6.3. CGT values of $(3 \times n)$ -V-C Konane boards

For the V-C-setup in Triple Konane the same opposite-color strategy as in Triple Konane with the V-M-setup guarantees a win for the second player. This is expressed in Theorem 12 and exemplified in Fig. 21.

Theorem 12.
Every $(3 \times n)$ -V-C Konane board is a win for the second player (so has CGT value 0).
Proof.
The proof is identical as the proof of Theorem 6. □
Theorem 12 guarantees that the second player can always win Triple Konane boards with V-C-setup.

Fig. 21.
The initial position of the $(3 \times 7)$ -V-C Konane board.

As a consequence of the theorems in this section, Triple Konane with either V-M- or H-M-setup as well as with V-C-setup is also completely solved. For Triple Konane with H-C-setup no general proofs have been found, so their CGT values have to be determined “by hand”.
7. Quadruple Konane

In analogy with Double and Triple Konane we denote finite $4 \times n$ Konane boards as Quadruple Konane. Again we know of no investigation of such boards.

7.1. CGT values of $(4 \times n)$ -V-M Konane boards

Using the V-M-setup we effectively start with a Double Konane board with V-M-setup, flanked above and below by a completely filled row. Therefore, Quadruple Konane with the V-M-setup also is trivial. The underlying cause is that at the start the lower and upper row are completely filled, so both players can only start in one of the two middle rows with a horizontal move. Now the second player can adopt again the opposite-color strategy to secure a win, as expressed in Theorem 13.

Theorem 13.
Every $(4 \times n)$ -V-M Konane board is a win for the second player (so has CGT value 0).
Proof.
The proof is identical as the proof of Theorem 6. □
We give an example position in Fig. 22. Although the $(4 \times 7)$ -V-M Konane board is like the $(3 \times 7)$ -V-M Konane board not equivalent with the $(2 \times 7)$ -V-M Konane board (vertical moves are possible during game play), Fig. 22 shows that White using the opposite-color strategy can prevent both the lower and the upper row from coming into play, and consequently wins.

Theorem 13 shows that any $(4 \times n)$ -V-M Konane board is a second-player win by using the opposite-color strategy. Therefore, Quadruple Konane with the V-M-setup is also completely solved. No general proofs for other setups for Quadruple Konane have been found, so again these have to be determined “by hand”.

Fig. 22.
The initial position of the $(4 \times 7)$ -V-M Konane board.
8. Conclusions and future research

We showed that the concept of safe moves is important for Konane. Moreover, from CGT it is known that a position with independent fragments has as value the sum of the values of the fragments. For Linear Konane we showed that a gap of three subsequent empty squares guarantees independency of the fragments. If only safe moves are present, we proved that this gap can be narrowed to just two empty squares. Based on these findings with the support of a useful copy strategy we then solved many classes of narrow Konane boards.

Firstly, for Linear Konane we proved that $(1 \times n)$ -H-M boards have value 0 (second-player wins) for $n = 4 k$ , $n = 4 k + 2$ , and $n = 4 k + 3$ and have value 1 (Black wins) for $n = 4 k + 1$ . To prove this result the notion of safe moves was pivotal. The CGT value of an $(1 \times n)$ -H-C Konane board is $- ⌊ \frac{(n - 2)}{2} ⌋$ . Since no vertical setup is possible it follows that Linear Konane is completely solved.

Secondly, for Double Konane with both vertical setups (in the middle of the board and at a corner) an easy copy strategy proved that all boards are second-player wins (value 0). For both horizontal setups (middle and corner) we showed that their values are equal to the corresponding Linear Konane boards, ignoring the fully-filled row. Therefore, Double Konane is also completely solved.

Thirdly, for Triple Konane boards with both vertical setups (middle and corner) the same copy strategy of Double Konane proved them to be second-player wins (value 0), whereas the horizontal setup in the middle of the board was again equivalent to Linear Konane, ignoring both fully-filled rows. The horizontal corner setup has not been solved so far.

Fourthly, for Quadruple Konane we were only able to solve boards with the vertical setup in the middle of the board using the copy strategy, being second-player wins (value 0). For the other three possible setups no general solutions were found.

As mentioned in Section 1.1 sometimes the setup is part of the game, with Black having the choice of removing a black stone either from the middle of the board or at a corner, after which White has the choice of removing a white stone horizontally or vertically adjacent to the black stone removed. In this case the outcome of a game is determined fully by the dimensions of the board. For Linear Konane Black only wins $1 \times n$ boards with $n = 4 k + 1$ by removing the black stone at the middle of the board; all other Linear Konane boards are wins for White. Double and Triple Konane boards are always wins for White by opting for a vertical setup after whatever first choice Black makes. For Quadruple Konane we know that Black should not start by removing a black stone in the middle of the board, since White then also wins by choosing a vertical setup; for corner setups it is not yet determined who wins.

For future research we are interested in other strategies and/or patterns to determine values for classes of Konane boards unsolved so far. For the missing Triple and Quadruple Konane classes we determined values of several small and medium-sized boards, but were unable to find any patterns. Maybe deeper analysis might reveal useful insights.

References

Albert, M.H., Nowakowski, R.J. & Wolfe, D. (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. Wellesley, MA: A K Peters.

Allis, L.V. (1994). Searching for Solutions in Games and Artificial Intelligence. PhD. thesis, University of Limburg.

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

Bouton, C.I. (1902). Nim, a game with a complete mathematical theory. Annals of Mathematics, 3, 35–39. doi:10.2307/1967631.

Chan, A.Y.W. & Tsai, A. (2002). 1 × n Konane: A summary of results. In

R.J.

Nowakowski (Ed.), More Games of No Chance (MSRI Publications 42), pp. 331–339. Cambridge University Press.

Conway, J.H. (1976). On Numbers and Games. London: Academic Press.

Cook, J. & King, J. (1784). A Voyage to the Pacific Ocean. London: W. and A. Strahan, for G. Nicol and T. Cadell.

Dos Santos, C.P. & Silva, J.N. (2008). Konane has infinite Nim-dimension. Integers: Electronic Journal of Combinatorial Number Theory, 8, #G02.

Ernst, M.D. (1995). Playing Konane mathematically: A combinatorial game-theoretic analysis. UMAP Journal, 16, 95–121.

10.

Gyllenskog, J.H. (1976). Konane as a vehicle for teaching AI. ACM SIGART Bulletin, 56, 5–6. doi:10.1145/1045259.1045261.

11.

Hearn, R.A. (2009). Amazons, Konane, and Cross Purposes are PSPACE-complete. In

M.H.

Albert and

R.J.

Nowakowski (Eds.), Games of No Chance 3 (MSRI Publications 56), pp. 287–306. Cambridge University Press. doi:10.1017/CBO9780511807251.015.

12.

Hendrick, K. (2018). Analysis of Artificial Intelligence Techniques for Konane. Bachelor thesis, Department of Computer Science, Texas Christian University.

13.

Kirk, O. (2020). Solving Konane: A blended approach. Bachelor thesis, Department of Data Science and Knowledge Engineering, Maastricht University.

14.

Siegel, A.N. (2013). Combinatorial Game Theory. Graduate Studies in Mathematics (Vol. 146). American Mathematical Society.

15.

Siegel, A.N. (2020). Combinatorial Game Suite: A computer algebra system for research in combinatorial game theory. Available from http://cgsuite.sourceforge.net/. Last updated August 23, 2020.

16.

Thompson, D. (2005). Teaching a Neural Network to Play Konane. Bachelor thesis, Department of Computer Science, Bryn Mawr College.

17.

Uiterwijk, J.W.H.M. (2014). The impact of safe moves on perfectly solving Domineering boards. In three parts: part 1 ICGA Journal, 37(2), 97–105; part 2 ICGA Journal, 37(3), 144–160; part 3 ICGA Journal, 37(4), 207–213. doi:10.3233/ICG-2014-37204.

Solving narrow Konane boards

Abstract

Keywords

1. Introduction

2 We can view the board as consisting of two sets of squares, the dark squares that only can contain black stones and the light squares reserved for white stones. For illustrative purposes in all diagrams in this paper we use gray cells for dark squares and white cells for light squares.

2. Combinatorial game theory for Konane

2.1. Konane and CGT

2.2. Konane positions with integer values

3.1. Setups of starting positions

3.1.1. Setups at the middle of the board

4.1. Independence of Linear Konane fragments

4.2.1. 1 × n boards for 4 ⩽ n ⩽ 7

5.1. CGT values of ( 2 × n ) -V-M Konane boards

6.1. CGT values of ( 3 × n ) -V-M Konane boards

7.1. CGT values of ( 4 × n ) -V-M Konane boards

References

²
We can view the board as consisting of two sets of squares, the dark squares that only can contain black stones and the light squares reserved for white stones. For illustrative purposes in all diagrams in this paper we use gray cells for dark squares and white cells for light squares.

4.2.1. $1 \times n$ boards for $4 ⩽ n ⩽ 7$

5.1. CGT values of $(2 \times n)$ -V-M Konane boards

6.1. CGT values of $(3 \times n)$ -V-M Konane boards

7.1. CGT values of $(4 \times n)$ -V-M Konane boards