反復深化とは、ある深さまで探索を行う場合に、その深さまで一気に探索を行うのではなく、最初は浅い探索から始めて、徐々に深くしていく方法である。
単純には、同じ探索を何回も繰り返すことになるので、こうすることによるメリットが一見ないように見えるが、ハッシュ及び局面表と組み合わせることでαβの効率化を図ることが出来る。
局面表とは、ハッシュ値とそれに対応する局面での探索結果の値、最善手などを記憶する表である。
2015年10月追記： 局面表はTransPositionTableの訳語のつもりであるが、もっと良い名前を募集中。
つまり、一度浅い探索を行なわせることで、浅い探索での最善手を局面表に記憶しておき、二度目以降の探索では先の探索での最善手から探索することで、手の探索の順序を最適に近いものにして、αβの効率化を図るわけである。
また、将棋のようなゲームでは、「Ａ→Ｂ→Ｃ」という手順でも、「Ｃ→Ｂ→Ａ」という手順でも同じ局面にたどり着くことがある。このような場合に、局面表を見てすでに探索済みの値を引くことでも効率化を図ることができる。
まず、局面表に何を記憶するかだが、ここでは、
・ハッシュ値 ・最善手 ・最善手が変わる前の最善手 ・評価値 ・その評価値が下限か上限かまたは正確な値か（αとβとの関係から決まる） ・その評価値を得たときの探索の深さ ・その評価値を得たときの残り探索の深さを記憶することとする。
以上のデータで、約４０バイトを消費する。４０Ｍバイトを局面表に使うとして、局面表の大きさは「１Ｍ＝２２０」とすることにしよう。
まず、局面表のエントリーとなるクラスだが、下記のように定義される。
enum {
EXACTLY_VALUE, // 値は局面の評価値そのもの
LOWER_BOUND, // 値は局面の評価値の下限値(val>=β)
UPPER_BOUND // 値は局面の評価値の上限値(val<=α)
};
class HashEntry {
public:
uint64 HashVal; // ハッシュ値
Te Best; // 前回の反復深化での最善手
Te Second; // 前々回以前の反復深化での最善手
int value; // αβ探索で得た局面の評価値
int flag; // αβ探索で得た値が、局面の評価値そのものか、上限値か下限値か
int Tesu; // αβ探索を行った際の手数
short depth; // αβ探索を行った際の深さ
short remainDepth; // αβ探索を行った際の残り深さ
};
次に、「局面表に局面を追加する」「ある局面を局面表から探す」部分は以下のようになる。
//局面表から探す
if (HashTbl[k.HashVal & 0x0fffff].HashVal==k.HashVal) {
HashEntry e=HashTbl[k.HashVal & 0x0fffff];
}
//局面表に追加する（場合によっては上書きする）
HashEntry e;
e.xx=xxxx; // eに適当な値を代入する。
HashTbl[k.HashVal & 0x0fffff]=e;
これを使って、探索を効率化したαβ探索は以下のようになる。
// 局面表から手を探す
int Sikou::MakeMoveFirst(int SorE,int depth,Te teBuf[],Kyokumen k)
{
int teNum=0;
if (HashTbl[k.HashVal & 0xfffff].HashVal!=k.HashVal) {
return 0;
}
if (HashTbl[k.HashVal & 0xfffff].Tesu%2!=k.Tesu%2) {
// 手番が違う。
return 0;
}
// 局面が一致したと思われる
Te te=HashTbl[k.HashVal & 0xfffff].Best;
if (!te.IsNull()) {
if (k.IsLegalMove(SorE,te)) {
teBuf[teNum++]=te;
}
}
te=HashTbl[k.HashVal & 0xfffff].Second;
if (!te.IsNull()) {
if (k.IsLegalMove(SorE,te)) {
teBuf[teNum++]=te;
}
}
if (depth>1) {
te=Best[depth-1][depth];
if (!te.IsNull() && k.IsLegalMove(SorE,te)) {
teBuf[teNum++]=te;
}
}
return teNum;
}
int Sikou::NegaAlphaBeta(int SorE,Kyokumen &k,int alpha,int beta,int depth,int depthMax)
{
if (depth==1) {
// 千日手チェック
int sennitite=0;
for(int i=k.Tesu;i>0;i-=2) {
if (k.HashHistory[i]==k.HashVal) {
sennitite++;
}
}
if (sennitite>=4) {
// 千日手
sennitite=0;
// 連続王手の千日手チェック
int i;
for(i=k.Tesu;sennitite<=3&&i>0;i-=2) {
if (!Kyokumen::OuteHistory[i]) {
break;
}
if (k.HashHistory[i]==k.HashVal) {
sennitite++;
}
}
if (sennitite==4) {
// 連続王手の千日手をかけられている
return INFINITE;
}
sennitite=0;
for(i=k.Tesu;sennitite<=3&&i>1;i-=2) {
if (!Kyokumen::OuteHistory[i-1]) {
break;
}
if (k.HashHistory[i]==k.HashVal) {
sennitite++;
}
}
if (sennitite==4) {
// 連続王手の千日手をかけている
return -INFINITE;
}
return 0;
}
}
if (depth==depthMax) {
int value=k.value+k.BestEval(SorE);
// 自分の手番から見た得点を返す
if (SorE==SELF) {
return value;
} else {
return -value;
}
}
if (HashTbl[k.HashVal & 0x0fffff].HashVal==k.HashVal) {
HashEntry e=HashTbl[k.HashVal & 0x0fffff];
if (e.value>=beta && e.Tesu>=k.Tesu && e.Tesu%2==k.Tesu%2 && e.depth<=depth && e.remainDepth>=depthMax-depth && e.flag!=UPPER_BOUND) {
return e.value;
}
if (e.value<=alpha && e.Tesu>=k.Tesu && e.Tesu%2==k.Tesu%2 && e.depth<=depth && e.remainDepth>=depthMax-depth && e.flag!=LOWER_BOUND) {
return e.value;
}
}
Te teBuf[600];
int teNum=MakeMoveFirst(SorE,depth,teBuf,k);
int retval=-INFINITE-1;
int i;
for(i=0;i<teNum;i++) {
Kyokumen kk(k);
if (teBuf[i].IsNull()) {
continue;
}
kk.Move(SorE,teBuf[i]);
int v=-NegaAlphaBeta(SorE==SELF?ENEMY:SELF,kk,-beta,-max(alpha,retval),depth+1,depthMax);
if (v>retval) {
retval=v;
Best[depth][depth]=teBuf[i];
for(int i=depth+1;i<depthMax;i++) {
Best[depth][i]=Best[depth+1][i];
}
if (depth==0) {
printf("retval:%d,te:",retval);
for(int j=0;j<depthMax;j++) {
Best[0][j].Print();
}
printf("\n");
}
if (retval>=beta) {
goto HashAdd;
}
}
}
teNum=k.MakeLegalMoves(SorE,teBuf);
if (teNum==0) {
// 負け
return -INFINITE;
}
for(i=0;i<teNum;i++) {
Kyokumen kk(k);
kk.Move(SorE,teBuf[i]);
int v=-NegaAlphaBeta(SorE==SELF?ENEMY:SELF,kk,-beta,-max(alpha,retval),depth+1,depthMax);
if (v>retval) {
retval=v;
Best[depth][depth]=teBuf[i];
for(int i=depth+1;i<depthMax;i++) {
Best[depth][i]=Best[depth+1][i];
}
if (depth==0) {
printf("retval:%d,te:",retval);
for(int j=0;j<depthMax;j++) {
Best[0][j].Print();
}
printf("\n");
}
if (retval>=beta) {
goto HashAdd;
}
}
}
HashAdd:
HashEntry e;
e=HashTbl[k.HashVal & 0x0fffff];
if (e.HashVal==k.HashVal) {
e.Second=e.Best;
} else {
e.HashVal=k.HashVal;
e.Second=Te(0);
}
if (retval>alpha) {
e.Best=Best[depth][depth];
} else {
e.Best=Te(0);
}
e.value=retval;
if (retval<=alpha) {
e.flag=UPPER_BOUND;
} else if (retval>=beta) {
e.flag=LOWER_BOUND;
} else {
e.flag=EXACTLY_VALUE;
}
e.depth=depth;
e.remainDepth=depthMax-depth;
e.Tesu=k.Tesu;
HashTbl[k.HashVal & 0x0fffff]=e;
return retval;
}
int Sikou::ITDeep(int SorE,Kyokumen &k,int alpha,int beta,int depth,int depthMax)
{
int retval;
int i;
for(i=1;i<=depthMax;i++) {
retval=NegaAlphaBeta(SorE,k,alpha,beta,depth,i);
}
return retval;
}
ここまでのソースコードはchapter06-01フォルダに収録した。
反復深化は、ルートノード（探索の開始点）でのみ反復深化を行う方法だが、さらに、多重反復深化というアイデアが提唱されている。
これは、探索の開始点だけでなく、初めて探索するノード（局面表上に見つからなかったノード）についてもそこからの探索では反復深化を行うことで、より探索が効率的になるという手法である。
実際に組み込んだαβ関数の変更点は以下のようになる。
if (HashTbl[k.HashVal & 0x0fffff].HashVal==k.HashVal) {
HashEntry e=HashTbl[k.HashVal & 0x0fffff];
：
} else if (depthMax-depth>2 && bITDeep) {
// 初めて訪れた局面で、深さも残っているので多重反復深化を行う。
return ITDeep(SorE,k,alpha,beta,depth,depthMax);
}
変更点は、基本的にはたった４行。しかもそのうち１行はコメント、もう１行は「｝」だけである。
反復深化は、ある程度以上の深さが残っていない場合、単なるαβより遅くなることがあるため、「深さ３以上残っているとき」に限って反復深化を実行するものとしてみた。
また、αとβの幅が充分狭いときにも単純にαβを実行したほうが良い可能性が高い。しかし、このような微妙なバランスを取る作業は読者の課題としてほしい。※4
※4 読者が改良したプログラムでは、多重反復深化や反復深化そのものが最良でない可能性もある！
以下の「bITDeep」は、ある局面がたまたま局面表上で上書きされているために見付からない場合に、「ITDeep」と「NegaAlphaBeta」で無限ループを起こさないように導入された、「NegaAlphabeta」の新しい引数である。
int Sikou::NegaAlphaBeta(int SorE,Kyokumen &k,int alpha,int beta,int depth,int depthMax,bool bITDeep=true)
省略時には「true」となるが、「ITDeep」からは、「false」を設定して「NegaAlphaBeta」を呼び出すことで、無限ループを回避している。
なお、筆者の環境でテストした結果では、多重反復深化によって３０％程度は高速化されたようだ。
ここまでのソースコードはchapter06-02フォルダに収録した。