This article originated from personal public account: TechFlow, original is not easy, for attention


In today’s series on algorithms and data structures, we look at a new game theory model, the Nim subproblem.

This game problem is so old, it lasted for thousands of years, that it wasn’t solved until the early 20th century by a mathematician at Harvard University, which shows the difficulty of thinking. But the problem itself is interesting, and the derivation is even more interesting, even if you don’t have a lot of data.

Nim subfetching problem

So the problem is this, we have three piles of pebbles, and we have two people, A and B, taking turns picking pebbles from one of the piles. It is stipulated that each person should take at least 1 stone at a time, and the person who cannot continue to take stones will lose. If you are the first mover, do you have a winning strategy?

So, in the way that we’ve been doing wetzoff’s games, we need to analyze the problem, and find some typical situations. For example, (0, 0, 0) is a sure loser for the first player, and for a (0, n, n) situation, it is also a sure loser. Because no matter how the first hand picks the pebbles, the second hand just does the same thing in the other pile, and the first hand is still left with a (0, n, n) situation. In game theory, we often refer to situations in which the first mover loses as bizarre situations.

So is there any connection between these bizarre situations? Can we find a connection or a formula between these situations?

It’s hard to come up with a list of all the fantastic situations we can think of just by thinking about them or using a pen and paper, or it wouldn’t have bothered people for more than a thousand years. But the answer to this question is incredibly simple.

First of all, let’s think about a problem, which is complicated because we have three piles of pebbles instead of two. If there are two piles of pebbles, then it’s easy, and the first player wins unless he’s faced with two equal piles of pebbles. Because it can leave two piles of the same stones for the latter hand by taking them, so that no matter how the latter hand takes them, the first hand only needs to do the same operation in the other pile, which will certainly leave a strange situation for the latter hand. This is the same thing that we just analyzed for the (0, n, n) case.

But they say three piles instead of two, and we can’t help but think about the question, can we think of a strategy that allows us to “convert” three piles of pebbles or see two piles of pebbles? So we can make a pretty easy decision about whether the pebbles are winning or losing.

Method of analysis

I have three piles of pebbles, but how can I see two piles? Either way, it’s self-evident, but if you’re familiar with binary, you’ll see that the problem might not be impossible.

Yes, binary is by nature a two-dimensional “creature” in which there are only two kinds of everything, zeros and ones. So intuitively, maybe we can relate the number of pebbles to binary. Maybe that connection will help us find a solution. The question then becomes, what is this correlation?

Let’s think about another problem, if we take a bunch of pebbles, if we take away a number of pebbles, the number of pebbles is going to go down, that’s obvious. The total number of pebbles, the number of pebbles in the pile, minus another number. This is the operation of subtraction, elementary school students know. But what elementary students don’t know is how subtraction works in binary, or how it works.

Before we rush to answer, let’s take a closer look. First, both the subtraction and the minuend can be reduced to binary, which is a number of ones and zeros. If we assume that each of the 1 bits of the subtraction corresponds to a 1, then this subtraction will work perfectly. That corresponds to the process of removing 1’s from the minuend.

For example, the minuend is 9, and the subtraction is 1. We all know that 9 written in binary is 1001, and the binary of 1 is 1. So the minuend minus the subtraction is equal to 8, which is 1000, or you can view it as 1001 minus the 1 at the end.

If there is a case where the minuend is 0, such as 10-3, the binary of 10 is 1010, and 3 is 11. It’s obvious that the 0th bit of 3 is 1, and 10 is 0. What happens in that case? First, let’s get rid of the ones in both the 3 and 10 bits. So what we’re left with is 1000 minus 1, so we can subtract 1 from 1000 to 111, so we’re back to the first case, and then we add back, so we’re going to get 111, and we’re essentially borrowing to the higher level. If you look at the whole process of subtraction, which is actually the process of changing the bits in the minuend, subtracting something is the same thing as changing the number of zeros in the minuend to 1 and 1 to 0.

Combining binary, we can think of a strategy. We’re counting all the bits of these three numbers, and since we have three numbers, each of these bits has at most three ones and at least zero ones. If the sum of 1’s in each digit is even, that is, either 0 or 2, then this must be a strange situation.

For example, if [10, 8, 2] is a strange case, let’s write them as binary. The binary of 10 is 1010, the binary of 8 is 1000, the binary of 2 is 10. So we can see that the binary bits of these three numbers add up to two 1’s in the first, second, and third digits. In this case, no matter what the first hand does, the second hand only needs to ensure that the remaining three bits maintain this property. This ensures that after the last grab, the first player is left with a [0, 0, 0] situation. Essentially, it’s the same principle that we had when we had two pebbles, but in a different form.

