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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

3回答

3966閲覧

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

_Victorique__

総合スコア1392

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2017/05/24 02:05

編集2017/05/24 02:26

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

###該当のソースコード

C++

1//銀が33にいて、自分の駒が22と42にいる場合 2int enemyboard=65600,ginmove=330048; 3int 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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

coco_bauer

2017/05/24 02:18

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

2017/05/24 02:22

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

2017/05/24 02:27

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

2017/05/24 02:35

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

回答3

0

ベストアンサー

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

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

投稿2017/05/24 02:44

Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2017/05/24 02:52

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

2017/05/24 04:52

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

0

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

投稿2017/05/24 02:20

szk.

総合スコア1400

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

_Victorique__

2017/05/24 02:25

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

2017/05/24 02:43

`手に変換する方法`とは、具体的にどのようなことでしょうか。 駒が3マスのいずれかに移動できることが手だと思うのですが、 3マスのどこに移動したらいいかを判断するには、 言わるれ通り各手をループで回すしかないかと思います。 高速化というのであれば、非同期にするとか方法はありますが、、、
szk.

2017/05/24 02:55

あ~なんか検討違いな回答しちゃいましたね; おそらくですが、 人がイメージしやすい配列や座標に変換すると遅くなります。 すべてビットで計算して、最後に座標化する方法を考えると 早くなるかと思います。
_Victorique__

2017/05/24 04:51

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

0

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

01010

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

C

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

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

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

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

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

投稿2017/05/24 03:12

KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

_Victorique__

2017/05/24 04:50

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問