単純なアルファベータとビットボードと駒割で作り、そこへ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つに分けている。差分計算するのにはわかりやすくてよかったが、ここは高速化の余地がある気もする。ただ、そうだとしても、少なくともこのくらいはわかりやすく書きたい。コード量を増やしたくない。