#77 ⭕️❌ゲームで学ぶビット演算
⭕️❌ゲームで学ぶビット演算
今回はタイトルの通り、⭕️❌ゲームの作成を通じてビット演算を学んでいきたいと思います
ビット演算とは
ビット演算（bitwise operation）とは、主にコンピュータ上で行われる演算の一つで、対象データをビット列（2進数の0と1の羅列）とみなして、ビットの移動やビット単位の論理演算などを行うもの。
引用元の説明にある通り、ビット列に対して論理演算を行うことを指し、省メモリ化や処理の高速化などの恩恵を受けられる可能性があります
デメリットとしてはコードの可読性が落ちることが挙げられます
基本的なビット演算
言語によって異なる場合がありますが、基本的な演算子としては以下のようなものがあり、これらを組み合わせて演算を行います
- & (AND) 論理積
- | (OR) 論理和
- ~ (NOT) 反転
- ^ (XOR) 排他的論理和
- >> (右シフト)
- << (左シフト)
ビット列で⭕️❌ゲームの盤面を表現する
まず、⭕️❌ゲームのマス目に以下のように番号を振ります。
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
今回は⭕️をBlack, ❌をWhiteと表現することにします
一般的な9マスなので、9bit以上であることが保証されている数値型の変数をBlackとWhite用に2つ用意します
例えば、0番と4番にBlackがあり、2番と8番にWhiteが存在した場合
Blackは、0b000010001 → 0x11
Whiteは、0b100000100 → 0x104
と表現します
着手可能位置を求める
着手可能な位置を求めるためには、着手可能位置 = ~(Black | White)で求められます
例) 先ほどの盤面の着手可能位置を求める場合
0b000010001
OR 0b100000100
---------------
NOT 0b100010101
---------------
0b011101010
これは一体何を行なっているのかというと、Black | Whiteでどちらかが必ず置かれているマスを取得し、それを反転することで何も置かれていないマスつまり着手可能位置を求めることができます
任意の位置に石を置く
任意の位置に石を追加したい場合は、対象の種類 |= 0b01 << 位置番号と書きます。
例) Blackを3番の位置おく場合
Black |= 0b01 << 3
Black → 0b000011001 → 0x19
一体どのような演算を行なっているのかというと、0b01は最下位ビットが立っている状態で、位置番号分左シフトするとその位置のビットが立っているビット列が得られます
例) 0b000000001を左に3つシフトすると0b000001000となります
得られたビット列を元々の盤面のビット列の論理和をとることで街頭の位置のビットを立てることができます
視覚的にわかりやすく表現すると以下のように表せます
0b000010001
OR 0b000001000
--------------
0b000011001
実装例
先ほどのビット演算の説明を踏まえ、以下に実装例を示します
const enum Color {
SPACE,
BLACK,
WHITE
};
class Field {
//⭕️
private blackStones: number;
//❌
private whiteStones: number;
//手番
private turn: Color.BLACK | Color.WHITE = Color.BLACK;
/**
*
* @param optionTypeBitBoard
*/
constructor(optionTypeBitBoard?: { blackStones: number, whiteStones: number, turn: number }) {
if (optionTypeBitBoard) {
this.blackStones = optionTypeBitBoard.blackStones;
this.whiteStones = optionTypeBitBoard.whiteStones;
this.turn = optionTypeBitBoard.turn;
}
else {
this.blackStones = this.whiteStones = 0;
this.turn = Color.BLACK;
}
}
/**
* 盤面を複製する
* @returns
*/
clone() {
return new Field({
blackStones: this.blackStones,
whiteStones: this.whiteStones,
turn: this.turn
});
}
/**
* 手番を入れ替える
*/
private switchTurn() {
this.turn = this.turn == Color.BLACK ? Color.WHITE : Color.BLACK;
}
/**
* 手番を取得する
* @returns
*/
getTurn() {
return this.turn;
}
/**
* 手番を設定する
* @param color
*/
setTurn(color: Color.BLACK | Color.WHITE) {
this.turn = color;
}
/**
* 指定した箇所に石を置く。着手した後、自動で手番が変わる
* @param x
* @param y
* @returns
*/
putStoneXY(x: number, y: number) {
if (x < 0 || 2 < x || y < 0 || 2 < y) {
throw new Error("Out of Range");
}
this.putStone(x + y * 3);
}
/**
* 指定した箇所に石を置く。着手した後、自動で手番が変わる
* @param x
* @returns
*/
putStone(x: number){
const position = 0b01 << x;
//すでに石が置かれているか判定
if ((this.blackStones & this.whiteStones & position) != 0) {
throw new Error("Out of Range");
}
if (this.turn == Color.BLACK) {
this.switchTurn();
return this.blackStones |= position;
}
if (this.turn == Color.WHITE) {
this.switchTurn();
return this.whiteStones |= position;
}
}
/**
* 盤面を取得する
* @returns
*/
getField() {
const field: Color[][] = new Array(3);
for (let i = 0; i < 3; i++) {
field[i] = new Array(3);
}
for (let x = 0; x < 3; x++) {
for (let y = 0; y < 3; y++) {
field[y][x] =
((this.blackStones >> (x + y * 3)) & 0b01) == 1 ? Color.BLACK
: (((this.whiteStones >> (x + y * 3)) & 0b01) == 1 ? Color.WHITE : Color.SPACE);
}
}
return field;
}
//ビットボードで盤面を取得する
getFieldTypeBitBoard() {
return {
black: this.blackStones,
white: this.whiteStones,
space: ~(this.blackStones | this.whiteStones)
};
}
}
まとめ
今回は⭕️❌ゲームでビット演算について学びました
⭕️❌ゲームでビット演算を使ってみましたが、オセロなどでも使うことができビット演算の恩恵をかなり受けることができますので試してみてください
Discussion