Nim game question

Question

OK, I have to make a nim game and try to find the strategy to always win with the following nim game:

21 matches, player 1 and 2 each take 1, 2, 3, 4, or 5 matches each turn, and one cannot take the same amount of matches the previous player takes. Th eplayer wins if/when they take the last match.

I have to program something for this, but I don't even understand were to start. How can i find the winning strategy with this type of nim game?

EDIT:

So I figured you'll always win when you get to 7 matches still in the middle. The other can take 2-5 and you can add up to 7 taking the last one. when the other takes 1, you take 3 (the other can't take 3 as well then) and has to pick 1 or 2 in which case you'll get the alst one and win as well.

However, going from 21 to 7 is a puzzle for me i cant figure out how you can always be the person getting to 7.

EDIT 2: ok so without the rule that you can't take the same as the previous player it is quite simple i think.

You'd make k = 5 + 1 = 6. then you should make the first move such that the matches left then % 6 = 0. So in this case take 3 first and then afterwards fill up the move of the other player to 6. However in this case that won't work because the other player can take 3 after which you can't take 3 to fill up to 6. So there is my problem. Any ideas?

EDIT3:

ok so you say I can force 7 matches. However suppose I take the same thinking to the 14-7 matches step. (it then is the other's turn)

there are two scenarios then: 1: he takes 2-5 and I fill it up to seven which let 7 there and I win. 2: he takes 1, so there are 13 left. When i take 3 as i do in the (7-0)-step it becomes 10. Then he takes 5 and i can't take 5 anymore to finish and i will loose.

Here lies the problem, where scenario 2 is no problem in the (7-0)-step it is now. How do I solve this?

YES, THE SOLUTION:

btw, na speler 1 means: after player 1's turn etc (I'm dutch).

Ok so i tried some things and i think i have the solution. You have to take 1 match as the first player first. Then the other guys can take 2-5 matches. You match (pun intended) his amount up to 7 so you'll have (21-1-7=) 13 matches left in the middle always. Then it is Player 2's turn again and there are two scenarios: player 2 takes 1,2,4,or5 matches, in which case you take as much matches that there will be 7 in the left. (as told earlier when you take matches such that there are 7 left you'll always win). The second scenario is that player 2 takes 3 matches in which case there are 10 in the middle when it is your turn. You can't take 3 to make 7 because you can't take 2 times the same amount. So you take 5 so there are 5 left. Player 2 then can't take 5 to win and has to pick 1-4 after which you can take the remaining ones and win.

This is the solution i guess. I somehow came onto it because i noticed this:

Normal Nim game with modulo etc:

P2  1  2  3  4  5  
P1  5  4  3  2  1  
------------------
    6  6  6  6  6 

But you cant do 3,3 here so it is liek this:

p2 1  2  3  4  5 
p1    5  4  3  2  1
---------------------
      7  7  7  7 

So you can make 7 everytime and 1 is a special case. I don't know why but i intuitively took 1 as starting point as it feels like you need to take initiative to be able to control the other's moves. (one cannot do two times 1 so the other has to take 2-5 which makes you in control)

Anyway, THANKS a lot for all the help. Also for the whole program that was written. I couldn't use it because it wouldn't compile as a lack good java skills :) and i also wanted to solve it myself.

Anyway, i saw this is a wiki, good luck for people in the future trying to solve this!

Answer 1

In games like this, you need to maintain the invariant of being in a winning position (if you're already in one). So you need to know how to start from a winning position, and then go back to it no matter what move your opponent does.

Here are three hints for you:

1. Your moveset, and your opponent's moveset, is the same: take 1, 2, 3, 4, or 5 matches.
2. This game, when you get down to it, is an adding game. Yes, you're subtracting matches, but it still helps to think in terms of addition when you're formulating your strategy.
3. Start with this: For any opponent move X (where X is 1, 2, 3, 4, or 5), what move can you do to "cancel" that move out?

The concept I'm trying to go for is explained in the concept of modular arithmetic, in case that helps.

---

Edit: The restriction on not taking the same number of matches makes things interesting, though. We'll have to address that as a corner case later, but let's first see how you come along with what I've said so far. Please feel free to comment on that.

---

Edit 2: You're correct with the second edit in general (if the rule about no repeated moves weren't there, I mean). But your first edit was on the right track: You can make things work in 7's.

