Edax AVX - bitboard 以外の最適化

(†は外部サイトへのリンク)


評価関数 (eval.c, eval_sse.c, midgame.c)

edax eval patters logisttello eval patters Edax の評価関数はこちら†に詳しい解説があるが、基本的には Logistello† のそれを引き継いでおり、盤面を複数のパターンに分解し、それぞれのパターンに対し、多数の棋譜を元に事前にロジスティック回帰で求めておいた評価値表を引いて、その総和を評価値としている。
Figure 1 は Logistello で用いられているパターンだが、Edax では 2x5-corner を省き、右の図の corner+block, angle+X を追加している。 diag-8 は 2 か所、その他は各 4 か所にあるので、合計 46 要素になる。
/** number of (unpacked) weights */
static const int EVAL_N_WEIGHT = 226315;

/** number of plies */
static const int EVAL_N_PLY = 61;

/** eval weights */
short ***EVAL_WEIGHT;

// allocation
EVAL_WEIGHT = (short***) malloc(2 * sizeof (*EVAL_WEIGHT));
if (EVAL_WEIGHT == NULL) fatal_error("Cannot evaluation weights.\n");
EVAL_WEIGHT[0] = (short**) malloc(2 * EVAL_N_PLY * sizeof (**EVAL_WEIGHT));
if (EVAL_WEIGHT[0] == NULL) fatal_error("Cannot evaluation weights.\n");
EVAL_WEIGHT[1] = EVAL_WEIGHT[0] + EVAL_N_PLY;
EVAL_WEIGHT[0][0] = (short*) malloc(2 * EVAL_N_PLY * EVAL_N_WEIGHT * sizeof (***EVAL_WEIGHT));
if (EVAL_WEIGHT[0][0] == NULL) fatal_error("Cannot evaluation weights.\n");
EVAL_WEIGHT[1][0] = EVAL_WEIGHT[0][0] + EVAL_N_PLY * EVAL_N_WEIGHT;
for (ply = 1; ply < EVAL_N_PLY; ply++) {
	EVAL_WEIGHT[0][ply] = EVAL_WEIGHT[0][ply - 1] + EVAL_N_WEIGHT;
	EVAL_WEIGHT[1][ply] = EVAL_WEIGHT[1][ply - 1] + EVAL_N_WEIGHT;
}
オリジナルのコードで表の実体をアロケートしているのは 16 行の EVAL_WEIGHT[0][0] で、55MB の巨大な配列になっている。
(なお配列の各要素をアクセスするためにポインターの配列を用意しているが (Java の影響?)、 乗算をメモリ参照に代えているだけでほとんど意味がなく、最適化後は通常の配列アクセスに直している。)
対称形を省いた 13.6MB のファイル eval.dat から、ここに評価値表を読み込んでいる。

各パターンの配列は各桁が白、黒、空きに対応する3進数をインデックスにして参照される。
評価値を求める際には 46 要素のインデックスを用いて表を引くことになるが、このインデックスの生成は処理が重いため、 盤面に対応するインデックスの配列 eval feature を保持していて、盤面の更新と同期して変化したマスの分を更新している。

	score = w[f[ 0]] + w[f[ 1]] + w[f[ 2]] + w[f[ 3]]
	  + w[f[ 4]] + w[f[ 5]] + w[f[ 6]] + w[f[ 7]]
	  + w[f[ 8]] + w[f[ 9]] + w[f[10]] + w[f[11]]
	  + w[f[12]] + w[f[13]] + w[f[14]] + w[f[15]]
	  + w[f[16]] + w[f[17]] + w[f[18]] + w[f[19]]
	  + w[f[20]] + w[f[21]] + w[f[22]] + w[f[23]]
	  + w[f[24]] + w[f[25]]
	  + w[f[26]] + w[f[27]] + w[f[28]] + w[f[29]]
	  + w[f[30]] + w[f[31]] + w[f[32]] + w[f[33]]
	  + w[f[34]] + w[f[35]] + w[f[36]] + w[f[37]]
	  + w[f[38]] + w[f[39]] + w[f[40]] + w[f[41]]
	  + w[f[42]] + w[f[43]] + w[f[44]] + w[f[45]]
	  + w[f[46]];
各 ply ( = 60 - n_empties) に対する Eval weight は 226315 個の short の配列で宣言されているが、その中身は前述の評価パターン 12 種類に対する評価値表である。 構造体にした方が見やすいし、各要素のインデックスが 16ビットに納まるようになる(後述のベクター化の際に重要)。
f[46] は常に0であり、参照する必要はない。

typedef struct Eval_weight {
	short	C9[19683];
	short	C10[59049];
	short	S10[2][59049];
	short	S8[4][6561];
	short	S7[2187];
	short	S6[729];
	short	S5[243];
	short	S4[81];
	short	S0;
} Eval_weight;

Eval_weight (*EVAL_WEIGHT)[2][EVAL_N_PLY];

