TUTORIAL ON MASTERMIND CODEBREAKING STRATEGY (6)
DIGITS / COLOURS ARRANGED IN RANDOM ORDER
Game Setting: No. of colours: 7; Start from: Trial 1; Length of code: 4; Hints contain error(s)?: No error; Order type: Random order; Colour repeated?: No repetition
Code: 1425
The Codes in Tutorials (1) to (5) are all arranged in a fixed order. In these five tutorials, we concentrated on determining what digits are included in the Code without worrying about their positions. But in this tutorial, the digits of the Code are arranged in random order. We do not only need to determine what digits are included in the Code, but we also need to determind their positions, which makes the process of guessing more complicated. As a matter of fact, according to my experience, the process of Mastermind codebreaking may be divided into two phases. In Phase 1 we determine what digits are tp be included in the Code. In the Phase 2 we determine the position of these digits (Note 1). These two Phases are distinct but interrelated. They are distinct because the reasoning processes of the two Phases may be carried out independently. When we are undergoing one Phase, basically we do need to consider the problems of the other Phase. They are interrelated because the Phase 2 is dependent on the Phase 1. We may consider the Phase 2 as an "Input-Output" process. Its input is the group of digits determined in Phase 1, while its output is an ordering of the aforesaid digits. On the other hand, in some cases there will be "feedbacks" from Phase 2 to Phase 1. If in Phase 2 we have exhausted all possible orderings without finding an ordering that is consistent with all the given guess results, it means that the "input" provided by Phase 1 is not a correct guess. At this time Phase 2 can then convey this message as a "feedback" to Phase 1, so that Phase 1 can modify its "input". In the following discussion, the readers will see an example of such a "feedback".
Well, let's start our game now. As the readers have already learned the various codebreaking strategies for Phase 1 in Tutorials (1) to (5), in what follows I will only provide the guess results of Phase 1 without giving any explanation. The readers are asked to reason by themselves and see how I come up with the guess results. Moreover, to avoid confusion between the notations for digits and positions, I will use ABCD to denote the positions of the digits, i.e. A denotes the leftmost position, B the second position from the left, C the third position and D the rightmost position.
In the beginning there is no constraint for Phases 1 and 2 and we can input any 4 digits. Suppose we input 0123 and the hint we get is 1,1 (i.e. we have got 2 correct digits, among which one is in the correct position and the other is in the wrong position). At the end of the first Round, we get the following Trace Table (please note that this Trace Table is different from the Trace Tables in Tutorials (1) to (5), because the reasoning process in Phase 2 is very different from that in Phase 1. The meaning of the last column in the following Table will be explained below):
Round | Input | Hint | Digit(s) Assumed to be Correct | Position(s) Assumed to be Correct |
1 | 0123 | 1,1 | - | - |
Then we enter the 2nd Round. After going through Phase 1, we obtain 0145 as the input for Phase 2. Then we carry out the reasoning process of Phase 2, i.e. determing the positions of the above group of digits. How to determine? The principle is to make assumptions based on the given guess results and then verify if these assumptions are consistent with all the given guess results. Now let's start our reasoning. As in the 1st Round we got 1 digit in the correct position, we may assume that digit is the one in position A. That means we assume that the first digit of the Code is 0. As we have assumed that position A is correct, the remaining positions are all wrong positions, i.e. 1 must not be in position B. We may assume that it is in position C. Having determined the positions of 0 and 1, we may then determine the positions of 4 and 5 arbitrarily. Suppose we assume that 4 is in position B and 5 is in D. Thus we input 0415 as our guess for the 2nd Round. As a result, the hint we get is 2,1. At the end of the 2nd Round, our Trace Table becomes:
Round | Input | Hint | Digit(s) Assumed to be Correct | Position(s) Assumed to be Correct |
1 | 0123 | 1,1 | 01 | A |
2 | 0415 | 2,1 | 4 | - |
Then we enter the 3rd Round. After going through Phase 1, we obtain 0146 as the input for Phase 2. Then we carry out the reasoning process of Phase 2. As the digits assumed to be correct in the 1st Round (01) remain the same, we continue to assume that position A is the correct position in that Round. Next we consider the guess result of the 2nd Round. In the 2nd Round we have 2 correct positions, one of which must be A (because 0 is in position A in the 1st and 2nd Rounds). There is one more correct position. We may assume it to be B, i.e. the second digit of the Code is 4. So far we have determined the digits in positions A and B, and the digits in positions C and D are yet to be determined. Let's determine the digit in C first. As we assume that the position of 1 in the 2nd Round (C) is not the correct position, the digit in C cannot be 1 and so it must be 6. We can then determine the digit in D is 1. In this way we determine that the input guess for the 3rd Round is 0461. After inputting 0461, the hint we get is 1,1. Thus at the end of the 3rd Round, our Trace Table becomes:
Round | Input | Hint | Digit(s) Assumed to be Correct | Position(s) Assumed to be Correct |
1 | 0123 | 1,1 | 01 | A |
2 | 0415 | 2,1 | 4 | B |
3 | 0461 | 1,1 | - | - |
Then we enter the 4th Round. After going through Phase 1, we obtain 0245 as the input for Phase 2. Then we carry out the reasoning process of Phase 2. As the digits assumed to be correct in the 1st Round have been changed to 02, we have to make assumptions anew. First we assume that position A is the correct position in the 1st Round. Next we assume that position B is correct in the 2nd Round. We thus assume that the first two digits of the Code are 04. But this assumption contradicts the guess results of the 3rd Round (because in the 3rd Round we got only 1 digit in correct position), i.e. the above assumptions cannot pass the verification in the 3rd Round and so we must go back to modify our previous assumptions.
We first return to the 2nd Round and modify our assumption for that Round. Please note that we cannot change B to C, because in that Round the digit in position C is 1, but now 1 is not among the digits assumed to be correct. Thus we can only change B to D (in that Round, the digit in position D is 5, and 5 is among the digits assumed to be correct). So far we have determined the digits in positions A and D, while those in B and C are yet to be determined. Let's determind B first. Given the current assumptions and the guess result in the 2nd Round, the digit in B cannot be 4, and so it must be 2. Then we may determine that the digit in C is 4. Since the ordering 0245 can pass the verification in the 3rd Round, we finally conclude that the input guess for the 4th Round should be 0245. After inputting 0245, the hint we get is 1,2. Thus at the end of the 4th Round, our Trace Table becomes:
Round | Input | Hint | Digit(s) Assumed to be Correct | Position(s) Assumed to be Correct |
1 | 0123 | 1,1 | 02 | A |
2 | 0415 | 2,1 | 45 | D |
3 | 0461 | 1,1 | - | - |
4 | 0245 | 1,2 | - | - |
Then we enter the 5th Round. After going through Phase 1, we obtain 0345 as the input for Phase 2. Then we carry out the reasoning process of Phase 2. As the digits assumed to be correct in the 1st Round have been changed to 03, we have to make assumptions anew. First we assume that position A is correct in the 1st Round. Next we consider the guess result in the 2nd Round. According to the previous reasoning, we cannot assume B to be the correct position in the 2nd Round (as we have mentioned before, this assumption cannot pass the verification in the 3rd Round). Neither can we assume C to be correct (because 1 is not among the digits assumed to be correct). So we can only assume D to be correct. So far we have assumed that the first digit in the Code is 0 and the last digit is 5. But this assumption cannot pass the verification in the 4th Round (because in the 4th Round we only got 1 digit in correct position). So we must go back to modify our previous assumptions.
We first return to the 2nd Round. As the position assumed to be correct in that Round (D) is already the final position, no modification can be made. So we have to return to the 1st Round and modify the assumptions made in that Round. Please note that we cannot change A to B or D because in the 1st Round, the digits 1 and 2 in positions B and C are not among the digits assumed to be correct. So we can only change A to D. Next we consider the guess result of the 2nd Round again. As there are 2 correct positions in the 2nd Round, we must determine these 2 positions. These 2 positions can neither be D (because in the 2nd Round the digit in D is 5, but now we assume that the digit in D is 3), nor C (because in the 2nd Round the digit in C is 1, but 1 is not among the digits assumed to be correct), nor A (because in the 2nd Round the digit in A is 0, but according to our assumption for the 1st Round, the digit in A cannot be 0). Thus there is no way we can determine the 2 correct positions in that Round. This shows that our previous assumptions are incorrect. We cannot but return to the 1st Round to modify the assumption made for Round. But the current assumption for that Round (D) is already the final position, which is unchangeable. Now that we have exhausted all possible orderings without finding an ordering which is consistent with all the given guess results, this shows that the "input" provided by Phase 1 -
0345 is not a correct guess. At this time Phase 2 conveys this passage as a "feedback" to Phase 1 so that Phase 1 can modify its "input". The following Trace Table shows the situation immediately before Phase 2 gives the "feedback" (the ? mark in the Table shows that there is no way we can determine the correct position for the 2nd Round).
Round | Input | Hint | Digit(s) Assumed to be Correct | Position(s) Assumed to be Correct |
1 | 0123 | 1,1 | 03 | D |
2 | 0415 | 2,1 | 45 | ? |
3 | 0461 | 1,1 | - | - |
4 | 0245 | 1,2 | - | - |
After we make modifications in Phase 1, we obtain 1245 as the new input. Then we carry out the reasoning process of Phase 2. As the digits assumed to be correct in the 1st Round have been changed to 12, we have to make assumptions anew. Now we cannot assume that the correct position in the 1st Round is A, because 0 is not among the digits assumed to be correct. So we assume that B is the correct position in the 1st Round. Next we consider the guess result in the 2nd Round. As there are 2 correct positions in the 2nd Round, we must determine these 2 positions, which can neither be A (because 0 is not among the digits assumed to be correct), nor B (because in the 2nd Round the digit in B is 4, but we now assume that the digit in B is 1), nor C (because in the 2nd Round the digit in C is 1, but we now assume that 1 is in B). Thus there is no way we can determine the 2 correct positions for the 2nd Round. This shows that our previous assumption is incorrect and so we must return to the 1st Round and modify the assumption made for that Round.
After changing the assumption for the 1st Round to C, we consider the guess result in the 2nd Round again. As there are 2 correct positions in the 2nd Round, we must determine these 2 positions, which can neither be A (because 0 is not among the digits assumed to be correct), nor C (because the digit in C is 1, but we now assume that the digit in C is 2), so they can only be B and D. Now we determine that the second digit of the Code is 4, the third digit is 2 and the fourth digit is 5. Thus the first digit of the Code must be 1. As the ordering 1425 can pass the verification in the 3rd and 4th Rounds, we finally conclude that our guess for the 5th Round should be 1425. After inputting 1425, we successfully break the Code. At the end of the 5th Round, our Trace Table becomes:
Round | Input | Hint | Digit(s) Assumed to be Correct | Position(s) Assumed to be Correct |
1 | 0123 | 1,1 | 12 | C |
2 | 0415 | 2,1 | 45 | B,D |
3 | 0461 | 1,1 | - | - |
4 | 0245 | 1,2 | - | - |
5 | 1425 | WIN | - | - |
Note 1: In certain cases, we only need to go through one Phase. For example, when we are playing a Fixed order game, there is no need to go through Phase 2. Another case is when we are playing a Random order game and we have come up to a stage when the digits included in the Code have been completely determined (but their positions haven't been determined yet), then we only need to concentrate on Phase 2 and no longer need to go through the reasoning process of Phase 1.
Go to 3-Way A.I. Mastermind Website.