ビットボードを用いて、ぷよぷよみたいに4つ以上のブロックの繋がりを判定してみる

はじめに

おそらくビットボードとは何ぞやという人が多いと思うので、すごく参考になる記事を置いていきます。

速度向上のためにC++で書いてますが全然C++初心者です。
図を用いてわかりやすく説明する頭脳と技術と慈悲はありません。

前準備

整数をビットボードとして扱うために少し前準備を行います。
今回扱うのは、8*8のビットボードです。uint64_tをビットボードとして用います。

main.cpp

#include <iostream>
#include <vector>
#include <stdio.h>
#include <Windows.h>
#include <random>
#include <array>

#define W 8
#define H 8
#define BIT_SIZE H*W

using BitType = std::uint64_t;

const BitType WALL_RIGHT = 0b11111110'11111110'11111110'11111110'11111110'11111110'11111110'11111110;
const BitType WALL_LEFT = WALL_RIGHT >> 1;

const BitType WALL_BOTTOM = 0b11111111'11111111'11111111'11111111'11111111'11111111'11111111'00000000;
const BitType WALL_TOP = WALL_BOTTOM >> W;

const BitType WHITE_ROW = 0b11111111;

簡単に解説すると、宣言してるconstのWALLなんとかは、ビットボードのマスク処理に使うものです。マスク処理と言ってもただのマスクではなく、ビットが行を越えないようにするためのものですね。後で出てくると思いますが、使用例としては、(bbd << 1) & WALL_RIGHTみたいな感じで使います。ビットボードの用語とか全然知らないので、「壁っぽいからwallでいいか」みたいなノリで変数を命名してます。厳密すぎても先に進めませんし。

実装

前準備もできたので、ここからは実際に書いていきます。

安直な実装

ぷよぷよの四連結の判定方法と言われてパッと思いつくものは、深さ優先探索を用いた方法ですね。

一点ずつ見て行って、その一点に繋がっている数をカウントする感じでできると思います。

これを配列を使わずにわざわざビットボードでやる意味はあるのかと思いますが、まあ座標を一つで表せることと、すでに調べた点かどうかの判定が、check_bit & checked_bitのように論理演算1回でできるのが結構メリットかなと思います。

main.cpp

void getClearBlockBitBoard_loop(BitType bitBoard, BitType check_bit, BitType& checked_bits, BitType& route_bits, int& count);

BitType getClearBlockBitBoard(BitType bitBoard) {
	BitType res = 0, checked_bits = 0, route_bits;
	int count;

	for (int i = 0; i < BIT_SIZE; ++i) {
		route_bits = 0;
		count = 0;

		getClearBlockBitBoard_loop(bitBoard, 1ULL << i, checked_bits, route_bits, count);

		if (count >= 4) {
			res |= route_bits;
		}
	}

	return res;
}

void getClearBlockBitBoard_loop(BitType bitBoard, BitType check_bit, BitType& checked_bits, BitType& route_bits, int& count) {
	if (check_bit & bitBoard & ~checked_bits) {
		++count;

		checked_bits |= check_bit;
		route_bits |= check_bit;

		//left
		getClearBlockBitBoard_loop(bitBoard, check_bit << 1 & WALL_RIGHT, checked_bits, route_bits, count);

		//up
		getClearBlockBitBoard_loop(bitBoard, check_bit << W, checked_bits, route_bits, count);

		//right
		getClearBlockBitBoard_loop(bitBoard, check_bit >> 1 & WALL_LEFT, checked_bits, route_bits, count);

		//down
		getClearBlockBitBoard_loop(bitBoard, check_bit >> W, checked_bits, route_bits, count);
	}
	else {
		checked_bits |= check_bit;
	}
}

主に再帰関数を用いて探索を行ってます。配列だと(x, y)の二つで座標を表しますが、こちらは座標ビットボードだけでいいし（ビットボードが大きくなった時に不便ですが…）、さらに複数の座標を一度に演算できるのがいいですよね。少しこだわったポイントは、ビットボードの右下から始まるので、調べるのが上→左→右→下の順にしたところです。

まあ少しだけビットボードの恩恵にあやかってますが、あまりビットボードらしくない気がします。

popcountを用いた実装

こちらは、一点ずつ調べていくのは同じですが、繋がりをcheck_bitsでまとめて、最後にpopcountで何個繋がっているかを数える方式です。

main.cpp

BitType popcount(BitType x) {
	x = (x & 0x55'55'55'55'55'55'55'55) + ((x >> 1) & 0x55'55'55'55'55'55'55'55);
	x = (x & 0x33'33'33'33'33'33'33'33) + ((x >> 2) & 0x33'33'33'33'33'33'33'33);
	x = (x & 0x0f'0f'0f'0f'0f'0f'0f'0f) + ((x >> 4) & 0x0f'0f'0f'0f'0f'0f'0f'0f);
	x = (x & 0x00'ff'00'ff'00'ff'00'ff) + ((x >> 8) & 0x00'ff'00'ff'00'ff'00'ff);
	x = (x & 0x00'00'ff'ff'00'00'ff'ff) + ((x >> 16) & 0x00'00'ff'ff'00'00'ff'ff);
	x = (x & 0x00'00'00'00'ff'ff'ff'ff) + ((x >> 32) & 0x00'00'00'00'ff'ff'ff'ff);

	return x;
}

