LoginSignup
19
10

More than 5 years have passed since last update.

@rimol

JavaScriptでのリバーシのビットボードの実装

Posted at

はじめに

リバーシのビットボードはもう既に洗練されていますが（後にリンクを張ります）、これらの方法はほとんど全て64ビット整数が使える環境用です。JavaScriptは64ビット整数が使えないので、これらの優秀なコードがそのまま使えません。

そこでこの記事では、JavaScriptでの、ある程度速いビットボードの実装を紹介します！

実際にJavaScriptで作ったリバーシはこちら。序・中盤は9手読み、終盤20手読み切り(遅くても10秒程度、iPhone 6s上)します。僕は某リバーシアプリでレート1600ぐらい(強くない)ぐらいですが全く歯が立ちません。まあでも評価関数がかなり適当で、たまに簡単に角をくれたりするので絶対に勝てないことはないと思います。

注意

基本的なビット演算を理解しているものとして書きます。

1. 石数を数える (popcount)

popcount.js
function popcount64(x1, x0) {
    let t0 = x1 - (x1 >>> 1 & 0x55555555);
    t0 = (t0 & 0x33333333) + ((t0 & 0xcccccccc) >>> 2);
    let t1 = x0 - (x0 >>> 1 & 0x55555555);
    t0 += (t1 & 0x33333333) + ((t1 & 0xcccccccc) >>> 2);
    t0 = (t0 & 0x0f0f0f0f) + ((t0 & 0xf0f0f0f0) >>> 4);
    return t0 * 0x01010101 >>> 24;
}

よくあるやつを少しひねったバージョンですね。

コード解説

まず1行目の

popcount.js
let t0 = x1 - (x1 >>> 1 & 0x55555555);

ですが、これはビット列を2ビットごとに区切ったときに、その区切り1つにあるビットの数を計算しています。なぜこれで求められるのかというと、例えば、ある区切りのビットが10のとき、2ビット目の立っているビットは2個としてカウントされているので、2ビット目のビットが立っているとき、その区切りにおいて1を引けば区切りごとのビットの数が求められるというわけです。

こうすることで2行目のコードのようにするより、ANDが1つ減らせますね。

example.js
// 数えたいビット列: 10 11 00 01
// 各ビットの数　　:  1  2  0  1
// 計算する前　　　:  2  3  0  1  <- 2ビット目のビットが2個としてカウントされている
// (10 11 00 01) >>> 1 & (01 01 01 01) = 01 01 00 00
// これを引けば、各区切りごとのビットの数が計算できる
// 0x55 == 0b01010101

次に、

popcount.js
t0 = (t0 & 0x33333333) + ((t0 & 0xcccccccc) >>> 2);

1行目のコードで、2ビットごとのビットの数が求められたので、2行目では、4ビットごとのビットの数を求めます。こっちはそんなに複雑ではありません。

example.js
// 1行目の結果:  01 10 00 01
// イメージ:
//   (0110 0001) & (0011 0011) =   0010 0001
//   (0110 0001) & (1100 1100) = +   01 0000|00 >>> 2
//                                 0011 0001
// 0x33 = 0b00110011, 0xcc = 0b11001100

x1, x0のそれぞれのビット列の4ビットごとのビットの数が求まったら、それらを足すと、x1, x0それぞれのビット列の4ビットごとのビットの数の和が求まります。このビットの数の和は最大で8なので、4ビットからあふれることはありません。これが4行目のコードになります。

5行目も、同じように8ビットごとのビットの数を求めています。

そして6行目です。なにやら掛け算がありますが、難しくはありません。

popcount.js
t0 * 0x01010101 >>> 24;

まず、2^nの掛け算は左にnシフトするのと同じです。これを利用します。

また

0x01010101 == (0x00000001 + 0x00000100 + 0x00010000 + 0x01000000)

なので、いわゆる分配法則で、

x * 0x01010101 == x * 0x00000001 + x * 0x00000100 + x * 0x00010000 + x * 0x01000000

となるので、x * 0x01010101は

x << 0 + x << 8 + x << 16 + x << 24

を計算していることになります。t0には8ビットごとのビットの数が入っているので、t0 * 0x01010101を計算すると上位8ビットに求めたい数が来るわけです。そこで最後に右に24シフトして、無事ビットの数が求まりました。

2. 置ける場所の列挙(mobility)

