Hello!

This is the Qualiteg Research Team!

Today we will explore information theory—a concept that is also extremely important in AI—using "Hit & Blow," a game included in the popular Nintendo Switch title "Clubhouse Games: 51 Worldwide Classics," as our subject!

Introduction

"Hit & Blow" (known internationally as "Mastermind") is a classic puzzle game that has long been enjoyed as a way to sharpen logical thinking.

While the game looks simple at first glance, mastering it calls for a deeply logical approach.

In this article, we take a closer look at how the mathematical framework of information theory can be used to analyze the fundamental nature of this game.

We will also touch on how information theory is applied in modern artificial intelligence (AI) technology.

Rules of Hit & Blow

Hit & Blow is a game in which you try to guess a secret combination of colors or numbers set by your opponent. In Japan it is popular mainly as a number-guessing game, but in this article we focus on the color-based version (Mastermind).

In the version of Hit & Blow playable in "Clubhouse Games: 51 Worldwide Classics" on Nintendo Switch, you choose 4 out of 6 colors and arrange them in order, and the player must find the correct answer within a maximum of 8 turns.

The basic rules of the game are as follows.

● There are balls in 6 colors
(Strictly speaking they are pegs, but "balls" is easier to say, so that is what we will call them ^_^)

● The answer is 4 balls arranged in a specific order

The codemaker (in this case, the computer) picks 4 of the 6 balls, arranges them in a specific order, and fixes that as the answer in advance — for example, like this.

● The challenger's goal is to guess the combination of colors and their order.

● When the challenger presents a combination of colors, the codemaker returns feedback in the following form

• "Hit": both the color and the position are correct
• "Blow": the color is correct but the position is different

In other words, the challenger's guess is compared against the answer, and the feedback tells you how many balls were hits and how many were blows.

Relying on this feedback alone, the challenger aims to reach the correct answer within a limited number of tries.

There is usually a limit of about 10 tries, but with an efficient strategy you can find the answer in roughly 5 to 7 tries.

The appeal of this game lies in the process of logically narrowing down the possibilities from limited information. The key is a strategy that makes the most of the feedback from each try and closes in on the answer efficiently.

The game also makes an accessible subject for mathematical study, and countless strategies have been proposed over the years, some of them published as academic papers.

So, let's give it a try.

An Example Strategy for Hit & Blow

Many strategies exist for Hit & Blow, but here let's walk through an actual game we played at home, using the 6-color, 4-peg version with an 8-turn limit available on Nintendo Switch.

◆ Turn 1: The Guess

At the start we know nothing at all about the answer, so let's simply place two balls each of two colors. Our opening move looked like this

◆ Turn 1: Feedback

We then received the following feedback.

This means the following.

There was one orange ●, which means one hit
There was one white ●, which means one blow

That is what the indicator tells us. A hit means both the color and the position are correct, while a blow means only the color is correct. So from my Turn 1 guess, we learned that one ball is in the correct position and another has the correct color.

Both ● and ● have a correct color, and one of the two is in the correct position. That lets us break things down into the following cases.

【Assuming ● is the hit】 one of the top two positions is ●, and since the other ball ● also has a correct color, the top half should follow one of the patterns below

【Assuming ● is the hit】 one of the bottom two positions is ●, and since the other ball ● also has a correct color, the bottom half should follow one of the patterns below

So we actually learned quite a lot

◆ Turn 2: The Guess

Now, on to Turn 2.

Which balls should we place?

We now know a fair amount about ● and ●, so this time let's try a different pair of colors.

Again, let's place two of each.

So this time, choosing from the balls we have not used yet,
let's place ● and ● as shown below.

◆ Turn 2: Feedback

We then received the following feedback.Hits: 0, Blows: 1That was the result.

Here is what the game board looks like.

So, what can we learn from this result?

Either ● or ● is one of the correct colors

— that much is now clear.

Furthermore, it follows that among the remaining balls not yet chosen,
either ● or ● is one of the correct colors

as well.

◆ Turn 3: The Guess

Now for Turn 3.

It's about time we set a strategic goal for each turn.

The goal for Turn 3 is to refine the information gained in Turns 1 and 2. Specifically:

【Goals for Turn 3】

・Confirm whether or not the hit in Turn 1 was ●

and one more:
・Confirm whether or not the blow in Turn 2 was ●

To achieve these goals, the following combination seems like a good choice.

The two ● at the top let us confirm whether or not the Turn 1 hit was ●.

The two ● at the bottom let us confirm whether or not ● was the blow in Turn 2.

Thinking about the possible feedback here, only the following four patterns exist — and whichever of the four we get, we can achieve this turn's goals

Pattern 1
1 hit, 1 blow → ● was the hit, ● was the blow

Pattern 2
1 hit, 0 blows → ● was the hit, ● was the blow

Pattern 3
0 hits, 1 blow → ● was the hit, ● was the blow

Pattern 4
0 hits, 2 blows → ● was the hit, ● was the blow

◆ Turn 3: Feedback

