Nim game question

Question

Ok, I need to make a nim game and try to find a strategy to always win with the next nim game:

21 matches, players 1 and 2 took 1, 2, 3, 4 or 5 matches in each turn, and one cannot match the match of the previous player. The winner receives a win if / when they take the last match.

I need to program something, but I don’t even understand what needs to be started. How can I find a winning strategy with this type of game?

EDIT:

So, I decided that you will always win when you get to 7 matches, which are still in the middle. Another can take 2-5, and you can add up to 7 by taking the last one. when the other accepts 1, you accept 3 (the other cannot accept 3, and then) and must choose 1 or 2, in which case you will receive the second and win.

However, the transition from 21 to 7 is a mystery to me, I cannot understand how you can always be a person who has reached 7.

EDIT 2: OK, so without the rule that you cannot take the same as the previous player, it's pretty simple, I think.

You must make k = 5 + 1 = 6. then you must make the first move so that the matches remain then% 6 = 0. Thus, in this case, first take 3, and then fill up the replenishment of another player to 6. However, in in this case, it will not work, because the other player can take 3, after which you cannot take 3 to fill up to 6. So there is my problem. Any ideas?

EDIT3:

ok, so you say that I can force 7 matches. However, suppose that I accept the same thinking until stage 14-7 matches. (then this is another twist)

There are two scenarios: 1: it takes 2-5, and I fill it up to seven, which allow 7 there, and I win. 2: it takes 1, so it remains 13. When I take 3, as I do in (7-0), it becomes 10. Then it takes 5, and I can no longer take 5 to finish, and I will lose.

Here lies the problem when scenario 2 is not a problem in the (7-0) -stage now. How to solve this?

YES, SOLUTION:

btw, na speler 1 means: after the player 1 turn, etc. (I am Dutch).

Ok, so I tried some things, and I think I have a solution. First you must accept 1 match as the first player. Then other guys can take 2-5 matches. You compare (pun intended) your amount to 7, so you will always have (21-1-7 =) 13 matches in the middle left. Then player 2 turns again, and there are two scenarios: player 2 accepts 1,2,4, or 5 matches, in which case you take so many matches that the left side will be 7. (as mentioned earlier, when you accept matches so there’s 7 left, you will 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 cannot take 3 to make 7, because you cannot take 2 times the same amount. So, you take 5, so there is 5. Player 2 then cannot take 5 to win and must choose 1-4, after which you can take the rest and win.

This is a solution, I think. I somehow came across this because I noticed this:

Normal Nim game with module, etc .:

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

But you cannot do 3.3 here, so this is liek this:

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

So you can do 7 every time, and 1 is a special case. I don’t know why, but I intuitively took 1 as a starting point, as it seems that you need to take the initiative in order to be able to control other moves. (you cannot do it twice 1, so the other should take 2-5, which allows you to control)

In any case, THANKS a lot for all the help. Also for the entire written program. I could not use it because it did not compile as a lack of good java skills :), and I also wanted to solve it myself.

Anyway, I saw that it was a wiki, luck for people in the future, trying to solve it!

Answer 1

In such games, you need to maintain the invariant of being in a winning position (if you are already in one). Therefore, you need to know how to start from a winning position, and then return to it no matter what your opponent is moving .

Here are three tips for you:

• Your running set and your opponent are one and the same: take 1, 2, 3, 4, or 5.
• This game, when you start it, is an additional game. Yes, you subtract matches, but when developing a strategy you can still think in terms of adding.
• Start with this: for any opponent, move X (where X is 1, 2, 3, 4, or 5), what step can you take to “undo” which comes out?

The concept I'm trying to find is explained in the concept of modular arithmetic , if that helps.

---

Edit: Limiting the absence of the same number of matches makes things interesting. We will have to consider this later, but first see how you agree with what I have said so far. Please feel free to comment on this.

---

Edit 2: You are right with the second board as a whole (if there was no rule on repeat moves, I mean). But your first edit was on the right track: you can make everything work in 7th.

Just keep asking and answering yourself:

Q: How can I reliably make a win for AI by making the AI ​​last?
A: Get the AI ​​to leave 7 matches, and then use your strategy to get the AI ​​to take 7th place on the left. This is because you can subtract exactly 7 matches.
Q: So, how can I make a win for the AI, making sure the AI ​​takes the last match (but seven)?

Do not overdo it. Take what you already know - what you can already do AI - and apply this step as many times as you can.

---

Edit 3: This is just a minor point that I thought it might help you solve the problem that you mentioned in your third edit.

If for all X in the chordate (1, 2, 3, 4, 5) there is a 2X match when it rotates AI, then you can make a win by taking X matches. (You described in detail how, with the exception of the other player, in your third edit)

Unfortunately, this is not something you can force, because I am saying that there are 2X matches before the AI ​​turn, while other winning strategy conditions depend on the position after the AI turns, so moving the AI ​​can force it.

Similarly, you want the result of the AI ​​move to not match the 2X value for any of these X.

Answer 2

Use a minimal algorithm , potentially with alpha beta cropping, if you need to shorten the execution time.

In fact, you are exhaustively looking through the tree of possible moves, and then returning up to select the best result.

Change Here is the code showing you how easy it is to create the perfect agent. It took about 5 minutes to encode.

 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 can check this out:

 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 explore the moves made by the ideal player.

Again, this does not show you the best strategy, but will demonstrate the optimal game against any opponent (although unverified).

Edit 2

If you are interested, from the initial state there are only 26705 terminal states (where the player won) that need to be studied. It gets smaller and smaller when you make more moves. What makes this ideal for minimax is that progress is always made ... once you remain on the heap in 15 matches, you cannot go back to 17, for example. In a game like chess, you can get cycles in the search tree, as players can simply dance around the board, return to previous states, etc.

Answer 3

Like some other data to consider, I launched my agent against all possible scenarios that might be in the game (1-21 sticks to the left in 5 possible last moves). Some of these states are impossible (for example, 20, with the last move equal to 2). I deleted most of them from the table, but most likely will remain.

If there is a value for this combination, this means that the reproduction of this movement at this point will necessarily lead to victory (provided that the ideal game continues).

Those marked with an x ​​indicate that being in this state will certainly result in loss, regardless of movement (assuming that the adversary is perfect).

  0 1 2 3 4 5 21 1 20 x 19 3 18 5 5 5 17 4 4 5 16 3 3 x 3 3 15 2 1 1 1 1 14 x 1 1 1 1 13 xxxxx 12 5 5 5 5 x 11 4 4 4 x 4 10 3 3 5 3 3 9 2 3 2 2 2 8 4 1 1 1 1 7 xxxxx 6 3 3 x 3 3 5 5 5 5 5 x 4 4 4 4 x 4 3 3 3 x 3 3 2 2 1 1 1 1 1 x 1 1 1 1 

So, if you are stuck in the analysis, you can find in this table that (or a, if there are several best moves) is the best move in this particular state.

One thing to mark jiva perfectly with your analysis so far: if this is your move and there are 7 sticks left, you are screwed! But note also 13.