禁手列挙

ある着手[math]m[/math]が禁手かどうかチェックする機能（禁手チェック）に続き、ある局面の禁手を列挙する機能を実装しました。

もちろん、局面の空点に対して禁手チェックを行えば禁手を列挙することは出来るのですが、禁点パターンを検索することで高速に禁手を列挙することができます^[1]実際、着手が禁手かどうかを解説したサイトはありますが禁手を列挙する方法を説明したサイトは見たことがないです。。

そもそも禁手を列挙する必要性があまり無い^[2]生成する手を枝狩り等で絞っている場合はわざわざ禁手列挙せず生成した手だけ禁手チェックすれば良いetcように感じられる方もいると思いますが、限珠案の解図や追詰め問題の最短解を求める場合は候補手として全空点を生成することがあり、禁手列挙を高速に行うことで全体を高速化することが出来ます。

禁手列挙のための禁点パターン

禁手を列挙するために禁手に関連する長連、達四／四、見かけの三の1手前のパターンを定義します。

• 長連点: B[B3O1]B
• 達四点：XO[B3O1]OX
• 四ノビ点：X[B3O2]X
• 見かけの三ノビ点：XO[B2O2]OX

長連となる位置の列挙

長連点パターン（B[B3O1]B）を検索しパターン中の空点が禁点になります。

四々となる位置の列挙

四ノビ点パターン（X[B3O2]X）を検索し、パターン中の空点を

• 四ノビ点
• 次に五連を作る点

とし、「四ノビ点」ごとに「次に五連を作る点」を記録していきます。記録後、「同一四ノビ点に次に五連を作る位置が2つ以上ある」場合、その四ノビ点は四々となる点になります。

なお、達四点パターン（XO[B3O1]OX）が存在すると「四ノビ点パターン」が2回マッチして正しく「次に五連を作る点」をカウントできないので片方のマッチをオフにする必要があります。詳細はGitHub上のドキュメントforbidden_check.pptx: 「達四点がある場合の四ノビ点のマッチ方法」を参照ください。

三々となる位置の列挙

まず、見かけの三ノビ点パターン（XO[B2O2]OX）を検索し、見かけの三を作る空点とその方向（ヨコ、タテetc）を記録していきます。同一空点に複数の方向で見かけの三ができる場合は、「見かけの三々」ができることになります。あとは、「着手の禁手判定」で紹介したように「見かけの三々」が「三々」か判定します。

禁点パターン検索の差分更新

長連点、達四点／四ノビ点、見かけの三ノビ点のパターンをBitBoard上で検索しても十分高速ですが、1手の着手で検索結果が変わるのは限られた領域^[3]REAL Coreでは着手によりパターンが成立しなくなる点の集合を「影響領域(Influence area)」と呼んでいます。詳細はGitHub上のドキュメントmove_pattern.pptx: … Continue readingだけであることに着目すると着手前の検索結果を引き継いで、着手による変化があった部分だけ更新することでさらに高速化することができます。

REAL Coreではパターン検索結果の差分更新をサポートしており、

• OpenStateクラス: 特定パターンの検索結果を保持
• BoardOpenStateクラス: 局面ごとに検索パターンの結果リストを保持

を使って1つ前の局面のBoardOpenStateクラスから現局面のBoardOpenStateクラスを差分計算できるようにしています。

性能評価

以下の3つのアルゴリズム

• EachPoint: 全空点の禁手をチェック
• BitBoardScan: BitBoardから禁点パターンを検索
• OpenStateUpdate: パターン検索結果を差分更新

ごとに手元の棋譜データベース（棋譜数: 1,073,787, 総局面数: 38,040,967）の禁手を列挙するのに要した時間を計測しました。

• CPU: Core i5-2500K
• OS: Ubuntu 16.04 on Windows with VMWare Player
• Mem: 8GB
• Compiler: g++ 5.4.0
• Compile Option: -O3 -DNDEBUG

評価結果

• EachPoint: 160.9秒(23.6万局面/秒)
• BitBoardScan: 34.2秒（111.2万局面/秒）
• OpenStateUpdate: 27.4秒（138.7万局面/秒）

となり、禁点パターンを使って禁手列挙することで全空点の禁手をチェックとするのと比べて5倍程度高速化できました。さらにパターン検索結果を差分更新することで25%程度の高速化に成功しています。