// allocation
EVAL_WEIGHT = (Eval_weight(*)[2][EVAL_N_PLY]) malloc(sizeof(*EVAL_WEIGHT));
if (EVAL_WEIGHT == NULL) fatal_error("Cannot allocate evaluation weights.\n");
	return w->C9[f[ 0]] + w->C9[f[ 1]] + w->C9[f[ 2]] + w->C9[f[ 3]]
	  + w->C10[f[ 4]] + w->C10[f[ 5]] + w->C10[f[ 6]] + w->C10[f[ 7]]
	  + w->S10[0][f[ 8]] + w->S10[0][f[ 9]] + w->S10[0][f[10]] + w->S10[0][f[11]]
	  + w->S10[1][f[12]] + w->S10[1][f[13]] + w->S10[1][f[14]] + w->S10[1][f[15]]
	  + w->S8[0][f[16]] + w->S8[0][f[17]] + w->S8[0][f[18]] + w->S8[0][f[19]]
	  + w->S8[1][f[20]] + w->S8[1][f[21]] + w->S8[1][f[22]] + w->S8[1][f[23]]
	  + w->S8[2][f[24]] + w->S8[2][f[25]] + w->S8[2][f[26]] + w->S8[2][f[27]]
	  + w->S8[3][f[28]] + w->S8[3][f[29]]
	  + w->S7[f[30]] + w->S7[f[31]] + w->S7[f[32]] + w->S7[f[33]]
	  + w->S6[f[34]] + w->S6[f[35]] + w->S6[f[36]] + w->S6[f[37]]
	  + w->S5[f[38]] + w->S5[f[39]] + w->S5[f[40]] + w->S5[f[41]]
	  + w->S4[f[42]] + w->S4[f[43]] + w->S4[f[44]] + w->S4[f[45]]
	  + w->S0;

メモリーの節減

EVAL_WEIGHT の最上位のインデックス [2] は手番が入れ替わった時に色を逆にした評価値を得るためのもので、[0] と [1] には3進数の各桁の白と黒を入れ替えたインデックスに同じ値が入っている。 基本的には偶数 ply(黒番)で [0], 奇数 ply(白番)で [1] が使われるが、途中にパスが入ると逆になる。

この使われる方の表(手番側から見た評価)だけを残すとメモリーを半減することができ、27.5MB の節約になる。 パスの時には eval feature の3進数の各桁を入れ替える必要があるが、パスの頻度は少ないし、 これも表引きで行えば(表は各パターン共通に使えるし、既に初期化の際にも使用している)、パスの時だけならそれほど重い処理でもない。

さらには 0 か所空き (ply = 60) は石差が評価値になり、表は使用されない。 また 60 か所空きと 59 か所空きの評価値は無意味なので 58・57 か所空きの表で代用すると、計 1.3MB 節減できる。

Eval update のベクター化

Edax の評価関数では、盤面の各位置は 4 〜 7 の評価要素に影響する。 オリジナルのコードでは、盤面が変化した時に石を打った位置と返った位置が含まれる要素の eval feature を選択的に更新している。
	const CoordinateToFeature *s = EVAL_X2F + move->x;
	switch (s->n_feature) {
	default:
		feature[s->feature[6].i] -= 2 * s->feature[6].x;	// FALLTHRU
	case 6:	feature[s->feature[5].i] -= 2 * s->feature[5].x;	// FALLTHRU
	case 5:	feature[s->feature[4].i] -= 2 * s->feature[4].x;	// FALLTHRU
	case 4:	feature[s->feature[3].i] -= 2 * s->feature[3].x;
		feature[s->feature[2].i] -= 2 * s->feature[2].x;
		feature[s->feature[1].i] -= 2 * s->feature[1].x;
		feature[s->feature[0].i] -= 2 * s->feature[0].x;
		break;
	}
	foreach_bit (x, f) {
		s = EVAL_X2F + x;
		switch (s->n_feature) {
		default:
			feature[s->feature[6].i] -= s->feature[6].x;	// FALLTHRU
		case 6:	feature[s->feature[5].i] -= s->feature[5].x;	// FALLTHRU
		case 5:	feature[s->feature[4].i] -= s->feature[4].x;	// FALLTHRU
		case 4:	feature[s->feature[3].i] -= s->feature[3].x;
			feature[s->feature[2].i] -= s->feature[2].x;
			feature[s->feature[1].i] -= s->feature[1].x;
			feature[s->feature[0].i] -= s->feature[0].x;
			break;
		}
	}
AVX2 では一度に 16 ワードの 16 ビット変数を更新できるので、46 の eval feature をすべて更新するのに3命令しかかからない。 場合分けも不要だし、計算途中の 46 の eval feature はレジスターに保持できる。 ついでに(後述の、eval feature を復元するために保存する代わりに)更新後の eval feature を別変数に保存することも同コストでできる。
AVX2 が使えない場合、SSE2 / Neon だとステップは倍になるが、それでも十分メリットがある。
intrinsic を使わずにループで書いても、コンパイラが自動ベクトル化する可能性もある。