mobility.js
// p1, p0: 自石ビット
// o1, o0: 敵石ビット
function mobility(p1, p0, o1, o0, out) {
    let mob1 = 0;
    let mob0 = 0;

    let blank1 = ~(p1 | o1);
    let blank0 = ~(p0 | o0);

    let mo1 = o1 & 0x7e7e7e7e;
    let mo0 = o0 & 0x7e7e7e7e;

    // 右向き

    let ps1 = p1 << 1;
    let ps0 = p0 << 1;

    mob1 = (mo1 + ps1) & blank1 & ~ps1;
    mob0 = (mo0 + ps0) & blank0 & ~ps0;

    // 左向き

    let t0 = p0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;

    mob0 |= t0 >>> 1 & blank0;

    let t1 = p1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;

    mob1 |= t1 >>> 1 & blank1;

    // 上下

    mo1 = o1 & 0x00ffffff;
    mo0 = o0 & 0xffffff00;

    // 下向き
    t0 = p0 << 8 & mo0;
    t0 |= t0 << 8 & mo0;
    t0 |= t0 << 8 & mo0;

    t1 = (p1 << 8 | (t0 | p0) >>> 24) & mo1;
    t1 |= t1 << 8 & mo1;
    t1 |= t1 << 8 & mo1;

    mob1 |= (t1 << 8 | t0 >>> 24) & blank1;
    mob0 |= t0 << 8 & blank0;

    // 上
    t1 = p1 >>> 8 & mo1;
    t1 |= t1 >>> 8 & mo1;
    t1 |= t1 >>> 8 & mo1;

    t0 = (p0 >>> 8 | (t1 | p1) << 24) & mo0;
    t0 |= t0 >>> 8 & mo0;
    t0 |= t0 >>> 8 & mo0;

    mob1 |= t1 >>> 8 & blank1;
    mob0 |= (t0 >>> 8 | t1 << 24) & blank0;

    // 斜め

    mo1 = o1 & 0x007e7e7e;
    mo0 = o0 & 0x7e7e7e00;

    // 右下
    t0 = p0 << 9 & mo0;
    t0 |= t0 << 9 & mo0;
    t0 |= t0 << 9 & mo0;

    t1 = (p1 << 9 | (t0 | p0) >>> 23) & mo1;
    t1 |= t1 << 9 & mo1;
    t1 |= t1 << 9 & mo1;

    mob1 |= (t1 << 9 | t0 >>> 23) & blank1;
    mob0 |= t0 << 9 & blank0;

    // 左上
    t1 = p1 >>> 9 & mo1;
    t1 |= t1 >>> 9 & mo1;
    t1 |= t1 >>> 9 & mo1;

    t0 = (p0 >>> 9 | (t1 | p1) << 23) & mo0;
    t0 |= t0 >>> 9 & mo0;
    t0 |= t0 >>> 9 & mo0;

    mob1 |= t1 >>> 9 & blank1;
    mob0 |= (t0 >>> 9 | t1 << 23) & blank0;

    // 左下
    t0 = p0 << 7 & mo0;
    t0 |= t0 << 7 & mo0;
    t0 |= t0 << 7 & mo0;

    t1 = (p1 << 7 | (t0 | p0) >>> 25) & mo1;
    t1 |= t1 << 7 & mo1;
    t1 |= t1 << 7 & mo1;

    mob1 |= (t1 << 7 | t0 >>> 25) & blank1;
    mob0 |= t0 << 7 & blank0;

    // 右上
    t1 = p1 >>> 7 & mo1;
    t1 |= t1 >>> 7 & mo1;
    t1 |= t1 >>> 7 & mo1;

    t0 = (p0 >>> 7 | (t1 | p1) << 25) & mo0;
    t0 |= t0 >>> 7 & mo0;
    t0 |= t0 >>> 7 & mo0;

    mob1 |= t1 >>> 7 & blank1;
    mob0 |= (t0 >>> 7 | t1 << 25) & blank0;

    // outには適当に使い回しのオブジェクトを渡す。
    // いちいちオブジェクトを作って返すのは実行速度に響きそうなので。
    // 全部展開するのが一番いいと思うが、めんどくさい。
    out.mob1 = mob1;
    out.mob0 = mob0;
}

コード解説

まず石を置ける場所とは、右向きにひっくり返せる場所を例に考えると、

その場所から右向きに1つ以上の敵石がつながっていてかつ、その敵石の並びが途切れた場所に自石があるような場所

です。これは、

