最近「はせらリバーシ」色々いじっていて、少し強くなったような気がするのと、ビットボードを実装して、高速化しました。
詰めオセロもビットボード化しました。15個空きのサンプルを貼ります（1手打つとCOMが14個空きを読み切ります）
白番。勝って下さい。
ビットボードは、以下のサイトのものをほぼそのまま使わせていただきました（感謝）局面にもよりますが、従来より2～5倍くらい速くなったと思います。
一旦ほぼそのまま実装して動作を確認した後、少し改良しました。
どの位置に打っても8方向分のビット演算をするのは無駄があるので、例えばa1に打つときは右、右下、下方向のみのビット演算を行うようにしました。
// 石を返す関数のテーブル、打つ位置によって呼ぶ関数を変える flipfunc = [ flip0a, flip0a, flip0b, flip0b, flip0b, flip0b, flip0c, flip0c, flip0a, flip0a, flip0b, flip0b, flip0b, flip0b, flip0c, flip0c, flip0d, flip0d, flip0 , flip0 , flip0 , flip0 , flip0e, flip0e, flip0d, flip0d, flip0 , flip0 , flip0 , flip0 , flip0e, flip0e, flip1d, flip1d, flip1 , flip1 , flip1 , flip1 , flip1e, flip1e, flip1d, flip1d, flip1 , flip1 , flip1 , flip1 , flip1e, flip1e, flip1a, flip1a, flip1b, flip1b, flip1b, flip1b, flip1c, flip1c, flip1a, flip1a, flip1b, flip1b, flip1b, flip1b, flip1c, flip1c ];
使うときは、flip0,flip1を呼ぶ代わりに、flipfunc[pos]を呼ぶという方法です。
posは盤面上の位置で、0～63で、例えばA1ならposは0で、flipfunc[0]（つまりflip0a）を呼びます。
呼び元はこんな感じです。
if( turn == 'X' ){
if( pos < 32 ){
[f0, f1] = flipfunc[pos](board[1], board[0], board[3], board[2], 1<<pos);
}
else{
[f0, f1] = flipfunc[pos](board[1], board[0], board[3], board[2], 1<<(pos-32));
}
}
else{
if( pos < 32 ){
[f0, f1] = flipfunc[pos](board[3], board[2], board[1], board[0], 1<<pos);
}
else{
[f0, f1] = flipfunc[pos](board[3], board[2], board[1], board[0], 1<<(pos-32));
}
}
flip0aは、flip0から左、左上、上以外を削除したものです。
function flip0a(p1, p0, o1, o0, sq_bit) {
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;
return[f0, f1];
}
a1の場合は右、右下、下のみにするべきですが、このソースコードに書いてある日本語はでは、原作者様のイメージで上下逆なのです。
上下という概念は人間がどう認識するかの話なので、別に右下をA1にしても良いというか、最下位ビットをA1と考えても、H8と考えても良い訳です。私は原作者様のイメージのまま、最下位ビットをA1にしたので、普段使ってるA1～H8とは180度回転した座標になっています。
つまり、ビッグエンディアンとリトルエンディアンみたいな話…というか、そのものかも知れません。
こんな感じで、12種類の関数を呼び分けています。効果は…微妙でしたが、確実に速くはなりました。なぜ微妙かというと、もっと遅い部分があるからだと思います。
「打てる場所の一覧」を作る関数があるのですが、
/*打てる場所の一覧を作る*/
function makemoveables(board, turn){
var moveables = new Array();
if( turn == 'X' ){
[mob0, mob1] = mobility(board[0], board[1], board[2], board[3]);
}
else{
[mob0, mob1] = mobility(board[2], board[3], board[0], board[1]);
}
pos = 0;
length = 0;
while( mob0 != 0 ){
if( (mob0 & 1) == 1 ){
moveables[length] = pos;
length++;
}
mob0 >>>= 1;
pos++;
}
pos = 32;
while( mob1 != 0 ){
if( (mob1 & 1) == 1 ){
moveables[length] = pos;
length++;
}
mob1 >>>= 1;
pos++;
}
return( moveables );
}
moveablesという配列に、打てる場所（0～63の数字）の一覧を格納します。最初はfor分で必ず64回（32回×2）ループするように作ってしまったのですが、ループ回数減らせると気付いてこうしました（それで30%くらい速くなりました）
というか、打てる場所を数値に変換しないといけないか、というところに無駄があるような気がして考えたのですが、moveablesにビットマップを分解したものを格納するようにしてもループはするので、ほとんど変わらないか…
尚、ビットボードの話自体は、Booby Reversiの作者の奥原氏のページなどが詳しいです。
