【お勉強】Rustでオセロを実装する（機能編）【Bitboard】

はじめに

この記事は、Rustの勉強を目的としたオセロの実装をまとめたものになります。
私自身AtCoderなどの競技プログラミングで　Rust　を使っていますがそこで得られる知識は限られています。なので何かを作成することで他では得られない知識を得ようと考えた次第です。

なんでオセロ？

私がエンジニアの道を進むになるきっかけになったものがあります。コンピュータ将棋って世界なんですけど。
昔C++で頑張って実装していました。当時は情報系でもなかったし志半ばで終わったことを思い出し、将棋をリベンジする前にまずオセロを実装してみるのはアリだなと思ってオセロを選びました。今ならきっとできるはず...

オセロと将棋の違い

オセロも将棋も二人零和有限確定完全情報ゲームと言われていますがその最終局面数は将棋で $10^{68}$, オセロで $10^{22}$ とかなり差があります。差があると言ってもどちらも完全解析できるほどではないです（ちなみに6x6オセロは完全解析されています）。

Bitboardとは？

引用:ビットボードの凄さをざっくりと解説してみる
　その探索局面数の多さゆえにオセロ、将棋どちらもその計算量を減らす工夫がされてきました。そのうちの１つがビットボードと呼ばれるものです。盤面を管理することを考えた時にまず思いつくのが配列を利用する方法だと思います。ただ、配列で管理してしまうとメモリや探索の面で大きくパフォーマンスを下げてしまいます。そこで登場するのがビットボードです。盤面を１つの整数値で表すことで探索や更新にビット演算を用いることができます。このビット演算によって不必要なifやforを使わなくて済むので各種処理を高速化しています。以下は今回実装した合法手の生成のコードになります。たった数行で実現できています。

pub fn legal_moves(&self) -> u64 {
       #[inline]
       const fn calc(tp: u64, ntp: u64, mask: u64, shift: u32) -> u64 {
           let l = line!(tp, ntp & mask, shift_l, shift);
           let r = line!(tp, ntp & mask, shift_r, shift);
           shift_l(l, shift) | shift_r(r, shift)
       }

       let players = [self.black, self.white];
       let tp = players[self.turns % 2];
       let ntp = players[(self.turns+1) % 2];
       let blank_board = !(tp | ntp);
       let mut possible = 0;
       for (shift, mask) in Board::SHIFT_MASK_LIST {
           possible |= calc(tp, ntp, mask, shift);
       }
       possible & blank_board
   }

実装パート

あくまでRustのお勉強が目的なのでビットボードに関する詳しい解説はしません。もし詳しく知りたいという方のために参考にしたリンクをまとめておきます。

• ビットボード解説
• オセロをビットボードで実装した話
• 歌舞伎座.tech#4「コンピュータ将棋プログラミング」【山本一成】

実装したコードはGitHubにあげています。

プログラムの要件

以下を要件とします。

• 人 vs CPU の対戦ができること
• 黒番と白番選べること
• ビットボードを用いた実装であること
• リトライができること

プロジェクト作成

$ cargo new othello --bin

盤面管理の実装

黒の盤面と白の盤面を表す変数と手数を定義したもの

board.rs

pub struct Board {
    black: u64,
    white: u64,
    turns: usize,
}

impl Board {
    pub fn new() -> Self {
        let black = 0x0000000810000000;
        let white = 0x0000001008000000;
        let n_moves = 0;
        Board { black, white, turns: n_moves }
    }
}

合法手の生成

連続する白石を調べ、その隣のマスが空マスの場所を全方位調べています。
ビット演算は可読性が悪いですがコード量を限りなく減らせるので数行でかけてしまいます。
そもそもビット演算に可読性を求めてはいけません。

board.rs

pub fn legal_moves(&self) -> u64 {
    #[inline]
    const fn calc(tp: u64, ntp: u64, mask: u64, shift: u32) -> u64 {
        let l = line!(tp, ntp & mask, shift_l, shift);
        let r = line!(tp, ntp & mask, shift_r, shift);
        shift_l(l, shift) | shift_r(r, shift)
    }

    let players = [self.black, self.white];
    let tp = players[self.turns % 2];
    let ntp = players[(self.turns+1) % 2];
    let blank_board = !(tp | ntp);
    let mut possible = 0;
    for (shift, mask) in Board::SHIFT_MASK_LIST {
        possible |= calc(tp, ntp, mask, shift);
    }
    possible & blank_board
}

