Algorithm for "pick the number up game"

Question

I'm struggling to get some solution, but I have no idea for that.

RobotA and RobotB who choose a permutation of the N numbers to begin with. RobotA picks first, and they pick alternately. Each turn, robots only can pick any one remaining number from the permutation. When the remaining numbers form an increasing sequence, the game finishes. The robot who picked the last turn (after which the sequence becomes increasing) wins the game.

Assuming both play optimally , who wins?

Example 1:

 The original sequence is 1 7 3. 
 RobotA wins by picking 7, after which the sequence is increasing 1 3.

Example 2:

 The original sequence is 8 5 3 1 2.
 RobotB wins by selecting the 2, preventing any increasing sequence.

Is there any known algorithm to solve that? Please give me any tips or ideas of where to look at would be really thankful!

Answer 1

Given a sequence w of distinct numbers, let N(w) be the length of w and let L(w) be the length of the longest increasing subsequence in w. For example, if

w = 3 5 8 1 4

then N(w) = 5 and L(w) = 3.

The game ends when L(w) = N(w), or, equivalently, N(w) - L(w) = 0.

Working the game backwards, if on RobotX's turn N(w) - L(w) = 1, then the optimal play is to remove the unique letter not in a longest increasing subsequence, thereby winning the game.

For example, if w = 1 7 3, then N(w) = 3 and L(w) = 2 with a longest increasing subsequence being 1 3. Removing the 7 results in an increasing sequence, ensuring that the player who removed the 7 wins.

Going back to the previous example, w = 3 5 8 1 4, if either 1 or 4 is removed, then for the resulting permutation u we have N(u) - L(u) = 1, so the player who removed the 1 or 4 will certainly lose to a competent opponent. However, any other play results in a victory since it forces the next player to move to a losing position. Here, the optimal play is to remove any of 3, 5, or 8, after which N(u) - L(u) = 2, but after the next move N(v) - L(v) = 1.

Further analysis along these lines should lead to an optimal strategy for either player.

---

The nearest mathematical game that I do know is the Monotone Sequence Game. In a monotonic sequence game, two players alternately choose elements of a sequence from some fixed ordered set (e.g. 1,2,...,N). The game ends when the resulting sequence contains either an ascending subsequence of length A or a descending one of length D. This game has its origins with a theorem of Erdos and Szekeres, and a nice exposition can be found in MONOTONIC SEQUENCE GAMES, and this slide presentation by Bruce Sagan is also a good reference.

If you want to know more about game theory in general, or these sorts of games in particular, then I strong recommend Winning Ways for Your Mathematical Plays by Berlekamp, Conway and Guy. Volume 3, I believe, addresses these sorts of games.

Answer 2

Looks like a Minimax problem.

Answer 3

I guess there is more fast solution for this task. I will think. But I can give you an idea of solution with O(N! * N^2) complexity.

At first, note that picking number from N-permutation is equivalent to the following:

1. Pick number from N-permutation. Let's it was number X.

2. Reassign numbers using rule:

1 = 1

2 = 2

...

X-1 = X-1

X = Nothing, it's gone.

X+1 = X

...

N = N - 1

And you get permutation of N-1 numbers.

Example:

1 5 6 4 2 3

Pick 2

1 5 6 4 3

Reassign

1 4 5 3 2

Let's use this one as move, instead just picking. It's easy too see that games are equivalent, player A wins in this game for some permutation if and only if it wins in original.

Let's give a code to all permutations of N numbers, N-1 numbers, ... 2 numbers.

Define F(x) -> {0; 1} (where x is a permutation code) is function which is 1 when current

player wins, and 0 if current player fails. Easy to see F(1 2 .. K-1 K) = 0.

F(x) = 1 if there is at least on move which transforms x to y, and F(y) = 0.

F(x) = 0 if for any move which transforms x to y, F(y) = 1.

So you can use recursion with memorization to compute:

Boolean F(X)
{
    Let K be length of permutation with code X.
    if you already compute F for argument X return previously calculated result;
    if X == 1 2 .. K return 0;
    Boolean result = 0;
    for i = 1 to K do
    {
         Y code of permutation get from X by picking number on position i.
         if (F(y) == 0)
         {
             result = 1;   
             break;
         }
    }
    Store result as F(X);
    return result;
}

For each argument we will compute this function only once. There is 1! permutations of length 1, 2! permutations of length 2 .. N! permutations of length N. For permutation length K, we need to do O(K) operation to compute. So complexity will be O(1*1! + 2*2! + .. N*N!) =<= O(N! * N^2) = O(N! * N^2)