著者

三島 健 櫻井 英俊 吉元 昭裕 野下浩平

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.49, no.12, pp.4007-4015, 2008-12-15

---

ゲームHexでは,具体的な必勝手順を求めるために,様々な数学的技法が提案されている.8×8や9×9など大きい盤面に対する必勝手順を導くためには,これらの技法に基づいたシステムで人間とコンピュータの共同作業ができるものを実装する必要がある.本稿では,与えられた局面に対してユニオン連結性を判定するプログラムAとBを提示する.プログラムAは局面表を用いたAND-OR探索に基づくものであり,Hex特有の着手選択アルゴリズムにより強化した.プログラムBは,さらに仮想準連結などを組み込んで改良したものである.これらのプログラムは,実行時間と探索節点について評価する.ベンチマーク問題として,Noshitaによる7×7と8×8の必勝手順に現れる約40種類の難しい問題を選んだ.我々の実験結果によると,これらの局面の正しさは,非常に速く検証できた.このことは,我々のプログラムが実用に使えるということを意味する.着手選択(順序付けと先行排除)は,人間の熟練者と同程度に正確であると評価できる.本稿の実験結果をみると,我々のプログラムは,8×8以上の必勝手順の検証・発見のための対話システムを開発する際に最も基本的な道具として使えることが分かる.