1908. Game of Nim

MediumBit ManipulationBrainteaserArrayMathDynamic ProgrammingGame Theory
Leetcode Link

Problem Description

In this game-themed problem, we have two players, Alice and Bob, who are playing a turn-based game involving piles of stones. There are n piles of stones, and on each player's turn, that player must remove any positive number of stones from any one pile. If a player can't make a move (which happens when all piles are empty), they lose. The twist in the problem comes from the assumption that both players will make the best possible move at any point in the game, meaning they play optimally. The task is to determine if Alice, who always goes first, will win the game given the initial number of stones in each pile represented by an integer array piles, where piles[i] specifies the number of stones in the ith pile.

Intuition

The problem is a variant of the classical game theory problem known as Nim. The key to solving this sort of problem lies in understanding the optimal strategies that players can employ and the winning positions in such a game.

A fundamental concept in playing Nim optimally is the Nim-sum, or the bitwise XOR sum of the number of stones in each pile. If the Nim-sum is 0 at the beginning of a player's turn, that player is in a losing position (assuming both players play perfectly). This is because no matter what move they make, the opponent can always return the game to a state where the Nim-sum is 0, putting the initial player back into a losing position on their next turn.

Therefore, if the Nim-sum of all the pile sizes is not 0 when it's Alice's turn (which is the case at the start of the game since she goes first), then Alice can make a move that forces a 0 Nim-sum on Bob's turn, putting her in a winning position from the start.

As the problem assumes optimal play from both Alice and Bob, we can deduce the winner by calculating the Nim-sum of all the pile sizes.

Although the provided solution code uses a depth-first search (DFS) approach, which can handle variations of the problem where the rules of play diverge from classical Nim, for this specific problem, a simplified solution would compute the Nim-sum, like so:

1class Solution:
2    def nimGame(self, piles: List[int]) -> bool:
3        xor_sum = 0
4        for pile in piles:
5            xor_sum ^= pile
6        return xor_sum != 0

This code simply iterates over the piles and computes the cumulative XOR. If the result is non-zero, Alice wins, since she can always make a move to set the Nim-sum to 0 for Bob; if it is zero, Bob wins by maintaining the 0 Nim-sum position through each of his turns.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The reference solution provided uses a recursive DFS approach to simulate every possible state of the game. Although for the specific game rules provided, there is a more efficient solution as explained earlier, this approach can handle a wider variety of game rules where the winning strategy might not be straightforward.