現在の自石から左向きに1つ以上の敵石がつながっていてかつ、その敵石が途切れた場所が空白であれば、そこは石が置ける場所である

と考えることができます。ここで紹介しているコードは2つのテクニックを使っていますが、どちらもこの考え方が元になっています。では解説していきます。

左向きに返せる位置を求める

mobility.js
t0 = p0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;

mob0 |= t0 >>> 1 & blank0;

自石ビットを右にシフト、敵石とAND、...を6回繰り返すことによって、自石の右に連続している敵石ビットを全て立たせます。最後にもう一度シフトして、空白ビットとANDを取れば、左向きに返せる場所が求められます。JavaScriptは64ビット整数が使えないので、盤面の上側と下側でそれぞれ同じ計算をする必要があります。

右向きに返せる位置を求める

mobility.js
ps1 = p1 << 1;
ps0 = p0 << 1;

mob1 = (mo1 + ps1) & blank1 & ~ps1;
mob0 = (mo0 + ps0) & blank0 & ~ps0;

こちらの向きでも、シフトを繰り返すことによって同じように求められるのですが、このテクニックを使えばなんと2行で求められます！

自石ビットを左に1シフトして、敵石ビットに足すことで、自石の左に敵石があれば繰り上がって敵石の連続が切れる位置にビットが立ちます。これで立ったビットのマスのうち、空白マスであるビットは、右向きに石を返せる場所であるので、空白マスでANDを取ります。また、左に敵石がなければ自石ビットの1つ左にビットが立つのでこれを除去するためにさらに~(p << 1)でANDを取ります。

足し算で次の行にまで繰り上がるのを阻止するためと、左端の自石が次の行に行って足し算で繰り上がってしまうのを防ぐために、予め敵石ビットを0x7e7e7e7eでマスクしておく必要があります。

上下/斜め 向きに返せる位置を求める

mobility.js
t0 = p0 << 8 & mo0;
t0 |= t0 << 8 & mo0;
t0 |= t0 << 8 & mo0;

t1 = (p1 << 8 | (t0 | p0) >>> 24) & mo1;
t1 |= t1 << 8 & mo1;
t1 |= t1 << 8 & mo1;

mob1 |= (t1 << 8 | t0 >>> 24) & blank1;
mob0 |= t0 << 8 & blank0;

この向きに対しては、64ビット整数が使えないJavaScriptにおいて、今までの手法がそのまま使えません。

例として、下向きにひっくり返せる場所を求めるコードを解説すると、まず下側のビットボードにおいて、自石の上に続く敵石のビットを立たせていきます(t0)。上側のビットボードでは、上側と下側で連続している石も考慮しないといけないので、左に8シフトするとあふれるt0とp0の上位8ビットを上側のビットボードの下位8ビットに持ってきます。あとは同じですね。

他の方向に対しても、敵石につけるマスクを変えることで求められます。

3. ひっくり返る石を求める(flip)

僕の実装では高速化のために、盤面の上側に置いたときと、下側に置いたときで呼ぶ関数を分けています。

