たこっとのByteBoardはコンピューター将棋の革命児になりうるのか？

いよいよ世界コンピューター将棋選手権の季節がやって参りました。注目のソフトについて少しずつ解説記事を書いていこうかと思います。

たこっとのアピール文書

たこっとのアピール文書
http://www.computer-shogi.org/wcsc26/appeal/takotto/appeal.html

ByteBoardを採用しAVX2命令を使いまくって高速化してあるようです。
評価関数の差分計算をせずに3駒で1スレッドにて1Mnpsも出ているのは超速いです。

世界最速の指し手生成ルーチンを搭載している、やねうら王2015とくらべても1,2割速いです。というか、指し手生成の速度自体で負けています。私の「世界最速」とは何だったのか…。

とまあ、そんなわけで私の「世界最速」が破られたのだとしたら、黙ってはおれません。このへんを解明するためにもたこっとのアプローチが成立しうるのかどうか考えていきたいと思います。

ByteBoard::Pack()

たこっとの肝は、以下のPack関数です。

typedef __m256i	PackedType;

class ByteBoard
{
protected:
	union
	{
		__m256i		boards[3];
		PieceBit	elements[96];
	};

public:
	PackedType	Pack(const ByteBoard& theShuffle) const
	{
		/* 戻り値の上位 16 byte はゴミのため注意 */
		PackedType	tmp1, tmp2, tmp3, tmp4;

		tmp1	= _mm256_shuffle_epi8(this->boards[0], theShuffle.boards[0]);
		tmp2	= _mm256_shuffle_epi8(this->boards[1], theShuffle.boards[1]);
		tmp3	= _mm256_shuffle_epi8(this->boards[2], theShuffle.boards[2]);
		tmp4	= _mm256_xor_si256(tmp1, tmp2);
		tmp1	= _mm256_xor_si256(tmp4, tmp3);

		return	_mm256_xor_si256(tmp1, _mm256_castsi128_si256(_mm256_extracti128_si256(tmp1, 1)));
	}
};

typedef __m256i PackedType;

class ByteBoard

{

protected:

union

{

__m256i boards[3];

PieceBit elements[96];

};

public:

PackedType Pack(const ByteBoard& theShuffle) const

{

/* 戻り値の上位 16 byte はゴミのため注意 */

PackedType tmp1, tmp2, tmp3, tmp4;

tmp1 = _mm256_shuffle_epi8(this->boards[0], theShuffle.boards[0]);

tmp2 = _mm256_shuffle_epi8(this->boards[1], theShuffle.boards[1]);

tmp3 = _mm256_shuffle_epi8(this->boards[2], theShuffle.boards[2]);

tmp4 = _mm256_xor_si256(tmp1, tmp2);

tmp1 = _mm256_xor_si256(tmp4, tmp3);

return _mm256_xor_si256(tmp1, _mm256_castsi128_si256(_mm256_extracti128_si256(tmp1, 1)));

}

};

盤面自体はAVX2の256ビットレジスタ(__m256i)、3本とみなされています。これがByteBoardの正体です。そして、このPack()関数は、盤面上の任意の升の値を指定された順番を保ったまま16升分一気に取ってこれます。

_mm256_shuffle_epi8()でその対象となる16升の順番の並び替えをしていて、そのあとの_mm256_xor_si256()は、それらの重ねあわせをしているだけですね。このPack()関数自体がうまく設計されていて、設計能力および実装能力において達人級の技だと言えるでしょう。

PieceBit

次にByteBoardに何のデータを持たせるのかという点についてですが、たこっとで示されている定数のビット表記は次のようになっています。

/*
	駒のビット表記

	EGSR BLNP
	0000 0001	0x01	PAWN
	0000 0010	0x02	KNIGHT
	0000 0100	0x04	LANCHE
	0000 1000	0x08	BISHOP
	0001 0000	0x10	ROOK
	0010 0000	0x20	SILVER
	0100 0000	0x40	GOLD
	1000 0000	0x80	ENEMY
	0110 0000	0x60	KING
	0100 1000	0x48	HORSE
	0111 0000	0x70	DRAGON
*/

駒のビット表記

EGSR BLNP

0000 0001 0x01 PAWN

0000 0010 0x02 KNIGHT

0000 0100 0x04 LANCHE

0000 1000 0x08 BISHOP

0001 0000 0x10 ROOK

