CellBEによるオセロ解法プログラム

o-cell-o

N-queen問題を解いてみる事で、SPUを128bitの論理回路として用いる事で、ある程度の速度のプログラムが書ける事は分かった。
次にどのような目標を立てるかということだが、以前から少し興味のあった話題として、オセロのプログラムを作成してみたい。
最初に言ったように途方もない目標としては囲碁のプログラムがあるので、まずは単純なものからやってどのような問題があるかを洗い出しておく必要がある。とはいえこういった積極的な意図だけではなくて、以前からアルゴリズムだけは分かっている気になっていたαβカットを自分で実装してみようという興味本位や、ボードゲームの探索プログラムではあまり並列処理の効果がでないと言われているので、私がやればもうちょっとましなことができるのではないか？という不遜な考えがあるからでもある。そして何より重要だったのは、オセロの盤の大きさは8x8=64で、二色の石をそれぞれ64bitで表すと、SPUのレジスタのサイズである128bitにちょうど合うのでうまくはまるだろうという期待ができたからである。

いくつか簡単にオセロプログラムのサイトを読んでみたが、結局盤面をどれだけ高速に読めるかで勝負が決まってきているというのが私の印象だ。
プログラムは見ていないが、Zebraというプログラムがビット演算で次に石が置ける位置を計算する事で高速に処理しているらしいというので、これをSPU用に自分で実装してみる。

今、白の配置を全て格納した変数をX, 黒の配置を格納した変数をYとして、連結した128it変数を(X||Y)と表す。
このとき、ある変換Rを定義すると、Rが示す方向へ他の石をひっくり返す事ができるかをA, その可能性があるかをDで示すと、以下の操作で石を置きうる全ての位置をAに格納することができる。またEは現在石が置かれていない空白のマスである。



1. D = E = ~( (X||Y) | (Y||X) ) # 現在石の置かれていない場所をEとDに格納

2. (X||Y) = R( (X||Y) )         # 一マス分動かす

3. A = A | ( (Y||X) & (X||Y) )  # 一つ前と違う色の石が置かれている場所は置く事ができる

4. D = D & (X||Y)               # 同じ色が続いている場合のみ置く可能性が残る

5. if not end then goto 2       # 7回繰り返す

6. A = A & E                    # 最初に空白の場所のみを提示

これをSPUのコードで表すと以下のようになる。このコードでは下方向にひっくり返す事ができるかを調べている。



    const static vector unsigned int mask 

      = (vector unsigned int){ 0xffffffff, 0xffffff00, 0xffffffff, 0xffffff00 };

  A  = (vector unsigned int){ 0, 0, 0, 0 };

  E  = spu_orc( board, spu_rlqwbyte( XY, 8 ) );

  XY = spu_and( mask, spu_rlqwbyte( XY, 1 ) );

  D  = XY;

  for ( i = 0; i < 6; i++ ) {

      XY = spu_and( mask, spu_rlqwbyte( XY, 1 ) );

      A  = spu_or( A, spu_and( XY, spu_rlqwbyte( D, 8 ) ) );

      D  = spu_and( D, XY );

  }

  A = spu_and( A, E );

ここで得られるAは黒白両方が次に置ける場所を表現している。