Rustで速習ゲーム木探索

この記事はRustのカレンダー | Advent Calendar 2021の15日目の記事です。

二人零和有限確定完全情報ゲームである三目並べを作ってゲーム木探索を学びましょう。ボードゲームの強いAIが作れるようになります。

ボードゲームAIの強さを決めるポイントとして探索と評価があります。この記事では勝ち負け以外の評価をせず、探索に絞って話を進めます。ゲーム木・二人零和有限確定完全情報ゲームを説明してから、本記事のゴールであるモンテカルロ木探索に向けて全探索・ランダム・原始的なモンテカルロ探索・モンテカルロ木探索の順で解説をします。

もっと情報が欲しい方は記事末尾の参考文献を参照ください。

ゲーム木とは?

ゲームを盤面(ノード)から合法手(エッジ)を選択して次の盤面に移動するとみたときの、初期盤面を根とする根付き木のことです。

二人零和有限確定完全情報ゲームとは?

次のようなゲーム群を指す言葉です。

マンカラのイラストリバーシのイラスト

これらは次のような特徴を持ちます。

  • 二人: プレイヤーが2人。
  • 零和: 全プレイヤーの利得の総和が0になる。あるプレイヤーが勝つ(+v)とその分別のプレイヤーが負ける(-v)。
  • 有限: 合法手を選び続けると、有限の手数でゲームが終わる。
  • 確定: 選んだ手が確率によって失敗するなどの運要素がない。
  • 完全情報: 伏せカード・同時に出される相手の手など隠された情報がない。
脱出ゲームのイラストババ抜きのイラストポッキーゲームのイラスト

二人零和有限確定完全情報ゲームは、お互いが最善手を指したときに「先手必勝」「引分」「後手必勝」が確定するため、十分な計算資源があればゲームの先読みをして最善手を指すことができます。

二人零和有限確定完全情報ゲームではないものの例

  • 3人以上で行うゲーム: プレイヤーが2人でない
  • 協力型のゲーム: 利益が相反しないため(全員勝利・全員敗北などがある)零和でない
  • ババ抜き: JOKERを引き続けるとゲームが終わらない
  • バックギャモン:すごろくなどサイコロを振って選択肢を決めるため確定ではない
  • じゃんけん: 同時に行動するため、自分が手を決めるときに分からない情報があり完全情報ではない sweets_pokki_game_couple.png (36.0 kB) game_dassyutsu_people.png (41.5 kB) game_trump_babanuki.png (32.7 kB)

3目並べのプログラム

3目並べのプログラムをRustで実装しました。 game.rs に3目並べの初期局面・終了判定・勝利判定・合法手生成が、strategy以下に各アルゴリズムで合法手を返す関数が実装されています。

.
├── Cargo.toml
└── src
    ├── game.rs
    ├── lib.rs
    ├── main.rs
    ├── strategy
    │   ├── alpha_beta.rs
    │   ├── mcs.rs
    │   ├── mcts.rs
    │   └── random.rs
    └── strategy.rs

ここからはstrategy側からある盤面と合法手が与えられたときにどの手を選ぶかという話をしましょう!

Minimax法という全探索

ゲーム理論でいうところのサブゲーム完全均衡を探索する方法。

ある局面から全ての合法手を辿る(それぞれの分岐を葉まで探索する)と勝ち負けが確定している木が得られます。 このゲームは先手必勝(先手が最善手を選び続ける限り、後手がどのように手を選んでも先手が勝つ)・後手必勝・引き分けのどれでしょうか?

f:id:matsu7874:20211215030106p:plain
ゲーム木

各ノードについて下記のルールに従って深さ優先探索をすることで後手必勝であると確かめることができます。

  • 先手手番(青丸)では子ノードのうち最大値をもつノードを選択する
  • 後手手番(赤四角)では子ノードのうち最小値をもつノードを選択する

各ノードにそれぞれのプレイヤーにとっての利得(嬉しさ)を持たせることができますが、特に二人零和ゲームの文脈では プレイヤー1の利得= -プレイヤー2の利得 が成り立つため、Negamaxという実装テクニックが使えます。 これは同じ評価値を使い手番が交代するたびに子ノードの評価値を-1倍する実装方法です。探索が各ノードで常に最大値を探すと表現できるため実装が簡単になるメリットがあります。

ゲームの初期局面から到達可能な全ての局面を調べることで、ゲームを完全に解析することができますが、局面数が多いゲームでは計算量が爆発し現実的な時間で計算を終えることができません。

αβ法という枝刈り

Minimax法の高速化としてαβ法という枝刈りテクニックがあります。 注目ノードの子ノードで最大値がαであるようなもの(ノードA)があれば、α > βであるような子(ノードC)を持つ子ノード(ノードB)に遷移すると相手にノードCへ遷移されて不利になるため、ノードBに遷移することはありえず、ノードBの残りの子ノードの探索が不要になるという考え方です。

f:id:matsu7874:20211215031320p:plain
青線で枝刈りが発生
f:id:matsu7874:20211215031442p:plain
右下の赤線で枝刈りが発生

先手勝ちの評価を1.0, 後手勝ちの評価を-1.0として実装例は下記のようになります。

use crate::State;
fn alpha_beta(state: &State, alpha: f64, beta: f64) -> f64 {
    if state.is_lose() {
        return -1.0;
    }
    if state.is_draw() {
        return 0.0;
    }
    let mut alpha = alpha;
    for action in state.legal_actions() {
        let score = -alpha_beta(&state.next(action), -beta, -alpha);
        if score > alpha {
            alpha = score;
        }
        if alpha >= beta {
            return alpha;
        }
    }
    alpha
}
pub fn alpha_beta_action(state: &State) -> u16 {
    let mut best_action = 0;
    let mut alpha = f64::MIN;
    for action in state.legal_actions() {
        let score = -alpha_beta(&state.next(action), f64::MIN, -alpha);
        if score > alpha {
            best_action = action;
            alpha = score;
        }
    }
    best_action
}

