HEXは先手必勝である

HEXは以下の記事で紹介したボードゲームです。

fibonacci-freak.hatenablog.com

実はHEXは先手必勝であることが知られています。このこともまた、ゲームの考案者の1人であるNashが証明しました。

しかもその証明法はあまりにも意外です。ふつう先手必勝といえば「各ターンでこういう手を打てば勝てる」という必勝法を見つけようと考えるでしょう。しかしなんとHEXにおいては具体的な必勝法はわからないのです。

今回はその不思議で圧倒的な証明を紹介したいと思います。

注意: ドロップダウンの中に証明があります。自分で考えてみたい方は見てしまわないようにご注意ください。

定理. HEXは先手必勝である。 

証明. 背理法で示す。先手必勝でないならば後手必勝である（HEXの定理と、残り手数についての帰納法でわかる）。この仮定のもとで先手の戦略を考える。先手は初手はどこを塗ってもよい。この一手を無視し、先手は後手の必勝手順の通りにゲームを進める。ただし途中で塗るべきタイルが既に塗られている場合はどこを塗ってもよい。このとき先手は必勝手順よりさらに1手分得をしているので必ず勝つことができる。これは後手必勝に矛盾している。ゆえに先手必勝である。

このような議論はstrategy stealing argumentと言われていて、他にも様々なゲームに応用できます。しかしこんな証明は人間には思いつかないように思われます。Nashは宇宙人だったのでしょう。