flip1.js
// 上側に置いたとき
// p1, p0: 自石ビット
// o1, o0: 敵石ビット
// sq_bit: 石を置くマスのビット(2^n)
function flip1(p1, p0, o1, o0, sq_bit, out) {
    let f1 = 0;
    let f0 = 0;

    let mo1 = o1 & 0x7e7e7e7e;
    let mo0 = o0 & 0x7e7e7e7e;

    // 左
    let d1 = 0x000000fe * sq_bit;
    let t1 = (mo1 | ~d1) + 1 & d1 & p1;
    f1 = t1 - ((t1 | -t1) >>> 31) & d1;

    // 左上
    d1 = 0x08040200 * sq_bit;
    t1 = (mo1 | ~d1) + 1 & d1 & p1;
    f1 |= t1 - ((t1 | -t1) >>> 31) & d1;

    // 上 マスクは付けてはだめ。
    d1 = 0x01010100 * sq_bit;
    t1 = (o1 | ~d1) + 1 & d1 & p1;
    f1 |= t1 - ((t1 | -t1) >>> 31) & d1;

    // 右上
    d1 = 0x00204080 * sq_bit;
    t1 = (mo1 | ~d1) + 1 & d1 & p1;
    f1 |= t1 - ((t1 | -t1) >>> 31) & d1;

    // 右
    t1 = sq_bit >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;
    t1 |= t1 >>> 1 & mo1;

    f1 |= t1 & -(t1 >>> 1 & p1);

    // 右下
    t1 = sq_bit >>> 9 & mo1;
    t1 |= t1 >>> 9 & mo1;
    t1 |= t1 >>> 9 & mo1;

    let t0 = (t1 | sq_bit) << 23 & mo0;
    t0 |= t0 >>> 9 & mo0;
    t0 |= t0 >>> 9 & mo0;

    let t = t1 >>> 9 & p1 | (t0 >>> 9 | t1 << 23) & p0;
    t = (t | -t) >> 31;

    f1 |= t1 & t;
    f0 |= t0 & t;

    // 下 敵石にマスクはつけない
    t1 = sq_bit >>> 8 & o1;
    t1 |= t1 >>> 8 & o1;
    t1 |= t1 >>> 8 & o1;

    t0 = (t1 | sq_bit) << 24 & o0;
    t0 |= t0 >>> 8 & o0;
    t0 |= t0 >>> 8 & o0;

    t = t1 >>> 8 & p1 | (t0 >>> 8 | t1 << 24) & p0;
    t = (t | -t) >> 31;

    f1 |= t1 & t;
    f0 |= t0 & t;

    // 左下
    t1 = sq_bit >>> 7 & mo1;
    t1 |= t1 >>> 7 & mo1;
    t1 |= t1 >>> 7 & mo1;

    t0 = (t1 | sq_bit) << 25 & mo0;
    t0 |= t0 >>> 7 & mo0;
    t0 |= t0 >>> 7 & mo0;

    t = t1 >>> 7 & p1 | (t0 >>> 7 | t1 << 25) & p0;
    t = (t | -t) >> 31;

    f1 |= t1 & t;
    f0 |= t0 & t;

    out.f1 = f1;
    out.f0 = f0;
}
flip0.js
// 下側に置いたとき
// p1, p0: 自石ビット
// o1, o0: 敵石ビット
// sq_bit: 石を置くマスのビット(2^n)
function flip0(p1, p0, o1, o0, sq_bit, out) {
    let f1 = 0;
    let f0 = 0;

    let mo1 = o1 & 0x7e7e7e7e;
    let mo0 = o0 & 0x7e7e7e7e;

    // 左
    let d0 = 0x000000fe * sq_bit;
    let t0 = (mo0 | ~d0) + 1 & d0 & p0;
    f0 = t0 - ((t0 | -t0) >>> 31) & d0;

    // 左上
    t0 = sq_bit << 9 & mo0;
    t0 |= t0 << 9 & mo0;
    t0 |= t0 << 9 & mo0;

    let t1 = (t0 | sq_bit) >>> 23 & mo1;
    t1 |= t1 << 9 & mo1;
    t1 |= t1 << 9 & mo1;

    let t = (t1 << 9 | t0 >>> 23) & p1 | t0 << 9 & p0;
    t = (t | -t) >> 31;

    f1 |= t1 & t;
    f0 |= t0 & t;

    // 上 敵石にマスクはつけない
    t0 = sq_bit << 8 & o0;
    t0 |= t0 << 8 & o0;
    t0 |= t0 << 8 & o0;

    t1 = (t0 | sq_bit) >>> 24 & o1;
    t1 |= t1 << 8 & o1;
    t1 |= t1 << 8 & o1;

    t = (t1 << 8 | t0 >>> 24) & p1 | t0 << 8 & p0;
    t = (t | -t) >> 31;

    f1 |= t1 & t;
    f0 |= t0 & t;

    // 右上
    t0 = sq_bit << 7 & mo0;
    t0 |= t0 << 7 & mo0;
    t0 |= t0 << 7 & mo0;

    t1 = (t0 | sq_bit) >>> 25 & mo1;
    t1 |= t1 << 7 & mo1;
    t1 |= t1 << 7 & mo1;

    t = (t1 << 7 | t0 >>> 25) & p1 | t0 << 7 & p0;
    t = (t | -t) >> 31;

    f1 |= t1 & t;
    f0 |= t0 & t;

    // 右
    t0 = sq_bit >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;
    t0 |= t0 >>> 1 & mo0;

    f0 |= t0 & -(t0 >>> 1 & p0);

    // 右下
    t0 = sq_bit >>> 9 & mo0;
    t0 |= t0 >>> 9 & mo0;
    f0 |= t0 & -(t0 >>> 9 & p0);

    // 下 敵石マスク無し
    t0 = sq_bit >>> 8 & o0;
    t0 |= t0 >>> 8 & o0;
    f0 |= t0 & -(t0 >>> 8 & p0);

    // 左下
    t0 = sq_bit >>> 7 & mo0;
    t0 |= t0 >>> 7 & mo0;
    f0 |= t0 & -(t0 >>> 7 & p0);

    out.f1 = f1;
    out.f0 = f0;
}

