オセロ最終1手最適化
#オセロAI で最後の盤面まで読み切るとき、最後の1手は返る石を厳密に求める必要がなく、返る石の数だけわかれば良い。8マスの石の並び(手番側、空きマス(1マスのみ)、相手)のすべてのパターンについて、返る石の数をあらかじめ計算しておき、探索中には縦横斜めのそれぞれの方向の手番側の石の配置を8bit整数に直し、表引きをする。 縦横斜め4方向についてそれぞれ表引きをするので、メモリ参照は4回することになる。
最終1手では~player == opponent | put_bitが成立するので、8マスの石の並び方は8bit分=256通り考えれば良い。さらに、空きマスの位置についても8マス分考えれば良い(厳密にはもっと少なくて済むけど)ので、このテーブルの要素数はuint8_t N_LAST_FLIP[256][8]となる。N_LAST_FLIP[8マスのplayerのbit列][そのbit列の中での空きマスの位置]を4方向について足していけば、返る石の個数がわかる。
表引きの並列化
最終1手で手番側がパスだった場合、相手側の石の並びでまた表引きすることになる。つまり、通常の実装では、最終手でパスが発生すると8回のメモリ参照が発生する。ただ、実装上の工夫でこれを6回に減らせる。
返る石の数を記録したテーブルに、「相手の手番だとしたときに(相手の石として)返る石の数<<8 + 自分の手番で返る石の数」を記録しておくと、縦横だけはパス判定前にほぼ追加計算なしで手番側と相手側の返る石の個数を同時に表引きできる。
つまり、以下のような感じで実装する
縦横で返る石の数(手番側、相手側)を同時計算 (メモリ参照2回)
斜めで返る石の数(手番側)を計算 (メモリ参照2回)
もし、手番側がパスだったら
斜めで返る石の数(相手側)を計算 (メモリ参照2回)
単純に返る石を計算するのとどっちが速いか
AVX512だと返る石を愚直に計算したほうが速いこともあるらしい