詰め探索を利用 - 小宮日記

久しぶりに詰め将棋コードをさわりました。
挙動が変な証明数探索はやめて、
王手の手数、受けの手数を探索深さ引き算する探索深さ制御の反復進化でコードを作ってみました。
無駄合いの処理はいれてませんが、７手探索は0.05秒ぐらいで探索できるのでわりと速いです。
これを使って、初回時に、頓死する手を見つけたらハッシュに登録して、指さないようにしてみました。
いまいち信用できませんが……
あと、詰めろをやろうと思って、
打ってみて、相手がパスしたら、次に詰めがある手を、「詰めろ」とみなすというのもやってみましたが、
パスせずに受けると、ただ損するような手を「詰めろ」とみなしてしまうので、使えない方法でした(^^;
さすがに探索中に詰めルーチンを呼ぶのは、全幅探索ではもったいないかと思います。

以下のような探索深さではなくて、受け手数を、パラメーター(cn)から引いて探索すると、
王手の受けの手数が多いものは、あまり有望じゃない変化なので、その手数を引く（探索削減）
さっき書いてたコードは、思いっきり間違ってたので修正(^^;　書かないと気づかなかった。恐ろしい。
と思って修正したコードがさらに間違ってた(汗
再度修正。

結局、王手の応手の数を引くだけじゃなくて、王手の数も引かないとだめらしい。
王手がたくさんできるのは、良いことと思うけど、証明しないといけない展開図が増える方向は探索削減しないと
収束しないからかなあ。
もうちょっとコードをリファイン。

char mateITDeep( uchar SorE )
{
	for(int cn=20;cn<=50;cn+=10) {
		ret=attack( cn,SorE,0 );
		if(ret==1) break;
	}
	return ret;
}

char attack(int cn,uchar SorE,int depth )
{
//hash確認
	HashEntry e = HashTbl[hashVal & HASHMASK];
	if ( e.hashVal==hashVal && e.SorE==SorE && e.ret!=0 ) return e.ret;

	char ret=-1;

	Te t[600];
	int tp=makeMoves(SorE,t);
	if(tp==0) goto AddHash; //手が無いなら不詰み

//王手の手数を数える
	int c=0;
	for(int i=0;i< tp ;i++) {
		moveMateFast( t[i],SorE );
		if( !isMate(enemy(SorE)) ) {
			undoMateFast( t[i],SorE );
			t[i].to=0;
		}
		else {
			undoMateFast( t[i],SorE );
			c++;
		}
	}
	if(cn-c<0) return 0;//不明

	for(int i=0;i< tp ;i++) {
		if(t[i].to==0) continue;
		push();moveFast( t[i],SorE );
		int v=defense(cn-c,enemy(SorE),depth+1 );
		undoFast( t[i],SorE );pop();

		if(v>ret) ret=v;
		if(ret==1) break;
	}

AddHash:
//ハッシュ登録
	if(ret==0) return 0;

	e.hashVal = hashVal;
	e.ret=ret;
	e.SorE=SorE;
	HashTbl[hashVal & HASHMASK]=e;
	return ret;
}

char defense(int cn,uchar SorE,int depth )
{
//hash確認
	HashEntry e = HashTbl[hashVal & HASHMASK];
	if ( e.hashVal==hashVal && e.SorE==SorE && e.ret!=0 ) return e.ret;

	char ret=1;

	Te t[100];
	int tp=makeMoves(SorE,t);
	if(tp==0) goto AddHash;//手が無いなら詰み


//受けの手数を数える
	int c=0;
	for(int i=0;i< tp ;i++) {
		moveMateFast( t[i],SorE );
		if( isMate(enemy(SorE)) ) {
			undoMateFast( t[i],SorE );
			ret=0;goto AddHash;//相手を王手できる応手があれば不明
		}
		else c++;
		undoMateFast( t[i],SorE );
	}
	if(cn-c<0) return 0;//不明

	for(int i=0;i< tp ;i++) {
		push();moveFast( t[i],SorE );
		int v=attack(cn-c,enemy(SorE),depth+1 );
		undoFast( t[i],SorE );pop();

		if(v<ret) ret=v;
		if(ret==-1) break;//詰まなかった
		if(ret==0) break;//詰まなかった
	}

AddHash:
//ハッシュ登録
	if(ret==0) return 0;

	e.hashVal = hashVal;
	e.ret=ret;
	e.SorE=SorE;
	HashTbl[hashVal & HASHMASK]=e;
	return ret;
}

以下、７手詰めを解いた場合

▼持駒v歩十四v香三v桂三v銀二v金三v角二v飛二
 ９ ８ ７ ６ ５ ４ ３ ２ １ 　 ９８７６５４３２１
---------------------------+　 ------------------+
 ・ ・ ・ ・ ・ ・ ・ ・ ・|一  0 0 0 0 0 0 0 0 0|一
 ・ ・ ・ ・ ・ ・ ・ ・ ・|二  0 0 0 0 0 0 0 0 0|二
 ・ ・ ・ ・ ・ ・ ・ ・ ・|三  0 0 0 0 0 0 0 0 0|三
 ・ ・ ・ ・ ・ ・ ・ ・ ・|四  0 0 0 0 0 0 0 0 0|四
 ・ ・ ・ ・ ・ ・ ・ ・ ・|五  0 1 1 1 1 1 1 0 0|五
 ・ ・ と ・ ・ 杏 ・ ・ ・|六  0 1 0 1 1 0 0 0 0|六
 ・ ・ ・ ・ ・ ・v圭 ・ ・|七  0 0 1 0 0 0 0-1 0|七
 ・ ・v歩 ・ ・ ・ ・ ・ ・|八  0 1-1-1 0-1-1-1 0|八
 ・ 歩 ・v玉 歩 ・ ・ ・ ・|九  0 0-2 0-1 0 0 0 0|九
---------------------------+　 ------------------+
△持駒 銀二 金

#020   0.00s +0 (135)
#030   0.02s +1 (268)
詰み(268):△58銀打▼59王△49金打▼68王△77銀打▼79王△88銀