Obtain the "Master of stones" title

Question

Note : the mechanisms described in this puzzle are related to those found in this question.

This is a game of 2 players.
Each player can pick up 1, 2, or 3 coins in any pile (copper , silver , gold) in their turn. The winning condition for a player is to pick up the last gold coin.
However, it is forbidden to empty a pile if there are non-empty piles of less valued coins.
(can't empty the gold pile if the silver pile is still non-empty)

At the start of the game, the initial number of coins on each pile is set as a random strictly positive number.
For each game, you have the undeniable advantage of deciding who goes first, between you and your opponent. Beware, he knows already all the tricks and will play perfectly.

Question : How can you win, given any possible combination, in the initial state ?

Example of a game :

[C1 | S4 | G1] you decide to go first  (S : -2)
[C1 | S2 | G1] he has 2 possibilities : (C : -1) or (S : -1)
[C0 | S2 | G1]  or  [C1 | S1 | G1] you respond adequally to make [0 1 1]
[C0 | S1 | G1] his turn (S: -1)
[C0 | S0 | G1] (G : -1) -> you win

Source : A stone minigame found in the video game Tales of Eternia (PSP).
The title "Master of stones" is actually granted to any player who can win this mini game.
Here, stones have been replaced by coins for differentiating the orders of the piles and the extra rule about non empty piles.

Answer 1

Let's forget about the "no emptying a stack until cheaper stacks are empty rule" for a second. In this case, the game is just three-stack Nim, except you can't remove more than three coins at a time. The solution is almost the same as Nim: compute the nim-sum C ⊕ S ⊕ G of the heap sizes, and choose to go second if and only if this sum is congruent to zero (mod 4). The winning strategy is to always ensure the sum stays zero (mod 4) after each of your moves.

Now, how do things change with the "cheaper stacks first" condition? The only difference is the bottommost gold and silver coins are sometimes illegal to remove. Let's put a mark on these two coins. By using the previous paragraph's strategy on the unmarked coins, you can ensure that you will remove the last unmarked coin. At this point, your opponent is faced with a single gold and silver coin, and loses.

The only slight hiccup is that even though you are ignoring the marked coins until the end, your opponent doesn't have to. Namely, he can remove the marked silver coin before all the unmarked gold coins are gone. If he does this, remove the number of unmarked gold coins the strategy specifies, plus the marked one.

Here is the conclusion:

You should choose to go second if and only if C ⊕ (S-1) ⊕ (G-1) is a multiple of four, where ⊕ denotes the nim-sum.

The winning strategy is to keep moving so this quantity stays a multiple of four.

Answer 2

You can determine if the initial hand is a losing one (and decide to not start).

The first losing hand is [0 1 1] and also all [4*k 1 1], [0 1+4k, 1], [0,1,1+4k] hands.

Every time it is necessary to make 2 moves to go to a losing hand, you have also a losing hand => [0+i 1+i 1], [0 1+i 1+i], [i 1 1+i].

Is [1 4 1] a losing hand? Not of the form of the losing hands, so no. You should begin.

Is [1 2 1] a losing hand? Of the form [0+i,1+i,1] with i=1, so yes. You should leave the opponent to begin the game.

Is [2 4 3] a losing hand? We can take an i of 2 => [0 4 1] which is not of the form [0 1+4k, 1], so it is a winning one. Breakdown of possible moves: [2 4 3] -> [2 1 3] -> { [1 1 3] or [0 1 3] or [2 1 2] or [2 1 1] } -> { [1 1 2] or [0 1 1] } -> { [0 1 2] or [1 1 1] or [0 0 1] } -> win this turn or make [0 1 1] and win on the next one.

Answer 3

You choose whether or not to go first, based on the results of the three piles modulo 4.

To 'win' a pile: if the # modulo 4 is 0, you want to go last, otherwise you want to go first.

To 'lose' a pile: if the # is 1 modulo 4, you want to go last, otherwise you want to go first.

Apply the following: To win the last pile, work out if you need to go first or last on it. This will tell you if you need to win or lose the preceeding pile. Apply this logic back to the first pile.

Play as follows to 'win' a pile: If this is the first move, and the pile has more than 4 stones, cut it down to 0 modulo 4. If this is not the first move, and the pile has more than 4 stones, play 4-x where x was the other player's preceeding move. If it's <4, finish it (if you can). (Note that it should never be 4 stones in your turn if you're playing to win and have chosen correctly)

Play as follows to 'lose' a pile: If this is the first move, and the pile has more than 5 stones, cut it down to 1 modulo 4. If this is not the first move, play 4-x where x was the other player's preceding move.

If you're going first, focus first on the first pile.

This technique will always ensure that you have the capacity to take (or give) the last stone. If your opponent attempts to divert onto other piles, it should be possible to just continue playing 4-x until you can force the pile to only contain 1, but I haven't proven that yet.

UPDATE:

Got it!

If your opponent starts another pile, you just have to make your second move take it to 0 or 1 modulo 4, as appropriate, depending on your goal for that pile.

The only issue with this now is if your opponent takes 1 or 2 from a pile of 4 that you can't finish yet. If this is the case, it's your move, so switch your objective on the first unfinished pile.

Answer 4

Every time you play, you play 4-number_of_stone_previously_played.

Well, we know that for if the gold pile is a multiple of 4, you want him to be first playing on it. Else, you start and leave the pile as a multiple of 4.

Now for silver row : if the gold % 4 = 0 you want to finish the pile of silver. Else you want to let him finish. So you want to start the pile of silver :

• if gold%4 = 0 && silver%4 !=0 and leave the pile of silver as silver%4=0 (after you played)

• if gold%4!=0 && silver%4=0

The choice on starting the pile i depends of either you want or not start pile i+1 and pile_i%4

Here is a table to sum up either stating or not : let's say (1,0,1) means copper%4=0, silver%4!=0 and gold%4=0 (ie pile%4=0 ->1 else 0)

here is how to make a table with all solutions : F means you have to finish pile , P mean opponent has to finish pile, S mean Start, N means play as second. let's file it from right to left.

( 1 , 0 , 1 ) ->  ( 1 , 0 , 1 ) -> ( 1 , 0 , 1 ) -> ( 1 , 0 , 1 ) -> ( 1 , 0 , 1 )  ->  ( 1 , 0 , 1 )
( | , | , |F)     ( | , | ,S|F)    ( | , |P,S|F)    ( | ,S|P,S|F)    ( |P,S|P,S|F)      (N|P,S|P,S|F)

because F under a 1 means you have to start. Starting means you have to NOT finish previous pile etc : (0,0,0) : opponent start (0,0,1) : we start (0,1,0) : we start (0,1,1) : opponent start (1,0,0) : time up i have to leave my pc (1,0,1) : (1,1,0) : (1,1,1) :