With our thinking sorted out, we made the guess — and here is the feedback we received

The result was Pattern 2: 1 hit, 0 blows

In other words, this told us that

● was the hit, and ● was the blow

— both now confirmed.

First,
knowing that ● was the hit,

we were able to narrow the top two positions of the sequence down to

as shown above.

Also, since ● was the blow, it is now certain that ● is a dud (not in the answer).

Furthermore, from the Turn 2 result we know that ● is not in the top half, so ● must be somewhere in the bottom half.

◆ Turn 4: The Guess

After three turns, quite a lot has come into view.

Let's press our advantage in Turn 4.

First, let's set this turn's strategic goals.

Goal 1: Pin down the order of the top half. We want to settle the following.

Goal 2: Pin down the position of ●. We want to determine which of the following it is.

Goal 3: Determine the color of the last remaining ball — is it ● or ●?

So, what is the best move to achieve all of these goals?

It is probably the following.

First, the top half addresses Goal 1: the order of ● and ●.

In the bottom half, we want to determine the one remaining color.
The reason we deliberately mix in the known dud ● here is that if ● turns out to be a correct ball, we can also pin down the position of ●. And once the position of ● is known, the position of ● follows automatically.
With this arrangement, we get that lucky break with probability 1/2.

You might think we could simply have played the following from the start — but then, if we got 2 hits, we could not tell whether the top half or the bottom half was correct, so it may not be the sharpest line of play

◆ Turn 4: Feedback

So, let's see the result.

The Turn 4 feedback came out like this

2 hits, 1 blow

Let's summarize what we learned from this result!

① The order of the top half is settled
From the top: ● then ●

② Since ● was a blow, all four colors are settled: ●●●●.

③ Since ● was a blow, we know that ● is third from the top.

④ From ③, ● must be at the very bottom

And with that, the positions of all the balls are known!

◆ Victory on Turn 5

So we concluded that the answer is

and on Turn 5 we played exactly that —

There it is! 4 hits — the complete correct answer!

By analyzing logically, we reached the answer in 5 turns. Our aim was to rely on logic rather than luck as much as possible when choosing each best move — what do you think?

With this approach, allowing for some variation in the initial ball choices, you can reach the answer in about 5 turns. That leaves plenty of headroom within the 8-turn limit of Hit & Blow on Nintendo Switch.

But is 5 turns really a good number? Could there be an approach that solves the game in 3 turns?

From here, let's look at information theory, which can clear up exactly these kinds of questions.

By applying information theory, we can derive the theoretical minimum number of turns!

What Is Information Theory?

Information theory is a mathematical framework for quantifying and transmitting information, founded by Claude Shannon in the 1940s.

Originally developed to improve the efficiency of telecommunications, it is now applied across a wide range of fields including computer science, cryptography, statistics, physics, and AI.

The central concept of information theory is "information content".

Information content is defined as the degree to which uncertainty is reduced, and it is usually measured in bits.

For example, identifying the outcome of a fair coin flip requires 1 bit of information, because singling out one of the two possibilities — heads or tails — requires log₂(2) = 1 bit.

Similarly, identifying the face of a 6-sided die requires about 2.58 bits (log₂(6)). In general, if there are N options, the amount of information needed to single out one of them is log₂(N) bits.

Another important concept in information theory is "entropy".

Entropy is a measure of uncertainty, or the disorder of information, and it is computed from the probabilities of each possible state.The higher a system's entropy, the more uncertainty it contains — and therefore the more information it holds.

The concept of "mutual information" is also important: it measures how much knowing one variable reduces the uncertainty of another.

In Hit & Blow, for example, the ideal strategy is one that maximizes the mutual information gained from each turn's feedback.

In short, information theory quantifies uncertainty and optimizes how efficiently information is conveyed — providing the mathematical foundation for both.

Estimating the Optimal Number of Turns in Hit & Blow with Information Theory

Analyzing Hit & Blow from the standpoint of information theory lets us calculate the theoretical minimum number of turns.

Two quantities are key to this analysis: the "amount of information required" and the "maximum information gained per turn."

First, let's consider all the possibilities in the game.

In the Hit & Blow found in "Clubhouse Games: 51 Worldwide Classics," where you choose 4 balls out of 6 colors and arrange them in order,

the total number of possible combinations is 6P4 (the permutation of 6 things taken 4 at a time) — that is, the number of ways to choose 4 out of 6 distinct items where order matters, so

6P4 = 6! ÷ (6-4)! = 6! ÷ 2!

First compute the factorials: 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720, 2! = 2 × 1 = 2

Therefore: 6P4 = 720 ÷ 2 = 360

The answer is 360 possibilities.

Calculating the Required Information (Entropy)

The amount of information needed to pinpoint the single correct answer among these is as follows.

Expressed as entropy in information theory, the information required to uniquely identify the answer among 360 possibilities is

log₂(360) ≈ 8.94 bits

.

Next, consider the amount of information that can be gained each turn.

In 4-peg Hit & Blow, each turn's feedback is a combination of hits and blows.

