Predict Pattern & Top Down Approach

Suppose you are in an exam and you have to answer a set of True or False questions. Also, suppose you do not know the correct answers to any of the questions (because they seem nonsense to you). In this situation, all you can do is random guessing and normally your resulted score is around 50% by chance. Let’s say the teacher who marks your work gives you many more trials to answer the same set of questions. Also, he/she shows you your total score at the end of each trial. What will you do to reach the perfect score with a minimal number of trials?

One obvious strategy is a brute-force strategy. In this strategy, you randomly change all your answers in each trial until you get the full score by chance (Figure 1). With this strategy, if the number of questions is 10, your chance of guessing all the answers correctly by brute-force is 1 in 1024 trials. Your winning chances decrease exponentially as the number of questions increases.

The alternative strategy is to change only one question in each trial. If your total score increases, it means your change was correct. If not, it means your change was incorrect. With this simple strategy, you can guarantee to reach the perfect score in just 10 trials (if you have 10 questions). The number of trials required to reach the perfect score using this simple strategy is massively less than the brute-force strategy.

To have more insight into these kinds of problems, we performed some simulations and we figured out that it is possible to improve the chance of ‘reaching the full score in fewer trials’ even further if we try to maximize the information gain. This is possible by changing more than one question at a time. Maximizing information gain is a big topic and is detailed through “Shannon’s Information Theory”. In this article, we will not go into the theoretical details.

For educational and entertainment purposes, we turned part of our simulations to an Android game which we called “MineClear”. It is now available on Google’s Play Store. We also made a similar online version but with a different interface (Links at the end). Below are some screenshots of MineClear.
*Edit: MinClear is now discontinued but we made a similar online game where you need to find the hidden True and False pattern, just like the given example above. Here is the link to the online game.

In MineClear, you need to figure out all the ‘Mine’ and ‘Clear’ squares by flagging or unflagging them correctly. To know if you have made a correct guess you must peek at your score, which shows your current score. What makes the game challenging is that you can only peek at your score for a limited number of trials. The simple strategy described above can help you to pass the first level. However, in the more challenging levels, you have fewer trials than squares, therefore, you cannot figure out all the answers using that strategy because you will run out of your limited number of allowed peeks.

Another possible strategy is to change two squares at once, then peek at your score. For example, say you have flagged two squares (or changed two False choices to True). As a result, two possible changes might occur to your total score:

1. Your total score increases or decreases by a factor of two (+/-2). This means the changes you made were either “both correct” or “both incorrect”. This situation happens 50% of the time (Figure-3, situation-2).
2. Your total score does not change. This means one of the changes was correct, but the other was not. In this case, you need another trial to find out which change was the correct one. This happens 50% of the time (Figure-3, situation-1).

As you can see, following the above strategy, half of the time you need one trial to correctly guess about two squares, and half of the time you need two trials to correctly guess about both squares. Hence, this strategy can potentially increase your chance of winning by about 25% of our simple strategy. And this will be enough to pass the second level of MineClear most of the time.

If you want to maximize the information gain even further, you have to change even more squares. For example, changing 4 squares at once gives you 16 guessing possibilities and 3 distinct situations (Figure 3). In the best-case scenario, you will be able to guess about 4 squares with only 1 trial and this happens 2 out of 16 times (situation-3 in Figure 4). And in the worst-case scenario, you might need up to 4 trials to guess about all the 4 squares correctly (situation-1 in Figure 4). Changing 4 squares at once can increase your chance of winning in the later levels of MineClear.

Please note that no strategy can guarantee your win all the time if the number of the trials is fewer than the number of the squares. Therefore, you need some luck on your side to win, but having a good strategy maximizes your chance of winning. Without a good strategy, you are out of luck too.

We will not spoil all the possible strategies and will leave that to you to find ingenious ways to solve the problem, but the take-home message is: To maximize the information gain, you need to have the bird’s eye view of the entire grid at first then come down to the specifics. This is analogous to the top-down approach (Figure 5). With a top-down approach, you can visualize the problem as an inverted tree in which to figure out the values of the nodes at the bottom of your tree, first, you need to figure out the nodes at the top of the hierarchy. Changing a top node changes the nodes directly below it, but changing a node at the bottom will not change the nodes above it.

We think the game we presented here is a simplified simulation of many other real-life situations where you have to reach a goal with a minimal number of trials and errors. There are so many situations where you cannot get the specific feedback for the individual parts of your actions, instead, you get the feedback for your entire work as a whole. For instance, you might get rejected for a job interview without specific reasons. This rejection represents your total score. In this case, it is your job to find out which parts of you were responsible for the rejection and needs to be improved just like the game presented here.

In fact, in the evolutionary process, natural selection and the survival of the fittest is also a sort of this kind of feedback where each organism is assessed as a whole. This is why the mutation rate is generally slow. Because mutations happen randomly, widespread changes in the DNA structure of the next generations are usually fatal and can hardly improve the species because negative mutations cancel out the positive ones. On the other hand, small and incremental changes in DNA are not fatal. And with natural selection, the process of climbing the mount improbable or even reaching the global maxima is possible (similar to our first simple strategy). Minimizing the number of trials to reach the correct answer is probably the most valuable thing for our survival. Our DNAs cannot use the sophisticated top-down strategies we described here, but our brains can.

Edit: MineClear is no longer available on the Play store, instead you can play it online here under the name: Predict Hidden Pattern. Also, You can watch our new video about this topic and it’s relation to consciousness here: https://youtu.be/5qqxGwlUilU