著者

ディプタラマ 石黒 裕也 成澤 和志 篠原 歩 ジョーダン チャールズ

雑誌

ゲームプログラミングワークショップ2015論文集

巻号頁・発行日

vol.2015, pp.154-161, 2015-10-30

---

一般化三並べはFrank Hararyによって提案された2人完全情報ゲームであり,碁盤面上に先手後手が交互に石を1つずつ置き,あらかじめ定められた動物を先に作ったプレイヤが勝ちというゲームである.2人完全情報ゲームの勝敗判定問題は与えられたゲームに対して,先手必勝,後手必勝または引き分けとなるかを判定する問題である.オセロや五目並べなど,多くの2 人完全情報ゲームの勝敗判定問題はPSPACE完全であることが知られている.それに対して,代表的なPSPACE 完全問題としてQuantified Boolean Formula (QBF) に対する充足可能性問題(TQBF)が存在し,TQBFを高速に解くプログラム,QBFソルバが開発されてきた.本研究では一般化三並べの拡張であるGTTT(p,q)およびTorusGTTT(m,n)の勝敗判定問題をTQBFに帰着し,QBFソルバを用いてゲーム勝敗判定問題を解く.ゲームのパラメータによっては既存のゲームの探索手法より,QBFソルバの方がより速く勝敗判定問題を解けることが見られた.