Problem of the Month (June 2006)

This month we consider a group of combinatorial games. The two players each have a polyomino they can place. The players take turns placing copies of their polyomino on vacant squares of a board. The player who finds himself unable to move is the loser. We are interested in playing this game where both players have tetrominoes to place, and the board is one or more rectangles.

For game theory novices, the question is who wins starting from a single rectangle. For example, consider the example where is playing . Then wins no matter who starts on a 4×4 board (the unique winning move for is ). It is harder to see, but the first player can win on a 6×4 board (the unique winning move for is , and there are many winning moves for ). For each of the 15 pairs of tetrominoes, who wins starting from small rectangles? Which winning moves are unique?

For game theory experts, the question is who wins starting with more than one rectangle. To help determine this, each rectangle can be assigned a value, roughly how many moves a given polyomino wins by. Positions in which neither player can win going first are assigned value 0. In the example above, a 9×1 board has value 2 (since 2 copies of will fit), and a 3×3 board has value -1 (since 1 copy of will fit). For larger rectangles, the values are not numbers, but can be symbolized inductively with brace notation, indicating what values each player can move to. For example, a 4×2 board has value {1 | 0} since can move to a position of value 1 (by moving to ) and can move to a position with value 0 (by moving to ).

Simplifying games in brace notation is relatively hard. We give a few simple rules here that will help with most small rectangles. If a<b, {a | b} is the "simplest" number between a and b, which means the integer with the smallest absolute value if there is one, or the dyadic rational with the smallest denominator. If a>b, {a | b}, cannot be simplified, and is said to have temperature a-b. Since they pop up so often, we give a special names to {0 | 0} = *, the game with only one move by either player, and {0,* | 0,*} = **, the game with one or two moves by either player. These are equivalent to Nim piles, and have temperature 0.

When playing with more than one rectangle, a player should play in the rectangle with the highest temperature, since they have the most to gain. For example, continue our example by starting from rectangles of size 4×3, 4×2, and 7×2. The values of these rectangles are {2 | -1}, {1 | 0}, and {½ | -2} respectively. If starts, the game will go like this: , leaving value (2) + (-2) + (1) = 1, a win for . If starts, the game will go like this: , leaving value (-1) + (½) + (0) = -½, a win for . For each of the 15 pairs of tetrominoes, what are the values of small rectangles?

ANSWERS

For each of the 15 pairs of tetrominoes, a table of rectangles is given. The color of the rectangle indicates the winner (yellow = second player, white = first player, color = only that player). Unique winning moves are shown. The value of some of the rectangled are also given.

12345678910111213
1 0 0 0
*
* 		* * **
**
** 		0
***
***
2 0 0 0 0 0 0 0 0 0 0 0 0
3 0 * * * * ** ** ** 0 *** ***
4 0 * 0 * 0 *
5 0 *

12345678910111213
1 0 0 0
1
1 		1 1 2 2 2 2 3 3
2 0
-1
{1 | -1}
{* | -1}
{* | -1}
{* | -2}
3 -2
{2 | -1}
{0 | -2}
{0 | -3}
4
5

12345678910111213
1 0 0 0
1
1 		1 1 2 2 2 2 3 3
2 0
-1
{1 | 0}
{1 | -1}
{1 | -1}
{½ | -2}
3
-1
{2 | -1}
{2 | -1 + {0,*}}
4
{{2|1} | 1}
5

12345678910111213
1 0 0 0
1
1 		1 1 2 2 2 2 3 3
2 0
-1
{1 | 0}
{1 | -1}
{1 | -1}
{½ | -2}
3
-1
{2 | -1}
{2 | -1}
{2 | -2}
{1 | -1½}
4
1
5

12345678910111213
1 0 0 0
1
1 		1 1 2 2 2 2 3 3
2
-1
-1
{1 | -1}
{1 | -1}
{1 | -2}
{½ | -2}
3
-1
{2 | -½}
{2 | -½}
{2 | -1}
4 0
5

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0
*
**
** 		0
***
**** 		* 0 ***** *** ***
3
** 		0 *** * 0
4 0 0
5

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0
*
{1 | 0}
{1 | 0,*}
{1 | *}
{1+* | {0,*,{-1|1}}
3
{0,* | 0}
{1 | *}
4
5

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0
*
{1 | 0}
{1 | 0,*}
{1 | *}
{1+* | {0,*,{-1|1}}
3
{0,* | 0}
{1 | *}
{2 | {1|0}}
4
5

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2
-1
* 		{1 | -1}
{1 | -1}
{0,* | -2}
{1+* | -1+*}
3
{0,* | 0}
{1 | *}
{2 | 1+*}
4
5

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0
*
*
** 		0
***
*
* 		0
***
*** 		**
3
*
**
*** 		**** 0
4 0
** 		0
5 0

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0
*
*
** 		0
***
*
* 		0
***
***
**
3
*
**
{0,{1|0} | *}
4 0
5

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2
-1
*
{0 | -1}
{0,* | -1}
{* | -2}
3
*
**
{1 | *}
4
5

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0
*
*
** 		0
***
*
* 		0
***
***
**
3
* 		** 0 *** * * 0
4 0
*
** 		***
5 0 ***

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2
-1
*
{0 | -1}
{0,* | -1}
{* | -2}
3
*
** 		0 0
4
5 0

12345678910111213
1 0 0 0 0 0 0 0 0 0 0 0 0 0
2
*
*
** 		0
*** 		* * 0
*** 		*** **
**
3
*
** 		0
*** 		* * 0
*** 		*** **
**
4
* 		0 *** ** * 0
5 0 0 0
6
****

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 6/12/06.