ゲームHexにおける必勝手順の検証プログラム

概要

論文の詳細を見る
ゲームHexは、先手必勝手順の存在が証明されているが、具体的な必勝手順を求めることは長年の研究課題である。これまでに示されている必勝手順は、ユニオン連結による盤面分割が多用されている。今後大きな盤面における必勝手順を導くためには、人の手で盤面分割を行い、コンピュータでその細部の検証を行うなどの共同作業が必要になる。そこで、本稿では、連結の判定を行うプログラム(プログラムAとB)を作成した。プログラムAは、通常のand-or探索にHex特有の技法を導入し、探索効率を向上させたものである。プログラムBは、プログラムAに、仮想準連結に基づく連結判定法などを組込んだものである。両プログラムの性能評価のために、野下の示した7×7と8×8の必勝手順の正しさを検証した。その結果、両方のプログラムにおいて、極めて短時間で検証を終えることができた。さらに、人間の熟練者と同じ程度に正確な盤面解析を行っていた。本稿のプログラムは、必勝手順の検証・発見に充分実用的な性能を持っているといえる。
一般社団法人情報処理学会の論文
2008-03-12