Hexの必勝手順に対する新証明技法について
スポンサーリンク
概要
- 論文の詳細を見る
ゲームHexは,先手必勝手順の存在が証明されているが,具体的な必勝手順を示すことは長年の研究課題である.盤面の大きさが8×8以上になると,必勝手順を簡潔な形で扱うことは複雑すぎるとされてきた.本稿では,石の連結性を定義するための新しい概念として,σ 連結を提案し,それに基づくσ 拡張の技法を導入する.本稿の目的は,σ 連結とσ 拡張によって,新しい先手勝ちの証明法を確立し,必勝手順の構成に応用することである.本稿では,Noshitaのユニオン連結を一般化する.これにより,連結の論理和だけでなく,論理積を扱えるようにする.この一般化した連結をAND-OR連結と呼ぶ.σ 連結は,着手が指定がされたAND-OR連結であり,AND-OR連結の手順を示す証明木の部分木で定義される.σ 拡張は,σ 連結の着手指定に基づいて,AND-OR連結に関与する領域を拡張する技法である.これらの技法を用いることで,深い探索をしなくても,勝利手順を示すことができる.σ 連結とσ 拡張を必勝手順の構成に応用すると,8×8の必勝手順を簡単に検証可能な形で記述することができる.
- 2009-02-15