Synchronized Triomineering on Rectangular Boards

Abstract

In synchronized games players make their moves simultaneously rather than alternately. Synchronized Triomineering is the synchronized version of Triomineering, a variant of a classical two-player combinatorial game called Domineering. New theoretical results for the $n \times 11$ board are presented.

1 Introduction

The game of Domineering is a typical two-player game with perfect information, proposed around 1973 by Göran Andersson [3, 12, 13]. The two players, usually denoted by Vertical and Horizontal, take turns in placing dominoes ($2 \times 1$ tile) on a checkerboard. Vertical is only allowed to place its dominoes vertically and Horizontal is only allowed to place its dominoes horizontally on the board. Dominoes are not allowed to overlap and the first player that cannot find a place for one of its dominoes loses. After a time the remaining space may separate into several disconnected regions, and each player must choose into which region to place a domino.

Berlekamp [2] solved the general problem for $2 \times n$ board for odd $n$. The $8 \times 8$ board and many other small boards were recently solved by Breuker et al. [5] using a computer search with a good system of transposition tables. Subsequently, Lachmann et al. solved the problem for boards of width 2, 3, 5, and 7 and other specific cases [14]. Finally, Bullock solved the $10 \times 10$ board [6].

The game of Triomineering was proposed in 2004 by Blanco and Fraenkel [4]. In Triomineering Vertical and Horizontal alternate in tiling with a straight triomino ($3 \times 1$ tile) on a checkerboard. Blanco and Fraenkel calculated Triomineering and values for boards up to $6$ squares and small rectangular boards.

2 Synchronized Games

For the sake of self containment, we recall the previous results concerning synchronized games. Initially, the concept of synchronism was introduced in the games of Cutcake [8], Maundy Cake [9], and Domineering [1, 10] in order to study combinatorial games where players make their moves simultaneously.

As a result, in the synchronized versions of these games there exist no zero-games (fuzzy-games), i.e., games where the winner depends exclusively on the player that makes the second (first) move. Moreover, there exists the possibility of a draw, which is impossible in a typical combinatorial game.

In the game of Synchronized Triomineering [7, 11], a general instance and the legal moves for Vertical and Horizontal are defined exactly in the same way as defined for the game of Triomineering.

There is only one difference: Vertical and Horizontal make their legal moves simultaneously, therefore, triominoes are allowed to overlap if they have a $1 \times 1$ tile in common. We note that $1 \times 1$ overlap is only possible within a simultaneous move.

At the end, if both players cannot make a move, then the game ends in a draw, else if only one player can still make a move, then he/she is the winner.

For each player there exist three possible outcomes:

• The player has a winning strategy ($ws$) independently of the opponent’s strategy, or

• The player has a drawing strategy ($ds$), i.e., he/she can always get a draw in the worst case, or

• The player has a losing strategy ($ls$), i.e., he/she does not have a strategy either for winning or for drawing.

Table 1 The possible outcomes in Synchronized Triomineering

Table 1 shows all the possible cases. It is clear that if one player has a winning strategy, then the other player has neither a winning strategy nor a drawing strategy. Therefore, the cases ws−ws, ws−ds, and ds−ws never happen. As a consequence, if $G$ is an instance of Synchronized Triomineering, then we have six possible legal cases:

• $G = D$ if both players have a drawing strategy, and the game will always end in a draw under perfect play, or

• $G = V$ if Vertical has a winning strategy, or

• $G = H$ if Horizontal has a winning strategy, or

• $G = VD$ if Vertical can always get a draw in the worst case, but he/she could be able to win if Horizontal makes an unlucky move, or

• $G = HD$ if Horizontal can always get a draw in the worst case, but he/she could be able to win if Vertical makes an unlucky move, or

• $G = VHD$ if both players have a losing strategy and the outcome is totally unpredictable.

3 Examples of Synchronized Triomineering

The game always ends in a draw, therefore $G = D$.

In the game

Vertical has a winning strategy moving in the second (or in the third) column, therefore $G = V$.

In the game if Vertical moves in the first column we have two possibilities therefore, either Vertical wins or the game ends in a draw. Symmetrically, if Vertical moves in the third column we have two possibilities therefore, either Vertical wins or the game ends in a draw. It follows $G = VD$.

Symmetrically, in the game either Horizontal wins or the game ends in a draw therefore, $G =HD$.

In the game each player has $4$ possible moves. For every move of Vertical, Horizontal can win or draw (and sometimes lose); likewise, for every move by Horizontal, Vertical can win or draw (and sometimes lose). As a result it follows that $G = VHD$.

4 New Results

In the previous works [7, 11] the $n\times 4$, $n \times 5$, $n \times 7$, and $n \times 8$ boards have been solved. In this section the solution for the $n \times 11$ board is presented.

Theorem 1

