Hello Codeforces community! Hope you all are doing well.
I need some help in understanding misere version of games.
First, let's start with the classic misere nim. I have no idea why its solution works. I have seen the proof (without using Sprague-Grundy theorem) of the normal nim and it is understandable that the xor-sum = 0 state is a losing state and if I start with non zero xor-sum I can push my opponent into a xor-sum = 0 state and then my opponent cannot make a move and keep the game in a xor-sum = 0 state. Why should this even work for the misere version ?
Upon googling, I found [this](https://math.stackexchange.com/questions/375114/nimbers-for-mis%C3%A8re-games) article. While the author mentions of deleting the outdegree = 0 states and corresponding incident edges and labelling the grundy value of newly formed outdegree = 0 states as 0, the "correct answer" mentions labelling grundy value of original outdegree = 0 states as 1. The procedure of calculating grundy values for the rest of the states remains the same as in case of normal version. If I apply these to the misere nim, I obtain the following sequences respectively:
state, grundy : <1 0>, <2 1>, <3 2>, <4 3>, ... (Author)
state, grundy : <0 1>, <1 0>, <2 2>, <3 3>, <4 4>, ... ("Correct Answer")
However, neither of these sequences explain why N = 3, A = {1, 2, 3} is a losing state for First Player to move.
Next, I was trying to solve [this](https://codeforces.me/contest/1312/problem/F) problem which looks like a misere game. But the accepted solutions I have checked all did the following: rep(i, 0, 3) grundy[0][i] = 0. My question is why ? Those are winning states, right ? Then why ? And if it is true that if the grundy value of the initial state is 0 then it is a winning state then why doesn't this work for the misere nim and why would that be even true in the first place ?
I found this discussion on Codeforces about this topic, and Jakube's comments answer most of your questions. I will pick the most relevant parts to share here, but you should probably also read the original comments.
Why should this even work for the misere version [of nim]?
You can find the proof here (scroll down to Proof of Winning Strategy, and check the bottom part for misere nim). Such a correspondence between the optimal strategy of "normal" games and misere versions doesn't exist in the general case, nim is an exception.
However, neither of these sequences explain why N = 3, A = {1, 2, 3} is a losing state for First Player to move.
The reason is this: Let $$$x$$$ and $$$y$$$ be states of a normal combinatorial game (not misere), let $$$\mathrm{grundy}(x)$$$ be the grundy number of state $$$x$$$ and let $$$\{x, y\}$$$ denote the combined state of two separate games with states $$$x$$$ and $$$y$$$. Now, $$$\mathrm{grundy}(\{x, y\}) = \mathrm{grundy}(x) \oplus \mathrm{grundy}(y)$$$, where $$$\oplus$$$ is XOR. This is does not work in misere games.
We can still calculate the grundy numbers of states in misere games using the normal definition of $$$\mathrm{grundy}(x) = \mathrm{mex}(\{\mathrm{grundy(y)}\ |\ y \text{ can be reached from } x \text{ with one move}\})$$$, but combining states with XOR doesn't work.
If you wanted to see why $$$\{1, 2, 3\}$$$ is a losing state in misere nim, you would have to calculate the grundy values according to the above definition.
Next, I was trying to solve 1312F - Attack on Red Kingdom which looks like a misere game.
It's a normal game, not a misere game. From the problem statement: The King who launches the last attack will be glorified as the conqueror of the Red Kingdom. In misere games, the player who moves last, loses. In this problem, the player who moves last, wins.
Understood. Thanks for the clear explanation.