Bulls and cows Olympiad Plus. Development of the optimal strategy of the game "Bulls and Cows" based on the theory of information. Watch what is "bulls and cows" in other dictionaries
Bulls and cows - logic game For two players. It is enough to have a piece of paper and a handle, free time and a little luck. As a rule, such a time is in schoolchildren and students. But to me, your submissive servant, did not happen in my years to learn this fun. Although why not smash your gray substance at your leisure? This is a good training for the mind that does not require strong tension, and how the entertainment is quite justified.
In its classic version, the rules are very simple and not attracted. Two people play, each comes in secret from the opponent four digits without repetitions. For example, it may be the number 0834. Zero is also a digit and may well be in the first place.
Further, players take turns make moves, that is, trying to guess the opponent's conceived opponent. But they must also ask in the form of a four-digit number. For example, we will ask: "Your number 3094?". In response, we must report the number of bulls and cows. Bull is a figure that is in our specified number and is on the same position. And the cow is a figure that is also in our number, but is not in his place. In our case, we get two cows, these are figures 3 and 0, and one bull, it is 4. Now we will ask we, and so on, until someone does not fully solve the number. That is, in the answer, he will receive four bulls. The picture shows an example of the game. Time for one batch requires quite a bit. In practice, it is usually required from 5 to 8 moves, but there are unicumes that manage and defeat three strokes. Of course there is a considerable share of luck.
On our site you can play the "bulls and cows" both against the computer and online with a live opponent. At the bottom of the game room for your convenience there is a gaming chat in which you can choose an opponent for playing on the network, or ask the Council. Just if you have comments on the implementation of our game, suggestions for its improvement or development - then write to us. You can write both on the forum and our mail [Email Protected]website.
Game varieties
Great set games:
- 1. By type of guessing sequence - it may be a number. In the classics, this is a four-digit without repetitions, consisting of numbers from 0 to 9. The number of digits can also increase the possibility of repeating them. As a sequence, color, which is cryptogram, word can be used.
- 2. By type of game itself. In the era of computers, it is possible to play one. When a person is guessing the number planted by a computer or against the computer. But it is difficult to win the car, there is more of the question of the correct algorithm in it. Players play a classic option, but are at a considerable distance from each other. Players guess the number in turn, which was conceived by the computer - there are options for the so-called hot chair, when opponents are located near and play with one computer and remotely.
At the moment, only the classic version of the game is implemented. If you have ideas, what kind of bulls and cows should appear on our website, then share them with us.
Annotation: The game "Bulls and Cows" In this lesson, consideration of the previous game "Wake up the number" continues. A binary search algorithm that gives an optimal search strategy of the intended number is discussed. The implementation of this strategy is provided. The "Computer, Guess the number" button appears in the game interface. The project implementing the project new game "Bulls and cows", where you also need to guess the number planted by a computer. Find the intended number in this game is more difficult, since it is allowed to ask the question of only one type of "number equal to N?" For technical reasons, the next lecture was recorded, where the variation of the project "Bulls and Cows" was considered, in which the intended combination was randomly chosen from the set, including 12 pictures. In the text accompanying this lesson, a brief description of this project is given.
The lesson begins with the analysis of the homework performed by a schoolboy. In your homework, it was necessary to add new buttons to the game interface and write the corresponding event handlers in the code. The schoolboy added two buttons "greater than or equal" and "less or equal." Correctly wrote the appropriate event handlers. Although the answer to the question was formed not quite accurately, the proposed decision deserves a good assessment. Inaccuracies of response are easily eliminated.
When schoolchildren, playing the game, gave way to a computer planned, then, as a rule, received the title of "Master of the game". This allowed an intuitive level to understand the essence of one of the classical data search algorithms in an ordered set - a dichotomy or binary search algorithm, for the sake of studying which this game was written.
What is the essence of the game "Say the number"? The computer thinks the number from some interval. The interval boundaries are communicated to the player. The player has the opportunity to choose a number of N from this interval and set a computer to a question of one of three types: "Number N is more conceived", "Number N is less than planned", "Number n equally intended." For each question, the computer responds to "yes", if the statement is fair, and no otherwise. To become a master game, you need to ask no more than k questions, where K depends on the interval.
Optimal strategy Games are determined by the binary search algorithm, which is also called the dichotomy algorithm or the division method in half. Consider it in more detail.
Algorithm of binary search
The essence of this algorithm will look at the example of the search for the intended number in a specified interval. What is the initial uncertainty? The specified interval is MAX - min + 1 number. So in the interval is a hundred one number and the intended number can be any of them. So uncertainty is equal to the number of numbers in this interval. How to ask a question so that it is possible to reduce uncertainty as possible. The middle of the interval is the MID number (max - min) / 2, in our example - this is the number 50. By specifying the question "the intended number is more (less) MID", with any answer, the uncertainty is reduced by half. Having received the answer "yes" to the question "conceived more MID?" The value of the bottom limit of the MIN interval changes to the MID + 1. Otherwise, the upper limit of the MAX is changed to the MID value. With each question, the interval is shrinking twice. When the interval is reduced to one number, the question of equality is guaranteed by a conceived number. The total number of issues that should be specified equally rounded in the largest value of the function log (n) is a binary algorithm of N number N, where N is the initial uncertainty, the number of numbers in the interval.
Consider an example. The number 83 in the interval is conceived. The optimal number of issues allowing you to guess the planned number equal to the log 101, rounded to the nearest whole, which gives the number 7. Here is a sequence of 7 issues, allowing to guess the planned:
- Number more than 50? - Yes.
- Number more than 75? - Yes.
- Number more than 88? - Not.
- Number more than 81? - Yes.
- Number more than 84? - Not.
- Number more than 82? - Yes.
- Number equal to 83? - Yes.
The binary search algorithm is widely used in a variety of applied tasks, - everywhere where it is required to find an element in a sorted set, over the elements of which the comparison operation is defined on the "greater", "less".
How does the computer play?
A computer, of course, "knows" the optimal strategy and therefore always reaches the title of "Master of Game" of any level. The preferred version of the strategy uses the "number more" type. With each question, the uncertainty interval is reduced by half until it contains exactly one element, which is the intended number. The computer strategy is determined by the disassembled by the binary search method. So the handler of the CLICK Event Handler "Computer, Guess the number" is the implementation of the binary search algorithm, supplemented by the output of the corresponding messages. This is what the CLICK event handler code looks like:
///
Hello.
In autumn on the 2nd year as a laboratory work on the "automatic theory", the teacher in the course came up with us tasks, focusing on our wishes in the assessment. Basically it was games. Someone got hockey, someone tennis, I got not so famous logical game "Bulls and cows".
It was necessary to realize at least some reasonable behavior of the computer in the game with a person. But I went on and after a month the computer in most cases was easily played by my classmates. And on the subject was obtained automat. Program Get after describing algorithms.
The essence of the game
The player and the computer make four-digit numbers using numbers from 0 before 9 . Players are trying to solve the numbers of the opponent, sending it the possible options of numbers, in response to get two numbers - the number "Bykov" and number "Cows". What are these numbers?- Bulls are the correct numbers on the right places. Four "Bull" - the key to the victory, the dream of every farmer.
- "Cows" - the correct numbers on the wrong places.
Sung one 1622 . If we are supposed 6112 , then in response will come: 1 bull(fourth digit "2" in its place), 2 cows(Six and units are not in their places).
Operating the enemy's "Skot" data, you need to guess the number faster.
The first trivial algorithm, which so encounters it, is to sort out the sets "1111", "2222", "3333" ... As long as the full set is received, and then generate the movement of this set.
For example, the same number is guess 1622 , we suppose "1111"we get in response "Bull", then "2222" - We get in response already 2 "Bykov", "3333" - Empty, "4444" - Empty, "5555" - Empty, "6666" - 1 bull.
There will not continue further, since already scored 4 bulls in sum. It remains to find the desired combination. We will generate a permutation until we get ta-daaam: "1226", "1262", "1226", "1262", "1622" . Everything.
Obviously, the algorithm is not very good, but understandable and not confused. The maximum number of moves for guessing - 10 ("7890") + 24 permutations. 34 - This is at the worst case. Of course, it is possible to bust and permutations in every way to optimize, for example, searched alternately from two ends - "1111", "0000", "2222", "9999" ... It is also to optimize the generation of permutations in the presence of the same digits (as in our example - we ask the same thing several times).
But let's not do it. Let this strategy be with us light level Computer complexity.
I sat on a lot on the pair and played myself with myself, trying to come up with some kind of cool algorithm. But only a single ideas came from which I could not compile a single strategy. Began to study literature. I came across articles, the genus "Guessing for 7 moves." They did not attract me, because there highly Many branching. But reading the book of our Kirov professor (but not from our university) CM. Okulova "Programming in algorithms", I found a description of a fairly simple and fairly effective algorithm. It uses the so-called "Single method" (An example is the famous "Decade Erasopena" - Classic task of finding simple numbers). We consider the final set of all possible numbers and each move exclude all the elements of the set, not representing interest.
For example, for the mandated number 1234 We suggested 5678 and got 0 bulls and 0 cowswhat to think - we exclude all the numbers containing 5, 6, 7, 8 . You can immediately estimate how much is passed from 10000. Do not be afraid of many of 10000 Elements. Per 5-6 There will be only a few numbers.
Let's start with data structures. Code on Pascal:
Const pmax \u003d 10,000; Type Post \u003d String; VAR A: Array of POST; // Most B: Array of Boolean; // Array of flags, 1 - So suitable, 0 - excluded
Initialization:
T: \u003d 1; For i: \u003d 0 to 9 do for a j: \u003d 0 to 9 Do for k: \u003d 0 to 9 do for L: \u003d 0 to 9 Do Begin A [T]: \u003d INTTOSTR (I) + INTTOSTR (J) + INTTOSTR (k) + INTTOSTR (L); // Formulate the set Inc (T); end; For i: \u003d 1 to Pmax Do B [i]: \u003d True; // Default all numbers are suitable
Function implementing an analysis of the set of sets by variable values \u200b\u200b(BK, KR - bulls and cows)
FUNCTION PR (A, B: POST; BK, KR: Integer): Boolean; // B - our stroke, a- element of the "tested" of the set VAR i, x: integer; Begin x: \u003d 0; For i: \u003d 1 to 4 Do // Check for bulls IF A [I] \u003d B [i] THEN INC (X); if X.<>bk then begin pr: \u003d false; exit; end; x: \u003d 0; For i: \u003d 1 to 4 Do // Check for Cows IF (A [I]<>b [i]) and (POS (B [i], a)<>0) THEN INC (X); If X. So after each of our stroke, launch the sieve For i: \u003d 1 to Pmax DO IF B [i] and NOT PR (A [I], HOD, BK, KR) THEN B [i]: \u003d false; In conclusion, we can say that the algorithm is spent on memory and compared with standard algorithms will think "longer", but how easily it is completely optimized. Hello. The first trivial algorithm, which so encounters it, is to sort out the sets "1111", "2222", "3333" ... As long as the full set is received, and then generate the movement of this set. I sat on a lot on the pair and played myself with myself, trying to come up with some kind of cool algorithm. But only a single ideas came from which I could not compile a single strategy. Began to study literature. I came across articles, the genus "Guessing for 7 moves." They did not attract me, because there highly Many branching. But reading the book of our Kirov professor (but not from our university) CM. Okulova "Programming in algorithms", I found a description of a fairly simple and fairly effective algorithm. It uses the so-called "Single method" (An example is the famous "Decade Erasopena" - Classic task of finding simple numbers). We consider the final set of all possible numbers and each move exclude all the elements of the set, not representing interest. Const pmax \u003d 10,000; Type Post \u003d String; VAR A: Array of POST; // Most B: Array of Boolean; // Array of flags, 1 - So suitable, 0 - excluded Initialization: T: \u003d 1; For i: \u003d 0 to 9 do for a j: \u003d 0 to 9 Do for k: \u003d 0 to 9 do for L: \u003d 0 to 9 Do Begin A [T]: \u003d INTTOSTR (I) + INTTOSTR (J) + INTTOSTR (k) + INTTOSTR (L); // Formulate the set Inc (T); end; For i: \u003d 1 to Pmax Do B [i]: \u003d True; // Default all numbers are suitable Function implementing an analysis of the set of sets by variable values \u200b\u200b(BK, KR - bulls and cows) FUNCTION PR (A, B: POST; BK, KR: Integer): Boolean; // B - our stroke, a- element of the "tested" of the set VAR i, x: integer; Begin x: \u003d 0; For i: \u003d 1 to 4 Do // Check for bulls IF A [I] \u003d B [i] THEN INC (X); if X.<>bk then begin pr: \u003d false; exit; end; x: \u003d 0; For i: \u003d 1 to 4 Do // Check for Cows IF (A [I]<>b [i]) and (POS (B [i], a)<>0) THEN INC (X); If X. So after each of our stroke, launch the sieve For i: \u003d 1 to Pmax DO IF B [i] and NOT PR (A [I], HOD, BK, KR) THEN B [i]: \u003d false; In conclusion, we can say that the algorithm is spent on memory and compared with standard algorithms will think "longer", but how easily it is completely optimized. When I entered the institute, the game "Bulls and Cows" was very popular. So coincided that at the same time I read the mathematical novel Alfred Reni "Diary. - Student's notes on the theory of information. " Thanks to this article, I met. And I had the idea of \u200b\u200bhow to improve my performance in the "bulls and cows", relying on new knowledge. Briefly remind the rules.Two play. Everyone thinks and records a secret 4-digit number with non-repeating numbers (the first can be zero). A player who starts the game by lot, makes an attempt to guess the number. An attempt is a 4-digit number with non-refining numbers, reported by the enemy in the form of a question. The enemy speaks in response, how many figures are guessed with the coincidence of their positions in the secret number and how much is guess without coincidence. For example: the secret number 3219 is conceived; Attempt (question) 2310; The result (answer): one "bull" (figure 1 from the question enters the secret number and is in its place) and two "cows" (figures 2 and 3 from the question are included in the secret number, but they are not in place). The answer is reported in the form of a 2-digit number. In our example, the answer is 12 (one "bull", two "cows"). Players make attempts in turn. The one who first receives the answer to its question 40. Download a note in format or, examples in format, an example in zip format (within an Excel file by 57mV). These are the ideas of the theory of information seemed to me useful to improve the indicators in the game (see): For a better understanding of the material, it is also useful to open an excel file. 1. The secret number can be refined 10 * 9 * 8 * 7 \u003d 5040 (in the first place there can be any of 10 digits, on the second - any of the 9 remaining, etc.). In order to form an array of permissible numbers, I used simple algorithms in Excele (see "Subc1" and "subg."). Since the probability of being conceived by any of the 5040 numbers is the same, uncertainty (H) is calculated using the Hartley formula: H \u003d log 2 N. Before the start of the game, the uncertainty is log 2 5040 \u003d 12.30 bits of information. 2. It is clear that the first question can be any, for example, 0123. 14 replies are possible on it (see also the "Question1" list of Excel files): Here: P is the probability of a response, n is the uncertainty that remains after the corresponding answer, H is the amount of information obtained if one or another answer was implemented. The most likely answer is 01, meaning that only one digit is among the question in a secret number, and it is not in its place. Answer 01 implies that one of the 1440 numbers could be conceived, that is, the uncertainty remaining after this response is log 2 1440 \u003d 10.49 bits, and the information obtained with such a response is 12.30 - 10.49 \u003d 1.81 bit. The answer 40 gives 12.30 bit of information, and the uncertainty after it does not remain j. Since the probabilities of answers are different, the amount of information contained in the question is determined by the Shannon formula: H (x) \u003d p 1 log 2 (1 / p 1) + P 2 Log 2 (1 / p 2) + ... + p n log 2 (1 / p n). The first question brings 2.77 bits of information. 3. When choosing a second question, three ideas formulated above should be followed. In practice, this means that the question must be allowed to answer 40. The rule of formation of the second question.Let the first question (0123) we received an answer 01. For the second question, take one digit from the first question, put it on a new place and add three new numbers. We obtain, for example, 4561. If a question 1 was obtained, for example, an answer 11, you need to take two numbers from the first question, one to leave in my place, the second to put on a new place, and add two new numbers; For example, 0435. On the question 2,4561 14 replies are also possible (see "Question 2" list): We selected the second question brought 2.86 bits of information. Let's see how much information will give other second questions. For these purposes, I created a separate file "Non-optimal second question.xlsx" (he "weighs" 58mV, so be careful with it :)). The second question can be one of 5040 possible numbers (including the repetition of the first question). As a result of this study, I received the amount of information that these or other issues give (I remind you that the analysis is made under the assumption that the first question 0123 gave an answer 01). For example, the question 2 - 0123 gives zero bits of information, since it is only one answer 01, a (for n \u003d 1) log 2 1 \u003d 0. Question 2 0132 gives 0.65 bits of information, question 2 0148 - 2.53 bits of information . The maximum amount of information gives 1440 second issues formed by the above-described rule. The results of the study I transferred to the "Different Questions2" list "Bull-Cow.xlsx" file and then I will only talk about this file. As I said, the maximum amount of information is 2,859 - will be obtained for a question 2, prepared as follows: You need to take one digit from the first question, put it on a new place and add three new numbers: It can be seen that another 180 questions give almost the same information - 2,774 bits. Such a number of information will be obtained when responding, for example, to a question 1045 (see the "Question of the Point" sheet). But this question can not give a response 40! That is, the question is prepared with a violation of the formulated rule. How big is the difference in information between 2,859 and 2,774 bits!? At first glance, it does not look big. On the other hand, with the most unfavorable answer to the question 2,4561 (01), there will be 378 options for the secret number, and with the most unfavorable answer to the question 2,045 (also 01) - 408 options. 8% more! This is the price of a non-optimal question. 4. In preparing the third (and subsequent) issues, I follow the following mnemonic rule. It is necessary to make an aggregated table of all possible secret numbers that satisfy the responses to previous questions. After that, to form a question3, using the part of this table, which contains more options (the assessment is arising "on the eyes"). A little confusing? Let's consider two examples. Example1. The first option: a unit includes, then not included, nor 023, nor 456; That is, they are included, not used in the first two questions, numbers - 789. We get a set of numbers of the secret number 1789 (the order of their location any, satisfying the responses to the first two questions). Options that meet this set, 12. The second option: the unit is not included, then one digit is among 023, one - out of 456, and two from 789. I write it up so: The estimated number of digit set options is 3 (one of 023) * 3 (one of 456) * 3 (two of 789) \u003d 27. And taking into account the locations of the numbers of the variants are significantly more than 100. For the question 3 we take one digit out of 023, one of 456, two of 789. We have figures so that there are no coincidences of location sites with a question1 and a question2. Moreover, we have figures that have previously met (4 and 2) in completely new places, that is, on the 2nd or 4th. For example, the question 3 7482 is better than 2784. Since in the first case, the 4th and 2-ka stand on the ground, which in question1 and the question 2 they did not occupy. At the same time, in question 3,2784, the number 2 stands in place 4-ki from the question2 (see the "Question3" sheet). The answer to the question 3 4782 contains 2.958 bits of information, and the answer to question 3 2784 - "Only" 2,955. Example2. The first two questions and answers were as follows: First option: Included 13, then not included, nor 02, nor 45, and from the remaining numbers are two: The number of secret numbers in the embodiment1 - 48. The second option: one digit is among 13, then one includes one - out of 02, one - out of 45, and one - out of 6789: The approximate number of secret numbers in the embodiment2 is more than 100. Third Option: Do not include 13, then consist of 02, and 45: 0245. The number of secret numbers in the embodiment 3 - 8. 5. When the secret numbers remain a little (from 4 to 10 ... 20), I turn to full search for all possible options. Play with an algorithm based on the theory of information, and win! Zeplem Kenezhebekov wrote a program that allows you to play with a computer. The program works under Windows 7, 8, 8.1 with Framework 4.5 installed. I really liked the game, but the algorithm is clearly distant from the optimal one. I played three times and won everything three times. Download program in format. http://slovesnov.narod.ru/articles/bullcow.pdf. . To tell the truth, I could not master it 🙂 But mentions the theory of information when I did not find it in it ...
Well, that's all, not at all difficult. My first article, judge strictly.
In autumn on the 2nd year as a laboratory work on the "automatic theory", the teacher in the course came up with us tasks, focusing on our wishes in the assessment. Basically it was games. Someone got hockey, someone tennis, I got not so famous logical game "Bulls and cows".
It was necessary to realize at least some reasonable behavior of the computer in the game with a person. But I went on and after a month the computer in most cases was easily played by my classmates. And on the subject was obtained automat. Program Get after describing algorithms.The essence of the game
The player and the computer make four-digit numbers using numbers from 0
before 9
. Players are trying to solve the numbers of the opponent, sending it the possible options of numbers, in response to get two numbers - the number "Bykov" and number "Cows". What are these numbers?
For understanding, I will give an example: Sung one 1622
. If we are supposed 6112
, then in response will come: 1 bull(fourth digit "2" in its place), 2 cows(Six and units are not in their places).
Operating the enemy's "Skot" data, you need to guess the number faster. For example, the same number is guess 1622
, we suppose "1111"we get in response "Bull", then "2222" - We get in response already 2 "Bykov", "3333" - Empty, "4444" - Empty, "5555" - Empty, "6666" - 1 bull.
There will not continue further, since already scored 4 bulls in sum. It remains to find the desired combination. We will generate a permutation until we get ta-daaam: "1226", "1262", "1226", "1262", "1622"
. Everything.
Obviously, the algorithm is not very good, but understandable and not confused. The maximum number of moves for guessing - 10 ("7890") + 24 permutations. 34
- This is at the worst case. Of course, it is possible to bust and permutations in every way to optimize, for example, searched alternately from two ends - "1111", "0000", "2222", "9999" ... It is also to optimize the generation of permutations in the presence of the same digits (as in our example - we ask the same thing several times).
But let's not do it. Let this strategy be with an easy level of computer complexity. For example, for the mandated number 1234
We suggested 5678
and got 0 bulls and 0 cowswhat to think - we exclude all the numbers containing 5, 6, 7, 8
. You can immediately estimate how much is passed from 10000.
Do not be afraid of many of 10000
Elements. Per 5-6
There will be only a few numbers.
Let's start with data structures. Code on Pascal:
Well, that's all, not at all difficult. My first article, judge strictly.Answer
Number of answers
r
H.
h.
00
360
7,1%
8,49
3,81
01
1440
28,6%
10,49
1,81
02
1260
25,0%
10,30
2,00
03
264
5,2%
8,04
4,25
04
9
0,2%
3,17
9,13
10
480
9,5%
8,91
3,39
11
720
14,3%
9,49
2,81
12
216
4,3%
7,75
4,54
13
8
0,2%
3,00
9,30
20
180
3,6%
7,49
4,81
21
72
1,4%
6,17
6,13
22
6
0,1%
2,58
9,71
30
24
0,5%
4,58
7,71
40
1
0,02%
0,00
12,30
5040
100,0%
12,30
2,77
Answer
Number of answers
r
H.
h.
00
54
3,8%
5,75
4,74
01
378
26,3%
8,56
1,93
02
369
25,6%
8,53
1,96
03
91
6,3%
6,51
3,98
04
6
0,4%
2,58
7,91
10
126
8,8%
6,98
3,51
11
222
15,4%
7,79
2,70
12
83
5,8%
6,38
4,12
13
6
0,4%
2,58
7,91
20
57
4,0%
5,83
4,66
21
31
2,2%
4,95
5,54
22
5
0,3%
2,32
8,17
30
11
0,8%
3,46
7,03
40
1
0,07%
0,00
10,49
1440
100,0%
10,49
2,86
Information from Question2, Bit
The number of such issues
0,000
1
0,650
6
0,811
8
0,918
9
1,899
24
2,104
72
2,258
144
2,268
72
2,365
216
2,372
48
2,530
180
2,624
360
2,664
720
2,756
360
2,766
480
2,767
720
2,774
180
2,859
1440
TOTAL
5040
Question1
0123
Answer1
01
Question2.
4561
Answer2.
01
Question1
0123
Answer1
02
Question2.
3541
Answer2.
02