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

daruma3940の日記

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

GainとHistoryについて

f:id:daruma3940:20160520223745p:plain
ゆっくりするのじぇ...頭がいたいのじぇ...
f:id:daruma3940:20160521003616p:plain
どうしたの?だいじょうぶ?まりちゃ?
f:id:daruma3940:20160520223745p:plain
昨日友達と飲みに行って運動部のやつに飲まされて倒れて吐いてその上に倒れて全身ゲロまみれになったのじぇ..そのお酒のせいで頭がいたいのじぇ...
f:id:daruma3940:20160520223530p:plain
お酒は程々にね!!!
f:id:daruma3940:20160709192554j:plain
無理は禁物だよ!!!!
f:id:daruma3940:20160520223745p:plain
今回はApery-twigの探索部と指し手生成部に関連のあるHistoryとGainクラスについて、そして可能であれば指し手生成部の指し手オーダリングについてしゃべるつもりなのじぇ。
f:id:daruma3940:20160709192554j:plain
どんなクラスかはわからないけど指し手生成部と探索部に関係するようなクラスってことはなかなか重要な役割を担っていると言えそうだね~
f:id:daruma3940:20160520223745p:plain
Historyについては指し手のオーダリングでかなり重要な役割を担っていると言えるけど
gainの方はfutility cutのscore based pruningでしか使われていないのじぇ。
これはせっかくgainを用意したのにもったいないと思うのじぇ。
これを使ってうまく指し手の枝切りができる方法がないか独自性の名のもとに考えてみるのもいいかもしれないのじぇ。
f:id:daruma3940:20160520223745p:plain
GainとHistoryについてまずはざっくりと説明するのじぇ

Gain

Gainとは
とある指し手を指した時にその指し手を指す前と指す後でどれだけ静的評価値が変動したのかを格納するテーブルを持つクラス。
futility cutにおけるscore based pruningで用いられる。

History

Historyとは
ある局面でbeta-cutが起こった時に
その局面で探索をした指し手について、指し手がbetacutを起こすような良い手であればその指し手とbeta-cutが起こった時の残り深さに依存する正の値を格納し、
beta-cutを起こさないような指してはその指し手と残り深さに依存する負の値を格納するテーブルを持つクラス。
指し手orderingではbeta-cutを起こす可能性の高い指し手から返していきたいのでこの値をorderingに利用する。

f:id:daruma3940:20160709192554j:plain
gainもhistoryも指し手と値をペアにして格納するという点で似てるね..
f:id:daruma3940:20160520223745p:plain
そうなのじぇ!HistoryもGainも元は同じ構造体テンプレートStatsからできているのじぇ!

using History = Stats<false>;
using Gains   = Stats<true>;

f:id:daruma3940:20160520223530p:plain
ほんとだ!
f:id:daruma3940:20160520223745p:plain
このStats構造体の中身はこんな感じなのじぇ。

//Gain==false であればこれはHistory
template <bool Gain>
class Stats {
public:
	static const Score MaxScore = static_cast<Score>(2000);

	void clear() { memset(table_, 0, sizeof(table_)); }


	Score value(const bool isDrop, const Piece pc, const Square to) const {
		assert(0 < pc && pc < PieceNone);
		assert(isInSquare(to));
		return table_[isDrop][pc][to];
	}


	//tableの内容をupdateする
	void update(const bool isDrop, const Piece pc, const Square to, const Score s) {

		if (Gain) {
			//gainには絶対値的にあまり大きな負の値は入らない?
			table_[isDrop][pc][to] = std::max(s, value(isDrop, pc, to) - 1);
		}
		//historyはこっち
		else if (abs(value(isDrop, pc, to) + s) < MaxScore) {
			table_[isDrop][pc][to] += s;
		}
	}



private:
	// [isDrop][piece][square] とする。
	Score table_[2][PieceNone][SquareNum];//0で初期化される
};

f:id:daruma3940:20160520223745p:plain
ここで一番大切なのがtable_なのじぇ!ここに指し手の種類に対応した値(GainかHistoryかによって値の内容、意味は変わる)が格納されるのじぇ!

f:id:daruma3940:20160520223745p:plain
それじゃあGain,Historyがどのように用意されて使われているか見ていこうじぇ
まずは使われている場所の少ないGainの方から見ていこうじぇ
Gainはこのようにして用意されているのじぇ

// step5
	// evaluate the position statically

	eval = ss->staticEval = evaluate(pos, ss); //KPP の差分評価の為に、指し手を指すごとに評価関数を呼ぶ必要がある。

