Shulou(Shulou.com)11/24 Report--

Single spider solitaire (hereinafter referred to as "Spider Solitaire") is a popular game that people often play online or offline on their computers. As can be seen from the name, there is only one player in the game. There are two sets of standard playing cards in the game, and players need to arrange the playing cards into eight complete groups (two sets of cards, each with four colors) in order to further eliminate them from the table. Cards can be extracted from a deck or moved from one column to another according to specific rules. We will not discuss the rules of the game in detail here, assuming that our readers already understand the rules of the game. If you need to recall, you can look here. Here we will only discuss the four-group version of the game.

Spider cards contain two sets of standard playing cards. Players have been complaining about deviations in different software. Specifically, if the program detects that the player's winning rate is high, it may secretly manipulate the order of the cards behind to reduce the winning rate. Players themselves may also be biased to play at their best. However, through some basic statistical means, it is possible to confirm or refute this "accusation of bias". This can also be used as a good exercise to see how a person uses data observed in the real world combined with statistics to determine whether a hypothesis (such as "spider card programs are biased") is true or false.

Basics from the perspective of this article, we assume here that players do not use "undo", "redo" and "add steps" when playing spider cards (reducing the game to a crude initial version). So players don't have to think about scoring, time spent, and the number of steps to move. Many people think that games are almost impossible to win under such conditions, but Steve Brown of California State University in long Beach gives some detailed strategies in his excellent book, "Spider Solitaire winning Strategies." and mentioned that 48.7% of games can be won in 306 games. At the same time, he also pointed out that his way of playing is not perfect, and those professional players can do better, even reaching a winning rate of more than 60%. I used Brown's strategies to conduct experiments, and the results show that it can indeed achieve a winning rate of more than 48.7%.

Ideally, computer-side spider card games can simulate real and fully shuffled card games. If there are N cards at any point in the game that have not been seen, then each card has a 1 / N chance of appearing as the next flipped card (for narrative convenience, we ignore the equivalence between cards of the same color and size). For example, in the starting position we know that 10 cards have been highlighted. Because there are a total of 8 Ks in a total of 104 cards, the probability that a single card is K is 8max 104pm 13, so the expected number of cards shown is K is 10 × 1 / 13 cards 10max 13. If, after playing a considerable number of games, we find that the average number of highlighted Ks is close to 11gam13, we have reason to believe that this spider card program is biased.

Test data for each game, we want to record a set of data that can reflect the luck of the card. The higher the number, the more likely it is to win. One solution we came up with was to evaluate the values of these test data in an absolutely fair and unbiased game and compare them with those recorded in games in which we suspected bias.

Once the first ten cards are determined, we can calculate the "guaranteed turn" (guaranteed turns,GT), that is, the minimum number of cards to be shown before the player is forced to change to another row. Whenever a new row of ten cards has been decided, we can do a similar calculation and pretend it is the beginning of a new game. In this way, we can calculate the average value of GT (AGT). If the GT value is very small after a few rounds, then the player will be in trouble. It is important to note that AGT has nothing to do with the players themselves, so it is easy to simulate the probability distribution of AGT by conducting many experiments (that is, determining many rows).

In terms of experience, if the overall distribution of cards is poor, players will also get into trouble. For example, when there are seven Qs but only two Js are not typed, even if you have one or more columns empty, there will still be problems. Therefore, an overall variance (total square variation,TSV) is defined here, which is the sum of the negative squares of the number of cards of adjacent sizes. In the example just now, seven Qs and two Js will contribute-(7-2) 2 colors 25 when summing. The negative value is taken here to ensure that the increase or decrease of TSV is consistent with the increase or decrease of the probability of winning, just like AGT. Each time a new card is shown, we calculate the TSV so that we can calculate the average TSV (ATSV) of a single game. It is important to note that ATSV also has nothing to do with the player, and we assume that the player will show all the cards in a random order (although the player can choose which card to show first, the probability of each card is the same). Fortunately, this can be easily done through simulation.

A typical scatter chart of spider cards (○ = win, x = lose) A typical scatter chart is shown above, where a blue circle and a red fork indicate victory and defeat in turn.

