第 26 回世界コンピュータ将棋選手権アピール文書

概要

「たこっと」は，電王戦を見てコンピュータ将棋に興味を持った筆者らが，フルスクラッチで実装した (している) 将棋プログラムです。

Web 上の解説記事や論文，Stockfish, Apery, Bonanza 6.0 のソースコードを参考にしています。

特徴

各種処理が AVX2 命令で実装されていて高速
AVX2 命令を適用しやすいデータ構造 (非ビットボード)
Stockfish 風の探索アルゴリズム

評価関数の設計や学習ルーチンの実装が間に合いそうにありません。 Apery の評価パラメータをたこっとの内部形式に合うように変換して使用する予定です (Apery チームの皆さまありがとうございます)。

当面は将来性のある将棋プログラム開発プラットフォーム (高速かつ AVX-512 に対応できる) にすることを目標に実装を進め，一段落したら独自の評価関数の開発に取り組む予定です。

序章「さよならビットボード」

某電王戦を観て「面白そうだな～」

時は過ぎ．．．(単に忘れっぽいだけ)

2014 年の某電王トーナメントを観て「まともに動かないのが結構あるな～」

動かなくてもいいのならと，安易に考えて将棋プログラムの開発に着手しました。当初は，Bonanza 6.0 のソースコードを勉強がてら C++ に書き換えて，少しづつ独自ルーチンに置き換えていこうと目論んでいました。

ある日，C++ で実装した指し手生成ルーチンのベンチマークを取ってみました。

「なんか遅いな～」

バグがあるのかもしれないと，Bonanza 6.0 でもベンチマークを取ってみました。

「やっぱり遅いな～」

ノート PC であるとはいえ，今どきの PC でこんなはずがありません。 for 文をグルグル回すだけの単純な指し手生成ルーチンを実装してみました。

「何ということでしょう」

速度が 2 ～ 3 倍くらいになりました (現在は様々な秘術を駆使して Bonanza 6.0 に対して 3 ～ 5 倍くらいの速度が出ます。ベンチマーク参照)。

Bonanza 6.0 を C++ に書き換えている場合ではありません。独自路線に舵を切ることになりました。

ビッドボードとはさよならです (ときどき後悔することがあります．．．)。

続く (どこに？)

並列化

CPU の動作クロックが頭打ちになりつつある現在，処理速度を向上させるには並列化するしかありません。既存の将棋プログラムでも

マルチスレッド化
PC のクラスタ化

は取り組まれています。

しかし，命令レベルの並列化は遅れているように感じます。 Apery や Bonanza でもビッドボードの論理演算に SIMD 命令や BMI 命令が使用されている程度です。

現在の Intel CPU には AVX2 命令が実装されいます。一度に 256bit のデータを処理できます。ビットボードはたかだが 81bit を同時に処理するだけなので効率が良くありません。また，今後は 512bit 幅の AVX-512 命令も実装される予定です。

AVX2 命令や AVX-512 命令に関しては下記 URL を参照してください
https://software.intel.com/sites/landingpage/IntrinsicsGuide/

ここでは AVX-512 命令まで視野に入れてたこっとで実装した「バイトボード」について簡単に解説します。

他にも指し手生成やオーダリングなど様々ところを AVX2 命令で高速化しています
でも内緒です

バイトボード

疑似コードを掲載します。

/*
	駒のビット表記

	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
*/
enum PieceBit : uint8_t
{
	PIECE_BIT_EMPTY		= 0x00,
	PIECE_BIT_PAWN		= 0x01,
	PIECE_BIT_LANCE		= 0x04,
	PIECE_BIT_KNIGHT	= 0x02,
	PIECE_BIT_SILVER	= 0x20,
	PIECE_BIT_GOLD		= 0x40,
	PIECE_BIT_BISHOP	= 0x08,
	PIECE_BIT_ROOK		= 0x10,
	PIECE_BIT_KING		= 0x60,
	PIECE_BIT_PRO_PAWN	= PIECE_BIT_GOLD,
	PIECE_BIT_PRO_LANCE	= PIECE_BIT_GOLD,
	PIECE_BIT_PRO_KNIGHT	= PIECE_BIT_GOLD,
	PIECE_BIT_PRO_SILVER	= PIECE_BIT_GOLD,
	PIECE_BIT_HORSE		= 0x48,
	PIECE_BIT_DRAGON	= 0x70,
	PIECE_BIT_ENEMY		= 0x80,
};

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)));
	}
};

これで何ができるのでしょうか？

下図の A - J の位置の PieceBit を取り出すことができます。つまり，飛び駒 (龍，馬，飛，角，香) 以外の王手を簡単に調べることができます。

   9   8   7   6   5   4   3   2   1    
+-----------------------------------+   
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 一
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 二
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 三
| ・  ・  ・  Ａ  Ｂ  Ｃ  ・  ・  ・| 四
| ・  ・  ・  Ｄ  玉  Ｅ  ・  ・  ・| 五
| ・  ・  ・  Ｆ  Ｇ  Ｈ  ・  ・  ・| 六
| ・  ・  ・  Ｉ  ・  Ｊ  ・  ・  ・| 七
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 八
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 九
+-----------------------------------+

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