Let $G$be a$n \times 11$board of Synchronized Triomineering with $n \ge 41$. Then, Vertical has a winning strategy.

Proof

In the beginning, Vertical will always move into the third, the sixth, and the ninth column of the board, i.e., $(m, c)$, $(m+1, c)$, $(m+2, c)$, $(m, f)$, $(m+1, f)$, $(m+2, f)$, $(m, i)$, $(m+1, i)$, and $(m+2,i)$, where $m \equiv 1 \,({\text{mod 3}})$, as shown in Fig. 1.

When Vertical cannot move anymore into the third, the sixth, and the ninth column, let us imagine that we divide the main rectangle into $3 \times 11$ sub-rectangles starting from the top of the board (by using horizontal cuts). Of course, if $n \not \equiv 0 \,({\text{mod 3}})$, then the last sub-rectangle will be of size either $1 \times 11$ or $2 \times 11$, and Horizontal will be able to make respectively either three more moves or six more moves.

We can classify all these sub-rectangles into $22$ classes according to:

• The number of vertical triominoes already placed in the sub-rectangle (vt),

• The number of horizontal triominoes already placed in the sub-rectangle (ht),

• The number of moves that Vertical is able to make in the worst case, in all the sub-rectangles of that class (vm),

• The number of moves that Horizontal is able to make in the best case, in all the sub-rectangles of that class (hm),

as shown in Table 2. We denote with $|A|$ the number of sub-rectangles in the $A$ class, with $|B|$ the number of sub-rectangles in the $B$ class, and so on. The value of vm in all the sub-rectangles belonging to the class E, F, G, J, K, and P considered as a group is

$$\begin{aligned} 5|E| + 3|F| + |G| + 2|J| +\lceil 3|K|/4 \rceil + \lceil 3|P|/4 \rceil \end{aligned}$$

The last statement is true under the assumption that Vertical moves first into the sub-rectangles of class E, F, G, and J as long as they exist, and after into the sub-rectangles of the class K and P. When Vertical cannot move anymore into the third, the sixth, and the ninth column, both Vertical and Horizontal have placed the same number of triominoes, therefore

$$\begin{aligned} 3|A|+2|B|+|C|+|E|&= |G|+2|H|+3|I|+|J| \nonumber \\&\quad + 2|K|+3|L|+4|M|+5|N| \nonumber \\&\quad +6|O|+3|P|+4|Q|+5|R| \nonumber \\&\quad + 6|S|+7|T|+8|U|+9|V| \end{aligned}$$

(1)

Let us prove by contradiction that Vertical can make a larger number of moves than Horizontal. Assume therefore

$$\begin{aligned} moves(V) \le moves(H) \end{aligned}$$

using the data in Table 2

$$\begin{aligned}&8|A| + 6|B| + 4|C| + 2|D| \\&\quad +5|E| + 3|F| + |G| + 2|J| \\&\qquad +\lceil 3|K|/4 \rceil + \lceil 3|P|/4 \rceil \le 2|E|+2|F|+2|G|+|H| \\&\qquad \qquad \qquad \qquad \qquad +\, 4|J|+4|K|+3|L|+2|M| \\&\qquad \qquad \qquad \qquad \qquad +\, |N|+6|P|+5|Q|+4|R| \\&\qquad \qquad \qquad \qquad \qquad + \,3|S|+2|T|+|U|+6 \end{aligned}$$

and applying Eq. 1

$$\begin{aligned}&2|A|+2|B|+2|C|+2|D|+|E|+|F|+|G|+3|H|\\&\quad + 6|I|+ \lceil 3|K|/4 \rceil + 3|L|+6|M|+9|N|+12|O|\\&\quad +\lceil 3|P|/4 \rceil +3|Q| +6|R| +9|S| +12|T| + 15|U| + 18|V| \le 6 \end{aligned}$$

which is false because

$$\begin{aligned}&|A|+|B|+|C|+|D|+|E|+|F|+|G|\\&\quad +|H|+|I|+|J|+|K|+|L|+|M|+|N| \\&\quad +|O|+|P|+|Q|+|R|+|S|+|T|+|U|+|V| = \lfloor n/3 \rfloor \end{aligned}$$

and by hypothesis $n \ge 41$. Therefore, $moves(V) \le moves(H)$ does not hold and consequently $moves(H) < moves(V)$. We observe that if $n \equiv (3)$, then the theorem holds for $n \ge 22$ and if $n \equiv (3)$, then the theorem holds for $n\ge 3$.

$\square$

Fig. 1

Vertical strategy on the $n \times 11$ board of Synchronized Triomineering

Table 2 The $22$ classes for the $3 \times 11$ sub-rectangles

By symmetry the following theorem holds.

Theorem 2

Let $G$ be a $11 \times n$ board of Synchronized Triomineering with $n \ge 41$. Then, Horizontal has a winning strategy.