The simulation results show that for non-biased game programs, after a large number of games, AGT should be equal to 3.96 and ATSV should be equal to-32.29. In the starting position of the following example, GT=1,TSV=-42, because the game is not over, we don't know what the values of AGT and ATSV are.

For example, the starting position GT=1,TSV=-42 is calculated as follows:

Hypothesis testing in order to test whether a spider card game is biased, we use a method called hypothesis testing. Let's first make a zero hypothesis (meaning that the effect we suspect may not exist), in our case, "there is no bias in the spider card program." the complementary assumption is that "the spider card program deliberately causes stumbles to reduce the player's winning rate."

First of all, a larger number N is selected as the number of games in the spider card game to be tested, and then we calculate AGT and ATSV for each game. The next general idea is to find out the probability of the observation we want to compare (that is, the P value), or, more extreme, the probability of the zero hypothesis to be true (that is, the program is not biased). If the probability is lower than a certain threshold (i.e. significance level), an unbiased program is unlikely to produce the AGT and ATSV values that we observe in the N-game, then we reject the zero hypothesis and come to the conclusion that the game is biased.

So how do we calculate the probability of getting the p value, that is, the probability of observing the AGT and ATSV values we have observed (which proves that the game is not biased)? In the simulation, we have obtained the expected values of AGT and ATSV in unbiased games, which are 3.96 and-32.9, respectively. More interestingly, probability theory tells us how AGT and ATSV values are distributed in unbiased games, in other words, it helps us calculate the probability of observing a particular AGT and ATSV value. The so-called "student t test" can take all these values into account and get the p value we want. The details are skipped here, and those who are interested can refer to the relevant contents of probability and statistics.

From the point of view of this paper, we choose Nasty 100 as the number of games we play the game program to be tested, and get a significant level of 0.05.

In addition to AGT and ATSV, we also want to assess the "real" probability of winning for the "unbiased" spider card program. An obvious difficulty is that the winning rate is related to players, so it is difficult to verify the saying that a player can win 50% of the game. Another situation is that I get winning rates ranging from 45% to 60% in different spider card games, and there is no evidence that my winning rate has improved in the process of using these programs (that is, my winning rate does not show a positive correlation over time).

A more interesting free online card games website Pipkin's Idiot's Delight Solitaire Server, which contains a lot of card games. It allows players to specify a "number of seeds" in a number from 1 to 999999. For example, if the seed count is 142857, the first 10 cards will always be 2J56J9JQ59, but the combination will be different. It is important to note that if the player randomly generates a long number of seeds before the game, then the program cannot adjust the difficulty level according to the player's winning rate. It is for this reason that you can choose this site to estimate the winning rate.

Rejecting the zero hypothesis when the zero hypothesis is true is called the first kind of error, and its probability is equal to the level of significance. Another kind of error in the hypothesis test is called the second kind of error, which means to accept the zero hypothesis if the zero hypothesis is false.

I played 100 games on Idiot's Delight, using a seed count from 1 to 100. In the end, I won 59 games and lost 41. So I estimate that when I play the "unbiased" spider card game, the winning rate will be about 59%.

It's probably worth playing 100 games of Spider Solitaire on Free Spider Solitaire. Although I chose to play the game here, after the experiment, the game experience here is really "bad": although you can win, it will be difficult for even the master players to play. Each game records the winning or losing results of the game as well as AGT and ATSV data. I observed that the p values of AGT and ATSV are 0.115 and 0.201, respectively. This means that both AGT and ATSV data are lower than expected (that is, players will suffer), but because both values are higher than our threshold of 0.05, they are not statistically significant: this may be due to accidental changes that lead to lower values.

Unfortunately, I only won 46 of those games, 13 games less than expected. This indicates that further testing and verification may be needed. However, to know that the winning rate of each player is different, there is a good chance that I have not played my best in these 100 innings.

My conclusion is that there is not enough evidence to prove that the program on Free Spider Solitaire is biased. The number of wins in 46 games is a bit frustrating, but indeed, the process has stood the test this time. However, other spider card programs may not be so lucky.

Author: Trevor Tao

Translation: Dannis

Revision: Nuor

Original text link:

Https://plus.maths.org/content/spider-solitaire

This article comes from the official account of Wechat: Institute of Physics, Chinese Academy of Sciences (ID:cas-iop), author: Trevor Tao

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.