# Predict Pattern & Top Down Approach

Home / Blog / 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.