数学ゲームで必ず勝てる方法

海野研究室

コンピュータに実行してほしいことを伝えるために、私たちは「プログラム」を書きます。しかし、そのプログラムが本当に意図どおりに動作しているかを確認するのは簡単ではありません。多くの場合、いくつかの入力で試しに実行してみるだけです。しかし、それで本当に正しいと言えるでしょうか？入力には無限の可能性があり、すべてを試すことはできません。

そこで、この展示では「数学ゲームで必ず勝てる方法」を題材に、論理的な思考で確実な正しさを導く考え方を紹介します。扱うのは「Nim（ニム）」という有名なゲームです。Nimではいくつかの山に置かれた石を、交互に好きなだけ取っていき、最後の石を取った人が勝ちです。一見、単純なゲームのように見えますが、実は数学的に「必ず勝てる戦略」が存在します。

この戦略を見つけるには、すべての可能な局面を論理的に分析し、「勝ち」や「負け」の状態を理詰めで分類する必要があります。これはまさに、プログラムの正しさを数学的に保証する「ソフトウェア検証」と同じ発想です。どんな入力が与えられても、正しく動作することを数学的に証明することが、私たちの研究分野です。

パズルのように楽しみながら、「論理で確実に正しさを保証する」世界を体験してみましょう。

より詳しく知りたい方はこちら