[NFLSPC #2] Game

Difficulty Ratings

Idea Creativity: 3/5
Techniques Used: 2/5
Implementation : 3/5
Game Theory not possible...

Problem Link

Link in Simplified Chinese by wzy.

Simplified Statement

Given an $N \times M$ grid, where $N,M \le 10$. Initially, some cells are colored pink, some are colored purple, and some are empty.
While there is still an empty cell in the board:
1. Flip a coin. Heads show up 50% and Tails show up 50%.
2. If Heads show up, Alice will pick a cell and paint it pink.
3. If Tails show up, Bob will pick a cell and paint it purple.
Alice score is 1 if there is a path consisting of only pink cells from the left hand side of the board to the right hand side of the board, and 0 otherwise.
Bob score is 1 if there is a path consisting of only purple cells from the top side of the board to the bottom side of the board, and 0 otherwise.
Note that each cell is adjacent to its 4 neighbouring cells.
Alice wants to maximize (Alice's score - Bob's score), while Bob wants to minimize it. Find the expected value of the final score, assume Alice and Bob plays perfectly.

Solution

It looks impossible to track the game step by step and realise what changes, so lets find out a way to evaluate the final solution. There are always some cool things happening when things are symmetric.

It turns out that the answer is equal to the expected score when each empty cell is colored in pink or purple in equal probability. That is, lets define the answer to be $E$ while the expected value we get is $E'$. I will prove that $E=E'$. First I'll prove that $E' \le E$. For any stage of the game, imagine Bob has already chosen which cell to color, if Tails show up. Then, Alice will pick that cell if she head shows up. Then, Alice obtains a strategy will give $E'$ as result. Therefore $E'\le E$. However, Bob can use similar strategy, so we have $E'\ge E$. Therefore, we have proved that $E'=E$.

So we have that conclusion, what remains is some bitmask dp that can be done in $O(M*2^{2N})$. :)