So for example, if we take three stones out of 10, and we get (7, 8, 2), let’s look at the binary bits 111, 1000, 10. It is found that the number of 1s in each digit is [1, 2, 1, 1] from low to high. So we can take 3 stones from 1,000, and we’re going to have 101, which is 5. So the number of ones left is [2, 2, 2], which is still even. So no matter what the first hand does, the second hand is guaranteed to keep the digits even in binary, and the first hand is guaranteed to lose. In situations where this condition is not met, the first hand must win, because the first hand can guarantee a losing situation for the second hand by removing the extra 1 the first time.

And that’s how you solve this problem, which is to use the binary bits to determine whether a first mover wins. We need to determine whether the number of 1’s in each binary bit is even or not, which can be done by using the or of the bitwise operation. In the or operation, each binary bit is evaluated, and the odd bit is 1 and the even bit is 0. So all we have to do is figure out if these three pebbles or any subsequent pebbles are zero, and we can figure out if each of these bits has an even number of ones.

It’s very easy to write the code, we usually use the symbol ^ to indicate the or operation, so the code only needs one line:

def win_or_lose(a, b, c):
    return (a ^ b ^ c) == 0
Copy the code

Promotion and certification

This is not the end of the story, we can also generalize the situation of three pebbles to n, no matter how many pebbles the player is faced with in the game. It’s easy to see why this is true, and just for the sake of rigor, we can prove it in the same way that we do in game problems.

In a game problem, if there is a strange situation, a win-lose situation, then three conditions must be met. The first condition is that a situation in which nothing can be done is a strange situation. The second condition is that the situation that can move to a strange situation is a non-strange situation. The third condition is that any operation done in a singular situation results in a non-singular situation.

As long as we can prove these three points, we can prove our thinking is correct.

There’s no doubt about the first point. You can’t move a pile when there are no stones in it. It’s a losing state.

Let’s look at the second condition. Let’s say the number of pebbles in n is A1, A2… The an. If the current situation is non-singular, according to our theory, then A1 ^ A2 ^ A3 ^… ^ an > 0. That is, there is some binary number of ones that is odd.

Let’s assume a1 ^ A2 ^ a3 ^… ^an = k, then it must be possible to find an AI whose binary representation is 1 in the highest digit of k, because all binary ones of K come from these n numbers, so such an AI must exist. So we can go on and get ai ^ k < ai. Since the highest 1 becomes 0 after or, it must be reduced after the operation. Let’s take p = ai ^ k, and let’s take a1^ A2 ^a3^… ^an = k or ai, a1 ^ a2 ^… ^ai-1^ai+1^… ^an = k ^ai, so a1 ^ a2 ^… ^ p ^… The an = 0.

The third condition is also easy to prove, because if we’re in a losing situation, that means a1 ^ A2 ^… ^ an = 0. Let’s suppose that if we turn an into P we still have a1 ^ A2 ^… P is equal to 0, p is less than an. If we add p and an to both sides of this equation, we get an ^ p = 0, which means p = an. This contradicts p < an, so there is no such transformation that makes the singular situation remain singular after the operation.

Thus we prove the correctness of this reasoning mathematically. In fact, there has been a thorough study of Nim subproblem, which is also a proven theorem called Bouton theorem. The content of the theorem is that the first hand can win in the unbalanced Nim game, and the second hand can win in the balanced Nim game. The equilibrium here means that the number of binary ones is even.

So it’s easy to write code:

def win_or_lose(nums):
    ret = 0
    for i in nums:
        ret ^= i
    return ret == 0
Copy the code

conclusion

So that’s the end of the Nim game. The solution is really quite simple to judge by either or operation, but the derivation is not easy to figure out. I read a lot of blogs, and they all come out directly or this conclusion, but I rarely see the detailed derivation. It’s easy to remember the conclusion directly, but it’s also easy to forget that you have to go through it yourself to understand how or why this magic operation came about and why it solved the Nim game.

In the whole process of thinking and reasoning and proving, we make a lot of use of the “or” bit operation, which may seem confusing to students who are not familiar with it. It is suggested that you can learn about the properties of binary or before reading this article, the effect will be better.

So far, we have introduced bash game, Witzoff game and Nim game, which are three relatively simple game models. In future articles, we will continue to delve into game theory and work together on more difficult game theory problems to see how we can find strange states in complex scenarios.

This is the end of the article, if you like this article, if you can, please click a concern, give me a little encouragement, but also convenient to get more articles.

This article is formatted using MDNICE