typedef union {
	unsigned short us[48];
	unsigned long long ull[12];	// SWAR
	__m128i	v8[6];
	__m256i	v16[3];
} EVAL_FEATURE_V;

	__m256i	f0 = _mm256_sub_epi16(eval_in->feature.v16[0], _mm256_slli_epi16(EVAL_FEATURE[x].v16[0], 1));
	__m256i	f1 = _mm256_sub_epi16(eval_in->feature.v16[1], _mm256_slli_epi16(EVAL_FEATURE[x].v16[1], 1));
	__m256i	f2 = _mm256_sub_epi16(eval_in->feature.v16[2], _mm256_slli_epi16(EVAL_FEATURE[x].v16[2], 1));

	foreach_bit(x, f) {
		f0 = _mm256_sub_epi16(f0, EVAL_FEATURE[x].v16[0]);
		f1 = _mm256_sub_epi16(f1, EVAL_FEATURE[x].v16[1]);
		f2 = _mm256_sub_epi16(f2, EVAL_FEATURE[x].v16[2]);
	}
	eval_out->feature.v16[0] = f0;
	eval_out->feature.v16[1] = f1;
	eval_out->feature.v16[2] = f2;
オリジナルでは盤面を戻すときにはアップデートと逆の操作を行っているが、打つ前の eval feature を保存しておき、それに戻す方が速い。
これは CPU による選択的アップデートの場合でも同じで、ここでも eval feature が 16 ビットだと転送量が半分になり、より効果がある。 構造体のコピーは明示しなくても、コンパイラが AVX / SSE レジスターを使ってくれる。

Gather による表引き

AVX2 ではベクトルで表引きを行う Gather 命令が追加されており、評価値の集計に利用することができる。 8 個のデータを 1 命令 (CPU 内で複数のマイクロコードに分解されるが) でロードでき、コードサイズはかなり短くなる。
Gather は Haswell, Zen 1/2 では遅い† ことが知られているが、処理の一部分なので、速くなるにしろ遅くなるにしろここではそれほど大きい影響があるわけではない。
このテーブルのデータは 16 ビットだが、Gather は 32/64 ビットデータしかサポートしていないので、32 ビットで読み半分を捨てているが、 非アラインアクセス (AVX では MOVDQA を除き速度は落ちるが許容される) が多発することと、配列外の 1 ワードをアクセスすることにも注意が必要 (ここでは S0 を最初に置いてガードを兼ねている) 。
オフセットの加算を減らすため、要素数合計が 16 ビットに納まる S8[4] と S7/6/5/4 をそれぞれ一つの配列にまとめている(少し先祖返り)。
typedef struct Eval_weight {
	short	S0;		// also acts as guard for VGATHERDD access
	short	C9[19683];
	short	C10[59049];
	short	S100[59049];
	short	S101[59049];
	short	S8x4[6561*4];
	short	S7654[2187+729+243+81];
} Eval_weight;
	enum {
		W_C9 = offsetof(Eval_weight, C9) / sizeof(short) - 1,	// -1 to load the data into hi-word
		W_C10 = offsetof(Eval_weight, C10) / sizeof(short) - 1,
		W_S100 = offsetof(Eval_weight, S100) / sizeof(short) - 1,
		W_S101 = offsetof(Eval_weight, S101) / sizeof(short) - 1
	};

	__m256i FF = _mm256_add_epi32(_mm256_cvtepu16_epi32(eval->feature.v8[0]),
		_mm256_set_epi32(W_C10, W_C10, W_C10, W_C10, W_C9, W_C9, W_C9, W_C9));
	__m256i DD = _mm256_i32gather_epi32((int *) w, FF, 2);
	__m256i SS = _mm256_srai_epi32(DD, 16);	// sign extend

	FF = _mm256_add_epi32(_mm256_cvtepu16_epi32(eval->feature.v8[1]),
		_mm256_set_epi32(W_S101, W_S101, W_S101, W_S101, W_S100, W_S100, W_S100, W_S100));
	DD = _mm256_i32gather_epi32((int *) w, FF, 2);
	SS = _mm256_add_epi32(SS, _mm256_srai_epi32(DD, 16));

	DD = _mm256_i32gather_epi32((int *)(w->S8x4 - 1), _mm256_cvtepu16_epi32(eval->feature.v8[2]), 2);
	SS = _mm256_add_epi32(SS, _mm256_srai_epi32(DD, 16));

	DD = _mm256_i32gather_epi32((int *)(w->S7654 - 1), _mm256_cvtepu16_epi32(*(__m128i *) &f[30]), 2);
	SS = _mm256_add_epi32(SS, _mm256_srai_epi32(DD, 16));

	DD = _mm256_i32gather_epi32((int *)(w->S7654 - 1), _mm256_cvtepu16_epi32(*(__m128i *) &f[38]), 2);
	SS = _mm256_add_epi32(SS, _mm256_srai_epi32(DD, 16));
	__m128i S = _mm_add_epi32(_mm256_castsi256_si128(SS), _mm256_extracti128_si256(SS, 1));

	__m128i D = _mm_i32gather_epi32((int *)(w->S8x4 - 1), _mm_cvtepu16_epi32(eval->feature.v8[3]), 2);
	S = _mm_add_epi32(S, _mm_srai_epi32(D, 16));

	S = _mm_hadd_epi32(S, S);
	sum = _mm_cvtsi128_si32(S) + _mm_extract_epi32(S, 1);

	return sum + w->S8x4[f[28]] + w->S8x4[f[29]] + w->S0;

