Entries

【アイデアメモ】王手をかけれる駒の有無を高速に判定する方法

　昨日の記事に引き続き王手生成の高速化案。

　ここ数日はビット演算を駆使して高速化する方法を考えていたので、なんとなく上手いやり方が分かってきた。この調子でどんどんアイデアが出ればいいのだが。


【既存方式の問題点】

  • あるマスに利きがある全ての駒に関して、個別に駒情報テーブル（※）から情報を引き出して王手可否を判定する必要があり、処理時間が長くなる。



【概要】

  • 先手・後手それぞれに対して、特定方向に移動可能な駒のマスクを作成しておく。

    ex.
    上に移動可能な先手の駒が2番、3番、4番ならマスクは00001110（上位ビットは省略）。

  • あるマスから見て敵玉がどの方向かを判断し、その方向に移動可能な駒のマスクとそのマスに利いている駒の情報を取り出す。

    ex.
    後手玉の一マス下に利いている先手の駒が1番、5番、7番なら、その位置の利き情報は01010001。マスクは上記のもの。

  • マスクと利き情報のビットANDを取り、結果が0なら王手不可能・それ以外なら王手可能。

    ex.
    マスクと利き情報のビットANDを取ると00000000になり、この場所に移動して王手をかけれる駒が無い事が分かる。

  • 王手可能と分かったら上記計算結果の各ビットを見て王手をかける手のリストを生成する。

  • 持ち駒に関しては、歩〜飛車の有無を表すマスク（ex. 桂馬と銀がある場合なら0011000）と特定方向に移動可能な駒のマスク（ex. 上に移動出来るのは歩・銀・金なので1001100。）からビットANDで判断する。
    なお、二歩を回避する為に、持ち駒有無マスクを位置に応じて適当に加工してから使用する。行き所なき駒の禁は考慮する必要無し。

  • 打ち歩詰めに関しては詰め将棋ルーチン側で対応する事とし、王手生成ルーチンでは一切考慮しない。



【利点】

  • あるマスで王手をかけれるか否かを高速に判定可能。



【欠点】

  • 成る時・駒を取る時・駒を打つ時にマスクを再構成する必要があるので、指し将棋の速度が低下する可能性がある。



【事前準備】

  • 特に無し。



【事後処理】

  • 本案の実装による指し将棋の速度低下率を計測。5％以下の低下ならば問題無しとする。



※駒情報テーブル：駒番号と駒の種類・所有者等を保存するテーブル




この記事に対してトラックバックを送信する（FC2ブログユーザー）
http://streakeagle.blog15.fc2.com/tb.php/681-15cd40eb

0件のトラックバック

0件のコメント

コメントの投稿

投稿フォーム
投稿した内容は管理者にだけ閲覧出来ます

Appendix

QRコード

http://streakeagle.blog15.fc2.com/?m

プロフィール

アベント

  • @author アベント
  • @mail murakumo_xp@yahoo.co.jp
  • アセンブラなんて分からないニュージェネレーションのJAVAプログラマ。
    でもJAVA実習の単位は落とした経験あり。二回目もC判定。＜ だめジャン
    でもJAVAが好き。
  • 2ch プログラム板にも出没。
    • おまいら最強の将棋プログラムしてみろよ
    • すれ立てるまでもない質問はここで
    • Java質問・相談スレッド
    • クラス名・変数名に迷ったら書き込むスレ

つっこみをいれる

メッセージを送る(メアド不要)

カテゴリー

月別アーカイブ

最近の記事

最近のコメント

最近のトラックバック

RSSフィード

リンク集

Shangri-La
リアル広島人（ぉ

小宮日記
コンピュータ将棋を作成されている方です

ぴんきーのよこちん
18禁サイトにあらず!!


FirefoxやPCの便利な使い方等が書かれています。


音楽の自主作成をされているWanCoさん

ば〜な〜あぁ〜〜
管理人サイト

BlogPet


← | RAN | →

アクセスカウンタ

トータルアクセス

ユニークアクセス

ブログランキング参加中

FC２ブログランキング
気が向いたらクリックお願いします。

googleページランク

Powered By The-Searchstreakeagle.blog15.fc2.comのPageRankを表示しています。

x-w.jp