追い詰めルーチンでは相手の
- 三、四などの追い手
- ネライ手（Passすると禁手に極められる）
の防手を頻繁に生成します。三、四の直接防手生成はパターンマッチングで容易に生成可能ですが、解禁する手など禁手に絡む防手生成処理が煩雑で実装上の難しいポイントの一つだと思います。
実際、初めて作った連珠プログラムではパターンマッチングで防手生成をしていましたが、防手生成漏れがあり正しく詰み／不詰が判定できないという問題がありました。
例えば上の例では出来たトビ三を点GH, JH, LHで止めてもいずれも黒勝ちがあります。万事休すかと思いきや点JJ！という手があり、この手で点JHが禁点になり達四が消滅するだけでなく白勝ちになります。
こういった例がルール上あり得るので相手の追い手／ネライ手に対してすべての空点を生成して防げるかチェックするように変更しましたが、処理が重いという欠点がありました。
REAL Coreでは「影響領域（Influence area）」という概念を定義して防手を効率的に生成できるようにしています。
影響領域の定義
指し手[math]m[/math]と指し手のパターン[math]P[/math]（四、三など）に対して
- パターン[math]P[/math]が新たに成立するための手の集合
- パターン[math]P[/math]が成立から不成立になるための手の集合
を以下で定義します。
- 着手[math]m[/math]でパターン[math]P[/math]が成立するとする。着手[math]m[/math]の前に着手[math]m_i[/math]を行うことでパターン[math]P[/math]が成立しなくなる手[math]m_i[/math]の集合を「下向きの影響領域（downward influence area）」と呼ぶ。
- 着手[math]m[/math]の前に着手[math]m_i[/math]を行うことでパターン[math]P[/math]が新たに成立する手の集合[math]m_i[/math]を「上向きの影響領域（upward influence area）」と呼ぶ
影響領域による防手生成
相手が黒番の場合、終端手は達四のみです。Passをしたときに相手（黒番）に達四ができる場合その防手は
- 達四の下向き影響領域
- 達四点を禁点にするための上向き影響領域
になります[1]他にも四ノビする手もありますがここでは割愛します。。
相手が白番の場合、終端手は達四、四々、極め手なので、Passをしたときに相手（白番）に終端手ができる場合その防手は
- 達四の下向き影響領域
- 四々の下向き影響領域
- 極め手（四）の下向き影響領域
- 極め手（禁点）の下向き影響領域
になります。達四、四々、四の下向き影響領域はパターンマッチングで求めることができますが、禁手の下向き／上向きの影響領域は少し複雑です。
禁手の下向き影響領域
長連、四々が成立している場合はその下向き影響領域をパターンマッチングが求めることができます。三々が成立している場合、
- 見かけの三が2つ以上存在する
- 見かけの三のうち達四点が禁点でない見かけの三が2つ以上存在する
なので、その下向き影響領域は
- 見かけの三の下向き影響領域
- 見かけの三のうち達四点を禁点にするため上向き影響領域
の和集合で与えられます。三々の下向き影響領域を求めるのに禁点の上向き影響領域が必要になるので再帰的に求める必要があります。
禁手の上向き影響領域
長連、四々の上向き影響領域をパターンマッチングが求めることができます。三々が成立していない場合に三々が成立するための上向き影響領域は
- 見かけの三の上向き影響領域
- 見かけの三の達四点を解禁するための下向き影響領域
になります。この場合も禁点を解禁するための下向き影響領域が必要になるので再帰的に求める必要があります。
REAL Coreでの実装
上記の影響領域の考え方を下に相手の終端手防手を生成する機能をBitBoard.hの
template<PlayerTurn P> const bool GetTerminateGuard(const BoardOpenState &board_open_state, MoveBitSet * const guard_move_set) const;
で実装しており、相手に終端手防手が存在する場合にはguard_move_setに防手bitがセットされるようになっています。なお、黒の達四、白の達四、四々、極め手に対する判定／防手生成はそれぞれ
//! @brief 1手勝ち(達四)が生じているかチェックし、その防手を生成する //! @param P チェックする手番 //! @note 四ノビ防手は生成しない //! @note 禁手チェックは行わない template<PlayerTurn P> const bool GetOpenFourGuard(const BoardOpenState &board_open_state, MoveBitSet * const guard_move_set) const; //! @brief 1手勝ち(四々)が生じているかチェックし、その防手を生成する //! @note 四ノビ防手は生成しない const bool GetDoubleFourGuard(const BoardOpenState &board_open_state, MoveBitSet * const guard_move_set) const; //! @brief 1手勝ち(極め手)が生じているかチェックし、その防手を生成する //! @note 四ノビ防手は生成しない const bool GetMakeForbiddenGuard(const BoardOpenState &board_open_state, MoveBitSet * const guard_move_set) const;
で実装しています。なお、より詳細な情報を知りたい方は
- move_pattern.pptx: 「終端手の防手生成」
- forbidden_check.pptx: 「禁手判定の影響領域」
を参照ください。
References
| ↑1 | 他にも四ノビする手もありますがここでは割愛します。 |
|---|