Problem with checker for task 180 (Simple Game of Sticks)
Back to General discussions forum
Hello everyone,
I think that the checker for task 180 (Simple Game of Sticks) is incorrect.
For some reason checker thinks that the position 4 5 4 4 5 5 is lost and answer should be 0.
But I can prove that this position is a win.
Undeed, given initial position:
| | | | | | | | | | | | | & | | | | | | | | | | | | | |
We can play:
| | | | | | | | | | | | | & | | | | | | | | | | | | | -
Effectively getting two identical sub-games (which I separate by &) and taking the initiative. Now, no matter what opponent plays in one sub-game, we can mirror his/her action in another sub-game, maintaining the initiative. For example, opponent can play:
| - - | | | | | | | | | | & | | | | | | | | | | | | |
And we respond with:
| | | | | | | | | | | & | - - | | | | | | | | | |
Opponent can play:
| | | | | | | | - | | & | | | | | | | | | | |
And we respond with:
| | | | | | | | | | & | | | | | | | | - | |
Such mirroring continues until all piles are of size 1, except one. For example, at some point opponent plays:
| | | | | | | - & | | | | | | | |
...and we should not mirror here (this would be a mistake), but instead take both sticks from remaining non-unit pile:
| | | | | | | & | | | | | | - -
...and then players alternate taking sticks one by one until only one stick remains. At this point, it is opponent's turn and he/she is forced to take the last stick. We win.
There is a flaw in your argument. If you follow your approach, the second player might end up with the following position:
IIII IIII
This is indeed a winning position for the second player, as they can leave the first player the following position:
I I IIII
Which is essentally:
IIII
And this is lost for the player who has to do the next move.
Hello, gardengnome.
I said:
Such mirroring continues until all piles are of size 1, except one.
And there is some equilvalence class of size 1 piles in this game... How can I tell you more without spoiling the solution? Maybe by email?
gardengnome, what your solution outputs for 4 5 4 4 5 5. Does it output 0 as well as checker?
Let's go back a couple of steps then. The following position is a win for the player who goes next:
I I IIII I I IIII
My understanding of your approach is this is a position that the second player might encounter.
This position is not possible if we follow my approach. I repeat again:
Such mirroring continues until all piles are of size 1, except one.
You continued mirroring to get to such position.
And you did not answer to my question for your output for 4 5 4 4 5 5.
Sorry, didn't see the question until a refresh.
My solution reports result 0 for 4 5 4 4 5 5.
And why can 1 1 4 1 1 4 not be reached as a position where the second player has the next move according to your rules?
There is symmetrie and there are still two piles with more than one stick.
There are no piles with more than one stick in your example, but I refuse to explain it better to not spoil the solution to others...
Rodion, can you unblock me for a moment, so I can write more detailed comment for gardengnome in submission for this problem? I know that only those who solved the task can see submissions.
Hi there! Actually I noticed few days ago that your account is blocked and being unable to recollect how it happened, I unblocked it then - so feel free to go on please, have fun! :)
Looking forward to the more detailed discussion. We seem to have our wires crossed at the moment.
Rodion, thanks you much for rescuing my account!
gardengnome, submission for task 180 is done, you are free to play my bot and prove me wrong by winning position described above as second player.
You can play manually or write your bot as subclass of YourBot.
Just submitted my Python solution. It beats your bot for the position in question. :)
Starting position: | | | | | | | | | | | | | | | | | | | | | | | | | | |
...
You managed to beat Qwerty. Congratulations!
FWIW, I was easily able to beat the bot using the starting arrangement 4 5 4 4 5 5 and the bot going first, using exactly the approach Mathias has indicated above.
Qwerty, the flaw in your logic is that "the last remaining non-unit pile" is not guaranteed to have "both" sticks to take.
P.S. If a problem has been correctly solved by 49 people, perhaps it's likely that the checker works fine.
by 49 people
By 50 people actually... I do not have a 100% working solution yet, but managed to pass by luck, so I can study the closed topic.
I will give you my conclusion after analysing the game with GardengnomeBot.
Here is my conclusion.
My mistake was that I studied theory for Nim game, but this game is different. The key difference is that the number of sticks one can take from pile is limited, so we cannot take all sticks from remaining not-unit pile in some cases, as zelevin pointed out.
As Nim theory does not work here, is seems there are no fancy maths to help, and the only way to solve this problem is by brute force, as gardengnome demonstrated in closed topic.
Thanks to you all for helping me understand the problem better!
there are no fancy maths to help
Ahh, but there are!
I'll continue this conversation in the private thread.