目的

全探索のアルゴリズムの勉強を進めていると3目並べの最善手をどうやったら出せるのか？って内容の問題がありました。
何をもってして最善手と評価するのか中々思いつかなかったのですが、ゲーム木とミニマックス法、ネガマックス法...etcなるものに出会いました。

とりあえず入門はミニマックス法ぽかったし(適当)、割とこれなら実装が行けそうだったし、理解を足すために1度実装してみようと思い、やりました。
とりあえず動くのを目指したので、自分の実装はお世辞にもあまり良くできているとは言えませんが、自分の為にもメモがてら解説記事を書くことにしました。

今回実装したコードはここにあります。
https://github.com/kahirokunn/minimax_tic_tac_toe

このコードをwasmでビルドしてcpuとして使ったマルバツゲームはここでプレイできます。
https://react-ttt.firebaseapp.com

対象読者

ここに貼った参考にした記事を読んだ方です。 (もうこの記事の意味ないっすね。。。笑完全に自分用メモです

Rustでminimax法

minimax法とは、想定される最大の損害が最小になるように決断を行う戦略のこと。
※ ちなみにマルバツゲームの場合だと先手と後手が二人共minimax法で打った場合、必ず引き分けになります。

minimax法の特徴

ちなみにminimax法は先手後手両方ともに使える手法です。
つまり、次に石を置くのが自分なら最大を取り、その次に相手が石を置くなら最悪の手を選択するので、普通に実装すれば先手後手どちらかでしか使えないようになることはありません。便利。

あと、こっちが最善手を打って、向こうも最善手を打った際に、もし向こうが勝てるパターンが1つでもそこにあればその手は打たないし、もしその様なパターンしかない場合は一番粘れる手を打つアルゴリズムです。またその中ででも、こちらが勝てるパターンがある場合は最速で勝てる手を選びます。

Rustのコード

今回用意したデータの構造はこんな感じです。
各データ構造が何を表現しているかはコメントで書きましたのでそちらを御覧ください.

// その盤面の状態を表します
#[derive(PartialEq, Clone)]
enum BoardState {
  Playing,  // プレイ中
  BlackWin, // 黒の勝ち
  WhiteWin, // 白の勝ち
  Draw,     // 引き分け
}

// 縦横斜めのラインの状態を表します
#[derive(PartialEq, Clone)]
enum LineState {
  BlackWin,
  WhiteWin,
  Playing,
  Draw,
}

// 誰のターンかを表します
#[derive(PartialEq, Clone)]
enum Turn {
  White,
  Black,
}

// 盤面とその盤面の価値を表します
struct Valuation {
  board: CrossAndKnotsBoard,
  score: i32,
}

// 盤面のマス目の上に置く石を表します
#[derive(PartialEq, Clone)]
enum Piece {
  White,
  Black,
}

// マス目を表現します
// マス目に何も置かれてなければNone, 置けれていればSome<Piece>
type Cell = Option<Piece>;

// 盤面を表現します
// cellsは3*3のマルバツゲームの盤面を1次元配列にならしたものです.
#[derive(Clone)]
struct CrossAndKnotsBoard {
  cells: Vec<Cell>,
}

// これは盤面とindexのペアを実現するために作りました.
// これはなくても良いけど、あると便利だったので.
struct WithIndex<T> {
  elem: T,
  index: usize,
}

ではこのデータ構造を使って実際にminimax法を実装して行きます.
とりあえず全部CrossAndKnotsBoardに突っ込んでいこうと思います.

impl CrossAndKnotsBoard {
  pub fn new() -> Self {
    let mut cells = vec![];
    for _ in 0..3 * 3 {
      cells.push(None);
    }
    CrossAndKnotsBoard { cells }
  }

  pub fn can_put(&self, index: usize) -> bool {
    self.cells[index] == None
  }

  pub fn put(&mut self, index: usize, piece: Piece) {
    self.cells[index] = Some(piece);
  }

  pub fn who_can_put_next_piece(&self) -> Turn {
    match self.count_blank() % 2 {
      1 => Turn::White,
      _ => Turn::Black,
    }
  }

  // 次に打つべきな最善手を取得します
  pub fn get_next_best_board(&self) -> CrossAndKnotsBoard {
    self.minimax(0).board
  }

  fn minimax(&self, depth: i32) -> Valuation {
    let boards = self.get_next_all_pattern_board(&self);
    if boards.len() == 0 {
      return self.calc_valuation(depth);
    }

    let vals: Vec<WithIndex<Valuation>> = boards
      .iter()
      .map(|board| {
        let _val = board.calc_valuation(depth);
        match _val.board.board_state() == BoardState::Playing {
          true => _val.board.minimax(depth + 1),
          false => _val,
        }
      })
      .enumerate()
      .map(|(index, elem)| WithIndex { elem, index })
      .collect();

    // minimaxの由来である
    // 次石置くのが自分なら最大を取る
    // 次石置くのが相手なら最小を取る (最小は相手が最も有利な手の為
    let val: Option<WithIndex<Valuation>> = match self.who_can_put_next_piece() {
      // 最悪の手を取る
      Turn::White => vals.into_iter().fold(None, |min, v| match &min {
        Some(WithIndex {
          elem: min_elem,
          index: _,
        }) => match v.elem.score > min_elem.score {
          true => Some(v),
          false => min,
        },
        None => Some(v),
      }),
      // 最短で勝てる手を取る
      Turn::Black => vals.into_iter().fold(None, |max, v| match &max {
        Some(WithIndex {
          elem: max_elem,
          index: _,
        }) => match v.elem.score > max_elem.score {
          true => max,
          false => Some(v),
        },
        None => Some(v),
      }),
    };
    let val_with_index = val.unwrap();
    Valuation {
      score: val_with_index.elem.score,
      board: boards[val_with_index.index].clone(),
    }
  }

  fn get_next_all_pattern_board(&self, board: &CrossAndKnotsBoard) -> Vec<CrossAndKnotsBoard> {
    if board.board_state() != BoardState::Playing {
      return Vec::new();
    }
    let mut boards = vec![];
    let piece = match board.who_can_put_next_piece() {
      Turn::Black => Piece::Black,
      Turn::White => Piece::White,
    };
    for i in 0..9 {
      if board.can_put(i) {
        let mut cloned_board = board.clone();
        cloned_board.put(i, piece.clone());
        boards.push(cloned_board);
      }
    }
    boards
  }

  // 盤面単位の評価関数
  fn calc_valuation(&self, depth: i32) -> Valuation {
    let win_score = 99;

    match self.board_state() {
      BoardState::WhiteWin => Valuation {
        board: self.clone(),
        // 勝つ場合は短いターンの方がスコアを高くする
        score: win_score - depth,
      },
      BoardState::BlackWin => Valuation {
        board: self.clone(),
        // 負ける場合は延命した方がスコアを高くする
        score: win_score * -1 + depth,
      },
      // それ以外の場合は深さをとりあえず返す。
      _ => Valuation {
        board: self.clone(),
        score: depth,
      },
    }
  }

  fn count_blank(&self) -> u8 {
    let mut count = 0;
    for cell in &self.cells {
      if let None = cell {
        count += 1;
      }
    }
    count
  }

  fn board_state(&self) -> BoardState {
    for col_num in 0..3 {
      let raw_num = col_num * 3;

      // 横向きの線
      match self.judge_for_line(
        &self.cells[raw_num],
        &self.cells[raw_num + 1],
        &self.cells[raw_num + 2],
      ) {
        LineState::BlackWin => return BoardState::BlackWin,
        LineState::WhiteWin => return BoardState::WhiteWin,
        _ => (),
      };

      // 縦向きの線
      match self.judge_for_line(
        &self.cells[col_num],
        &self.cells[col_num + 3],
        &self.cells[col_num + 6],
      ) {
        LineState::BlackWin => return BoardState::BlackWin,
        LineState::WhiteWin => return BoardState::WhiteWin,
        _ => (),
      };
    }
    // 左上から右下にかける線
    match self.judge_for_line(&self.cells[0], &self.cells[4], &self.cells[8]) {
      LineState::BlackWin => return BoardState::BlackWin,
      LineState::WhiteWin => return BoardState::WhiteWin,
      _ => (),
    };
    // 右上から左下にかける線
    match self.judge_for_line(&self.cells[2], &self.cells[4], &self.cells[6]) {
      LineState::BlackWin => return BoardState::BlackWin,
      LineState::WhiteWin => return BoardState::WhiteWin,
      _ => (),
    };
    // 全ての勝利パターンに該当せず、ここまですり抜けてきた
    // 何も置かれていないマスがあったらプレイ中
    for cell in &self.cells {
      if let None = cell {
        return BoardState::Playing;
      }
    }
    // 引き分け
    BoardState::Draw
  }

  // ラインの為の評価関数
  fn judge_for_line(&self, a: &Option<Piece>, b: &Option<Piece>, c: &Option<Piece>) -> LineState {
    if a.is_none() || b.is_none() || c.is_none() {
      return LineState::Playing;
    }

    match a == b && b == c {
      true => match a {
        Some(Piece::White) => LineState::WhiteWin,
        Some(Piece::Black) => LineState::BlackWin,
        // ありえないケース
        None => LineState::Playing,
      },
      false => LineState::Draw,
    }
  }
}

calc_valuation

上に既に登場していますが、再度ここに貼ります。
このメソッドがminimax法で言われている評価関数です.
ここで出て来るdepthは何層目の再起なのかを表せます。つまり、起点となる盤面から何手目の盤面かって事です。
勝った場合は99点 - 手数、負けた場合は-99点 + 延命した手数、引き分けの場合はゲームを長引かせただけの手数を点数にします。
ちなみにこの手数を計算に入れないと全く良いゲームにならないです。
自分は最初の実装の時、手数を計算に入れ忘れたのですが、その場合次の手で勝てるのに、他の手でも勝てる場合、どちらの手をうつかはどちらが先にmax_valに来るか依存になってました。
あれはめちゃくちゃ弱かったです。。。
絶対深さを計算に入れましょう。。。！minimaxは深さの評価必須です！

  // 盤面単位の評価関数
  fn calc_valuation(&self, depth: i32) -> Valuation {
    let win_score = 99;

    match self.board_state() {
      BoardState::WhiteWin => Valuation {
        board: self.clone(),
        // 勝つ場合は短いターンの方がスコアを高くする
        score: win_score - depth,
      },
      BoardState::BlackWin => Valuation {
        board: self.clone(),
        // 負ける場合は延命した方がスコアを高くする
        score: win_score * -1 + depth,
      },
      // それ以外の場合は深さをとりあえず返す。
      _ => Valuation {
        board: self.clone(),
        score: depth,
      },
    }
  }

色んな人がもっと少ない行数でスマートに評価関数を書いてるのも見ましたが、マルバツゲームは大した数の勝利条件もないし、私みたいな段階の人は丁寧に1ラインずつ書いていくのが良いと思います。

get_next_all_pattern_board

get_next_all_pattern_boardメソッドは今の盤面の次に打てる全ての盤面の配列を返してくれます。 (これがあると便利
ちなみに与えられた盤面が既にゲーム終了だった場合は空配列を返します.

  fn get_next_all_pattern_board(&self, board: &CrossAndKnotsBoard) -> Vec<CrossAndKnotsBoard> {
    if board.board_state() != BoardState::Playing {
      return Vec::new();
    }
    let mut boards = vec![];
    let piece = match board.who_can_put_next_piece() {
      Turn::Black => Piece::Black,
      Turn::White => Piece::White,
    };
    for i in 0..9 {
      if board.can_put(i) {
        let mut cloned_board = board.clone();
        cloned_board.put(i, piece.clone());
        boards.push(cloned_board);
      }
    }
    boards
  }

minimax

minimaxメソッドは今の盤面を与えたらminimax法に従った最適な次に打つべきな手を教えてくれます。
今回に打つべき手を表すデータではなく、次に打つべき盤面を返すようにしました。

  fn minimax(&self, depth: i32) -> Valuation {
    let boards = self.get_next_all_pattern_board(&self);
    if boards.len() == 0 {
      return self.calc_valuation(depth);
    }

    let vals: Vec<WithIndex<Valuation>> = boards
      .iter()
      .map(|board| {
        let _val = board.calc_valuation(depth);
        match _val.board.board_state() == BoardState::Playing {
          true => _val.board.minimax(depth + 1),
          false => _val,
        }
      })
      .enumerate()
      .map(|(index, elem)| WithIndex { elem, index })
      .collect();

    // minimaxの由来である
    // 次石置くのが自分なら最大を取る
    // 次石置くのが相手なら最小を取る (最小は相手が最も有利な手の為
    let val: Option<WithIndex<Valuation>> = match self.who_can_put_next_piece() {
      // 最悪の手を取る
      Turn::White => vals.into_iter().fold(None, |min, v| match &min {
        Some(WithIndex {
          elem: min_elem,
          index: _,
        }) => match v.elem.score > min_elem.score {
          true => Some(v),
          false => min,
        },
        None => Some(v),
      }),
      // 最短で勝てる手を取る
      Turn::Black => vals.into_iter().fold(None, |max, v| match &max {
        Some(WithIndex {
          elem: max_elem,
          index: _,
        }) => match v.elem.score > max_elem.score {
          true => max,
          false => Some(v),
        },
        None => Some(v),
      }),
    };
    let val_with_index = val.unwrap();
    Valuation {
      score: val_with_index.elem.score,
      board: boards[val_with_index.index].clone(),
    }
  }

まずは与えられた盤面を起点として、最適な手を探していきます。
まずは get_next_all_pattern_board メソッドを使って次に打てる全ての手を取得します。
そして、その時の盤面がゲーム終了していたら、その盤面の評価値を取得します。ゲームに勝ってれば99+深さ、負けていれば-99+深さ、引き分けなら深さがポイントです。
もしゲームが終了しない一手があった場合は、その一手をminimax関数に与えて、その一手の点数を計算してもらいます。※1
そして、その結果得られた vals の中から白の手番(先手, 又は○)なら最大の要素を、黒の手番なら最低の要素を取り出し、それの要素番号と対応するboard要素をboards変数から返します。

※1 つまり、その一手もまたゲームが終了していない一手だったら更にminimaxに与えられて、、、って再帰的になります。

今回は再帰の終わりがゲーム終了なので比較的条件分木が書きやすくて思考もしやすかった気がします。
そうすると再帰的に次の一手、その次の一手、その次の一手と計算されていき、必ずゲームが終了している状態の点数を取得できます。
その点数を元に、自分が次の一手を打つなら最も得点が高い手を選び、相手が次の一手を打つなら、自分にとって最悪な手、つまり最も点数が低い手を選んでいきます。そうすることにより、互いに最善手を打った際に、被害が最小に抑えられた手を探す事ができます。
しかもマルバツゲームは計算量が残りの開いてるマス目の数をNとした場合、O(N!)で、最大のNが9で9! = 362880通り、そこから途中でゲームが終わるパターン数を引く数なのでこの辺の心配がいらないのも良いなと。

※余談: 再起の考え方はフィボナッチ数列等の、漸化式のコードに似てるなって思いました。

さいごに

マルバツゲームはまだ簡単ですが、将棋とか盤面がめっちゃできかい奴や動きのパターンが多い奴、特殊条件付きのゲーム等の実装は大分めんどくさそうですね。。。って思いました。

雑なまとめになりましたが、詳しく解説している記事が沢山あるのでこんなもので良いかなと。 (編集リクエスト大歓迎です！
もし何かわからない事がありましたら言っていただけたらと思います。