BitType getClearBlockBitBoard2(BitType bitBoard) {
	BitType res = 0, checked_bits = 0, route_bits, check_bits;
	int count = 0;

	for (int i = 0; i < BIT_SIZE; ++i) {
		check_bits = 1ULL << i & ~checked_bits & bitBoard;
		route_bits = 0;

		while (check_bits) {
			check_bits = ((check_bits << 1 & WALL_RIGHT) | (check_bits >> 1 & WALL_LEFT) | (check_bits << W) | (check_bits >> W)) & ~checked_bits;
			checked_bits |= check_bits;
			check_bits &= bitBoard;
			route_bits |= check_bits;
		}

		if (popcount(route_bits) >= 4) {
			res |= route_bits;
		} 
	}

	return res;

ちょっと説明とかめんどくさいのでなんとなくで理解してください。さっきとやってることほとんど変わりません。

側近ブロックの個数から求める実装

側近のブロックの数に注目したとき、側近のブロックの数が3以上のブロックがあるとき、または側近のブロックの数が2以上のブロックが二つ以上隣り合ってるとき、そのブロックが繋がっているブロックは４つ以上繋がっているという性質を利用します。

main.cpp

BitType getClearBlockBitBoard3(BitType bitBoard) {
	BitType res = 0;
	BitType shift_r, shift_l, shift_d, shift_u, digit0, digit1, digit2, sumMoreEqual2, x, sumMoreEqual3, sumMoreEqual2Connected;

	//shift
	shift_r = (bitBoard >> 1) & WALL_LEFT;
	shift_l = (bitBoard << 1) & WALL_RIGHT;
	shift_d = (bitBoard >> W);
	shift_u = (bitBoard << W);

	//digits = shift_r + shift_l
	digit0 = shift_r ^ shift_l;
	digit1 = shift_r & shift_l;

	//digits += shift_d 
	digit1 |= digit0 & shift_d;
	digit0 ^= shift_d;
	
	//digits += shift_u
	x = digit0 & shift_u;
	digit2 = digit1 & x;
	digit1 ^= x;
	digit0 ^= shift_u;


	//digits > 2
	sumMoreEqual3 = (digit2 | (digit1 & digit0)) & bitBoard;

	//digits == 2
	sumMoreEqual2 = (digit2 | digit1) & bitBoard;

	//sumMoreEqual2 which is next to each other
	sumMoreEqual2Connected = (((sumMoreEqual2 >> 1) & WALL_LEFT) | ((sumMoreEqual2 << 1) & WALL_RIGHT) | (sumMoreEqual2 >> W) | (sumMoreEqual2 << W)) & sumMoreEqual2;

	res |= sumMoreEqual3;
	res |= sumMoreEqual2Connected;
	res &= bitBoard;

	//satisfy
	res |= ((res >> 1) & WALL_LEFT) | ((res << 1) & WALL_RIGHT) | (res >> W) | (res << W);
	res &= bitBoard;

	return res;
}

側近ブロックの計算についてですが、こちらのサイトにとても助けられました。というか感銘を受けました。

側近のブロックの数をdigits（仮）として表すのですが、2進数である以上1ブロックを1, 0以外で表すことができないので、digit0, digit1, digit2の3桁に分けて表します。
足し算したdigitsからsumMoreEqual2（側近二つ以上）とsumMoreEqual3（側近三つ以上）を取得します。

側近二つ以上のブロックが隣り合っているブロックを求めてそれをsumMoreEqual2Connectedとします。

sumMoreEqual2とsumMoreEqual2Connectedが揃ったのでresに追加します。残るはそれに繋がるブロックを追加するのみです。

ところで、4つ以上のつながりを持つブロックにおいて、側近二つのブロックの隣には必ず側近二つ以上のブロックがあります。このことから、今この時点でresに追加されていないのは末端の側近一つのブロックのみということになります。

また、３つ以上の繋がりを持つブロックにおいて、側近一つのブロックが隣同士になることはありません。つまり、resから上下左右に1範囲を広げるだけで、末端まで行き届きます。

なので特にループも必要なく//satisfy以降の2行で何とかなります。

速度比較

速度計測方法

結構雑ですけど大丈夫なのかは知らないです。まぁざっくりとした時間くらいはわかると思います。
ランダムなビットボードxを引数として1000回処理するのにかかる時間を1000回計測します。

main.cpp

struct Timer {
	LARGE_INTEGER freq;
	LARGE_INTEGER startTime{}, endTime{};
	double time = 0;

	Timer() {
		QueryPerformanceFrequency(&freq);
	}

	void start() {
		QueryPerformanceCounter(&startTime);
	}

	void end() {
		QueryPerformanceCounter(&endTime);

		time = static_cast<double>(endTime.QuadPart - startTime.QuadPart) * 1000.0 / freq.QuadPart;
	}

	void printTime(int div = 1) {
		printf("time %lf[ms]\n", time / div);
	}

	void print(int div = 1) {
		printf("%lf\n", time / div);
	}
};

int main()
{
    Timer timer;

	std::random_device seed_gen;
	std::mt19937_64 engine(seed_gen());

	BitType x, res, ans;
	int n = 1000;
	
	for (int i = 0; i < 1000; ++i) {
		
		x = engine();
		timer.start();
		for (int j = 0; j < n; ++j) {
			res = getClearBlockBitBoard(x);
		}
		timer.end();
		timer.print();
	}
}

計測結果

左から、getClearBlockBitBoard,getClearBlockBitBoard2,getClearBlockBitBoard3の計測結果を箱ひげ図にしたものです。やはりgetClearBlockBitBoard3が最速で速度も安定してますね。

まとめ

と言っても特にまとめることないですが、手法としてもgetClearBlockBitBoard3が、ビットボードが大きくなったとしても速度があまり大きく変わらないので最良だと思います。

最後に

ここまで読んでくれてありがとうございました。

参考文献