将棋クラスタ向けTwitterアプリ kiftwi

kiftwi -キフツイ- http://kiftwi.dip.jp/

というのを3月頃から密かに作ってました。Rails、というかWebアプリ系のサービスを一から開発したの初めてなのでちょっとアレですがそれなりに形にはなっているかなと思います。

内容は、将棋版Twitpic的な棋譜投稿支援ツール。詳細な解説はだるいので後で暇なときにします。
Railsのアプリケーションとして恐らく特に凝ったことはしてないですし。盤面を再生する部分は、以下のサイトのFlashアプリケーションを設置して、DBに収められた棋譜をHTMLのコメントに埋め込むだけという簡単な仕組みで動いてます。

KiFLA - NHK杯の将棋棋譜囲碁棋譜FLASHにて掲載 - http://homepage3.nifty.com/amihot/

リバーシプログラム - bitboard による合法手生成

前回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が立っている値が得られます。

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

ラムダ式活用例

リバーシプログラムのために試行錯誤。全体の進捗についてはまた記事書きます。

現在ビットボードの各辺から合法手配列へのアクセス用のインデックスを生成する部分を記述中。ためしにラムダ式を使ってみた部分があったので記念にコピペしときます。コメント少ないのはご愛嬌ということで。

簡単に解説するとCreateAllIndexでCreateIndexを呼び出すときに、ビットボードからのビットの切り出し方をラムダ式で渡してます。すると、回転ビットボードの時とかでちょっとビットの切り出し方が違ってる時でも同じ関数で対応できると言うわけです。(通常のビットボードからは上から8bitずつ単純に切り出すだけ)

		public uint CreateIndex(Bitboard b, Bitboard w, Func<Bitboard, int> GetBitLine)
		{
			var black = GetBitLine(b);
			var white = GetBitLine(w);

			uint a = 0;
			for (int i = 0; i < Board.BoardSize; i++)
			{
				a += ((black >> i) & 1U) * Pow3[i];
				a += ((white >> i) & 1U) * 2 * Pow3[i];
			}
			
			return a;
		}

		public void CreateAllIndex(List<Bitboard> b, List<Bitboard> w)
		{
			for (int i = 0; i < Board.BoardSize; i++)
			{
                //rank, fileはチェス用語?w
				Rank[i] = CreateIndex(b[Board.Occupied], w[Board.Occupied], (bb) =>
				{
					return (int)((bb.p >> i * 8) & 0xFF);
				});
				File[i] = CreateIndex(b[Board.RL90], w[Board.RL90], (bb) =>
				{
					return (int)((bb.p >> i * 8) & 0xFF);
				});
			}
                        //今後回転ビットボードの処理も記述・・・

		}

メリットとしては

  • 無駄にメソッドが増えずに済む=>コード全体が短くなる

デメリットは

  • 実行速度? => 調べてないので分からないw
  • 重複する処理がある => 重複するならデリゲートで定義しておけばおk

こんな感じか?

参考図書

[完全版] 究極のC#プログラミング ~新スタイルによる実践的コーディング

[完全版] 究極のC#プログラミング ~新スタイルによる実践的コーディング

これ買ってしまいました。C#3.0は既存の知識だけじゃちょっと理解できんかった。

企画変更 → リバーシのプログラム作成

N-Queen作ろうとしてちょこちょこ書いてましたが、新学期の生活リズムになれずそんなに作業進んでなかったorz
んでゼミの方でリバーシのプログラムを書くことになりそうなので、どうせだからNQueen放り投げてC#リバーシ作ってみます。
実行速度ェ・・・