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


Today is the 24th article in our series on algorithms and data structures, and we’re going to talk about some interesting game theory problems.

Game theory is a huge discipline, it’s a branch of mathematics, it’s related to operations research and even economics. Although it’s not strictly algorithmic, there are some interesting algorithms and problems in game theory. Theories of games have been around for a long time, but the formal establishment of theory as a discipline began with Von Neumann, the father of computing. It’s also a little bit about computers in that sense.

Today we’re going to talk about the simplest of Game theory, the Bash Game.

Count off the problem

You can’t talk about Bash Game without counting it. It’s so classic that I think you’ve probably heard of it. The title is like this, it is A and B two people together to play A counting game, two people take turns to count, each time at least one number, the most 5 numbers, the first report 100 people win. If you are the first player A, what strategy should you take?

If you haven’t thought about this problem before or if you’ve looked at game theory, you probably think it’s complicated, it’s difficult, and there’s no good way to do it. Because two people can make several choices at a time, and each choice leads to a different one, this cascade of possibilities opens up a lot of possibilities. In this case, it seems difficult to come up with an algorithm to solve the problem.

Reporting 100 doesn’t show, so let’s zoom out. What if reporting 6 wins? Isn’t it obvious that alpha is going to lose no matter what strategy he uses? Because no matter how many numbers it reports, B can report 6 directly.

And since A must lose for every six numbers, it follows that A must lose for every multiple of six. Let’s say it’s an I in a certain round, and the other side just has to say 6-I. I’m going to do this a couple of times and I’m going to end up with 6, so I’m back to the simplest case.

Suppose we have developed a state function that calculates whether the first player must win or lose in a certain state, and we use 1 to indicate that the first player must win and 0 to indicate that the first player must lose. So state of 0 is 0, state of 6 is 0. Since no matter what the first hand says in each round, the second hand can control to say a number that adds up to 6, so we can get state(n) = state(n-6). So, we can deduce that state(6n) = 0.

Since the first hand can count from 1 to 5 at a time, when he is faced with a 6n+k situation, as long as k is not equal to 0. So he gives us k numbers, and we can turn this into a 6n losing situation for B. So we know that the first mover wins every situation except 6n.

If we do it in code, it’s just one line:

def win_or_lose(n):
    return n % 0! =0
Copy the code

The essence of game theory is the analysis of the problem, which is embodied in the code of complex thinking, but extremely simple code.

Count off this problem is more intuitive, so look for rules to think carefully is also can guess the answer. But if we wrap it up, it might be different.

Playing CARDS problem

This is from HDU1847, and it’s about two people playing cards. There are n cards, and they take turns to draw. It is stipulated that each card draw must be a power of 2, and the last one to complete the row wins. Assuming both are extremely smart, who will win in the end?

Let’s say that two people are extremely smart, which is the premise of the game theory problem, which is that both of them play the optimal strategy. Without that premise, you can’t use game theory to do an analysis, because it’s not just math anymore.

Compared to the above problem, this problem becomes more complicated. Because the number of strategies per person has changed, from being strictly limited to five possibilities, to an infinite number. But in fact, there is a trick to hide.

Let’s first list all the powers of 2, starting with 2 to the 0, 1, 2, 4, 8… . I don’t know if you think about this 1 and 2, but if you know a little bit about number theory you know that powers of 2 are never divisible by 3. That is to say there are only two possible outcomes of 2 to the power of 3, which is 1 or 2. So this is actually the same problem as the previous one, it doesn’t matter how many powers of 2 we take, what matters is what’s left after we take modulo 3.

State (0) = 0, because the other side is done. So state(1) is equal to state(2) is equal to 1, so if you only have one or two cards left, you can take them all at once. State (3) = 0, because you can’t get it all at once. We can generalize to state(3n) = 0. So multiples of 3 are a loser. Since we just said, the power of 2 must be 1 or 2. So you getFor the first hand,As long as the state is not a multiple of 3, we must win. Because he must be able to find a power of two that will leave him a multiple of three.

Once the analysis is done, the code is just one line:

def win_or_lose(n):
    return n % 3! =0
Copy the code

conclusion

Bashi’s problem is simple, and once you know the formula, a series of similar problems can be easily solved. But it should be noted that, faced with the problem of Bash game, we can not simply understand as a number, or to find a winning or losing strategy. But to analyze it from the point of view of the state, what kind of state is sure to win or lose, and what kind of transfer relationship exists between the states.

From this point of view, it seems to be a little bit of dynamic programming, but the difference is that dynamic programming algorithms solve finite boundary problems. And sometimes in game theory the strategy or the state may be infinite, but there is some overlap. Bash game is just the simplest of the game theory algorithms, and we’ll move on to other more complicated game theory problems.

If you like this article, if you can, please click the following, give me a little encouragement, but also convenient access to more articles.

This article is formatted using MDNICE