Go to Qiita Advent Calendar 2024 Top
LoginSignup
8
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@ysuzuk81

ビットボードの回転

Last updated at Posted at 2022-02-26

1. はじめに

本記事では、8×8のビットボードの90度回転、180度回転、45度回転について取り扱う。
45度回転については、ビットボードを厳密に45度回転させることは出来ないため、
本記事では、斜め方向のビットを水平方向のビットの並びに変換することを45度回転と呼ぶことにする。

2. 本記事で用いるビットボードの定義

符号なし64ビット整数を8×8の行列だと捉えたものを用いる。
オセロの駒の位置とビット位置は下記の画像のように対応する。
例えば、位置A1の駒の状態は63ビット目で管理する。
1.png

3. Delta Swapと循環ビットシフト

ビットボードを回転させるためには、Delta Swapと循環ビットシフトが必要である。
Delta Swapとは、対象のビット列の部分列をXORを用いて入れ替える操作である。
下記の記事で、図付きで分かりやすく紹介されている。
Delta Swapの簡単解説

よって、本記事では下記の関数を用いる。

using u64 = unsigned long long;

// Delta Swap
u64 delta_swap(u64 x, u64 mask, int delta) {
    u64 t = (x ^ (x >> delta)) & mask;
    return x ^ t ^ (t << delta);
}

// 左循環ビットシフト
u64 rotateLeft(u64 x, int n) {
    return (x << n) | (x >> (64 - n));
}

// 右循環ビットシフト
u64 rotateRight(u64 x, int n) {
    return (x >> n) | (x << (64 - n));
}

4. 回転させるために必要な操作

ビットボードの回転は、下記の4つの反転操作をうまく組み合わせることで実現可能である。

  • D列とE列の間を軸とする反転（以下 水平反転）
  • 4行目と5行目の間を軸とする垂直反転（以下 垂直反転）
  • A1-H8の対角線を軸とする反転（以下 A1-H8反転）
  • A8-H1の対角線を軸とする反転（以下 A8-H1反転）

まずはこの4つの操作について解説する。

4-1. 水平反転

D列とE列の間を軸とする水平反転は以下の手順で行う。

① Delta Swapを用いて、A列⇔B列、C列⇔D列、E列⇔F列、G列⇔H列を入れ替える。
2.png

  • オレンジ：入れ替え元の部分。Delta Swapの引数maskに指定する。
  • 緑：入れ替え先の部分。

Delta Swapの引数deltaには、オレンジの部分を左シフトして緑の部分に重なるような値を指定する。
この場合だと、mask=0x5555555555555555、delta=1となる。

これにより、オレンジと緑の部分が入れ替わる。

② A-B列⇔C-D列、E-F列⇔G-H列を入れ替える。
3.png
③ A-D列⇔E-H列を入れ替える
4.png
以上より、D列とE列の間を軸とする水平反転を実現できる。

  • 水平反転後
    5.png 
// 水平反転
u64 flipHorizontal(u64 x) {
    x = delta_swap(x, 0x5555555555555555, 1);
    x = delta_swap(x, 0x3333333333333333, 2);
    return delta_swap(x, 0x0F0F0F0F0F0F0F0F, 4);
}

4-2. 垂直反転

4行目と5行目の間を軸とする垂直反転は以下の手順で行う。

① 1行目⇔2行目、3行目⇔4行目、5行目⇔6行目、7行目⇔8行目を入れ替える。
2.png
② 1-2行目⇔3-4行目、5-6行目⇔7-8行目を入れ替える。
3.png
③ 1-4行目⇔5-8行目を入れ替える。
4.png
以上より、4行目と5行目の間を軸とする垂直反転を実現できる。

  • 垂直反転後
    5.png 
// 垂直反転
u64 flipVertical(u64 x) {
    x = delta_swap(x, 0x00FF00FF00FF00FF, 8);
    x = delta_swap(x, 0x0000FFFF0000FFFF, 16);
    return delta_swap(x, 0x00000000FFFFFFFF, 32);
}

4-3. A1-H8反転

A1-H8の対角線を軸とする反転は以下の手順で行う。

① 太字の2x2の集合において、左下と右上の部分を入れ替える。
2.png
② 4×4の集合において、左下と右上の部分を入れ替える。
3.png
③ 8×8の集合において、左下と右上の部分を入れ替える。
4.png
以上より、A1-H8の対角線を軸とする反転を実現できる。

  • A1-H8反転後
    5.png 