CRC32C hash function (bit.c, board.c)

手順前後による同一局面(置換表)や、反復深化・拡幅で前の探索の評価値を残すためにハッシュ表が用いられているが、 128 ビットの盤面を 64 ビットのハッシュ値にするハッシュ関数に、オリジナルコードでは 16 種類の乱数表を用いている。
(なおハッシュ値を 64 ビットにしているのは、 Edax の過去のバージョンで盤面の一致をハッシュ値で判断していたために 衝突を最小限にしなければならなかったためで、version 4.4 からは完全読みを真に完全にするため盤面を置換表に保存するようになっており、 現在はハッシュ値の上位ビットは利用されていない。)
Edax をプロファイリングしてみると関数単位では Move generator 以外では滞在時間の上位に来るが、単純な処理でこれ以上の最適化が難しい。 (2変数で並列に xor したりしているが、コンパイラが最適化すると同じコードになるようだ。)

unsigned long long board_get_hash_code(const Board *board)
{
	unsigned long long h1, h2;
	const unsigned char *p = (const unsigned char*)board;

	h1  = hash_rank[0][p[0]];
	h2  = hash_rank[1][p[1]];
	h1 ^= hash_rank[2][p[2]];
	h2 ^= hash_rank[3][p[3]];
	h1 ^= hash_rank[4][p[4]];
	h2 ^= hash_rank[5][p[5]];
	h1 ^= hash_rank[6][p[6]];
	h2 ^= hash_rank[7][p[7]];
	h1 ^= hash_rank[8][p[8]];
	h2 ^= hash_rank[9][p[9]];
	h1 ^= hash_rank[10][p[10]];
	h2 ^= hash_rank[11][p[11]];
	h1 ^= hash_rank[12][p[12]];
	h2 ^= hash_rank[13][p[13]];
	h1 ^= hash_rank[14][p[14]];
	h2 ^= hash_rank[15][p[15]];

	return h1 ^ h2;
}
SSE4.2 と armv8.1 で、CPU 命令として CRC32C が追加されていて、これをハッシュ関数に使うと数クロックで 16 バイトに対するハッシュ値を得られる。
CRC32C が理想的な ハッシュ関数†というわけではないが、オリジナルコードと同等以上の一様性(ハッシュ効率)はあるようだ。
CPU が対応していない場合にはソフトウェアでの実装になるが、その場合も表引き 16 回とシフト, XOR で元のアルゴリズムと大きく変わらず、テーブルのサイズも 1 / 4 で済む。

#if defined(__SSE4_2__) || defined(__AVX__)
	#ifdef HAS_CPU_64
		#define	crc32c_u64(crc,d)	_mm_crc32_u64((crc),(d))
	#else
		#define	crc32c_u64(crc,d)	_mm_crc32_u32(_mm_crc32_u32((crc),(d)),((d)>>32))
	#endif
#elif defined(__ARM_FEATURE_CRC32)
	#define	crc32c_u64(crc,d)	__crc32cd((crc),(d))
#else
unsigned int crc32c_u64(unsigned int crc, unsigned long long data)
{
	crc ^= (unsigned int) data;
	crc =	crc32c_table[3][crc & 0xff] ^
		crc32c_table[2][(crc >> 8) & 0xff] ^
		crc32c_table[1][(crc >> 16) & 0xff] ^
		crc32c_table[0][crc >> 24];
	crc ^= (unsigned int) (data >> 32);
	return	crc32c_table[3][crc & 0xff] ^
		crc32c_table[2][(crc >> 8) & 0xff] ^
		crc32c_table[1][(crc >> 16) & 0xff] ^
		crc32c_table[0][crc >> 24];
}
#endif

unsigned long long board_get_hash_code(const Board *board)
{
	unsigned long long	crc;

	crc = crc32c_u64(0, board->player);
	return (crc << 32) | crc32c_u64(crc, board->opponent);
}

Endgame での move shuffle (endgame.c, endgame_sse.c)

