将棋の終盤において、詰めろは非常に重要な概念である。将棋プログラムにおいても、いかに詰めろを扱うかが終盤力を大きく左右する要素になる。
通常探索を行っている内部ノードで、手番プレイヤに敵玉への即詰が生じれば、そのノードの評価値は+∞にすべきである。しかし、通常探索では比較的簡単な詰みなら見つけられるが、一般には詰を認識することは難しい。将棋ではかなり大胆な前向き枝刈りが行われるので王手の多くは探索されないし、探索の深さも比較的浅いので、内部ノードに現れる詰は短手数の簡単なものでも見過ごされる場合が多い。
そこで、通常探索の内部で詰探索を行う手法が考えられる。探索関数の冒頭で敵玉への詰探索を行い、詰めば+∞の評価値を返し、詰まなければ通常の処理を行う。全ての内部ノードにおいて、十分な深さの詰探索を行なえれば良いのだが、そうはいかない。それでは詰探索に時間がかかり過ぎてしまうのだ。そこで、全てのノードでなく、詰みそうな局面だけに限定して詰探索を行うようにする。詰みそうな局面は、玉の周りの利きの数、持ち駒の種類／数などの局面の静的な条件からヒューリスティックを用いて選び出す。また、浅いところは念入りに詰を調べて、深いところではやらないようにする。
typedef Int16 SCORE;
enum TEBAN {SENTE = 0, GOTE};
enum RESULT {TUMI, FAIL};
extern SCORE evlt(TEBAN tbn); // 静的評価関数
extern RESULT tumiSearch(TEBAN tbn); // 詰探索
extern bool tumiQ(TEBAN tbn, int depth); // 現局面で詰探索を行うかを判定
int gMax_depth;
CSST gBest_move;
SCORE negaMax(int depth, TEBAN tbn){
if(tumiQ(tbn, depth) && tumiSearch(tbn) == TUMI) return(+∞);
if(depth == gMax_depth) return(evlt(tbn));
着手を生成する
SCORE best_score = -∞;
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMax(depth+1, 1^tbn);
if(score > best_score){
best_score = score;
if(depth == 0) gBest_move = その手;
}
局面を戻す
}
return(best_score);
}
という探索関数、negaMax()を定義して
gMax_depth = 5; SCORE gBest_score = negaMax(0, SENTE);
とnegaMax()を呼べば、5手読みでの最善手がgBest_moveに、その評価値がgBest_scoreに得られる。
negaMax()の強調表示しているところで詰探索を行っている。negaMax()はnega max表現でのミニマックス法をとっているが、本解説では通常探索のアルゴリズムは特に何でも良いので簡単なものにしている。evlt(TEBAN tbn)は静的評価関数である。tbnにとっての値（大きいほど手番tbnにとって有利）であり、任意の局面において、evlt(SENTE) == -evlt(GOTE)の関係がある。tumiSearch(TEBAN tbn)は、現局面において詰め方をtbnとしてtbnから先に着手しての詰探索を行い、その結果を返す。tumiQ(TEBAN tbn, int depth)は、現局面でtbnが詰探索を行うべきかを判定する。局面の静的な条件から詰む可能性が高いと思われる場合にtrueを返す。また、探索の深さも考慮され、depthが大きいとfalseを返す。
前章では、局面が詰みそうかを判定するのに、局面の静的な条件からヒューリスティックを用いているが、この判定に詰めろを利用することが非常に有力である。詰めろがかかった局面の子局面は非常に高い確率で詰む。したがって、親局面に詰めろがかかっている局面では、詰探索を必ず行うようにすればよい。探索関数を以下のように修正する。
extern bool tumeroQ(TEBAN tbn, int depth); // 現局面が詰めろであるかの詰探索を行うかを判定
SCORE negaMax(int depth, TEBAN tbn, bool mustTumi){
if((mustTumi || tumiQ(tbn, depth)) && tumiSearch(tbn) == TUMI)
return(+∞);
if(depth == gMax_depth) return(evlt(tbn));
bool tumero = 現局面に王手がかかっていない &&
tumeroQ(1^tbn, depth) && tumiSearch(1^tbn) == TUMI;
着手を生成する
SCORE best_score = -∞;
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMax(depth+1, 1^tbn, tumero);
if(score > best_score){
best_score = score;
if(depth == 0) gBest_move = その手;
}
局面を戻す
}
return(best_score);
}
追加、修正しているところを強調表示している。negaMax()の引数にフラグmustTumiを追加している。mustTumiが立っているときは、tumiQ()に関係無く必ず詰探索を行う。王手がかかっておらずtumeroQ()==trueのとき、現局面が詰めろであるかを確かめるため詰探索を行う。tumeroQ()は、tumiQ()と同じような意味で定義されている。再帰的にnegaMax()を呼ぶとき、現局面が詰めろであればmustTumiにtrueを与えて、子局面では必ず冒頭で詰探索を行うようにする。
詰めろをかけられた局面で王手をすると、相手はその王手を防ぐ手を指さなければならないので、一時的に詰めろを回避することができる。しかし、敵がその王手を防ぐ手を指した局面は、多くの場合再び詰めろがかかっているので、そこで改めて詰めろに対処しなければならない。このような詰めろを回避するための一時的な王手は複数回可能なので、探索において一種の水平線効果が生じてしまう。詰めろをかけられた局面で、王手、それを防ぐ手を繰り返して、探索の深いところまで行くと、tumeroQ()が深さの制限からtrueを返さなくなる。すると、詰めろを認識するための詰探索が行われなくなり、詰めろであるにもかかわらず詰めろでないとされる。その結果、本来は自玉が詰んでしまう手に対して詰探索が行われなくなり、そのような手の評価が高くなってしまう。言わば、一時的な王手の繰り返しによって、詰めろであることを忘れてしまったような振るまいになってしまう。この問題は、資料[1]棚瀬で具体例をあげて詳しく論じられている。この問題に対処するための準備を次章で行う。
詰めろを考慮して局面を次の3つの状態に分類する。
手が指されることによって局面が進み、それに伴って状態も変化していく。状態が遷移する様子を図1に示す。
図1で円は状態を、矢印はその状態遷移を起こす手を表わす。ある状態s1から状態s2へ遷移させる手をM(s1,s2)と表記する。状態Nでは自玉に詰めろがかかっていないが、王手がかかっている場合はある。状態Tに移るM(N,T)は詰めろで、M(T,N)は詰めろを逃れる手である。この2種類の手は王手であることはない。M(T,0)は詰めろをかけられた状態での王手で、多くの場合一時しのぎにしかならない手である。状態Oからの王手を防ぐ手はほとんどがM(O,T)になり、再び敵玉に詰めろがかかる。状態Oからの逆王手は全てM(O,N)になる。M(N,N)は詰めろでない、普通の手である。王手であってもよい。M(T,T)は詰めろ逃れの詰めろである。定義から、M(N,O)、M(O,O)という手は存在しない。また、図1では、その手を指した局面で自玉が詰まされるような手は除いている。したがって、敵玉を詰ます手も無い。
詰めろ局面での王手の問題を回避するには、親局面が状態Oのとき、現局面が詰めろであるかを必ず確かめるようにすれば良い。それは以下の探索関数で実現できる。
enum STATE {STATE_T, STATE_O, STATE_N};
const SCORE BIAS_tumero = 3000;
const int MAX_DEPTH_tumero = 5;
SCORE negaMax(int depth, TEBAN tbn, STATE statePre){
if((statePre==STATE_T || tumiQ(tbn, depth)) && tumiSearch(tbn) == TUMI)
return(+∞);
if(depth == gMax_depth) return(evlt(tbn));
bool tumero = 現局面に王手がかかっていない &&
(statePre==STATE_O || tumeroQ(1^tbn, depth)) &&
tumiSearch(1^tbn) == TUMI;
STATE state;
if(tumero) state = STATE_T;
else if(現局面に王手がかかっている && statePre==STATE_T) state = STATE_O;
else state = STATE_N;
if(state==STATE_O && depth >= MAX_DEPTH_TUMERO)
return(evlt(tbn) + BIAS_tumero);
着手を生成する
SCORE best_score = -∞;
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMax(depth+1, 1^tbn, state);
if(score > best_score){
best_score = score;
if(depth == 0) gBest_move = その手;
}
局面を戻す
}
return(best_score);
}
追加、修正しているところを強調表示している。negaMax()の引数のフラグmustTumiを、親局面の状態statePreに換えている。親局面の状態が状態Tのとき、tumiQ()に関係無く必ず詰探索を行う。親局面の状態が状態Oのとき、現局面が詰めろであるかを確かめるための詰探索を、tumeroQ()に関係無く必ず行う。前章で示した状態の定義に従って現局面の状態を決定し、それを再帰的にnegaMax()を呼ぶときに引数として与えている。さらに、現局面の状態が状態Oのとき、深さがMAX_DEPTH_tumero以上になれば終端するようにしている。詰めろをかけられた局面での王手はかなり多く続くことがしばしばある。この場合、探索の深いところまで詰探索を行うことになってコストがかかりすぎる。状態Oで終端されるとき、返す評価値にBIAS_tumeroだけボーナスを与えるようにする。BIAS_tumeroはかなり大きな値だが、詰の評価に比べると十分小さい値である。これによって、深いところでは状態Tから一時しのぎの王手を行うと、評価値で大きなペナルティーを受ける。したがって、他に詰めろを逃れる手があるときは一時しのぎの王手を行わない。
詰めろがかかった局面において、その詰めろの詰手順をtとする。その詰めろ局面の子局面に詰が生じたとき、その詰手順は手順tと同じであることが多い。この性質を利用して、詰めろ局面の子局面における詰探索に、手順tを利用して詰探索を高速化することができる。探索関数を次のように修正する。
struct TUMI_RECORD {詰手順、詰手数、実行時間};
extern RESULT tumiSearch(TEBAN tbn, TUMI_RECORD *in, TUMI_RECORD *out); // 詰探索
SCORE negaMax(int depth, TEBAN tbn, STATE statePre, TUMI_RECORD *rec){
if((statePre==STATE_T || tumiQ(tbn, depth)) && tumiSearch(tbn, rec, null) == TUMI)
return(+∞);
if(depth == gMax_depth) return(evlt(tbn));
TUMI_RECORD record, *next_rec;
bool tumero = 現局面に王手がかかっていない &&
(statePre==STATE_O || tumeroQ(1^tbn, depth)) &&
tumiSearch(1^tbn, rec, &record) == TUMI;
STATE state;
if(tumero)
{state = STATE_T; next_rec = &record;}
else if(現局面に王手がかかっている && statePre==STATE_T)
{state = STATE_O; next_rec = rec;}
else
{state = STATE_N; next_rec = null;}
if(state==STATE_O && depth >= MAX_DEPTH_TUMERO)
return(evlt(tbn) + BIAS_tumero);
着手を生成する
SCORE best_score = -∞;
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMax(depth+1, 1^tbn, state, next_rec);
if(score > best_score){
best_score = score;
if(depth == 0) gBest_move = その手;
}
局面を戻す
}
return(best_score);
}
追加、修正しているところを強調表示している。構造体TUMI_RECORDを定義して、これに詰探索で利用する情報を記録する。tumiSearch()は引数に2つのTUMI_RECORDへのポインタを追加している。inは詰探索を行うときに高速化のために利用するもので、outは詰探索を行った結果得られた情報を記録するためのものである。与えられたポインタがnullのときは、情報の利用、記録を行わない。negaMax()の引数にTUMI_RECORDへのポインタを加えて、子孫局面の探索のために詰探索の情報を伝播する。冒頭の詰探索において、negaMax()に引数として与えられた情報recを利用する。現局面が詰めろであるかを確かめるための詰探索でもrecを利用し、さらにその結果から得られる情報をrecordに記録する。再帰的にnegaMax()を呼ぶときに引数として与えるTUMI_RECORDへのポインタは、現局面の状態によって決定される。状態Tのときは、recordに記録された詰めろの情報を与える。状態Oのときはrecをそのまま与える。状態Nのときは情報は何もないのでnullを与える。このように詰の情報を伝播することによって、詰めろをかけられた局面からの王手に対しても、詰の情報を有効に利用できる。
TUMI_RECORDには、詰手順、詰手数、実行時間が記録されるが、これをどのように詰探索で利用するかを簡単に説明する。詰手順は、指し手を表わす構造体CSSTのツリーとして表わされる。それを手繰るようにツリー上の手を優先して展開して探索する。また、記録された詰手数に探索の深さを制限し、記録された時間が経過すると探索を終了するようにする。こうすることによって、記録された手順と同一の手順で詰む場合は確実に詰ますことができ、詰まない場合も探索に費やす時間を押さえることができる。
(2000.9.18)