質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.91%

将棋プログラムbitboardによる高速化について

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,826

_Victorique__

score 1258

前提・実現したいこと

5×5の将棋プログラムでbitboardの実装をしようとしているのですが、イマイチ速くなるように書けません。というのも、例えば銀を動かす手を調べるとして、自分の駒のbitboardとその地点の銀の動きの&を取れば動かせる場所を1で示せますが、それをどうやって取り出せば高速になるのかわかりません。

該当のソースコード

//銀が33にいて、自分の駒が22と42にいる場合
int enemyboard=65600,ginmove=330048;
int move = enemyboard ^ ginmove;

試したこと

ー銀ー ー自駒ー ー動きー
00000   00000     00000
01110   01010     00100
00000   00000     00000
01010   00000     01010
00000   00000     00000

動きのbitは得られますが実際に手にするのにfor文を回すと計算量が増え、bitを使う意味がない。33に居る時の銀の動きを予め配列にしておけば計算量は少ししか変わらないですよね?
実際にfor文で確かめるしか無いのでしょうか?

補足情報(言語/FW/ツール等のバージョンなど)

windows VisualStudio2015
C++14

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • coco_bauer

    2017/05/24 11:18

    コードを示して下さい。そうでないと質問の意図が判りかねます。

    キャンセル

  • _Victorique__

    2017/05/24 11:22

    コードとはfor文でbitの立っている場所を探すコードのことでしょうか?

    キャンセル

  • Zuishin

    2017/05/24 11:27

    ビットの立っている場所の座標を求めるという問題ですか?

    キャンセル

  • _Victorique__

    2017/05/24 11:35

    そうです!5×5の将棋なので25マス1一から5五までです。単純にforループで求めるしか方法は無いのでしょうか?bitが何乗の部分に立っているかを把握できれば座標に変換できます。

    キャンセル

回答 3

checkベストアンサー

+5

C# ですが移植は容易だと思います。
[C#] 一番右端の立っているビット位置を求める「ものすごい」コード

一番右端のビット位置を求め、それを 0 にすることを繰り返せばすべてのビット位置が求められると思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/24 11:52

    言うまでもないと思いますが、x & -x で一番右端の 1 だけ残した数が得られているので、それと元の数との xor を取れば一番右端の 1 だけ 0 にした数になります。

    キャンセル

  • 2017/05/24 13:52

    こんなテクニックがあったんですね><ありがとうございました!

    キャンセル

+2

and&じゃなくてxor^で取ればいいんじゃないですか。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/24 11:25

    すみません間違えました。
    xorで取った後にbitの立っている場所を探して手に変換するにはfor文を回すしかないのでしょうか?という質問です。上記の例なら3つbitが立っていますがそれを手に変換する際の方法ですね。

    キャンセル

  • 2017/05/24 11:43

    `手に変換する方法`とは、具体的にどのようなことでしょうか。

    駒が3マスのいずれかに移動できることが手だと思うのですが、
    3マスのどこに移動したらいいかを判断するには、
    言わるれ通り各手をループで回すしかないかと思います。

    高速化というのであれば、非同期にするとか方法はありますが、、、

    キャンセル

  • 2017/05/24 11:55

    あ~なんか検討違いな回答しちゃいましたね;

    おそらくですが、
    人がイメージしやすい配列や座標に変換すると遅くなります。
    すべてビットで計算して、最後に座標化する方法を考えると
    早くなるかと思います。

    キャンセル

  • 2017/05/24 13:51

    確かにそうですね!位置の取得から座標変換を保留して探索するようなプログラムにしようと思います!ありがとうございました!

    キャンセル

+1

bitパターンをそのまま配列の指標として「得たい情報を一発で取り出す」といったことをやることがあります。例えば

01010

というビットパターンから1と3というONビットの場所を取り出したいなら

int bitsToIndices[][] = {
 { { -1 } },       //index=00000の行
 { { 0, -1 } },    //index=00001の行
 ...
 { { 1, 3, -1 } }, //index=01010の行
 ...
};
// この例ではC++であることを意識しておらずCとして書いてます。
// C++ならもっと分かりやすい構造もあり得ると思います。
// 要素の最後を示す-1なんて不格好なことをせずに・・・

こういうものを用意しておいて1と3を取り出すわけです。同様の応用は色々考えられます。例えば「そのビットパターンで一番小さなビット位置を求めるとか、ビットの数を求める」とか・・・
こういうのは演算した方がわかりやすいですが究極の速度を得たいときには「アリ」だと思います。

もちろん、とりだした1,3についてはループしなければなりませんが、それでも0~4までを無条件にループするよりは効率がよくなるのではないかと考えるわけです。

ただしおわかりと思いますがこれは「小さなビット数」の場合にのみ使えるテクニックです。5x5の25bitに対してやろうとすると巨大な配列領域が必要になっちゃいますね。そういうときは10bit前後で分割して配列のサイズが大きくなりすぎない程度に収めるなどの工夫をします。また要素をintにしてますが0~4までの値なら3bitで事足りるので配列ではなくbitを詰めた整数型にするといったアイデアもあるかも知れません。例えば5要素分だとすると15bitで済むのでshortに詰め込めるなぁとか・・・

ただ構造に凝りすぎると却って単純ループの方が早くなりかねないのでバランスが肝心と思います。こうしたことはshiftなどの演算命令の実行クロック数とかメモリーの間接参照はどの程度の性能なのかキャッシュの量はどのくらい?というようなプロセッサーの特徴までも意識する必要もあるでしょう。膨大な計算量のプログラムを力技で解かなければならないとき、その辺りまで意識してプログラミングしているのだろうと推測しますが、現代のプロセッサーの動きは複雑なので難しそうですね。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/24 13:50

    分割するとその分計算量も手間もかかるので32bitでやろうと思います。ありがとうございました!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.91%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る