(省略)
// 一手前の指し手について、history を更新する。
	// todo: ここの条件はもう少し考えた方が良い。
	if ((move = (ss-1)->currentMove) != Move::moveNull()
		&& (ss-1)->staticEval != ScoreNone
		&& ss->staticEval != ScoreNone
		&& !move.isCaptureOrPawnPromotion() // 前回(一手前)の指し手が駒取りでなかった。
		)
	{
		const Square to = move.to();
		//TODO gain とはなに? (moveで一手進めた時に静的評価値がどれだけ動いたのかを格納)(futiltyで使用される)
		//gainのtableのupdate
		gains.update(move.isDrop(), pos.piece(to), to, -(ss-1)->staticEval - ss->staticEval);
	}

gainのupdateってところでgainのtableが更新されているのじぇ
tableにはmoveで一手進めた時に静的評価値がどれだけ動いたのかが格納されているのじぇ

f:id:daruma3940:20160520223745p:plain
またgainはこのようにして使われているのじぇ

               // ーーーーーーーーーーーーーーーーーーーーーーstep13
		// futility pruning

               // score based pruning
			const Depth predictedDepth = newDepth - reduction<PVNode>(depth, moveCount);
			// gain を 2倍にする。(gainは以前の局面からこの指し手を打ったことでどれだけ評価血が変化したかを表す正の値のtable)
			const Score futilityScore = ss->staticEval + futilityMargin(predictedDepth, moveCount)
				+ 2 * gains.value(move.isDrop(), colorAndPieceTypeToPiece(pos.turn(), move.pieceTypeFromOrDropped()), move.to());

			if (futilityScore < beta) {
				bestScore = std::max(bestScore, futilityScore);
				if (SPNode) {
					splitPoint->mutex.lock();
					if (splitPoint->bestScore < bestScore) {
						splitPoint->bestScore = bestScore;
					}
				}
				continue;
			}

f:id:daruma3940:20160520223745p:plain
次はHistoryなのじぇ

このようにして用意されているのじぇ

	//探索中にbeta値を超えた指し手からkillermoveを生成
	// historyも更新する
	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;
			}

			//これがscoreとしてhistoryのtableに格納される
			//historyは指し手orderingで用いられる。
			//depthは残り深さ。残り深さが大きい方が探索の浅いところでの枝切りということなので価値が高い
			const Score bonus = static_cast<Score>(depth * depth);

			const Piece pc1 = colorAndPieceTypeToPiece(pos.turn(), bestMove.pieceTypeFromOrDropped());

			history.update(bestMove.isDrop(), pc1, bestMove.to(), bonus);//betacutできた指し手のhistoryを正の方向に引き上げる。

			for (int i = 0; i < playedMoveCount - 1; ++i) {
				const Move m = movesSearched[i];
				const Piece pc2 = colorAndPieceTypeToPiece(pos.turn(), m.pieceTypeFromOrDropped());

				history.update(m.isDrop(), pc2, m.to(), -bonus);//betacutしなかった指し手のhistoryを引き下げる
			}
		}
	}

beta-cutされた指し手のtebleには+bonus
beta-cutされなかった指し手には-bonusが格納されるのじぇ
ここでbonusとは探索の残り深さをdepthとするとdepth * depthで表されるのじぇ。
残り深さが大きい方が探索の浅いところでの枝切りということ(つまり素晴らしい指し手)なのでbonusを大きくしようという考え方なのじぇ

f:id:daruma3940:20160520223745p:plain
次にHistoryはこのようにして使われているのじぇ

//駒取りと歩の成以外の指し手についてのscoreをつける。
template <bool IsDrop> void MovePicker::scoreNonCapturesMinusPro() {
	for (MoveStack* curr = currMove(); curr != lastMove(); ++curr) {
		const Move move = curr->move;

		//指し手の点数はhistoryによってつけられる。
		curr->score =
			history().value(IsDrop,
							colorAndPieceTypeToPiece(pos().turn(),
													 (IsDrop ? move.pieceTypeDropped() : move.pieceTypeFrom())),
																												move.to());
	}
}

このようにして指し手について点数をつけていくのに使われるのじぇ。
この点数は指し手を並べ替えるorderingのための点数で評価値の値とは関係ないのじぇ。


f:id:daruma3940:20160520223745p:plain
記事の内容はわかりにくいと思うけどこのブログは所詮まりちゃの備忘録的な記事なのでかんべんして欲しいのじぇ
今回はきりが良いのでここまでにしておくのじぇ