数当てゲームで遊んでみよう〜探索問題の二分探索アルゴリズム〜

ゲームとは？

ゲームとは何でしょうか？

色々な定義が考えられますが、ここでは、プレイヤーと相手（人間の場合もあれば、コンピュータの場合もあるでしょう）の間にやりとりがあり、またランダム性があって、決まった方法では勝ちが決まらないもの、と考えてみましょう。

そう考えると、綺麗な画像や、たくさんのボタン操作が無いものも、「ゲーム」と見なすことができます。

数当てゲームを作ってみる

数当てゲームは、プレイヤーは２人です。一方が秘密の数を決め、他方がその数を当てます。今回は、コンピュータに秘密の数を決めさせて、人間がそれを当てる形で、ゲームにします。

対戦の流れは次の通りです。

1. ゲームを始めると、コンピュータは１から１００の範囲で乱数を作ります。最初、コンピュータはその値を隠します。
2. プレイヤーは、その隠された値を当てます。
3. プレイヤーが「答え」として示した値が当たりでなかったとき、コンピュータはその値と隠された値を比較して、「もっと大きい数字です」または「もっと小さい数字です」とヒントを出します。
4. 正解が入力されるまで、2.と3.を繰り返します。

簡単ではありますが、プレイヤーとコンピュータの間にやりとりがあり、1から100のどの値を隠すかはランダムなので、ゲームと呼んでよいでしょう。

なお、値を入力せずにOKをクリックすると、強制的に終了できます。

さらに、「少ない回数で隠された値を見つける」ことを目標にして、採点するようにしたら、よりゲームらしくなりそうです。

最善手？

このゲームをプレイするとき、プレイヤーの最も善い手（最善手）はなんでしょうか？

コンピュータがランダムに決めた値を、1回目のチャレンジで、確実に当てることは不可能です（ランダムな値を「読む」なんて、無理です！）。

2回目はどうでしょうか？3回目は？・・・当てずっぽうなやり方だと、かなり心もとないですね。

当てずっぽうではなく、1から順に、１がダメなら２、２がダメなら３と、１ずつ増やしながら探していけば、必ず見つかります。コンピュータが隠した値が１なら1回目で見つかります。ですが、隠した値が１００なら100回の試行が必要です。コンピュータが隠す値はランダムなので、（ゲームを何度も繰り返すなら）平均して50回のチャレンジで見つけることができます。

100個の候補の中から、平均してその半分の回数で正解にたどり着くのであれば、悪くない方法かもしれませんが、せっかく対戦相手が出してくれる「大きい」「小さい」というヒントを生かせていないのは、いかにももったいないです。

もっと良い方法はないでしょうか？

7回目までには見つけられる方法

確実に1回で見つけることはできませんが、多い場合でも７回目までに見つけられる方法はあります。

7回目というと、ずいぶん多く感じますが、前に示した「1から順に」の方法だと、最大で100回、平均で50回試す必要があったわけなので、かなり良い成績だと言えるでしょう。

具体的には、次のような手順になります。仮に、コンピュータが隠した値が「78」だとして、手順を見てみます。

1. 1から100の範囲の中央の値を選ぶ。50でも51でもいいのですが、「51」を選びます（最小と最大の値を足して２で割り、端数が出たら切り上げ）。
2. コンピュータは「もっと大きい数字です。」と返します。

3. 「５１と１００」の範囲について、その中央の値を選びます。51+100の結果を2で割り、端数を切り上げます。値は「76」です。
4. コンピュータは、「もっと大きい数字です。」と返します。

ここで上の２つのイラストを見てください。黄色で示した部分が、正解の候補です。

１手目は、（当たり前ですが）正解の候補は１から１００の範囲にあります。

ここで「もっと大きい数字です」というヒントを得たので、答えは正解の候補は、５２から１００の間のどれか、になりました。最初、候補は１００個ありましたが、４９個になりました。およそ半減です。