// A1-H8反転
u64 flipDiagonalA1H8(u64 x) {
    x = delta_swap(x, 0x00AA00AA00AA00AA, 7);
    x = delta_swap(x, 0x0000CCCC0000CCCC, 14);
    return delta_swap(x, 0x00000000F0F0F0F0, 28);
}

4-4. A8-H1反転

A8-H1の対角線を軸とする反転は以下の手順で行う。

① 太字の2×2の集合において、右下と左上の部分を入れ替える。
2.png
② 4×4において右下と左上の部分を入れ替える。
3.png
③ 8×8において右下と左上の部分を入れ替える。
4.png
以上より、A8-H1の対角線を軸とする反転を実現できる

  • A8-H1反転後
    5.png 
// A8-H1反転
u64 flipDiagonalA8H1(u64 x) {
    x = delta_swap(x, 0x0055005500550055, 9);
    x = delta_swap(x, 0x0000333300003333, 18);
    return delta_swap(x, 0x000000000F0F0F0F, 36);
}

5. ビットボードの90度回転

時計回り・反時計回りの2種類の回転について解説する。

5-1. 時計回りに90度回転

先程の4つの操作をうまく組み合わせることで実現可能である。
下記の4つの組み合わせが存在する。

  • 垂直反転 ⇒ A1-H8反転
  • 水平反転 ⇒ A8-H1反転
  • A1-H8反転 ⇒ 水平反転
  • A8-H1反転 ⇒ 垂直反転

代表例として、今回は「A1-H8反転 ⇒ 水平反転」による方法を以下に示す。
1.png
① A1-H8反転後
2.png
② 水平反転後
3.png
以上より、時計回りに90度の回転を実現できる。

// 時計回りに90度回転
u64 rotateClockwise90(u64 x) {
    return flipHorizontal(flipDiagonalA1H8(x)); 
}

5-2. 反時計回りに90度回転

下記の4つの組み合わせが存在する。

  • 垂直反転 ⇒ A8-H1反転
  • 水平反転 ⇒ A1-H8反転
  • A1-H8反転 ⇒ 垂直反転
  • A8-H1反転 ⇒ 水平反転

代表例として、今回は「A1-H8反転 ⇒ 垂直反転」による方法を以下に示す。

1.png
① A1-H8反転後
2.png
② 垂直反転後
3.png
以上より、反時計回りに90度の回転を実現できる。

// 反時計回りに90度の回転
u64 rotateCounterclockwise90(u64 x) {
    return flipVertical(flipDiagonalA1H8(x)); 
}

6. ビットボードの180度回転

下記の2つの方法が存在する。

  • 水平反転 + 垂直反転
  • A1-H8反転 + A8-H1反転

180度回転は90度回転と異なり、組み合わせる操作に順序は存在しない。
「水平反転 ⇒ 垂直反転」と「垂直反転 ⇒ 水平反転」のどちらでも可能である。

代表例として、今回は「水平反転 ⇒ 垂直反転」による方法を以下に示す。

1.png
① 水平反転後
2.png
② 垂直反転後
3.png
以上より、180度の回転を実現できる。

// 180度回転
u64 rotate180(u64 x) {
    return flipVertical(flipHorizontal(x));
}

7. ビットボードの45度回転

7-1. 時計回りに45度回転

時計回りに45度回転する方法は、下記の2つが存在する。

  • A8-H1の対角線上のビットが上位8ビットに集まる方法
    （以下 時計回りに45度回転（A8-H1⇒上位8ビット））
    6.png
    ↓
    7.png

  • A8-H1の対角線上のビットが下位8ビットに集まる方法
    （以下 時計回りに45度回転（A8-H1⇒下位8ビット））
    6.png
    ↓
    7.png

7-1-1. 時計回りに45度回転（A8-H1⇒上位8ビット）

① オレンジの部分を8ビットだけ左循環ビットシフトする。
2.png
② 16ビットだけ左循環ビットシフトする。
3.png
③ 32ビットだけ左循環ビットシフトする。
4.png
以上より、時計回りに45度回転（A8-H1⇒上位8ビット）を実現できる。

  • 時計回りに45度回転（A8-H1⇒上位8ビット）後
    5.png 
