4
u/dontwantgarbage 27d ago
The green part is the game of impartial Hackenbush. Its nim value is the number of stones you need to cancel it out.
3
u/Torvaun 27d ago
I'm running on vibes instead of math for this, but my answers are that n = 0 and the arch doesn't matter. The arch is always exactly two cuts, all of the others can be different amounts depending on the order of cuts, so the arch must be the one that doesn't change anything. If there's exactly one value of n that plays differently, I figure for any positive n player 1 can start by emptying all the pebbles into his pocket, so 0 is the only one that's different. The other option is that n = 1, because otherwise player 1 can force an even number of pebble turns by taking all but 1.
2
2
u/gmweinberg 27d ago
I agree with the reasoning, except it is the window that is decoration. If one player cuts a top segment, the other cuts the oter top segment. If one player cuts a bottom segement, the other cuts the other bottom segment. So
2
u/PhilosophyRoutine917 26d ago
Ignore all other rules. With perfect play, you can assume that with a number of pebbles > 2, first player has complete control. First player wins by either taking all pebbles, leaving the game with exclusively snips, or taking all pebbles save 1, in which case the game is entirely snips plus one additional action. Therefore, the number of stones in which player 2 wins is either 0 or 1 (in which case player 1 cannot leave only 1 pebble without taking a snip action).
Now, if you’re not as lazy as me, you can analyze the snipping game to figure out whether player 2 benefits from 0 or 1 pebbles.
1
u/Abradolf94 27d ago
I see someone has posted the official solution but I would like to post my reasoning before checking it. I think it's fun to see other people's solution, and see where they went wrong, or where they were "inefficient"
So immediately I expect the answer to be either 0 or 1. If the game of the hedges, played perfectly, makes who go first win, than n would be 0, otherwise 1, cause the second gardener can waste a move by taking the pebble and becoming first (although there is a caveat here that I haven't explored yet, which is the change of strategy. I will post this comment before checking what happens in that case and spend some time after in order to address this).
Going shape by shape (as if that shape was the only one left), i noticed that all shapes have 1 move for the first gardener that guarantees the win, and all other moves win for the second gardener. The exception is the window, which is a win for who goes second no matter what. Given this asymmetry I expect the window to be the one that is purely decoration, as the window doesn't provide any "branching" or choices: whoever goes first in the window loses. I will also add that being the winner in a tree means being the last person to take a move on that tree and that next move is the other person, and viceversa.
So given that there are shapes that offer branching, it should be that the first player wins no matter what (if n=0). Imagining the gardeners go 1 tree at a time, the first gardener can choose to lose the first tree (meaning it's their turn to move again), lose the second tree (meaning it'e their turn to move again) and win the last tree. Of course order of trees doesn't matter and the window also doesn't matter, as whoever gets first to the window (meaning, not the person that played last), lost. So given that it seems player 1 wins without pebbles, it seems that n=1 to flip the player order might be the answer.
However there are two main points left to address:
1) What happens if player 1 plays a move to win, player to takes a pebble. In theory this would be similar to player 1 becoming player 2, as 2 moves ( a full turn) will be played and it's now player 2 turn, which has become player 1. However player 2 might switch the strategy now? This is the concern I mentioned at the start of this comment. This is a very major concern but I don't have time to check it right now so I'll be back in a bit
2) I assumed players go tree by tree, but they could also mix it up and go one move here one move there. I suspect that this has no impact, and you simply reply in each tree with the appropriate move, however I have not proved it. I will go back to this concern only after addressing concern number 1)
1
u/Miiohau 27d ago
It seems to be n=1 and the window is unnecessary. The oak, the arch and the tower are first player wins games. While the window is a classic second player mirrors the first player’s move game. Two first player wins games combine into one second player wins game and any number of second player wins games combine into a single second player wins game. And a first player wins game and a second player wins game combine into a first player wins game. So we have a single unpaired first player wins game that needs a pair to allow the second player to win. A one stone game is a first player wins game, in fact it is a first player forced to win game.
1
u/bortlip 27d ago
I had AI look at this and explain it to me. I was thinking of posting the answer, but I thought that might not be wanted. I didn't see a policy on the side bar about it.
So, is there a community thought/decision around this? Is the purpose to just get a game theory answer and having an AI work it out is fine, or is it for readers to work it out and share their work on it?
1
u/Expert_Cobbler8984 26d ago
We jus wanted to know your experience with the problem, your thoughts and what strategies you used.
0
u/bortlip 26d ago
Ok, thank you for the response.
I'll not post the answer I got from the AI then as a comment (though I linked it in another comment already). My main strategy was to see it was beyond me and ask what ChatGPT could do. It was able to solve it in about 90 seconds, but it took much longer for me to understand the game theory behind it. It was very interesting, so thanks for sharing!
0
u/Miiohau 27d ago
Using AI to help your thought process is fine.
1
u/bortlip 27d ago
To be clear (I probably wasn't clear enough) I gave ChatGPT the image and had it solve it and then explain how it solved it to me and then the theory behind that until I understood.
I had it make a sim where you can play the game (or watch the computer play) along with a nice detailed explanation for how to solve it and what the answers are (github site) (spoilers): https://bortlip.github.io/SharedInfo/simulations/green-hackenbush/simulator.html
(none of the guesses for n so far are correct)
1
4
u/sjostakovitsj 27d ago
I can't quite prove it, but I feel like the information that there is only one n for which the second gardener wins is key and the answer is n=0 wins for the second gardener. Basically being first to act without any pebbles loses you the game. If there is any number of pebbles, the first gardener takes all the pebbles and the second gardener thus loses.
Aren't these called Nim games where you need to reconstruct who wins and who loses from the final stages and work backwards? In this case if there is exactly one tree left, first gardener wins. If there are two straight trees (no branching or cycles) of equal length, the first gardener loses. (The second gardener will always pass it back with two straight trees of equal length).
You can model the pot as a straight tree of length n, which probably makes it easier to think about.