原网址：SIMDとBit演算を用いたテトリスの高速化に関する考察；作者：CSDotNet。

这是俄罗斯方块降临历第12天。

本文是有关加速俄罗斯方块AI的模拟过程的。

预计读者是想要加速到极限的有一定知识的开发者。

我看到噗哟噗哟AI中使用wikipedia:en:bitboard来模拟连锁和落下等过程[1]，感觉俄罗斯方块也能做bitboard来加速，所以试了一下。

这次要用的bitboard必须使用CPU的拓展指令集。

使用的命令集是AVX2和BMI2.

AVX2从2013年的CPU起开始支持，所以其实也没那么老，但像奔腾和赛扬等CPU好像不支持。

要是考虑面向一般大众分发软件的话，有必要注意一下这一点。

部分AMD的CPU在部分BMI2指令上非常慢。[2]

场地数据怎么放

考虑通常的俄罗斯方块的场地是10宽40高，需要400位才能表示，但这次要用AVX2，我们用4字节（32位）表示一列，这个大小没有太大，但也不会对游戏过程造成太多问题。

但这就意味着宽变成了8列，这就不够宽了，所以我们用左右2个256位的数据来分别表示5列场地+3列墙壁。

用图来表示的话就是这样。

方块的信息与操作

方块的信息包括旋转状态、位置和形状。

首先是旋转状态，一共有四种所以可以用两位来管理，通过上溢出和下溢出可以节约一次条件判断。

关于方块的形状，写普通的俄罗斯方块时，我认为主要有用数组记录哪个位置有块和直接记录一个4乘4矩阵这两种方法。

这次想尽可能多利用位来高效地运算，所以采用了后者。

比如说，I块可以被记成

因而可以被记成0000111100000000。

旋转时，可以使用DeltaSwap方法高速处理。

详情可以看bitboard的旋转（日文）会比较好理解。

考虑4乘4矩阵的话，可以这样写Mask和Delta。

	fn flip_horizontal_16(mut data: u16) -> u16 {
		data = Self::delta_swap(data, 0x5555, 1);
		data = Self::delta_swap(data, 0x3333, 2);

		data
	}
	fn flip_vertical_16(mut data: u16) -> u16 {
		data = Self::delta_swap(data, 0xF0F, 4);
		data = Self::delta_swap(data, 0xFF, 8);

		data
	}
	fn flip_diagonal_a1d4(mut data: u16) -> u16 {
		data = Self::delta_swap(data, 0xA0A, 3);
		data = Self::delta_swap(data, 0xCC, 6);

		data
	}
	fn flip_diagonal_a4d1(mut data: u16) -> u16 {
		data = Self::delta_swap(data, 0x505, 5);
		data = Self::delta_swap(data, 0xCC, 10);

		data
	}

	pub fn rotate_cw(&mut self) {
		self.data = Self::flip_horizontal_16(Self::flip_diagonal_a1d4(self.data));
	}
	pub fn rotate_ccw(&mut self) {
		self.data = Self::flip_vertical_16(Self::flip_diagonal_a1d4(self.data));
	}

虽然也可以预先准备好全部旋转状态，但考虑到内存和缓存的访问速度，还是要用的时候再计算会比较快，所以用了这样的方法。

另外，I块和O块的旋转轴在正中间，所以用4乘4的矩阵也没什么，但其余块的旋转轴在在3乘3的中心，所以不太能这样简单地旋转。

当前块的数据不会那么频繁地生成，所以生成时可以用函数指针把4乘4和3乘3的DeltaSwap给传过去，这之后好像也能做超级旋转系统中的(0, 0)旋转。

当前块的移动判定

要简单地计算的话，把当前块分成分别给左右两半场地用的两个_m256i，做逻辑与，判定结果是否为0就可以计算。但这个方法太慢了。

在该判定中，为了计算逻辑与，创造两个_m256i的方向不变，但考虑到获得__m256i的数据的方便程度，横跨已分割的数据进行处理还是太困难了，虽然x坐标能对上，但花费的代价太大了。（y坐标的话在两个分割的数据上做移位就行了）

这时，把4乘4的方块扩张到盘面的4乘16那么大，移位把x坐标对上之后转换成__m256i就能解决了。

另外，虽然可以把y坐标对齐到对应位置，用_mm256_slli_epi32就能把每一列分别移位到对应位置，但我们这里的移位的值是一个变量，所以用不了这个命令。

我有一个朋友用gcc的c++来实现了这一套，所以这只是rust上的规定限制，但Intel的官方文档中也写着这里得用一个字面量……？

嘛，因为是每列独立处理的，所以就算用简单实现，因为有流水线机制，所以也能搞得不错吧。（需要验证）

制作消行掩码

求各列的逻辑与即可得到。

不断对原始场地与左移一列的场地做逻辑与的话就能得到，但可以不做移位，而是使用shuffle来一次比较一半，这也是一个优势。

把这里得到的标识怎么怎么地搞一下就能得到消行用的掩码。

填上消去的行

填上消去的行（译注：即消行后的下落过程）时，可以用PEXT和PDEP命令。

虽然都是要对各列进行这样的处理，但拿到各列的数据有移到内存再读取和直接从寄存器拿到各列的数据[3]两种方法，因为访问内存比较慢，所以采用了第二种方法。

放置当前方块

在计算当前方块能否移动时已经能与场地相组合了，直接在这里使用逻辑或即可简单取得结果。

附录

如何计算堵上的洞

被堵上的洞可以定义成上面是1下面是0的位置。

把向下移动的场地与原场地做逻辑与的逆能够得到上下不同的位置的数目。

然后因为条件中还有上面得是1，所以在上式中取得原场地是1的部分，就可以计算场地上所有洞的数目。

总结

就这样，本文考察并实现了使用扩展指令集来进行高速模拟的程序。

我自己还没全部实现，所以不能完全确认，可能还有与理论不同的地方。

另外，我认为算法方面还有许多可以讨论的地方，要是还有更高效的算法的话，请一定不吝赐教。

这次的实现代码因为种种原因不能公开，但要是有能制作俄罗斯方块AI的机会的话，也可能会一并公开。

最后，写这篇文章的过程中、算法和实现都多亏了朋友Alcear的帮助。