8x8 bitboardへの対称な変換の全列挙にグレイコードを応用する

以前の記事（↓）の続きです。
eukaryote.hateblo.jp
符号なし64bit整数を8x8 bitboardとみなして(1)横方向に鏡映 (2)縦方向に鏡映 (3)行列転置という3つの処理をこの順番でやってもやらなくてもよいとしたとき、結果得られる最大8通りのbitboardのうち整数としての値が最小のものを得たいという問題を考えます。ベースラインとなるナイーブな実装は以下のようになります：

//horizontal_mirror, vertical_mirror, transposeの実装は省略
uint64_t get_unique_naive(const uint64_t b) {
	uint64_t answer = b;
	for (uint32_t i = 1; i <= 7; ++i) {
		uint64_t candidate = b;
		if (i & 1)candidate = horizontal_mirror(candidate);
		if (i & 2)candidate = vertical_mirror(candidate);
		if (i & 4)candidate = transpose(candidate);
		answer = std::min(answer, candidate);
	}
	return answer;
}

3種類の変換処理をやるかどうかの選択を「変数iを二進数として見たときの下位3桁のビットが立っているかどうか」と対応付けて、iをfor文で回して全通り作っています。

実際の使用例としては、Edaxというオセロソフトでは上記のような形で実装されています。
edax-reversi/src/board.c at 54578eefbb3fe5d734e02c0e6f6ffed11d1bad9e · abulmo/edax-reversi · GitHub

グレイコードの考え方を応用した実装

一方でEgaroucidという別の最強オセロソフトでは異なる実装になっています。
Egaroucid/src/engine/book_accuracy.hpp at 03f7c7df97ae01613f2c205758b76c9fbaa7156a · Nyanyan/Egaroucid · GitHub
この実装を模式的に書くと以下のような感じになります。
（厳密には違っていて、リンク先のEgaroucidの実装では行列転置（＝対角線を軸とする鏡映）を2回行っています。3種類の変換処理のうち行列転置が一番重いはずなので、行列転置を1回しかやらない以下のような順序付けのほうが少しだけ高速かもしれません）

uint64_t get_unique_graycode(const uint64_t b) {
	uint64_t answer = b;
	const uint64_t code001 = horizontal_mirror(b);
	answer = std::min(answer, code001);
	const uint64_t code011 = vertical_mirror(code001);
	answer = std::min(answer, code011);
	const uint64_t code010 = horizontal_mirror(code011);
	answer = std::min(answer, code010);
	const uint64_t code110 = transpose(code010);
	answer = std::min(answer, code110);
	const uint64_t code111 = horizontal_mirror(code110);
	answer = std::min(answer, code111);
	const uint64_t code101 = vertical_mirror(code111);
	answer = std::min(answer, code101);
	const uint64_t code100 = horizontal_mirror(code101);
	answer = std::min(answer, code100);
	return answer;
}

3種類の変換処理をやるかどうかの選択を3桁の二進数の各ビットの状態に対応付けるという発想はナイーブ実装と同じです。そのうえでこの実装では「直前のbitboardに対してどれか1種類の変換処理だけを行い次のbitboardを作る」を7回行うことで8通りのbitboardを網羅できています。このように「1ビットだけ逆転させる処理によって任意桁の二進数を巡回できること」やその順序自体については"グレイコード"という名前で広く知られており、様々な分野で応用されています。

ちなみに同様の実装は2048（ゲーム）を強化学習するソフトの実装でも見られます。
TDL2048/board.h at 665d470cd8790c88519352362f91f4209e0986a1 · moporgic/TDL2048 · GitHub
2048の場合は、1マスを4bitとみなして16マスの盤面全体を64bitとみなすことになります。その場合には転置操作をpext命令4回でゴリ押したりできて、縦鏡映や横鏡映と比べたときにどれが最も重い処理なのかはCPUアーキテクチャによって色々と話が変わってきます。

グレイコードの考え方を離れ、クリティカルパスを短くする

上記のグレイコードに基づくアルゴリズムは美しいですが、直前の変換が完了しないと次の変換を計算できない、すなわち計算グラフのクリティカルパスが長いのが欠点です。「変換処理を7回やるだけで8通りを網羅できる」「行列転置は1回しか行わない」という要件でクリティカルパスを短くしようとすると、例えば以下のように書くことができます。

uint64_t get_unique_notgraycode(const uint64_t b) {
	uint64_t answer = b;
	const uint64_t code100 = transpose(b);
	answer = std::min(answer, code100);
	const uint64_t code001 = horizontal_mirror(b);
	answer = std::min(answer, code001);
	const uint64_t code010 = vertical_mirror(b);
	answer = std::min(answer, code010);
	const uint64_t code101 = horizontal_mirror(code100);
	answer = std::min(answer, code101);
	const uint64_t code011 = horizontal_mirror(code010);
	answer = std::min(answer, code011);
	const uint64_t code110 = vertical_mirror(code100);
	answer = std::min(answer, code110);
	const uint64_t code111 = vertical_mirror(code101);
	answer = std::min(answer, code111);
	return answer;
}

この実装を含めた上記3つの実装はすべて同じ結果を返しますが、レイテンシ・スループットの面では一番下のコードが（私の環境では）最も高速でした。特にレイテンシに関しては前回の記事で紹介したAVX2版のものよりも高速でした。