2.4 順序付けと反復深化法

今回は、前回説明したAlpha-Beta法をさらに有効に利用するための方法について説明します。 Alpha-Beta法で効率よく探索を行うためには、Alpha-cutとBeta-cutが多く起こるようにすることが重要です。 そのためには、自局面の節点では自分が有利になるような手（＝評価が高い）から探索し、相手局面の節点では自分が不利になるような手から探索すればよいです。 なぜかというと、自局面の節点では、評価の高い手から探索すれば、それだけAlpha値が大きくなり、Alpha-cutが起こりやすくなります。 相手局面でも同様です。 そこで、子節点の探索を行う前にまず各子節点の局面を評価し、その評価の高い順から探索を行うようにします。 それによって、Alpha-Beta法がさらに効率のよいものとなります。

図1. 節点の順序付け

この考えをさらに進めたのが反復深化法です。 反復深化法では、最初に浅い（あまり先まで読まない）探索を行い、各手の評価付けを行います。 その後深さ（先読みの手数）を１ずつ（2以上の場合もある）増やして探索し、目的の深さまで探索を行います。

トップに戻る 2.3 Alpha-Beta法 2.5 Scout法