今日から使えないビット演算（CODE VS Reborn編）

0. はじめに

この記事は，チームラボ・リクルートさんがスポンサーするCODE VS Reborn (https://codevs.jp/ ) に関する記事になります．

CODE VS Rebornはぷよぷよとボンバーマンを合わせたようなゲームのAIを作るコンテストです．

1. ゲームのルール

今回のゲームは, CODE VS 2.0 のリメイク版であるCODE VS for STUDENTのリメイク版で, 対戦形式の落ちものパズルです．ルールの詳細は以下の PDF に記されています.
https://static.codevs.jp/reborn/rule.pdf

自分のAIは上から降ってくる数字のパックの位置・回転数を指定します．
フィールド上で隣り合う 縦，横，斜めのブロックの数字の和が 10 になった所が消え，消えたブロックの上にブロックが積まれていた場合，上のブロックが落下します.

ブロックが消えた事により上のブロックが落下し, 落下したブロックが消える…… という動作を繰り返し, 連鎖が発生します.

大きな連鎖を発生させると相手にお邪魔ブロックを送りつけることができ，お邪魔ストックが1行分（10個）貯まると，1列分相手のフィールドにお邪魔ブロックが降ってきます．

また，前作との大きな違いとしてスキルというものが追加されました．
これは5のブロックとその周囲8マス（お邪魔ブロックを除く）を一気に消し去ることができるもので，スコアが非常に大きく設定されています．
ブロックを消すとスキルゲージが貯まり，一定以上のスキルゲージが貯まると発動することができます．

2. フィールドをビットで表現する

それぞれのマスは0～11の数値なので，これは4bit あれば表現できます．フィールドの高さは16なので，1列を64bit整数1つで表現することができます．
このようにビットで圧縮して表現することのメリットとしてビット演算で表現しやすくなるほか，メモリ節約効果もあります．1マスをcharで8bit消費するよりも半分のメモリでフィールドを表現することができます．

現代のコンピューターは十分に潤沢なメモリがあり，このようなチマチマした節約するよりも富豪的プログラミングしたほうがいいというスタイルもありますが，高速化を考えた場合，メモリの節約技術はまだまだ現役です．

その最も大きな理由としてCPUのキャッシュはまだまだ小さいことが挙げられます．例えば提出サーバーで使用されていたXeon E5 2676 v3の場合，L1 dataキャッシュはコアあたり32KB，L2キャッシュはコアあたり0.25MB，L3キャッシュは12コア共用で30MBです．メモリの進化はCPUの演算性能に比べ著しく劣り，キャッシュメモリとの速度差は数十から大きいと百倍以上とも言われています．また現代のアプリケーションはほぼメモリ速度律速であるため，効率よくキャッシュを利用することは非常に重要です．
キャッシュヒットするかキャッシュミスするかでどのくらい差が生まれるかは，こちらの記事でも議論されています．
https://kimiyuki.net/blog/2019/05/17/clock-cycles-and-time-complexity/

他にも，CPUの1サイクルで演算できる幅はどの精度・命令でもおよそ固定長であるので，固定長に多くの情報を詰められると1サイクルあたりの処理能力が向上します．たとえば Intel の Haswell 世代以降や Ryzen に搭載されている AVX2 命令セットでは 256bitを単位とした処理を行います．AVX2 で整数足し算をするアセンブリ命令 vpaddb(char×32個) / vpaddw(short×16個) / vpaddd(int×8個) / vpaddq(long long×4個) はいずれも 1サイクルLatency で計算できます．
https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm256_add_epi
つまりcharの範囲に収まるならば，int型を使うよりも4倍効率的になります（うまくベクトル化ができる場合）．
ベクトル化に関しては自前でアセンブリやIntrinsics命令を使うのも良いですが，対応CPU上で gcc に -march=native 最適化オプションを付加すれば，コンパイラがベクトル化可能と判断した箇所は勝手にやってくれます．

3. Related Work

前作の mecha_g3 さんの記事の「落下処理の高速化」章にて，PEXT (Parallel bits extract)命令を使った高速化がありました．
PEXTとは値valとマスクmaskの2つの入力に対し，maskでビットが立っていた値だけを詰めて返してくれる命令です．例えば val : 0x1234'5678, mask : 0x00ff'0f0f の場合，0x0000'3468 と言った値を返してくれます．消えるマスのマスクを作ることができれば1列の落下処理が1命令でできるということです．愚直に実装した場合はちょっと複雑になりがちなので，これは嬉しいですね．
http://klabgames.tech.blog.jp.klab.com/archives/1062972532.html

4. 足して10を判定するビット演算

前作では 1+3+6 = 10 のような10の作り方も許されていましたが，今回は2つの合計が10と制約が厳しくなりました．前作では制約が緩かったがゆえに10の判定が難しかったのですが，今回は判定が非常に簡単にできる形になりました．
今回はこの改善された制約を用いて，10和判定をする方法を紹介します．

part 1 足し算をつかう

盤面をビットボードで表した際，愚直に2列の値をそのまま足しても16進の各桁で独立に考えると足し算が大体できてます．

  0x 1234'5678
+ 0x 4208'6420
= 0x 543C'BA98

このように下の桁から，8+0=8, 7+2=9, 6+4=A, ..., 1+4=5 と足し算ができています．
しかし，入力が[0,11]の範囲をとり得る足し算の結果の範囲は[0,22]となり，16進数の1桁をオーバーしてしまいます．

  0x 1234'5678
+ 0x 4536'2718
= 0x 576A'7D90

このように 8+8=10 (16) なので，繰り上がりの影響が出て，2桁目が正しくない結果となっています．
今回の場合は16進数ではなく23進数や32進数を使うことにより，この問題を回避できます．
しかし32進数で表現しようとした場合，64bit整数を使うとしても 64/5=12.8 であり，12行分しか表現できません．

part 2 ビット演算を組み合わせる

足し算の場合，結果の範囲が大きすぎて16進数との相性が悪いことが分かりました．
4bit # 4bit = 4bit となるような演算# が必要になってきます．
さて，このような都合の良い演算とは……はい，ビット演算の登場です
例えば16進の入力X, Y があるとして X#Y = X+2 ^ Y+3 を考えると，X+Y=10 <=> X#Y=Fとなります．
入力として来るのは 空マス0，数字ブロック1~9，お邪魔ブロック11(0xB)なので，これらの演算結果をまとめると以下の通りになります．

#		0	1	2	3	4	5	6	7	8	9	B
	XOR	2	3	4	5	6	7	8	9	A	B	D
0	3	1	0	7	6	5	4	B	A	9	8	E
1	4	6	7	0	1	2	3	C	D	E	F	9
2	5	7	6	1	0	3	2	D	C	F	E	8
3	6	4	5	2	3	0	1	E	F	C	D	B
4	7	5	4	3	2	1	0	F	E	D	C	A
5	8	A	B	C	D	E	F	0	1	2	3	5
6	9	B	A	D	C	F	E	1	0	3	2	4
7	A	8	9	E	F	C	D	2	3	0	1	7
8	B	9	8	F	E	D	C	3	2	1	0	6
9	C	E	F	8	9	A	B	4	5	6	7	1
B	E	C	D	A	B	8	9	6	7	4	5	3

この性質は嬉しいですね．
よって2列 X, Y からマスクを生成するには

long long maskSum10(unsigned long long X, unsigned long long Y) {
    long long M = (X+2)^(Y+3);
    M &= M >> 1;
    M &= M >> 2;
    M &= 0x1111'1111'1111'1111;
    M |= M << 1;
    M |= M << 2;
    return M;
}

のようにすれば良いです．なお，後半の

M &= 0x1111'1111'1111'1111;
M |= M << 1;
M |= M << 2;

の部分は，各方向で10和判定した結果をORしたあとにまとめて行うこともできます．

part 3 内部の数値表現を変える

さて，part 2 で X#Y = X+2 ^ Y+3 を行うことにより，10和判定ができることが分かりました．しかしもっと計算を簡単にできないでしょうか…？

ここで，実際のブロックの数と，内部の数値の表現が一致している必要性が無いことに気づきます．なので入力を受け取ったときに全部のブロックを +2 してあげます．
そうすると判別式は X#Y = X ^ Y+1 に変化します．
おや，足し算1つとビット演算1つで10和判定ができるようになってしまいました．これより演算数を落とすのは難しそうですね．
出力するときに-2してあげるのを忘れずにしましょう．

5. スキルをビット演算で表現

このゲームではスキルを使うことにより，5のマスの縦横斜め9マスを消失させることができます．
5のマスのマスクは，5が2進数で表すと 0b0111 であることから ((~X>>3)&(X>>2)&(X>>1)&X)&1 と4bit分を判定しても良いですが，内部表現で下3bitが'0b111'になるのは5しかないので((X>>2)&(X>>1)&X)&1 で表現可能です．

long long mask5(unsigned long long X) {
    X &= (X>>1) & (X>>2);
    X &= 0x1111'1111'1111'1111;
    X |= X << 1;
    X |= X << 2;
    return X;
}

さて，めでたくスキルのマスクができたので，PEXTで消去…と行きたいところですが，このマスクは少し不完全です．
ルールを読んでみると，お邪魔ブロックはスキルを使用しても消去することができません．まさにお邪魔…！！
お邪魔ブロックの内部表現は 0xD = 0b1101 なので，上2ビットが立っているかで逆マスクで打ち消さなければなりません．

ところで，内部表現を入力の+2としましたが，これも別に規則的である必要は無いことに気づきます．そこで，以下のような変換を行います．

入力	内部表現(16進)	内部表現(2進)
0	0	0000
1	1	0001
2	2	0010
3	3	0011
4	4	0100
5	7	0111
6	A	1010
7	B	1011
8	C	1100
9	D	1101
11	8	1000

この場合，5のマスは中央2bitが 0b?11? のように立っているかどうかで確認することができます．
また，「スキルはお邪魔ブロックは消去できない」を「スキルはお邪魔ブロックと空マスは消去できない」と言い換えてあげると，下3bitが 0b?000 のように0になってるかどうかで判定ができます．

盤面にある5の数を数えたくなることもあると思いますが，中央2bitが立ってるかどうかだけで判定できるのはアドです．

6. 列の高さを計算する

例えば

0x 0000'0000'0000'1234 -> 4
0x 0000'0271'8281'8284 -> 11
0x 0000'0000'0000'0000 -> 0
0x 8888'8888'8888'8888 -> 16

のように，16進ビットボードからブロックの高さを計算したいとき，愚直にビット演算テクを使った場合は

int getHeight(unsigned long long X) {
    X |= X >> 1;
    X |= X >> 2;
    X |= X >> 4;
    X |= X >> 8;
    X |= X >> 16;
    X |= X >> 32;
    return __builtin_popcountll(X)+3 >> 2;
}

また __builtin_clzll を使って上位にある0のビットの数を数える(CLZ) テクがあります．
注意として __builtin_clzll を使った場合， __builtin_clzll(0) の値は未定義なので，条件分岐かマスクをしないといけません．また，この命令は GCC拡張であるため，GCCでしか使用することができません．今回は別の方向から列の高さを求める方法を考えていきたいと思います．

列の高さの関係を眺めると，16進数での桁数が求めたいものであることから，底が16のlogを求めれば良さそうです．
logを求めるときの定石テクとして，floatに変換してその指数部を使う技があります．これはfloatがIEEE754のbinary32形式で内部表現されるときに使えますが，身の回りのほとんどのアーキテクチャはこの形式で表現されているはずなので大体使用できます．
Wikipedia 単精度浮動小数点数

これを使って以下のように求めます．

int getHeight(unsigned long long X) {
    float f = (float)X;
    return (((*((int*)&f) >> 23) - 123) >> 2);
    //     (((*((int*)&f) >> 23) - 127) >> 2) + 1;
}

23bitずらして指数部を抜き出し，-127で下駄履きを脱がします．
これを使ってサンプル入力を試すとほぼうまくいっていますが，0を入力したときは-31となりうまくいきません．
これは下駄を脱がす際，0の指数部は0であるので，-127になってしまい，(-127 >> 2)+1 = -31となってしまうためです．ここは本当は0になってほしいです．

ところで，CPUのアセンブリ命令には飽和演算命令というものがあります．これは加減算でオーバーフローが起きる時，その上限（下限）で飽和処理をしてくれるものです．例えば 8bit演算整数の飽和加算である paddsb を使用した場合， 100+60 は -96 ではなく 127 となります．

この飽和演算命令をC/C++で使用するにはIntrinsics命令を使います．たとえば _mm_subs_epi16 命令を使うことにより，16bitの整数8個を飽和減算でベクトル処理してくれます．
https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm_subs_epi16

これを使うと以下のように書けます．

int getHeight(unsigned long long v) {
    __m128 f = _mm_set1_ps((float)v);
    __m128i x = _mm_castps_si128(f);
    x = _mm_subs_epu16(x, _mm_set1_epi16(123 << 7));
    return (_mm_cvtsi128_si32(x) >> 25);
}

これらはすべてAVXによるベクトル命令なので同時に8個のshort値を処理できますが，このサンプルでは1個の値のみを処理しています．

7. おわりに

さて，ビット演算を使用した Code VS Reborn 高速化テクはいかがでしたでしょうか？
大学では Intrinsics命令 やキャッシュを考慮したプログラミングの研究をやっていたのもあり，ビット演算等を使ったテクを考えてきました．

ビット演算テクを使った場合，5ターン先までのDFSがシングルスレッドで2秒程度でできました．DFSの仕組み上メモリをほぼほぼ使わないため，主要データがL1キャッシュに収まるのも高速化に一役かっています．ところで5ターン先の最善を愚直に選択していくだけでも勝手にnターンn連鎖 (n > 10)がバンバン打てるようになります．

今回，Code VS復活で非常に嬉しかったのですが，4月頭は引越しやら新居にインターネットが無いやら非常に苦しいスタートダッシュで，オンライン対戦が動き始めて最初の方はチラホラGOLDに入れましたが，ビット演算テクで満足したあとはあまり進捗が出せず，BRONZ落ちしてしまいました（）

参考になるかは分かりませんが，今後また似たようなルールでCode VSが復活した場合は適当に参考にしてください．