C# Source Generator で将棋の指し手生成を生成して高速化してみた

はじめに

現在、C# で将棋ライブラリを作っていて（ https://github.com/tomori-k/ShogiLibSharp ）、最近は指し手生成（局面が与えられて、そこで指せる手をすべて列挙する）のプログラムを延々高速化していました。（最強の将棋エンジンを作るのが目的ではないので、極限まで高速化する必要性はないですが）

今回、高速化の１つの手法として C# の Source Generator を使ってみたのですが、あまりこういう使い方は見ないので記事にしてみようと思います。

Source Generator でやりたいこと

将棋プログラムの多くは内部でビットボードと呼ばれるデータ構造を使っています。ShogiLibSharp も例に漏れません。

ビットボードは簡単にいうと、盤面の各マスに1ビットを割り当て、各マスの「駒があるかないか」や「利きがあるかないか」という情報をまとめて管理するデータ構造です。オセロやチェスは盤面サイズが 8x8 で ulong に収まってちょうどいいのですが、将棋の場合は81ビット必要なので ulong を2つ使って表します。詳しくはググってください。

このビットボードというデータ構造を使うと、例えば盤上の銀を動かす指し手を生成するコードは以下のようになります。 コードの詳細は説明はしませんが、雰囲気は伝わりますかね...？

var fromBB = pos.PieceBB(pos.Player, Piece.Silver).AndNot(pinned);
foreach (var from in fromBB)
{
    var toBB = Bitboard
	.Attacks(pos.PieceAt(from), from, occupancy)
	.AndNot(us);
    foreach (var to in toBB)
    {
	*buffer++ = MoveExtensions.MakeMove(from, to, false);
	if (Square.CanPromote(pos.Player, from, to))
	{
	    *buffer++ = MoveExtensions.MakeMove(from, to, true);
	}
    }
}

C# らしからぬポインタ演算がありますがキニシナイ

さらっとビットボードにたいして foreach を使っていますが、自作の Enumerator を Bitboard 構造体に定義してあります。

// 一部省略
public struct Enumerator : IEnumerator<int>
{
    bool first = true;
    ulong b0, b1;

    public int Current
	=> b0 != 0UL
	    ? BitOperations.TrailingZeroCount(b0)
	    : BitOperations.TrailingZeroCount(b1) + 63;

    public bool MoveNext()
    {
	if (first)
	{
	    first = false;
	    return b0 != 0UL || b1 != 0UL;
	}
	else
	{
	    if (b0 != 0UL)
	    {
		b0 &= b0 - 1UL;
		return b0 != 0UL || b1 != 0UL;
	    }
	    else if (b1 != 0UL)
	    {
		b1 &= b1 - 1UL;
		return b1 != 0UL;
	    }
	    else
		return false;
	}
    }
}

この Enumerator、速さを考えなければ便利なのですが、極限まで速くしたい今のケースだとちょっと速度低下が気になります。

原因はおそらく、

• MoveNext の仕様上、余計な処理(最初とそれ以外で場合分け、など)が増えてしまっている
• MoveNext がインライン展開されず関数呼び出しのコストが発生する

あたりだと思います。理想的には

foreach(var x in ビットボード)
    文

が

var _b = ビットボード.Lower();
while(_b != 0UL)
{
    var x = BitOperations.TrailingZeroCount(_b);
    文
    _b &= _b - 1UL;
}
_b = ビットボード.Upper();
while(_b != 0UL)
{
    var x = BitOperations.TrailingZeroCount(_b) + 63;
    文
    _b &= _b - 1UL;
}

みたいなコードになってほしいです。

今回はこれを Source Generator でやってみたという話になります。

Source Generator でコード置き換え

Source Generator は、ジェネレータ用のプロジェクトを作って、ISourceGenerator というインターフェースを実装したクラスを作るとできます。ISourceGenerator は void Execute(GeneratorExecutionContext context) というメソッドを持っており、この context が構文木を持っているのでそれを解析してコードを生成する...といった感じです。

しかし、ここで一つ問題があります。

Source Generator はコードの生成のみ可能で、部分的な置き換えをすることが出来ません。

じゃあどうするかというと、元のメソッドから、ビットボードの foreach の部分だけ書き換えた別のメソッドを生成することで無理やり解決します。

具体的には、今回作った Source Generator は InlineBitboardEnumerator 属性（Source Generator 側で定義）が付いた ○○Impl というメソッドを探し、ビットボードに対する foreach を上記で示したように while で置き換えた、 ○○ というメソッドを別ファイルに生成します。

クラス、メソッドの定義が2つのクラスに分かれるので元のファイルではそれぞれ partial をつけておく必要があります。

例を示すと

Movegen.cs

static partial class MoveGen
{
    static partial void GenerateMoves();
    
    [InlineBitboardEnumerator]
    static void GenerateMovesImpl()
    {
        // ...
    }
}

というクラスがあったとき、Source Generator は GenerateMovesImpl をもとにして、 GenerateMoves の中身を生成し、

Movegen.g.cs

static partial class Movegen
{
    static partial void GenerateMoves()
    {
        // foreach のところだけ書き換えた GenerateMovesImpl の中身をここに生成
    }
}

という新しいソースファイルを生成することで置き換えっぽいものを実現します。

実装

気になる方は GitHub を参照してください。ShogiLibSharp.MovegenGenerator というプロジェクトが Source Generator のプロジェクトです。

高速化の効果

perft という、ある局面から n 手進める手順の数を求める合法手生成のテストがあります。例えば、平手の局面から 1 手進める手順は 30 通り、2手なら 900 通り、といった感じです。

この perft の実行時間を測って高速化の効果を確かめてみます。

Perft	手順数	Source Generator なし	Source Generator あり	実行時間の比率（なし／あり）
平手、n=5	19861490	495.9 ms	411.2 ms	1.2059...
指し手生成祭り、n=4	516925165	4,728.7 ms	3,302.6 ms	1.4318...
最大合法手局面、n=3	53393368	178.6 ms	120.2 ms	1.4858...

※指し手生成祭りの局面: sfen l6nl/5+P1gk/2np1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL w RGgsn5p 1
※最大合法手局面: sfen R8/2K1S1SSk/4B4/9/9/9/9/9/1L1L1L3 b RBGSNLP3g3n17p 1

大体 20% から 40% ぐらい速くなっています。

ただ、Source Generator の作成は結構大変（特にデバッグ）なので、それを考えるとコスパは悪いと思います。高速化の最終手段ぐらいにしておくのが良さそうです。

まとめ

• 特定の型に対する foreach を置き換える Source Generator を作って高速化した
• 20%〜40% ぐらい高速化できた
• 実装の大変さに比べると効果は微妙なので、高速化の最終手段としてはいいかも