Hatena::ブログ(Diary)

プログラミング練習帳&備忘録

2010-04-26

[][] リバーシプログラム - bitboard による合法手生成 07:59

前回C#3.0な機能を何とか使ってみたいという思いでプログラム書いてましたが、結局実行速度の問題(ラムダ式が、というよりビットボードからインデックスを求めて合法手配列にアクセスするという手法が無駄だったwビットボード使うならビット演算だけで合法手求めろって話ですね。)なため貼りつけた部分のコードは全部消しました。

というわけで現在リバーシプログラムの実装状況を挙げると、

  • コンソールへの盤面印字
  • 着手可能点の生成
  • 盤面更新処理

です。ここまで来ると次はいよいよ探索部分ですね。

全合法手はこんな感じで生成出来ます。ビットボードは64bitのC#だとulong型で、各ビットに石があれば1のビットが立っていて、白黒それぞれ別に持っています。orをとるとどっちかの石の置かれてるビットボードになり、そのnotをとると空白のマスを表します。以下のソースの詳細はコメント書いたので省略。以下を全方向に対して行うと、全合法手が生成出来ます。

            var black = BlackBB.p;
            var white = WhiteBB.p;
            //左側方向の処理
            var w = white & 0x7e7e7e7e7e7e7e7e; //端の1列が0、それ以外は1な盤面
            var t = w & (black << 1);           //黒石の左隣にある白石を調べる
            t |= w & (t << 1);                  //その隣の
            t |= w & (t << 1);                  //隣の・・・
            t |= w & (t << 1);
            t |= w & (t << 1);
            t |= w & (t << 1);          //一度にひっくり返せる石は6つまで
            var blank = ~(black | white);       // 空白の箇所
            var mobility = blank & (t << 1);    //着手出来るのは空白のマスだけ

            //右方向の処理
            w = white & 0x7e7e7e7e7e7e7e7e;     //以下同様だけど
            t = w & (black >> 1);               //黒石の右側を調べる
            t |= w & (t >> 1);
            t |= w & (t >> 1);
            t |= w & (t >> 1);
            t |= w & (t >> 1);
            t |= w & (t >> 1);
            blank = ~(black | white);
            mobility |= blank & (t >> 1);    

結果として、mobilityに石がおける地点のビットに1が立っている値が得られます。

次に盤面の更新の処理。は、また次に書きます。

トラックバック - http://d.hatena.ne.jp/ainame/20100426/1272236395