図2
チェスライクゲームでは駒を取ることによって局面の静的評価値が大きく変化するため、探索の末端で静止探索を行うのが一般的だ。KFEndも行っているが、以下の点で静止探索はより重要な意味がある。
これらの点を効果的に行うために、「脅威」を考慮した静止探索を行っている。
静止探索の基本的な探索関数は以下のようになる。
リスト 1
int gMax_qui_depth;
SCORE negaMaxQui(SCORE alpha, SCORE beta, int depth){
SCORE best_score = 現局面の静的評価値;
if(depth == gMax_qui_depth || best_score >= beta)
return(best_score);
if(alpha > best_score) best_score = alpha;
着手（取る手のみ）を生成する
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMaxQui(-beta, -best_score, depth+1));
if(score > best_score) best_score = score;
局面を戻す
if(best_score >= beta) break;
}
return(best_score);
}
一般的なやり方では、探索の末端で通常の探索関数の代わりに、適当にgMax_qui_depthを設定してnegaMaxQui()を呼ぶ。negaMaxQui()は以下の2つの特徴がある。
局面の評価値を大きく変化させる可能性の高い取る手のみを探索することで、探索量を減らしながら明らかに重要な手順は見逃さないという狙いがある。取る手以外にも重要な手、例えば、成る手を加えることも有力だ。KFEndは資料[1]小谷を参考にして、歩が成る手を加えている。現局面の静的評価値を選択することは、取る手以外の手を選択したときはそれ以上探索しないということを意味していると考えられる。
静止探索の中に王手がかけられた局面が現れたときの扱いを考える。1つの方法として、何もしないことも可能であると思う。しかし、これを行うと詰の局面を詰と認識できない。KFEndでは、王手の局面では全ての合法手を生成するようにしている。そして、王手の局面では、現局面の静的評価値を選択することを許していない。したがって、合法手が無いときは正しく詰の評価を得るようなる。リスト1を以下のように修正する。
リスト 2
SCORE negaMaxQui(SCORE alpha, SCORE beta, int depth){
if(depth == gMax_qui_depth) return(現局面の静的評価値);
SCORE best_score;
if(現局面に王手がかかっている){
着手（全ての合法手）を生成する
if(生成した手が無い) return(-∞);
best_score = alpha;
} else {
best_score = 現局面の静的評価値;
if(best_score >= beta) return(best_score);
if(alpha > best_score) best_score = alpha;
着手（取る手のみ）を生成する
}
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMaxQui(-beta, -best_score, depth+1));
if(score > best_score) best_score = score;
局面を戻す
if(best_score >= beta) break;
}
return(best_score);
}
今まで述べてきたものは、全ての取る手を生成しているが、これをさらに限定して、敵が直前に指した駒を取る手のみを生成する、というやり方が考えられる。これだと、局面の評価は不正確になるが、探索量は大きく減る。そこで、リスト2で示した静止探索の末端で、さらに着手を限定した探索を行うようにする。まず、新しい探索関数negaMaxQui_End()を以下のように定義する。
リスト 3
SCORE negaMaxQui_End(SCORE alpha, SCORE beta){
if(現局面に王手がかかっている){
着手（全ての合法手）を生成する
if(生成した手が無い) return(-∞);
生成した手から、直前に指された駒を取る手のみ残す
} else {
着手（直前に指された駒を取る手のみ）を生成する
}
SCORE best_score = 現局面の静的評価値;
if(best_score >= beta) return(best_score);
if(alpha > best_score) best_score = alpha;
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMaxQui_End(-beta, -best_score));
if(score > best_score) best_score = score;
局面を戻す
if(best_score >= beta) break;
}
return(best_score);
}
このnegaMaxQui_End()を使って、リスト2のnegaMaxQui()を以下のように修正する。
リスト 4
SCORE negaMaxQui(SCORE alpha, SCORE beta, int depth){
if(depth == gMax_qui_depth)
return(negaMaxQui_End(alpha, beta));
”以下はリスト2と同じ”
}
リスト2で、静的評価関数の代わりにnegaMaxQui_End()を使う形にしたのがリスト4である。negaMaxQui_End()とnegaMaxQui()の違いは、生成する手と王手のかかった局面での処理である。negaMaxQui_End()は、王手のかかった局面でも、直前に指された駒を取る手のみを展開する。しかし、その局面が詰であるかは確かめている。
なお、コードリストには書いていないが、negaMaxQui()は局面表を用いている。negaMaxQui_End()では用いていない。
図2
図1、図2の局面（いづれも先手番）を比べると、図2の方が先手にとって不利である。先手は放っておくと次に△14歩と金を取られるので、それを防がなければならず手の選択が制限される。図2の先手は駒取りの脅威を受けていると言える。このような脅威を評価に反映させるため、静的評価関数に脅威を評価する要素を設けるというやり方が考えられる。例えば、味方の駒が敵の利きの上にあるときペナルティーを与えるようにする。しかし、KFEndではそのような方法は取っておらず、静止探索の中で脅威の大きさを探索によって評価している。
探索関数で、現局面の静的評価値を選択したとき、脅威があればその値をマイナス方向に修正する。リスト4を次のように修正する。
リスト 5
SCORE negaMaxQui(SCORE alpha, SCORE beta, int depth){
if(depth == gMax_qui_depth)
return(negaMaxQui_End(alpha, beta));
SCORE best_score;
if(現局面に王手がかかっている){
着手（全ての合法手）を生成する
if(生成した手が無い) return(-∞);
best_score = alpha;
} else {
best_score = 現局面の静的評価値;
best_score = modifyByThreat(best_score);
if(best_score >= beta) return(best_score);
if(alpha > best_score) best_score = alpha;
着手（取る手のみ）を生成する
}
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMaxQui(-beta, -best_score, depth+1));
if(score > best_score) best_score = score;
局面を戻す
if(best_score >= beta) break;
}
return(best_score);
}
強調表示した1行を加えただけである。関数modifyByThreat()が、探索によって脅威を評価しbest_scoreをマイナス方向に修正する。
modifyByThreat()の動作を簡単に言えば以下のようになる。手番プレイヤはパスをして、敵側の取る手を生成する。その各手に対して静止探索し、その手のうちで最小（敵にとっては最大）になる評価値Vを得る。Vが現局面の静的評価値に比べて小さければ、modifyByThreat()はVの大きさに応じて現局面の静的評価をマイナス方向に修正する。コードは次のようなる。
リスト 6
int gMonoThreatC;
SCORE modifyByThreat(SCORE static_value){
敵の着手（取る手のみ）を生成する
SCORE threat1 = static_value;
for(生成した各手に対して){
その手で局面を進める
SCORE score = negaMaxQui_End(-∞, threat1));
局面を戻す
if(score < threat1) threat1 = score;
}
return(static_value - (static_value - threat1)/gMonoThreatC);
}
敵の取る手のそれぞれに対して、negaMaxQui_End()を呼んで静止探索値を得る。最大の脅威（値としては最小）がthreat1に得られる。探索により得られた値がstatic_valueより大きいときは無視するので、threat1の初期値にはstatic_valueを与えればよい。threat1と現局面の静的評価値static_valueの差に比例した値をstatic_valueから減じた値を返す。gMonoThreatCはパラメタで、小さくすれば脅威の効果が大きく反映される。
ある局面において同時に2つの脅威が存在するとき、その脅威の影響は非常に大きい。将棋は1手づつしか指せないので、2つの脅威を同時に防ぐことは難しいからだ。
図4
図3、図4の局面（いづれも先手番）を比べると、図4の方が先手にとって不利である。図3では55の銀を逃げればよいが、図4では銀を逃げても△87飛成と竜を作られてしまう。図4では△55飛と△87飛成の2つの脅威がある。
今まで述べてきた静止探索でこれらの局面を評価すると、図4の方が不利であることは分からない。図4の局面でnegaMaxQui()を呼ぶとする。先手に取る手は無いので現局面の静的評価値に脅威を考慮した値が返される。最大の脅威は△55飛と銀を取られることなので、(銀損分の評価値)/gMonoThreatCが脅威によって修正されるマイナス値である。これは図3でも全く変わらない。図4の方が先手にとって明らかに不利であるにもかかわらず、図3と図4の局面の静止探索値はほとんど同じに評価されてしまう。
2つの脅威を評価するために、リスト6のmodifyByThreat()を以下のように修正する。
リスト 7
int gMonoThreatC, gDoubleThreatC;
SCORE modifyByThreat(SCORE static_value){
敵の着手（取る手のみ）を生成する
SCORE threat1 = static_value, threat2 = static_value;
for(生成した各手に対して){
その手で局面を進める
SCORE score = negaMaxQui_End(-∞, threat2));
局面を戻す
if(score < threat1) {threat2 = threat1; threat1 = score}
else if(score < threat2) {threat2 = score;}
}
SCORE res1 = static_value - (static_value - threat1)/gMonoThreatC;
SCORE res2 = static_value - (static_value - threat2)/gDoubleThreatC;
if(res1 < res2) return(res1); else return(res2);
}
最大の脅威(threat1)の他に2番目の脅威(threat2)を記録する。そして、それぞれの脅威に対してstatic_valueを修正した値(res1、res2)を算出し、小さい方を返す。2番目に大きい脅威を問題にするのは、脅威が複数ある局面でもっとも単純な着手は最大の脅威を防ぐことで、そのとき2番目の脅威が現実になるからである。res2を算出するのに使うパラメタgDoubleThreatCはgMonoThreatCより小さくして、2番目の脅威の効果をより大きく反映するようにする。中盤以降では、gMonoThreatC = 6、gDoubleThreatC = 2 と設定している。
図6
図5、図6の局面（いづれも先手番）を比べると、図6の方が先手にとって不利である。両局面とも飛を取られる脅威を受けているが、図5では飛が逃げることができ、図6では逃げることができない。しかし、これはこれまで述べた静止探索では区別できない。このように価値の高い駒が「詰んでいる」局面は、単純には防ぐことができないので、2つの脅威と同じように脅威の効果をより大きく反映すべきである。そのために、リスト7のmodifyByThreat()を以下のように修正する。
リスト 8
SCORE modifyByThreat(SCORE static_value){
敵の着手（取る手のみ）を生成する
SCORE threat1 = static_value, threat2 = static_value;
for(生成した各手に対して){
その手で局面を進める
SCORE score = negaMaxQui_End(-∞, threat2));
局面を戻す
if(score < threat1) {threat2 = threat1; threat1 = score}
else if(score < threat2) {threat2 = score;}
if(score >= threat2) continue;
if(取られる駒が敵の利きの無いますに移動する手がある) continue;
取られる駒が移動する全ての手を生成する
SCORE max_score = score;
for(生成した各手に対して){
if(その手が駒を取る手である) continue;
その手で局面を進める
SCORE score = -negaMaxQui_End(-threat2, -max_score));
局面を戻す
if(score > max_score){
max_score = score;
if(max_score >= threat2) break;
}
}
if(max_score < threat2) threat2 = max_score;
}
SCORE res1 = static_value - (static_value - threat1)/gMonoThreatC;
SCORE res2 = static_value - (static_value - threat2)/gDoubleThreatC;
if(res1 < res2) return(res1); else return(res2);
}
ここでやっていることは、取られる駒の逃げる場所があるかを調べ、無い場合は取られる駒が移動することで生じる取り合いを探索で評価し、それをもとに最大の逃れられない脅威を決定する、ということだ。以下、詳しく説明する。2番目の脅威と、最大の逃れられない脅威のうちより大きい方の脅威を変数threat2に記録するようにする。まず、敵の取る手によって取られる駒が逃げる場所（敵の利きの無います）があるかを調べる。もしあれば、逃れられない脅威にはならない。取られる駒の移動可能な全てのますに敵の利きがあるとき、取られる駒が移動する全ての手を生成する。その各手に対して局面を進め、negaMaxQui_End()で探索する。その最大の評価値(max_score)が逃れられない脅威となる。このようにして敵の取る各手に対して逃れられない脅威を求め、2番目の脅威と合わせて、最大の（値としては最小）脅威がthreat2に得られる。
まとめると、リスト8にあるmodifyByThreat()は、
を認識し、現局面の静的評価をマイナス方向に修正する。また、2、3の場合を1と区別してより大きな影響を評価値に与える。
ABC探索／KFEndへの適用／前向き枝刈りで述べたが、KFEndでは、探索関数で生成した手を静止探索値でソートして、その上位の手を残し下位の手を捨てている。通常探索の探索関数は次のようになる。
リスト 9
int gMax_depth;
SCORE negaMax(int depth, TEBAN tbn){
gMax_qui_depth = 3;
if(depth == gMax_depth) return(negaMaxQui(-∞, +∞, 0));
着手を生成する
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMaxQui(-∞, +∞, 0);
その手のキー = score;
局面を戻す
}
生成した手をキーでソートして、上位n手のみを残す
SCORE best_score = -∞;
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMax(depth+1, 1^tbn);
if(score > best_score) best_score = score;
局面を戻す
}
return(best_score);
}
ここでは、通常探索のアルゴリズムは特に関係無いので簡単なものにしている。生成した各手に対して局面を進め、深さ3手の静止探索を行って評価値を求める。その評価値をキーとしてソートし上位の手のみを残す。残す手の数は深さによって変えているが、10手くらいである。
今まで解説してきた静止探索を使って、リスト9のような前向き枝刈りを行うとどのようなことになるかを考える。まず、単純な駒の取り合いで駒得する取る手が残される。そして、単純な駒得する取る手を防ぐ手（逃げたりひもを付けたりする手）も残される。言うまでもなく、将棋においては駒の損得は非常に重要で、このような手を見逃すことは負けに直結する。簡単な駒得の手を確実に残すことは、将棋プログラムで第一に考えなければならないと思う。次に、敵に脅威を与える手が残される。敵が受けなければ駒を取って駒得できるような手である。特に2つの脅威、逃れられない脅威を与える手は評価が高くなるので上位で残される。
以上のような、取り、取りを防ぐ手、取りの脅威を与える手を、直接的な手と呼ぶことにする。直接的な手を通常探索の候補手として残すことによって、攻めの基本的な手順を探索することができる。攻めが決まる基本的な手順は、取りと取りをかける手で相手を追い込み、最後に2つの脅威を実現して受け無しにすることである。生成する手は深さによらず、どの深さでも生成した全ての手の静止探索値を得るので、通常探索の深いところでも直接的な手を確実に残すことができる。このことによって、直接的な手が続く限り長手数の読みが可能である。KFEndは、直接的な手を深く読むことで局面の戦術的な評価を正確に行うことをめざしたプログラムである。
取りの脅威を与える手を残すことに関して、静止探索値が上位の手を残すということでは不十分な場合がある。それは敵に脅威を与えるが、取り合いで駒損になる手が刈られてしまう点である。このような手は駒損するので多くの場合最善手になることはないのだが、ときとして非常に有効であることがある。例えば、大駒を切る手や歩の叩きである。駒を交換する手はたとえ駒損であっても局面を大きく変化させるので有効な攻めにつながる可能性がある。また、歩を叩いたり突き捨てたりするのは手筋によく現れる。このような手を全て刈ってしまうのはまずい。そこで、静止探索値が上位になる手以外にも別に基準を設けて残すようにしている。ひとつは、取る手を最低5つは残すようにする。こうすると、序中盤ではほとんど取る手は残すことになるが、取る手の数は多くないので探索コストの増加はそれほどでもない。さらに、特定の条件を満たす手を少数残している。歩の叩きなど、広い意味での手筋に相当する手を検出している。これは探索のアルゴリズムに手筋の知識を融合させる機構の一部である（この機構自体は試みの段階で有効かどうかはまだ分からない）。
駒の損得に関係する手、すなわち戦術的な手以外にも、当然ながら重要な手は存在する。しかし、KFEndではそのような手を残すために特に注意を払っていない。ただ、評価値の高い手を残すので、静的評価関数で考慮している要素は反映される。例えば、評価関数に玉の安全度という項目があるので、敵玉の安全度を下げたり自玉の安全度を上げる手が上位に来る傾向にある。
(2000.12.8)