ちょっとした現実世界の例

ドラフツ (draughts) は何千年にもわたって遊ばれているボードゲームです。ドラフツには様々なバージョンがありますが、アメリカ人の多くにとってはチェッカー (checker) あるいはイングリッシュドラフツ (English draughts) と呼ばれるものが一番身近でしょう。しかし世界で一番知られているバージョンは国際ドラフツ (international draughts) あるいはポーランドドラフツ (Polish draughts) と呼ばれるものであり、16 世紀のオランダに起源を持ちます。完全なルールについては Wikipedia に譲り、英米バージョンとの主な違いをここに示します:

例えば次に示す初期状態において円が普通の駒を、二重の円がキングを表しているとすると、黒は必ず図に示された動きを行わなければなりません。この動きで黒が取り除くことになる白い駒の数 \(5\) が他のどんな動きよりも多いからです。黒の駒が 5 個の駒を取った後に動きをこれ以上続けられないのは、一度取った駒はターンが終わるまで盤に残ったままであるためです。その後白は図に示された動きを必ず行わなければならず、この動きによって白が勝利します。

国際ドラフツの動き。二重の円がキング。この盤面においては二人のプレイヤーが打てる手はこれしかない (!)
図 12.18
国際ドラフツの動き。二重の円がキング。この盤面においては二人のプレイヤーが打てる手はこれしかない (!)

実際のゲームは \(10 \times 10\) の盤と双方 20 個ずつの駒を使って行いますが、この設定では任意のゲームが計算機的に自明になってしまいます。つまり、任意の盤面に対する可能な手をあらかじめ計算して定数サイズのルックアップテーブルに格納しておくことで、次の盤面の計算が定数時間で行えるということです。もちろん定数は巨大になりますが、定数であることに違いはありません!

しかし国際ドラフツを \(n \times n\) に自然に拡張した場合、合法な手を見つけることが NP 困難になります! 次に説明するのは 2010 年に Bob Hearn によって発見された1 有向グラフにおけるハミルトン閉路問題からの帰着です。ほとんどの二人対戦ゲームにおいては最良の手を見つける問題が NP 困難に (あるいはそれ以上に難しく) なりますが、ルールに従うだけで NP 困難となってしまうゲーム ――さらに言えば、何世紀にもわたって遊ばれているゲーム―― というのは私はこれしか知りません!

\(n\) 頂点の無向グラフ \(G\) が与えられたと仮定して、国際ドラフツの盤面であって \(G\) にハミルトン閉路が存在するときに限って白が指定された数の黒の駒を取れるものをこれから構築します。\(G\) の頂点に適当な順番で \(1\) から \(n\) まで番号を振り、\(G\) の無向辺 \(uv\) を \(u \rightarrow v\) と \(v \rightarrow u\) に分けることで \(G\) を有向グラフとして考えます。構築するドラフツの盤面はいくつかのガジェットからなります:

ハミルトン閉路から国際ドラフツへの帰着の概観図
図 12.19
ハミルトン閉路から国際ドラフツへの帰着の概観図

初期盤面では一つの白いキングはいずれかの金庫の下部に置かれ、弧をたどって金庫を空にしていく動きを行えます。\(G\) のハミルトン閉路の逆も \(G\) のハミルトン閉路なので、ガジェットの入口と出口を反転させても構いません。

\(G\) がハミルトン閉路を持つ場合、白いキングは全ての金庫を訪れて最低でも \(nN\) 個の駒を飛び越したうえでスタート地点に戻ってくることができます。一方 \(G\) がハミルトン閉路を持たない場合には、白いキングは少なくともスタート地点の金庫にある黒い駒の半分を飛び越えることができないので、全体で飛び越えることになる黒い駒の数は最大でも \((n - 1 / 2)N + O(n^{3})\) 個となります。ここで \(O(n^{3})\) は曲がり角ガジェットと交差点ガジェットの分です (任意の弧には一つの曲がり角ガジェットと最大 \(n^{2} / 2\) 個の交差点ガジェットが含まれます)。

以上より \(N=n^{4}\) とすれば帰着が完成します。全体としては \(O(n^{5}) \times O(n^{5})\) の盤面となり、\(O(n^{5})\) 個の黒い駒と一つの白いキングを含みます。この構築は総当たりを使っても多項式時間で行えます。完全な盤面の例を次に示します。なお次の問題が NP 困難であるかどうかは未解決です: 「\(n \times n\) の国際ドラフツの盤面が与えられる。白は黒い駒を全て飛び越すことができる (そしてルール上必ずそうすることになる) か?」

例の 4 頂点のグラフに対する最終的なドラフツの盤面 (緑色の矢印は盤面に含まれない)
図 12.22
例の 4 頂点のグラフに対する最終的なドラフツの盤面 (緑色の矢印は盤面に含まれない)

  1. Theoretical Computer Science Stack Exchange より: http://cstheory.stackexchange.com/a/1999/111[return]

広告