KFEndは探索アルゴリズムとしてABC探索を採用している。ABC探索とは、Davit A.McAllesterとDeniz Yuretがweb上に公開した論文である資料[1]McAllesterで発表された一種の縦型探索である。以下の特徴がある。
本解説ではまず準備として、nega max表現でのalpha-betaアルゴリズムの探索関数をC++ライクな疑似コードで書く。ここで古典的な縦型探索のアルゴリズムを確認しておく。この後、ABC探索の探索関数の疑似コードを示してその動作を説明する。最後に、ABC探索をKFEndに適用する上で考慮したことを述べる。
本解説はABC探索のアルゴリズムを説明することが目的だが、その前に従来のalpha-betaアルゴリズムを記述しておく。ABC探索は古典的な縦型探索の拡張になっていると考えることができ、両者は共通する部分が多い。アルゴリズムは"基本データ構造"で解説したデータ構造を用いて、C++ライクな疑似コードで記述する。
なお資料[1]McAllesterに習って、ABC探索でない従来の、深さをしきい値とする縦型探索に対して「古典的」(classical)という表現を用いる。
int gMax_depth;
CSST gBest_move;
SCORE negaMax(SCORE alpha, SCORE beta, int depth){
if(depth == gMax_depth) return(現局面の静的評価値);
着手を生成する
SCORE best_score = alpha;
for(生成した各手に対して){
その手で局面を進める
SCORE score = -negaMax(-beta, -best_score, depth+1));
if(score > best_score){
best_score = score;
if(depth == 0) gBest_move = その手;
}
局面を戻す
if(best_score >= beta) break;
}
return(best_score);
}
という探索関数、negaMax()を定義して
gMax_depth = 5; SCORE gBest_score = negaMax(-infinity, +infinity, 0);
とnegaMax()を呼べば、5手読みでの最善手がgBest_moveに、その評価値がgBest_scoreに得られる。これはよく知られたnegaMax表現でのalpha-betaアルゴリズムである。
negaMax()をKFEndの実装を反映してさらに細かく定義してみる。
int gMax_depth;
CSST gBest_move;
enum TEBAN {SENTE = 0, GOTE};
extern SCORE evlt(TEBAN tbn); // 静的評価関数
SCORE negaMax(SCORE alpha, SCORE beta, int depth, TEBAN tbn){
if(depth == gMax_depth) return(evlt(tbn));
CSST head;
着手を生成して、headに付ける
for(CSST *sst=head.link2; sst!=null; sst=sst->link2){
*sstで局面を進める
sst->key = evlt(tbn);
局面を戻す
}
headに属する手のリストをkeyの値によってソートする
SCORE best_score = alpha;
for(CSST *sst=head.link2; sst!=null; sst=sst->link2){
*sstで局面を進める
SCORE score = -negaMax(-beta, -best_score, depth+1, 1^tbn);
if(score > best_score){
best_score = score;
if(depth == 0) gBest_move = *sst;
}
局面を戻す
if(best_score >= beta) break;
}
return(best_score);
}
上のコードリストを説明しよう。negaMax()の最後の引数tbnは、negaMax()が呼ばれる局面での手番である。引数depthとは、depthが偶数（奇数）のときtbnはmax（min）プレイヤであるという関係がある。evlt(TEBAN tbn)は静的評価関数である。手番tbnにとっての値（大きいほど手番tbnにとって有利）であり、任意の局面において、evlt(SENTE) == -evlt(GOTE)の関係がある。生成された着手はheadに図1に示すように付けられる。
headはこの手のリストを管理するためのリストヘッドである。全ての手に対してメンバkeyに、その手で進めた局面における静的評価値を設定する。その後、keyをキーにしてソートする。このように手を展開する前にある基準でソートして、なるべく高い評価値が得られると予想される手から先に展開することは、一般的に行われる。上のコードリストでは、その基準として静的評価値を用いている。
KFEndの実装をもとにABC探索のアルゴリズムを説明して行く。ただし、KFEndの実装そのものではなく説明のために省略、簡略化している。また、アルゴリズムの一般性を損なうことなく記述している。
古典的探索では深さが探索の終端を決めるしきい値であるのに対して、ABC探索では共謀深さをしきい値として探索を終端する。大きな枠組みで見ると、古典的探索とABC探索の違いはここだけである。古典的探索関数は、コードリストにあるように冒頭で、depth == gMax_depthを条件に終端している。この条件をABC探索の終端条件を判定する、bool terminate()なる関数に置き換えれば、ABC探索の探索関数になる。コードリストを以下に示す。
int gMax_cdepth[2]; // 共謀深さのしきい値 [先手|後手]
CSST gBest_move;
enum TEBAN {SENTE = 0, GOTE};
extern SCORE evlt(TEBAN tbn); // 静的評価関数
extern bool terminate(SCORE alpha, SCORE beta, SCORE score, TEBAN tbn, CSST *head);
SCORE
negaMax(SCORE alpha, SCORE beta, int depth, TEBAN tbn, CSST *pmove, CSST *phead){
if(terminate(-beta, -alpha, pmove->key, 1^tbn, phead))
return(-pmove->key);
CSST head;
head.link1 = phead;
着手を生成して、headに付ける
for(CSST *sst=head.link2; sst!=null; sst=sst->link2){
*sstで局面を進める
sst->key = evlt(tbn);
局面を戻す
sst->searching = false;
}
headに属する手のリストをkeyの値によってソートする
SCORE best_score = alpha;
for(CSST *sst=head.link2; sst!=null; sst=sst->link2){
*sstで局面を進める
sst->searching = true;
SCORE score = -negaMax(-beta, -best_score, depth+1, 1^tbn, sst, &head);
sst->searching = false;
if(score > best_score){
best_score = score;
if(depth == 0) gBest_move = *sst;
}
局面を戻す
if(best_score >= beta) break;
}
return(best_score);
}
強調表示してある部分が古典的探索関数に追加、あるいは修正したところである。終端のしきい値は共謀深さ、gMax_cdepth[]になる。先手用、後手用の2つある。これはterminate()の内部で使用される。negaMax()は、terminate()に与える引数のために、局面を進めた手とリストヘッドへのポインタを引数に加えている。また、各深さでのリストヘッドをlink1を使ってつないでいる。展開中の手に対してsearchingフラグを立てる（"基本データ構造"におけるCSSTの定義に、bool searchingをメンバとして追加しておくことにする）。
ルート局面（この例では先手番とする）で下のようにnegaMax()を呼んで最善手を得る。
gMax_cdepth[SENTE] = gMax_cdepth[GOTE] = 20; SCORE gBest_score = negaMax(-infinity, +infinity, 0, SENTE, null, null);
ここではgMax_cdepth[SENTE]とgMax_cdepth[GOTE]を同じ値にしているが、一般には異なった値にしても良い。
関数terminate()は以下のように定義される。
// 1つの深さでの共謀深さの上限を設定する
int SFunc(int cnt){
if(cnt > 5) return(5);
return(cnt);
}
// 共謀深さの算出
int cnspDepth(SCORE score, CSST *head){
CSST *hd, *sst;
int cnt, cDepth = 0;
for(hd = head; hd; ){
cnt = 0;
for(sst = hd->link2; sst!=hd; sst = sst->link2)
if(!sst->searchimg && sst->key > score) cnt++;
cDepth += SFunc(cnt);
if(hd->link1) hd = hd->link1->link1;
else break;
}
return(cDepth);
}
const SCORE Delta = 50;
bool terminate(SCORE alpha, SCORE beta, SCORE score, TEBAN tbn, CSST *head){
if(head == null) return(false);
if(score >= beta)
return(cnspDepth(beta - Delta, head) >= gMax_cdepth[tbn]);
else if(score <= alpha)
return(cnspDepth(-alpha - Delta, head->link1) >= gMax_cdepth[1^tbn]);
else
retuen(cnspDepth(score - Delta, head) >= gMax_cdepth[tbn] &&
cnspDepth(-score - Delta, head->link1) >= gMax_cdepth[1^tbn]
);
}
terminate()の説明を行う。初めに、negaMax()内でterminate()が呼ばれるとき渡される引数、alpha, beta, score, tbnは、深さがdepth-1での手番に対しての値になっていることに注意する必要がある。scoreは、pmoveを指した局面でのtbnにとっての評価値で、negaMax()内ではpmove->keyで与えられる。これは、深さdepth-1でソートされるときに設定されている。scoreがαβウインドウの中か外かによって、終端の条件が異なる。まず、ウインドウの中の場合を見る。cnspDepth()は共謀深さを与える関数であるので、終端の条件は、tbn側の共謀深さ>=tbn側の共謀深さのしきい値、かつ、1^tbn側の共謀深さ>=1^tbn側の共謀深さのしきい値となる。先手、後手に対してそれぞれ条件があり、その両者がともに成立しないと終端しないのが特徴である。これに対し、scoreの値がαβウインドウの外にあるときは、片方だけの条件が成立するだけで終端する。よって、より終端しやすい。さらにcnspDepth()に渡されるscoreの値が小さくなることも、終端しやすくなることに貢献する。
次に、cnspDepth()の説明を行う。例をあげよう。図2は、depth==5でnegaMax()が呼ばれたときのリストヘッドとそれに属する手を表わしたものである。
四角はリストヘッドで、円は手である。link1によるつながりを縦の矢印、link2を横の矢印で表わす。便宜的に、先手はヘッドから右に、後手は左に向って手を描いている。現在、depth==4で手Mを展開して、depth==5のnegaMax()の冒頭でterminate()を呼んだところである。手Mのkeyはvであるとし、手Mの属するヘッドをHとする。cnspDepth()における外側のforループはヘッドを1つおきにスキャンして行くことに注意すると、cnspDepth(v-Delta, H)は、
Σ全ての先手のヘッドに対してSFunc(k) : kはそのヘッドに属する手の中で、v-Deltaより大きいkeyを持ち、かつ、展開中でない手の数
となる（Σは和を表わす記号である）。また、cnspDepth(-v-Delta, H->link1)は、
Σ全ての後手のヘッドに対してSFunc(k) : kはそのヘッドに属する手の中で、-v-Deltaより大きいkeyを持ち、かつ、展開中でない手の数
となる。両者をまとめて、
探索中の局面pにおける手番tの共謀深さ(conspiracy depth)は、 全ての手番tのヘッドに対して ΣSFunc(k) : kはそのヘッドに属する手の中で、(手番tにとっての局面pの評価値)-Deltaより大きい評価値を持ち、 かつ、展開中でない手の数 である
と定義できる。
関数SFunc()は、1つの深さでの共謀深さの寄与に上限を設けるためのものである。一般には、任意の単調増加関数で良い。なお、資料[1]McAllesterでは、SFunc(x)=xのときを共謀深さと言い、それ以外の場合を調節された共謀深さ(adjusted conspiracy depth)と呼んでいるが、本解説ではこの場合も単に共謀深さとする。
共謀深さは、探索の先端ノードの評価値と、展開中の手の兄弟手の評価値によって決定される。深く探索する程増加する傾向にあるが、先端ノードの評価値は探索中に変化するので、単調に増加するとは限らない。 手番tの共謀深さは、展開中の手の兄弟手の評価値に対して、先端ノードのtにとっての評価値が大きい程、小さくなる。共謀深さが小さいと、設定されたしきい値になかなか達しないので、探索が深くなる。まとめると以下のようになる。
展開中の手の兄弟手の評価値に対して、先端ノードの評価値が大→共謀深さが小→探索が深くなる （展開中の手の兄弟手の評価値に対して、先端ノードの評価値が小→共謀深さが大→探索が浅くなる）
このABC探索の性質は以下のように解釈することができる。兄弟手の評価値に対して先端ノードの評価値が大きいということは、その先端ノードへ到る手順が最善手順になる可能性が高いことになる。すると、もしその先端ノードの評価が誤りで本当はもっと低い評価しか得られない局面であったとすれば、ルート局面の評価を大きく誤る恐れがある。したがって、そのような先端ノードではそこで探索を止めずにさらに深く探索して、より正確な評価を得ようとするのである。反対に、兄弟手の評価値に対して先端ノードの評価値が小さいときは、他に良さそうな手が多くあるので、その先端ノードへ到る手順が最善手順になる可能性が低い。よって、そのような先端ノードでは早めに探索を打ち切って、その分他の有力な手を探索する。このような性質を一言で言うと、「強制された手順は深く探索する」ということになる。
ABC探索は興味深い性質を持った探索アルゴリズムだが、実際のプログラムに適用するにあたっては工夫が必要だ。KFEndでABC探索を採用するにあたって考慮した点を述べる。
今までの解説では、共謀深さを算出するのに静的評価値を用いている。この静的評価値の代わりに静止探索の評価値を用いることが、資料[1]McAllesterで提案されており、KFEndではそのようにしている。evlt()を静的評価関数としているが、これを修正して、evlt(TEBAN tbn)を、静止探索して得られるtbnにとっての評価値と解釈すれば良い。evlt()は内部で静止探索を行っていると考える。
静止探索について簡単に説明すると、各ノードで手番プレイヤが、そこで探索を終端してそのノードの静的評価値を取るか、駒を取る手を展開して得られる評価値を取るかの選択(stand-pat or capture)を持った探索である。将棋、あるいはチェスライクゲームでは、駒を取ることによって静的評価値が大きく変化する。よって、静的評価値をもとに共謀深さを算出するのは適当でなく、より正確な静止探索値を用いる方が良い。
将棋は平均分岐因子が大きいので前向き枝刈りを行うのが普通である。KFEndはnegaMax()で生成した手を静止探索値でソートしているが、その上位の手を残し下位の手を捨てている。深さ別に残す手の数を決めていて、
| 1手目 | 2〜8手目 | 9手目以降 |
|---|---|---|
| 30手 | 10手 | 5手 |
である。静止探索値が低くても、ある条件を満たす手（例えば取る手）は上表の手の数に加えて少数残している。
静止探索値が上位の手を候補としているので、単純に駒得になる手やそのような手を防ぐ手は確実に展開される。また、このような直接的な手によって構成される手順は、「強制された手順」でありABC探索では深く探索することができる。したがってKFEndは、駒の取り合いを中心とした手順を深く読むことで、局面の正確な戦術的評価を得ることが期待できる。
1つの深さでの共謀深さの上限を設定するSFunc()は、先にコードリストで示したものを用いている。上限を5にして、5以下では0からリニアに増加していく。
ルートにおいて共謀深さをしきい値とする反復深化を行っている。以下のような工夫をしている。ルートにおいて、ある手がある共謀深さのしきい値で探索して得られた評価値を、その手のkeyに設定する。その共謀深さのしきい値での探索が終了した後、手をソートする。すると、次の共謀深さのしきい値で探索するときには、共謀深さのルートにおける寄与は、静止探索値ではなく前回の共謀深さのしきい値での探索で得られた評価値を用いて算出されることになる。このようにすると、より正確な評価値を用いて共謀深さが計算される。ただし、これを行うにはα-βウインドウの問題がある。すなわち、最善手の評価値は正確だが、2番目以降の手の評価値は上限を与えるだけで正確な値ではない。そこで、ルートから呼ぶ探索関数に与えるベータを少し大きくする。これによってα-βウインドウの幅を広げた範囲において評価値が正確になる。もちろん、これによってalpha-betaアルゴリズムの後ろ向き枝刈りの効率が悪くなってしまうデメリットはある。
また、ABC探索ではα-βウインドウが広い程、探索が終端しにくい性質があるがあるので、初めに展開する手は2番目以降に展開する手に比べて、探索量が極端に多くなってしまう現象が現れることがある。前述のようにルートでα-βウインドウをルーズにすることは、この現象を緩和することにも役立つ。
先に示したABC探索のnegaMax()によれば、生成した手の全ての静止探索値を得ることになる。KFEndは全合法手ではないもののかなり多くの手を生成するので、その全ての手に対して静止探索を行うのは多くの実行時間を消費する。計測したことはないのだが、典型的な中盤では全消費時間のほとんどを静止探索に費やしていて、それ以外の処理はおそらく2、3%に過ぎないだろう。
深さd、手番tで呼ばれたnegaMax()で、手を生成した後、各手の静止探索値を求める処理を行っているとする。このとき、全ての手の静止探索値を求める前に、深さd+1のnegaMax()の冒頭で探索が終端することが分かることがある。その条件は、ある1つの手の静止探索値がbeta以上であり、かつ、手番tの共謀深さがしきい値に達していることである。この条件がいったん満たされれば、残りの手の静止探索値がどのようになっても、深さd+1で必ず終端し、評価値はbeta以上になる。
このことよりKFEndでは、negaMax()の各手の静止探索値を求める処理において、上の条件をチェックして成立すればただちに終端するようにしている。前述のように静止探索は非常にコストがかかるので、これは非常に実行速度の向上に役立つ。ABC探索には必須の処理だろう。
negaMax()で生成した手の静止探索値を得るときに行う静止探索において、α-βウインドウの設定をどう行うべきか。-∞、+∞にするのが正確な値が得られて簡単だが、実行時間がかかる。そこで、negaMax()の引数に渡されたalpha、betaをそのまま静止探索で使うことが考えられる。これは得られた静止探索値がウインドウの外になると不正確な値になってしまいまずそうだが、depth+1で探索が終端されるときは問題が無い。なぜなら、terminate()によると、静止探索値がウインドウの外のときは静止探索値そのものは終端の条件に関係しないからだ。しかし、探索が続くときはムーブオーダリングで問題が生じる。静止探索値が不正確なので本来上位に来るはずの手が展開されない恐れがある。この欠点はあるが静止探索の実行時間を減じる効果が大きいので、KFEndはこのやり方を取っている。
反復深化を行うと同じゲーム木を何度も探索することになるが、その度に各ノードで生成した手の静止探索値を求めるのは非常に無駄である。これを解決するには局面表を設けるのが良い。記録する情報は、生成した手とその静止探索値である。前述したように、前向き枝刈りによって展開される手は最大で10手程度なので、局面表にも1エントリ当たりこの程度の数の手を記録する。この局面表はヒットしたとき探索を終端するのではなく、静止探索を省略することのみを目的としている。また、静止探索そのもののための局面表を別に設けている。
前半でABC探索の紹介をしたが、興味を持たれた方は資料[1]McAllesterを読まれることを強く薦める。基本の考え方、例をあげた動作の解説、数学的基礎などが書かれていて非常におもしろい。本解説におけるABC探索のアルゴリズムの記述はかなり具体的なので、原論文で分かり難いと思われる箇所があったとき、理解の助けになるかもしれない。なお、原論文とこの解説でアルゴリズムに異なる点を見つけられた方は、メールで教えて頂けるとありがたい。
詰将棋の分野で非常に優れた性能を示した、C*アルゴリズム（資料[2]脊尾、[3]脊尾）がある。C*のキーワードは、縦型探索、共謀数、多重反復深化である。ABCでも、縦型探索、共謀数（深さ）はやはり重要な概念だ。これに多重反復深化を加えれば新しい探索が生まれるかもしれない。私はC*の圧倒的な性能に驚いたひとりであったので、ABC＋多重反復深化に大いに期待をかけて実験を行った。しかし、これは全くうまくいかなかった。原因は簡単には言えないが、将棋の探索の難しさを改めて認識させられた感じだ。課題としてこれからも考えていきたい。
(2000.8.12)