前回、kouryo()関数は実はサボれる、という話をしました。
これは、同じ結果を得られるけれど、新しいやり方はより少ない時間で
回答を見つけられる、という意味でお話しました。
今回は、ほぼすべての将棋ゲームプログラムの基礎となっている、アルファベータ法
という探索アルゴリズムを紹介いたします。
まずはC言語で書かれたkouryo()関数と、AlphaBeta()関数を見てもらいましょう。
int kouryo(int *te, int fukasa)
{
int te2;
int teban = 1; // 先手がCOMPUTER, -1なら後手がCOMPUTER
int val = AlphaBeta(&te2, -10000, 10000, fukasa, teban);
*te = te2;
return val;
}
int AlphaBeta(int *te, int alpha, int beta, int depth, int teban)
{
int kazu;
int hairetsu[1024];
kazu = kanoushu(hairetsu, teban); // hairetsu[0] から hairetsu[kazu-1]に手が入る
if (depth <= 0) { return hyouka(teban);}
int i;
int ret = 0;
for ( i = 0 ; i < kazu ; i++) {
int te, te2;
te = hairetsu[i];
sasu(te);
int a = - AlphaBeta( &te2, -beta, -alpha, depth - 1, (-1)*teban);
modosu(te);
if ( a > alpha) { // alpha update
alpha = a;
ret = te;
}
if ( ban >= beta ) { // beta cut
*te = ret;
return ban;
}
}
*te = ret;
return ban;
}
まずkouryo()関数に探索深さがわたると、その中でAlphaBeta関数を呼び出します。
このとき重要なのがalphaとbetaと呼ばれる二つのパラメータです。
AlphaBeta関数には面白い性質があります。探索の答えの値（評価値）が、
alpha以上beta以下だと、AlphaBeta関数はその答えの値を返します。
もしalphaからbetaの範囲内に答えが無かったら、alphaかbeta（大小による）
を返します。この、alphaからbetaの範囲のことをウィンドウと言いますが、
もしある程度の誤差でAlphaBeta関数の答えをあらかじめ知っていれば、
ウィンドウを狭めて検索することで早く答えを出す事ができます。
AlphaBeta()関数の内部を見て行きましょう。
この前のkouryo()関数と似ていますがいくつか異なる点があります。
まずfukasaをdepthという値に置き換えて、探索が深くなるとdepthが
小さくなるようにしています。hyouka()を返す条件をdepthが0以下と
しました。またhyouka()は手番をとるように変更しました。
また、手番を追加しました。1を先手、-1を後手とします。
同じAlphaBeta関数を中で呼んでいる（これを再帰といいます）
あと、二つの条件文のところにコメントで、
alpha update, beta cutと書いてあります。この二つがとても
重要です。
厳密にはこのアルゴリズムはアルファベータ法ではなく、
ネガマックス法という、より簡略化した手法ですが、同じ正解を
得られます。
ではalpha updateとbeta cutの説明をしましょう。
alpha updateとは、「答えかもしれない良い手に出会いました」
という意味で、alpha updateのときは手と評価値を保存します。
またalphaパラメータを更新して、より大きい値に変更します。
つまりウィンドウを狭める訳です。
beta cutは正確にはbeta cut-offと言います。
これが実はサボりのために必要な部分です。
評価値がbetaを超えた場合、その手はとても良い手なので、
その手で探索を打ち切ります。それより後ろの可能手を
AlphaBeta()関数で調べなくても、最終的な正解は変わらない
という性質を利用しています。
結果、極端な場合には始めの一手でbeta cutが起こると、
その手しか調べません。これが効率がよい秘密です。
このAlphaBeta関数には入っていませんが、可能手を、beta cut-off
しやすい順にならべれば、探索する探索木はより深くまで読める
ような理想型になります。このソート（並べ替え）のことを
ムーブオーダリングと呼び、強い将棋ソフトには必須の機能です。
またこの探索木の理想型のことをoptimal treeと呼んでいます。
Knuth先生という方の論文に、このoptimal treeになったときに
どのくらい局面を探索するか、という値が計算されています。
詳しくはその論文に譲りますが、まじめに全部調べるよりずっと
少ない数になります。
ではねちゃお！
0 件のコメント:
コメントを投稿