合法手をランダムに選ぶAI

ところで、枝刈りをしても全探索で所望の時間内で計算が終わらない場合はどうすればいいでしょうか?

最もシンプルな方法として合法手の中からランダムに選ぶという方法があります。

pub fn random_action(state: &State) -> u16 {
    let mut rng = rand::thread_rng();
    let legal_actions = state.legal_actions();
    *legal_actions.choose(&mut rng).unwrap()
}

合法手から手を選び続ける限り、ルール違反で負ける事はありません。

モンテカルロ探索

では、上記の各手番でランダムに手を選択する戦略よりもよりよい手を選ぶ確率を上げることはできるでしょうか?

それぞれの手を選んだ後もプレイアウト(ランダムにプレイを続け勝敗が確定するところまで進めること)を行います。 これを何度も繰り返すと、比較的勝てる手が分かります。これを返すことにしましょう。

const MCS_SIMULATION_COUNT: usize = 1000;
pub fn mcs_action(state: &State) -> u16 {
    let mut best_action = 0;
    let mut best_score = f64::MIN;
    let legal_actions = state.legal_actions();
    let simulation_count = MCS_SIMULATION_COUNT/legal_actions.len();
    for action in state.legal_actions() {
        let mut score = 0.0;
        for _ in 0..simulation_count {
            score += -State::playout(&state.next(action));
        }
        if score > best_score {
            best_action = action;
            best_score = score;
        }
    }
    best_action
}

モンテカルロ木探索

モンテカルロ探索ではランダムに手を選んでいるため、あまり現実的ではない手についても同じ回数探索が行われていました。 モンテカルロ木探索ではプレイアウトを繰り返す中で、よく選ばれる手に関してシミュレート回数を増やすことで、比較的勝ちやすい手を探せるように修正します。

基本的にはモンテカルロ探索同様にプレイアウトを行いますが、プレイアウト回数が既定値(下記ソースでは EXPAND_THRESHOLD = 10)を越えたノードについては子ノードを作成して、プレイアウトではなく子ノードのUCB1値が最大である(比較的勝率が高いor比較的探索回数が少ない)ものを選びます。

図で書くと点線部分がプレイアウトとしてこのような木構造を持ちながらゲームを探索することになります。

f:id:matsu7874:20211215033233p:plain
モンテカルロ木探索のイメージ図

const EXPAND_THRESHOLD: usize = 10;
const MCTS_SIMULATION_COUNT: usize = 1000;
struct Node {
    state: State,
    w: f64,
    n: usize,
    child_nodes: Vec<Node>,
}
impl Node {
    fn new(state: State) -> Self {
        Node {
            state,
            w: 0.0,
            n: 0,
            child_nodes: vec![],
        }
    }
    fn evaluate(&mut self) -> f64 {
        if self.state.is_done() {
            let value = if self.state.is_lose() { -1.0 } else { 0.0 };
            self.w += value;
            self.n += 1;
            value
        } else if self.child_nodes.is_empty() {
            let value = State::playout(&self.state);
            self.w += value;
            self.n += 1;
            if self.n == EXPAND_THRESHOLD {
                self.expand();
            }
            value
        } else {
            let next_node_index = self.next_child_node_index();
            let value = -self.child_nodes[next_node_index].evaluate();
            self.w += value;
            self.n += 1;
            value
        }
    }
    fn expand(&mut self) {
        let legal_actions = self.state.legal_actions();
        for action in legal_actions {
            self.child_nodes.push(Node::new(self.state.next(action)));
        }
    }
    fn next_child_node_index(&self) -> usize {
        for i in 0..self.child_nodes.len() {
            if self.child_nodes[i].n == 0 {
                return i;
            }
        }
        let mut t = 0;
        for c in self.child_nodes.iter() {
            t += c.n;
        }
        let mut max_value = f64::MIN;
        let mut best_node = 0;
        for i in 0..self.child_nodes.len() {
            let ucb1 = self.child_nodes[i].ucb1_value(t);
            if ucb1 > max_value {
                max_value = ucb1;
                best_node = i;
            }
        }
        best_node
    }
    pub fn ucb1_value(&self, total: usize) -> f64 {
        if self.n == 0 {
            f64::MAX
        } else {
            -self.w / self.n as f64 + (2.0 * (total as f64).ln() / self.n as f64).sqrt()
        }
    }
}
pub fn mcts_action(state: &State) -> u16 {
    let mut root_node = Node::new(state.clone());
    root_node.expand();

    for _ in 0..MCTS_SIMULATION_COUNT {
        root_node.evaluate();
    }

    // legal_actionsが常に同じ順番でactionを返すことを期待している。
    let mut best_action = 0;
    let mut best_score = usize::MIN;
    let legal_actions = state.legal_actions();
    for i in 0..legal_actions.len() {
        let score = root_node.child_nodes[i].n;
        if score > best_score {
            best_action = legal_actions[i];
            best_score = score;
        }
    }
    best_action
}

まとめ

以上、全探索と枝刈りによる高速化・ランダム・原始的なモンテカルロ探索・モンテカルロ木探索の実装方法を紹介しました。 ゲームAIに興味を持ってくださった方は こちらのCodinGameというサイト でゲームAIを作る常設のコンテストが開催されていますので、ぜひご参加してみてください。とても楽しいです。

参考文献