Bulls and cows - a logical game, during which, for several attempts, one of the players must determine what the other player is up to. Variants of the game may depend on the type of predictable sequence - it can be numbers, colors, icons or words. After each attempt, the conceived player puts up a “rating”, indicating the number of guesses without coincidence with their positions (number of “cows”) and complete matches (number of “bulls”). The roles of the participants in the game are not equivalent - the guesser must analyze the attempts made and the ratings obtained, that is, his role is active. His partner only compares the next option with his plan and gives an assessment according to formal rules, that is, his role is passive. To counterbalance the roles, two opposing parties play simultaneously.
| Bulls and cows | |
|---|---|
 Screenshot of the computer version of the game. The game is won in seven moves | |
| Players | 2 |
| Batch duration | 5-30 minutes |
| Complexity of rules | Low |
| Strategy level | Low |
| The influence of chance | Low |
| Develops skills | logical thinking, counting, memory |
Initially, the game was conceived for two players, but with the advent of computer versions, the option became popular when the player guesses the number conceived by the program, that is, plays alone. To play together, it is enough to have paper and a pen. In electronic versions, the game at a distance against the enemy is provided by the multiplayer function.
Content
Game Rules
In the classic version, the game is designed for two players. Each of the players concocts and writes down a secret 4-digit number with non-repeating numbers [1] . The player who starts the game by lot makes the first attempt to guess the number. An attempt is a 4-digit number with non-repeating numbers that is communicated to the enemy. The enemy responds in response to how many numbers were guessed without coincidence with their positions in the secret number (i.e. the number of cows) and how many were guessed right up to the position in the secret number (i.e. the number of bulls). For example:
Concealed secret number "3219".
Attempt: "2310".
Result: two “cows” (two digits: “2” and “3” - guessed at the wrong positions) and one “bull” (one digit “1” guessed right up to the position).
Players make attempts to guess in turn. The winner is the one who guesses the number first, provided that he did not start the game. If the guesser started the game, his opponent is given the last chance to guess the sequence.
When playing against the computer, the player enters combinations one after another until he guesses the whole sequence.
Game Variations
In the game “mastermind” ( Eng. Mastermind , possible translation: “Intellectual, clever”) a sequence of 4 color chips is made up, moreover, colors can be repeated. In a complicated embodiment, a sequence of 5, 6 or more chips may be used [2]
There is a variant of the game with words . That is, the player makes a word, usually of 5 letters (in the nominative case is singular according to the rules of the game “ bulda ”), and the opponent’s task is to guess it using the same correct words from the Russian dictionary as attempts. However, there is an option when it is possible to use an arbitrary combination of letters.
Algorithm
In the general case, the number of options for a k-digit number in an N- number system without repetitions will be equal to the number of placements : .
In the case of a variant with repetitions, the number of variants will be equal to .
Most of the known algorithms are the variations of the full enumeration algorithm with a certain heuristic . Due to the fact that the number of options is not so large and the direct enumeration scheme is elementarily implemented, the computer plays “bulls and cows” much stronger than a person. The more signs in the number, the greater the difference in the strength of the game of a person and a computer.
As Donald Knuth showed, for the game Mastermind (6 of 4 options) with the strategy proposed by him, it takes no more than 5 attempts to guess any combination, and on average 4,321 attempts to guess [3] [4] .
Knuth's strategy is as follows:
- Build the set S from 6 4 = 1296 possible codes (1111, 1112, ..., 6666).
- Make the first move with a code of two matching digits, for example, 1122 (Knut gives an example showing that other initial approximations, such as 1123 or 1234, will not always be able to guess the combination in 5 attempts).
- If the combination is guessed, the algorithm ends.
- Otherwise, remove from S all codes that, being secret, would give a result different from the one obtained.
- Make the following move according to the minimax rule:
- For any combination of 1296 initial ones (including those that are not in S), calculate how many possible codes will be deleted from S in case of any move result. The number of points awarded to a possible move is equal to the minimum number of elements that can be removed from S.
- One pass through the set S for each unused combination of 1296 possible will give a certain number of cows and bulls; the combination of bulls and cows with the most matches will remove the least number of options from the set; the number of points accrued to the move will be equal to the number of elements in S minus the largest number of matches.
- Of all the moves with the maximum number of points, preference is given to the move that is in S. If there are several such options, then you can choose any of them. To simplify the procedure for choosing an option, Knut suggests choosing the move with the smallest numerical value (for example, 2345 is less than 3456).
- If the best move is not in S, then the next move will definitely not end the game.
- Repeat from step 3.
Implementations
There are many options for electronic implementation of the game, including for mobile phones and mobile computers.
Board games Mastermind are popular all over the world. The most common variations are:
- classic, four non-repeating numbers.
- regular, 4 places for chips of 6 colors with repetitions.
- advanced, 5 places for chips 8 colors .
In Culture
- In the computer game Sleeping Dogs , the game Bulls and Cows is an imitation of hacking computer police networks.
- In Fallout 3 , Fallout New Vegas and Fallout 4 games, the process of hacking computer terminals is a type of the game “Bulls and Cows”, in which, if an unsuccessful attempt is made, only the number of “bulls” is reported [5] .
- The game “Bulls and Cows” is found in the computer game “ Space Rangers ” during the passage of the text quest “Diamond”.
Notes
- ↑ The Bulls and Cows game in Microsoft Excel . Into the world of computer science , No. 78.
- ↑ Investigations into the Master MindTM Board Game
- ↑ Mastermind Optimal strategy
- ↑ Knuth, Donald. Selected papers on fun and games. - Center for the Study of Language and Information, 2011 .-- P. 226. - ISBN 9781575865843 .
- ↑ "Hacking a terminal" .
Links
- Candidate of Technical Sciences E. Gick. Bulls and cows. “Science and Life,” No. 2, 1978, p. 150-151; No. 8, 1978, p. 142-143.
- Charles Weatherly. Etudes for programming, The Great Combinator. M .: 1982, p. 140.