着手の実装

着手地点から全方位に対して連続する白石を調べ、それをそれぞれの盤面に反映させています。
最後に更新された状態のBoardを返しています。手数も忘れずに進めておきます。

board.rs

pub fn reverse(&self, position: u64) -> Self {
    #[inline]
    const fn calc(tp: u64, ntp: u64, position: u64, mask: u64, shift: u32) -> u64 {
        let mask = ntp & mask;
        let l1 = line!(position, mask, shift_l, shift);
        let r1 = line!(tp, mask, shift_r, shift);
        let r2 = line!(position, mask, shift_r, shift);
        let l2 = line!(tp, mask, shift_l, shift);
        (l1 & r1) | (r2 & l2)
    }

    let players = [self.black, self.white];
    let tp = players[self.turns % 2];
    let ntp = players[(self.turns+1) % 2];
    
    let mut target = 0u64;
    for (shift, mask) in Board::SHIFT_MASK_LIST {
        target |= calc(tp, ntp, position, mask, shift);
    }
    let new_tp = tp ^ position ^ target;
    let new_ntp = ntp ^ target;
    let new_players = [new_tp, new_ntp];
    let black = new_players[self.turns % 2];
    let white = new_players[(self.turns+1) % 2];
    Board { black, white, turns: self.turns + 1 }
}

全コードは載せていませんが盤面管理の部分に関してはあらかた実装完了です。

ゲームを管理する部分の実装

必要そうなメソッドを先に定義しておきます。
Rustに限らず毎回思うんですがこの実装でいいのかわかりません。
詳細コードに関してはゲームを開始する部分のみにします。

game.rs

pub struct OthelloGame {
    state: OthelloGameState,
    black_player: PlayerType,
    board: Board,
}

impl OthelloGame {
    pub fn new() -> Self {
        OthelloGame {
            state: OthelloGameState::BeforeMatch,
            black_player: PlayerType::Human,
            board: Board::new(),
        }
    }

    // 黒番と白番の設定を想定
    pub fn configure(&mut self) {}

　　　　　　　　// ゲームを開始し管理する
    pub fn start(&mut self) {}

    // 勝者を出力
    pub fn results(&self) {}

    // 続けるか終わるのか選択
    pub fn continue_or_not(&self) -> bool {}
}

ゲームを開始する

流れとしては、

1. 現在の盤面の表示
2. 合法手の生成
3. 指手の表示
4. 選択された指手を着手
5. 盤面を更新
6. 勝敗を確認、決まっていれば終了

このようになります。オセロのルール上、盤面が全部埋まる or お互い置ける場所がなくなった場合に終了になります。

game.rs

pub fn start(&mut self) {
    let mut pass = false;
    let row_label = ["H","G","F","E","D","C","B","A"];
    loop {
        self.board.show();
        let moves_value = self.board.legal_moves();
        let moves = self.board.split_moves(moves_value);
        let black_turn = self.board.turn() == Player::Black;
        let p_label = if black_turn {"黒[●]"} else {"白[○]"};
        
        if moves.len() != 0 {
            println!("{}手目 - {} の手番です", self.board.turns() + 1, p_label);
            println!("Moves");
            for (i, m) in moves.iter().enumerate() {
                let n_shift = format!("{:b}", m).len()-1;
                println!("{}: {}{}", i+1, row_label[n_shift%8], 8-n_shift/8);
            }
            let input = if black_turn {
                let human = self.black_player == PlayerType::Human;
                if human {OthelloGame::human_input} else {OthelloGame::cpu_input}
            } else {
                let human = self.black_player == PlayerType::Cpu;
                if human {OthelloGame::human_input} else {OthelloGame::cpu_input}
            };
            let index = input(moves.len());
            self.board = self.board.reverse(moves[index-1]);
            pass = false;
            if self.board.end() {
                self.state = OthelloGameState::MatchFinished;
                return;
            }
        } else {
            println!("{} の手番ですが指す手がないためパスします", p_label);
            self.board = self.board.pass();
            if pass {
                self.state = OthelloGameState::MatchFinished;
                return;
            }
            pass = true;
        }
    }
}

