正規局面[math]P[/math]における着手[math]m[/math]が禁手か判定することを考えます。なお、白番には禁手がないので手番は黒番であるとします。
公式ルールでは着手[math]m[/math]により以下のいずれかが生じる場合、禁手となります。
- 長連:6個以上の黒石の連ができること
- 四々:四または達四が同時に2つ以上できること
- 三々:三が同時に2つ以上できること
この記事ではそれぞれの判定方法について紹介します。なお、局面の正規性、Bitboardでのパターン検索、直線近傍で説明した内容を前提としているので併せてご参照ください。
長連の判定
[math]m[/math]を着手後に黒石が6個連続するパターンBBBBBBを検索しパターンが存在すれば長連が生じています。パターンの検索には長さ5の直線近傍を使えば十分です。
なお、着手[math]m[/math]で長連が生じる場合、着手[math]m[/math]は連の端ではない(すでに五連か長連ができてることになり着手前の局面[math]P[/math]が正規局面であることに反する)ことに注意すると長さ4の直線近傍で十分ですが、
- 四々、三々の判定では長さ5の直線近傍を使う
- 長連の判定は長さ5の直線近傍でも同じ結果が得られる
ので処理を共通化するためREAL Coreの実装では長さ5の直線近傍を使っています。
四々の判定
[math]m[/math]を着手後に四のパターンX[B4O1]X[1]Xは黒石以外、[BmOn]は黒石m個、空点n個を含むパターンを表します。を検索して五連になる位置が2カ所以上[2] … Continue reading見つかるかどうかで判定できます。パターンX[B4O1]Xの検索には着手[math]m[/math]の長さ5の直線近傍を使えば十分です。ただし、達四(XOBBBBOX)がある場合には2カ所で四のパターンがマッチするので重複カウントしないよう四の検索結果から達四による重複分を除く必要があります。
四々については一直線上にできる[3]両頭の四々、長蛇の四々、双竜の四々と呼ばれるパターンがあることがあり、ルール説明やパターンマッチの解説では分けて説明されることがありますが上記の判定方法で一直線上にできる四々も正しく判定できるのでREAL Coreでの実装では特に分けていません。
三々の判定
長連と四々はパターン検索だけで判定できますが三々については「三の判定」と「禁手の判定」が相互に依存するため少し複雑な処理が必要です。
まず「三」の定義を確認すると「同色の石を1個加えると達四になるもの」となっており、達四にするために「同色の石を1個加える」点(トビ三の場合は1カ所、三連の場合は2カ所存在)がすべて禁点の場合は三ではありません。例えば、下図のI点は一見、三が二つできているように見えますが横方向の三が達四になる点はともに四々禁点となるため横方向は三はできていません。(引用元:The Renju International Federation portal: Advanced Tutorial)
この例から分かるように
- 三の判定には禁手の判定が必要
- 禁手の判定には三の判定が必要
と相互に依存しており、正しく三/禁手の判定するには再帰的に判定する必要があります。
REAL Coreでは判定の高速化、差分計算をしやすいよう三の判定を
- 見かけの三(Semi three)の判定:パターン検索のみでできる判定
- 三(Three)の判定:再帰的な処理が必要になる判定
の2つに分けています。
「見かけの三」はパターンXO[B3O1]OXにマッチするもので、「三」は「見かけの三」の達四にする位置のうち少なくとも1つが禁点ではないものと定義します。パターンXO[B3O1]OXの検索は着手[math]m[/math]の長さ5の直線近傍[math]L[/math]を使えば十分で、三の判定フローは以下になります。
- 直線近傍[math]L[/math]でパターンXO[B3O1]OXを検索する。マッチしなければ三ではない
- マッチした場合は達四にする位置を記録しておく
- 達四にする位置が1つでも禁点でなければ三、すべて禁点ならば三ではない
となります。さらに長さ5の直線近傍[math]L[/math]では各方向で高々1つしか「(見かけの)三」が生じないことに注意すると三々の判定フローは以下になります。
- 直線近傍[math]L[/math]の各方向で三が生じているか判定する
- 2方向以上で三が生じていれば三々、そうでなければ三々ではない
一部のソフトでは「三」の判定を「見かけの三」の判定で代用しているようですが、公式ルールに準拠するためには三の判定をきちんと実装する必要があります。
ピンバック: 禁手列挙 | 連珠プログラム(Quinstella, REAL Core)開発ブログ
ピンバック: 禁手列挙 | 連珠プログラム開発ブログ