終盤探索のうち最後の4か所空きは、ソースコード中のコメントによれば Zebra by Gunnar Anderson を元にしているとのことだが、 ループや再帰を展開して各段用に最適化している。

偶数理論は終盤に盤面上に複数の空地ができたとき、奇数空きの空地に先着すると、その空地に交互に打った時に手止まりが打て有利になるというもの。
7か所空きから5か所空きまでは、盤面を4象限に分けてそれぞれの空きの偶奇をパリティフラグとして持ち、奇数空き、偶数空きの2回ループしている。 (8か所空き以上では eval_evaluate 内で考慮)
次のコードは4か所空きのためのもので、空地の分配は 4, 3-1, 2-2, 2-1-1, 1-1-1-1 のいずれかになっており、このうち 2-1-1 のみ並べ替えが必要になる。
3か所空きでは 3, 2-1, 1-1-1 のいずれかで、2-1 の場合に並べ替えが必要になる。

	// parity based move sorting.
	// The following hole sizes are possible:
	//    4 - 1 3 - 2 2 - 1 1 2 - 1 1 1 1
	// Only the 1 1 2 case needs move sorting.
	if (!(search->parity & QUADRANT_ID[x1])) {
		if (search->parity & QUADRANT_ID[x2]) {
			if (search->parity & QUADRANT_ID[x3]) { // case 1(x2) 1(x3) 2(x1 x4)
				int tmp = x1; x1 = x2; x2 = x3; x3 = tmp;
			} else { // case 1(x2) 1(x4) 2(x1 x3)
				int tmp = x1; x1 = x2; x2 = x4; x4 = x3; x3 = tmp;
			}
		} else if (search->parity & QUADRANT_ID[x3]) { // case 1(x3) 1(x4) 2(x1 x2)
			int tmp = x1; x1 = x3; x3 = tmp; tmp = x2; x2 = x4; x4 = tmp;
		}
	} else {
		if (!(search->parity & QUADRANT_ID[x2])) {
			if (search->parity & QUADRANT_ID[x3]) { // case 1(x1) 1(x3) 2(x2 x4)
				int tmp = x2; x2 = x3; x3 = tmp;
			} else { // case 1(x1) 1(x4) 2(x2 x3)
				int tmp = x2; x2 = x4; x4 = x3; x3 = tmp;
			}
		}
	}
0 1
0 00 01 02 03 04 05 06 07
08 09 0A 0B 0C 0D 0E 0F
10 11 12 13 14 15 16 17
18 19 1A 1B 1C 1D 1E 1F
1 20 21 22 23 24 25 26 27
28 29 2A 2B 2C 2D 2E 2F
30 31 32 33 34 35 36 37
38 39 3A 3B 3C 3D 3E 3F
オリジナルのコードではパリティフラグの偶奇で場合分けしているが、64 マスがどの象限に含まれるかは、右図の通り位置を 6 ビットで表したとき、bit 2 と bit 5 の2ビットが示している。
なので 4 か所 * 2 bit の 8 bit で表を引くと、空地の分配が一度で分類できる。(うち一つが 00 になるように正規化すれば、6 bit の表でよい。)

この情報を元に、4か所空きと3か所空きの両方の並べ替えを行うことができる。
ただし元コードでは4か所空きから残り3か所空きを呼び出すとき、並べ替える前の順で渡していることに注意が必要。 (パリティ同格の場合は元の順番を維持する。)
並べ替えを一度に行ってしまうと、3番目と4番目が入れ替わっている場合がある。

	static const unsigned char parity_case[64] = {	/* x4x3x2x1 = */
		/*0000*/  0, /*0001*/  0, /*0010*/  1, /*0011*/  9, /*0100*/  2, /*0101*/ 10, /*0110*/ 11, /*0111*/  3,
		/*0002*/  0, /*0003*/  0, /*0012*/  0, /*0013*/  0, /*0102*/  4, /*0103*/  4, /*0112*/  5, /*0113*/  5,
		/*0020*/  1, /*0021*/  0, /*0030*/  1, /*0031*/  0, /*0120*/  6, /*0121*/  7, /*0130*/  6, /*0131*/  7,
		/*0022*/  9, /*0023*/  0, /*0032*/  0, /*0033*/  9, /*0122*/  8, /*0123*/  0, /*0132*/  0, /*0133*/  8,
		/*0200*/  2, /*0201*/  4, /*0210*/  6, /*0211*/  8, /*0300*/  2, /*0301*/  4, /*0310*/  6, /*0311*/  8,
		/*0202*/ 10, /*0203*/  4, /*0212*/  7, /*0213*/  0, /*0302*/  4, /*0303*/ 10, /*0312*/  0, /*0313*/  7,
		/*0220*/ 11, /*0221*/  5, /*0230*/  6, /*0231*/  0, /*0320*/  6, /*0321*/  0, /*0330*/ 11, /*0331*/  5,
		/*0222*/  3, /*0223*/  5, /*0232*/  7, /*0233*/  8, /*0322*/  8, /*0323*/  7, /*0332*/  5, /*0333*/  3
	};

	paritysort = parity_case[((x3 ^ x4) & 0x24) + ((((x2 ^ x4) & 0x24) * 2 + ((x1 ^ x4) & 0x24)) >> 2)];