Here's a walk-through of the provided DFS solution:

  1. The dfs function is defined within the context of the nimGame method. It is decorated with @cache, which is a Python decorator that automatically memoizes the results of the function calls. Memoization ensures that repeated states of the game are not re-evaluated, which optimizes the solution by reducing the number of recursive calls.

  2. The dfs function is intended to be called with a tuple st representing the current state of the game, i.e., the number of stones in each pile. It converts st into a list lst for easier manipulation since tuples are immutable.

  3. The dfs function then iterates over every pile lst[i] and for each pile tries removing every possible positive number of stones j (from 1 to the pile's size inclusive). This simulates all potential moves a player could make.

  4. After simulating the move (removing j stones from pile i), dfs recursively checks whether this state leads to a losing state for the opponent by calling not dfs(tuple(lst)). If a losing state for the opponent is found, then the current state is winning, hence it returns True.

  5. If no move leads to an immediate winning state, the dfs function returns False, indicating that any opponent's response to the current state can at most prolong the game, but eventually the current player will lose.

  6. nimGame calls dfs using the initial state tuple(piles) and returns the result. If the result is True, it means Alice can win starting from the initial state; otherwise, if it's False, Bob will win.

The beauty of this approach is that it considers the entire space of possible moves and outcomes, and it ensures that we do not overlook any strategy that could lead to a win. However, as mentioned, the specific problem of Nim has a well-known mathematical solution, which is more efficient than the general DFS approach.

Nonetheless, the DFS approach is a powerful technique when dealing with complex decision-making problems in games or situations where optimal strategies are not known in advance. It provides a methodical way to explore all possible outcomes and determine the best sequence of actions when players are acting optimally.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

Let's consider a small example where there are 3 piles of stones with the following number of stones in each pile: piles = [1, 3, 5]. We will use this example to illustrate the solution approach.

  1. At the beginning of the game, the Nim-sum is calculated by performing a bitwise XOR operation of the numbers of stones in each pile: 1 ^ 3 ^ 5.

  2. Performing the calculation gives us 1 ^ 3 = 2 and then 2 ^ 5 = 7. Since 7 is not equal to 0, Alice can make a move to leave the Nim-sum at 0 for Bob.

  3. To find Alice's optimal move, we can look at the binary representation of the pile sizes and compare it with the Nim-sum. Let's do this:

    • The binary representation of the piles: 1 -> 001, 3 -> 011, 5 -> 101
    • The binary representation of the Nim-sum 7: 111
  4. Alice will try to make a move that results in a new state with a Nim-sum of 0. She can do this by choosing a pile and removing enough stones to turn the current Nim-sum (111) to 000. For example, Alice can remove 4 stones from the third pile (5 stones), which gives us a new state of [1, 3, 1].

  5. The new Nim-sum after Alice's move is 1 ^ 3 ^ 1, which equals 0, since 1 ^ 1 = 0 and 0 ^ 3 = 3 and finally 3 ^ 0 = 3, and in binary, 3 is 011, which will result back to 0 once XOR'ed with itself during Bob's turn.

  6. Now it is Bob's turn, and since the Nim-sum is 0, any move he makes will leave a non-zero Nim-sum for Alice to exploit.

  7. If Bob removes 1 stone from any pile, the piles may look like [1, 2, 1]. Alice can then remove 2 stones from the second pile, leaving a single stone in two piles: [1, 1, 1], which has a Nim-sum of 0 again.

  8. Ultimately, no matter how Bob plays, if Alice starts with a non-zero Nim-sum and both play optimally henceforth, Alice will always be able to return the game to a state where the Nim-sum is 0 at Bob's turn.

Using this example, we can see that the decision on the first move is crucial: given a non-zero Nim-sum, there is always a winning strategy for the player making the first move. Alice wins this game if she follows the strategy of always making a move to return the game to a state with a Nim-sum of 0 at the end of her turn.

Solution Implementation

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def nimGame(self, piles: List[int]) -> bool:
6        # Apply memoization to avoid recomputation of the same game states
7        @lru_cache(maxsize=None)
8        def can_win(st):
9            # Convert tuple to list to modify the piles
10            piles_list = list(st)
11            # Iterate over each pile
12            for i, pile in enumerate(piles_list):
13                # Try removing 1 to pile stones from the current pile
14                for stones_removed in range(1, pile + 1):
15                    # Remove the stones for the current move
16                    piles_list[i] -= stones_removed
17                    # Check if opponent would lose from this state
18                    if not can_win(tuple(piles_list)):
19                        return True  # If opponent loses, current player wins
20                    # Undo the move
21                    piles_list[i] += stones_removed
22            # If no winning move, return False
23            return False
24
25        # Start the game with the initial piles configuration
26        return can_win(tuple(piles))
27
28# Example usage:
29# sol = Solution()
30# result = sol.nimGame([1, 2, 3])  # Pass the initial piles as a list
31# print(result)  # Outputs True or False depending on whether you can win the Nim game
32
1import java.util.Map;
2import java.util.HashMap;
3
4class Solution {
5    // Initialize a memoization map to store computed game states
6    private Map<Integer, Boolean> memoization = new HashMap<>();
7    // 'powersOfEight' array will store the powers of 8 (1, 8, 64, ...) for encoding the game state
8    private int[] powersOfEight = new int[8];
9
10    public Solution() {
11        // Precompute the powers of 8 up to 8^7
12        powersOfEight[0] = 1;
13        for (int i = 1; i < 8; ++i) {
14            powersOfEight[i] = powersOfEight[i - 1] * 8;
15        }
16    }
17
18    // Method to determine if the current player can win the nim game given the piles
19    public boolean nimGame(int[] piles) {
20        return depthFirstSearch(piles);
21    }
22
23    // Private method for a recursive depth-first search to simulate all possible moves
24    private boolean depthFirstSearch(int[] piles) {
25        // Calculate a unique state hash for the current state of the piles
26        int stateHash = computeStateHash(piles);
27        // If this state has been encountered before, return the stored result
28        if (memoization.containsKey(stateHash)) {
29            return memoization.get(stateHash);
30        }
31      
32        // Try reducing each pile by a number of stones and perform DFS on the new state
33        for (int i = 0; i < piles.length; ++i) {
34            for (int stonesToRemove = 1; stonesToRemove <= piles[i]; ++stonesToRemove) {
35                piles[i] -= stonesToRemove;
36                // If the opponent cannot win after our move, we found a winning move
37                if (!depthFirstSearch(piles)) {
38                    piles[i] += stonesToRemove; // Undo the move
39                    memoization.put(stateHash, true); // Memoize the winning result
40                    return true;
41                }
42                piles[i] += stonesToRemove; // Undo the move before trying next move
43            }
44        }
45
46        // If no winning move is found, this is a losing state
47        memoization.put(stateHash, false);
48        return false;
49    }
50
51    // Computes a unique hash for the current state of the piles using powers of 8
52    private int computeStateHash(int[] piles) {
53        int stateHash = 0;
54        // Encode the piles' state into a single integer using base 8 representation
55        for (int i = 0; i < piles.length; ++i) {
56            stateHash += piles[i] * powersOfEight[i];
57        }
58        return stateHash;
59    }
60}
61
1#include <vector>
2#include <unordered_map>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9    bool nimGame(vector<int>& piles) {
10        unordered_map<int, int> memo; // Store calculated game results to avoid recomputation.
11        int powerOfEight[8] = {1}; // Precomputed powers of 8 for state encoding.
12        for (int i = 1; i < 8; ++i) {
13            powerOfEight[i] = powerOfEight[i - 1] * 8;
14        }
15
16        // Function to encode the current state of piles as a single integer.
17        auto encodeState = [&](vector<int>& piles) {
18            int state = 0;
19            for (int i = 0; i < piles.size(); ++i) {
20                state += piles[i] * powerOfEight[i];
21            }
22            return state;
23        };
24
25        // Depth-First Search (DFS) algorithm to determine if current player can win.
26        function<bool(vector<int>&)> dfs = [&](vector<int>& piles) {
27            int currentState = encodeState(piles);
28            if (memo.count(currentState)) {
29                return memo[currentState]; // Return precomputed result if available.
30            }
31            for (int i = 0; i < piles.size(); ++i) { // Try each pile.
32                for (int j = 1; j <= piles[i]; ++j) { // Try removing 1 to all stones from pile.
33                    piles[i] -= j; // Remove stones from the current pile.
34                    if (!dfs(piles)) { // If opponent loses from the resulting state...
35                        piles[i] += j; // Backtrack to restore pile size.
36                        return memo[currentState] = true; // Current player can win.
37                    }
38                    piles[i] += j; // Backtrack to restore pile size.
39                }
40            }
41            return memo[currentState] = false; // If no winning move found, current player loses.
42        };
43
44        return dfs(piles); // Start the game with the initial piles.
45    }
46};
47
48int main() {
49    vector<int> piles = {3, 4, 5};
50    Solution solution;
51    bool canWin = solution.nimGame(piles);
52    // canWin will be true or false depending on whether the player can win or not.
53    return 0;
54}
55
1// Represents the Nim game initial state
2function nimGame(piles: number[]): boolean {
3    // Base for representing the state
4    const base: number[] = Array(8).fill(1);
5    for (let i = 1; i < base.length; ++i) {
6        base[i] = base[i - 1] * 8;
7    }
8
9    // Converts a pile array into a unique state representation
10    const toState = (piles: number[]): number => {
11        let state = 0;
12        for (let i = 0; i < piles.length; ++i) {
13            state += piles[i] * base[i];
14        }
15        return state;
16    };
17
18    // Memoization cache to store known game states
19    const memo: Map<number, boolean> = new Map();
20
21    // Recursive function to determine if the current player can win from the given pile configuration
22    const canWin = (piles: number[]): boolean => {
23        const currentState = toState(piles);
24        if (memo.has(currentState)) {
25            return memo.get(currentState)!;
26        }
27        for (let i = 0; i < piles.length; ++i) {
28            for (let j = 1; j <= piles[i]; ++j) {
29                piles[i] -= j; // Try reducing the current pile by 'j'
30                if (!canWin(piles)) { // If the opponent can't win from here, current player wins
31                    piles[i] += j; // Restore the pile before memoizing and returning
32                    memo.set(currentState, true);
33                    return true;
34                }
35                piles[i] += j; // Restore the pile for the next iteration
36            }
37        }
38        memo.set(currentState, false); // Current player can't win from this state
39        return false;
40    };
41
42    // Start the game by calling the recursive function with the initial piles configuration
43    return canWin(piles);
44}
45

