Application of “game theory” analysis of the “first hand must win” sequence has what kind of nature

This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 810 on LeetCode. Blackboard xor game, difficulty is difficult.

Tag: “Game theory”, “mathematics”, “xor”

On the blackboard is written an array of non-negative integers nums[I].

Alice and Bob take turns to erase a number from the blackboard, Alice first. If after erasing a number, all remaining digits in bitwise xor result in 0, the current player loses the game. (Also, if there is only one number left, the bitwise xor operation yields itself; If there are no digits left, the bitwise xor operation results in 0.

In other words, when it’s a player’s turn, if all the numbers on the current board are xor equal to 0, that player wins.

Assuming that both players use the optimal solution at every step, return true if and only if Alice wins.

Example:

Input: nums = [1, 1, 2] Output: false Explanation: Alice has two choices: erase the number 1 or 2. If I erase the 1, the array becomes [1, 2]. The remaining digits are XOR by bit to get 1 XOR 2 = 3. So Bob can erase any number, because Alice will be the one to erase the last number, and she always loses. If Alice erases 2, then the array becomes [1, 1]. The remaining digits are XOR by bit to get 1 XOR 1 = 0. Alice will still lose the game.Copy the code

Tip:

• 1 <= N <= 1000
• 0 <= nums[i] <=
  $2^{16}$

Fundamental analysis

This is a game theory problem.

It’s hard to imagine if you haven’t seen game theory, especially if the data range is 10310^3103, which is very confusing.

If you have been exposed to game theory, the game theory direction is a preferred direction for determining the winner of the game.

According to the question, if a player has all values equal or equal to 000 before the action, the player wins. To determine whether the hand is in a “win” or “lose” state for a given sequence, return True if it is in a “win” state, False otherwise.

There are two ways to think about game theory problems:

1. Empirical analysis: see similar problems, guess a property, and then to prove whether the property can be generalized.
2. State analysis: according to the given rule of the topic is to judge “victory” or “defeat” to determine the priority analysis of “victory” or “defeat” of the nature, and then prove whether the nature can be generalized.

Game theory

For this case, what is given is the rule for determining “victory” (in the case of a given sequence, if the sum of all values is xor
$0$Can immediately judge the victory, other cases can not immediately judge the victory), then we should give priority to judge what is the “first hand must win”, if not good analysis, then consider the analysis of the “must lose”.

Here’s a case by case discussion:

1. If the given sequence xor sum is
$0$At the beginning of the game, the first player wins directly:

Property 1: given the xOR sum of nums is 000, the first hand is in a “must win” state and returns True.

2. If the given sequence is xOR and not
$0$, we need to analyze what properties the sequence will satisfy if the first hand wins:

Obviously, if the first hand is to win, it needs to meet the following requirements: “if the first hand removes a number, the sum of the remaining values must not be 000; at the same time, if the second hand removes a number, the sum of the remaining values must be 000”.

In other words, we need to analyze under what circumstances “after a backhand operation” the sequence will return to the first hand situation in the state of 111 described above.

That is, the reverse analysis of the sequence in order to appear “after the defeat”, what kind of properties.

Assuming that the xOR Sum before the back-hand operation is SumSumSum (Sum≠0Sum \neq 0Sum=0), the “back-hand must fail state” means that the xor Sum after removing any digits is 000.

Meanwhile, according to the property of “the xor result of the same value is 000”, we know that removing a certain value is equivalent to adding this value on the basis of the original xor and.

There are:

$Sum’ = Sum ⊕ nums[i] = 0$

Since it is a “sure defeat state”, any digit of III can satisfy the above formula.

There are:

$Sum ⊕ NUMs [0] =… = Sum ⊕ nums[k] =… = Sum ⊕ NUMs [n-1] = 0$

At the same time, according to the property of “any value is equal to 000 or the value is unchanged”, we perform xOR for each item:

$(Sum ⊕ NUMS [0]) ⊕… ⊕ (Sum ⊕ NUMS [k]) ⊕… ⊕ (Sum ⊕ NUMs [n-1]) = 0$

According to the commutative law:

$(Sum ⊕ Sum ⊕… ⊕ Sum) ⊕ (NUMs [0] ⊕… The radius nums [k] the radius… ⊕ Nums [n-1]) = 0$

Then SumSumSum is the xOR sum of the original sequence, which can be obtained:

$(Sum ⊕ Sum ⊕… ⊕ Sum) ⊕ Sum = 0, Sum \neq 0$

So far, we have analyzed that the above formula can be satisfied by removing any value when in the “backhand must fail state”.

According to the property of “the same value is even times or the result is 000”, it can be deduced that the “hindhand must lose state” will lead to an even number of sequences returned to the first hand, so it can be deduced that the number of sequences before the hindhand operation is odd, and the turn before the hindhand operation is even.

Thus, property 2 can be deduced: the “last-hand must fail” will appear when the number of sequences before the first-hand operation is even, so as to ensure the “first-hand must win”.

Code:

class Solution {
    public boolean xorGame(int[] nums) {
        int sum = 0;
        for (int i : nums) sum ^= i;
        return sum == 0 || nums.length % 2= =0; }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(1)O(1)O(1)

conclusion

In fact, when I do problems, I do the “assume parity and prove it later,” because it’s faster.

But “assume parity” this step is compared with the leap, it is a bit like I said earlier to “experience” analysis method, and the answer key to prove that didn’t do any front assumption, from a purely “Julio cruz win state” and “successful” losing state inference, finally deduces properties of even “win” solution sequence, more in line with the front said “state analysis method”.

The two approaches come to the same conclusion. In some game theory problems, the “empirical analysis solution” can be well analyzed through “induction” and “counterproof”, but this requires players to have a certain basis in game theory. The “state analysis method” requires less questions and higher logical reasoning ability.

Neither method is superior to the other. Both methods are scientifically rigorous.

The last

This is No.810 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01, and there are 1916 questions on LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.