キングと悪魔の問題


2003.12.16 ver 0.03
2005.11.29 ver 0.08

 03年12月15日に、「キングと悪魔の問題」として、以下のような紹介をしました。



 無限に広いチェス盤を想像してください。そこに、チェスのキング(あるいは将棋の王将)が1つ、ぽつんと置いてあります。キングですから、自分の手番の時には、タテヨコ斜めの8つのマスのどこか1つに移動できます。孤独なキングは一歩ずつ、この無限に広いチェス盤を歩き回ります。

 さて、この無限に広いチェス盤の下に悪魔がおりました。悪魔はこのキングを動けなくしてやろうと思います。悪魔は、キングが一歩動くたびに、チェス盤のマスを1マス食べてしまいます。食べられてしまったマスにはキングは進入できません。万能の悪魔ですから、無限に広いチェス盤のどのマスでも食べることができます。キングの隣のマスでも、100万も離れたマスでもよいのです。ただしキングが乗っているマスは食べられませんし、一手で食べられるのは1マスだけです。 また、一度食べられてしまったマスは二度と再生しません。時間が経つにつれて、チェス盤にはポツポツと穴が増えてゆきます。

 もしもキングが移動できる周囲8マスの全てが食べられてしまっているという状況に追い込まれてしまったら、キングの負けです。 さて、キングは未来永劫逃げ続けることはできるのでしょうか? それとも、悪魔が十分に賢ければキングを立ち往生させることができるのでしょうか?



 この問題についてちょっと体感していただくため、簡単なJavaアプレットを作ってみました。

このゲームはJavaが動くブラウザでお楽しみいただけます。

 画面中央のマスに描かれた赤丸がキングを表します。これをコンピュータが操作します。あなたは悪魔になって、マス目を1つずつ「食べて」ください。マウスでマスをクリックすると、そのマスの色が黒に変わります。キングはこの盤面から脱出しようとします。盤の周囲のマスは黄色になっていますが、この黄色のマスのどこか1つにキングが到達したらキングの勝ち、あなたの負けです。 ちなみに、この黄色いマスもキング進入不可の黒マスにすることができます。

 実は、キングが十分賢ければこの盤面ではキングの脱出を防ぐことはできないはずなのですが、このプログラムのキングは頭が弱いので、上手に追い詰めれば黒マスで取り囲んでしまうことができます。このプログラムは乱数を利用していないので、こちらが同じ手を打てばキングは必ず同じところに動きます。

 お試し下さい。

(2005.11.29 付記)
 これでは簡単すぎて面白くない、キングにはもっと合理的に動いて欲しい、という方もいらっしゃると思うので、こちらにもっと賢いキングのバージョンを用意しました。こちらにも挑戦してみてください。


[戻る]

mailto:hhase@po10.lcv.ne.jp
2001-2003 hhase