📚

thunder本をRustで実装する(4章)

2025/01/16に公開

概要

先日、「ゲームで学ぶ探索アルゴリズム実践入門~木探索とメタヒューリスティクス」(通称「thunder本」)の3章をRustで実装した記事を書きました。今回は同書4章をRustで実装します。実装の中で書籍のC++コードとは一部処理が異なりますが、アルゴリズムの中核となるロジックはほぼ同等の内容になっているかと思います。

thunder本4章に登場するアルゴリズム概要

4章では、「文脈のない」一人ゲームを題材として、「山登り法」「焼きなまし法」といったメタヒューリスティックスアルゴリズムが紹介されています。

これらのアルゴリズムは、厳密に最適解を探す場合に膨大な計算時間がかかりすぎる状況で、より短時間に「そこそこ良い解」を見つけるのに有効です。

  • 山登り法は現状の「近傍」でより評価が高いものに遷移し続ける戦略を取ります。局所最適解に素早く到達しやすい一方、そこにハマって抜け出せない場合があります。
  • 焼きなまし法は、確率的に「悪い解」への遷移を受け入れることで局所解からの脱出を図るアルゴリズムです。初期段階では「悪い解」を受け入れる確率を高めに設定し、後半にかけてその確率を徐々に下げることで、大域的な探索を行いつつ最終的に良い解へ収束させることを目指します。

焼きなまし法で、「悪い解」の受け入れ確率は、以下の式で表されることが多いです。

p = \exp\!\Bigl(\frac{\Delta E}{T}\Bigr).

ここで、\Delta E = E_{\text{new}} - E_{\text{current}} は評価関数(スコア)の変化量、Tは「温度パラメータ」と呼ばれます。

実装

まず、盤面の状況を保持する構造体です。

auto_move_maze_state.rs
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};

#[derive(Clone, Eq, PartialEq)]
pub struct Coord {
    pub x: usize,
    pub y: usize,
}

const H: usize = 5;
const W: usize = 5;
const END_TURN: i32 = 5;
const CHARACTER_N: usize = 3;

#[derive(Clone, Eq, PartialEq)]
pub struct AutoMoveMazeState {
    points: Vec<Vec<i32>>,
    turn: i32,
    pub characters: Vec<Coord>,
    pub evaluated_score: i32,
    pub game_score: i64,
}

impl AutoMoveMazeState {
    const DX: [isize; 4] = [1, -1, 0, 0];
    const DY: [isize; 4] = [0, 0, 1, -1];

    pub fn new(seed: u64) -> Self {
        let mut rng = StdRng::seed_from_u64(seed);
        let mut points = vec![vec![0; W]; H];
        for y in 0..H {
            for x in 0..W {
                points[y][x] = rng.gen_range(1..=9);
            }
        }
        Self {
            points,
            turn: 0,
            characters: vec![Coord { x: 0, y: 0 }; CHARACTER_N],
            evaluated_score: 0,
            game_score: 0,
        }
    }

    pub fn init(&mut self, seed: u64) {
        let mut rng = StdRng::seed_from_u64(seed);

        for character in self.characters.iter_mut() {
            character.y = rng.gen_range(0..H);
            character.x = rng.gen_range(0..W);
        }
    }

    pub fn transition(&mut self) {
        let mut rng = rand::thread_rng();
        let target = &mut self.characters[rng.gen_range(0..CHARACTER_N)];
        target.y = rng.gen_range(0..H);
        target.x = rng.gen_range(0..W);
    }

    pub fn set_character(&mut self, character_id: usize, y: usize, x: usize) {
        if character_id < self.characters.len() {
            self.characters[character_id].y = y;
            self.characters[character_id].x = x;
        }
    }

    pub fn is_done(&self) -> bool {
        self.turn == END_TURN
    }

    fn move_player(&mut self, character_id: usize) {
        let (current_y, current_x) = {
            let ch = &self.characters[character_id];
            (ch.y, ch.x)
        };
        let mut best_point = i32::MIN;
        let mut best_action_index = 0;

        for action in 0..4 {
            let ny = current_y as isize + Self::DY[action];
            let nx = current_x as isize + Self::DX[action];
            if ny >= 0 && ny < H as isize && nx >= 0 && nx < W as isize {
                let point = self.points[ny as usize][nx as usize];
                if point > best_point {
                    best_point = point;
                    best_action_index = action;
                }
            }
        }
        self.characters[character_id].y =
            (current_y as isize + Self::DY[best_action_index]) as usize;
        self.characters[character_id].x =
            (current_x as isize + Self::DX[best_action_index]) as usize;
    }

    pub fn advance(&mut self) {
        for character_id in 0..CHARACTER_N {
            self.move_player(character_id);
        }
        for ch in &self.characters {
            let point = &mut self.points[ch.y][ch.x];
            self.game_score += *point as i64;
            *point = 0;
        }
        self.turn += 1;
    }