Time and Space Complexity

The provided Python code implements a recursive solution to the Nim Game problem with memoization using the cache decorator, which caches results of subproblems to avoid repetitive calculations.

Time Complexity

The time complexity of the recursive solution is determined by the number of possible states and the transitions between these states. Since the state is represented by the st tuple, which is essentially the current configuration of piles, the number of distinct states can be vast. For each state, the dfs function iterates over each pile and attempts to reduce the number of stones in each pile by every possible number from 1 to x (the size of the pile).

Let's suppose:

  • n is the number of piles.
  • m is the maximum size of a single pile.

In the worst case, each pile can be reduced to zero in m different ways, which gives us m^n possible states (assuming piles can have different maximum sizes, in practice it's less due to combining identical pile sizes). The dfs function is called once for each transition between these states, and because of memoization, each state is computed only once. Hence, the time complexity is O(m^n) but in practice, it can be significantly less due to memoization and the fact that not all transitions occur due to pruning (when a winning state is found, further exploration of that branch is stopped).

Space Complexity

The space complexity is determined by the maximum size of the recursion stack and the space required to store the memoization cache. The recursion depth can go as deep as the number of possible transitions m^n, in the worst case. The cache will need to store a result for each unique state of the piles, thus requiring O(m^n) space as well. Therefore, the total space complexity is O(m^n).

In summary:

  • Time Complexity: O(m^n)
  • Space Complexity: O(m^n)

Please note that in practice, the actual complexities may be lower due to memoization and pruning as explained above.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