情報処理学会 第87回全国大会

5K-05
ヤバラスのPSPACE完全性
○武藤里樹,武永康彦(電通大)
2人用のボードゲームであるヤバラスの計算複雑さを明らかにした。ヤバラスは六角格子上で行われるゲームで、各プレイヤーは手番に自駒を空きマスに1個置く。勝利条件は自駒を4個以上連続で並べることだが、勝利条件を満たさずにちょうど3個連続で並べると敗北する。本論では、一辺当たりのマスの数を任意の値とした一般化ヤバラスの必勝性判定問題がPSPACE完全であることを明らかにした。また、勝敗条件を変更した穴マスが存在する一般化ヤバラスがPSPACE完全であることを明らかにした。