Shulou(Shulou.com)06/03 Report--

In this issue, the editor will bring you about what Nim games and SG functions are. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

1. Nim games

Key conclusion: for the situation of a Nim game, it is P-position if and only if A1 ^ A2 ^. ^ an = 0, where ^ represents a xor operation.

Nim game is one of the most classical models in game theory. It also has very simple rules and extremely beautiful conclusions, so it is probably most appropriate for this game to begin to understand game theory.

Nim game is a kind of combination game (Combinatorial Games). To be exact, it belongs to "Impartial Combinatorial Games" (hereinafter referred to as ICG). A game that meets the following conditions is ICG (which may not be very rigorous): 1, there are two players; 2, two players move the game alternately, one step at a time, and the player can move either of a limited set of legal movements. 3. For any possible situation in the game, the legal movement set only depends on the situation itself, and does not depend on which player's turn to operate, any previous operations, the number of dice points or any other factors; 4. If it is a player's turn to move, and the legal movement set of the situation is empty (that is, it cannot be moved at this time), then the player is negative. According to this definition, many everyday games are not ICG. For example, chess does not meet condition 3, because the red side can only move the red spot, the black side can only move the sunspot, and the legal movement set depends on which player it is the player's turn to operate.

The definition of the Nim game is like this: there are several piles of stones, the number of stones per pile is limited, the legal movement is to "select a pile of stones and take away several (can not be taken away)", if it is someone's turn when all the stones have been empty, then negative (because he does not have any legal movement at the moment).

The game looks a little complicated, so let's start with a simple situation. If there is only a pile of stones left when it is your turn, then the winning strategy must be to take all the stones and not give them to your opponent, and then lose against each other. If there are two unequal piles of stones left, the winning strategy is to make the two piles equal by taking more than one pile of stones. Later, if your opponent takes several stones in one pile, you can take the same number in the other pile until you win. If you are faced with two equal piles of stones, then you do not have any winning strategy, but the opponent can follow the above strategy to ensure victory. If it's three piles of stones... It seems to be difficult to analyze, and it seems that we have to use some other useful (preferably stylized) analysis methods, or we'd better be able to design an algorithm that can find a winning strategy when there is a winning strategy.

Define P-position and N-position, where P stands for Previous,N and Next. Intuitively speaking, the last time move people had a winning strategy was P-position, that is, "the second hand can guarantee victory" or "first hand must lose". Now it is move's turn to win the situation is N-position, that is, "first hand can guarantee victory". A more rigorous definition is: 1. The situation in which no movement can be made (that is, terminal position) is PMaipositionist2. The situation that can be moved to P-position is NMI position position 3. All moves lead to a situation where N-position is P-position.

According to this definition, if the situation cannot be reproduced, or if the set of positions can be topologically sorted, then each position is either P-position or N-position, and can be calculated by definition.

Take the Nim game as an example to do the calculation. For example, I just said that when there are only two piles of stones and the number of two piles of stones is equal, there is a winning strategy, that is, this is a P-position, let's rely on the definition to prove that P is a P is a P-position. First of all, the sub-situation (that is, the situation that can be caused by legal movement) is (0magin3) (1mag3) (2mag3) (obviously the position of the exchange gravel pile does not affect its nature, so it is only necessary to calculate the properties of the three situations). The sub-situations of (0meme3) are (0rect 0), (0rect 1), (0pr 2), where (0je 0) is obviously P-position, so (0meme 3) is N-position (as long as you find a sub-situation that is P-position, you can tell it is N-position). The successor of (1) (1) is P-position (because the only sub-plane (0) of (1) is N-position), so (1) is also N-position. It can also be proved that (2p3) is N-position. So all the sub-scenarios of (3p3) are N-position, which is P-position. Through a simple mathematical induction, it can be strictly proved that "the situation with two piles of stones is P-position if and only if the number of the two piles of stones is equal".

According to the above process, we can get a recursive algorithm-for the current situation, recursively calculate the properties of all its sub-situations. If there is a sub-situation that is P-position, then the move to this sub-situation is a winning strategy. Of course, you may already be acutely aware of a large number of overlapping sub-problems, so you can use DP or memory search to improve efficiency (just think of this step for simple game problems). But the problem is that using this algorithm, for the situation of a certain Nim game (A1 a1*a2*...*an), if you want to judge its nature and find out the winning strategy, you need to calculate the nature of the situation, no matter how much memory can not reduce this time complexity. So we need a more efficient way to judge the nature of the situation in Nim games.

Just come to the conclusion. (Bouton's Theorem) for the situation of a Nim game, it is P-position if and only if A1 ^ A2 ^.. ^ an = 0, where ^ represents an xor operation. What do you think? isn't it amazing? I thought it was amazing when I saw it, and it had something to do with XOR operations that didn't make any sense. But the proof of this theorem is not complicated, basically according to the proof of two kinds of position.

According to the definition, to prove the correctness of a method of judging the nature of position, it is only necessary to prove three propositions: 1. This judgment judges all terminal position to be N-position 2, the situation judged to be N-position according to this judgment must be moved to some P-position, and the situation judged to be P-position according to this judgment cannot be moved to a certain P-position.

The first proposition is obviously that there is only one terminal position, which is all zero, and XOR is still zero.

The second proposition is that for a certain situation, if A1 ^ A2 ^ .an! = 0, there must be some legal movement that satisfies A1 ^ A2 ^.. ^ ai'^. ^ an=0 after changing ai to ai'. If A1 ^ a2 ^. ^ an = k, there must be some ai whose binary representation is 1 at the highest bit of k (otherwise, how did the highest bit 1 of k be obtained). At this time, aik

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.