WCSC25 その8 技術的なこと(探索)

単純なアルファベータとビットボードと駒割で作り、そこへPVSや高速1手詰めなどを実装していき、最終的にはStockfishの枝刈りを全て実装した(つもりだが抜けや間違いや過剰が相当あると思う)。アイデアを放置しているコードがあちこちに残っていたりして、全体的に未完成ではある。

置換表

ずっとオープンアドレス法とかいうのを使っていたのだが、スピードと使いやすさで劣るかもしれないので普通のに書き換えた。データへのアクセスも、わかりやすさを重視するようにした。ロックレスハッシュを意識した作りになっているが、未実装。

置換表の1エントリは16byteで、半分が局面のハッシュキー、半分がデータとなっている。データ部分が64bitしかないので、持ち駒の情報はハッシュキーの側に入れている。「持ち駒だけが違う」という局面を検出するために、局面を保持するPosition構造体は盤面と手番だけのハッシュキーを持ち、置換表に登録するときはその下位32bitへ持ち駒をxorしている。「盤面と手番だけのハッシュキー」の下位bitの情報は少し失われるが、下位bitは置換表の格納場所で決まっているのでデメリットが小さい(ハッシュ衝突がそれほど起こりやすくならない)。

盤面と手番が同じで持ち駒の歩だけが1枚変化しているようなケースでは、比較対象が棋譜にある場合と探索の祖先である場合は+∞や-∞の評価値を返したい。それを判定するため、持ち駒の変化を検出するのにはビット演算を使う。また、今の対局で既に現れた局面かどうか、探索の祖先かどうかは、置換表のデータに1bitずつ記録する場所を作った。探索の祖先であることを示すbitを、時間制限で探索を打ち切ったときに消去するのが面倒なので、もう少しいい方法があるかもしれない(ていうか普通の方法をまず試せ)。

それ以外のケースで、持ち駒が減っているのに置換表の評価値がβ以上ならβカットというのもやっている(持ち駒が増えてα以下の場合も)。ただ、わずかな探索ノード数削減のために探索の構造が変わってしまうのは、history等を考慮すると果たして強くなっているのかという疑問は残る。

千日手

祖先の局面かどうかの判定は、上で書いたように置換表を使う。各手番が何回連続で王手しているかは記録してあるので、それが2回以上だったら連続王手の千日手とする(本当は2回固定では危険かもしれない)。
静止探索内でも置換表を見ているので、ついでに判定しているが、静止探索でどこまでやるべきかはよくわからない。

各種延長

SingularExtensionはStockfish通り。リキャプチャーが0.5手(Root以外)。王手は0.5手で、SEEが非負なら1手。

王手か王手回避でβカットもfail-lowもせずbestValueの更新で負けでない評価値が1回しかなかった場合に、置換表でその局面に印を付けて、以降ハッシュ手で+0.5手延長する、というのもやっているが、強くなっているかは不明(一部の局面で詰みが速く見えるのは確か)。

評価関数

評価関数が駒割と2駒関係だけなので、全て差分計算している。ただ、差分にしろ直接にしろ、あまり高速に計算できている自信はない。

2駒関係の絶対値の和で評価値を正規化するようなことを考えた(仕掛けて評価値が上がりすぎるのを抑制するため)が、劣勢になってからも素直すぎる棋風で全然ダメだった。特に対人戦では嫌らしさが全くない。

手番を持っているほうへ1点だけ加点していた時期もあったが、実は弱くなっていた。主な原因は枝刈りとの相性のようだった。ただ、少し修正しても強くはならない。静止探索でStand-Patを使っているのもそうだけど、探索ではけっこう非人間的な考え方で高速化してたりして、しかもそれが絶妙に成立してたりする。相当に探索を理解したうえで考えないと、手番を評価に入れるのは難しそうだ。

入玉勝ち宣言

とりあえず実装しただけ。本当は宣言できるようなドーピングをした評価関数とセットで実装したかった。玉の位置をまずチェックするので、非入玉形ならNPSが落ちるような悪影響はほとんどないはず(入玉形ではけっこう遅くなるのが問題、差分計算するべきかなあ)。

探索開始前にはもちろん宣言勝ちかをチェックするとして、探索中はどの部分でチェックしたらいいか迷った。結局、高速1手詰めの中で呼び出すことにした。1手詰めは置換表に登録された局面では呼び出す必要がないが、宣言勝ちも同じ理屈で置換表に現在の局面があれば省略できる。

高速1手詰め

よくわからなかったので、玉の周りだけ利きを取得して詰まないケースを除外していく感じで実装した。何か違う気もするが、Bonanza方式も何か遅く見えてやる気がしなかった。高速化を考えると条件がどんどん複雑になっていって、もう読む気がしない。

高速1手詰めは、かなり遅くても実用になる(詰みの発見が2手近く違う)ので、早めに実装して損はない。

手を進める

駒を移動する動作は、「移動元の駒を消す」「移動先に駒を出す」の2つに分けている。差分計算するのにはわかりやすくてよかったが、ここは高速化の余地がある気もする。ただ、そうだとしても、少なくともこのくらいはわかりやすく書きたい。コード量を増やしたくない。

手生成

ここは、4年前に作っていた部分からほとんど論理構造が変わっていない(変数名やラムダ式など見た目はかなり変わっている)。ビットボードで手番の駒がある位置を見て、その駒が何かを配列から得る。Bonanzaなどは各駒のビットボードを見ているそうなので、これは遅いのかもしれないが、ただBonanza式にしてもそんなに速くなると思えなかったので今まで放置してしまった。

チェスと比べて「成」の価値が低いので、その点も考える必要があるかもしれない。