ぷよ碁 開発ブログ
オセロやチェスはよく高速化のためにビットボードで実装されることがありますが、囲碁のビットボードは良さそうなものが見つからなかったので自前で実装してみました。
ビットボードの表現
５路盤であれば、黒石と白石の位置を32bitの変数に格納して表現できる。
盤面の表現
let black: u32 = 0b00000_00010_00011_00000_00000;
let white: u32 = 0b00010_00101_00100_00011_00000;
let bw = black | white;黒 白 白+黒 盤面
00000 00010 00010 ---○-
00010 00101 00111 --○●○
00011 00100 00111 --○●●
00000 00111 00111 --○○○
00000 00010 00010 ---○-盤面端の表現
let RIGHT_EGDE = 0b00001_00001_00001_00001_00001;
let LEFT_EDGE = 0b10000_10000_10000_10000_10000;
let TOP_EDGE = 0b11111_00000_00000_00000_00000;
let BOTTOM_EDGE = 0b00000_00000_00000_00000_11111;石を打つ
盤面に新しい石を打つ場合は単純にorでビットを立てます
例えば、5-5に石を打つ場合
black = black | 1;3-4に石を打つ場合
black = black | (1 << 11); // 5*(5-3) + (5-4) = 11
石を取り除く
死んだ石をビット反転してandを取ります
black = black & !black_death;死に石を調べる
/**
* 死んだ石を返す
* stone 死活判定対象の石
* opp_stone 相手の石
*/
fn death_stones(stone: u32, opp_stone: u32) -> u32{
let n = 5; // 盤面サイズ
let bw = stone | opp_stone;
let st = stone;
// 上下左右囲まれてる石を求める
let surr = bw & (
(bw >> 1 | LEFT_EDGE) &
(bw << 1 | RIGHT_EGDE) &
(bw >> n | TOP_EDGE) &
(bw << n | BOTTOM_EDGE));
let mut dp = st & surr;
let mut death = bw;
// 死に石候補が確定するまでチェック
while death != dp {
death = dp;
let alive = dp ^ st;
dp = dp & !(
dp & (alive >> 1 & !LEFT_EDGE) |
dp & (alive << 1 & !RIGHT_EGDE) |
dp & (alive >> n & !TOP_EDGE) |
dp & (alive << n & !BOTTOM_EDGE)
);
}
death
}変数がわかりにくいので補足
st 自分の石
bw 自分の相手の石を合わせたもの
surr 囲まれている石(色は考慮しない)
dp 死に石候補
alive 生きが確定した石
death 死んだ石
さっきの盤面の死に石をチェック
盤面 st bw surr dp alive death
---○- 00000 00010 00000 00000 00000 00000
--○●○ 00010 00111 00010 00010 00000 00010
--○●● 00011 00111 00011 00011 00000 00011
--○○○ 00000 00111 00010 00000 00000 00000
---○- 00000 00010 00000 00000 00000 00000ちゃんと黒石が死に石判定されています。
少し石を減らして、ぎりぎり生きてる盤面もチェック
盤面 st bw surr dp alive dp alive dp alive death
---○- 00000 00010 00000 00000 00000 00000 00000 00000 00000 00000
---●○ 00010 00111 00000 00000 00010 00000 00010 00000 00010 00000
--○●● 00011 00111 00011 00011 00000 00001 00010 00000 00011 00000
--○○○ 00000 00111 00010 00000 00000 00000 00000 00000 00000 00000
---○- 00000 00010 00000 00000 00000 00000 00000 00000 00000 00000すると今度はちゃんと黒石は死んでない判定になりました。
aliveの変数を追いかけるとわかりやすいです。最初に4-2地点の黒石が囲まれてないのを発見してそこから順に繋がっている黒石も生き石判定を伝播していっています。
動きとしては、石のつながりを再帰で算出する流れに似ていますが、ビットボードの場合は一か所だけのチェックではなく盤面全体の石の生き死に判定を一発でできるのがメリットです。
合法手を調べる
fn valid_moves(st: u32, op: u32) -> u32{
let n = 5; // 盤面サイズ
let bw = st | op;
let kuten = !bw & 0b11111_11111_11111_11111_11111;
// 空きマスのうち、周りを同じ色で囲まれている場所を探す
let st_surround_kuten = kuten & (
(st >> 1 | LEFT_EDGE) &
(st << 1 | RIGHT_EDGE) &
(st >> s | TOP_EDGE) &
(st << s | BOTTOM_EDGE));
let op_surround_kuten = kuten & (
(op >> 1 | LEFT_EDGE) &
(op << 1 | RIGHT_EDGE) &
(op >> s | TOP_EDGE) &
(op << s | BOTTOM_EDGE));
let surround_kuten = st_surround_kuten | op_surround_kuten;
// 自殺手を禁止
let mut st_try = op_surround_kuten;
let mut dstone = 0;
while st_try != 0 {
// 周りを囲まれた空きマスに石を試しに打ってみる
let rbit = st_try & ((!st_try) + 1);
st_try = st_try ^ rbit; // 右端のビットを消す
// 自分の色の石を試す
let new_try = st | rbit;
let ds = death_stones(op, new_try);
if ST_HISTORY.contains(&new_try) && OP_HISTORY.contains(&(op ^ ds)) {
// 過去の履歴に同じ石の配置があればコウ確定
continue;
}
dstone = dstone | ds;
}
let mut op_try = st_surround_kuten;
while op_try != 0 {
// 周りを囲まれた空きマスに石を試しに打ってみる
let rbit = op_try & ((!op_try) + 1);
op_try = op_try ^ rbit; // 右端のビットを消す
// 相手の色の石を試す
let new_try = op | rbit;
let ds = death_stones(st, new_try);
dstone = dstone | ds;
}
// 隣り合う石が１つでも死んだらそれは合法手
let dbeside = surround_kuten & (
(dstone >> 1 & !LEFT_EDGE) |
(dstone << 1 & !RIGHT_EDGE) |
(dstone >> s & !BOTTOM_EDGE) |
(dstone << s & !TOP_EDGE));
// 合法手 = (空きマス かつ 周りが囲まれてない) もしくは 隣り合う石が１つでも死んだ時
let valids = (kuten & !surround_kuten) | dbeside;
valids
}STEP1 空きマスの絞り込み
まずは石が置いてない場所が合法手の可能性があるので、空きマスを探します。
空きマスは3パターンに分けられる
- 隣りあうマスにも空きがある
- 隣り合うマスに１つも空きがなく、相手の石に囲まれている
- 隣り合うマスに１つも空きがなく、自分の石に囲まれている
1の場合は、無条件で合法手になります。
2, 3の場合は、合法かどうかまだわからないのでSTEP2に進みます
STEP2 試しに打ってみる
囲まれたマスが合法か判定するために試しにその場所に自分の石を打ってみてどうなるか見ます。
周りの石が死んだ → 合法
自分が死んだ → 違法
過去の盤面と同じになった → 違法(コウ)
STEP3 最終判定
STEP1と2で判定した結果を合わせたものが最終的な合法手の場所になります。
合法手 = (STEP1で1のもの) もしくは STEP2で合法判定されたもの
まとめ
ビット演算はカオスになるので未来の自分に向けて解説を残そうと思いましたが、細かい解説までは無理だったのでせめてヒントになりそうな部分だけまとめました。
もっといい手法をご存じの方がいましたら、ぜひTwitterで教えてください。