Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Seems to me that the naive algorithm runs in O(2^n⋅poly(n)) time. –  Tsuyoshi Ito Dec 29 '11 at 13:36
    
From your examples, it is obvious that Alice always wins if the sequence is descending and Bob always wins if the sequence is ascending. This problem reminds me of analyzing sorting algorithms, which have been extensively studied and allow you to use a wide arsenal of tools. –  chazisop Dec 29 '11 at 13:53
1  
@chazisop: “Alice always wins if the sequence is descending”: That is the case if and only if n is even. –  Tsuyoshi Ito Dec 29 '11 at 14:09
2  
@Suresh: In the case of (2,4,1,3), the graph representation is the linear graph on 4 vertices (2-1-4-3). If Alice removes an end node, this leaves the linear graph on 3 vertices; Bob wins by removing the center vertex (so 3 is answered by 1, and 2 is answered by 4). If Alice removes an interior node, this leaves two connected vertices and an isolated node; Bob wins by removing either of the two connected vertices (so 1 is answered by 3 or 4, and 4 is answered by 1 or 2). –  mjqxxxx Dec 30 '11 at 1:32
1  
Thanks, @TsuyoshiIto! I fixed the time bound. –  JɛffE Dec 30 '11 at 1:39

4 Answers 4

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.

share|improve this answer
2  
I think that this kind of games are collectively referred to as “vertex deletion games.” But I agree with you that the winning condition is quite nonstandard in that it refers to the global property of the graph instead of local properties such as the degree of a vertex. –  Tsuyoshi Ito Dec 30 '11 at 1:43
4  
The constructed graph is called a permutation graph (en.wikipedia.org/wiki/Permutation_graph) in the literature. Some structural properties might help. –  Yoshio Okamoto Dec 30 '11 at 4:41
1  
@Yoshio: That's a good point. The permutation game is isomorphic to the graph game, but the starting graphs aren't arbitrary. So even if the general graph game is hard to analyze, it's possible that when restricted to this subclass of graphs, it becomes simpler. –  mjqxxxx Dec 30 '11 at 4:52
2  
On the other hand, the more general formulation might be easier to prove hard. Variants of vertex-deletion games are known to be PSPACE-hard, for example: emis.ams.org/journals/INTEGERS/papers/a31int2005/a31int2005.pdf –  JɛffE Dec 30 '11 at 11:35
2  
I've added a question on this kind of game specifically over at math.SE (math.stackexchange.com/questions/95895/…). Incidentally, since permutation graphs are circle graphs, an alternate formulation is the following: Players take turns removing chords from an initial set; the player that leaves a non-intersecting set of chords is the winner. –  mjqxxxx Jan 2 '12 at 20:44

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.

share|improve this answer
1  
In my answer, I noted that having a solution to this special case also solves the special case with an increasing series of decreasing runs, by playing in the "dual" position obtained by transposing the Young diagram. In particular, Eve's optimal strategy becomes "take from the largest heap, unless there are exactly two of that size", and Otto's optimal strategy becomes "take from the smallest heap". –  mjqxxxx Jan 9 '12 at 20:39
    
I am sure that this approach will lead to a perfect solution, but at the moment there still is a minor mistake, e.g. (3,1) is not losing and (3,1,1) is. The problem is that the definition of 2. should exclude this case, since we can reach a one heap position in one step. But I think this is the only problem with 2. and hopefully it is not hard to correct it. –  domotorp Jan 10 '12 at 6:09
1  
@domotorp: For (3,1), t = 0 and s = 1, so t $\not\geq$ s, and criterion (2) says that it is not a losing position. For (3,1,1), t = 0 and s = 2, so t $\leq$ s $-$ 2, and criterion (1) says that it is a losing position. I think you missed that in the definition of t, you ignore the largest heap. –  Peter Shor Jan 10 '12 at 18:17
    
Of course, I forgot that part at the end... Then this game is solved! –  domotorp Jan 11 '12 at 6:35
1  
Not a complete answer, but still worth the bounty. –  JɛffE Jan 11 '12 at 10:19

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!

share|improve this answer
1  
Can you give at least one example showing how a particular permutation is turned into a Young Tableau and how the same game (number removal until an ascending sequence is reached) is played on the Tableau? In particular I don't understand what it means to remove "one of the bottom-right squares". –  mjqxxxx Dec 30 '11 at 13:32
5  
Here is a counterexample to a weaker claim that removing a number from a permutation corresponds to a removing one of the bottom-right cells from the corresponding Young diagram (instead of Young tableau). Let n=5, and consider a position specified by the permutation [4,1,3,5,2] (that is, σ(1)=4, σ(2)=1, and so on), and remove 3 from it. The corresponding Young diagram before the move is 5=3+1+1, but the corresponding Young diagram after the move is 4=2+2, which is not obtained from removing one cell from 3+1+1. –  Tsuyoshi Ito Dec 31 '11 at 3:10
5  
And the permutation [5,4,1,2,3] has the same Young diagram as [4,1,3,5,2], but you cannot reach the Young diagram 4=2+2 from it. So the game depends on more than the shape of the Young tableau. –  Peter Shor Dec 31 '11 at 11:32
2  
Hooray for constructive misunderstanding! –  JɛffE Jan 1 '12 at 10:37
3  
@JɛffE: Yeah, this is much more useful than a proof of mere existence of misunderstanding. –  Tsuyoshi Ito Jan 3 '12 at 12:28

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.

share|improve this answer
    
Oops, my mistake. Fixed the question: g(1,3,2) = mex{g(1,3), g(1,2), g(3,2)} = mex{0, 0, *1} = *2. –  JɛffE Jan 7 '12 at 18:28
    
@JɛffE It's interesting that for $n \le 10$ SG-value of any position is not greater than 2. I'm trying to prove that now for arbitrary $n$, although I dunno how will that help. –  Dmytro Korduban Jan 7 '12 at 18:51
    
@maldini: it gives hope that the game has some nice properties, which might make it tractable. I wonder what happens to the game generalized to graphs, or the game just generalized to perfect graphs. –  Peter Shor Jan 17 '12 at 20:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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