半減した理由は、もとの範囲の、中央の値を指定しているからです。

続けて、中央の値を指定しながら、どんどん調べる範囲を半減させていきましょう。

5. 「７６と１００」の範囲について、その中央の値を選びます。76+100の結果を2で割り、端数を切り上げます。値は「88」です。
6. コンピュータは、「もっと小さい数字です。」と返します。
7. 「７６と８８」の範囲について、その中央の値を選びます。76+88の結果を2で割り、端数を切り上げます。値は「82」です。
8. コンピュータは、「もっと小さい数字です。」と返します。
9. 「７６と８２」の範囲について、その中央の値を選びます。76+82の結果を2で割り、端数を切り上げます。値は「79」です。
10. コンピュータは、「もっと小さい数字です。」と返します。
11. 「７６と７９」の範囲について、その中央の値を選びます。76+79の結果を2で割り、端数を切り上げます。値は「78」です。
12. 当たりを見つけることができました。

入力は、①51、②76、③88、④82、⑤79、⑥78の順に行いました。6回の試行で、見つけることができました！

※なお、コンピュータ隠した値が「77」だった場合は、7回目で見つけられたことを確認してみてください。「(76+78)/2=77」です。

なぜこの方法がうまくいくか

この「最初に範囲の真ん中を探す。探す範囲を半分にしながら、見つかるまで繰り返す」方法が、7回目までに値を見つけられる理由は、次のように考えると分かります。

1. 1回目に、真ん中で範囲を２つにすると、探す範囲は元の2分の１になる。
2. 2回目に、さらに半分にする（2分の1の、また2分の1なので、4分の1）。
3. 3回目で8分の１。
4. 4回目で16分の１。
5. 5回目で32分の１。
6. 6回目で64分の１。
7. 7回目で128分の１になります。

元の数の範囲が1から100の100個なので、128分の１になると探す範囲は1未満になります。つまり、ここまでで必ず見つかる、ということです。

探索問題を解くアルゴリズム：二分探索

複数の値の中から、対象の値を探す問題を「探索問題」と言います。

実は、「１から１００の範囲の中から、当たりの値を探す」というゲームは、探索問題です。

そして、上で紹介した、「最初に範囲の真ん中を探す。探す範囲を半分にしながら、見つかるまで繰り返す」という方法は、二分探索（別名：バイナリサーチ binary search）として知られるアルゴリズムです。値を探す範囲を二分しながら進めていく、そんな手順をよく表した名前ですね。

１つの問題を解くアルゴリズムは一つではない

ところで、途中で紹介した「1から順に１つずつ」という手順は、線形探索というアルゴリズムでした。

このゲームの例では、最大で100回チャレンジしなければならないので、二分探索より性能の点で劣っていることが分かります（ゲームの値の範囲が「１から１０」なら性能の差はほとんどありません。「１から１０００」になると二分探索の性能の良さが、さらにはっきりします）。

いつでも二分探索が線形探索より優秀なわけではありません。二分探索は、探索する対象の範囲について、値で整列されていないと利用できないのに対して、線形探索の「先頭から順に１つずつ」という方法は、探索する対象が整列していなくても利用できるのです。

問題に対して、それを解くアルゴリズムは、１つとは限りません。複数ある場合もある、ということを確認して、この記事を終わりにします。

学習のヒント

• ゲームの範囲が「１から１００」ではなく「１から１０００」だった場合に、二分探索法で探索を行うとします。最大で何回のチャレンジが必要でしょうか？範囲が10倍に広くなっているので、チャレンジの回数も10倍になるでしょうか？

数当てゲームのプロジェクトのインポート

下記のボタンをクリックすると、数当てゲームのプログラムを含むMonaca Educationプロジェクトをインポートできます。

Monaca Educationにインポートする(要ログイン)

もっと広い範囲（１から５００など）や、もっと狭い範囲（１から１０など）に変更して、二分探索法を試してみてください。