During the first year of my undergraduate studies, I lived in a boarding house together with around 10 other students. Among of them, there was a
nerd programming expert that excel at every programming language that I know at that time (At that time, I only know C++). One time, he has a programming assignment for his class and for that he made a number guessing game. At that time, the game was called (or at least that is what he names it) Dolpeng. However, after a quick google search, I just found out that the game’s real name is Bulls and Cows. The game get him an A, so, he was so proud and shared his game in the network (along with other ‘adult’ stuff that he downloaded for us). And I accidentally ran into that game folder when I was browsing through his ‘adult’ stuff was curious, so I take a quick look at it.
The game (Bulls and Cows or Dolpeng or whatever the name is) is a number guessing game. It is played by two players only. Each player must choose their own secret number that consist of 4 non-repeating digits (for example: 1457). A number with repeating digits like 1272 cannot be used. After deciding the secret number, each player takes turn guessing the other player’s secret number. After a player (guesser) make a guess, the other player (guessee) must evaluate the guess and tell the number of bulls and cows of the guess as a hint for the guesser. Then the players switch turn until a player correctly guess the other player’s secret number.
Evaluating the guess and providing hint for the guesser is done as follows. If in the guesser’s guess, there is a digit that also exist in the guessee’s secret number and that digit is located at the same position as it is on the secret number, it is called bull. If in the guesser’s guess, there is a digit that is also exist in the guessee’s secret number but it is not located at the same position as in the secret number, it is called cow. From the number of bulls and cows of the guess, the guesser must be able to predict the guessee’s secret number.
For example, if the guessee’s secret number is 1250 (This number, of course, must not be told to the guesser) and the guess is 4510, then the number of bulls is 1 (The bull is 0) and the numbers of cows is 2 (The cows are 1 and 5). Note that sometimes a guess may not contain any bulls or cows at all. To make it clearer, here are several list of guess and their respective numbers of bulls and cows (The secret number is still 1250).
Guess: 1250, Bulls: 4, Cows: 0 (Guesser guessed correctly). Guess: 4310, Bulls: 1 (0), Cows: 1 (1). Guess: 1273, Bulls: 2 (1 and 2), Cows: 0. Guess: 5120, Bulls: 1 (0), Cows: 3 (5, 1, and 2). Guess: 5789, Bulls: 0, Cows: 1 (5) and so on...
Okey, that’s it about the game. Now back to the story.
At that time, the game that my friends make was designed to be able to guess our secret numbers. So, what the game does was tells me to choose a secret number (in my mind, I did not input my secret number to the game) and asks your input of the number of Bulls and Cows for the guess that it made, and after a few guess (I forgot how many), it correctly guess my secret number. At that time I was really blind to programming and was really amazed by his game. I thought that this guy is a Genius that someday in the future he will win a Nobel prize or something like that. But it turned out that I was wrong. He wasn’t that genius (because he haven’t win any Nobel up to now). It is only me that was too idiot to understand it.
Now that I’ve become smarter than I was, I finally found out how to solve the game. So, I decided to make similar game for my MATLAB Fun Toolbox. So, long story short (I notice that this is the most freuqnt pphrase that I use everytime I announce that I’ve created something new for my MATLAB Fun Toolbox), here it is, the game’s screenshot and a video capture of the game.
I provided four modes for the game. The first one is where you play solo to guess a secret number. Nothing special here other than doing Bulls and Cows evaluation for player’s guess. The second one is where COM guesses your secret number. This mode is what was shown in the two video captures above and I think that this mode is the most interesting mode, because COM fill be able to found out your guess in not less than 8 guesses. I’ve done some simulations on the ‘solving’ algorithm and the result shows that the algorithm needs 5 guesses in average to find out the secret number with the worst case scenario of 8 guesses. I will talk about the ‘solving’ algorithm in the later part of this post (I found out that hyperlinking post to itself is a little bit weird but I’m gonna do it anyway:D, just don’t click the link, it is useless:D). For now, let me finish explaining the game mode.
The third one is player versus COM. It is where both player and COM take turns guessing each other’s secret number. This mode is like combining the first and the second mode altogether in turns. The fourth one is for player versus player. Yup, player versus player. You must be thinking, was do we need this mode? You can just play it together with your friends on a piece of paper. Why all the trouble? Well, the reason is that when playing the game, players often make mistake when evaluating its opponent guess. It might be on purpose or not, but nevertheless, it is not fair to the guesser. So, as a fail safe (or a referee, whatever that is), in this fourth mode, both player’s guess and Bulls and Cows number are being checked by COM for its consistency. Don’t worry, COM can do that without you inputting your secret number to the game (and risk your opponent knowing it by peeking). Instead, the ‘solving’ algorithm (that I mentioned earlier) are applied. This way, no one can cheat!
So, that’s it about the game. Now, let’s talk about how to solve and beat the game, hence code the ‘solving’ algorithm. Well, I’ve looked up on internet and there are a lot of methods to solve the game. Some uses fancy stuff like Genetic Algorithm and other optimization method that was too high for my intelligence. So, I decided to use one simple method: the elimination method. This method is actually a semi brute-force method and is not ideal is you are looking for optimization, but, to the hell with that, this is the only method that I can understand, so I’m just gonna use it.
Elimination method is done by firstly creating a list of all possible numbers for Bulls and Cows game. This range from 1234 to 9876 and the permutation in total will have 5040 possible combinations (5040=10*9*8*7). From this list, a number are randomly chosen as the guess. The guess then will be evaluated by user/player and the number of Bulls and Cows will be given (This is the reference number of Bulls and Cows). Then, all numbers in the list are evaluated against the guess for the number of Bulls and Cows. All numbers in the list that yield different number of Bulls and Cows when it is evaluated against the guess will be removed from the list (Note that I emphasized on ‘and’ because both the number of Bull and Cow must be the same with the reference or it is eliminated). From this the list will now have fewer number and the second guess is made by choosing randomly again from this list. This continues until all the numbers in the list are eliminated except one, which is the secret number itself.
Let’s try this for example. Let’s say that your secret number is 1234. If a guess of 1357 is made, it will have number of Bulls of 1 (1) and number of Cows of 1 (3). Then, 1357 is evaluated for all 5040 numbers in the list. This will yield 5040 combination of numbers of Bulls and Cows. The number whose number of Bulls and Cows is not 1 are eliminated from the list. For example, number of 1357 from the list will yield 4 Bulls when evaluated against 1357 (the guess). This number will be eliminated from the list because it is not possible that this number is the secret number. (I hope you understand that because I don’t how how else to say it).
The cool thing about this method is that if somewhat there is a mistake from user/player when he is evaluating the guess (either accidentally or not), all numbers on the list will be eliminated, leaving nothing in the list. When this occurs, no doubt someone has made a mistake. I also read it somewhere else that you can further optimize this method by ‘smartly’ choosing guess from the list instead of doing it randomly. But it complicates tings too much and it only improve the average guesses needed to find the secret number insignificantly, so I decided not to included it and go on with random guess from the list.
Wow, that was a lot of writing for one post. I hope you can understand what I mean and wasn’t falling asleep in the middle of reading this post. As usual, the game is downloadable from my MATLAB Fun Toolbox page. Please leave any critics or comments.