Yesterday, during the "Scientific Computing Software" class, we discussed a game called "Pick 15." In this game, two players take turns selecting a number from the set \{1, 2, \dots, 9\}. Numbers cannot be repeated. The first player to have exactly three numbers in their collection that sum to 15 is the winner.
This is a simple game that falls under the category of game theory. In game theory, there is a famous theorem known as Zermelo’s theorem. It states that in a finite two-person game with perfect information and no element of chance, either the first player or the second player must have a winning strategy or a non-losing strategy. For example, Chinese Chess belongs to this category; the theorem tells us that for one of the sides, there must exist a strategy that guarantees they will not lose (it could be a draw or a win, but they definitely won’t lose). Of course, Zermelo’s theorem only proves the existence of such a strategy; it does not tell us how to find it, nor does it even specify which side possesses the optimal strategy. This is fortunate, because if such a strategy were discovered one day, games like chess would lose their meaning.
The Pick 15 game mentioned above also belongs to this class of games. Unlike the infinite variations of chess, its possibilities are relatively simple, and it is easy to see that it offers a significant advantage to the first player. Let us analyze it below.
In the Matlab Pick 15 program used in our course, the human plays first, while the computer follows a "three-step strategy":
If possible, make a winning move.
If necessary, block the opponent’s winning move.
Otherwise, randomly occupy an empty small square.
Is there any problem with this strategy?
Let’s first look at a scenario. Suppose the first player chooses 4. The second player can then choose any of the remaining 8 numbers, say 7. Next, the first player chooses 8. The second player is forced to choose 3 to block. Then, the first player can only choose 5, but at this point, the second player is defeated. To "block" the first player’s victory, the second player would need to choose both 6 and 1 simultaneously, which is impossible. The entire process is as follows:
This case at least tells us that the "three-step" strategy mentioned above is not perfect, because according to its rules, if the first player picks 4, the second player might pick 7, which leads to a certain loss for the second player.
This process can be abstracted into a general form:
The entire flow depends only on the first three numbers. Obviously, if every number in the boxes is distinct and belongs to the set \{1, \dots, 9\}, then the Red player wins. Red, of course, wants this to happen. However, the description above has many constraints; is it really that easy to achieve? In fact, it is very easy... I performed a simple analysis using inequalities and found that many of these conditions are compatible; satisfying one condition often satisfies a whole set of others. To make this more concrete, rather than using formulas, I wrote a crude Matlab program and obtained the following table:
1st 2nd 1st
3
1
2
2
2
2
2
2
2
2
3
3
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
7
7
8
8
8
8
8
8
8
8
9
9
This table shows that if the first player picks the first number, the second player picks the second, and then the first player picks the third, the first player wins! This includes 48 winning scenarios!! Of course, the winning situations are not limited to these.
What if a+c-b < 1 or a+c-b > 9? This is also an advantage for the first player, because it tells us that no matter what the first player chooses in this step, the second player cannot win immediately. The first player is freed from "worries about the future" and can choose numbers that are as advantageous as possible. If the first player’s choice leads to a situation where the second player cannot "block" the next move, the first player wins. How many such cases are there? Surprisingly, there are 80 such cases!! The winning rules are as follows:
1st 2nd 1st 2nd 1st
2
1
1
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
8
8
8
8
8
8
8
8
8
8
8
8
9
9
9
From the statistical results, if the first player chooses an even number, the second player must choose 5, otherwise they will lose!! (Assuming the first player follows the optimal rules). Therefore, the "three-step" strategy mentioned above is not just problematic; it is significantly flawed, as we would have a 7/8 win rate! Are there any other winning rules? I don’t think so, because if no one has won after 5 moves, then after the second player picks another number, only three numbers remain, leaving little freedom of choice; it should already be a draw.
Of course, this purely computer-based analysis method at most provides some practical information without offering much aesthetic appeal. There is a method that allows us to look at this problem from another perspective, which we will discuss next time (though there are already analyses of this kind online). Below are my crude programs:
Judgment of winning in three moves_Matlab.txt
Judgment of winning in five moves_Matlab.txt
When reprinting, please include the original address of this article: https://kexue.fm/archives/1973
For more detailed reprinting matters, please refer to: Scientific Space FAQ