3
$\begingroup$

I'd like to know if this game can end in a draw:

Nakatta is a connection game for two players: Black and White. It is played on the intersections (points) of an initially empty square grid (board). The top and bottom edges of the board are colored black; the left and right edges are colored white.

On your turn, place a stone of your color on an empty point without creating any hard corners or naked attachments. A hard corner is a 2×2 pattern with two diagonally adjacent stones of the same color, one stone of the opposite color, and one empty point. A naked attachment is a 2×2 pattern with two orthogonally adjacent empty points, one black stone, and one white stone. Passing is not allowed, but, if you have no legal moves available, your turn is skipped.

You win if there is a chain of orthogonally (horizontally or vertically) interconnected stones of your color touching the two opposite board edges of your color.

I know there is always a winner when the board is full, so the question is whether the board can always fill. Here is the list of all minimal patterns with at least one empty point on which neither player can currently place a stone:

• x -    • x -    • x -    • x -    • x  
x , o    x , „    „ , o    „ , „    „ ,
- o .    - o .    - „ .    - o .    . o

x → black stone
o → white stone
„ → empty point where both players can place a stone
, → empty point where neither player can place a stone
• → empty point where only Black can place a stone
. → empty point where only White can place a stone
- → black stone, white stone or empty point

And these are the two banned patterns:

x o    Naked attachment
= =

x o    Hard corner (also illegal with reversed colors)
o =

= → empty point
$\endgroup$
5
  • $\begingroup$ Your link says "The existence of deadlocks in this game has not been disproved yet." $\endgroup$ Commented Apr 28 at 13:38
  • $\begingroup$ ...oh, the "Luis" there is you. $\endgroup$ Commented Apr 28 at 13:44
  • 2
    $\begingroup$ I'm curious, what's the deal with you and other users (Mark Steere, Alek Erikson) posting all these puzzles about loops and draws in many different connection games? $\endgroup$
    – xnor
    Commented Apr 28 at 15:27
  • 1
    $\begingroup$ We are abstract game designers who try to design games without loops or draws. When we cannot prove that our games have these features, we ask for help in places like this. $\endgroup$
    – Luis
    Commented Apr 28 at 16:23
  • $\begingroup$ The existence of deadlocks in this game has not been disproved yet, hence the question in the title. $\endgroup$
    – Luis
    Commented Apr 28 at 16:37

1 Answer 1

5
$\begingroup$

I believe the answer is

the board can always be filled, and a deadlock is not possible in this game.

Claim 1.

When a corner cell is empty, it can always be filled by one of the players.

Consider the 2x2 region containing the corner cell. If $O$ cannot play the corner cell, the region can be one of $\begin{array}{|cc} X & . \\ . & X \\\hline \end{array}$, $\begin{array}{|cc} X & . \\ . & . \\\hline \end{array}$, or $\begin{array}{|cc} . & . \\ . & X \\\hline \end{array}$. In any case, $X$ can play the corner cell.

Claim 2.

If a non-corner edge cell is empty, it can eventually be filled by one of the players.

Let's first assume that $O$ cannot play the cell. By symmetry, we can also assume that the left 2x2 region is forcing it.

  • If the current state is $\begin{array}{ccc} . & X & ? \\ X & . & ? \\\hline \end{array}$ or $\begin{array}{ccc} . & X & ? \\ . & . & ? \\\hline \end{array}$, $X$ can play the cell regardless of the cells on the right side.
  • If the current state is $\begin{array}{ccc} . & . & ? \\ X & . & ? \\\hline \end{array}$, there is one case where $X$ cannot play there either: $\begin{array}{ccc} . & . & . \\ X & . & O \\\hline \end{array}$. In this case, the cell right above the border cell is playable by at least one player: the only way to ban it for some player is by naked arrangement from above, and the opponent can always play there. Once that cell is filled, the state turns into the first case, and the border cell can be played.

Claim 3.

Starting from any game state, all border cells can be eventually filled. This is the outcome of applying claims 1 and 2 repeatedly.

Claim 4.

Once all the border cells are filled, the game state is equivalent to the one with those cells stripped away, in terms of possible moves.

In order for a 2x2 region to have two cells filled and ban a move, the only rule applicable is a hard corner. However, such position would itself be a naked attachment, which is not allowed. Therefore, the border cells cannot restrict any moves in the inner region.

Summing up all the results above, the following conclusion is reached:

Given any valid position, the players can fill up the border cells layer by layer until a grid of width 1 or 2 remains, and then fill up the corners repeatedly to completely fill the grid. This works for rectangular boards of any size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.