こんにちは

こんにちは、ボードゲームのAIの作成をするため、Stockfish を参考にしたいと思い、そのメモ程度で記事を書きます。Stockfish 15 は難解すぎてよく分からんので、ひとまず見つけた Stockfish 3 で勉強したいと思います。

勉強するのは、StockFish の評価基準ではなく、技術寄りな話です。評価基準は最新の Stockfish の方が良いと思います。ただ、色々あって多少評価基準の方にも顔を出すことはありそうです。

プログラムおおよそ初心者が書いたような記事なので、温かい目で見守ってくれると嬉しいです。
また、気付いたことから順に書いていくので、見る場所があっちこっちします。

どこから読むか

困りました。StockFish における main.cpp は非常によく分かりません。なんか設定したりしてると思います。読みたいのは正直そこじゃないですよね。メインターゲットとしては

• Bitboard などの盤面の表現
• Thread
• Game Tree の探索

この辺りでしょうか。どこを辿れか良いか分かりませんが、おそらく Thread と Game Tree の話は密接に関係しているので後回しでしょう。というわけで、つまりは Chess における bitboard 表現から見ていこうと思います。

Bitboard を辿って

Bitboard 知らない人へ

僕もほとんど理解してないのですが、一応知らない人用に、簡単に Bitboard の説明をします。
Bitboard とは、2進数の各桁ごとにマス目を表して、それを元に盤面を表すものです。例えば、簡単のためマルバツゲームで考えたら盤面を

000 000 000

という感じで、3x3 = 9桁で表します。しかし、これでは各マスには 0 または 1 の情報しか保存できません。これでは空マス、マル、バツ、の3状態を保存できません。ではどうするのかというと単純で、2つにします。例えば、中央にマル、その左にバツとなっていれば

maru: 000 010 000
batu: 000 100 000

という感じに表します。チェスでも同じように駒ごとに分ければ良さそうです。
これが使われている理由ですが、どうも駒を動かす、や、駒の動けるマスを調べる、といった操作を高速なアルゴリズムで書けるっぽいです。すごいですね。

まずは Bitboard の定義から

僕はカスなので、初歩的な話から行きましょう。まず Stockfish では

typedef uint64_t Bitboard;

と定義されていますね。盤面が 8x8 なので当然64bitである必要があります。しかし、型を定義しただけではまだ Bitboard の強みが活かされていません。そういうわけで、Bitboard に対する操作がどう定義されているかを見ていきます。

Bitboard の操作

どうやって見つけるかですが、おそらくお使いのコードエディタの検索機能で、inline Bitboardを検索すればいろいろ出てきます。

まずですが、どうも Bitboard SquareBB[SQUARE_NB] というものが定義されていて、列挙型Squareからそのマスだけを指す Bitboardを簡単に取得できるようにしているようです。Bitboard::init()というところで、この値は初期化されていました(これは main.cpp で呼び出されていました)。これによって、Bitboardと Square の bit 演算が定義されています。同様に、各ランクを指す RankBBやファイルを指すFileBBも定義されていました。確かに for 文などを使わず Bitboard を使えば演算が速くなるというのは、この時点で実感ができます。さらにですが、AdjacentFilesBBというものもあり、これは隣のファイルを表すものでした。いちいち AFILE かどうかとかを場合分けしなくて良いわけだ。確かに速くなりそうですね。その他、とても便利な定数が用意されていました。

まずこれらを漁った感想として、面倒な操作を前倒しにできて、さらにそれがたったの 64bit で表現できてしまうという利点があるようです。

ちょっと胃もたれしてきました。別の話題に移りましょう。

実際の盤面はどこに...?

実際のところ盤面はどのように定義されているかというと、実は分かりづらいことに position.h という場所にあり、

class Position {
    // ... いろいろ書いてあって ...
private:
  Bitboard byTypeBB[PIECE_TYPE_NB];
  Bitboard byColorBB[COLOR_NB];
}

とされていました。
SFでは駒のタイプごとに Bitboard を作り、また色ごとにも Bitboard を作っているそうですね。頭いい。
確かに駒の色ごとにしたら、どこまで動けるかは byColorBBだけを参照すれば良いですからね。

何も方針を立てずにメモをしているので今気づいたことですが、どうも Positionクラスを見ればSFさんによるチェス盤の表現が分かるということですかね。そういうわけで次は Positionクラスを見てみます。

Position を見る

膨大なデータ量のクラスであるところの Positionです。僕は今まで再帰によりたくさんインスタンスを作成するために盤面を表現するクラスのデータ量は極力押さえておきました。多少の速度は犠牲にしてね。そうして SF のプログラムを見てみるとどうでしょうか。思いっきりデータ量を増して高速化を測っています。例えば

  Square pieceList[COLOR_NB][PIECE_TYPE_NB][16];

というプログラムがありました。当然現在残っているPieceを保存しているのでしょう。Type は Square ということで Square -> Piece である bitboard と対比的に Piece から Square を参照できるようにしているわけですね。おそらくこの利点としては、チェックやピンの確認などが高速化できる点だと思います。
また、この変数の更新は、1手指す事に更新すれば良いので、特にそこで遅くなることもないでしょう。
頭いい2

今回はこの程度でしょうか。また次気が向いた時に書きます。多分次回はまた Bitboard の話に戻ります。