必至は終盤において重要な概念だ。必至をかければ勝ちになるので、必至になる手順を見つける必至探索は詰探索と同じ価値があると言える。本解説では、KFEndで行われている必至探索について述べる。まず、対象とする必至の定義を行い、詰探索との類似点／相違点を明らかにする。次に、証明数を用いた探索の試みを含めた、探索アルゴリズムを解説し、必至問題集を解いた実験結果を示す。最後に、必至探索を指将棋プログラムで使用する上での工夫を述べる。
必至とは、詰めろをかけられた状態でその詰めろを逃れる手が無い状態である。詰めろと王手の連続で、受け方がどう受けても必至の状態に到る手順が存在するとき、必至であるという。この定義で必至の本質は表現されているが、受け方による攻め方の玉への王手の扱いが曖昧である。受け方による王手の存在が必至を複雑にしている。資料[1]飯田では、受け方による王手を考慮して、強必至、弱必至という概念を定義している。
強必至は受け方の全合法手に対して攻め方の勝利を保証する。
として、受け方がどう対応しても着手を生成できない局面になることを強必至であるという。ここで「自玉が詰まされない手」とは、その手を指した局面で敵方からの自玉への即詰が無いような手のことである。これには王手も含まれる。
一方、弱必至は受け方の着手から王手を除いたものである。
として、受け方がどう対応しても着手を生成できない局面になることを弱必至であるという。受け方は王手をしないので、攻め方の玉が詰まされることはない。したがって、攻め方の着手から、自玉が詰まされない手という条件は自ずと除かれる。
強必至は弱必至に比べて探索空間が非常に大きい。将棋では王手を10手や20手続けることができる局面は頻繁に現れる。受け方が詰めろをかけられた状態で王手を続ければ、強必至の探索空間はどんどん広がって行く。よほど優れたアルゴリズムを考案しない限り、探索コストがかかりすぎて強必至探索は不可能だろう。
そこで、まずは弱必至に限定して必至を扱うことが考えられる。弱必至は攻め方の必勝を保証するものではないが、以下の理由で研究する価値が十分ある。必至は詰将棋と同じように一種のパズルの問題として扱われる。詰将棋と同様に、必至問題は攻め方の玉が無いものが一般的である。片玉の必至問題を解くには、攻め方への王手が存在しないので、弱必至探索を行うことになる。必至問題を解くことはゲームプログラミングにおいて十分興味のある問題である。また、実戦の終盤において弱必至になる手があるとき、その手が最善手である可能性は非常に高い。必勝の保証は無くても指してみる価値はある。あるいは、得られた弱必至手順をある程度、強必至であるか検証してから指すというやり方もある（これについては後述する）。
KFEndの必至探索が対象とする必至は以下のようなものである。
とした必至である。ただし、それぞれの着手は全ての合法手ではなく一部のみである（すなわち、探索のとき前向き枝刈りを行うということ）。
受け方の着手には、王手でないという条件が無い。したがって王手を生成するが、この王手は、受け方の玉に対しての受けに利きそうな手に限定する。攻め方は弱必至のときと違って王手されることはあるが、自玉の詰をチェックしない。したがって強必至の場合と異なり、攻め方の玉が詰まされる可能性を排除できない。
受けに利きそうな王手というのはヒューリスティックを用いて判断する。例えば、自玉のまわりに利きを生じさせる手とか、敵の駒を取る手である。こういう王手が必至を防ぐのに有効であることはよくある。指将棋の実戦で使用する必至探索で、受けに利きそうな王手を読まないのは危険が大きい。そこで、KFEnd必至探索は受けに利きそうな王手だけは読むようにしている。また、このような王手は通常あまり数多くあるものではないので、探索空間が爆発することはない。以下の解説では、ここで定義した必至を対象とする。
必至は詰と似ているところが多いので、詰探索の理論や有効なテクニックが必至でも使えることが期待できる。またその反面、必至特有の困難もある。
詰探索は詰むかそうでないかを決定するので、AND/OR木を探索することになる。必至探索も同じで、必至になるかそうでないかを決定すればよいので、AND/OR木の探索になる。詰探索はこれまで非常に研究が進んでいる分野だ。深さをしきい値とした縦型探索による反復深化、最良優先探索、証明数をしきい値とした縦型探索による多重反復深化など有力な探索アルゴリズムが発表されている。必至探索も同じAND/OR木の探索なので、これらの探索法が適用できる。もちろん、詰と必至は性質が異なる部分があるので、これらの探索法が全て詰将棋と同じように効果があるとは言えないが、必至でも試してみる価値は十分ある。
詰も必至も、敵玉を追っていって最後に受け無しの状態にするという点は同じである。したがって、どのような着手が有効かを判断するヒューリスティックが詰将棋と同じであることが期待できる。詰探索で重要な「玉の自由度」（玉の逃げ方の個数）を必至探索でも使用できる。
必至の着手生成は非常にコストがかかる。王手、およびそれを逃れる手は局面の静的な情報から生成できるが、詰めろや自玉の詰を回避する手は詰探索を行う必要がある。全ての詰めろを生成しようとすれば、全合法手に対して詰チェックを行う必要があり、探索コストは莫大になる。詰を回避する手も同様だ。詰探索と違って、必至探索では全幅探索は現実的でない。
詰探索で実績のある2つの縦型探索（深さをしきい値とした反復深化、証明数をしきい値とした多重反復深化）を元に、それぞれ必至探索を組み立てた。
enum RESULT {HISSI, FAIL};
int gMax_depth;
CSST gHissi_move;
RESULT attack(int depth){
if(depth < gMax_depth - 1) 詰めろ、王手を生成する
else 詰めろを生成する
生成した手をソートする
for(生成した各手に対して){
その手で局面を進める
RESULT result = defense(depth+1);
局面を戻す
if(result == HISSI){
if(depth == 0) gHissi_move = その手;
return(HISSI);
}
}
return(FAIL);
}
RESULT defense(int depth){
自玉が詰まされない手を生成する
if(depth == gMax_depth){
if(生成した手の数 == 0) return(HISSI);
else return(FAIL);
}
生成した手をソートする
for(生成した各手に対して){
その手で局面を進める
RESULT result = attack(depth+1);
局面を戻す
if(result == FAIL) return(FAIL);
}
return(HISSI);
}
と、互いに再帰的に呼び合うattack()とdefense()を定義して
RESULT gResult;
for(gMax_depth=1; gMax_depth<=5; gMax_depth+=2){
gResult = attack(0);
if(gResult == HISSI) break;
}
と、ルート局面でattack()を呼べば、5手以内で必至があるかがgResultに得られ、必至のときはその初手がgHissi_moveに得られる。
n手必至のn手目は王手でなく必ず詰めろであることを、attack()の着手生成で考慮している。以下、この基本型を詳細化、修正していくことでKFEndの必至探索を明らかにしていく。
必至探索の探索関数は、基本型のように必至かそうでないか(HISSI／FAIL)だけを返せば良いが、KFEndでは符合付き整数で表わした評価値を返すようにして、HISSI／FAIL以外の情報を加えている。それは以下のように決めている。
上で、PNは証明数を表わす。1000という値はn、PNに比べて十分大きいので、評価値空間においてそれぞれの領域が互いに重なることはない。PNの正確な定義はすぐ後のコードリストで明らかになる。評価値が大きい程、攻め方にとって有利になり、0を境に必至かそうでないかに別れるようになっている。証明数が大きくなると、必至になるために探索すべきノードが多くなり、必至になり難いことになる。同じFAILの結果でも証明数が小さい方が評価値はより大きくなり、評価値は必至になりやすいことを表わすことができる。評価値を返すようにした探索関数は基本型の探索関数から修正して、以下のようになる。
typedef Int16 SCORE;
SCORE attack(int depth){
if(depth < gMax_depth - 1) 詰めろ、王手を生成する
else 詰めろを生成する
生成した手をソートする
SCORE best_score = -1000;
for(生成した各手に対して){
その手で局面を進める
SCORE score = defense(depth+1);
局面を戻す
if(score > best_score){
best_score = score;
if(best_score > 0){
if(depth == 0) gHissi_move = その手;
return(best_score);
}
}
}
return(best_score);
}
SCORE defense(int depth){
自玉が詰まされない手を生成する
if(depth == gMax_depth){
if(生成した手の数 == 0) return(1000 - depth);
else return(-20 - 生成した手の数);
}
生成した手をソートする
SCORE best_score = 1000 - depth;
for(生成した各手に対して){
その手で局面を進める
SCORE score = attack(depth+1);
局面を戻す
if(score < best_score){
best_score = score;
if(best_score < 0){
if(best_score == -1000)
return(-1000);
else
return(best_score - まだ展開していない手の数);
}
}
}
return(best_score);
}
形式的に言えば、α-βアルゴリズムを用い、0近傍のヌルウインドウで探索していることになる。受け方手番のノードでの未展開ノードの証明数への寄与は、ノード当たり一律に1としている。局面表を使った動的評価は行っていない。
着手生成の基本的な手続きは、ヒューリスティックを用いて局面の静的な情報からまず候補手を生成し、それらの手を詰探索でチェックして所望の着手を選別するというものだ。
候補手として、敵玉の周りに利きを付ける手、駒を取る手、取られそうな駒を逃げる手を生成する。ただし、自玉に王手がかかっているときは全合法手を生成する。これらの手のうち、王手でない手について詰めろかどうかを判定する。ここで行う詰探索は、単純な深さをしきい値をする縦型探索で行う。重要なパラメータとして詰手数がある。詰手数を大きくとれば、詰めろを見逃す恐れが小さくなり正確だが、実行時間がかかってしまう。
このようにして詰めろと王手を選び出すが、さらに敵玉の自由度によって前向き枝刈りを行う。その手を指した局面での敵玉の自由度がある一定の値より大きい手は削除する。玉の自由度は、玉の周りの8つのますのうち敵（ここでは攻め方）の利きが無いますの数である。KFEndではこれに以下のような修正を行っている。敵利きの無いますに、盤の辺を構成するますが複数含まれているとき、それらのますの数に関わらずそれらのますの寄与は1にする。
例えば図1で、A、B、C、3つの従来の玉の自由度はいづれも8であるが、修正された玉の自由度はAからそれぞれ、8、6、4である。灰色で示したますは辺のますなので、Bでは3つ、Cでは5つあるが、いづれも1とカウントする。手の前向き枝刈りの基準に修正された玉の自由度を用いると、玉を端やすみに追い詰めるような手を刈ってしまうことが少なくなる。
この修正された玉の自由度は、詰探索を研究しているときに思い付いた手法で、有効であった。それを必至でも使っている。以下の解説で、玉の自由度とは、修正された玉の自由度を指すこととする。
候補手として、自玉に王手がかかっているときは全合法手を生成する。そうでないときは、攻め方と同じく、自玉の周りに利きを付ける手、駒を取る手、取られそうな駒を逃げる手を生成する。これに加えて、敵の利きをさえぎるような打つ手、自玉の周りに（利きは生じなくとも）打つ手を生成する。生成した候補手を詰探索して、自玉が詰まされない手を選別する。この詰探索は単純な深さをしきい値をする縦型探索で、やはり詰手数が重要なパラメータになる。
候補手から自玉が詰まされない手を選別する処理は、各手を展開する直前に行う。このため、"評価値"のところで示した探索関数defense()は次のように修正される。
SCORE defense(int depth){
自玉が詰まされない手の候補手を生成する
生成した手をソートする
SCORE best_score = 1000 - depth;
for(生成した各手に対して){
その手で局面を進める
if(受け方の玉に対する詰探索==詰){
局面を戻す
continue;
}
SCORE score;
if(depth < gMax_depth) score = attack(depth+1);
else score = -20 - 1;
局面を戻す
if(score < best_score){
best_score = score;
if(best_score < 0){
if(best_score == -1000)
return(-1000);
else
return(best_score - まだ展開していない手の数);
}
}
}
return(best_score);
}
このように手を展開する直前に逐次的に詰チェックを行う方が、候補手を生成した後全ての候補手をまとめて詰チェックするよりも効率が良い。
defense()は、結果が必至にならないとき、その深さでの証明数の寄与を「まだ展開していない手の数」として評価値に反映させている。自玉が詰まされない手を選別する処理を手を展開する直前に行うと、「まだ展開していない手の数」に自玉が詰まされる手が含まれてしまう。これでは証明数が不正確になって、必至になりやすさの尺度としての評価値に悪影響が出る。しかしKFEndでは、逐次的に詰チェックを行うことの効率の良さを重視して、証明数が不正確になる恐れを受け入れている。より正確な値にするため「まだ展開していない手の数」に次のような修正を行う。
受け方の玉に王手がかかっているとき、合駒する手は数えない。受け方の玉に詰めろがかかっているとき、打つ手は数えない。
いわゆる「強い手」から展開すると探索の効率が良いが、その基準は玉の自由度が基本である。攻め方の手は、受け方の玉の自由度を小さくする手から展開し、受け方の手は逆に自由度を大きくする手から展開するように、並び変える。修正された自由度を使うので、玉を端に追い込むような手が優先される。自由度が同じ手の中では、移動先のますと玉との距離、移動元／指す先のますの利き、指す駒の種類、駒取りの有無（あればその種類）を考慮して順位を決める。
ルートでの反復深化のときに行うソートは、評価値で行う。ある深さのしきい値で行った探索が必至にならなかったとすると、ルートで展開した全ての攻め方の手は負の評価値を得たことになる。"評価値"のところで説明したように、評価値 == -20 - PNであるから、評価値が大きいと証明数が小さいということで必至になりやすいと考えられる。探索関数が証明数を評価値として返すようにているのは、このように反復深化のときのソートキーに使用するためである。
ハッシュ表で実装した局面表を使用している。一般的によく知られた方法を取っているが、ここでは特に、テーブルの登録すべきエントリにすでにデータが登録されている場合に起こる、データの上書きの処理を説明する。KFEndは"Two-level Table"と呼ばれる方式を採用している（資料[2]Breuker）。同一の大きさを持った2つのテーブルA、Bを用意する。現局面を登録すべきエントリをxとする。まず、テーブルAのエントリxを見てすでにデータが登録されており、かつミスすれば、次に、テーブルBのエントリxを見る。ここでもすでにデータが登録されており、かつミスしたときデータの上書きが起こる。テーブルAのエントリxのデータが現局面のデータより価値があるとき、現局面のデータは、テーブルBのエントリxに上書きされる。そうでないとき、すなわち、現局面のデータがテーブルAのエントリxのデータより価値があるか同じとき、テーブルAのエントリxのデータで、テーブルBのエントリxを上書きし、その後、現局面のデータをテーブルAのエントリxに書き込む。ここで「価値がある」とは、より深い探索で得られたデータということである。
この方式だと、テーブルAには価値の高いデータが登録されやすく、テーブルBにはより新しいデータが登録されやすくなる。2つの性質のデータが片方だけでなく、ともにバランス良く局面表に残るので効率が良い。実装が簡単であることも、"Two-level Table"の利点である。
詰将棋では無駄合いが禁止されている。必至でも詰将棋の無駄合いに相当する、取られるだけの無駄な手数延ばしが存在する。必至問題の規則は明確に規定されているわけではないが、このような手は禁止されていると考えて良いようだ。必至問題創作で有名な佐藤大五郎九段の問題集の解説（資料[3]佐藤）にそのような記述がある。詰将棋における柿木の無駄合い判定アルゴリズム（資料[4]柿木）に習って、一般的な必至の無駄な手数延ばしを以下のように定義することができる。
受け方の取られる手をMとして、Mを指さないとn手必至がかかるとする。Mを指し、攻め方がその指された駒を取って王手ないしは詰めろをかけ、その取った駒を使わずに、取った手を含めずにn手必至がかかるとき、Mは無駄な手数延ばしであるとする。ここで、n手必至を調べるときも、無駄な手数延ばしを考慮する。
受け方が王手をかけられている局面では、手Mは合いに限定すべきだろう。詰めろをかけられている局面ではどうだろうか。全ての取られる手を対象にするのは多すぎるように思える。となると、何らかの基準で手を限定する必要があるが、その基準がはっきりしない。また、上の定義では手Mを取られる手としているが、単なる攻め方の玉に対する王手も、無駄な手数延ばしに加えるべきだ。
このように必至における無駄な手数延ばしは、詰将棋に比べて複雑で扱いが面倒だ。そこでKFEndでは、対象となる手を大胆に限定した、以下のような定義を用いている。まずは簡単なものだけを扱おうという方針だ。
N手必至の探索において、N手目を指した局面で、受け方の取られる手をMとして、Mを指さないと（0手）必至の状態であるとする。Mを指し、攻め方がその指された駒を取って詰めろをかけた状態が（0手）必至であるとき、Mは無駄な手数延ばしであるとする。ここで、（0手）必至を調べるときも、無駄な手数延ばしを考慮する。
チェックする局面を、N手必至の探索のN手目を指した局面に限定している。つまり、探索木の末端で探索の延長を行うということになる。一般に、延長は再帰的に複数回行われる。探索木の末端でのみのチェックであるが、KFEndは後述する「1手の先読み」を探索木の内部ノードで行っているので、内部ノードでも限定的ではあるが無駄な手数延ばしが除かれている。また、簡略化のため「取った駒を使わずに」という条件もはずしている。
探索関数は基本型を次のように変更すればよい。defense()で強調表示した部分が基本型との違いである。新たにattack_last()を加える。
RESULT attack(int depth){
”基本型と同じ”
}
RESULT defense(int depth){
自玉が詰まされない手を生成する
if(depth == gMax_depth){
if(生成した手の数 == 0) return(HISSI);
}
生成した手をソートする
for(生成した各手に対して){
その手で局面を進める
RESULT result;
if(depth == gMax_depth) result = attack_last(depth-1, その手);
else result = attack(depth+1);
局面を戻す
if(result == FAIL) return(FAIL);
}
return(HISSI);
}
RESULT attack_last(int depth, CSST move){
moveで指された駒を取る手となる詰めろを生成する
生成した手をソートする
for(生成した各手に対して){
その手で局面を進める
RESULT result = defense(depth+1);
局面を戻す
if(result == HISSI) return(HISSI);
}
return(FAIL);
}
詰将棋の無駄合いの場合も同様だが、無駄な手数延ばしを処理することは探索の効率を上げることにもなる。無駄な手数延ばしがm回発生するn手必至の問題を、無駄な手数延ばしを処理しないで解こうとすると、n+2*m手の必至を探索するコストが生じる。特に実戦の必至ではmが大きくなることがしばしばある。KFEndがとっているような限定的な処理でも、探索の効率化には大きく貢献する。
探索中、攻め方の手番のノードで3手以上手数が残っているとき、まず1手必至がないかを調べる。1手必至でないとき、本来の手数で探索を行う。探索関数は基本型のattack()を以下のように修正したものになる。基本型との違いを強調表示してある。
RESULT attack(int depth){
if(depth < gMax_depth - 1) 詰めろ、王手を生成する
else 詰めろを生成する
生成した手をソートする
RESULT result = FAIL;
if(depth < gMax_depth - 1){
int saved = gMax_depth;
gMax_depth = depth + 1;
for(生成した各手に対して){
その手で局面を進める
result = defense(depth+1);
局面を戻す
if(result == HISSI) break;
}
gMax_depth = saved;
if(result == HISSI) return(HISSI);
}
for(生成した各手に対して){
その手で局面を進める
result = defense(depth+1);
局面を戻す
if(result == HISSI){
if(depth == 0) gHissi_move = その手;
return(HISSI);
}
}
return(FAIL);
}
簡単な1手必至があるにもかかわらず、手を展開する順番が悪くてなかなか結果にたどり着けないという状況に対応するものである。詰探索のルーチンを書いた経験で、この1手の先読みは大して効果が無いと思っていたが、必至ではかなり効果がある。理由はよく分からない。先読みを3手以上にすると先読みのオーバーヘッドが大きくなるためか、かえって遅くなる。また、前述したように、先読みの1手必至の探索においても、無駄な手数延ばしはチェックする。
基本型の探索関数では、必至の手数と初手のみしか得られないが、全ての必至手順が得られるのが望ましい。必至を問題として見た場合、詰将棋と同様、必至手順が解となる。また、指将棋の実戦で必至探索を用いる場合でも、後述する、得られた必至手順を検証するという処理を行うため、手順を得ることが必要である。以下に説明する解手順を得る方法は、KFEndの詰探索で行われているものをそのまま流用している。
処理は2段階に別れる。第1段階は探索中に行われる。探索関数でそのノードの結果が必至のとき、必至となる手を記録する。attack()では、結果が必至となる手が1つ見つかればただちに終了するので、その手を記録すればよい。defense()で、そのノードの結果が必至になるということは、展開した全ての手の結果が必至になるということである。それらの手のうち、必至の手数が最長となる手を記録する。複数ある場合は全て記録する。n手必至になるとき、評価値は1000-nが返ってくるので、評価値が最小になる手を記録すればよい。
このようにして得られる手順はツリーを構成する。"基本データ構造/指し手"にあるようにKFEndの指し手を表わす構造体CSSTはツリーを構成できるように定義されている。探索関数の中でCSSTとして表現された指し手のlink1、link2をつないでツリーを作っていく。探索が終了すると、1つのツリーが得られる。
第2段階として、得られたツリーから必至の解となる手順（ツリー）を抽出する処理を行う。まず、探索で得られたツリーがどのような性質を持つかを述べる。ルートでは反復深化が行われているので、探索で得られた結果がn手必至のとき、n-2手以下では必至にならないことが保証されている。しかし、ルート以外の攻め方手番のノードでは、最短手数の必至手順が得られているとは限らない。このため、受け方手番のノードからの手順には、詰将棋の専門用語で言うところの「変化別詰」（この場合は必至だが）が含まれている可能性がある。一般に変別は解として認められないので、これを除去する必要がある。
変別手順は以下のようにして取り除く。ルートで反復深化の必至探索を行った結果、n手必至になったとする。探索で得られたツリーをルートから深さ優先でスキャンしていき、各ノードで以下の操作を行う。dはそのノードの深さとする。
if(子ノードが2つ以上存在する){
for(各子ノードに対して){
子ノードの表わす手で局面を進める
n-d-3手の必至探索を行う
局面を戻す
if(必至探索の結果が必至である){
子ノード以下の部分ツリーを削除する
}
}
}
ルートでn手必至が最短であることが分かっているので、解手順が最低一つは削除されずに残る。一般には「変化同手数」の解があるので、解はツリーで与えられることになる。
第1段階でツリーを生成するとき、変別が多発してツリーが非常に大きくなり、計算機の記憶領域を使い果たしてしまうことがある。必至では手数が比較的小さいのでそうでもないが、詰将棋では20手前後の手数で探索すると、頻繁に発生する。この問題を解決するには以下のようにする。第1段階のツリーの生成で、深さに制限を設ける。すなわち、ある深さより深いところでは、必至となった手を記録しない。経験上、制限深さを10手位にすれば、ツリーの爆発は生じないことが分かっている。第2段階で、ツリーをルートから深さ優先でスキャンしていくとき、変別解の除去の他に、制限深さより深いところのツリーを生成する必至探索を行う。上のコードリストを以下のように修正する。
if(現ノードがツリーの末端 && d > n){
n-d手の必至探索を行う
得られたツリーを現ノードの子としてつなぐ
}
if(子ノードが2つ以上存在する){
”上のコードリストと同じ”
}
このようにして制限深さ付のツリーを逐次的に生成していきながら、変別解を除去していく。
以上、述べてきた各項目を全て考慮した探索関数によってKFEndの必至探索は行われる。この探索関数を疑似コードで書き下すのは少々煩雑なのでコードリストは省略する。
資料[5]脊尾のC*を必至探索に適用した。ただし、受け方でなく攻め方手番のノードの探索関数で、多重反復深化をしている点が表面的に異なる。
CSST gHissi_move;
SCORE table[局面]; // 局面表
bool checkTable(SCORE &score, int PN, int depth){
if(現局面がtableに登録されている){
SCORE s = table[現局面];
if(s > 0) {score = s - depth; return(true);}
if(s == -1000) {score = -1000; return(true);}
if(-20 - s >= PN) {score = s; return(true);}
}
return(false);
}
void setTable(SCORE score, int depth){
if(score > 0) table[現局面] = score + depth;
else table[現局面] = score;
}
SCORE attack(int depth, int PN){
SCORE best_score = -1000;
if(checkTable(best_score, PN, depth))
return(best_score);
詰めろ、王手を生成する
生成した手をソートする
for(int pn=2; pn<=PN; pn++){
if(pn != 2) 手をkeyをキーとしてソートする
for(生成した各手に対して){
その手で局面を進める
SCORE score = defense(depth+1, pn);
局面を戻す
if(score > best_score){
best_score = score;
if(best_score > 0){
if(depth == 0) gHissi_move = その手;
goto end;
}
}
その手のkey = score;
}
}
end :
setTable(best_score, depth);
return(best_score);
}
SCORE defense(int depth, int PN){
SCORE best_score = 1000 - depth;
if(checkTable(best_score, PN, depth))
return(best_score);
自玉が詰まされない手の候補手を生成する
生成した手をソートする
int pn = PN - まだ展開していない手の数;
if(pn <= 0){
best_score = -20 - まだ展開していない手の数;
setTable(best_score, depth);
return(best_score);
}
for(生成した各手に対して){
if(pn < PN) pn++;
その手で局面を進める
if(受け方の玉に対する詰探索==詰){
局面を戻す
continue;
}
SCORE score = attack(depth+1, pn);
局面を戻す
if(score < best_score){
best_score = score;
if(best_score < 0){
if(best_score > -1000)
best_score = best_score - まだ展開していない手の数;
break;
}
}
}
setTable(best_score, depth);
return(best_score);
}
と探索関数を定義して
SCORE gScore = attack(0, 50);
と、ルート局面でattack()を呼べば、証明数が50以内で必至があるかがgScoreに得られ、必至のときはその初手がgHissi_moveに得られる。
探索関数が返す評価値の意味は、深さをしきい値とした反復深化と同じで、評価値から証明数を取り出すことができる。attack()、defense()の引数として証明数のしきい値を与えるようにする。attack()では、証明数をしきい値とする多重反復深化を行い、各しきい値での展開が終了するごとに手をソートする。そのソートキーは前回しきい値で得られた各手の評価値である。深さをしきい値とした反復深化においてルートで行っている処理と同じことを、全ての攻め方ノードで行うということになる。defense()では、与えられた証明数のしきい値を満たすように、attack()に与える証明数のしきい値を決める。
tableは局面表を抽象的に表わしたものである。多重反復深化では局面表は不可欠である。実装には"Two-level Table"を使っている。ここで、「価値がある」とはより大きな証明数である、ということになる。
生成する着手、着手のソートは、深さをしきい値とした反復深化と同じである。解手順を得る処理は、第1段階の探索中の指し手ツリー生成は行っているが、第2段階の指し手ツリーからの変別解の除去は実装していない。取られるだけの無駄な手数延ばしへの対応は行っているが、コードリストには記述していない。また、これもリストには示していないが、探索する深さの上限を設定できるようにしている。その深さに達すれば、証明数のしきい値に関係無く探索を終端する。長手数の必至を見つけることが目的でないとき、深さの上限を適当に設定することで効率良く探索できる。
defense()にある、「まだ展開していない手の数」は、"深さをしきい値とした反復深化/着手生成/受け方"で説明したものと全く同じであって、局面表を使った動的評価を行っていない。動的評価を行うには「まだ展開していない手の数」の代わりに、以下に定義する「動的評価の和」を用いる。
int 動的評価の和(){
int sum = 0;
for(まだ展開していない手に対して){
if(その手を指した局面がtableに登録されている){
if(table[その局面] == -1000) return(∞);
if(table[その局面] > 0) continue;
sum += -20 - table[その局面];
} else sum++;
}
return(sum);
}
詰探索では、証明数の算出に動的評価を用いることは非常に有効に働く。しかし、必至探索では動的評価を用いると、かえって効率が悪くなった。したがって、KFEndの必至探索では動的評価を用いていない。理由はよく分からない。defense()で、手を展開する直前に逐次的に詰チェックを行うことが影響しているのかもしれない。
市販の必至問題集である資料[6]金子の7手必至から15手必至の32問をKFEndで解いた。双玉の問題は含まれていない。使用したハードウェアは、CPUがPowerPC 750(320MHz、バックサイドキャッシュ=1Mバイト)のノートパソコンである。局面表のサイズは必至、詰それぞれ、128*1024エントリ（2Mバイト）である。玉の自由度が5以上になる攻め方の手を前向き枝刈りしている。
攻め方が詰めろを選択するときに使用する詰探索の詰手数を5手、受け方が自玉が詰まされない手を選別するときに使用する詰探索の詰手数を11手として問題を解いた結果を示す。なお、パラメタとなる詰探索の手数を、この場合なら{5,11}と略記することにする。
| 実行結果 | |||
|---|---|---|---|
| No. | 必至手数 | 必至手数 | 時間(秒) |
| 69 | 7 | 7 | 0.28 |
| 70 | 7 | 7 | 0.72 |
| 71 | 7 | 7 | 1.7 |
| 72 | 7 | 7 | 0.47 |
| 73 | 7 | 7 | 0.45 |
| 74 | 7 | 7 | 7.7 |
| 75 | 7 | 7 | 2.1 |
| 76 | 7 | 7 | 12.8 |
| 77 | 7 | 7 | 4.8 |
| 78 | 7 | 7 | 0.5 |
| 79 | 7 | 9 | 125.0 |
| 80 | 7 | 11 | 28.8 |
| 81 | 7 | 7 | 0.23 |
| 82 | 7 | 7 | 3.1 |
| 83 | 9 | 9 | 0.17 |
| 84 | 9 | 9 | 0.68 |
| 85 | 9 | 9 | 6.0 |
| 86 | 9 | 9 | 6.2 |
| 87 | 9 | 9 | 5.9 |
| 88 | 9 | 9 | 0.75 |
| 89 | 9 | 9 | 4.3 |
| 90 | 9 | 9 | 0.72 |
| 91 | 9 | 9 | 2.0 |
| 92 | 9 | 7 | 0.25 |
| 93 | 9 | 9 | 20.9 |
| 94 | 11 | 11 | 4.5 |
| 95 | 11 | 9 | 2.7 |
| 96 | 11 | 11 | 10.8 |
| 97 | 11 | 11 | 71.2 |
| 98 | 11 | 11 | 5.7 |
| 99 | 15 | 15 | 28.3 |
| 100 | 15 | 15 | 300.0 |
| 平均 | - | - | 20.6 |
上表において、「No.」は問題集に記された番号、2列目の「必至手数」は問題集の解答にある作意の手数、3列目の「必至手数」はKFEndが返した結果のよる手数である。
詰手数パラメタが{5, 11}のとき、全32問を現実的な時間内に解くことができた。作意の必至手数と実行結果の必至手数が異なる問題が4問あるが、これは以下の理由による。No.79は、KFEndが解手順の末端以外で無駄な手数延ばしを行ったため、No.92、No.95は、受け方の最後の手を無駄な手数延ばしと解釈するかどうかの違いのためで、解手順そのものは同じになる。No.80は、KFEndは作意順の最終図よりまだ手が続くと解釈しており（13手必至）、早い別の必至（11手）を見つけている。これらの問題も正解とみなして良いだろう。
次に、詰手数パラメタを振ったとき実行時間がどう変化するかを調べたデータを示す。
| 受け方＼攻め方 | 3手 | 5手 | 7手 | 9手 |
|---|---|---|---|---|
| 9手 | 0.81 | |||
| 11手 | 0.61 | 1.00 | 1.50 | 2.66 |
| 13手 | 1.76 | |||
| 15手 | 4.06 |
実行時間の変化率の平均とは、詰手数パラメタ{n,m}で全ての問題を実行し、各問題の実行時間が{5,11}での実行時間の何倍か（変化率）を算出し、それを全問題について平均したものである。例えば、{5,13}の実行時間の変化率は{5,11}に比べて平均1.76倍になることが表から分かる。{3,11}でNo.93が解けなかった以外は全て解を得た。この問題集に限って言えることかもしれないが、{3,9}のような探索コストをかなり押さえた設定でも大部分の必至問題は解くことができる。
なお、これまでに示した実行時間は、"解手順を得る"で説明した第1段階に費やす時間のみで、第2段階の時間は含まれていない。しかし、これは以下の理由で問題にならない。詰手数パラメタ{5,11}で第2段階まで含めて実行時間を計測したデータの変化率の平均は、第1段階のみの{5,11}に比べて1.07倍にすぎない。すなわち、ほとんどの問題では、第2段階にかかる時間を十分小さいとみなすことができる。
詰手数パラメタを{5,11}、ルートで与える証明数のしきい値を50、探索する深さの上限を17手として問題を解いた結果を示す。
| 実行結果 | ||||
|---|---|---|---|---|
| No. | 必至手数 | 必至手数 | 時間(秒) | 変化率 |
| 69 | 7 | 7 | 3.1 | 10.9 |
| 70 | 7 | 7 | 0.72 | 1. |
| 71 | 7 | 7 | 34.1 | 20. |
| 72 | 7 | 7 | 2.5 | 5.32 |
| 73 | 7 | 7 | 0.32 | 0.704 |
| 74 | 7 | 9 | 43.9 | 5.73 |
| 75 | 7 | 9 | 11.3 | 5.43 |
| 76 | 7 | 13 | 1407 | 109. |
| 77 | 7 | 7 | 6.7 | 1.4 |
| 78 | 7 | 7 | 0.63 | 1.27 |
| 79 | 7 | X | 7200 | - |
| 80 | 7 | X | 1183 | - |
| 81 | 7 | 7 | 0.17 | 0.714 |
| 82 | 7 | 9 | 304.0 | 97. |
| 83 | 9 | 9 | 1.3 | 7.7 |
| 84 | 9 | 9 | 0.82 | 1.2 |
| 85 | 9 | 9 | 8.6 | 1.43 |
| 86 | 9 | 17 | 29.6 | 4.81 |
| 87 | 9 | 9 | 236.0 | 40.3 |
| 88 | 9 | 9 | 0.70 | 0.933 |
| 89 | 9 | 9 | 667.0 | 156. |
| 90 | 9 | 9 | 0.42 | 0.581 |
| 91 | 9 | 11 | 8.4 | 4.17 |
| 92 | 9 | 9 | 0.45 | 1.8 |
| 93 | 9 | 13 | 410.0 | 19.6 |
| 94 | 11 | 11 | 2.0 | 0.445 |
| 95 | 11 | 11 | 9.9 | 3.73 |
| 96 | 11 | 17 | 3.1 | 0.289 |
| 97 | 11 | 11 | 2.9 | 0.04 |
| 98 | 11 | 11 | 2.0 | 0.36 |
| 99 | 15 | 15 | 7.0 | 0.245 |
| 100 | 15 | 15 | 4.4 | 0.0145 |
| 平均 | - | - | 107.0 | 16.75 |
上表において、5列目の「変化率」は、実行時間が、深さをしきい値とする反復深化で詰手数パラメタ{5,11}で行った実行時間の何倍かを示す。No.79とNo.80では解を得ることができなかった。深さしきい値の反復深化と違って、実行結果の必至手数は最短手数であるとは限らない。
反復深化に比べて、変化率の平均が16.75と非常に悪くなっている。個々の問題を見ると、10個の問題で速くなっているが、20個の問題で遅くなっている。この実験結果より、KFEndで使われている証明数をしきい値とする反復深化は、深さをしきい値とする反復深化より優れた探索法であるとは言えない。
この実験で取得した全ての生データを別に示す。
KFEndの終盤におけるおおまかな処理の流れを示す。手を指すべき局面が与えられると、まず、敵玉への即詰みが無いかを詰探索で調べる。詰があればその手を指す。無いとき、敵玉への必至探索を行い、必至があれば、その必至手順を検証し、パスすればその手を指す。必至が無いか、あっても検証にパスしないとき、通常の静的評価関数を使った探索を用いて手を決定する。
必至探索は、深さをしきい値とする反復深化で行い、必至手数は5手である。攻め方の詰めろ生成に用いる詰探索の詰手数は3手（初手のみ13手、後述）、受け方の自玉が詰まされない手を選別するのに用いる詰探索の詰手数は11手に設定している。また、探索する時間に上限を設けている。1手を指すのに与えられた時間の最大1/6まで必至探索に使うようにしている。
"必至の定義"で述べたように、KFEndの必至探索が対象とする必至は強必至ではないので、結果が必至であっても必勝を保証するものではない。必至探索が返した手順の途中で、攻め方の玉に王手をかけながら必至を逃れたり、受け方の玉に詰めろがかけられた局面から攻め方の玉が詰まされてしまうということが起こる恐れがある。このような状況はそう頻繁に起こるものではないが、無視しうる程、稀であるとも言えない。この点、資料[1]飯田では比較的楽観視しているが、資料[7]山下では用心深い立場を取っている。
KFEndは必至探索で得られた必至手順（ツリー）を検証して危険を減らす戦略を取っている。強必至であることを検証できれば最も良いが、これは基本的に強必至探索を行わなければならないので現実的でない。KFEndによる数多くのセルフプレイの棋譜から、必至探索が返した手を指しても勝利できなかった局面を取り出してみると、受け方が詰めろ逃れの詰めろを指して必至を逃れるケースが多いことが分かった。3手以上の必至で、初手が相手に駒を渡す手であるときによく起こる。攻め方の玉に王手をかけながら必至を逃れるケースはほとんどなかった。前述したように、受け方は探索の中で受けに利きそうな王手を生成するので、必至探索の段階である程度除かれていると考えられる。
以上の分析よりKFEndでは、必至手順中に、受け方の詰めろ逃れの詰めろがあるかのみを検証している。これだけでも必至手順の信頼性はかなり高くなる。検証は以下のように行う。必至探索で得られた解のツリーをルートから深さ優先でスキャンしていき、受け方手番のノードで攻め方の玉に対し詰探索を行う。全ての受け方手番のノードで詰が無いとき、結果はパスになる。
KFEndは、通常の静的評価関数による探索の中で、詰めろを認識し利用している。特にルートでの詰めろは重要なので、詰めろ判定に時間をかけて、詰手数が13手の詰めろを見つけている。前述したように、必至探索での詰めろを判定するとき行う詰探索の手数は3手だが、ルートではこの情報を利用して、初手のみは詰手数が13手の詰めろを探索している。
必至探索を行って必至が見つからなかったとき、探索に費やした時間は無駄になる。しかし、必至探索の局面表を通常探索で利用することができる。通常探索中のノードで、必至の局面表を見て必至になるなら高い評価値を与える。同じように、詰探索の局面表も見ている。
(2000.9.11)