また，飛び駒 (龍，馬，飛，角，香) の場合はもっと効率良く処理できます。下図の 01 - 32 の位置の PieceBit を取り出し，まとめて利きを調べられるからです。

   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);

後はこの line に対して演算すれば飛び駒の王手もまとめて調べることができます。この先は考えてみてください。

この例ではあるマスに対する利きの有り無しを調べました。応用すると，ある駒に利きを与えている駒が存在するマスを取得したりすることができます。

また，AVX-512 命令が使用できる時代が来ると，さらに少ない命令数で高速に処理できるようになります。ビットボードより将来性を感じませんか？

今後はさらに並列化を進めるため，GPU で何かできないかというのも検討していきたいです

ベンチマーク

指し手生成ルーチンのパフォーマンス

実装時に CSA ライブラリになっているいくつかのプログラムのベンチマーク (疑似合法手の生成回数) を取っていました。たこっとのベンチマークと共に比較対象として掲載しておきます。たこっとのみ大会参加時の PC (Core i7-6700K) でもベンチマークを取りました。

測定環境

Windows 8.1 Home (64bit)
Intel Core i7-4500U 1.8GHz
RAM 8192MB

測定条件

gcc が必要なプログラムは Cygwin 上でコンパイル
シングルスレッドで測定

結果

	bonanza 6.0	nanoha mini 2.1.1	apery e9384d3	takotto	takotto Core i7-6700K
平手初期局面	332.2	320.5	459.1	1295.8	2141.0
指し手生成祭りの局面	155.2	200.0	301.0	734.7	1065.8
第 19 期竜王戦第 3 局	180.0	220.8	342.5	834.8	1073.2
最大合法手局面	70.7	115.3	122.3	288.8	395.1

単位は万回 / sec
nanoha mini は合法手のようなので不利
takotto 以外のプログラムは設定などが適当なので参考記録
局面の詳細については局面情報を参照

思考ルーチンのパフォーマンス

並列化のところで述べたような手法も含め，様々な処理を AVX2 命令を多用して高速化しているため，局面の評価値を毎回計算しても 1.0 Mnps を超えるようです。

今後，局面の評価値を置換表に格納したり，差分更新するようにしたりして，さらに高速化する予定です。

測定環境

Windows 10 Pro (64bit)
Intel Core i7-6700K 4.0GHz
RAM 32GB

測定条件

反復深化
PVS
置換表あり
前向き枝刈なし
後ろ向き枝刈あり (それなりの実装)
ムーブオーダリング (それなりの実装)
静止探索 (簡易実装)
局面の評価値 (駒割り + KPP + KKP + KP) を毎回計算
探索深さを指定 (静止探索は指定以上に深く読む)
シングルスレッドで測定
floodgate で R2320 くらいの強さ (マルチスレッド時)

結果

平手初期局面

思考時間            : 0.7485 秒
読み筋              : ▲２六歩（２七）△８四歩（８三）▲２五歩（２六）△８五歩（８四）▲２四歩（２五）△２四歩（２三）▲２四飛（２八）△８六歩（８五）▲８六歩（８七）△８六飛（８二）
評価値              : 121
置換表のサイズ      : 1024 MB
探索深さ            : 8 (15)
指し手生成数        : 980471
違法手数            : 24789
局面探索数          : 890373
NPS                 : 1189617
局面評価数          : 582759
置換表ヒット数      : 136948 (15.381 %)
置換表エントリ破棄数: 0
置換表使用率        : 0.7 %

指し手生成祭りの局面

思考時間            : 19.7448 秒
読み筋              : △４五桂打 ▲３八金（３七）△３三金打 ▲３二と（４二）△３七桂（４五）▲３七金（３八）
評価値              : -963
置換表のサイズ      : 1024 MB
探索深さ            : 6 (25)
指し手生成数        : 50322479
違法手数            : 20065872
局面探索数          : 23150952
NPS                 : 1172507
局面評価数          : 15782216
置換表ヒット数      : 3300123 (14.255 %)
置換表エントリ破棄数: 130825
置換表使用率        : 23.8 %

第 19 期竜王戦第 3 局

思考時間            : 14.0969 秒
読み筋              : △７七桂成（８五）▲７七桂（８九）△７九銀打 ▲７九玉（８八）△６八龍（２八）▲６八玉（７九）
評価値              : -1651
置換表のサイズ      : 1024 MB
探索深さ            : 6 (28)
指し手生成数        : 50114317
違法手数            : 21077005
局面探索数          : 15218957
NPS                 : 1079595
局面評価数          : 11014815
置換表ヒット数      : 1833751 (12.049 %)
置換表エントリ破棄数: 21103
置換表使用率        : 16.0 %

最大合法手局面

思考時間            : 0.0012 秒
読み筋              : ▲２一飛成（９一）
評価値              : 32598
置換表のサイズ      : 1024 MB
探索深さ            : 5 (4)
指し手生成数        : 1229
違法手数            : 56
局面探索数          : 1171
NPS                 : 946586
局面評価数          : 563
置換表ヒット数      : 2 (0.171 %)
置換表エントリ破棄数: 0
置換表使用率        : 0.0 %

