Permutation game redux

Question

This is a restatement of an earlier question.

Consider the following impartial perfect information game between two players, Alice and Bob. The players are given a permutation of the integers 1 through n. At each turn, if the current permutation is increasing, the current player loses and the other player wins; otherwise, the current player removes one of the numbers, and play passes to the other player. Alice plays first. For example:

• (1,2,3,4) — Bob wins immediately, by definition.

• (4,3,2,1) — Alice wins after three turns, no matter how anyone plays.

• (2,4,1,3) — Bob can win on his first turn, no matter how Alice plays.

• (1,3,2,4) — Alice wins immediately by removing the 2 or the 3; otherwise, Bob can win on his first turn by removing the 2 or the 3.

• (1,4,3,2) — Alice eventually wins if she takes the 1 on her first turn; otherwise, Bob can win on his first turn by not removing the 1.

Is there a polynomial-time algorithm to determine which player wins this game from a given starting permutation, assuming perfect play? More generally, because this is a standard impartial game, every permutation has a Sprague–Grundy value; for example, (1,2,4,3) has value *1 and (1,3,2) has value *2. How hard is it to compute this value?

The obvious backtracking algorithm runs in O(n!) time, although this can be reduced to $O(2^n poly(n))$ time via dynamic programming.

Answer 1

The "permutation game" is isomorphic to the following game:

Disconnect. Players alternately remove vertices from a graph $G$. The player that produces a fully disconnected graph (i.e., a graph with no edges) is the winner.

The graph $G_{\pi}$ corresponding to a particular initial permutation $\pi\in S_n$ contains just those edges $(i,j)$ for which $i-j$ and $\pi(i)-\pi(j)$ have opposite signs. That is, each pair of numbers in the wrong order in the permutation is associated with an edge. Clearly the allowed moves are isomorphic to those in the permutation game (remove a number = remove a node), and the winning conditions are isomorphic as well (no pairs in descending order = no edges remaining).

A complementary view is obtained by considering playing a "dual" game on the graph complement $G^{c}_\pi = G_{R(\pi)}$, which contains those edges $(i,j)$ for which $i$ and $j$ are in the correct order in the permutation. The dual game to Disconnect is:

Reconnect. Players alternately remove vertices from a graph $G$. The player that produces a complete graph is the winner.

Depending on the particular permutation, one of these games may seem simpler than the other to analyze. The advantage of graph representation is that it is clear that disconnected components of the graph are separate games, and so one hopes for some reduction in complexity. It also makes the symmetries of the position more apparent. Unfortunately, the winning conditions are non-standard... the permutation game will always end before all moves are used up, giving it something of a misère character. In particular, the nim-value cannot be calculated as the nim-sum (binary XOR) of the nim-values of the disconnected components.

---

