### Anachor's blog

By Anachor, 7 months ago, ,

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


• +66

 » 7 months ago, # |   0 Auto comment: topic has been updated by Anachor (previous revision, new revision, compare).
 » 7 months ago, # |   0 Auto comment: topic has been updated by Anachor (previous revision, new revision, compare).
 » 7 months ago, # | ← Rev. 4 →   -10 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.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 What would be the output of this case according to your algorithm ? 1 2 XX. X.X .XX XX. X.X .XX 
•  » » » 7 months ago, # ^ |   +5 Since board states are same his algo with say 0, so Alice wins.
•  » » » » 7 months ago, # ^ |   0 Correct.
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 7 months ago, # ^ | ← Rev. 3 →   0 Bob wins and it's correct."The player that made the last move loses the game"
•  » » » » » » 7 months ago, # ^ |   0 Well, I was wrong here. But check the second sample, here we can reach the state ..X X.. XXX (by making a move in the last row , middle column)so grundy value of the initial state is going to be non-zero. But still Alice wins here.
•  » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 https://math.stackexchange.com/questions/375114/nimbers-for-mis%C3%A8re-gamesThe grundy number for misere game for terminal states isn't 0.So the grundy number of that original state in the sample is going to be 0.
 » 7 months ago, # | ← Rev. 2 →   0 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
 » 7 months ago, # |   +8 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? SolutionTurns out, the game is equivalent to tic-tac-toe on 3x3 magic square (with row, column and diagonal sum equal to 15). This means that optimal plays will lead to draw. 2 7 6 9 5 1 4 3 8
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.22548243403434753, "perplexity": 1403.446528266546}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-24/segments/1590347396089.30/warc/CC-MAIN-20200528104652-20200528134652-00159.warc.gz"}