はじめに
こんにちは、データベースマーケティング研究所の伊藤です。
今年の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)、
連続した相手の石の後に自分の石があった場合にrevにrを追加(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でビットボードオセロを実装しました。 次回はモンテカルロ木探索を実装します。
