この記事は朝活部 Advent Calendar 20248日目の記事です。
初めて一般公開する記事を書くので、拙いところもありますが暖かい目で最後まで読んでいただけると嬉しいです。
また、数学的な知識及びプログラミングに関する知識は皆無なので、間違い等ありましたら指摘していただけたら幸いです。
はじめに
HIT AND BLOWとは何か？
各プレイヤーがはじめに、0から9までの数字を重複させずに組み合わせた4桁の秘密の数字を決める。
ゲームは交互に進行し、プレイヤーは相手の秘密の数字を予想していきます。
予想した数字を相手に伝えると、相手はその予想に対してヒット及びブローの個数を返す。
ヒットとは、予想した数字のうち、数字とその数字の位置が一致している場合の数をさし、ブローは数字は一致しているが、位置が異なる場合の数を指す。
先にヒット数が4となるような数字を予想したプレイヤーが勝者となる。
もちろん、4桁の数字でなく、3桁に減らしたり、5桁に増やしてもプレイ可能である。
参考にしたサイト: ヒットアンドブローゲーム
理論値を考えてみる
今回は、4桁で対戦する場合について考えていきます。
多分絶対に最初にすることではないが、理論値を考えてみます。
理論値についての理解があまりなかったので調べてみると、
ゲームにおける理論値とは、主に上手くプレーができれば獲得できるスコアの最高値を意味します
引用元: ゲームにおける「理論値」とは？意味や使い方を解説！
すなわち、ヒットアンドブローにおいて理論値を出すには、最短で1ターン目で勝てるため、最初に正解の数字を言えば良いことがわかった。
4桁の場合、0~9までの数字の順列なので、
_{10}P_4 = \frac{10!}{(10-4)!} = 5040
5040個の数字の集合から1つを選んで当てれば良いのだが、相手の心でも読めていない限り不可能であり、そのようなアルゴリズムを書くことも多分不可能だと思う。
真面目に考えてみる
先ほど述べたように、4桁のヒットアンドブローにおいて、ありうる4桁の数字は高々5040個しかありません。
全ての数字を片っ端から言っていけば必ず5040回以内には相手の数字を当てることができます。
ただもちろん、それではヒット数及びブロー数を聞く必要がありません。
ヒット数とブロー数からの絞り込み
このゲームで大事になってくる、ヒット数とブロー数から残りの数を求めてみます。
例えば、最初に"0123"と予想して、ヒット数及びブロー数が0だった場合、0~3いずれかの数字が1つでも入っているものが候補から消されます。よって、残りの4~9までの数字から4つを選んだ数が候補として残ります。
すなわち、6個の数字を4つ並べた時の順列なので、
_6P_4 = \frac{6!}{(6-4)!} = 360
ヒット数及びブロー数が0だった場合、5040個あった候補が一気に360個まで減ることがわかりました。
ブロー数が1だった場合、0~3までの数字が必ず1つだけ入っているものが候補に残ります。
0~3までの数字を1つ選び、4~9までの数字を3つ選んだ時の順列となるので、
{}_6P_3 \times 4 \times 4 = 1920
ただし、ヒット数が0のため、0が1番目に来る数字、1が2番目に来る数字、…は省かれる。
よって、この数字に3/4をかけたもの、すなわち1440個が残りの候補数となります。
3/4の説明
上記の候補のうち、
0~3が先頭に来るのは全体の$\frac{1}{4}$、0が先頭に来るのはそのまた$\frac{1}{4}$で$\frac{1}{16}$
2番目に来るのは全体の$\frac{1}{4}$、1が2番目に来るのは$\frac{1}{16}$
3番目に来るのは…とやっていくと、
$1 - \frac{1}{16} \times 4= \frac{3}{4}$となります。
残りのヒット数及びブロー数でも同じように考えることができます。
予想を重ねての絞り込み
上記のように候補を絞り込んでいくと、i回目の予想でのヒット数とブロー数から絞り込んだ数字の候補の集合を$A_i$とすると、n回質問した時点での残りの候補は$\bigcap_{i=1}^{n} A_i$となります。
残りの候補が1つになるまで、1つ数字を候補から選んで予想していく方針で今回はプログラムを書いてみます。
追記: 集合の積の表記が間違っていたため、直しました。(2024/12/08)
実装方法
予想してヒット数及びブロー数を受け取ったあと、残りを絞り込む方法の実装を考えると、上記の計算のようにヒット数及びブロー数に応じて処理を変えるのは筆者の実装力的には厳しい。
そこで、残りの候補からヒット数及びブロー数が同じものを列挙していく方法を考えていきます。
例えば、答えが"4567"の時に"0123"と予想するとヒット数及びブロー数は0となります。
"0123"と予想してヒット数及びブロー数が0となるものを候補列挙し、それを新たな候補とする方針でいきます。
結局、先ほど計算で求めた集合は「ヒット数及びブロー数が0となるもの」の集合であり、今説明したものと変わらないことがわかりました。
このような方針なら、実装できそうなのでやってみます。
プログラムを書いてみる。
今回は、筆者の都合上、C言語を使って実装してみます。
上記で書いたことをもとに、実装してみると次のようになりました。
#include <stdio.h>
// 最初の候補となる数字の列挙
void initialCount(int candidates[], int *candidates_count) {
for (int num = 0; num < 10000; num++) {
int number = num;
int flag = 1;
int count[10] = {0}; // 各数字の登場回数
for (int i = 0; i < 4; i++) {
int digit = number % 10;
if (count[digit] > 0) {
flag = 0;
break;
}
count[digit]++;
number /= 10;
}
if (flag) {
candidates[*candidates_count] = num;
(*candidates_count)++;
}
}
}
// 予想した数字と残りの候補の任意の数字のヒット数とブロー数が一致するか確認する関数
int check(int candidate, int guess, const int hit_count, const int blow_count) {
int hits = 0, blows = 0; // 予想した数字とのヒット及びブロー数
// 簡単のため、各桁の数字を配列に入れる。
int cand[4], gss[4];
for (int i = 3; i >= 0; i--) {
gss[i] = guess % 10;
cand[i] = candidate % 10;
guess /= 10;
candidate /= 10;
}
// ヒット数を数える
for (int i = 0; i < 4; i++) {
if (gss[i] == cand[i])
hits++;
}
// ブロー数を数える
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (i == j)
continue;
if (gss[i] == cand[j])
blows++;
}
}
if((hits == hit_count) && (blows == blow_count))
return 1;
else
return 0;
}
// ヒット数とブロー数から候補を絞り込む関数
void narrowdown(int candidates[], int *candidates_count, const int guess,
const int hit_count, const int blow_count) {
int narrowed_candidates[10000]; // ヒット数とブロー数から計算した残りの候補を入れる
int narrowed_candidates_count = 0; // 上の個数
for (int i = 0; i < *candidates_count; i++) {
if (check(candidates[i], guess, hit_count, blow_count) == 1) { // ヒット数とブロー数が一致しているか
// していたら残りの候補に入れる
narrowed_candidates[narrowed_candidates_count] = candidates[i];
narrowed_candidates_count++;
}
}
for (int i = 0; i < narrowed_candidates_count; i++) {
candidates[i] = narrowed_candidates[i];
}
*candidates_count = narrowed_candidates_count;
}
int main() {
int candidates[10000]; // 残りの候補
int candidates_count = 0; // 残りの候補数
initialCount(candidates, &candidates_count);
int guess = candidates[0]; // 今回は候補の中から1番小さい数字を選び、予想とする
int hit_count = 0, blow_count = 0;
int turns = 0;
while (hit_count != 4) {
turns++;
// printf("候補数: %d\n", candidates_count);
printf("Turn:%d\nGuess: %04d\n", turns, guess); // 予想した数字を出力
printf("Enter hit counts! = ");
scanf("%d", &hit_count); // ヒット数を受け取る
printf("Enter blow counts! = ");
scanf("%d", &blow_count); // ブロー数を受け取る
printf("\n");
narrowdown(candidates, &candidates_count, guess, hit_count, blow_count);
guess = candidates[0]; // 候補の中から1番小さい数字を選び、予想とする
}
printf("needed turns: %d\n", turns);
return 0;
}
動かしてみる
筆者の数字を"5469"としてやってみます。
Turn:1
Guess: 0123
Enter hit counts! = 0
Enter blow counts! = 0
Turn:2
Guess: 4567
Enter hit counts! = 1
Enter blow counts! = 2
Turn:3
Guess: 4658
Enter hit counts! = 0
Enter blow counts! = 3
Turn:4
Guess: 5469
Enter hit counts! = 4
Enter blow counts! = 0
needed turns: 4
なんと、4ターンで当てることができました！
候補数を出力してみます。
候補数: 5040
Turn:1
Guess: 0123
Enter hit counts! = 0
Enter blow counts! = 0
候補数: 360
Turn:2
Guess: 4567
Enter hit counts! = 1
Enter blow counts! = 2
候補数: 72
Turn:3
Guess: 4658
Enter hit counts! = 0
Enter blow counts! = 3
候補数: 18
Turn:4
Guess: 5469
Enter hit counts! = 4
Enter blow counts! = 0
needed turns: 4
最初のターンではヒット数及びブロー数が0であるため、計算通り候補数を5040から360に絞り込めてますね。
最後のターンではまだ4つ候補が残っていましたが、当てることができました。
何回か試すスクリプトを書き、必要なターン数の平均を取ってみます。
10000回試した結果:
Average turns: 5.58
1 turns: 1
2 turns: 21
3 turns: 210
4 turns: 1160
5 turns: 3228
6 turns: 3589
7 turns: 1497
8 turns: 283
9 turns: 11
10 turns: 0
(ランダムに4桁の数字を生成し、それを当てる数字として検証)
追記: たかだか5040通りしかないため、全て試せば良かったのでは…？
数字の生成方法
今回はpythonでスクリプトを書いたので、pythonのmoduleであるrandomを使用して生成しました。import random
def generate_num():
digits = random.sample(range(10), 4)
num = 0
for d in digits:
num = num * 10 + d
return num
平均して5,6回で当てることができてますね。
9回かかった時の実行logを1つ見てみます。
候補数: 5040
Turn:1
Guess: 0123
Enter hit counts! = 0
Enter blow counts! = 2
候補数: 1260
Turn:2
Guess: 1045
Enter hit counts! = 0
Enter blow counts! = 2
候補数: 288
Turn:3
Guess: 2354
Enter hit counts! = 1
Enter blow counts! = 1
候補数: 96
Turn:4
Guess: 2406
Enter hit counts! = 1
Enter blow counts! = 2
候補数: 5
Turn:5
Guess: 2560
Enter hit counts! = 0
Enter blow counts! = 2
候補数: 4
Turn:6
Guess: 3604
Enter hit counts! = 2
Enter blow counts! = 0
候補数: 3
Turn:7
Guess: 7204
Enter hit counts! = 3
Enter blow counts! = 0
候補数: 2
Turn:8
Guess: 8204
Enter hit counts! = 3
Enter blow counts! = 0
候補数: 1
Turn:9
Guess: 9204
Enter hit counts! = 4
Enter blow counts! = 0
候補数が5になってからは、残りの候補を総当たりをしているようです。
最初の方のターンであまり絞りこめてないからでしょうか。
今回の記事はここまでにしてみようと思います。何かまた案ができたら、実装してみることとします。
おわりに
ここまで読んでいただき、ありがとうございました！
間違い等ありましたら指摘していただけたら幸いです。
また機会があったら、さらなる改良をしてみたいと思いました。
ぼんやりとしか考えていないのですが、ヒット数及びブロー数が0の時に、360通りまで候補数が減るので、それをうまく使えないのか模索しています。今回の9回かかってしまったケースで、2ターン目に残りの候補から選ぶのではなく、一気に絞れるような数字を選んでみたりできたらいいなと思っています。