コード解説

敵石をひっくり返せる条件の、

敵石がその向きに1つ以上並んでいる
敵石の並びが途切れた位置に自石が存在する

をいかにビット演算のみでチェックするかがポイントです。

左・左上・上・右上 向きにひっくり返る石を求める

盤面の上側に石を置いたとき専用（左向き以外）です。

flip.js
d0 = 0x000000fe * sq_bit;
t0 = (mo0 | ~d0) + 1 & d0 & p0;
f0 = t0 - ((t0 | -t0) >>> 31) & d0;

解説が非常に難しいのですが、

1行目では、求めたい向きのマスクを作っています。

2行目では、足し算でその向きに連続している敵石が途切れる位置にビットを立てています。マスクをしているので、このとき立つビットは1個以下で、そのビットが表すマスに自石があればひっくり返せます。

3行目では、ビットが立っている(=挟める)とき、1を引くことで、そのビットより下のビットを全て立てることができ、これと最初に作ったマスクでANDを取ればひっくり返る石が求まります。

(t0 | -t0) >>> 31 は (t0 | -t0) が t0 が0でないとき、32ビット目に必ずビットが立つことを利用して、t0 != 0 と同等のコードを実現しています。Chromeで実験すると、わざわざこうするほうが速かったのでこうしています。

右向きにひっくり返る石を求める

flip.js
t0 = sq_bit >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;
t0 |= t0 >>> 1 & mo0;

f0 |= t0 & -(t0 >>> 1 & p0);

mobilityのコードの応用です。-(t >>> 1 & p) で打つ位置の右に連続している敵石のすぐとなりに自石があれば、その自石より上のビットをすべて立てます。これとANDを取ることでひっくり返るかどうかの判定ができます。

その他の向きにひっくり返る石の求め方

flip.js
// 下向きにひっくり返るか石を求める
t1 = sq_bit >>> 8 & o1;
t1 |= t1 >>> 8 & o1;
t1 |= t1 >>> 8 & o1;

t0 = (t1 | sq_bit) << 24 & o0;
t0 |= t0 >>> 8 & o0;
t0 |= t0 >>> 8 & o0;

// (t1, t0) >> 8 & p !== 0 ? -1 : 0;
t = t1 >>> 8 & p1 | (t0 >>> 8 | t1 << 24) & p0;
t = (t | -t) >> 31;

f1 |= t1 & t;
f0 |= t0 & t;

盤面の上側と下側をまたぐ向きにも、mobilityのコードの応用が効きます。

ポイントは、ひっくり返せるかどうかの判定です！盤面の上側に石を置いたときに、下向きにひっくり返る石を求めるコードで解説します。

bitboard.js
t = t1 >>> 8 & p1 | (t0 >>> 8 | t1 << 24) & p0;
t = (t | -t) >> 31;

1行目では、t1, t0を64ビット整数とみて右に8シフトして、自石ビットとANDを取っています。このときt != 0であればひっくり返せることが分かります。そこで2行目で t != 0 なら -1 (-1は2進数で全ビットが立っている状態)、t == 0 なら 0 とマスクを作っているわけです。
ここのポイントは、論理シフトではなく算術シフトを使っているところで、こうすることで論理シフトを使うより1演算減らすことができます。

bitboard.js
// 論理シフトを使うと-演算がさらに必要になる。
t = -((t | -t) >>> 31);

おわりに

文章力がないので非常に読みにくいと思います。ごめんなさい。
誰かの役に立てれば嬉しいです。

最初にURLを貼った僕のリバーシのソースはこちら（汚いです）。

主な参考にしたサイトやコード

右向きのコードは天才過ぎて涙が出ました（嘘）、でも本当にすごいです
http://primenumber.hatenadiary.jp/entry/2016/12/26/063226
もう少しわかりやすくFlipを解説してくれています
http://t-ishii.cocolog-nifty.com/blog/2014/02/flip-02bb.html
すごい64ビット整数演算(シフト、足し算、引き算など)の実装があります
https://github.com/saharan/ReversiAI

19
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
19
10