daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

gainとhistoryを用いた探索手法を考えようじぇ!

前回
daruma3940.hatenablog.com
の続き
f:id:daruma3940:20160520223745p:plain
ゆっくりするのじぇ。前回Aperyの探索部とmovepickerで用いられていたGainとHistoryについて解説したのじぇ。
f:id:daruma3940:20160709192554j:plain
Gainは
前回指された指し手でどれだけ評価値が動いたのかということを格納するための構造体だったよね。
f:id:daruma3940:20160521003616p:plain
Historyは
beta-cutを引き起こす指し手に高い点数をつけてmovepickerで先に高い点数をつけられた指し手を返すためにその点数を格納する構造体だったわね。

f:id:daruma3940:20160520223745p:plain
これらの構造体(特にGain)はApery-twigではあまり使われていない、陽の目を浴びていない構造体だったので
これらを使って探索をする手法を考えて陽の目を見せてやろう!!!という作戦なのじぇ!!!!

f:id:daruma3940:20160520223530p:plain
これはきっと独自性だよぉ!

f:id:daruma3940:20160520223745p:plain
そうなのじぇ!独自性なのじぇ!ようやっと自分のソフトにも独自性を加える事のできる時が来たのじぇ!!!

f:id:daruma3940:20160520223745p:plain
まりちゃがHistory,Gainを使った探索手法を使えると思ったところは探索関数のここなのじぇ!

bool fullDepthSearch = (PV && moveCount == 1);

if (!fullDepthSearch)
{
	// nonPVならざっくり2手ぐらい深さを削っていいのでは..(本当はもっとちゃんとやるべき)→ここをgainやhistoryで何とかできるのでは?
	Depth R = ONE_PLY * 2;

	//nullwindow探索
	value = depth - R < ONE_PLY ?
		-qsearch<NonPV>(pos, -beta, -alpha, depth - R) :
		-search<NonPV>(pos,ss+1, -(alpha + 1), -alpha, depth - R);

	//alpha値を更新できそうなのでちゃんとした探索を行う
	fullDepthSearch = value > alpha;
}

if (fullDepthSearch) {
	value = depth - ONE_PLY < ONE_PLY ?
		-qsearch<PV>(pos, -beta, -alpha, depth - ONE_PLY) :
		-search<PV>(pos, ss + 1, -beta, -alpha, depth - ONE_PLY);
}

f:id:daruma3940:20160520223745p:plain
ここでは今考えている指し手がPV(principal variation:読み筋)か現局面一手目の指し手であればちゃんと探索して
そうでないあまり有望ではない指し手であれば探索を簡単にしてしまおうということを考えているところなのじぇ。


今のコードのままでは
有望な指し手かどうかの判定もかなり厳しいし、
有望でない指し手の先読みを減らす量もテキトーにしか決めることができていないし、
有望な指し手は深く読む!ということもできていないのじぇ。
f:id:daruma3940:20160520223530p:plain
そこでhistoryとgainを用いてここをちゃんとしようということだね!!!
f:id:daruma3940:20160520223745p:plain
その通りなのじぇ!
f:id:daruma3940:20160520223745p:plain
まずは改良その1!!
gainとHistoryのtableを
table[駒打ちか][動かす駒種][移動先]から
table[駒成か][駒打ちか][動かす駒種][移動先]
に変更して精度を高めようじぇ!!!

f:id:daruma3940:20160520223745p:plain
改良その2
historyの値がある程度よりも小さい指しては先読みの量を減らそうじぇ!
逆にhistoryの値が正の指してはfulldepthsearchにして先読みの量を増やそうじぇ!

f:id:daruma3940:20160520223745p:plain
改良その3
gainの値をsearchstackに格納し
2手前のゲイン、4手前のゲイン(自分の手番の指し手によるゲイン)が連続して負(後手の場合は連続して正)になっていればそのノードの探索深さを減らそうじぇ!


f:id:daruma3940:20160520223745p:plain
ざっとこんな感じなのじぇ

なんか局面の実現確率探索に近いものを感じるのはまりちゃだけかだじぇ?

f:id:daruma3940:20160520223745p:plain
あともう一つまりちゃがこれをしたいなと思っているのは
kkpの値から手番ごとの終盤度を計算して、終盤度がある程度以上の手番はmovepickerで最初に王手をかける指し手を生成するようにして、擬似詰めルーチンを作ってそれで探索をすることもしてみたいのじぇ!
df-pnとかを実装するのは大変そうだという考えなのじぇ!


f:id:daruma3940:20160520223745p:plain
夏休み前に時間がかかりそうな作業を思いついておけてよかったのじぇ!夏休みはこれをがんばるじぇ!