2016の23日目の記事です。www.adventar.orgオセロとビット演算オセロは盤面サイズが8x8=64マスなので、64bit変数を2つ用意し、1つめを自分の石(あるいは黒石)の位置を、2つめを相手の石(あるいは白石)を表すために使うと合計128ビットで自然に表現できます。diaryで紹介したような方法で効率的に行なえます。着手可能位置の生成はタテ・ヨコ・ナナメの一直線上をpextなどで取ってきて表引きをすることにより、ある程度の速度で可能ですが、(38=6561なのでL1キャッシュに乗る程度の大きさとはいえ)メモリアクセスが必要になってしまいそれなりの時間がかかります。以下、ビットボードには以下のようにマス目とビット列の対応が付いているとします(0が最下位ビット)。参考文献の方法を使っています。参考文献のOpenCL風のコードがわかりやすいのでそれを元に動作を解説します。マス目をマスクするビット列を計算するposからみて相手の石が途切れたところをclzで求め、自分の石の位置とandを取ることでひっくり返せるかどうかがわかる。outflankの各要素は高々1ビットが立つ。2でoutflankより上位のビットが全部1になる。これとマスクを取ることでひっくり返る石の位置がわかる。後半部分は下位ビットから見ていって相手の石が途切れたところを探します。これは関係ない場所を1埋めしてから+1すればよいです。あとは単に前半部分の逆です。GitHubにあります。このコードでは各方向に対するひっくり返る石をビット演算で求めることができ、AVX2を使うと256bit一気に操作でき高速です。clzの並列版はないので、立っている一番上のビット位置を頑張って求めます。diaryと違い、1<<bsrを求める関係で浮動小数点数への変換より下位ビット埋め+vpshufb+最下位ビット抽出のほうが速いです。着手可能位置(mobility)の計算をビットボードで行う方法はd.hatena.ne.jpで言及されているビットシフトを繰り返す方法が知られているようです。今回はそれより高速な方法を解説します。この方法では、石を置くと左に向かって相手の石をひっくり返せるような位置を一気に列挙します。これを盤面を回転・反転させて8方向に対して行うことで着手可能位置を計算することができます。1列分の着手可能位置を求めるコードは以下の通り。o);}このプログラムの動作を具体例を元に解説します。0となり着手可能位置が計算できました。これを64ビット*2の盤面全体に対して一気にやろうとすると、8ビット単位のシフトや足し算が必要になります。うまくマスクを取って64ビット演算に帰着してもいいですが、SSE/AVX2には8ビット単位の加算が用意されているので、それを使うと良いでしょう。1ビットの左シフトはp+pで実現できます。SSEなら2並列、AVX2なら4並列で着手可能位置を求められるので、8方向に対する計算をかなり高速化することができます。全体をSSE/AVX2で書いたものがこちらになります。22日目】この記事はKMCアドベントカレンダー22日目の記事です。「サイゼリヤで1000円あれば最大何kcal摂れるのか」を全探索で解いてみたLeapMind株式会社に入社しました月別アーカイブはてなブログをはじめよう!PrimeNumberさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。