main関数の実装

先ほど実装したOthelloGameを使って順に呼び出します。
実装としてはイマイチになりましたが機能的には動くのでヨシとしましょう。

main.rs

fn main() {
    loop {
        let mut game = OthelloGame::new();
        game.configure();
        game.start();
        game.results();
        if !game.continue_or_not() {
            break;
        }
    }
}

遊んでみる

開始時にまず黒番か白番を設定するか聞かれるので答えます（画像では私が黒番）。
こちらが着手すると白番のCPUが自動で着手します。

終了時を見てみると盤面の全てのマスが埋まった瞬間に勝者が表示されています（今回は黒番の私の勝ち）。
その後、リトライするかどうか聞かれます（2を選んだので終了）。

開始時	終了時

ということで無事プログラムが完成しました。ちゃんと動くものができているのは感慨深いですね。

作ってみた感想

今回はオセロでビットボードを使った実装をしましたが、将棋ではこれよりはるかにハードルが高いです（駒がそれぞれ違う動きをしたり、取った駒を使えたり自由すぎる）。それと違ってオセロは64マスなので64bit変数１つで綺麗に表現できるのが便利すぎます。将棋でやろうとすると64bit+32bitの２つを使うことになるので実装もそれなりに複雑です。いつかやってみようとは思ってますがとりあえずは5五将棋という5x5マスの方に挑戦します。あと、この記事のメインであるRustのお勉強に関して今回の実装で得た学びをまとめておきます。

Rustでは桁溢れを切り捨ててくれない

立っている最右端ビット(Right Most Bit)の位置を高速に算出する方法
こちらを実装しようとしていた時の話。
C#とは違い桁溢れはRuntimeErrorになるみたいです（debugモードのみらしい）

let y = memo & !memo.wrapping_sub(1);

なので上記のようにwrapping_xxx()を用いて回避

macro_rulesの使い方

今回実装したマクロ。純粋に使い方を知らなかったので今回で使いこなせるようになった気がします。
以下は連続する相手の石を調べるもの

macro_rules! line {
    ($start:expr, $data:expr, $shift:ident, $n:expr) => {
        {
            let mut result = $data & $shift($start, $n);
            result |= $data & $shift(result, $n);
            result |= $data & $shift(result, $n);
            result |= $data & $shift(result, $n);
            result |= $data & $shift(result, $n);
            result |= $data & $shift(result, $n);
            result
        }
    }
}

列挙型も構造体を同じようにメソッドを定義できる

これ便利すぎ。。知りませんでした。
今回利用した部分は以下の通り。

pub enum Player {
    Black,
    White,
}

pub enum GameResult {
    Winner(Player),
    Draw,
}

match white_count.cmp(&black_count) {
    Ordering::Equal => GameResult::Draw,
    Ordering::Greater => GameResult::Winner(Player::White),
    Ordering::Less => GameResult::Winner(Player::Black),
}

構造体の作法全般

構造体は競技プログラミングでも使っていますが今回の実装で知らなかったことがたくさんあったので知識としてかなりついたと思います。将来的にサーバーサイドをRustで実装したいなと思っているのでやって良かったなと思います。

また、今回実装していくにあたってChatGPTを活用しました。使い方としては、

• Rustの文法についての質問
• 命名や設計に関する質問
• 実装した関数のリファクタリング

でした。ChatGPTを活用したことで開発がスムーズに進んだのはもちろん、知り得なかった知識を提供してくれました。時には喧嘩もしたけど最後は完成に持って行けて本当に良かった。

↓対話の様子

終わりに

今回、Rustのお勉強を目的としたオセロの実装をしました。
どの歳になっても何かを作るということは楽しいなと思います。
次はオセロのCPUをある程度強くするために探索編を執筆予定です。

実装したコードはGitHubにあげています。