石が取れるかどうか (ビット演算)

囲碁

囲碁をビット演算考えてみる
まずは石を取る為の式が必要なので考えてみました。


■ データの持ち方とビット演算で考えるのは何故か
19路盤では置ける場所が 19*19=361 なので361桁の2進数を用意すればよい。
361桁のデータ型はないので、ビット演算が出来る演算子オーバーロード付きのクラスを用意すれば理論的にはどうとでもできるはずです。

容量もCPUがARMなら 4byte の int を12個用意すればよく、とても軽い！
通常の囲碁ソフトのアルゴリズムだと再起関数やらでスタックオーバーフローが心配だし、計算量が多すぎるとDSだともっさりしそう
ということでビット演算で出来ないものかと考えてます。


■ 石が取られるかのチェック
bs 黒石
ws 白石

5路盤だとすると以下のようになる？

① h = (bs | ws)
② hh = (h >> 5 & h) || (h << 5 &h)
③ hw = (h + 1 & h) || (h - 1 & h)
④ h = (hh & hw) & bs

1. 黒と白で隣接するものからあたり判定するため一度合わせる。
2. 縦軸のハッシュを取得 隣接する石があれば1を立てれば良い
3. 横軸のハッシュを取得 隣接する石があれば1を立てれば良い
4. 縦軸と横軸のハッシュをマスクすれば、取れる石だけが1立ち、どの色が取れるかは打った石の色と逆の色とをマスクすれば良さそう
　黒が手番なら白盤のハッシュとANDすれば、白石だけの取れる配置が分かるはず


上記はあくまで考えただけのもので、これだけでは多分バグがあると思われます。
間を空いている石が取れる可能性も出てくるので、というかそうなるはず。
その問題点をどうしたものか・・・


■ 備考
コウの判定は参考サイトを見つけて解決しました。
"2手前と同じなら" というのがとても簡単で計算量がほぼありません。
ビット演算ならではのマスクするだけで解決です。
判定として使うなら "数字が立っていれば" という考え方で良いので、XORした結果が0と等しければ判定できそうです。
後は本当にコウかどうかをは、取った石の数が1つで、2手前も1つなら　というのでいけるのかな？

if(([2手前の石の並び] xor [現在打った後の石の並び]) == 0)
{
    if ([現在打った後の取った石の数] == 1
        && [2手前の取った石の数] == [現在打った後の取った石の数])
    {
        // コウの処理
    }
}

■ 参考サイト
囲碁研究