SSE / AVX / Neon が利用できるとき、空き位置をベクターレジスターに持つと、並べ替えにシャッフル命令を使うことができる。
SIMD で処理するわけではないが、使用レジスタや引数の節約にもなる。
特に SSSE3 / AVX が利用できるとき、PSHUFB で 16 バイトの任意の並べ替えが行えるので、 4か所空きの並べ替えの時に残り3か所の並べ替えも同時に行え、前述の処理が不要になる。

	static const union V4SI shuf_mask[] = {	// make search order identical to 4.4.0
		{{ 0x03020100, 0x02030100, 0x01030200, 0x00030201 }},	//  0: 1(x1) 3(x2 x3 x4), 1(x1) 1(x2) 2(x3 x4), 1 1 1 1, 4
		{{ 0x03020100, 0x02030100, 0x01020300, 0x00020301 }},	//  1: 1(x2) 3(x1 x3 x4)
		{{ 0x03010200, 0x02010300, 0x01030200, 0x00010302 }},	//  2: 1(x3) 3(x1 x2 x4)
		{{ 0x03000201, 0x02000301, 0x01000302, 0x00030201 }},	//  3: 1(x4) 3(x1 x2 x3)
		{{ 0x03010200, 0x01030200, 0x02030100, 0x00030201 }},	//  4: 1(x1) 1(x3) 2(x2 x4)
		{{ 0x03000201, 0x00030201, 0x02030100, 0x01030200 }},	//  5: 1(x1) 1(x4) 2(x2 x3)
		{{ 0x02010300, 0x01020300, 0x03020100, 0x00030201 }},	//  6: 1(x2) 1(x3) 2(x1 x4)
		{{ 0x02000301, 0x00020301, 0x03020100, 0x01030200 }},	//  7: 1(x2) 1(x4) 2(x1 x3)
		{{ 0x01000302, 0x00010302, 0x03020100, 0x02030100 }},	//  8: 1(x3) 1(x4) 2(x1 x2)
		{{ 0x03020100, 0x02030100, 0x01000302, 0x00010302 }},	//  9: 2(x1 x2) 2(x3 x4)
		{{ 0x03010200, 0x02000301, 0x01030200, 0x00020301 }},	// 10: 2(x1 x3) 2(x2 x4)
		{{ 0x03000201, 0x02010300, 0x01020300, 0x00030201 }}	// 11: 2(x1 x4) 2(x2 x3)
	};

	empties_series = _mm_cvtsi32_si128((x1 << 24) | (x2 << 16) | (x3 << 8) | x4);
	empties_series = _mm_shuffle_epi8(empties_series, shuf_mask[paritysort].v4);

プロファイラからの分岐率の利用

Intel Compiler Classic (無料の oneAPI Toolkits に含まれる) で PGO ビルドし、アセンブラ出力させると、実際の分岐率がコメントで入り非常に参考になる。
次の2か所空き用のコードで、9 行、15 行などの NEIGHBOUR のビットテストは、隣のマスに相手の石がない場合に board_next (Flip) の判断を省略するためのものだが、テストは 2 〜 3 命令、Flip は AVX2 版で約 30 命令、 投機実行もあるがおおよそ 10% 以上の確率でショートカットできればメリットがあると予想される。
プロファイリングの結果(fforum-20-39 の実測値をコメントで追記)を見ると 24 行、30 行ではショートカットはほぼ 0 % になっていて、テストを入れない方がよい。 2か所空きでは自分が打てないマスは相手が打てることがほとんどなので、これは実感にも合っている。
3か所空きではパス以外でも 5% 以下になるところがいくつかあるようで、探索順位が低いマスほど打てる率が高い傾向があるようだが、こちらはプロファイリングデータがないと予想が難しい。
探索の性質上ある程度の分岐予測ミスは避けられないが、同じく oneAPI toolkits に含まれる VTune を使うと、関数ごとに分岐予測ミスで何%のマイクロコードが捨てられたかも見ることができる。

