読者です 読者をやめる 読者になる 読者になる

daruma3940の日記

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

KillerMoveについてなのじぇ。

コンピューター将棋

f:id:daruma3940:20160520223745p:plain
コンピューター将棋ではkiller moveという探索の効率化の手法が用いられているのじぇ。
この前Aperyの探索部についての解説の時に取り上げられなかったのでここで取り上げるのじぇ。
まあ取り上げなかったのは探索部に就いてというよりも指し手生成のorderingについての手法なので探索部の記事ではあえて取り上げなかったということもあるのじぇ。

f:id:daruma3940:20160521003616p:plain
余興はいいからさっさと始めなさい!

f:id:daruma3940:20160520223745p:plain
わ...わかったのじぇ。(きょうのありしゅはごきげんななめなのじぇ...)

killer_moveについてざっくり説明すると
これは現在局面の兄弟ノード(今の局面の一手前の局面で別の指し手を指した時の局面を兄弟ノードという)において
β値を超える価値を持った”良い手”を記憶しておいてその指し手を現在局面でも指し手のordering上位に持ってきて最初の方に調べるということをすれば
現局面でもβ値を超える可能性が高いので現局面をbeta-cutでき、探索量を減らせるかもしれないという探索の効率化を図る手法なのじぇ。

f:id:daruma3940:20160520223530p:plain
ゆゆっ!?ちょっとまってね!!
beta値を超えてしまうような指し手は良い手であるわけがないよ!
そのような指し手はあまりにも良すぎて実際に指されることはないはずだよ!
f:id:daruma3940:20160520223530p:plain
本当に良い手はbeta値以下でalpha値を更新するような指し手であるはずだよ!

f:id:daruma3940:20160520223745p:plain
その通りなのじぇれいみゅ。
しかしここでは探索の効率化という観点で”いい手”という言葉を使ったのじぇ。
探索の効率化の観点で言うと、beta値を超えてしまうような指し手が現れるとその局面はbeta-cutされてしまい、もう指し手を用意して探索する必要が無いので探索量を減らすことができるのじぇ!
その意味での”いい手”なのじぇ!

f:id:daruma3940:20160520223530p:plain
なるほどゆっくり理解したよ!!

f:id:daruma3940:20160520223745p:plain
AperyのkillermoveはSearchStack構造体に格納されているのじぇ。

//探索時のスタック(探索用の変数、指して生成用の変数、評価関数差分計算用の変数が格納されている)
struct SearchStack {
	SplitPoint* splitPoint;
	Ply ply;
	Move currentMove;
	Move excludedMove; // todo: これは必要?

	Move killers[2];//これがkillermove!!!!!

	Depth reduction;
	Score staticEval;
	bool skipNullMove;
	EvalSum staticEvalRaw; // 評価関数の差分計算用、値が入っていないときは [0] を ScoreNotEvaluated にしておく。
						   // 常に Black 側から見た評価値を入れておく。
						   // 0: 双玉に対する評価値, 1: 先手玉に対する評価値, 2: 後手玉に対する評価値
};

f:id:daruma3940:20160520223745p:plain
なぜkillermoveが2つあるのかはこの記事を見ればわかるのじぇ。
qiita.com
まあざっくりというと良質なkiller_moveを残しておくためということでいいと思うのじぇ。

f:id:daruma3940:20160520223745p:plain
これが指し手をphaseごとに生成するクラスMovePickerで用いられているのじぇ。

//次の差し手フェーズに移動 PH_TacticalMoves0など
//***************************************(ここで差し手も生成されている!!)*****************************
void MovePicker::goNextPhase() {
	currMove_ = firstMove(); // legalMoves_[0] は番兵(0は使わないということ。指し手は1から格納されていく)
	++phase_;

	switch (phase()) {

        //[駒取りと歩の成の指し手を生成するphase
	case PH_TacticalMoves0: case PH_TacticalMoves1:
		lastMove_ = generateMoves<CapturePlusPro>(currMove(), pos());
		scoreCaptures();
		return;

		//====================================
		//ここでkillermoveが次に返す指し手のlistに入れられる
		//====================================
	case PH_Killers:
		currMove_ = killerMoves_;
		lastMove_ = currMove() + 2;
		return;
        
      //(省略)

killer_moveはAperyでは[駒取りと歩の成の指し手を生成するphase]の次のphaseで生成されているのでorderingの優先度としては中位なのじぇ。


f:id:daruma3940:20160520223745p:plain
killer_moveが探索中にどのように更新されているのかを見ていくのじぇ。

//TTに保存されていた指し手からkillermoveの生成
ss->currentMove = ttMove; // Move::moveNone() もありえる。

		if (beta <= ttScore//TTによるさしての値がbeta値を超えた
			&& !ttMove.isNone()
			&& !ttMove.isCaptureOrPawnPromotion()//駒取りと歩の成ではない
			&& ttMove != ss->killers[0])//killers[0]とは異なる指し手
		{
			//killermoveの更新
			ss->killers[1] = ss->killers[0];
			ss->killers[0] = ttMove;
		}
		//beta cut
		return ttScore;
	}
//探索中にbeta値を超えた指し手からkillermoveを生成
	if (beta <= bestScore) {
		// failed high
		tt.store(posKey, scoreToTT(bestScore, ss->ply), BoundLower, depth,
				 bestMove, ss->staticEval);

		if (!bestMove.isCaptureOrPawnPromotion() && !inCheck) {
			if (bestMove != ss->killers[0]) {
				ss->killers[1] = ss->killers[0];
				ss->killers[0] = bestMove;
			}

f:id:daruma3940:20160520223745p:plain
ここでkillermoveに駒取りと歩の成を含めないのはもうお分かりだと思うけどkillermoveは[駒取りと歩の成の指し手を生成するphase]の次のphaseで用意されるので探索する指し手に重複が無いようにするためだと考えられるのじぇ。


f:id:daruma3940:20160520223530p:plain
でもなんでkillermoveは駒取りと歩の成を探索した後に探索するのかな?
別に駒取りと歩の成の前でもいいはずだよ!

f:id:daruma3940:20160520223745p:plain
それはやっぱり駒取りと歩の成はそれ以外の指し手に対して十分beta-cutする可能性が高いからだとおもうのじぇ。
駒取りと歩の成以外の指し手というbeta-cutする可能性が低いと考えられる指し手の集合から抜き出して来ることにこそkillermoveをわざわざ用意する意義があると思うのじぇ。

まあkiller moveについてはこんなもんなのじぇ。