Treblecross

Problem Name: Treblecross
UVa ID: 10561
LightOJ ID: 1229
Keywords: game theory, impartial game, sprague-grundy numbers

Quoting from the problem description:

Treblecross is a two player game where the goal is to get three X in a row on a one-dimensional board.

This can be recognised as a finite impartial game (finite meaning that it is not possible to keep playing it forever). This means that it can be analysed using the Sprague–Grundy theorem. This is very much related to the game of nim and many other impartial games. For those who are not yet familiar with these topics I can highly recommend the following article that does an excellent job explaining the basics of it: Sprague–Grundy theory.

What makes this problem interesting is that it’s one of those cases where the method to apply the Grundy theory is not very apparent at first, because it doesn’t look very much like just another variant of the classic nim game. And yet, the theory tells us that is should be possible to transform this game’s rules into something that can be modelled as a combination of nim games. Let’s try to do that.

But before going into the main rules, let’s stop for a second to notice one important thing: the problem gives us an arbitrary configuration for a game (which could be after having played a few rounds), and we have to identify all position from which a win is possible, given that both players play optimally. This is significant for one reason, which is that, unlike a fresh new game, an arbitrary game configuration could have trivial win positions. By trivial win positions I’m referring to any positions where placing an X ends the game with a win for the first player in just one move. Those positions don’t really fit into the theory discussed further below, so we better handle those as special cases right away. For example, in the following test case:

Positions 4, 7 and 10 are trivial wins. With that out of the way, we can concentrate on a game without trivial wins, which makes it possible to apply the Grundy number theory.

Let’s consider the following example:

One notable observation is this: an ideal move would never be done on a position closer than 3 cells to any X already on the board. In the example above, placing an X into any position other than 6 will give the opponent a trivial win. So, we consider any position at a distance of 1 or 2 to the closest X as unplayable, and now we see that the first player has only one possible move which is the 6. In fact, that move guarantees a win, because no matter what the other player does next, it will give us a trivial win in the following turn.

This already gives us a major piece of the puzzle of how to transform any arbitrary treblecross game, into a nim game. Let’s describe a treblecross game as a sequence of integer numbers that represent the length of all “open intervals” in the board in order. For example, the previous example would be denoted \((2, 5, 2)\). The other major piece of the puzzle is this: an open interval of length \(L\) is equivalent to a single treblecross game with a clean board of size \(\text{max}(0, L - 2x)\) where \(x\) is the number of X’s that surround the open interval. For example, the open interval 1 to 2 has 1 surrounding X, while the interval 4 to 8 has 2.

So, the game \((2, 5, 2)\) is equivalent to the combination of three separate games \(\{ (0), (1), (0) \}\) and, as the game theory tells us, if we know the “nim number” or nimber of each separate game, then we can know the nimber of their combination by simply applying the XOR operation.

All that is left now is calculating the S.G. numbers (or nimbers, as we have called them) of all possible “clean board” games of treblecross. Here’s a table that includes the first few cases:

To come up with this table, you just have to notice that placing an X anywhere on a clean board splits the game into two. The second column of the table has the list of reachable configurations, which are the games that can result after a single move from the game in the first column. Note how the \((4)\) game is the first one to reach a configuration with a \((1)\), because of the \(\text{max}(0, L - 2x)\) rule. The way those reachable positions are combined and how the new nimber is selected by applying the S.G. theorem is left as an exercise to the reader.

To summarise, the solution to this problem involves calculating the S.G. numbers of treblecross games of all sizes up to 200. Then, for each test case, the open intervals have to be identified, and then for each position with a dot, you calculate what would be the resulting intervals if an X would be placed there, and that gives you a new nimber. If that nimber is 0, then that position has to be printed, because the game is winnable from there. Make sure, however, not to include positions that give trivial wins to the next player. For example, in the game \((2, 5, 2)\) discussed above, if you place an X on position 5, you would find that the resulting intervals are \((2, 1, 3, 2)\) which you might turn into the combination of games \(\{ (0), (0), (0), (0) \}\), which has the nimber 0. But that position is not a good move because it gives a trivial win to the opponent.

One last tip. To simplify the calculation of the intervals with the \(\text{max}(0, L - 2x)\) rule, you can imagine an extended board, with three additional positions at each end. And then place an X on the very first and last positions of that extended board. Then the conversion of all intervals into a single treblecross game would be simply \(\text{max}(0, L - 4)\).