game theory algorithms: how to proceed

Question

Take an example: Permutation Game(interviewstreet.com). I would like to know how do I proceed in such questions.

P.S.: Please don't post the full algorithm(as that would spoil the fun), just a few pointers.

Answer 1

I would setup a small game with a small N and a random permutation and then draw a complete Alpha-Beta Tree...

http://en.wikipedia.org/wiki/Alpha-beta_pruning

of all possible moves, and then work bottom-up making the optimal choice for each player at each point.

Then generalize from there once you see the pattern.

In game theory terminology you need to use Backward Induction to find the Subgame Perfect Equilibrium.

Answer 2

N is rather small. In each turn, there are two possibilities for each number: remove that number or don't remove that number. Try both possibilities, resulting in an O(N*2^N) algorithm for each test case. In practice this will be lower since the game usually ends before all numbers are removed and you can cut the search short quite often.

So you want a backtracking function that tries all possibilities of removing the numbers and returns 1 if Alice wins and 2 if Bob wins. At depth k (first depth is k = 0), if k % 2 = 0, then it's Alice's turn. She wins if all the immediate recursive calls (that have depth k + 1) return 1. If at least one of them returns 2, then she loses, because there is at least one way for Bob to win.

Example run on 1 3 2:

k = 0 - Alice removes 1:
    k = 1 - Bob removes 3 => Bob wins because only 2 remains
          - Bob removes 2 => Bob wins because only 3 remains (note: this step
            is not needed, as Bob already proved he can win at this k = 1)
      - Alice removes 3 => Alice wins because 1 2 is increasing
      - Alice removes 2 => Alice wins because 1 3 is increasing

So Alice definitely has a winning strategy (when both play optimally) if she removes 3 or 2 in the first move, because the recursive branches of these two never give Bob as the winner.

Example run on 5 3 2 1 4 (partial run):

k = 0 - Alice removes 5
    k = 1 - Bob removes 3
        k = 2 - Alice removes 2 => 1 4 => Alice wins
    k = 1 - Bob removes 2
        k = 2 - Alice removes 3 => 1 4 => Alice wins
    k = 1 - Bob removes 1
        k = 2 - Alice removes 3 => 2 4 => Alice wins
    k = 1 - Bob removes 4
        k = 2 - Alice removes 3
            k = 3 - Whatever Bob removes, he wins
        k = 2 - Alice removes 2
            k = 3 - Whatever Bob removes, he wins
        k = 2 - Alice removes 1
            k = 3 - Whatever Bob removes, he wins
  ...

As you can see, there is at least one way for Bob to end up winning if Alice starts by removing 5. If you do the same for her other possibilities, you will probably get the same result. Thus, it's Bob who will definitely win if he plays optimally.

Answer 3

Pen and Paper

Use pen and paper, make sure you understand the rules of the game exactly, then think of all possible strategies for the game.

For a relatively simple problem like this, think backwards from the point when game is won, unrolling one step at a time and making sure the player who made that step could not have made a better step, that's the optimality requirement.

For more complicated problems, read up Wikipedia on game theory.