CCCマーケティング データベースマーケティング研究所の Tech Blog

研究所スタッフによる格闘記録やマーケティング界隈についての記事など

Rustでビットボードオセロを実装

はじめに

こんにちは、データベースマーケティング研究所の伊藤です。

今年の5月に研究所でオセロAI大会を開催しました。 この大会は私が実装したモンテカルロ木探索オセロAIが優勝しました。 大会直後は優勝したので記事を書こうと思っていたのですが なかなか記事を書く余裕がなく、 プログラムを改めて見直したうえで記事を書いてみました。

最近マイブームのRustでオセロAIのビットボードとモンテカルロ木探索を実装します。 今回はビットボードについての記事です。

環境

使用したコンパイラ、ツールのバージョンは以下のとおりです。

$ rustc --version
rustc 1.48.0 (7eac88abb 2020-11-16)
$ cargo --version
cargo 1.48.0 (65cbdd2dc 2020-10-14)

ビットボード

オセロはビットボードで実装しました。 ビットボードは盤面を石や駒があるマスを1, ないマスを0とするビット列で表現する方法です。 オセロだと8x8の64マスの黒石、白石の配置を考えればよいので、 64bit x 2 = 128bit で表現できます。

私の実装したビットボードでは盤面の 左上がビット列の64桁目、 左下がビット列の8桁目になっています。

実装

置ける石の位置を探す

置ける石の位置を返す関数legalを実装しました。

黒プレイヤーのターンの場合は、 引数playerに黒石のビット列(黒石があるマスを1、ないマスを0とする64bit符号なし整数)、 引数opponentに白石のビット列(白石があるマスを1、ないマスを0とする64bit符号なし整数)を与えると、 黒プレイヤーが石を置けるマスを1、 置けないマスを0とするビット列を返します。

use std::ops::{ Shl, Shr };

fn legal(player: u64, opponent: u64) -> u64 {
    let masks = [
        (1, 0x7e7e7e7e7e7e7e7e), // 左右
        (7, 0x007e7e7e7e7e7e00), // 右上、左下
        (8, 0x00ffffffffffff00), // 上下
        (9, 0x007e7e7e7e7e7e00), // 左上、右下
    ];
    let shifts = [Shl::shl, Shr::shr];
    let mut candidate = 0;

    // playerの配置を8方向にずらし合法手を探す
    for (n_shifts, mask) in masks.iter() {
        let mask = mask & opponent;

        for shift in shifts.iter() {
            let mut bits = mask & shift(player, n_shifts); // (1)
            for _ in 0..5 {
                bits |= mask & shift(bits, n_shifts); // (2)
            }
            candidate |= shift(bits, n_shifts); // (3)
        }
    }

    candidate & !(player | opponent) // (4)
}

masksは(シフトする桁数, マスク)の配列です。 シフトする桁数4通りと左右のシフト演算で8方向への移動を実現します。 マスクは、例えば、盤面を1ビット左シフトするときに 盤面左端の石が右端に移動しまうので、 右端を0にするために使います。

Rustでもほかの言語のようにシフト演算に<<, >>を使えますが、 コードの重複を減らすため[Shl::shl, Shr::shr]のように シフト演算の関数を配列にしてループ内で使っています。

合法手(置ける石の位置)を探す処理は、 playerの石の隣にあるopponentの石をbitsに代入(コード内の(1))、 連続しているopponentの石をbitsに追加していき(2)、 bitsの1つ隣を候補マスcandidateに追加(3)、 を8方向に行います。 ただし、このままでは石が置いてあるマスもcandidateに含まれているので、 (4)で石が置かれていないマスだけ取り出します。 石が置かれていないマスは!(player | opponent)で計算できます。

石を置く

reverse関数はビット列positionが1になっているマスに playerの石を置いたときの反転位置のビット列を返します。

put関数はreverse関数で計算した反転位置の石を反転 し、positionが1になっているマスにplayerの石を置きます。

どちらの関数も黒プレイヤーのターンのときは黒石のビット列、 白プレイヤーのターンのときは白石のビット列を引数playerに渡します。

