Anachor's blog

By Anachor, 4 years ago, In English

Recently I came across the following problem in a contest. We tried the problem for a long time, but could not come up with a correct solution.

Alice and bob are playing a game across $$$ n \leq 10000 $$$, 3×3 Tic-tac-toe boards with both players marking the board with X. Each board already has some X's on it. One player can choose an arbitrary board and put an X on any of the empty cells. Alice always makes the first move. You can not make any further moves on a board after it has three consecutive X's (column, row or diagonal). A game ends when all the boards contain three consecutive X's. The player that made the last move loses the game.

Given a configuration of the game, you have to find out the winner. It is given that none of initial boards contain three consecutive X's.

Sample Input:

5
1
XX.
..X
..X
1
..X
X..
X.X
1
..X
.X.
.X.
1
..X
X..
XX.
1
..X
X..
..X

Sample Output:

Game #1: Alice
Game #2: Alice
Game #3: Bob
Game #4: Bob
Game #5: Bob
  • Vote: I like it
  • +66
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Anachor (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Anachor (previous revision, new revision, compare).

»
4 years ago, # |
Rev. 4   Vote: I like it -10 Vote: I do not like it

Isn't this a grundy game?

Each board have a state that can be stored in 2^9 integer (512 possible values).

Compute for each state x, the grundy number g(x). The answer is Alice will win if the xor(g(state of boards)) == 0.

Edit: States are independents, so you can pre-compute the grundy numbers for all 512 states at first.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    What would be the output of this case according to your algorithm ?

    1
    2
    XX.
    X.X
    .XX
    XX.
    X.X
    .XX
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Since board states are same his algo with say 0, so Alice wins.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Correct.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Then what about this one ?

        1
        1
        XX.
        X.X
        .XX
        

        Now his solution would tell xor is 1, so Bob wins. But here clearly Alice wins.

        Edit: I was wrong here. Bob wins in this case actually.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Bob wins and it's correct.

          "The player that made the last move loses the game"

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a generated a test file containing all possible games of 2 boards. Also, I have generated the answer for those games, by writing a brute force solution (hopefully the brute force is correct). If you want to test your solution you can find the data here: link

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I know that my comment is off-topic. But I'd like to talk about an interesting game.

The numbers from 1 to 9 are written on the board. There're two players. Players take turns. During each turn, the player takes a number (each number can be taken only once). The player who takes 3 numbers such that their sum is 15 first wins. Who will win if both play optimally?

Solution