関連スレッド
他のスレで関連する話題が出たときに抜粋してみてはいかがでしょうか？
裏返しの処理
873 名前：デフォルトの名無しさん[] 投稿日：2006/08/26(土) 22:28:57
オセロの盤面を白黒２つの64ビット整数で表して（bitboard）、
黒石の打てる箇所をビット演算で求めたいのですが、どうしたらいいですか？
874 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/26(土) 22:35:42
白も黒もビットが立っている事はありえないなら空いてる場所はxorで0のビット
ルールに則って打てる場所なら㍉
875 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/26(土) 23:17:41
http://www.radagast.se/othello/bitmob.c
↑にZebraのソースコードが公開されているのですが、何がなにやらよくわりません
876 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 09:02:13
黒石を打って、右方向に白石を1個だけ返せるのは、空白黒 というパターンなので、
黒石のbitboardを black_board, 白石のを white_board とすれば、以下のようになる
blank = ~(black_board | white_board); // 空白の箇所
t = (blank >> 1) & white_board & 0x7f7f7f7f7f7f7f7f; // 空白 のパターン
t = (t >> 1) & black_board & 0x7f7f7f7f7f7f7f7f; // 空白黒 のパターン
mobility = t << 2; // 右方向に1個返せる箇所
これであってる？
877 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 09:19:53
右方向に打てる場所のビットを探すのであれば、右の黒石からスタートした方が、
最後のシフトが不要になる。
t = (black_board << 1) & white_board & 0xfefefefefefefefe; // 白黒 のパターン
blank = ~(black_board | white_board); // 空白の箇所
mobility = blank & (t << 1) & 0xfefefefefefefefe; // 右方向に1個返せる箇所
878 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 09:31:43
コードを見やすくするために左移動を
inline uint64 move_left(b) { return (b<<1)&0xfefefefefefefefe; }
と定義しておく。
1方向に返る石の数は最大6個なので、右方向の処理は以下のようになる
t1 = white & move_left(black); // 白黒 のパターン
t2 = white & move_left(t1); // 白白黒 のパターン
t3 = white & move_left(t2); // 白白白黒 のパターン
t4 = white & move_left(t3); // 白白白白黒 のパターン
t5 = white & move_left(t4); // 白白白白白黒 のパターン
t6 = white & move_left(t5); // 白白白白白白黒 のパターン
blank = ~(black | white); // 空白の箇所
mobility = blank & move_left(t1 | t2 | t3 | t4 | t5 | t6); // 右方向に返せる箇所
あとはこれを残りの7方向についてやればおけ？
879 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 11:25:28
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);
もうちょっとすっきりしたかな？
合ってる？
880 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 13:03:20
すばらしい>>879
>>878 と比べると
・ 論理積演算が1回で済んでいる
・ 使用する変数の数が減っているので、アセンブラにするときに都合がよい
・ 0x7e...7e と 論理積をとっているので、逆方向の処理についてもこの結果が使用できる
というアドバンテージがある
念のために、8ビットの全パターンについてプログラムを組んで動作を確認してみたところ、
878 と 879 は同じ結果を返した。
なので、879 は合ってるようだ
881 名前：デフォルトの名無しさん[] 投稿日：2006/08/27(日) 13:16:49
着手可能箇所のリストアップはできたので、今度は指定場所に黒石をおいたときに、
白石を反転させて、盤面を更新したい。
どう書いたらいい？
打つ場所は、Bitboard で表したときに１が立っているビットの位置（0..63）で指定するものとする。
int pos;
これをbitboradパターンに変換するために Bitboard set_mask[64] という変換テーブルが既に
用意されているものとする
882 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 13:29:45
先読みの処理は、以下のような感じに書ける
Bitboard mobility = getMobility(black, white); // すべての着手可能箇所を取得
while( mobility != 0 ) {
int pos = getFirstOne(mobility); // ビット値が１の一番下の位置を返す
Bitboard rev = getRevBlack(black, white, pos); // pos に黒石を打ったときに反転する白のパターンを取得
Bitboard m = (1<<pos); // 着手位置のビットパターン
black |= m | rev; // 黒石を更新
white ^= reb; // 白石を更新
// なんらかの処理
black ^= m | rev; // 黒石を元に戻す
white ^= reb; // 白石を元に戻す
mobility ^= m;
}
886 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 22:54:15
Bitboard m に黒石を打ったときに、反転する白石のパターンを取得する処理
まずは１方向のみ＆ループを使ったコード：（m に着手可能なのは次善にチェック済みとする）
Bitboard rev = 0;
Bitboard mask = m;
for(;;) {
mask >>= 1;
if( (mask & black) != 0 ) break;
rev |= mask;
}
さあ、ループを無くすことができるか？
887 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 23:00:38
おおっと、その方向に着手可能かどうかは保障されてないので、
>>886 のコードではまずいぞ
888 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/27(日) 23:45:33
着手可能箇所を調べるときに、8方向について計算し、その論理和をとるわけだが、
それぞれの方向の値を保持しておけば、特定の方向に返るかどうかがわかる。
そうであれば、>>886 のコードでも大丈夫だ
889 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/28(月) 12:38:49
>>879 と >>878 が何故同じ結果を返すのかよくわからなかったけど、
シフトと論理和が分配法則をみたし、論理和が重複法則を満たすからなんだね
(x | y) << 1 == (x << 1) | (y << 1) // 分配法則
x | y | y == x | y // 重複法則
937 名前：デフォルトの名無しさん[sage] 投稿日：2006/09/01(金) 21:35:31
回転問題で忘れられているオセロ
g_plus1[pos] にpos (0..63)
の位置から盤の右端までビットを立てたテーブルをあらかじめ作っておけば、
int pos に黒石を置いたとき、右方向に返る白石は以下のようにして取得できると思う
uint64 nwh = ~(white & 0x7e7e7e7e7e7e7e7e);
uint64 rev = 0, m;
if( (m = g_plus1[pos] & nwh & black) != 0 )
rev |= g_plus1[pos] ^ m ^ g_plus1[getLSSetBit(m)];
getLSSetBit(uint64) は一番下位のセットされたビットのビット番号を返す関数
x86 であれば BSF 命令を使用すれば高速に処理できる
こんなんでどうでしょうか？
942 名前：デフォルトの名無しさん[] 投稿日：2006/09/02(土) 12:56:52
オセロの話
オセロでは、絶対に返されることのない石を「確定石」といいます。
隅の石は無条件で確定石ですし、辺がすべて埋まっているときの辺の石はすべて確定石です。
確定石の個数と有利さには大きな相関があります。
しかし、確定石を計算するのは大きなコストがかかるので、オセロプログラムでは通常「準確定石」を計算します。
準確定石とは一回で返されることの無い石のことです。
uint64 rev = 0;
uint64 mobility = getMobility(black, white);
for(uint64 m = すべての可能な着手について)
rev |= getRevPat(black, white, m);
uint64 semiFixed = white ^ rev;
とすれば、白の準確定石を計算できますが、時間がかかりそうです。
ビット演算を駆使して準確定石を高速に計算するにはどうしたらいいでしょうか？
盤面回転の処理
890 名前：デフォルトの名無しさん[] 投稿日：2006/08/30(水) 21:27:30
8x8 のビットパターンが32ビットレジスタに入っているとき、
これを高速に90度回転するにはどうしたらいいんですか？
891 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/30(水) 21:28:55
ごめん、32ビットレジスタには8x8は入りきらない
32ビットレジスタ２つ、または64ビットレジスタに入っているものとします
896 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 [sage] 投稿日：2006/08/30(水) 23:23:43
SSEが使えるならpsllq & pmovmskb使うのが一番速そうだけど
とりあえず汎用性のあるのは
uint64 a[256] ;
memset(a, 0, sizeof(a);
for ( int i = 0; i < 256; i++ ) for ( int j = 0; j < 8; j++ ) a[i] += (i & (1 << j)) << (7 * j);
//↑ここまではあらかじめ計算しておく
reg = a[reg & 0xFF] | (a[(reg >> 8) & 0xFF] << 1) | (a[(reg >> 16) & 0xFF] << 2)
| (a[(reg >> 24) & 0xFF] << 3) | (a[(reg >> 32) & 0xFF] << 4) | (a[(reg >> 40) & 0xFF] << 5)
| (a[(reg >> 48) & 0xFF] << 6)| (a[reg >> 56] << 7);
897 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/30(水) 23:23:53
>>890
一応、ハッカーの楽しみを読めば乗っているよ。
typedef unsigned long long ulong;
ulong rotate(ulong x){
x =
x << 1 & 0xAA00AA00AA00AA00ULL |
x >> 1 & 0x0055005500550055ULL |
x >> 8 & 0x00AA00AA00AA00AAULL |
x << 8 & 0x5500550055005500ULL ;
x =
x << 2 & 0xCCCC0000CCCC0000ULL |
x >> 2 & 0x0000333300003333ULL |
x >> 16& 0x0000CCCC0000CCCCULL |
x << 16& 0x3333000033330000ULL ;
x =
x << 4 & 0xF0F0F0F000000000ULL |
x >> 4 & 0x000000000F0F0F0FULL |
x >>32 & 0x00000000F0F0F0F0ULL |
x <<32 & 0x0F0F0F0F00000000ULL ;
return x;
}
901 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/30(水) 23:58:31
>>897
何で、これで回転できるの？
さぱーりわからん
902 名前：897[sage] 投稿日：2006/08/31(木) 00:11:48
>>901
分割統治方をつかってますです。
最初は2*2の回転。
次は4*4の回転。既に4*4の中身の2*2の回転は済んでいるので外側だけの回転。
最後は8*8の回転。既に8*8の中身の4*4の回転は済んでいるので外側だけの回転。
とりあえず、下は4*4だけどこんな感じに回転する。
１２３４
５６７８
ＡＢＣＤ
ＥＦＧＨ
↓2*2の回転
２６４８
１５３７
ＢＦＤＨ
ＡＥＣＧ
↓4*4の回転
４８ＤＨ
３７ＣＧ
２６ＢＦ
１５ＡＥ
903 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 08:12:35
>>897
転置してバイトオーダを入れ替える方が速くないかい？
uint64 rotLeft90(uint64 x)
{
uint64 t = ((x >> 7) ^ x) & 0x00aa00aa00aa00aa;
x = x ^ t ^ (t << 7);
t = ((x >> 14) ^ x) & 0x0000cccc0000cccc;
x = x ^ t ^ (t << 14);
t = ((x >> 28) ^ x) & 0x00000000f0f0f0f0;
x = x ^ t ^ (t << 28);
return byteSwap(x);
}
こっちは (シフト演算*2 + 論理演算*4) * 3 + byteSwap
byteSwap は x86 の bswap を使えば4命令でできる
>>897 は (シフト演算*4 + 論理演算*7) * 3
904 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 08:57:14
実際にプログラムを書いて、回転関数を1億回コールした場合の時間を計測してみた
＠Athlon 64 2.0GHz
>>897 は 5.55秒
>>903 は 3.45秒 （byteSwap() の部分を __asm で記述した）
905 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 09:08:25
>>896 は、そのままだとコンパイルエラーになる
memset の閉じカッコが抜けている
しかも、テストプログラムを実行すると正しい値を返さなかった
906 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 09:18:19
>>896 は正しい値を返さないが、とりあえず実行速度を計ってみた
2.53秒/1億回ループ
デバッグすると遅くなるかもしれんが、今は速いぞ
907 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 09:54:53
テーブルを使う版を書いてみた。テストプログラムで動作確認済み
static uint64 g_rotTable[256];
void setup_rotTable()
{
//ix のビットパターンを左回転させたものを g_rotTable[ix] に格納
for(int ix = 0; ix < 256; ++ix) {
uint64 v = 0;
uint64 vm = 0x0100000000000000;
for(int mask = 1; mask < 0x100; mask <<= 1, vm >>= 8) {
if( (ix & mask) != 0 )
v |= vm;
}
g_rotTable[ix] = v;
}
}
uint64 rotLeft90_table(uint64 x)
{
uint64 t = g_rotTable[x & 0xff];
t |= (g_rotTable[(x >> 8) & 0xff] << 1);
t |= (g_rotTable[(x >> 16) & 0xff] << 2);
t |= (g_rotTable[(x >> 24) & 0xff] << 3);
t |= (g_rotTable[(x >> 32) & 0xff] << 4);
t |= (g_rotTable[(x >> 40) & 0xff] << 5);
t |= (g_rotTable[(x >> 48) & 0xff] << 6);
t |= (g_rotTable[(x >> 56) & 0xff] << 7);
return t;
}
908 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 10:04:13
んで、1億回ループさせて時間を計測すると
5.09秒
>>903 より全然遅い
それぞれの演算数を比べると以下のとおりだ
>>907 : 5.09秒 シフト演算 * 14 + 論理演算 * 15 + 配列によるメモリアクセス * 8
>>897 : 5.55秒 シフト演算 * 12 + 論理演算 * 21
>>903 : 3.45秒 シフト演算 * 6 + 論理演算 * 12 + byteSwap (アセンブラ4命令）
>>907 のコードだとメモリは食うし遅いしで、いいこと無いね
>>896 に書いてある「汎用性のある」とはどういう意味だ？
911 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 10:26:58
>>909 了解
ところで、時間計測は Athlon 64 2.0Ghz WinXP VC6 32ビットモードで計測している
VC6 の __int64 のシフト演算はサブルーチンコールになるので、非常に遅い
Athlon 64 の64ビットモードでコンパイルするとかなり高速になりそうだ
それと >>907 のコードはシフト処理を減らせばもっと高速になるはず
912 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 10:47:20
64ビットシフトをほとんど無くしてみた
uint64 rotLeft90_table(uint64 x)
{
uint32 hi = (uint32)(x >> 32);
uint32 low = (uint32)x;
uint64 t =g_rotTable[(uchar)(hi >> 24)];
t = t + t | g_rotTable[(uchar)(hi >> 16)];
t = t + t | g_rotTable[(uchar)(hi >> 8)];
t = t + t | g_rotTable[(uchar)hi];
t = t + t | g_rotTable[(uchar)(x >> 24)];
t = t + t | g_rotTable[(uchar)(x >> 16)];
t = t + t | g_rotTable[(uchar)(x >> 8)];
t = t + t | g_rotTable[(uchar)x];
return t;
}
しかし、処理時間は 6.69秒/1億回ループ と逆に増えてしまった。
何故だろう？
結局テーブルを用いる方法はテーブルアクセスが頻繁になりバス幅を使い切ってしまうので
よろしくない、ということなのかなぁ
913 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 10:47:56
64ビットシフトならInt64ShrlMod32とかはどう？
ヘッダ見る限り、インラインアセンブリで書いているようだけど。
914 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 19:01:28
> SSEが使えるならpsllq & pmovmskb使うのが一番速そうだけど
妄言のような気もするが、念のために MMX を使用した版も作ってみた。
アルゴリズムは最速の 転置を行って、バイトスワップをするのを使用
処理時間は 3.16秒/1億回ループ と期待したほどには高速化されなかった
uint64 rotLeft90_MMX(uint64 x)
{
__asm {
movq mm0, x
movq mm2, td_00aa00aa00aa00aa
movq mm1, mm0
psrlq mm1, 7
pxor mm1, mm0
pand mm1, mm2
pxor mm0, mm1
psllq mm1, 7
pxor mm0, mm1
=== 長いので省略 ===
movq x, mm0
mov edx, long ptr x ; 上下32ビット反転
mov eax, (long ptr x) + 4
bswap edx
bswap eax
}
}
915 名前：デフォルトの名無しさん[sage] 投稿日：2006/08/31(木) 20:38:31
ulong
r (ulong x)
{
unsigned int a, b, c, d;
unsigned int y[2];
asm volatile ("movq %0, %%mm0" : : "m" (x));
asm volatile ("pmovmskb %%mm0, %0" : "=g" (a) :);
asm volatile ("psllq $1, %mm0");
asm volatile ("pmovmskb %%mm0, %0" : "=g" (b) :);
asm volatile ("psllq $1, %mm0");
asm volatile ("pmovmskb %%mm0, %0" : "=g" (c) :);
asm volatile ("psllq $1, %mm0");
asm volatile ("pmovmskb %%mm0, %0" : "=g" (d) :);
y[0] = a | (b << 8) | (c << 16) | (d << 24);
asm volatile ("psllq $1, %mm0");
asm volatile ("pmovmskb %%mm0, %0" : "=g" (a) :);
asm volatile ("psllq $1, %mm0");
asm volatile ("pmovmskb %%mm0, %0" : "=g" (b) :);
asm volatile ("psllq $1, %mm0");
asm volatile ("pmovmskb %%mm0, %0" : "=g" (c) :);
asm volatile ("psllq $1, %mm0");
asm volatile ("pmovmskb %%mm0, %0" : "=g" (d) :);
y[1] = a | (b << 8) | (c << 16) | (d << 24);
return y[0] | ((ulong) y[1] << 32);
}
pmovmskb使ったのってこういうのだと思ったけどコンパイラの最適化にかなりたよった
これより速いの書けなかった
ちなみに>>897のが5.96秒でこれが3.41秒だった
919 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 [sage] 投稿日：2006/08/31(木) 23:03:53
>>915
1ビット左シフトはユニットの空きを考慮して適宜同一レジスタ間の加算で代用するのは常識
あと、SIMD整数ユニットは大概2本あり、AMDのSIMDはLatencyが大きいのでその辺も考慮されたい。
movq mm0, mmword ptr [src]
pmovmskb eax, mm0
mov byte ptr [dest + 7], eax
movq mm1, mm0
paddb mm0, mm0
psllq mm1, 4
pmovmskb edx, mm1
mov byte ptr [dest + 3], edx
paddb mm1, mm1
pmovmskb eax, mm0
pmovmskb edx, mm1
mov byte ptr [dest + 6], eax
mov byte ptr [dest + 2], edx
paddb mm0, mm0
paddb mm1, mm1
pmovmskb eax, mm0
pmovmskb edx, mm1
mov byte ptr [dest + 5], eax
mov byte ptr [dest + 1], edx
paddb mm0, mm0
paddb mm1, mm1
pmovmskb eax, mm0
pmovmskb edx, mm1
mov byte ptr [dest + 4], eax
mov byte ptr [dest], edx
つーか、全てにおいて最適なスケジューリングなんてねーだろよ
923 名前：デフォルトの名無しさん[sage] 投稿日：2006/09/01(金) 00:02:28
んで、>>919 は1億回コールすると何秒かかったんだ？
926 名前：デフォルトの名無しさん[sage] 投稿日：2006/09/01(金) 00:10:10
ulong r (ulong x) {
ulong y;
asm volatile ("movq %0, %%mm0" : : "m" (x));
asm volatile ("pmovmskb %mm0, %eax");
asm volatile ("movb %%al, %0" : "=m" (((unsigned char *) &y)[0]) :);
asm volatile ("movq %mm0, %mm1");
asm volatile ("paddb %mm0, %mm0");
asm volatile ("psllq $4, %mm1");
asm volatile ("pmovmskb %mm1, %edx");
asm volatile ("movb %%dl, %0" : "=m" (((unsigned char *) &y)[4]) :);
asm volatile ("paddb %mm1, %mm1");
asm volatile ("pmovmskb %mm0, %eax");
asm volatile ("pmovmskb %mm1, %edx");
asm volatile ("movb %%al, %0" : "=m" (((unsigned char *) &y)[1]) :);
asm volatile ("movb %%dl, %0" : "=m" (((unsigned char *) &y)[5]) :);
asm volatile ("paddb %mm0, %mm0");
asm volatile ("paddb %mm1, %mm1");
asm volatile ("pmovmskb %mm0, %eax");
asm volatile ("pmovmskb %mm1, %edx");
asm volatile ("movb %%al, %0" : "=m" (((unsigned char *) &y)[2]) :);
asm volatile ("movb %%dl, %0" : "=m" (((unsigned char *) &y)[6]) :);
asm volatile ("paddb %mm0, %mm0");
asm volatile ("paddb %mm1, %mm1");
asm volatile ("pmovmskb %mm0, %eax");
asm volatile ("pmovmskb %mm1, %edx");
asm volatile ("movb %%al, %0" : "=m" (((unsigned char *) &y)[3]) :);
asm volatile ("movb %%dl, %0" : "=m" (((unsigned char *) &y)[7]) :);
return y;
}
これだと3.57秒で>>915のよりちょっとだけ遅かった
CPUによって全然違うと思うけど
自分のはペンティアム3
927 名前：デフォルトの名無しさん[sage] 投稿日：2006/09/01(金) 00:16:35
単発でx秒だったとか言われても
同一環境で試した他の結果も一緒に貼らんと無意味
928 名前：デフォルトの名無しさん[sage] 投稿日：2006/09/01(金) 00:21:26
他のも>>915に書いたよ[[@wikiへ>http://kam.jp"><META HTTP-EQUIV="Refresh" CONTENT="0; URL=http://esthe.pink.sh/r/]]
最終更新：2007年12月09日 22:46
