CODEWITHSUNDEEP
algorithmgame-theory
iamGrooT
iamGrooT

Reputation: 13

Finding better approach of Modified Nim

It is ultimately a game of nim with certain modification.

Rules are as follows :

There are two players A and B.

The game is played with two piles of matches. Initially, the first pile contains N matches and the second one contains M matches.

The players alternate turns; A plays first.

On each turn, the current player must choose one pile and remove a positive number of matches (not exceeding the current number of matches on that pile) from it.

It is only allowed to remove X matches from a pile if the number of matches in the other pile divides X.

The player that takes the last match from any pile wins.

Both players play optimally.

My take :

let us say we have two piles 2 7. we have 3 cases to reduce the second pile to wiz : 2 1 , 2 3 , 2 5 If A is playing optimally he/she will go for 2 3 so that the only chance left for B is to do 2 1 and then A can go for 0 1 and win the game. The crust of the solution being that if A or B ever encounters any situation where it can directly lose in the next step then it will try their best to avoid it and use the situation to their advantage by just leaving at a state 1 step before that losing stage .

But this approach fails for some unknown test cases , is there any better approach to find the winner , or any other test case which defies this logic.

Upvotes: 1

Views: 438

Answers (1)

Confused Soul
Confused Soul

Reputation: 358

This is a classic dynamic programming problem. First, find a recurrence relationship that describes an outcome of a game in terms of smaller games. Your parameters here are X and Y, where X is the number of matches in one stack and Y in the other. How do I reduce this problem?

Well, suppose it is my turn with X matches, and suppose that Y is divisible by the numbers a1, a2, and a3, while x is divisible by b1, b2, b3. Then, I have six possible turns. The problem reduces to solving for (X-a1, Y) (X-a2, Y) (X-a3,Y), (X,Y-b1), (X,Y-b2), (X, Y-b3). Once these six smaller games are solved, if one of them is a winning game for me, then I make the corresponding move and win the game.
There is one more parameter, which is whose turn it is. This doubles the size of solvable problems.
The key is to find all possible moves, and recur for each of them, keeping a storage of already solved games for efficiency.

The base case needs to be figured out naturally.

Upvotes: 1

Related Questions