この章では、最後に残した課題として、終盤の「『詰め将棋』と『詰めろ』などの処理」について扱う。
「詰め将棋」自体は、αβをとても簡単にしたものとして取り扱える。
「詰みを１、不詰みを０」として評価点を返し、王手をかける番では王手のみを生成し、王手を受ける番では、王手を受ける手のみを生成すればよい。
王手の生成には、非常に簡単な方法があり、通常の手生成を呼び出して一手進めてみて、王手がかかっていなければその手は取り除けばよい。
2015年 10月 追記：上記の方法はとても遅いので、オススメは出来ない。
この方法で王手を生成するルーチンは、以下のようになる。
int Kyokumen::MakeChecks(int SorE,Te *teBuf,int *pin)
{
Kyokumen kk(*this); // 実際に動かしてみる局面
unsigned int *selfControl; // 手番側から見て、自分の利き
int enemyKing; // 手番側から見て、相手の玉の位置
if (SorE==SELF) {
selfControl=kk.controlS;
enemyKing=kingE;
} else {
selfControl=kk.controlE;
enemyKing=kingS;
}
int teNum=MakeLegalMoves(SorE,teBuf,pin);
// 実際に動かしてみて、王手だけを残す。
int outeNum=0;
for(int i=0;i<teNum;i++) {
kk=*this;
kk.Move(SorE,teBuf[i]);
// 相手の玉に利きが付いていれば王手。
if (selfControl[enemyKing]) {
teBuf[outeNum++]=teBuf[i];
}
}
return outeNum;
}
また、王手を受ける手については、通常の手生成を呼び出せば、王手がかかっていれば受ける手のみが生成される。受けなければ反則負けだから、１章で「ルール通りに指す」プログラムを作成する際に、すでにそのような仕様になっている。
というわけで、反復深化法による詰め将棋を簡単に書いてみよう。
class Kyokumen {
:
// 第９章で追加。王手を生成。
int MakeChecks(int SorE,Te *tebuf,int *pin=NULL);
// 第９章で追加。詰め将棋ルーチン。
int Mate(int SorE,int maxDepth,Te &te);
int CheckMate(int SorE,int depth, int depthMax, Te *checks,Te &te);
int AntiCheckMate(int SorE,int depth, int depthMax, Te *checks);
};
int Kyokumen::Mate(int SorE,int maxDepth,Te &te)
{
Te teBuf[10000]; // 深さ30程度までなら十分すぎる大きさ
int ret;
for(int i=1;i<=maxDepth;i+=2) {
if (ret=CheckMate(SorE,0,i,teBuf,te)) {
break;
}
}
// 0:不明
// 1:詰んだ
// -1:不詰み
return ret;
}
int Kyokumen::CheckMate(int SorE,int depth, int depthMax, Te *checks,Te &te)
{
int teNum = MakeChecks(SorE,checks);
if (teNum == 0) return -1; //詰まない
int valmax = -1;
for (int i = 0; i < teNum; i++) {
Kyokumen kk(*this);
kk.Move(SorE,checks[i]);
int val = kk.AntiCheckMate(SorE^0x30, depth+1, depthMax, checks+teNum);
if (val > valmax) valmax = val;
if (valmax == 1) {
te=checks[i];
break; //詰んだ
}
}
if (valmax == 1) { //詰んだ
} else if (valmax == -1) { //本当に詰まなかった
}
return valmax;
}
int Kyokumen::AntiCheckMate(int SorE,int depth, int depthMax, Te *antichecks)
{
Te te;
int teNum=MakeLegalMoves(SorE,antichecks);
int i=0;
int valmin = 1;
if (teNum == 0) {
return 1;
}
if (depth >= depthMax+1) return 0; //長さの限界詰みは不明
for (i = 0; i < teNum; i++) {
Kyokumen k(*this);
k.Move(SorE,antichecks[i]);
int val = k.CheckMate(SorE^0x30, depth+1, depthMax, antichecks+teNum,te);
if (val < valmin) valmin = val;
if (valmin == -1) break; // 詰まなかった
if (valmin == 0) break; // 詰まなかった
}
return valmin;
}
さて、先の方法には少々問題がある。
図１を見てほしい。玉方(ぎょくかた)はどこに合い駒を打ってもそれを龍でとられるだけなので、通常、９一飛成までの「１手詰め」とされる局面である。
しかし、先ほどの反復深化法では、これがなんと１７手詰めになってしまう。無駄に合い駒する手を一々読んでしまうからである。
つまり、８一に合い駒、同龍、７一に合い駒、同龍…と続くわけである。
このような問題に対しては、「柿木のアルゴリズム」と呼ばれる解決方法が知られている。
これは、一言で言うと、「王手をかけた駒で合い駒を取り、その合い駒を玉方にすぐに返したときに、それでも詰むならばその合い駒は無駄合いである」という定理である。
この裏には、「攻め方の持ち駒が増えないでも詰むならば、その局面は何で合い駒しても詰む」という単純な（しかし気がつきにくい）真理が隠されている。
前述のプログラムは、「ハッシュ法」を応用することで、柿木のアルゴリズムに対応したプログラムにすることができる。
つまり、局面のハッシュ値を、「盤面だけのハッシュ値」と「持ち駒の枚数」とに分けて記憶し、「最初に合い駒を取って、その合い駒を使わずに玉方に返した局面が詰むことを確認する」「すでに詰むことが分かっている盤面と現在の盤面のハッシュ値が一致した場合に、現在の局面のほうが持ち駒の枚数が多いならば必ず詰むので、それ以上調べずに詰みを返す」という２点をプログラムに加えればよい。
もっとも、それでも３手詰めにはなってしまうのだが…。
実際には、柿木のアルゴリズムではなく、ハッシュ法を応用して、「盤面が同じで、持ち駒がより多い局面では、ハッシュに登録された局面が詰みならば詰み」「盤面が同じで、持ち駒がより少ない局面で、ハッシュに登録された局面が不詰みなら不詰み」というルーチンを入れてみることにする。
この際、持ち駒のより多いかどうかをビット演算で実現できるよう、持ち駒を64ビットであらわす、CalcHandという関数を用意した。
CalcHandでは、たとえば、歩を１枚持っているときには、２進数で「0001」、３枚持っているときには、「0111」のようにあらわしている（それぞれ、１６進数なら「0x01」「0x07」となる）。これらの値が、FU_BITS_TBLに入っている。
ここで、論理演算のANDを用いると、現在の持ち駒AND 局面表の持ち駒= 局面表の持ち駒ならば、現在の持ち駒の方が多いというようにいえる。
先の歩の例ならば、「0111 AND 0001 = 0001」で、歩が３枚の方が歩が１枚よりも多いというようにいえるわけである。歩だけでなく、香車や桂馬、銀、金、角、飛車などを加えた場合についても、同様に計算できるように、テーブルの値などを設定している。
これは、以下のようになる。
#define RETRY_MAX 9
struct TsumeVal {
uint64 HashVal;
uint64 Motigoma;
int NextEntry;
int mate;
Te te;
};
#define TSUME_HASH_SIZE 1024*1024
#define TSUME_HASH_AND (TSUME_HASH_SIZE-1)
class TsumeHash {
static TsumeVal HashTbl[TSUME_HASH_SIZE];
static uint64 FU_BIT_TBL[19];
static uint64 KY_BIT_TBL[5];
static uint64 KE_BIT_TBL[5];
static uint64 GI_BIT_TBL[5];
static uint64 KI_BIT_TBL[5];
static uint64 KA_BIT_TBL[3];
static uint64 HI_BIT_TBL[3];
static TsumeVal *FindFirst(uint64 KyokumenHashVal);
static TsumeVal *FindNext(TsumeVal* Now);
static uint64 TsumeHash::CalcHand(int Motigoma[]);
public:
static void Clear();
static void Add(uint64 KyokumenHashVal,uint64 HandHashVal,int Motigoma[],int mate,Te te);
static TsumeVal *Find(uint64 KyokumenHashVal,uint64 HandHashVal,int Motigoma[]);
static TsumeVal *DomSearchCheckMate(uint64 KyokumenHashVal,int Motigoma[]);
static TsumeVal *DomSearchAntiMate(uint64 KyokumenHashVal,int Motigoma[]);
};
TsumeVal TsumeHash::HashTbl[TSUME_HASH_SIZE];
uint64 TsumeHash::FU_BIT_TBL[19]={
0x0000000000000000,
0x0000000000000001,
0x0000000000000003,
0x0000000000000007,
0x000000000000000f,
0x000000000000001f,
0x000000000000003f,
0x000000000000007f,
0x00000000000001ff,
0x00000000000003ff,
0x00000000000007ff,
0x0000000000000fff,
0x0000000000001fff,
0x0000000000003fff,
0x0000000000007fff,
0x000000000000ffff,
0x000000000001ffff,
0x000000000003ffff,
0x000000000007ffff
};
uint64 TsumeHash::KY_BIT_TBL[5]={
0x0000000000000000,
0x0000000000100000,
0x0000000000300000,
0x0000000000700000,
0x0000000000f00000,
};
uint64 TsumeHash::KE_BIT_TBL[5]={
0x0000000000000000,
0x0000000001000000,
0x0000000003000000,
0x0000000007000000,
0x000000000f000000,
};
uint64 TsumeHash::GI_BIT_TBL[5]={
0x0000000000000000,
0x0000000010000000,
0x0000000030000000,
0x0000000070000000,
0x00000000f0000000,
};
uint64 TsumeHash::KI_BIT_TBL[5]={
0x0000000000000000,
0x0000000100000000,
0x0000000300000000,
0x0000000700000000,
0x0000000f00000000,
};
uint64 TsumeHash::KA_BIT_TBL[3]={
0x0000000000000000,
0x0000001000000000,
0x0000003000000000,
};
uint64 TsumeHash::HI_BIT_TBL[3]={
0x0000000000000000,
0x0000004000000000,
0x000000c000000000,
};
uint64 TsumeHash::CalcHand(int Motigoma[])
{
return
FU_BIT_TBL[Motigoma[FU]] |
KY_BIT_TBL[Motigoma[KY]] |
KE_BIT_TBL[Motigoma[KE]] |
GI_BIT_TBL[Motigoma[GI]] |
KI_BIT_TBL[Motigoma[KI]] |
KA_BIT_TBL[Motigoma[KA]] |
HI_BIT_TBL[Motigoma[HI]];
}
void TsumeHash::Add(uint64 KyokumenHashVal,uint64 HandHashVal,int Motigoma[],int mate,Te te)
{
uint64 NowHashVal=KyokumenHashVal;
uint64 Hand=CalcHand(Motigoma);
int i;
for(i=0;i<RETRY_MAX;i++) {
if (HashTbl[NowHashVal&TSUME_HASH_AND].HashVal==0) {
TsumeVal &t=HashTbl[NowHashVal&TSUME_HASH_AND];
t.HashVal=KyokumenHashVal;
t.Motigoma=Hand;
t.mate=mate;
t.NextEntry=0;
t.te=te;
break;
} else if (HashTbl[NowHashVal&TSUME_HASH_AND].HashVal==KyokumenHashVal) {
if (HashTbl[NowHashVal&TSUME_HASH_AND].Motigoma==Hand) {
// 持ち駒も含めて同一局面
} else {
// 盤上が同一で、持ち駒が違うものが登録済み
while(HashTbl[NowHashVal&TSUME_HASH_AND].NextEntry!=0) {
NowHashVal=HashTbl[NowHashVal&TSUME_HASH_AND].NextEntry;
if (HashTbl[NowHashVal&TSUME_HASH_AND].Motigoma==Hand) {
// 持ち駒も含めて同一局面
break;
}
}
}
if (HashTbl[NowHashVal&TSUME_HASH_AND].Motigoma==Hand) {
TsumeVal &t=HashTbl[NowHashVal&TSUME_HASH_AND];
t.HashVal=KyokumenHashVal;
t.Motigoma=Hand;
t.mate=mate;
t.te=te;
break;
}
TsumeVal &pre=HashTbl[NowHashVal&TSUME_HASH_AND];
NowHashVal=KyokumenHashVal^HandHashVal;
for (int j=0;j<RETRY_MAX;j++) {
if (HashTbl[NowHashVal&TSUME_HASH_AND].HashVal==0) {
TsumeVal &t=HashTbl[NowHashVal&TSUME_HASH_AND];
t.HashVal=KyokumenHashVal;
t.Motigoma=Hand;
t.mate=mate;
t.NextEntry=0;
t.te=te;
pre.NextEntry=NowHashVal&TSUME_HASH_AND;
break;
}
NowHashVal+=TSUME_HASH_SIZE/11;
}
break;
}
NowHashVal+=TSUME_HASH_SIZE/11;
}
if (i==RETRY_MAX) {
printf("OVER MAX\n");
}
}
void TsumeHash::Clear()
{
memset(HashTbl,0,sizeof(HashTbl));
}
TsumeVal* TsumeHash::FindFirst(uint64 KyokumenHashVal)
{
uint64 NowHashVal=KyokumenHashVal;
for(int i=0;i<RETRY_MAX;i++) {
if (HashTbl[NowHashVal&TSUME_HASH_AND].HashVal==KyokumenHashVal) {
return HashTbl+(NowHashVal&TSUME_HASH_AND);
}
NowHashVal+=TSUME_HASH_SIZE/11;
}
return NULL;
}
TsumeVal* TsumeHash::FindNext(TsumeVal *Now)
{
if (Now->NextEntry==0) return NULL;
return HashTbl+Now->NextEntry;
}
TsumeVal *TsumeHash::Find(uint64 KyokumenHashVal,uint64 HandHashVal,int Motigoma[])
{
uint64 CalcMotigoma=CalcHand(Motigoma);
TsumeVal *ret=FindFirst(KyokumenHashVal);
while(ret!=NULL) {
if (ret->Motigoma==CalcMotigoma) return ret;
ret=FindNext(ret);
}
return NULL;
}
// ハッシュに登録された局面で、持ち駒がより少ない局面で詰んでいる局面を探す
TsumeVal *TsumeHash::DomSearchCheckMate(uint64 KyokumenHashVal,int Motigoma[])
{
uint64 CalcMotigoma=CalcHand(Motigoma);
TsumeVal *ret=FindFirst(KyokumenHashVal);
while(ret!=NULL) {
if (ret->Motigoma==CalcMotigoma) {
if (ret->mate!=1) {
return NULL;
}
}
// ハッシュに登録されているより持ち駒が多く、ハッシュで詰みなら詰み
if ((ret->Motigoma & CalcMotigoma)==ret->Motigoma && ret->mate==1) {
return ret;
}
ret=FindNext(ret);
}
return NULL;
}
int Kyokumen::Mate(int SorE,int maxDepth,Te &te)
{
Te teBuf[10000]; // 深さ30程度までなら十分すぎる大きさ
TsumeVal *p;
if ((p=TsumeHash::Find(KyokumenHashVal,HandHashVal,Hand+SorE))!=NULL) {
if (p->mate==1) {
te=p->te;
}
return p->mate;
}
int ret;
for(int i=1;i<=maxDepth;i+=2) {
if (ret=CheckMate(SorE,0,i,teBuf,te)) {
break;
}
}
// 0:不明
// 1:詰んだ
// -1:不詰み
return ret;
}
int Kyokumen::CheckMate(int SorE,int depth, int depthMax, Te *checks,Te &te)
{
int teNum = MakeChecks(SorE,checks);
if (teNum == 0) {
TsumeHash::Add(KyokumenHashVal,HandHashVal,Hand+SorE,-1,0);
return -1; //詰まない
}
TsumeVal *p;
if ((p=TsumeHash::DomSearchCheckMate(KyokumenHashVal,Hand+SorE))!=NULL) {
te=p->te;
return 1; //詰んだ
}
int valmax = -1;
for (int i = 0; i < teNum; i++) {
Kyokumen kk(*this);
kk.Move(SorE,checks[i]);
int val = kk.AntiCheckMate(SorE^0x30, depth+1, depthMax, checks+teNum);
if (val > valmax) valmax = val;
if (valmax == 1) {
te=checks[i];
break; //詰んだ
}
}
if (valmax == 1) { //詰んだ
TsumeHash::Add(KyokumenHashVal,HandHashVal,Hand+SorE,1,te);
} else if (valmax == -1) { //本当に詰まなかった
TsumeHash::Add(KyokumenHashVal,HandHashVal,Hand+SorE,-1,0);
}
return valmax;
}
int Kyokumen::AntiCheckMate(int SorE,int depth, int depthMax, Te *antichecks)
{
Te te;
int teNum=MakeLegalMoves(SorE,antichecks);
int i=0;
int valmin = 1;
if (teNum == 0) {
return 1;
}
if (depth >= depthMax+1) return 0; //長さの限界詰みは不明
for (i = 0; i < teNum; i++) {
Kyokumen k(*this);
k.Move(SorE,antichecks[i]);
int val = k.CheckMate(SorE^0x30, depth+1, depthMax, antichecks+teNum,te);
if (val < valmin) valmin = val;
if (valmin == -1) break; // 詰まなかった
if (valmin == 0) break; // 詰まなかった
}
return valmin;
}
※２ 詰めろ…放置しておくと、次に玉が詰む状況のこと。※３ 必至（ひっし）…次にどのように受けても玉が詰む状況のこと
詰め将棋ルーチンが出来たので、読みの最初に詰め将棋ルーチンを呼び出し、分かる範囲で詰む時には必ず詰ませることで、分かる範囲でならば勝ちを逃すことがなくなった。
これだけでもパワーアップなのだが、さらに自玉の詰みや、２手進めた局面での詰みを読むことで、「詰めろ」をかけたり、「詰めろ」から逃れたりできるようになる。
αβ法に組み込むと、以下のようになる。
int Sikou::NegaAlphaBeta(int SorE,KyokumenKomagumi &k,int alpha,int beta,int depth,int depthMax,bool bITDeep)
{
:
Te teBuf[600];
int retval=-INFINITE-1;
if (depth<2 && k.Mate(SorE,7,teBuf[0])==1) {
Best[depth][depth]=teBuf[0];
Best[depth][depth+1]=Te(0);
retval=INFINITE+1;
goto HashAdd;
}
int teNum;
if (depth==0) {
:
k.EvaluateTe(SorE,teNum,teBuf);
for(i=0;i30) && i>0 && retval>-INFINITE) {
break;
}
:
}
retval>-INFINITEになるまで、手を探し続けることで、一応「詰めろ」から逃れることができるようになったはず…である。
ただし、逃れ方がマズい可能性がある。
たとえば、王手をかければその一瞬は「詰めろ」から逃れられる。しかし、たとえば、王手をかけた駒をタダで取られれば、駒を損しただけで、（一応手数は伸びているが）何の意味もないことになる。
これには、「詰めろ」がかかっているときに無駄な王手を連続しないなどの高度な処理が必要になってくる。
これは少し高度で、本書の範囲を出ると思われるので、インターネットのホームページなどを参考にしてほしい。
2015年 10月 追記：KFEndの作者様のページ、Inside KFEndに詳しく載っていたのだが、現在はKFEndのページそのものがなくなっているようである…。
ここまでのソースコードは、chapter09-02.zipに収録した。
なお、前の方の章でバグを取ったのに、後の方の章でデグレードしている、なんてことが沢山あるので、気を付けて下さいｗ