この記事は 朝活部 Advent Calender 13日目の記事になります。
前回に引き続き、初学者の書く記事なので、お手柔らかにお願いします。
前回記事を読んでいない方はこちらに目を通していただけるとありがたいです！
はじめに
友達が対戦してくれるそうなので、それを超えていくようなプログラムを書きたいです。
解説記事というよりは、筆者の試行錯誤記みたいなものになっております。あまり記事を書くのは得意ではないので、暖かい目で見ていただけると幸いです。
課題点を考える
前回、当てるのに9回かかったケースを見てみます。
(コードは前回と全く同じものを使用)
使用したコード
#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;
}
0123~9876までの全ての有効な手数を試した結果、5040通りのうち、5つだけ当てるのに9回かかってしまっています。
Average turns: 5.56
1 turns: 1
2 turns: 13
3 turns: 108
4 turns: 596
5 turns: 1668
6 turns: 1768
7 turns: 752
8 turns: 129
9 turns: 5
10 turns: 0
今回は、この手数のバラつきをなるべく無くし、可能であれば手数を減らせるような方法を考えていきたいと思います。
改善1
コードを見てみると、残りの候補の中から1つを選んでいます。
guess = candidates[0]; // 候補の中から1番小さい数字を選び、予想とする
これだと、特定のケースでのみ手数が増えてしまいます。
とりあえず、残りの候補の中からランダムに選び、偏りを無くしてみます。
srand((unsigned int)time(NULL)); // randの初期化
guess = candidates[rand()%candidates_count];
// 候補の中からランダムに選ぶ
Average turns: 5.45
1 turns: 1 (1)
2 turns: 11 (13)
3 turns: 133 (108)
4 turns: 603 (596)
5 turns: 1861 (1668)
6 turns: 1724 (1768)
7 turns: 648 (752)
8 turns: 59 (129)
9 turns: 0 (5)
10 turns: 0 (0)
9回のケースがなくなり、8回のケースも半分以上減りました。
平均も0.11下がっていますね。
ランダムにすることによって、特定のケースで探索が局所的になる可能性が低下します。
ですが、あくまで可能性が低下しただけであって、完全に取り除けたわけではありません。
全てのケースを5回、試したところで、9手かかった数字が出てきてしまいました。
改善2-1
改善1では、次選ぶ数字をランダムに選んでみましたが、今度は戦略的に選んでみます。
残りの候補から1つを選び、各ヒット数及びブロー数の組み合わせの時にどれだけ候補が減るかを計算してその合計を取ります。その合計が一番低いものを採用してみます。
具体的には、次の候補が1000個あるとしたら、その1000個に対してそれぞれ、各ヒット及びブロー数における残りの候補数を出します。その合計が一番低いものを次の予想として採用してみます。
とりあえず、実装してみます。
const int combinations[15][2] = {{4, 0}, {3, 0}, {3, 1}, {2, 0}, {2, 1}, {2, 2}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}};
// 全てのヒット数及びブロー数の組み合わせ
int think_guess(int candidates[], int candidates_count) {
int best_guess = candidates[0]; // 一番良いguess
int best_sum = INT32_MAX; // 一番良いguessをした時の候補数の合計
for (int i = 0; i < candidates_count; i++) {
int guess = candidates[i]; // 一つ選ぶ
int sum = 0; // 各ヒット数及びブロー数の時に残る候補の合計
for (int j = 0; j < 15; j++) {
int hit = combinations[j][0];
int blow = combinations[j][1];
int count = 0;
for(int k = 0; k < candidates_count; k++) {
if(check(candidates[k], guess, hit, blow)) {
count++;
}
}
sum += count;
}
// 最善のものを取り出す
if (sum < best_sum) {
best_sum = sum;
best_guess = guess;
}
}
return best_guess;
}
int main() {
//省略
guess = think_guess(candidates, candidates_count);
//省略
}
とりあえず、前回書いたPythonのスクリプトを回してみます。
…あれ、結果が出てこない…
そうか、前回までは次の予想をする際にランダムに1個取り出していたので数秒ほどで5000ケース試せていましたが、流石に計算量的にそんなに早くは終わらないですね…
処理がどれぐらい終わったかをログに表示して待ってみます。
...
[##########--------------------] 1691/5040 (33.55%)
[##########--------------------] 1692/5040 (33.57%)
[##########--------------------] 1693/5040 (33.59%)
[##########--------------------] 1694/5040 (33.61%)
[##########--------------------] 1695/5040 (33.63%)
...
並列に回せるようにしなきゃですね…全ケース回すのに2時間弱待ちました。。。(反省)
結果を見てみます。
Average turns: 5.56
1 turns: 1
2 turns: 13
3 turns: 108
4 turns: 596
5 turns: 1668
6 turns: 1768
7 turns: 752
8 turns: 129
9 turns: 5
10 turns: 0
ん？よくみると全てのケースを実行した時と同じじゃないですか…？
よくよく考えたら、全てのヒット及びブロー数において、残りの候補からその候補を絞った時の和は全て一律になりますね。
例えば、"0123"について全てのヒット及びブロー数と一致する候補を絞り込むときを考えます。
すると、元からあった候補には"0123"と"0hit0blow"する数、"0h1b"する数、"0h2b"する数…"4h0b"する数、全てが重なることなく存在しているからです。そしてその合計は元からあった候補と同じです。
そして、"0123"以外の時も一緒です。なので上記のコードでのsumの値は変わりません。
意味のないコードの実行が終わるのに2時間かかりました。
2時間待ったのに…穴があったら入りたいです。
改善2-2
今行いたいことは、1回の予想でなるべく候補数を少なくすることです。
次のことを行ってみます。
評価関数として各ヒット及びブロー数における、候補数の2乗を計算し、それらの合計を求めます。この合計値が小さいものを採用します。
2乗を選ぶ理由として、どのヒット数及びブロー数であった時でも残りの候補数を少なく絞り込めるようにするためです。逆にいうと、あまり減少しないケースがあるものを省くことができます。
for (int j = 0; j < 15; j++) {
int hit = combinations[j][0];
int blow = combinations[j][1];
int count = 0;
for(int k = 0; k < candidates_count; k++) {
if(check(candidates[k], guess, hit, blow)) {
count++;
}
}
- sum += count;
+ sum += (count * count);
}
もう一度、全てのケースを試してみます。
並列処理を作ったのでもう2時間待つ必要がありません！
[##############----------------] 2365/5040 (46.92%)
並列処理を行い、コンパイルオプションに-O3をつけることで30秒ほどで終わりました。
追記: -O3をつけないと30分弱かかりました。だいぶ変わりますね…私のコードが改善の余地しかない、ということになります。
あまりコンパイルオプションについては知識がないので、語れません。後日ちゃんと調べてみることとします。
計算量について考えてみる
現在の実装では、もちろん、think_guess()関数での計算がかなり大きくなっております。
一番外側のループではcandidates_count回、そして中間では15回、そして内側のループでは同じようにcandidates_count回、回しています。
よって、計算量はだいたい$O(15\times N^2)$、$N=candidates_count$となります。
15回も、定数倍とはいえ、$O(N^2)\times15$となると大きいです。
実際にこの回数計算することはないのですが、候補の最大値5040をcandidates_countに入れると、大体$3.8\times10^8$回ほどの計算になってしまいます。
次回の改善は高速化になりそうですね…
結果を見てみると、
Average turns: 5.35
1 turns: 1 (1)
2 turns: 13 (13)
3 turns: 109 (108)
4 turns: 631 (596)
5 turns: 1999 (1668)
6 turns: 1897 (1768)
7 turns: 388 (752)
8 turns: 2 (129)
9 turns: 0 (5)
10 turns: 0 (0)
おお！だいぶ改善したのではないでしょうか？
9回のケースはもちろん、8回のケースですら2つになり、7ターンのケースも半分ほど減っています。
この方針で良さそうですね。
気持ち程度の改良(失敗)
気持ち程度ですが、以前このような評価関数を作った際に2.5乗の和を取ると良かった覚えがあるので、やってみます。
- sum += count * count
+ sum += count * count * sqrt(count);
結果は次のようになりました。
Average turns: 5.38
1 turns: 1
2 turns: 13
3 turns: 109
4 turns: 624
5 turns: 1918
6 turns: 1958
7 turns: 413
8 turns: 4
9 turns: 0
10 turns: 0
2乗の時と比べるとむしろ悪化していますね。
だめでした。
改善2-3
さて、現段階で私が思いつく最後の改良をしていきます。
改善2-1では残りの候補から次の予想の数字を選んでいましたが、全ての候補から選んでみます。
int think_guess(int candidates[], int candidates_count, const int all_candidates[], const int all_candidates_count) {
int best_guess = candidates[0]; // 一番良いguess
int best_sum = INT32_MAX; // 一番良いguessをした時の候補数の合計
for (int i = 0; i < all_candidates_count; i++) {
int guess = all_candidates[i]; // 一つ選ぶ
int sum = 0; // 各ヒット数及びブロー数の時に残る候補の合計
for (int j = 0; j < 14; j++) {
int hit = combinations[j][0];
int blow = combinations[j][1];
int count = 0;
for(int k = 0; k < candidates_count; k++) {
if(check(candidates[k], guess, hit, blow)) {
count++;
}
}
sum += (count * count);
}
// 最善のものを取り出す
if ((sum < best_sum)) {
best_sum = sum;
best_guess = guess;
}
}
return best_guess;
}
all_candidates[]に全ての候補が入っており、そこから一つを選んだ時における全てのヒット及びブロー数でどれぐらい候補が絞られるかをカウントし、そのカウントの2乗和を取っていきます。
前回のアルゴリズムで9ターンを要したケース、"9204"でやってみます。
候補数: 5040
Turn:1
Guess: 0123
Enter hit counts! = 0
Enter blow counts! = 2
候補数: 1260
Turn:2
Guess: 1435
Enter hit counts! = 0
Enter blow counts! = 1
候補数: 304
Turn:3
Guess: 3067
Enter hit counts! = 0
Enter blow counts! = 1
候補数: 70
Turn:4
Guess: 8261
Enter hit counts! = 1
Enter blow counts! = 0
候補数: 7
Turn:5
Guess: 4290
Enter hit counts! = 1
Enter blow counts! = 3
候補数: 1
Turn:6
Guess: 9204
Enter hit counts! = 4
Enter blow counts! = 0
needed turns: 6
前回の結果
候補数: 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
改善前のコードでは、確定したかと思われる数字を複数ターンで使い続けています。
それでは4つの枠を効率的に使っているとは言えません。
一方、改善後のコードでは2~4ターン目で様々な数字を使ってみることでヒット及びブロー数は少ないものの、効率的に絞り込めており、結果的に少ないターンで当てることができています。
全てのケースを試してみます。
Average turns: 5.27 (5.56)
1 turns: 1 (1)
2 turns: 4 (13)
3 turns: 59 (108)
4 turns: 574 (596)
5 turns: 2430 (1668)
6 turns: 1885 (1768)
7 turns: 87 (752)
8 turns: 0 (129)
9 turns: 0 (5)
10 turns: 0 (0)
平均が5.56から5.27ターンとなり、8ターンで当てていた数もなくなりました。
大分良い改良ができたのではないでしょうか。
改善2-4
最初の候補で必ず"0123"を選んでいるので、そこをランダムに取ってみます。
やることは改善1と同じです。
srand((unsigned int)(time(NULL)));
int guess = all_candidates[rand()%all_candidates_count];
実行してみます。
Average turns: 5.23 (5.56)
1 turns: 1 (1)
2 turns: 2 (13)
3 turns: 72 (108)
4 turns: 622 (596)
5 turns: 2471 (1668)
6 turns: 1790 (1768)
7 turns: 82 (752)
8 turns: 0 (129)
9 turns: 0 (5)
10 turns: 0 (0)
ばらつきが少なくなりましたね。
アイデアが尽きたので、今回の改良はここまでにします。
おわりに
自分の中ではかなりいいアルゴリズムを考えることができて満足しています。もちろん、今のコードだと計算量が膨大であまり綺麗とは言えませんが…
もし何か、良いアルゴリズム等があれば教えていただけると幸いです！
これってただの全探索ではないですか？
工夫したのは2乗和を取るところぐらいですかね…？
次回は計算量を削減したいところですが、私のデータ構造や高速化に対する知識がないため、直ぐには欠けるような気がしません。
ここまで読んでいただき、ありがとうございました！
作成したコード
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int combinations[14][2] = {{3, 0}, {3, 1}, {2, 0}, {2, 1}, {2, 2}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}};
// 全てのヒット数及びブロー数の組み合わせ
// 最初の候補となる数字の列挙
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;
}
int think_guess(int candidates[], int candidates_count, const int all_candidates[], const int all_candidates_count) {
int best_guess = candidates[0]; // 一番良いguess
int best_sum = INT32_MAX; // 一番良いguessをした時の候補数の合計
for (int i = 0; i < all_candidates_count; i++) {
int guess = all_candidates[i]; // 一つ選ぶ
int sum = 0; // 各ヒット数及びブロー数の時に残る候補の合計
for (int j = 0; j < 14; j++) {
int hit = combinations[j][0];
int blow = combinations[j][1];
int count = 0;
for(int k = 0; k < candidates_count; k++) {
if(check(candidates[k], guess, hit, blow)) {
count++;
}
}
sum += (count * count);
}
// 最善のものを取り出す
if ((sum < best_sum)) {
best_sum = sum;
best_guess = guess;
}
}
return best_guess;
}
// ヒット数とブロー数から候補を絞り込む関数
void narrowdown(int candidates[], int *candidates_count, const int guess, const int hit_count, const int blow_count) {
int narrowed_candidates[5040]; // ヒット数とブロー数から計算した残りの候補を入れる
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[5040]; // 残りの候補
int candidates_count = 0; // 残りの候補数
initialCount(candidates, &candidates_count);
int all_candidates[5040];
int all_candidates_count = 0;
initialCount(all_candidates, &all_candidates_count);
// ランダムな数を最初に選択する。(偏りをなくすため)
srand((unsigned int)(time(NULL)));
int guess = all_candidates[rand()%all_candidates_count];
int hit_count = 0, blow_count = 0;
int turns = 0;
while (hit_count != 4) {
turns++;
printf("候補数: %d\n", candidates_count);
fflush(stdout);
printf("Turn:%d\nGuess: %04d\n", turns, guess); // 予想した数字を出力
fflush(stdout);
printf("Enter hit counts! = \n");
fflush(stdout);
scanf("%d", &hit_count); // ヒット数を受け取る
printf("Enter blow counts! = \n");
fflush(stdout);
scanf("%d", &blow_count); // ブロー数を受け取る
narrowdown(candidates, &candidates_count, guess, hit_count, blow_count);
guess = think_guess(candidates, candidates_count, all_candidates, all_candidates_count);
}
printf("needed turns: %d\n", turns);
return 0;
}