static int board_solve_2(Board *board, int alpha, const int x1, const int x2, Search *search)
{
	Board next[1];
	register int score, bestscore;
	const int beta = alpha + 1;

	SEARCH_UPDATE_INTERNAL_NODES();

	if ((NEIGHBOUR[x1] & board->opponent) && board_next(board, x1, next)) {	// (84%/87%)
		SEARCH_UPDATE_INTERNAL_NODES();
		bestscore = board_score_1(next, beta, x2);
	} else bestscore = -SCORE_INF;

	if (bestscore < beta) {	// (50%)
		if ((NEIGHBOUR[x2] & board->opponent) && board_next(board, x2, next)) {	// (92%/91%)
			SEARCH_UPDATE_INTERNAL_NODES();
			score = board_score_1(next, beta, x1);
			if (score > bestscore) bestscore = score;
		}

		// pass
		if (bestscore == -SCORE_INF) {	// (17%)

			if ((NEIGHBOUR[x1] & board->player) && board_pass_next(board, x1, next)) {	// (100%/95%)
				SEARCH_UPDATE_INTERNAL_NODES();
				bestscore = -board_score_1(next, -alpha, x2);
			} else bestscore = SCORE_INF;

			if (bestscore > alpha) {	// (20%)
				if ((NEIGHBOUR[x2] & board->player) && board_pass_next(board, x2, next)) {	// (100%/99%)
					SEARCH_UPDATE_INTERNAL_NODES();
					score = -board_score_1(next, -alpha, x1);
					if (score < bestscore) bestscore = score;
				}
				// gameover
				if (bestscore == SCORE_INF) bestscore = board_solve(board, 2);
			}
		}
	}

	return bestscore;
}

solid stones (度外石) (endgame.c, midgame.c)

「オセロ盤面の冗長情報の破棄による探索の効率化」松尾 英和・楢崎 修二† による。
8方向とも辺まで埋まっている石は(スコアには関係するが)その後のゲーム進行には関与しないので、置換表内で共用できるというもの。
eval patters eval patters eval patters bitboard の埋まっている列の求め方はこちら

論文中では探索数が半減するとなっているが、(置換表の参照にもコストはかかる i ので)Edax では置換表を使うのは8か所空き以上になっており、 右図にいくつかの例を挙げるが8方向とも埋まっているマスは限られているため、実際の探索数の節減は 1 〜 2% にとどまるようだ。
それ以上の空きではさらに急減するので、8・9 か所空きのみに導入している。
また Edax の置換表は反復深化・拡幅の過程で前回の探索結果を保持するためにも使われているが、完全読み以外では度外石の処理コストが見合わないし、 またコードの変更も大きくなるので、完全読みのみに導入している。 その結果度外石がある局面では、完全読みの前の最後の反復の結果(局面の最善手)が引き継がれなくなり、ここでも改善効果がわずかながら損なわれる。

  1. VTune でこの NWS_endgame を見ると、CPU リソース の約 50% が置換表の DRAM アクセス待ちで損失している (Hyper Threading オフの値)。
	if (search->eval.n_empties <= MASK_SOLID_DEPTH) {
		get_all_full_lines(hashboard.player | hashboard.opponent, full);
		solid_opp = full[4] & hashboard.opponent;	// full[4] = all full
		hashboard.player ^= solid_opp;	// normalize solid to player
		hashboard.opponent ^= solid_opp;
		ofssolid = bit_count(solid_opp) * 2;	// hash score is ofssolid grater than real
	}

move_evaluate (move.c)

こちらのブログ†に Edax の move_evaluate で「プロファイリングによると、ここ (12〜14行) の if 文の連続が重い」との指摘があり、解決案も示されているが、さらに検討してみる。
static void move_evaluate(Move *move, Search *search, const HashData *hash_data, const int sort_alpha, const int sort_depth)
{
	Board *board = search->board;
	HashData dummy[1];

	if (move_wipeout(move, board)) move->score = (1 << 30);
	else if (move->x == hash_data->move[0]) move->score = (1 << 29);
	else if (move->x == hash_data->move[1]) move->score = (1 << 28);
	else {

		move->score = SQUARE_VALUE[move->x]; // square type
		if (search->n_empties < 12 && search->parity & QUADRANT_ID[move->x]) move->score += w_low_parity; // parity
		else if (search->n_empties < 21 && search->parity & QUADRANT_ID[move->x]) move->score += w_mid_parity; // parity
		else if (search->n_empties < 30 && search->parity & QUADRANT_ID[move->x]) move->score += w_high_parity; // parity

		if (sort_depth < 0) {
			board_update(board, move);
				SEARCH_UPDATE_ALL_NODES();
				move->score += (36 - get_potential_mobility(board->player, board->opponent)) * w_potential_mobility; // potential mobility
				move->score += get_corner_stability(board->opponent) * w_corner_stability; // corner stability
				move->score += (36 - get_weighted_mobility(board->player, board->opponent)) * w_mobility; // real mobility
			board_restore(board, move);
		} else {
			int selectivity = search->selectivity;
			search->selectivity = NO_SELECTIVITY;
			search_update_midgame(search, move);
				// 中略
			search_restore_midgame(search, move);
			search->selectivity = selectivity;
		}
	}
}

