Is there a sure-fire way to win at mahjong? Which game is more complicated: chess, go, mahjong, or Texas Hold'em?

Many children like board games, such as chess, go, mahjong, poker... When you are fighting with your opponent, have you ever thought about this question: Are there any winning strategies for these games?

If one day you accidentally found a cheat book in a cave and obtained the winning strategy for a certain game of chess or card, and Deep Blue and AlphaGo would all have to give way, what an honorable thing that would be!

Today, let’s discuss this issue.

Zermelo's Theorem

First, we need to divide games into two types: complete information games and incomplete information games. If all participants can know all the past and present game information at any stage of the game, this type of game is called a complete information game. Otherwise, it is called an incomplete information game.

For example, in chess, go, and gobang, everyone can see how the other party moves, which is a complete information game. However, it is not the case with military chess - you don't know the opponent's deployment of troops in four-country military chess, and you don't even know where your own chess pieces are. In poker, you don't know the cards in the opponent's hand, and in mahjong, you not only don't know the cards in the opponent's hand, but also don't know the remaining cards on the table. Games like military chess, poker, and mahjong are called incomplete information games.

In 1913, mathematician Zermelo proved that for a two-player perfect information game, there must be a strategy such that either the first player will win, or the second player will win, or both players will tie. This is Zermelo's theorem.

Zermelo

How to prove this theorem? It is actually very simple: in a game where you take turns to play chess, there are a finite number of ways to play each step, which is called a game branch. The number of game branches is finite. Because some rules for winning, losing, and drawing are set, the number of steps in the game is also finite.

Let's assume there is a very simple game. The first player A and the second player B each make a decision (choose the top lane or the bottom lane). Based on the results of the two decisions, the game is won or lost as follows. From this table, can you tell who wins the game?

The strategy and outcome of a game

Some students may think that A has a better chance of winning, but this is not the case. The result of this game must be a draw (unless one of the players is really not very smart and will lose). We can draw a game tree to explain:

Game Tree

If A chooses the top, the game enters a branch where B makes the decision. This is called a sub-game. In this sub-game, if B chooses the top, A wins. If B chooses the bottom, B wins. B must choose the one that is beneficial to him, so he must choose the bottom. The outcome of this sub-game is fixed, that is, B wins.

If A chooses the bottom position first, the game enters another sub-game where B makes the decision. If B chooses the top position, A wins; if B chooses the bottom position, the game ends in a draw. B must choose the position that is beneficial to him, so the outcome of this sub-game must be a draw.

Let's consider A again: If A moves up and enters subgame 1, B will definitely win; if A moves down and enters subgame 2, it will definitely be a draw. A also has to choose the one that is beneficial to him, so A chooses down. The final game is a draw.

If the game is more complicated, it will just have more branches and be longer. But as long as we start from the last sub-game and work backwards layer by layer, we will be able to figure out under the optimal strategy whether the game will end in a draw or the first player wins. This kind of victory or defeat is inevitable.

For example, in Gobang, the two sides take turns to make moves, and the winner is the one who connects five pieces. People gradually discovered that there is a sure-fire way to win if the player goes first. In order to make the game fair, they designed three-three forbidden moves, four-four forbidden moves, and long-chain forbidden moves. The first player to make a forbidden move loses.

Two sure-win openings for Gobang without forbidden moves

Compared with Gobang, the rules of Chinese chess and Go are much more complicated, but they are still two-player games with complete information. Although we don't know what the optimal routine is, we are sure that there must be such an optimal strategy. If both sides implement this strategy, the first player wins, the second player wins, or the game ends in a draw.

But why have we never heard of anyone mastering the winning method in chess and Go?

Tic-Tac-toe

Let’s take the simplest chess game – Tic-Tac-toe – as an example.

Tic-tac-toe is very simple. First draw a tic-tac-toe, then draw a cross first and a circle second, taking turns drawing in the nine squares. Whoever has three pieces connected in a line horizontally, vertically and diagonally wins. If the lines are full and neither side wins, it's a draw. For example, the following is a tic-tac-toe game where the first player wins.

A game of tic-tac-toe

Although the rules of this game are simple, it is still very playable because it actually has quite a few variations. To be more precise, it should be called the complexity of the game.

First, let's discuss the state complexity of the game, which indicates how many possible situations there are on the board. Generally speaking, we cannot accurately calculate the state complexity of a game, and in many cases it is not necessary to calculate it accurately. We only need to estimate an upper limit or an order of magnitude.

For example, in Tic-Tac-toe, each square has three possibilities: cross, circle, and blank. There are 9 squares in total, so the maximum number of possible situations will not exceed 39 = 19683. There are many situations that do not conform to the rules, such as the number of crosses is either the same as the number of circles, or one more. The other situations do not conform to the rules. Symmetric situations should actually be counted as one situation. If these situations that do not conform to the rules and symmetries are removed, the number of states left is 765 - you can only see these 765 situations in Tic-Tac-toe.