For Disconnect, it is not hard to see that for any graph $G$ and any even $n$, the game $G \cup \bar{K}_n$ is equivalent to $G$ (where $\bar{K}_n$ is the edgeless graph on $n$ vertices). To prove it, we need to show that the disjunctive sum $G + G\cup\bar{K}_n$ is a second-player win. The proof is by induction on $|G|+n$. If $G$ is edgeless, then the first player loses immediately (both games are over). Otherwise, the first player can move in either $G$, and the second player can copy his move in the other one (reducing to $G' + G'\cup \bar{K_n}$ with $|G'|=|G|-1$); or, if $n\ge 2$, the first player can move in the disconnected piece, and the second player can do the same (reducing to $G + G\cup\bar{K}_{n-2}$).

This shows that any graph $G$ is equivalent to $H \cup K_p$, where $H$ is the part of $G$ with no disconnected vertices, and $p=0$ or $1$ is the parity of the number of disconnected vertices in $G$. All games in an equivalence class have the same nim-value, and moreover, the equivalence relation respects the union operation: if $G \sim H \cup K_p$ and $G' \sim H' \cup K_{p'}$ then $G \cup G' \sim (H \cup H')\cup K_{p\oplus p'}$. Moreover, one can see that the games in $[H \cup K_0]$ and $[H \cup K_1]$ have different nim-values unless $H$ is the null graph: when playing $H + H \cup K_1$, the first player can take the isolated vertex, leaving $H+H$, and then copy the second player's moves thereafter.

I do not know any related decomposition results for Reconnect.

---

Two special types of permutations correspond to particularly simple heap games.

1. The first is an ascending run of descents, e.g., $32165487$. When $\pi$ takes this form, the graph $G_{\pi}$ is a union of disjoint cliques, and the game of Disconnect reduces to a game on heaps: players alternately remove a single bean from a heap until all heaps have size $1$.
2. The second is a descending run of ascents, e.g., $78456123$. When $\pi$ takes this form, the graph $G^{c}_{\pi}$ is a union of disjoint cliques, and the game of Reconnect reduces to a game on heaps: players alternately remove a single bean from a heap until there is only one heap left.

A little thought shows that these two different games on heaps (we can call them 1-Heaps and One-Heap, at some risk of confusion) are, in fact, themselves isomorphic. Both can be represented by a game on a Young diagram (as initially proposed by @domotorp) in which players alternate removing a lower-right square until only a single row is left. This is obviously the same game as 1-Heaps when columns correspond to heaps, and the same game as One-Heap when rows correspond to heaps.

A key element of this game, which extends to Disconnect and Reconnect, is that the duration is related to the final game state in a simple way. When it is your turn, you will win if the game has an odd number of moves remaining, including the one you're about to make. Since a single square is removed each move, this means you want the number of squares remaining at the end of the game to have the opposite parity that it has now. Moreover, the number of squares will have the same parity on all of your turns; so you know from the outset what parity you want the final count to have. We can call the two players Eve and Otto, according to whether the final count must be even or odd for them to win. Eve always moves in states with odd parity and produces states with even parity, and Otto is the opposite.

In his answer, @PeterShor gives a complete analysis of One-Heap. Without repeating the proof, the upshot is the following:

• Otto likes $1$-heaps and $2$-heaps, and can tolerate a single larger heap. He wins if he can make all heap sizes except one $\le 2$, at least without giving Eve an immediate win of the form $(1,n)$. An optimal strategy for Otto is to always take from the second-largest heap except when the state is $(1,1,n>1)$, when he should take from the $n$. Otto will lose if there are too many beans in big heaps to start with.
• Eve dislikes $1$-heaps. She wins if she can make all heap sizes $\ge 2$. An optimal strategy for Eve is to always take from a $1$-heap, if there are any, and never take from a $2$-heap. Eve will lose if there are too many $1$-heaps to start with.

As noted, this gives optimal strategies for 1-Heaps as well, although they are somewhat more awkward to phrase (and I may well be making an error in primary-to-dual "translation"). In the game of 1-Heaps:

• Otto likes one or two large heaps, and can tolerate any number of $1$-heaps. He wins if he can make all but the two largest heaps be $1$-heaps, at least without giving Eve an immediate win of the form $(1,1,\dots,1,2)$. An optimal strategy for Otto is to always take from the third-largest heap, or from the smaller heap when there are only two heaps.
• Eve dislikes a gap between the largest and second-largest heaps. She wins if she can make the two largest heaps the same size. An optimal strategy for Eve is to always take from the largest heap, if it is unique, and never if there are exactly two of the largest size.

As @PeterShor notes, it isn't clear how (or if) these analyses could be extended to the more general games of Disconnect and Reconnect.

Answer 2

In his answer, domotorp suggests analyzing a special case of the game. This special case arises when the permutation is a series of increasing sequences, each of which is larger than the following one, such as (8,9,5,6,7,4,1,2,3). In this game, you start with a collection of heaps of stones, and players alternately remove one stones from a heap. The player who leaves a single heap wins. We will say the $i$th heap has $h_i$ stones in it, and assume that the $h_i$ are given in decreasing order. For example, for the permutation above, the $h_i$ are 3,3,2,1. I tried giving the analysis of this game in the comments to domotorp's answer, but (a) I got it wrong and (b) there isn't enough room in comments to give a real proof.

To analyze this game, we need to compare two quantities: $s$, the number of heaps containing single stones and $t=\sum_{i\geq 2, h_i>2\,} h_i -2$; note that we ignore the largest heap in the sum. This is the number of stones you would have to remove to ensure that all heaps but one contain no more than two stones. We claim that the losing positions are as follows:

1. Positions where $t \leq s-2$ containing an odd number of stones.

2. Positions where $t \geq s$ containing an even number of stones.

It is easy to show that from a losing position, you must go to a winning position, since $t - s$ can only change by at most 1 each turn, and the number of stones goes down by 1 each move.

To finish showing that this is correct, we need to show that from any position which is not in category (1) or (2), the first player can in one move either reach a position in category (1) or (2), or win directly.

There are two cases:

1. Positions where $t \geq s-1$ containing an odd number of stones. Here, if $s>0$, remove a stone from a heap with a single stone. If there's only one heap left, we've won. Otherwise, we now have $t \geq s$. If there are no heaps with a single stone, remove a stone from a heap with at least three stones. (Since there were an odd number of stones, this is possible). Since $s = 0$, we have $t \geq s$.

2. Positions where $t \leq s-1$ containing an even number of stones. Here, if there are any heaps with at least two stones other than the largest heap, remove a stone from one of them. If this heap has three or more stones in it, $t$ decreases by one. If it has exactly two stones in it, $s$ increases by one. We now have $t \leq s-2$. The last case is when all the heaps except one consist of single stones; in this case, it is easy to check the first player wins if there are an even number of stones.

I've tried generalizing this strategy to the original game, and haven't figured out how to do it.

Answer 3

I've implemented an $O(2^n n)$ solution for quick hypothesis checking. Feel free to play with it. If you don't have C++ compiler locally, you can run it on different inputs remotely using "upload with new input" link.

@JɛffE It happened that (1,4,3,2) has value *1, not *2 as you suggested.

Answer 4

Edit 5th of Jan: In fact the One Heap Game described below is a special case of the problem, i.e. when the numbers follow each other in a specific way such that the first group is bigger than the second group which is bigger than the third etc. and the numbers in each group are increasing. E.g. 8, 9, 4, 5, 6, 7, 2, 3, 1 is such a permutation. So I propose to solve this special case first.

Disclaimer: I no longer claim that the below proof is correct, see e.g. the comment of Tsuyoshi which shows that deleting a number from a permutation will give a diagram not obtainable by deleting a square from the diagram of the permutation. I left the answer here to show that this approach does not work, plus since it contains another simple game.

The game has a very simple other formulation thanks to Young Tableaux. I am sure that it can be analyzed from there as other games and it will yield a linear time algorithm.

First define the following game on Young Diagrams: At each turn, if the current diagram is horizontal (all squares in one line), the current player loses and the other player wins; otherwise, the current player removes one of the bottom-right squares, and play passes to the other player.

Now order the sequence of numbers into a Young Tableaux. The main claim is that the winner of the original game is the same as the winner as the diagram game starting with this shape. To see this, notice that whenever the players delete a number, the diagram of the new sequence can be achieved by deleting a bottom-right square of the diagram. Moreover, any such diagram can be achieved by deleting the number from the respective bottom-right square. These statements follow from standard Young Tableaux theory.

Although this diagram game is simple enough, it is trivially equivalent to the following game, which seems more standard:

One Heap Game: The players are given some heaps with some pebbles in each. At each turn, if their is only one heap left, the current player loses and the other player wins; otherwise, the current player removes a pebble from a heap, and play passes to the other player.

If there is a simple solution to the heap game (and I strongly believe there is one) we also get a solution to the original game: Just put the sequence in a Young Tableaux, and transform its diagram into heaps.

Unfortunately I do not see which heap positions are winning/how to determine the Sprague–Grundy values. I checked a few cases by hand, and the following are the losing positions with at most 6 pebbles:

one heap; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2).

Anyone can solve this game?

Edit: Peter Shor can, see his answer!