0010 0000 0x20 SILVER

0100 0000 0x40 GOLD

1000 0000 0x80 ENEMY

0110 0000 0x60 KING

0100 1000 0x48 HORSE

0111 0000 0x70 DRAGON

bit0がP(Pawn:歩)、bit1がN(knight:桂)、bit2がL(Lance:香)、bit3がB(Bishop:角)、bit4がR(Rook:飛)、bit5がS(Silver:銀)、bit6がG(Gold:金)、bit7がE(Enemy:後手の駒)という表現です。

例)
王であれば、金+銀 = GとSのbitが1。
馬であれば、金+角 = GとBのbitが1。
龍であれば、金+銀+飛 = GとSとRのbitが1。(Gのbitは無くてもいいような気がしますが、Gを入れておいたほうが金と同じ近接王手として判定できることがあって多少得だということでしょうか…)

のように駒の移動特性ごとに分解され、それらのbit和として表現されています。

ある升への利き

そんなわけで、ある升の周辺10近傍(8近傍+桂の利き)をPack()で持ってきたあと、うまくbitwise andをとることでその升に利きがあるかどうかがわかるというわけです。

neighborhood	= byteBoard.Pack(TABLE::shuffleNeighborhoods[squareKing]);
mask		= _mm256_and_si256(neighborhood, TABLE::maskPackedBitNeighborhoods);
if (! _mm256_testc_si256(_mm256_setzero_si256(), mask)) {
	/* 王手されている */
	return true;
}

neighborhood = byteBoard.Pack(TABLE::shuffleNeighborhoods[squareKing]);

mask = _mm256_and_si256(neighborhood, TABLE::maskPackedBitNeighborhoods);

if (! _mm256_testc_si256(_mm256_setzero_si256(), mask)) {

/* 王手されている */

return true;

}

同じく、ある升から8方向のray(合計で最大32升)も、次のようにPack() 2回で集めてくることが出来ます。

   9   8   7   6   5   4   3   2   1    
+-----------------------------------+   
| 20  ・  ・  ・  04  ・  ・  ・  28| 一
| ・  19  ・  ・  03  ・  ・  27  ・| 二
| ・  ・  18  ・  02  ・  26  ・  ・| 三
| ・  ・  ・  17  01  25  ・  ・  ・| 四
| 12  11  10  09  玉  13  14  15  16| 五
| ・  ・  ・  29  05  21  ・  ・  ・| 六
| ・  ・  30  ・  06  ・  22  ・  ・| 七
| ・  31  ・  ・  07  ・  ・  23  ・| 八
| 32  ・  ・  ・  08  ・  ・  ・  24| 九
+-----------------------------------+   

tmp1	= byteBoard.Pack(TABLE::shuffleCrosses[squareKing]);
tmp2	= byteBoard.Pack(TABLE::shuffleDiags[squareKing]);
line	= _mm256_permute2x128_si256(tmp1, tmp2, 0x20);

9 8 7 6 5 4 3 2 1

+-----------------------------------+

| 20 ・・・ 04 ・・・ 28| 一

| ・ 19 ・・ 03 ・・ 27 ・| 二

| ・・ 18 ・ 02 ・ 26 ・・| 三

| ・・・ 17 01 25 ・・・| 四

| 12 11 10 09 玉 13 14 15 16| 五

| ・・・ 29 05 21 ・・・| 六

| ・・ 30 ・ 06 ・ 22 ・・| 七

| ・ 31 ・・ 07 ・・ 23 ・| 八

| 32 ・・・ 08 ・・・ 24| 九

+-----------------------------------+

tmp1 = byteBoard.Pack(TABLE::shuffleCrosses[squareKing]);

tmp2 = byteBoard.Pack(TABLE::shuffleDiags[squareKing]);

line = _mm256_permute2x128_si256(tmp1, tmp2, 0x20);

このあとはパッとは思いつかないですが、AVX2の匠の技を持ってすれば、なんとかなるのでしょう。

私がパッと思いつく範囲で適当に書くと、例えば
01 02 03 04
の升のPieceBitが順番に並んでいるとして、途中に駒があれば利きは遮断されて利きはそこ以上に及びませんから、駒があるところ以降をmaskしてしまい(0にして)、そして、01 02 03 04は上図で対象升の上方向ですから、飛車(or 後手の香)でなければならないので、飛車のbit以外をマスクして(andを取って)しまい、残ったものが非0ならそこに飛車の利きの特性を持つ駒があって、対象升に利いているということが言えます。