In the Clubhouse Games version of Hit & Blow, colors cannot repeat, so if we group the hit/blow patterns by the total of hits and blows, writing them as (hits, blows), we get

• When the total is 2: (2,0), (1,1), (0,2) [3 patterns]
• When the total is 3: (3,0), (2,1), (1,2), (0,3) [4 patterns]
• When the total is 4: (4,0), (2,2), (1,3), (0,4) [4 patterns]

for a total of 11 patterns.

In information theory, when an event splits into n equally likely outcomes, its information content is

log2(n) bits, so the maximum amount of information obtainable in one turn is log₂(11) ≈ 3.46 bits.

Computing the theoretical minimum number of turns: required information ÷ maximum information per turn = 8.94 ÷ 3.46 ≈ 2.58. Rounding up, under ideal conditions the game could be solved in 3 turns.

In actual play, however, more turns are needed than the theoretical value, for the following reasons

1. You cannot always gain the maximum amount of information on every try. Especially in the early turns, the lack of information makes optimal choices difficult
2. There are limits to the strategies a human can realistically execute — human players face cognitive constraints (exhaustively computing every possibility the way a computer does is a tall order for the human brain)
3. Luck also plays a non-negligible role
   A first guess may happen to yield a great deal of information, or almost none at all

Taking these factors into account, realistic optimal play works out to

• On average: around 5 turns
• Worst case: 6-7 turns

which seems like a reasonable estimate.

So, as for the strategy I came up with — let's just say it waswell, not bad at all. ^o^

As a further application of the information-theoretic approach, there is a strategy of making the "choice that maximizes information gain" on every turn.

This means choosing, on each turn, the guess that splits the set of remaining possibilities as evenly as possible, thereby maximizing the information gained. With a computer program executing this optimal strategy, it is possible to solve the game in an average number of turns close to the theoretical value.

Information Theory Is a Vital Concept in AI, Too

Information theory is one of the foundational concepts of modern artificial intelligence.

We make frequent use of it in our own research and development at Qualiteg.

Its range of applications is vast, spanning machine learning algorithm design, neural network training methods, and even natural language processing.

To begin with, the fundamental goal of machine learning — extracting patterns from data — is at heart an information theory problem.

The learning process can be described as reducing the uncertainty (entropy) in data and extracting useful information.

In decision tree algorithms, for example, at each split the feature chosen is the one that maximizes information gain (the reduction in information entropy).

In deep learning, the widely used loss function "cross-entropy" comes directly from information theory. It is a measure of the difference between the model's predicted probability distribution and the true distribution.

(Cross-entropy is a very important concept in machine learning, and it is explained in detail in https://blog.qualiteg.com/cross-entropy-01/ — please have a look.)

The "information bottleneck" theory used to prevent overfitting is another application of information theory. It is an approach that builds more generalizable models by extracting only the relevant information from the input data and discarding noise and irrelevant information.

In natural language processing, "perplexity" — a metric for evaluating language models — is based on conditional entropy. The "TF-IDF" score for measuring word importance is likewise rooted in information-theoretic thinking.

In reinforcement learning, there is a technique called "maximum entropy reinforcement learning," which controls entropy to balance efficiency toward the goal against diversity of exploration in the agent's action selection.

In the world of large language models (LLMs), the "temperature" parameter that controls the diversity of generated text is also related to the entropy of a probability distribution. Raising the temperature flattens the distribution (higher entropy), producing more varied output; lowering it sharpens the distribution (lower entropy), producing more deterministic output.

As you can see, information theory runs deep through many aspects of AI technology. Quantifying uncertainty, representing and processing information efficiently, designing optimal decision procedures — the concepts of information theory remain an essential foundation for AI research!

Conclusion

In this article, using the classic puzzle game Hit & Blow (Mastermind) as our subject, we introduced an example of a logical strategy and explored how information theory can be applied to measure the fundamental nature of such games.

Our strategy can be seen as a kind of "divide and conquer": split the whole problem into subproblems (Divide), solve each one individually (Conquer), and combine them into the overall solution — reaching the answer in as few as 5 turns. If you want to dig deeper into this area, Knuth's algorithm is a famous starting point and well worth looking up.

In the second half, we reinterpreted all of this through the lens of information theory.

Concepts such as information content and entropy form the mathematical foundation for quantifying uncertainty and optimizing information transmission, and they are widely applied in modern AI — playing key roles in everything from machine learning algorithm design to deep learning training methods and natural language processing.

Applying information theory to the 6-color, 4-peg, no-repetition version of Hit & Blow, the theoretical optimum suggests the game could be solved in 3 turns, but in practice various constraints make 4-6 turns the realistic estimate.

We hope that working through the strategy of a seemingly simple game has made the profound mathematical framework of information theory feel a little more approachable.

The ideas of information theory are universal — applicable not only to game strategy but also to everyday decision-making and problem-solving. The perspective of quantifying uncertainty and gathering and judging information optimally is useful in many situations.

Thank you for reading to the end!

See you next time!