The number of states is not the only way to measure the complexity of a game, because the same state can be reached from different paths. To consider the total number of gameplay options, we need to calculate the size of the game tree.

Part of the Tic-Tac-Toe game tree

Look: When you draw the first fork, without symmetry, there are actually only three ways to draw it: the middle, the midpoint of the side, and the corner. This is the first layer of the tree, with 3 branches.

If the first hand draws a cross in the middle, removing the symmetry, the second hand's circle will only have two ways to draw: the midpoint of the corner and the side. If the first hand draws on the side or the corner, the second hand will have five ways to draw as shown in the figure. This is the second level of the tree, with 12 branches.

After that, the game has many layers, and each layer has many branches, until one side wins or the game ends in a draw. The number of different paths in the game tree represents the number of possible variations of the game.

In the game of Tic-Tac-toe, we can estimate the complexity of the game tree: the first player chooses the position first, there are 9 possibilities; the second player only has 8 possibilities, and the first player has 7 possibilities... until all 9 squares are filled, so the complexity of the game tree does not exceed 9!=362880. There are many irregularities, such as no need to play if one side has won, and we also need to remove duplicates and symmetries, so the final complexity of the game tree is 26830.

People have examined all 26,830 possible paths in tic-tac-toe and found that if both players use the optimal strategy, then tic-tac-toe will definitely end in a draw.

The best strategy for first move

The best strategy for the second move

A game that draws out the game tree completely and finds the optimal strategy is called a solved game. Despite this, in most cases, there will be winners and losers in Tic-Tac-Toe, because some people have a good grasp of the game tree and some do not. Once the opponent makes a mistake, the person who has a good grasp of the game tree can quickly seize the loophole and let the person who does not know how to play fall into a losing game tree branch. This is the difference between a master and a novice.

Go

In fact, chess or go are not fundamentally different from tic-tac-toe, but they are much more complex than tic-tac-toe.

Go

Take Go as an example. In Go, the chess pieces are placed in turns on 19x19=361 grids, so each grid has three possibilities: black, white, and empty. The upper limit of the number of states on the entire Go board is 3361=1.7x10172. Excluding some repetitions and symmetries, the state complexity of Go is about 10171.

You should know that there are only about 1080 atoms in the universe. Even if we use one atom in the universe to represent a Go situation, even if we use all the atoms in the universe, we cannot represent all the Go situations.

The game tree of Go is even more difficult to draw. Because Go allows players to move pieces and continue to play when there are empty spaces, it is not necessarily the end of the game when the board is fully filled. However, we can estimate the total number of layers of the game tree and the average number of branches in each layer. According to statistics and calculations: the average number of moves in a game of Go is 150, and the average number of branches for each move is 250, so the complexity of the entire Go game tree is about 250150≈10360.

Theoretically, if we go through all 10360 situations, we can know whether the first player wins, the second player wins, or it is a draw. However, the amount of calculation is too large. The world's fastest computer, Fugaku, can calculate up to 100 quadrillion floating-point operations per second. If one floating-point operation can calculate a path, then it will take 10342 seconds to calculate all possible situations of the Go game, and the age of the universe is only 13.8 billion years, which is only about 1017 seconds.

Obviously, we know that there must be an optimal strategy for Go, but we cannot calculate this optimal strategy.

However, mathematicians have also found some other methods that can find better ways to win without going through all situations. For example, Deep Blue defeated the world chess champion Kasparov in 1997, and AlphaGo was invincible in 2016, both of which used artificial intelligence methods.

How artificial intelligence defeated humans

In addition to Go, people have also estimated the complexity of several other board games, as shown in the table below. You will find that Tic-Tac-toe has very few situations, so it is easy to become a master. When two masters meet, the only outcome is a draw. Gobang has a little more situations, but as long as you play more, you can also find routines and become a master. When there are no forbidden moves, the first move will win. Like chess and Chinese chess, Go is even more complex.

Military chess

The chess games we just discussed, although of different complexity, are all clear chess games, that is, both parties in the game are fully aware of the current situation. Such chess games have an optimal solution, and whoever is closer to the optimal solution has a higher chess skill. Unless there are unexpected circumstances, a person with low chess skills will never win against a person with high chess skills. For example, I will never win when playing Go against AlphaGo.

But there are also some chess games where the players do not know the status of all the chess pieces. Sometimes, due to good luck, a player with poor chess skills can also defeat a player with good chess skills, which adds a lot of fun to the game. This kind of dark chess is an incomplete information game.

For example, do you still remember military chess?

Military chess