この「飛車のbit以外をマスクして」の部分は、rayの方向によってマスクするbitは異なるのですが、結局は、ここは、_mm256_and_si256() 1回で済みます。

※　「駒があるところ以降をmaskしてしまい」の部分はパっとは思いつきません。お気づきの方がおられましたら、コメント欄で教えてもらえると嬉しいです。

さて、このようにしてある升に利きがあるかないかを調べるのであれば、Bitboardより速そうです。

Bitboardの場合、飛び利きは、magic bitboard、あるいはそれをBMI2のpext命令で取ってくるのが主流です。この場合、bitの並び順がbitboardのlayoutに依存してしまいます。なので大きなテーブルを引く必要がありました。これがByteBoardだと_mm256_shuffle_epi8()によって任意の16升を任意の順番で取ってこれるので、pext命令を使うより使い勝手が良いのです。

ByteBoardを用いた指し手生成は何故速いのか？

駒は、駒の移動特性ごとに分解されているのでたぶんそのあと、AVX2の命令を駆使すると各升から8近傍のうち移動できる方向が1になっている8bitの値に変換するというようなことも可能なはずで、そうなれば次のようなコードで指し手生成が出来ます。(実際は、桂と飛び駒と成り、打ちなどがありますが、そのへんは考えてみてください。)

for(int i = 0 ; i < 81 ; ++i)
  if (board[i])) // 自駒
    for(int j = 0 ; j < 8 ; ++j)
      if (board[i] & (1 << j))
        *mlist++ = make_move(i,sq_of(i,j));

for(int i = 0 ; i < 81 ; ++i)

if (board[i])) // 自駒

for(int j = 0 ; j < 8 ; ++j)

if (board[i] & (1 << j))

*mlist++ = make_move(i,sq_of(i,j));

これ自体は、Bitboardから1bitを取り出すときと違い、変な変換が入らない分だけ速いような気がします。内側のループは表引きするようにすれば高速化できそうですし。

ただ、「駒を取る指し手」「駒を取らない指し手」「駒を取る指し手 + 歩の成る指し手」「王手になる指し手」のような変則的な指し手生成を行なおうとすると一筋縄ではいかなさそうな印象はあります。私の予想としては、それは難しい(簡単に書けない＝Bitboardと同じか遅い)ということなんですけど、このへんも、匠の技でなんとかなってしまうのでしょうか。非常に興味深いところです。

ByteBoardを用いたSEE(静的交換評価)

将棋ソフトにSEEが必要なのかどうかは意見がわかれるところだと思います。評価関数の精度が十分よければ要らないような気もしなくもありませんが、やねうら王やAperyレベルの評価関数ですと、SEEを用いて指し手のオーダリングを行なったほうが若干良いようです。まあ、若干なのでSEEを用いないでその分色々高速化できるなら、SEEなしというのも別にいいのではないかと思います。

まあ、そのへんの議論はさておき、ByteBoardでSEEの実装は私は絶望的だと考えています。SEEでは安い駒で取っていく必要があるのですが、ByteBoardで安い駒を順番に列挙するためにはsortが必要になるからです。まあ、その升に利いている駒は平均的には1枚あるかないかぐらいなので、sort自体はそんなに重くないのかも知れませんが、駒の価値順に並べたりしているとAVX2の命令が使えなくなってくるのでByteBoardの利点が生きなくなってきます。

また、SEEでは、その対象升に駒を移動させたと仮定して、その駒を除外して、また対象升に利く駒を列挙していかないといけないのですが(影の利きが対象升に利いているケースがあるため)、そのへんの処理がByteBoardでは非常に難しいというのが私の考えです。

無論、SEEでその処理までしたほうがいいのかという議論はあります。このへん私にはよくわかりません。

結論

ともかく、ByteBoardでSEEの実装は難しいことは間違いなく、たこっとではSEEは実装していないと思います。あと指し手生成も段階的に(capture + quiet等)行おうと思うと色々難しい問題が出てくるような気はします。

そのへんを匠の技でなんとか回避出来るのかに注目しています。この部分が回避できるなら、いずれ上位のソフトはBitboardからByteBoardに切り替わっていくのではないでしょうか。ByteBoardはそれぐらいのポテンシャルを秘めていると思います。