分岐はないほうがいい

edaxというオセロソフトでは、探索処理の中でも最後の1手を打つ部分を計算する関数を個別に用意しています。board_score_1という関数です。

edax-reversi/endgame.c at master · abulmo/edax-reversi · GitHub

inline int board_score_1(const Board *board, const int beta, const int x)
{
	assert(_mm_popcnt_u64(board->player | board->opponent) == 63);
	assert(0 <= x && x < 64);
	assert(((board->player | board->opponent) & (1ULL << x)) == 0);

	register int score, n_flips;

	score = 2 * bit_count(board->opponent) - SCORE_MAX;

	if ((n_flips = count_last_flip(x, board->player)) != 0) {
		score -= n_flips;
	}
	else {
		if (score >= 0) {
			score += 2;
			if (score < beta) { // lazy cut-off
				n_flips = count_last_flip(x, board->opponent);
				score += n_flips;
			}
		}
		else {
			if (score < beta) { // lazy cut-off
				if ((n_flips = count_last_flip(x, board->opponent)) != 0) {
					score += n_flips + 2;
				}
			}
		}
	}

	return score;
}

（頭に3つあるassertは、わかりやすさのため私が書き加えました。）この関数は引数boardで示される盤面が1マス空きであることを仮定しています。また、引数xが空いているマスの座標を示していることを仮定しています。そのうえで、完全読みのスコアを求めて返します。（相手方から見たスコアです。）引数betaはアルファベータ法のbetaです。ゆえに真の完全読みスコアがbeta以上である場合は、「beta以上かつ真のスコア以下」の値が返されることのみが保証されます。

このなかで呼ばれているcount_last_flip関数は、最終局面においてプレイヤーが位置xに石を置いた場合にひっくり返る石の数の2倍を返す関数です。（2倍である理由は単に速さのためです。表引きで値を計算するので、表の値をあらかじめ2倍しておけば手っ取り早いわけです）これはAVX2で高速化した実装が存在していて、以下のように書かれています。

https://github.com/okuhara/edax-reversi-AVX/blob/master/src/count_last_flip_sse.c

int last_flip(int pos, unsigned long long P)
{
	unsigned char	n_flips;
	unsigned int	t;
	const unsigned char *COUNT_FLIP_X = COUNT_FLIP[pos & 7];
	const unsigned char *COUNT_FLIP_Y = COUNT_FLIP[pos >> 3];

	__m256i	MP = _mm256_and_si256(_mm256_broadcastq_epi64(_mm_cvtsi64_si128(P)), mask_dvhd[pos].v4);

	n_flips  = COUNT_FLIP_X[(unsigned char) (P >> (pos & 0x38))];
	t = _mm256_movemask_epi8(_mm256_sub_epi8(_mm256_setzero_si256(), MP));
	n_flips += COUNT_FLIP_Y[(unsigned char) t];
	t >>= 16;

	n_flips += COUNT_FLIP_Y[t >> 8];
	n_flips += COUNT_FLIP_Y[(unsigned char) t];

	return n_flips;
}

（原コードではプリプロセッサマクロでSSE版と書き分けられていますが、わかりやすさのため適宜削除しました）

board_score_1が分岐だらけの理由と分岐をなくす方法

board_score_1関数はゲーム木の末端で呼ばれるだけあって呼び出し回数が非常に多く、プロファイリングすると実行時間が上位に来る関数です。なので高速化できれば嬉しいです。おそらく分岐が多いせいで時間がかかっているのだろうと考えました。この分岐の多さの原因はbeta cutをやっているからです。beta cutをやりたい理由は、count_last_flip関数が重いのでなるべく呼びたくないからです。board_score_1関数は最初にcount_last_flip関数を1回必ず呼びますが、beta cutできれば2回目は呼ばずに済むわけです。

しかしながら、よく見るとAVX2版count_last_flip関数は命令レベルでかなり逐次的なので、自分と相手のビットボードに対するcount_flipを同時並行で計算してもレイテンシはほぼ変わらないと期待できます。つまり以下のような関数を用意すれば、count_last_flip関数を1回呼ぶのとほぼ同じレイテンシで、2回呼ぶのと等価な結果を得られます。

void count_last_flip_double(uint64_t position, uint64_t player, uint64_t opponent, int32_t *p_flipped, int32_t *o_flipped)
{
	const uint8_t * const COUNT_FLIP_X = COUNT_FLIP[position & 7];
	const uint8_t * const COUNT_FLIP_Y = COUNT_FLIP[position >> 3];

	const __m256i PPPP = _mm256_set1_epi64x(player);
	const __m256i OOOO = _mm256_set1_epi64x(opponent);
	const __m256i mask = _mm256_loadu_si256((__m256i*)mask_dvhd_double[position]);

	const __m256i maskPPPP = _mm256_and_si256(PPPP, mask);
	const __m256i maskOOOO = _mm256_and_si256(OOOO, mask);

	*p_flipped = COUNT_FLIP_X[(player >> (position & 0x38)) & 0xFF];
	*o_flipped = COUNT_FLIP_X[(opponent >> (position & 0x38)) & 0xFF];

	const uint32_t tP = _mm256_movemask_epi8(_mm256_sub_epi8(_mm256_setzero_si256(), maskPPPP));
	const uint32_t tO = _mm256_movemask_epi8(_mm256_sub_epi8(_mm256_setzero_si256(), maskOOOO));

	*p_flipped += COUNT_FLIP_Y[tP & 0xFF];
	*p_flipped += COUNT_FLIP_Y[tP >> 24];
	*p_flipped += COUNT_FLIP_Y[(tP >> 16) & 0xFF];

	*o_flipped += COUNT_FLIP_Y[tO & 0xFF];
	*o_flipped += COUNT_FLIP_Y[tO >> 24];
	*o_flipped += COUNT_FLIP_Y[(tO >> 16) & 0xFF];
}

そのうえで、三項演算子はconditional mov命令で分岐なしで処理されうることを踏まえつつ、board_score_1関数を以下のように書き換えられます。

int32_t board_score_1_branchfree(const Board &board, const uint64_t x) {

	const int32_t score = 2 * bit_count(board.opponent) - SCORE_MAX;

	int32_t p_flip, o_flip;
	count_last_flip_double(x, board.player, board.opponent, &p_flip, &o_flip);

	const int32_t x1 = score - p_flip;
	const int32_t x2 = score + 2;
	const int32_t x3 = x2 + o_flip;
	const bool b1 = p_flip != 0;
	const bool b2 = score >= 0;
	const bool b3 = o_flip != 0;
	const bool b4 = b2 | b3;
	const int32_t ax = b4 ? x3 : score;
	return b1 ? x1 : ax;
}

この関数は元のboard_score_1関数と完全に等価ではなくて、beta cutを行わずに常に真の完全読みスコアを返します。そのため、元の関数より高速でありつつ、探索ノード数もちょっと削減されます。