fn reverse(player: u64, opponent: u64, position: u64) -> u64 {
    let masks: [(i32, u64); 4] = [
        (1, 0xfefefefefefefefe), (7, 0x7f7f7f7f7f7f7f00),
        (8, 0xffffffffffffff00), (9, 0xfefefefefefefe00),
    ];
    let shifts = [Shl::shl, Shr::shr];
    let mut rev = 0;

    // positionを8方向に動かし反転位置を探す
    for (n_shifts, mut mask) in masks.iter() {
        for shift in shifts.iter() {
            let mut r = 0;
            let mut pos = mask & shift(position, n_shifts); // (1)
            while pos & opponent != 0 {
                r |= pos; // (2)
                pos = mask & shift(pos, n_shifts);
            }
            if pos & player != 0 {
                rev |= r; // (3)
            }

            mask = mask >> n_shifts;
        }
    }

    rev
}

fn put (player: u64, opponent: u64, position: u64) -> (u64, u64) {
    let rev = reverse(player, opponent, position);
    // 石を反転
    let player = player ^ (position | rev);
    let opponent = opponent ^ rev;

    (player, opponent)
}

反転位置の計算は、 positionの隣に移動し(1)、 連続した相手の石をrに記録していき(2)、 連続した相手の石の後に自分の石があった場合にrevrを追加(3) という処理を8方向に行っています。

盤面

盤面のビットボード表現を構造体として定義します。

Board構造体にはEqトレイトを導出(derive)しました。 これで自分で実装した構造体Boardでも==が使えるはずです。

#[derive(PartialEq, Eq)]
pub struct Board {
    pub is_dark_turn: bool, // 黒の手番か
    dark: u64, // 黒石のビット列
    light: u64, // 白石のビット列
}

Board構造体にメソッドを定義します。

impl Board {
    // 初期配置(中央の4マスに黒石と白石を2つずつ置く)、
    // 黒プレイヤーのターンから始まる盤面を生成して返す。
    pub fn new() -> Self {
        Self {
            is_dark_turn: true,
            dark: 0x0000000810000000,
            light: 0x0000001008000000,
        }
    }

    // 置ける位置をビット列で返す
    fn legal(&self) -> u64 {
        if self.is_dark_turn {
            legal(self.dark, self.light)
        } else {
            legal(self.light, self.dark)
        }
    }

    // positionのマスに石を置けるかを返す
    pub fn is_legal(&self, position: u64) -> bool {
        position & self.legal() != 0
    }

    // positionの位置に石を置いたあとの盤面を生成して返す
    // positionが不正な位置の場合はエラー
    pub fn put(&self, position: u64) -> Result<Self, &str> {
        // 不正な手の場合のエラー
        if !self.is_legal(position) {
            return Err("illegal position");
        }

        // 石を置いたあとの盤面を生成
        // パスが必要なときはパス
        let board = if self.is_dark_turn { // let文内でifが使える!
            let (dark, light) = put(self.dark, self.light, position);
            let is_dark_turn = legal(light, dark) == 0;
            Board { is_dark_turn, dark, light }
        } else {
            let (light, dark) = put(self.light, self.dark, position);
            let is_dark_turn = legal(dark, light) != 0;
            Board { is_dark_turn, dark, light }
        };

        Ok(board)
    }

    // 黒石、白石の数を数え、タプルで返す
    pub fn score(&self) -> (u32, u32) {
        (self.dark.count_ones(), self.light.count_ones())
    }
}

ついでにDisplayトレイトを実装し、 println!マクロで出力できるようにしてみました。

use std::fmt;

const UPPER_LEFT: u64 = 0x8000000000000000;

impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let legal = self.legal();

        let board: String = (0..143).map(|n| {
            let x = n % 18;
            if x == 0 {
                return std::char::from_digit(n / 17 + 1, 10).unwrap();
            } else if x == 17 {
                return '\n';
            } else if x % 2 == 1 {
                return ' ';
            }

            let position = UPPER_LEFT >> (n / 18) * 8 + x / 2 - 1;
            if position & self.dark != 0 {
                'X'
            } else if position & self.light != 0 {
                'O'
            } else if position & legal != 0 {
                '*'
            } else {
                '-'
            }
        }).collect();

        let (n_dark, n_light) = self.score();

        write!(
            f, "X: {}, O: {}\n  1 2 3 4 5 6 7 8\n{}",
            n_dark, n_light, board
        )
    }
}

Displayトレイトを実装したのでprinln!("{}", Board::new())で、 以下のような盤面が表示されます。

X: 2, O: 2       
  1 2 3 4 5 6 7 8
1 - - - - - - - -
2 - - - - - - - -
3 - - - * - - - -
4 - - * O X - - -
5 - - - X O * - -
6 - - - - * - - -
7 - - - - - - - -
8 - - - - - - - -

おわりに

今回はRustでビットボードオセロを実装しました。 次回はモンテカルロ木探索を実装します。