    pub fn to_string(&self) -> String {
        let mut result = format!("turn:\t{}\nscore:\t{}\n", self.turn, self.game_score);
        for y in 0..H {
            for x in 0..W {
                let mut found_char = false;
                for ch in &self.characters {
                    if ch.y == y && ch.x == x {
                        result.push('@');
                        found_char = true;
                        break;
                    }
                }
                if !found_char {
                    let p = self.points[y][x];
                    if p > 0 {
                        result.push_str(&p.to_string());
                    } else {
                        result.push('.');
                    }
                }
            }
            result.push('\n');
        }
        result
    }

    pub fn get_score(&self, is_print: bool) -> i64 {
        let mut tmp = self.clone();
        for ch in &tmp.characters {
            tmp.points[ch.y][ch.x] = 0;
        }
        while !tmp.is_done() {
            tmp.advance();
            if is_print {
                println!("{}", tmp.to_string());
            }
        }
        tmp.game_score
    }
}

pub fn random_action(mut state: AutoMoveMazeState, seed: u64) -> AutoMoveMazeState {
    let mut rng = StdRng::seed_from_u64(seed);
    for character_id in 0..CHARACTER_N {
        let y = rng.gen_range(0..H);
        let x = rng.gen_range(0..W);
        state.set_character(character_id, y, x);
    }
    state
}

type AIFunction = fn(AutoMoveMazeState, u64) -> AutoMoveMazeState;
pub type StringAIPair = (&'static str, AIFunction);

#[allow(dead_code)]
pub fn play_game(ai: StringAIPair, seed: u64) {
    let mut state = AutoMoveMazeState::new(seed);
    state = (ai.1)(state, seed);

    println!("{}", state.to_string());
    let score = state.get_score(true);
    println!("Score of {}: {}", ai.0, score);
}

次に、山登り法の実装です。

hill_climb.rs
use crate::auto_move_maze_state::AutoMoveMazeState;

const NUMBER: i32 = 10000;

pub fn hill_climb(state: AutoMoveMazeState, seed: u64) -> AutoMoveMazeState {
    let mut now_state = state.clone();
    now_state.init(seed);
    let mut best_score = now_state.get_score(false);

    for _ in 0..NUMBER {
        let mut next_state = now_state.clone();
        next_state.transition();
        let next_score = next_state.get_score(false);

        if next_score > best_score {
            best_score = next_score;
            now_state = next_state;
        }
    }

    now_state
}

続いて、焼きなまし法の実装です。

simulated_annealing.rs
use crate::auto_move_maze_state::AutoMoveMazeState;
use rand::{thread_rng, Rng};

const NUMBER: i32 = 10000;
const START_TEMP: f64 = 500.0;
const END_TEMP: f64 = 10.0;

pub fn simulated_annealing(state: AutoMoveMazeState, seed: u64) -> AutoMoveMazeState {
    let mut now_state = state.clone();
    now_state.init(seed);
    let mut best_score = now_state.get_score(false);
    let mut now_score = best_score;
    let mut best_state = now_state.clone();

    let mut rng = thread_rng();

    for i in 0..NUMBER {
        let mut next_state = now_state.clone();
        next_state.transition();
        let next_score = next_state.get_score(false);
        let temp = START_TEMP + (END_TEMP - START_TEMP) * (i as f64 / NUMBER as f64);
        let probability = f64::exp(((next_score as f64) - (now_score as f64)) / temp);
        let is_force_next = probability > rng.gen_range(0.0..1.0);

        if next_score > now_score || is_force_next {
            now_score = next_score;
            now_state = next_state.clone();
        }

        if next_score > best_score {
            best_score = next_score;
            best_state = next_state;
        }
    }
    best_state
}

最後に、各方法を複数回実行してスコアを比較する処理と、メイン関数を示します。

test_score.rs
use crate::auto_move_maze_state::{AutoMoveMazeState, StringAIPair};
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};

pub fn test_ai_score(ai: StringAIPair, game_number: i32) {
    let mut mt_for_construct = StdRng::seed_from_u64(0);
    let mut score_sum = 0.0;

    for _ in 0..game_number {
        let seed = mt_for_construct.gen::<u64>();
        let mut state = AutoMoveMazeState::new(seed);
        state = (ai.1)(state, seed);
        let score = state.get_score(false);
        score_sum += score as f64;
    }

    let score_mean = score_sum / game_number as f64;
    println!("Score of {}:\t{}", ai.0, score_mean);
}
main.rs
mod auto_move_maze_state;
mod hill_climb;
mod simulated_annealing;
mod test_score;

use crate::auto_move_maze_state::{random_action, StringAIPair};
use crate::hill_climb::hill_climb;
use crate::simulated_annealing::simulated_annealing;
use crate::test_score::test_ai_score;

fn main() {
    let ai: StringAIPair = ("randomAction", random_action);
    test_ai_score(ai, 100);

    let ai2: StringAIPair = ("hillClimbAction", hill_climb);
    test_ai_score(ai2, 100);

    let ai3: StringAIPair = ("simulatedAnnealingAction", simulated_annealing);
    test_ai_score(ai3, 100);
}

Next to do

  • AHCに備えて、関連性の高い7章を近日中に実装する予定です。
  • 5章、6章については CodinGame に参戦前に実装したいと考えていますが、時期は未定です。

Discussion