まず、ハッシュとは何かについて簡単に説明したい。
一般的に、「ハッシュ法」とは、長いデータを何らかの関数で短くする（＝ハッシュする※1）ことで、長いデータ同士を直接比較するのではなく、ハッシュ後の短いデータ同士を比較することで高速化を図る技法を言う。
※1この際に元と比較して情報は欠落する
たとえば、非常に原始的なハッシュ法としては、次のようなものがある。
ある文字列がたくさんある文字列と一致するかどうかを比較する場合、文字列同士を一つ一つ比較するのではなく、256の大きさの配列の配列を用意し、たくさんある文字列を先頭の１バイトで仕分けして256の大きさの配列の配列へとしまい込んでいく。そして、ある文字列を比較する際に、最初の１バイトだけでまず配列を参照し、その後、その配列内の文字列の配列と比較する、といった方法が考えられる。
将棋では、同一局面を判定するのに、ハッシュ法を用いる。
すでにチェスの世界で成功したハッシュの方法として、盤面のある箇所にある駒がいる場合、「Ｘ」という値を用意し、盤面にある駒すべてについて、その値をすべて「ＸＯＲ」していくことでハッシュ値を求めるという方法が知られている。
この方法をZobrist Hashと言う。1970年代には既にチェスで成功を納めている。
「ＸＯＲ」を使う利点には、次のようなものがある。
「Ｙ ＸＯＲ Ｘ＝Ｚ」ならば、「Ｚ ＸＯＲ Ｘ＝Ｙ」という性質を利用して、ある駒が動いた場合に、現在のハッシュ値「Ｚ」に対して、ある駒が移動元にいた場合の値「Ｘ」をまず「ＸＯＲ」し、ある駒が盤面から消えた場合のハッシュ値Ｙを求める（Ｚ ＸＯＲ Ｘ＝Ｙ）。
さらに、移動後の位置にある駒がいた場合の値「Ｘ’」を「Ｙ」と「ＸＯＲ」することで、新たな局面を表わすハッシュ値「Ｚ’」が求められる（Ｙ ＸＯＲ Ｘ’＝Ｚ’）。
もう一度「ＸＯＲ」すると元の値に戻るという性質を利用することで、盤面である駒が移動する場合のハッシュ値をかなり高速に（この場合「ＸＯＲ」２回で）演算できることになる。
問題は、ある駒がある位置にいる場合のハッシュ値Ｘをどのように決めるかということであるが、これには、乱数を用いれば良い結果が得られることが知られている。
また、ハッシュ値は３２ビットではハッシュミス（別の局面が同じハッシュ値を持つ）の頻度が高く起きることが知られているため、本書ではハッシュ値として６４ビットの値を用いる。
では、実際に、ある位置にある駒がいた場合のハッシュ値の種を決めて、局面をハッシュによって識別してみよう。
GCCでは、６４ビットの整数型に「long long」を用いることができる。また、「BorlandC++」「VisualC++」といったWindows系コンパイラでは、「__int64」という型を用いることができる。
そこで、６４ビット型の差を吸収するために、ヘッダ部は以下のようになる。
Kyokumen.h変更分
#ifdef _GCC_
typedef long long int64;
typedef unsigned long long uint64;
#else
typedef __int64 int64;
typedef unsigned __int64 uint64;
#endif
class Kyokumen {
:
static uint64 HashSeed[ERY+1][0x99+1];
static uint64 HandHashSeed[EHI+1][0x18+1];
:
}
kyokumen.cppの変更分: 注意：rand()関数が15bitの乱数列を返す事を期待している。ＧＣＣでは特に要注意。
void HashInit()
{
int i;
for(i=0;i<=ERY;i++) {
for(int pos=0x11;pos<=0x99;pos++) {
if (i==0) {
HashSeed[i][pos]=0;
} else {
HashSeed[i][pos]=((uint64)rand())<<49|
((uint64)rand())<<34|
((uint64)rand())<<19|
((uint64)rand())<<4|
rand() & 0x07;
}
}
}
for(i=SFU;i<=EHI;i++) {
for(int maisuu=0;maisuu<=18;maisuu++) {
HandHashSeed[i][maisuu]=((uint64)rand())<<49|
((uint64)rand())<<34|
((uint64)rand())<<19|
((uint64)rand())<<4|
rand() & 0x07;
}
}
}
では、局面のMove関数や、初期化の関数で、ハッシュ値を求めるように改造していこう。改造後の初期化関数は以下のとおり。
Kyokumen(KomaInf banmen[9][9],int Motigoma[])
{
:
HashInit();
}
また、改造後のMove関数は、以下のようになる。
// 手で局面を進める
void Kyokumen::Move(int SorE,const Te &te)
{
int i,j,b,bj;
if (te.from>0x10) {
// 元いた駒のコントロールを消す
int dir;
for(dir=0,b=1,bj=1<<16;dir<12;dir++,b<<=1,bj<<=1) {
if (SorE==SELF) {
controlS[te.from+Direct[dir]]&=~b;
} else {
controlE[te.from+Direct[dir]]&=~b;
}
if (CanJump[dir][te.koma]) {
int j = te.from;
do {
j += Direct[dir];
if (SorE==SELF) {
controlS[j] &= ~bj;
} else {
controlE[j] &= ~bj;
}
} while (ban[j] == EMPTY);
}
}
// 元いた位置は空白になる
ban[te.from]=EMPTY;
// 空白になったことで変わるハッシュ値
KyokumenHashVal^=HashSeed[te.koma][te.from];
KyokumenHashVal^=HashSeed[EMPTY][te.from];
// 飛び利きを伸ばす
for (i = 0, bj = (1<<16); i < 8; i++, bj<<=1) {
int Dir=Direct[i];
if (controlS[te.from] & bj) {
j = te.from;
do {
j += Dir;
controlS[j] |= bj;
} while (ban[j] == EMPTY);
}
if (controlE[te.from] & bj) {
j = te.from;
do {
j += Dir;
controlE[j] |= bj;
} while (ban[j] == EMPTY);
}
}
} else {
// 持ち駒から一枚減らす
HandHashVal^=HandHashSeed[te.koma][Hand[te.koma]];
Hand[te.koma]--;
value-=HandValue[te.koma];
value+=KomaValue[te.koma];
}
if (ban[te.to]!=EMPTY) {
// 相手の駒を持ち駒にする。
// 持ち駒にする時は、成っている駒も不成りに戻す。（&~PROMOTED）
value-=KomaValue[ban[te.to]];
value+=HandValue[SorE|(ban[te.to]&~PROMOTED&~SELF&~ENEMY)];
int koma=SorE|(ban[te.to]&~PROMOTED&~SELF&~ENEMY);
Hand[koma]++;
// ハッシュに取った駒を加える
HandHashVal^=HandHashSeed[koma][Hand[koma]];
//取った駒の効きを消す
for (i = 0, b = 1, bj = (1<<16); i < 12; i++, b<<=1, bj<<=1) {
int Dir=Direct[i];
if (CanJump[i][ban[te.to]]) {
j = te.to;
do {
j += Dir;
if (SorE==SELF) {
controlE[j] &= ~bj;
} else {
controlS[j] &= ~bj;
}
} while (ban[j] == EMPTY);
} else {
j=te.to + Dir;
if (SorE==SELF) {
controlE[j] &= ~b;
} else {
controlS[j] &= ~b;
}
}
}
} else {
// 移動先で遮った飛び利きを消す
for (i = 0, bj = (1<<16); i < 8; i++, bj<<=1) {
int Dir=Direct[i];
if (controlS[te.to] & bj) {
j = te.to;
do {
j += Dir;
controlS[j] &= ~bj;
} while (ban[j] == EMPTY);
}
if (controlE[te.to] & bj) {
j = te.to;
do {
j += Dir;
controlE[j] &= ~bj;
} while (ban[j] == EMPTY);
}
}
}
// ban[te.to]にあったものをＨａｓｈから消す
KyokumenHashVal^=HashSeed[ban[te.to]][te.to];
if (te.promote) {
value-=KomaValue[te.koma];
value+=KomaValue[te.koma|PROMOTED];
ban[te.to]=te.koma|PROMOTED;
} else {
ban[te.to]=te.koma;
}
// 新しい駒をＨａｓｈに加える
KyokumenHashVal^=HashSeed[ban[te.to]][te.to];
// 移動先の利きをつける
for (i = 0, b = 1, bj = (1<<16); i < 12; i++, b<<=1, bj<<=1) {
if (CanJump[i][ban[te.to]]) {
j = te.to;
do {
j += Direct[i];
if (SorE==SELF) {
controlS[j] |= bj;
} else {
controlE[j] |= bj;
}
} while (ban[j] == EMPTY);
} else if (CanMove[i][ban[te.to]]) {
if (SorE==SELF) {
controlS[te.to+Direct[i]] |= b;
} else {
controlE[te.to+Direct[i]] |= b;
}
}
}
// 王様の位置は覚えておく。
if (te.koma==SOU) {
kingS=te.to;
}
if (te.koma==EOU) {
kingE=te.to;
}
HashVal=KyokumenHashVal^HandHashVal;
Tesu++;
HashHistory[Tesu]=HashVal;
OuteHistory[Tesu]=(SorE==SELF)?controlS[kingE]:controlE[kingS];
}
先ほどの改造で、同一局面ならハッシュ値が同じになるようにプログラムができた。また、ハッシュが一致しているにもかかわらず、同一局面ではないという可能性も充分低いものと思ってよい。
そこで、ここまでは考慮しなかった「千日手のチェック」「連続王手の千日手のチェック」をハッシュ値を見て行なうように、main関数を書き換えてみる。
:
int sennitite=0;
int OuteSennitite=0;
int first=0;
int i;
for(i=k.Tesu;i>0;i-=2) {
if (k.HashHistory[i]==k.HashVal) {
sennitite++;
}
}
if (sennitite>=4) {
bSennitite=true;
break;
}
:
if (SorE==SELF && teNum==0) {
printf("後手の勝ち。\n");
} else if (teNum==0) {
printf("先手の勝ち。\n");
} else if (bSennitite) {
// 千日手による終局
// 王手の千日手の判定
printf("千日手です。\n");
int sennitite=0;
if (Kyokumen::OuteHistory[k.Tesu]) {
for(int i=k.Tesu;sennitite<=3&&i>0;i-=2) {
if (!Kyokumen::OuteHistory[i]) {
break;
}
if (k.HashHistory[i]==k.HashVal) {
sennitite++;
}
}
if (sennitite==4) {
// 連続王手の千日手
printf("連続王手の千日手です。\n");
if (SorE==SELF) {
printf("後手の勝ち。\n");
} else {
printf("先手の勝ち。\n");
}
}
} else if (Kyokumen::OuteHistory[k.Tesu-1]) {
// こちらは未検証
for(int i=k.Tesu;sennitite<=3&&i>0;i-=2) {
if (!Kyokumen::OuteHistory[i-1]) {
break;
}
if (k.HashHistory[i]==k.HashVal) {
sennitite++;
}
}
if (sennitite==4) {
// 連続王手の千日手
printf("連続王手の千日手です。\n");
if (SorE==SELF) {
printf("先手の勝ち。\n");
} else {
printf("後手の勝ち。\n");
}
}
}
}
:
実は、乱数を入れていない場合、先読みの深さを3手にすると、必ず先手の「王手千日手」で後手の勝ちとなる。これは、「連続王手の千日手」を思考ルーチンで負けとしていないので、先手が「連続王手の千日手」を避けないことに原因がある。
そこで、１手目に指した手が「千日手だったら引き分け」（評価値０）、「連続王手の千日手だったら負け（評価値－∞）または勝ち（評価値＋∞）」となるようにしてみよう。これで、連続王手の千日手や、千日手を打開しても自分が有利な局面での千日手はしないようになるはずである。また、逆に、不利な場合には喜んで通常の千日手にするようになる。
「先読みの途中での千日手のチェック」「王手の千日手のチェック」はプログラムが遅くなるのが怖いので、とりあえず実装しない。
実装は簡単なので、興味がある、または先読み中の千日手についてもきちんと処理したい読者は自分で改造を試みてほしい。
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;
}
}
:
以下は今まで通り。
今までのソースコードは、chapter05-03フォルダの下にある。違いなどを確認して欲しい。
2015年10月 追記 sennitite==4またはsennitite>=4だと（０から始まるので）5回目の登場のような気がする…。バグってる？