4

私はチェス盤を表し、合法的な動きをチェックするためにビットボードで遊んでいます。私が立ち往生しているのは、スライディング ピース攻撃におけるソース スクエアと宛先スクエア間の占有率の計算です。ルックアップでやりたくないので、ルックアップなしで間にある正方形のマスクを取得できるかどうかを調べようとしています。たとえば、次のボードでは、c4 に Rook があります。


8 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 0 0 
6 0 0 0 0 0 0 0 0 
5 0 0 0 0 0 0 0 0 
4 0 0 R 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 
  a b c d e f g h

空の正方形 (または占有された正方形、より簡単なもの) を表すビットボードと疑似有効な移動 Rf4 (Rook は c4 から f4 に移動できます) が与えられた場合、正方形 d4-e4 (ソースと宛先の正方形を除く) のマスクを取得する方法?

これが明確になると、垂直方向の移動は簡単になり、回転したビットボードを使用して斜め方向の移動を計算できるようになると思います。

編集:ビットボードは ulong/unsigned int64 で表され、8 ビットの各パックは実際のボードのランク/行を表します。

4

3 に答える 3

4

ここでいくつかの仮定を立てます: ボードは 64 ビットの数値として格納され、各 8 バイト ブロックは行を表します。行の各ビットは列 (a..h) を表します。ゼロベースの座標として開始位置と終了位置があります。すなわち:start = "C4" = [2,3]; end = "F4" = [5,3]

列が増加する水平移動の場合、移動距離を計算できます d = (F4-C4 = 3)。宛先を除外するために 1 を引くと、d-1 ビットの「トレイル」 t は になりt = (1<<(d-1))-1ます。ソース ピースに隣接するトレイルをシフトして、マスク M: を取得しますM = t<<(start.row*8 + start.column+1)。

これは、 M = ((1<<d)-2)<<(start.row*8 + start.column)

逆方向の水平移動の場合: 

 d = (C4-F4 = -3)
 t = (1<<(-d-1))-1
 M = (t<<dest.column+1)
 //-or-
 M = ((1<<-d)-2)<<(dest.row*8 + dest.column)

垂直に増加する動きの場合: 

 d = (C7-C4 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (start.row*8 + start.column)

垂直に減少する動きの場合: 

 d = (C4-C7 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (dest.row*8 + start.column)

垂直方向の移動については、最大の "vertical Trail" を格納することで d のループを置き換えることができます VT = 0x0101010101010101 = 72340172838076673。次に、実際の移動に適したビット数をマスクします。

これにより、計算が に減少しM = (VT & ((1<<(d*8)) - 2)) << (row*8+column)ます。

斜めの動きについても、おそらく同様のことができます。最大対角トレイル DT = から開始し0x0102040810204080、マスクを適用してdビットを設定し、エッジに近い方に応じて開始位置または終了位置にシフトします。これには、間違った行にラップアラウンドするエッジケースがないことを確認するための慎重なテストが必要です。

ソースと宛先の両方を除外し、1 回限りのエラーを修正するように編集

于 2011-06-27T20:04:25.753 に答える
1

事前の計算を行い、ピースの動きに対して可能なすべてのマスクを生成することを除けば（確実な可能性）、実行時にマスクを構築することは、各正方形の単純なルックアップと同じくらい時間的に費用がかかると予想されます' アプローチ。

于 2011-06-24T06:20:12.477 に答える
0

方向の単位ベクトルを取得 (dx,dy)/dx

この場合、(1,0)

次に、目的地に到達するまで、現在の位置をそのベクトルで繰り返しインクリメントします。対応する行列セルをインクリメント/割り当て中です。

于 2011-06-24T06:45:09.233 に答える