Just keep questioning and answering yourself:

Q: How do I reliably force a win for the AI by making the AI take the last match?
A: Force the AI to leave 7 matches, then use your strategy to force the AI to take the 7th one left. This is because you can force exactly 7 matches to be subtracted.
Q: So how do I force a win for the AI by making sure the AI takes the last match (but seven)?

Don't overthink it. Take what you already know-- what you can already make the AI do-- and apply that step as many times as you can.

---

Edit 3: This is just a minor point I thought of that might help you deal with the problem you mention in your third edit.

If, for all X in the moveset (1, 2, 3, 4, 5), there remain 2X matches when it's the AI's turn, then you can force a win by taking X matches. (You detailed how, except with the other player, in your third edit)

Unfortunately, this isn't something you can force because I'm talking about there being 2X matches before the AI's turn, whereas the other strategy winning conditions are contingent on the position after the AI's turn, so that the AI's move can force it.

Similarly, you want to avoid having the AI's move result in 2X matches for any of those X.

Answer 2

Use the Minimax algorithm, potentially with alpha-beta pruning if you need to cut down on the running time.

Essentially, you exhaustively search the tree of possible moves and then work back upwards to decide on the best result.

Edit: Here's some code to show you how easy it is to make a perfect agent. It took about 5 minutes to code up.

public class MinimaxNim {

    public static int getBestMove(int matchesLeft, int lastVal) {
        int max = Integer.MIN_VALUE;
        int bestMove = matchesLeft > 0 ? 1 : 0;
        for ( int move = 1; move <= 5 && move <= matchesLeft; move++ ) {
            if ( move == lastVal )
                continue;
            int val = minValue(matchesLeft - move, move);
            if ( val > max ) {
                bestMove = move;
                max = val;
            }
        }
        return bestMove;
    }

    private static int maxValue(int matchesLeft, int lastVal) {
        if ( matchesLeft == 0 ) 
            return -1; //min has won

        int max = Integer.MIN_VALUE;
        for ( int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) {
            if ( toTake == lastVal ) 
                continue;
            int val = minValue(matchesLeft - toTake, toTake);
            if ( val > max ) {
                max = val;
            }
        }
        return max;
    }

    private static int minValue(int matchesLeft, int lastVal) {
        if ( matchesLeft == 0 ) 
            return 1; //max has won

        int min = Integer.MAX_VALUE;
        for ( int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) {
            if ( toTake == lastVal ) 
                continue;
            int val = maxValue(matchesLeft - toTake, toTake);
            if ( val < min ) {
                min = val;
            }
        }
        return min;
    }
}

You could test with this:

public static void main(String[] args) {
    int count = 21;
    int move = -1;
    for ( ;; ) {
        move = getBestMove(count, move);
        System.out.println("Player 1 takes " + move);
        count -= move;
        if ( count == 0 ) {
            System.out.println("Player 1 has won");
            break;
        }
        move = getBestMove(count, move);
        System.out.println("Player 2 takes " + move);
        count -= move;
        if ( count == 0 ) {
            System.out.println("Player 2 has won");
            break;
        }
    }
}

But I would suggest replacing either player 1 or player 2 with yourself, or a random agent, so that you examine the moves that a perfect player makes.

Again, this doesn't show you the best strategy, but it will exhibit optimal play against any opponent (though untested).

Edit 2

In case you're curious, from the initial state there are only 26705 terminal states (where a player has won) that need to be examined. That gets less and less as you make more moves. What makes this perfect for minimax is that progress is always made...once you're at 15 matches left in the pile, you can't go back to 17, e.g. In a game like chess you can get cycles in the search tree since players can just dance around the board, returning to previous states, etc.