Boat for playing stone, paper, scissors

Theory

After reading this, it was decided to find a practical application of the mechanism of the fortune-teller Shannon. If we consider a person as a finite state machine, then the input data and the initial state completely determine the current state and output data. Immediately I will say the demo of the game and its source is not.

The game itself consists in choosing and showing the opponent one of three options: a well (stone), scissors and paper. Moreover, the scissors sink in the well (blunt on the stone), scissors cut the paper, the well is covered with paper (the stone is wrapped in paper). Denote:

1. 0 - well (stone)
2. 1 - scissors
3. 2 - paper

Suppose that the game is played long enough so that statistics can be collected, but not so long that a person starts to change his behavior, having understood the prediction algorithm. We have a sequence of pairs of numbers: (0, 1) (0, 2) (2, 2) (2, 0) ..., where the first number was shown by the bot, the second - by the person. To determine the winner in the pair, compare the numbers. (0 - 1)% 3 = 2, then the person lost, (0 - 2)% 3 = 1, then the person won, (2 - 2)% 3 = 0, a draw. Denote n - the length of a sequence of numbers of pairs. The number of possible sequences is 3 ^ n. When n = 5, we get 243 variants, which is much more than 32 for two choices. It is clear that getting all the options in one game is unlikely, so let's improve the fortuneteller. A person does not make every choice relying on all n elements of a sequence of numbers; he ignores some of its elements. Let's call these elements empty.

Total, input data for one of the prediction variants: (0, 1, Ø, 2, 0): 1. Numbers in brackets - alternating previous bot and man selections, the number after the colon is the current person choice. Based on the assumption of human predictability, variants, for example, (0, 1, 2, 2, 0): 1 and (0, 1, 2, 2, 0): 2 are not likely to be equally likely. By calculating which of them happens more often, you can get a more likely choice of a person. But it is precisely this variant of the penultimate that may not be repeated throughout the game in order to take this into account and need empty elements. Record (Ø, Ø, Ø, 2, 0): 1 means that after a couple (2, 0) a person chooses 1, and record (Ø, 1, Ø, 2, 0): 1 - after a couple (2, 0) a person chooses 1, if before that the bot chose 1. In total, there are 2 ^ n such records for each game game, going through all combinations of numbers in the record, replacing all those that did not fall into it with Ø.
')
Total records will be 3 * (3 + 1) ^ n. Three entries for the current choice of a person (well, scissors or paper) are multiplied by the number of variants of the preceding sequence, taking into account the additional option - an empty, non-essential choice.

An array of records allows you to make generalizations, for example, a person chooses a well more often, then the record counter (Ø, Ø, Ø, Ø, Ø): 0 must contain a larger value than (Ø, Ø, Ø, Ø, Ø): 1 or Ø, Ø, Ø, Ø, Ø): 2. Having solved a problem with a generalization, we can take n much more, its value is limited by the memory size and the time for the bot to move.

Each time a person makes a choice, the bot changes 2 ^ n values, and when it is necessary to predict, simply add the values ​​of 2 ^ n counters corresponding to the prehistory for each of the three possible current choices of a person, and choose the larger one. If there are no counter values ​​(at the beginning of the game), then it chooses a random one. Then adds 2 modulo 3 to get his value to win.

What is of interest is not the bot itself, but the comparison of the game profiles of different people, as representatives of various social groups, what information can be obtained about a person simply by playing with him (albeit for a very long time).

To calculate the degree of remoteness of profiles from each other, you can use an estimate similar to the Pearson criterion . Only we are not interested in the question: does the sample fit the distribution, but the degree or “probability” of compliance, if we consider one array of counters A1 as sampling data, and the second A2 as its possible distribution.

d_j = sum ((A1 [x_1, x_2 ..., x_i, ... x_n] [x_0] - A2 [x_1, x_2 ..., x_i, ... x_n] [x_0]) ^ 2 / A2 [x_1, x_2. .., x_i, ... x_n] [x_0]), the sum is taken over all the counters corresponding to the records with j non-empty values, x_0 is the possible current choice of a person (values ​​from 0 to 2), x_i have values ​​from 0 to 3, so as one of the values ​​means empty, let it be 3.

Since the distance should be the same in both directions, and also because a significant part of the array will contain zeros, the denominator should be replaced with the counter value of the corresponding record, whether the choice of a person is random S / 3 ^ j, where S is the number of games played, j is the number not played empty values ​​in the record.

The distance measure will be the probability of a mismatch of the distributions of A1 and A2. For the distribution of chi square important number of degrees of freedom, that is, the dimension of the distribution. Since the number of degrees of freedom is different and corresponds to our j, we simply add the values ​​of the corresponding distribution function for each d_j:

p = sum (F_j (d_j)), where p is a measure of the range, the sum is taken over j, F_j is the distribution function chi square for j degrees of freedom.

To test the fortune-teller algorithm Shannon a small demonstration .

The fortune teller's algorithm seems too primitive, but it is fast, and its modification for the game is well paralleled.

Earlier it was mentioned in the article Hierarchical Temporal Memory (NTM) and its self-learning algorithms that some neurons can be thought of as elements predicting their own activity.

There was a Reddwarf post for creating a Java server using the example of the online game Stone-Scissors-Paper: Server and Reddwarf using the example of the online game Stone-Scissors-Paper: Client .

The implementation of the bot, similar to that described above (link from the comments).