Each side has 25 chess pieces. The commander can capture the army commander, the army commander can capture the division commander, and the engineer can dig mines. After digging the mines, the person who carries the army flag wins. There are many ways to play military chess. One of them is: before the start of the game, you must secretly arrange your troops and put your 25 pieces in 25 positions without letting the opponent see. When two pieces meet, the referee decides who captures whom. So neither side knows what the other side's chess pieces are. When I was a child, I especially liked playing military chess. When I was lucky, my commander captured the enemy's army commander, or the enemy commander stepped on my mine, I was very happy.

How to describe the complexity of military chess? We need the concept of information set.

The size of the information set represents the number of possible unknown information. For example, if I play against Zhang San, I know that Zhang San only knows 10 ways to deploy troops, but I don’t know which one he chose. In this case, the size of the information set is 10.

The number of information sets indicates the number of possible known information. For example, if I only know 5 opening formations, then the number of my information sets is 5.

Think about it, when I play against Zhang San, how many possible situations are there? It should be 50, right? Just multiply the size of the information set by the number of information sets. In fact, if two people play against each other, each has 25 pieces, arranged on their own 25 military stations, the size and number of the military chess information set at the beginning of the game are both 25! = 1.5x1025 (ignoring repeated pieces).

Military chess board

Now, we have changed from a single dimension of situation status to two dimensions: information set size and number of information sets. Information set size represents the set of unknown possibilities, and the number of information sets represents the total number of known situations. Incomplete information games have two dimensions of complexity.

Mahjong

Let’s take a look at our national quintessence: Mahjong.

Mahjong

Mahjong is also a kind of hidden chess. There are 34 kinds of cards, 4 cards each, a total of 136 cards. At the beginning of the game, each side draws 13 cards, and each round draws one and then plays another. If there are 14 to 16 cards left and no one has won, the game is considered lost. We know the cards in our hands, but we don't know the cards in other people's hands and the cards we and others can draw, so it is an incomplete information game, a hidden chess game.

Let's calculate the number and size of information sets:

First round

Number of information sets: There are 136 mahjong tiles in total. I start with 13 tiles, ignoring duplicates. There are possible ways to get the tiles.

Information set size: In addition to the 13 cards in my hand, there are 123 cards. The other three players each have 13 cards in their hands, so the possible number of unknowns is.

Round 2

Number of information sets: In the first round, each of the 4 players played 1 card. There are 34 mahjong tiles, so there are 344 ways to play. At this time, I still have 13 cards in my hand, and the number of ways is , so now, I may face a situation of .

Information set size: In addition to the 13 cards in my hand and the 4 cards played in the previous round, there are 119 cards left. The three players still have 13 cards each. There are several possible numbers.

…

Because the game of mahjong ends when there are 14 to 16 tiles left, the maximum number of rounds is about 17. We use this method to list the number and size of information sets in these 17 rounds, as shown in the following table

The number and size of information sets in each round of Mahjong

Let’s make it clearer with a diagram:

You will find that as the game progresses, the number of information sets becomes larger and larger, that is, the number of possible situations that I can observe increases. The size of the information set becomes smaller and smaller, that is, the possibility of unknown situations decreases.

We can also calculate that in Mahjong, the total number of information sets is about 10115, which is the upper limit of the total number of states we can see when playing Mahjong. For each situation, the average size of the information set is about 1049, which is the possible combination of cards in other people's hands that we don't know. By multiplying the total number of information sets by the average information set size, we can estimate the state complexity of Mahjong, which is about 10^165.

Microsoft Research Asia once compared the state complexity of several board games. In this graph, the vertical axis represents the size of the information set, that is, uncertainty; the horizontal axis represents the number of information sets, that is, the changes in the exposed cards.

Refer to the chess and card complexity chart made by Microsoft Research Asia

You will find that: Tic-Tac-toe, international checkers, Chinese chess, chess and Go, because there is no uncertainty at all, its information set size is 1, and there is only one dimension, the number of information sets. As we just said, these games have optimal strategies.

In Mahjong, Bridge, and Texas Hold'em, besides the many variations of the cards you get, even if you see the same situation, others still have many possible cards. They are incomplete information games with two dimensions. In comparison, the information set size of Mahjong is much larger than that of Bridge and Texas Hold'em, which shows that Mahjong has greater uncertainty and luck is more important in Mahjong.

As long as there are two dimensions and uncertainty in the game, there is generally no winning strategy. Obviously, as long as my cards are good enough, no matter how good you are, you will most likely lose to me in mahjong. The progress of computers in calculating incomplete information games such as mahjong is obviously behind that of chess and go.

Mahjong has many changes and uncertainties, so that an ordinary player can also beat the master. The occasional surprise makes many people addicted. You have to go with the flow when playing mahjong. No matter how good your card skills are, you may not be able to control the development of the game. For example, if you want to win all the cards when playing mahjong, you may lose the whole night.

This is how playing mahjong is, and isn’t it the same for life?

END