忍者ブログ

Memeplexes

プログラミング、3DCGとその他いろいろについて

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

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


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

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

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

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

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

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

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

比較

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

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

拍手[0回]

PR