void movelist_evaluate(MoveList *movelist, Search *search, const HashData *hash_data, const int alpha, const int depth)
{
	int sort_depth, min_depth;
	int sort_alpha;
	Move *move;

	min_depth = 9;
	if (search->n_empties <= 27) min_depth += (30 - search->n_empties) / 3;
	if (depth >= min_depth) {
		sort_depth = (depth - 15) / 3;
		if (hash_data && hash_data->upper < alpha) sort_depth -= 2; 
		if (search->n_empties >= 27) ++sort_depth;
		if (sort_depth < 0) sort_depth = 0; else if (sort_depth > 6) sort_depth = 6;
	} else {
		sort_depth = -1;
	}

	sort_alpha = MAX(SCORE_MIN, alpha - SORT_ALPHA_DELTA);
	foreach_move (move, movelist) {
		move_evaluate(move, search, hash_data, sort_alpha, sort_depth);
	}
}
この move_evaluate はα-βの効率を上げるために手の予備的な評価を行う部分で、34 行以下の move_list_evaluate からのみ (53 行から) 呼び出される。
なので move_list_evaluate 中に展開すると、search->n_empties はループ不変なので、 「加算するのが w_low_parity / w_mid_parity / w_high_parity のいずれか?」もループ外に出せる。
move_list_evaluate では min_depth に分岐と除算(コンパイラが逆数の乗算に直すが、数命令になる)があるので、これも表引きに直す。
sort_depth もループ不変で、負のとき(現局面で評価、endgame では主にこちらが使われる)と 0 以上のときで move_evaluate 本体は大きく処理が分かれているが、 sort_depth < 0 となるのは depth < min_depth のときだけで、ここでループ自体も分けてしまう。(sort_depth にも除算があるが、重い方の分岐なので目をつぶる。)
さらに sort_depth < 0 の場合はこれ以上探索は行わないので、board_update も展開してしまうと board_restore は不要になる。 (評価自体が重い処理なので、さほど大きな改善ではないが。)
なおオリジナルでは movelist.n_moves = 1 のときも movelist_evaluate が呼ばれることがあるが、評価値は並べ替え以外には利用されないのでこれは省略できる。
void movelist_evaluate(MoveList *movelist, Search *search, const HashData *hash_data, const int alpha, const int depth)
{
	Move *move;
	int	sort_depth, min_depth, sort_alpha, score, empties, parity_weight, org_selectivity;
	HashData dummy;
	unsigned long long P, O;

	empties = search->eval.n_empties;
	parity_weight = parity_weight_table[empties];
	min_depth = min_depth_table[empties];

	if (depth >= min_depth) {
		sort_depth = (depth - 15) / 3;
		if (hash_data && hash_data->upper < alpha) sort_depth -= 2; 
		if (empties >= 27) ++sort_depth;
		if (sort_depth < 0) sort_depth = 0;
		else if (sort_depth > 6) sort_depth = 6;

		org_selectivity = search->selectivity;
		search->selectivity = NO_SELECTIVITY;
		sort_alpha = MAX(SCORE_MIN, alpha - SORT_ALPHA_DELTA);

		move = movelist->move[0].next;
		do {
			// move_evaluate(move, search, hash_data, sort_alpha, sort_depth);
			if (move_wipeout(move, &search->board)) score = (1 << 30);
			else if (move->x == hash_data->move[0]) score = (1 << 29);
			else if (move->x == hash_data->move[1]) score = (1 << 28);
			else {
				score = SQUARE_VALUE[move->x]; // square type
				score += (search->eval.parity & QUADRANT_ID[move->x]) ? parity_weight : 0; // parity

				search_update_midgame(search, move);
					// 中略
				search_restore_midgame(search, move);
			}
			move->score = score;
		} while ((move = move->next));
		search->selectivity = org_selectivity;

	} else {	// sort_depth = -1
		move = movelist->move[0].next;
		do {
			// move_evaluate(move, search, hash_data, sort_alpha, -1);
			if (move_wipeout(move, &search->board)) score = (1 << 30);
			else if (move->x == hash_data->move[0]) score = (1 << 29);
			else if (move->x == hash_data->move[1]) score = (1 << 28);
			else {
				score = SQUARE_VALUE[move->x]; // square type
				score += (search->eval.parity & QUADRANT_ID[move->x]) ? parity_weight : 0; // parity

				// board_update(&search->board, move);
				O = search->board.player ^ (move->flipped | x_to_bit(move->x));
				P = search->board.opponent ^ move->flipped;
				SEARCH_UPDATE_ALL_NODES(search->n_nodes);
				score += (36 - get_potential_mobility(P, O)) * w_potential_mobility; // potential mobility
				score += get_corner_stability(O) * w_corner_stability; // corner stability
				score += (36 - get_weighted_mobility(P, O)) * w_mobility; // real mobility
				// board_restore(&search->board, move);
			}
			move->score = score;
		} while ((move = move->next));
	}
}

(C)2022 奥原 俊彦
Toshihiko Okuhara (okuhara@amy.hi-ho.ne.jp)

Edax AVX の Source Code†

Booby Reversi Home