違法手が多いのは飛び駒 (龍，馬，飛，角，香) の王手に対して疑似合法手をすべて生成しているため
局面の詳細については局面情報を参照

局面情報

平手初期局面

SFEN="lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1"

   9   8   7   6   5   4   3   2   1    
+-----------------------------------+   
|v香 v桂 v銀 v金 v玉 v金 v銀 v桂 v香| 一
| ・ v飛  ・  ・  ・  ・  ・ v角  ・| 二
|v歩 v歩 v歩 v歩 v歩 v歩 v歩 v歩 v歩| 三
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 四
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 五
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 六
| 歩  歩  歩  歩  歩  歩  歩  歩  歩| 七
| ・  角  ・  ・  ・  ・  ・  飛  ・| 八
| 香  桂  銀  金  玉  金  銀  桂  香| 九
+-----------------------------------+   
手番 [先手]                             
先手 飛=0 角=0 金=0 銀=0 桂=0 香=0 歩=0 
後手 飛=0 角=0 金=0 銀=0 桂=0 香=0 歩=0

指し手生成祭りの局面

SFEN="l6nl/5+P1gk/2np1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL w RGgsn5p 1"

   9   8   7   6   5   4   3   2   1    
+-----------------------------------+   
|v香  ・  ・  ・  ・  ・  ・ v桂 v香| 一
| ・  ・  ・  ・  ・  と  ・ v金 v玉| 二
| ・  ・ v桂 v歩  ・  銀  ・  ・  ・| 三
|v歩  ・ v歩  ・  ・  ・  ・  歩 v歩| 四
| ・  ・  ・  歩  ・  ・  銀 v歩  ・| 五
| ・  歩  歩 v角  ・  ・  歩  ・  歩| 六
| 歩  ・  ・  ・  ・  ・  金  銀  ・| 七
| 飛  ・  ・  ・  ・  ・  ・  ・  ・| 八
| 香  桂  ・  ・  ・  ・ v角  玉  香| 九
+-----------------------------------+   
手番 [後手]                             
先手 飛=1 角=0 金=1 銀=0 桂=0 香=0 歩=0 
後手 飛=0 角=0 金=1 銀=1 桂=1 香=0 歩=5

第 19 期竜王戦第 3 局

SFEN="8l/1l+R2P3/p2pBG1pp/kps1p4/Nn1P2G2/P1P1P2PP/1PS6/1KSG3+r1/LN2+p3L w Sbgn3p 124"

   9   8   7   6   5   4   3   2   1    
+-----------------------------------+   
| ・  ・  ・  ・  ・  ・  ・  ・ v香| 一
| ・ v香  龍  ・  ・  歩  ・  ・  ・| 二
|v歩  ・  ・ v歩  角  金  ・ v歩 v歩| 三
|v玉 v歩 v銀  ・ v歩  ・  ・  ・  ・| 四
| 桂 v桂  ・  歩  ・  ・  金  ・  ・| 五
| 歩  ・  歩  ・  歩  ・  ・  歩  歩| 六
| ・  歩  銀  ・  ・  ・  ・  ・  ・| 七
| ・  玉  銀  金  ・  ・  ・ v龍  ・| 八
| 香  桂  ・  ・ vと  ・  ・  ・  香| 九
+-----------------------------------+   
手番 [後手]                             
先手 飛=0 角=0 金=0 銀=1 桂=0 香=0 歩=0 
後手 飛=0 角=1 金=1 銀=0 桂=1 香=0 歩=3

最大合法手局面

SFEN="R8/2K1S1SSk/4B4/9/9/9/9/9/1L1L1L3 b RBGSNLP3g3n17p 1"

   9   8   7   6   5   4   3   2   1    
+-----------------------------------+   
| 飛  ・  ・  ・  ・  ・  ・  ・  ・| 一
| ・  ・  玉  ・  銀  ・  銀  銀 v玉| 二
| ・  ・  ・  ・  角  ・  ・  ・  ・| 三
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 四
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 五
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 六
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 七
| ・  ・  ・  ・  ・  ・  ・  ・  ・| 八
| ・  香  ・  香  ・  香  ・  ・  ・| 九
+-----------------------------------+   
手番 [先手]                             
先手 飛=1 角=1 金=1 銀=1 桂=1 香=1 歩=1 
後手 飛=0 角=0 金=3 銀=0 桂=3 香=0 歩=17

第 26 回世界コンピュータ将棋選手権アピール文書

概要

特徴

序章 「さよならビットボード」

並列化

バイトボード

ベンチマーク

指し手生成ルーチンのパフォーマンス

測定環境

測定条件

結果

思考ルーチンのパフォーマンス

測定環境

測定条件

結果

平手初期局面

指し手生成祭りの局面

第 19 期竜王戦第 3 局

最大合法手局面

局面情報

平手初期局面

指し手生成祭りの局面

第 19 期竜王戦第 3 局

最大合法手局面

序章「さよならビットボード」