数あてゲームのエントロピー

数あてゲームは質問の仕方によってエントロピーの減り方が違います。数字を一気に当てようとする時と、数字の範囲を絞っていく質問では、平均すると後者のほうがエントロピーの減少が速いのです。

一気に当てようとする時のエントロピー

１から２０までの数字を言い当てようとする時、「その数字は１？」というふうに数字を直接指定した場合、運が良ければ一気に答えにたどり着けます。この時当てたい数字のエントロピーは4.3..ビットから一気に０ビットに減少します。無知が完全に消滅するからです。

ところが、実際には最初の質問で答えに当たるということはまずありません。たいていハズレで、候補をほとんど絞り込めずに終わるのです。この場合、減るエントロピーは0.1ビットもありません。

つまり、こういう直接的な質問は、当たったときにはエントロピーを大きく減らせて一見すごそうですが、ほとんどの場合ハズレてエントロピーをほとんど減らせないので、平均的に見るとあまりエントロピーを減らせないのです。計算してみると、減らせるエントロピーは平均して約0.29ビット程度しかないことがわかります。

範囲を半分にする時のエントロピー

では、「その数字は１０より大きい？」と範囲を半分に区切る質問をしたらどうでしょう？この場合、正解でも外れでもそこそこエントロピーを減らせます。

この質問の場合、一回の質問で減らせるエントロピーはおよそ0.5～１ビットです（半分にするというのが１ビット減ることの定義です。1,2,3を1,2に絞ったときは0.5...ビットしか減らせませんが、20選択肢をきっちり半分の10選択肢にできたときはきっちり1ビット減ります）。

比較

最初の質問でどのくらいエントロピーが減るのでしょう？数を直接聞く質問の場合は、平均して約0.29ビット減ります。数の範囲を聞く質問の場合は、確実に１ビット減らせます。範囲を半分に絞る方が３倍もビットを減らせるのです。

数あてゲームをクリアするとは、数字のエントロピー（無知）をゼロにするということです。数字の範囲を半分にしていくほうが着実にエントロピーを減らしていけるので、答えに素早くたどり着けるわけです。