// 時計回りに45度回転（A8-H1⇒上位8ビット）
u64 rotateClockwise45Upper(u64 x) {
    u64 const mask1 = 0xAAAAAAAAAAAAAAAA;
    u64 const mask2 = 0xCCCCCCCCCCCCCCCC;
    u64 const mask3 = 0xF0F0F0F0F0F0F0F0;

    x ^= mask1 & (x ^ rotateLeft(x, 8));
    x ^= mask2 & (x ^ rotateLeft(x, 16));
    return x ^ mask3 & (x ^ rotateLeft(x, 32));
}

7-1-2. 時計回りに45度回転（A8-H1⇒下位8ビット）

① オレンジの部分を8ビットだけ右循環ビットシフトする。
2.png
② 16ビットだけ右循環ビットシフトする。
3.png
③ 32ビットだけ右循環ビットシフトする。
4.png
以上より、時計回りに45度回転（A8-H1⇒下位8ビット）を実現できる。

  • 時計回りに45度回転（A8-H1⇒下位8ビット）後
    5.png 
// 時計回りに45度回転（A8-H1⇒下位8ビット）
u64 rotateClockwise45Lower(u64 x) {
    u64 const mask1 = 0x5555555555555555;
    u64 const mask2 = 0x3333333333333333;
    u64 const mask3 = 0x0F0F0F0F0F0F0F0F;

    x ^= mask1 & (x ^ rotateRight(x, 8));
    x ^= mask2 & (x ^ rotateRight(x, 16));
    return x ^ mask3 & (x ^ rotateRight(x, 32));
}

7-2. 反時計回りに45度回転

反時計回りに45度回転する方法は、A1-H8の対角線のビットが上位8ビットに集まる方法と、
下位8ビットに集まる方法の2つがあります。
反時計回りに45度回転する方法は、下記の2つが存在する。

  • A1-H8の対角線のビットが上位8ビットに集まる方法
    （以下 反時計回りに45度回転（A1-H8⇒上位8ビット））
    6.png
    ↓
    7.png

  • A1-H8の対角線のビットが下位8ビットに集まる方法
    （以下 反時計回りに45度回転（A1-H8⇒下位8ビット））
    6.png
    ↓
    7.png

7-2-1. 反時計回りに45度回転（A1-H8⇒上位8ビット）

1.png
① オレンジの部分を8ビットだけ左循環ビットシフトする。
2.png
② 16ビットだけ左循環ビットシフトする。
3.png
③ 32ビットだけ左循環ビットシフトする。
4.png
以上より、A1-H8の対角線のビットが上位8ビットに集まるような、反時計回りに45度回転を実現できる。

  • 反時計回りに45度回転（A1-H8⇒上位8ビット）後
    5.png 
// 反時計回りに45度回転（A1-H8⇒上位8ビット）
u64 rotateCounterclockwise45Upper(u64 x) {
    u64 const mask1 = 0x5555555555555555;
    u64 const mask2 = 0x3333333333333333;
    u64 const mask3 = 0x0F0F0F0F0F0F0F0F;

    x ^= mask1 & (x ^ rotateLeft(x, 8));
    x ^= mask2 & (x ^ rotateLeft(x, 16));
    return x ^ mask3 & (x ^ rotateLeft(x, 32));
}

7-2-2. 反時計回りに45度回転（A1-H8⇒下位8ビット）

1.png
① オレンジの部分を8ビットだけ右循環ビットシフトする。
2.png
② 16ビットだけ右循環ビットシフトする。
3.png
③ 32ビットだけ右循環ビットシフトする。
4.png
以上より、A1-H8の対角線のビットが下位8ビットに集まるような、反時計回りに45度回転を実現できる。

  • 反時計回りに45度回転（A1-H8⇒下位8ビット）後
    5.png 
// 反時計回りに45度回転（A1-H8⇒下位8ビット）
u64 rotateCounterclockwise45Lower(u64 x) {
    u64 const mask1 = 0xAAAAAAAAAAAAAAAA;
    u64 const mask2 = 0xCCCCCCCCCCCCCCCC;
    u64 const mask3 = 0xF0F0F0F0F0F0F0F0;

    x ^= mask1 & (x ^ rotateRight(x, 8));
    x ^= mask2 & (x ^ rotateRight(x, 16));
    return x ^ mask3 & (x ^ rotateRight(x, 32));
}

8. 参考文献

Flipping Mirroring and Rotating
ビットボードの回転・反転
Delta Swapの簡単解説
Delta swapとその応用 【ビット演算テクニック Advent Calendar 2016 3日目】
オセロをビットボードで実装した話

8
3
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?