Entries

連珠をビットボードで表現してみる【ビット演算テクニック Advent Calendar 2016 6日目】

概要


 今日、12/6は「連珠」が生まれた日とされます。それにちなんで、今回は連珠をビットボードで表現し、各種操作をビット演算で行う方法について紹介したいと思います。以下の記述では、連珠をある程度知っているものと仮定して書きますのでご注意ください。
 なお、タイトルにもありますように、当記事は「ビット演算テクニック Advent Calendar 2016」の6日目です。


www.adventar.org



盤面の表現


 まず、連珠の盤面をビットボードでどう表現するかについて見ていきましょう。
 15道盤ですので交点は225個あり、ビット表現には225ビット=28.125バイト必要です。ただ、都合がいいことにAVX2には256bitの整数型がありますのでありがたく利用します。
 また、unionを定義し、16bit整数型の配列としても利用するようにすれば、各行も効率よく取り扱えます。

#include<immintrin.h>
#include<cstdint>
struct BitBoard {
 union {
  __m256i board_;
  uint16_t line_[16];
 };
};



石を置く/戻す


 連珠は囲碁やオセロ等と違い、打った石が消えたり変わったりすることはありません。
 したがって盤面操作も、置く場合はその位置にビットをXOR演算し、戻す場合もXOR演算すればそれで済みます。毎回置く位置のビットだけ立ったビットボードを用意して……は無駄がありますので、事前に配列として保持しておきます。

struct BitBoard {
 // 石がないなら置き、あれば取り去る
 void ReverseBit(const size_t position) noexcept {
  *this ^= kPositionArray[position];
 }
 // 強制的に置く
 void SetBit(const size_t position) noexcept {
  *this |= kPositionArray[position];
 }
 // 強制的に取り去る
 void UnsetBit(const size_t position) noexcept {
  *this &= ~kPositionArray[position];
 }
};



盤面が等しいか判定


 AVX2などにおいて、SIMD型の比較といえばCMPEQ系列です。_m256i型なら_mm256_cmpeq_epi64 命令を使うのが普通でしょう。
 ただ、比較の際はより速い方法が存在しました。比較対象とXORを取った後、全てのbitが0かどうかを_mm256_testz_si256 命令で判断する方法です。ちなみに連珠の盤面が225交点しかない以上、31bit分余ることになりますが、適切にビットマスクすれば余り部分は常に0であり、各種判定に影響しません。


上下左右および斜めにシフト


 さて、連珠において最も問題になるのは各種判定です。五連・四・三を高速に判定できなければビットボード化した意味がありません。
 そのため、まずは盤面全体をシフトさせる方法を考えます。『ビットシフト命令でズラした後に、余計なビットをマスクして取り去ればOK』だと思っていませんか?甘い!
 確かに、左右にズラす場合は_mm256_slli_epi16 命令_mm256_srli_epi16 命令で事足ります。しかし、これらの命令は256bit全体ではなく分割した各要素に適用されます。つまり、最大でも64bit毎しかシフトできない(境界を乗り越えられない)のです。16bitシフトする上下シフトや、15・17bitシフトする斜めシフトをする際はこれらの命令がそのままでは使えません。

ビットシフト命令の弊害
 間に合わせの対策としては、一旦_mm256_store_si256 命令で書き出した後に_mm256_loadu_si256 命令でズラして読み込むものがあります。ただ、言うまでもなくこの方法だと遅いので、より速い方法が欲しいところ……。
 と思ってググっていたところ、妙案を発見しました。_mm256_permute2x128_si256 命令で再配置を施した後に_mm256_alignr_epi8 命令で読み込み、最後にビットシフトやマスクで調整するといった手法です。ストアしなくていいので速い……のですが完全に職人技で理屈がよく分かりません><

参考:「Emulating shifts on 32 bytes with AVX」(StackOverFlow)


各種判定処理


 盤面シフトまで実装したので、判定もスムーズに行なえます。
 まず五連判定ですが、例えば上下方向に判定する際は、元のビットボードに上 or 下方向に1~3路シフトさせた盤面をAND演算して立っているbitを探すだけでOKです。

(厳密には長連判定も必要だったりしますが)
無題2

  次に達四判定ですが、同じく2路までシフトさせた盤面をAND演算……するだけでなく、「五連」になる位置に打ったら長連にならないかも判断する必要があります。つまり、黒だと『達四候補から一間飛びの位置に黒石が無いか』も見る必要が生じます。
 これに限らず、「相対的にn路離れた位置にある石」の有無を判断させる際は、「n回ビットシフトしてAND演算で重ねる」ことで判断できます。これらから、ほぼ条件判断を挟まずに判定処理を行うことができます。


実際に実装してみた(途中)


 これらの考えを実装したものがこちらの連珠ソフト「Shioi」のIonaブランチになります。

github.com


 ……と言いたいところでしたが、色々な理由で制作が中断してますごめんなさい><
 Advent Calendarの次の日は誰になるのでしょう?

www.adventar.org

関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/86-154f3965

トラックバック

コメント

[C69] Qiitaの記事を拝見しました

YSR氏の「ビットボードの凄さをざっくりと解説してみる」を最近見つけましたので読ませて頂きました。

http://qiita.com/YSRKEN/items/29829c7f5beae7900f36

今日まさに、ビット演算テクニック Advent Calendar 2016 ご担当だったのですね。なんらかご参考になればと思い、上記記事のGistに、コメントを入れました。しつこくてすみません。

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

08 ≪│2017/09│≫ 10
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: