Go to Qiita Advent Calendar 2024 Top
LoginSignup
10
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

RustAdvent Calendar 2023

Day 15
@hituziando

Rustで遺伝的アルゴリズム。モンスターのパラメータを求めてみよう

Last updated at Posted at 2023-12-14

はじめに

RPGにおいて、モンスターのパラメータは、重要な要素の一つです。モンスターが強すぎるとゲームが過度に困難になり、弱すぎると退屈になる恐れがあります。楽しさと達成感をバランス良く保つためには、モンスターパラメータの調整が鍵となります。

このモンスターパラメータの調整は、修正とテストプレイを繰り返し、"いい感じ"の値を見つける作業です。例えば、攻撃力を上げてテスト、HPを減らしてテストなど。これらをすべて手作業で行うのは非常に大変なので、何らかのテクニックがほしいところです。

そこで本稿では、RPGのバトルシステムを模倣し、 遺伝的アルゴリズム(Genetic Algorithm, GA) を使ってモンスターのパラメータを求めてみます。

実装は実行速度が速いRustを使います。また、Pythonでも実装し、実行時間を比較した結果を最後に載せます。

遺伝的アルゴリズムとは

遺伝的アルゴリズムは、自然の進化のプロセスに基づいた最適化アルゴリズムです。主なプロセスには、選択、交叉、突然変異があり、これらのプロセスを繰り返すことで、最終的に最適解を見つけます。

以下はGAの基本的なプロセスです。

  1. 初期化: 解の集合(個体群)をランダムに生成
  2. 評価: 各個体の適合度を評価する関数を使用して各個体を評価
  3. 選択: 適合度に基づいて、次の世代に進む個体を選択
  4. 交叉: 選択された個体間で情報を交換し、新しい個体を生成
  5. 突然変異: 確率で個体の一部をランダムに変更
  6. 終了条件の確認: 指定された世代数や適合度の閾値に到達したら終了。そうでなければ、ステップ2に戻る

イメージ的には、

  1. 探索空間にランダムに個体をばらまく(このとき、各個体はどこに最適解があるか知らない)
  2. 個体群は情報をアップデートしながら、徐々に最適解へ近づいていく
  3. 最終的に最適解に収束する

という感じです。

GA.png

GAについて詳しく知りたい方は、ぜひ調べてみてください。

モンスターパラメータとバトルシステム

モンスターパラメータの定義

本稿で扱うモンスターパラメータの定義は以下の通りです。

(max_hp, atk, def, luc, speed)
  • max_hp: 最大HP
  • atk: 攻撃力
  • def: 防御力
  • luc: 運。クリティカルヒットが発生する確率
  • speed: スピード。高いほど先に行動できる

GAで、これらの値の最適な組み合わせを求めます。

バトルシステムの仕様

本稿で実装するバトルシステムは以下の通りです。

  • プレイヤーとモンスターの1対1のバトル
  • ターン制。speedが高い方が先に行動する
  • 行動は「攻撃」の一択のみ
  • 攻撃は必ず当たる
  • 攻撃された側はダメージを計算し(後述)、残りHPから引く
  • 勝敗の条件
    • プレイヤーの残りHPが先に0になると敗北
    • モンスターの残りHPを先に0にできれば勝利
  • 属性・弱点などの要素は一切なし

要はどちらかが倒れるまで、交互に殴り合うシステムです!

ゲームとしては、属性や魔法など他の要素がもっとある方が楽しいですが、今回は問題を単純にするために仕様を絞っています。

ダメージ計算式

ダメージは以下の式で計算します。

// `attacker` は攻撃するキャラ、 `defender` は攻撃されるキャラを表します
let mut damage = attacker.atk - defender.def * 0.5;

// クリティカルヒットのときは更に与ダメージ2倍
if is_critical {
    damage = damage * 2.0;
}

damage = max(damage.floor(), 0);

適合度関数の設計

適合度関数とは、個体の適合度を評価するために用いる関数です。
本稿で扱う問題において、適合度は以下の式で計算します。

// 残りHPの割合
// `character` はプレイヤーキャラを表します
let hp_ratio = character.hp as f32 / character.max_hp as f32;

// 適合度
// `result` はバトルの結果、 `turn` は勝敗がつくまでに経過したターン数を表します
let score = if result == BattleResult::GameOver {
    WORST_SCORE
} else if result == BattleResult::Draw {
    WORST_SCORE - 1.0
} else if turn < TURN_MIN {
    WORST_SCORE - 1.0
} else {
    hp_ratio
};

この適合度関数は、適合度が小さいほど優良で、次の思想を反映しています。

  • "なんとか勝てた感"を演出するために、プレイヤーの残りHPが少ないほど適合度が良くなるようにします。つまり、HP=1のときが最良です
  • HP=0のときは敗北(GameOver)のため、最悪値( WORST_SCORE )をセットします。 WORST_SCORE は問題の設定上、十分に大きい適当な値です
  • 両者ともに防御が固く、ダメージが全く通らない状態になると、勝敗がつかず無限ループに陥ってしまうため、ターン数に上限を設けます。上限に達しても勝敗がつかない場合は引き分け(Draw)となり、 WORST_SCORE - 1 をセットします
  • ワンパンで倒せてしまうと少々味気ないため、ターン数に下限( TURN_MIN )を設け、何度か攻撃の応酬があるようにします。下限未満の場合も WORST_SCORE - 1 をセットします

実装

ソースコード全体はGitHubにアップしています。

最初にモンスターパラメータを定義します。

main.rs
#[derive(Clone, Copy, Serialize, Deserialize, Debug)]
struct Status {
    max_hp: i32,
    atk: i32,
    def: i32,
    luc: i32,
    speed: i32,
}

GAの設定値は、試行を何度も繰り返しながらチューニングしていくため、毎回ビルドするのは面倒なので、以下のようなconfig.jsonから読み込めるようにします。

config.json
{
  "gene_num": 50,
  "selection_rate": 0.3,
  "mutation_rate": 0.005,
  "generation_max": 500000,
  "turn_min": 3,
  "turn_max": 10,
  "min_status": {
    "max_hp": 1,
    "atk": 1,
    "def": 0,
    "luc": 0,
    "speed": 1
  },
  "max_status": {
    "max_hp": 1000,
    "atk": 1000,
    "def": 1000,
    "luc": 10,
    "speed": 255
  },
  "character_status": {
    "max_hp": 200,
    "atk": 15,
    "def": 10,
    "luc": 0,
    "speed": 10
  }
}

config.jsonに対応するConfig構造体を実装します。

main.rs
#[derive(Clone, Serialize, Deserialize, Debug)]
struct Config {
    /// 個体数
    gene_num: i32,
    /// 選択率(0~1.0)
    selection_rate: f32,
    /// 突然変異率(0~1.0)
    mutation_rate: f32,
    /// 最大世代数
    generation_max: i32,
    /// 最小ターン数
    turn_min: i32,
    /// 最大ターン数
    turn_max: i32,
    /// モンスターパラメータの取り得る範囲(下限)
    min_status: Status,
    /// モンスターパラメータの取り得る範囲（上限)
    max_status: Status,
    /// プレイヤーキャラのステータス
    character_status: Status,
}

impl Config {
    fn read_from_json() -> Self {
        let content = fs::read_to_string("config.json")
            .expect("Failed to load config.json");
        serde_json::from_str(&content).unwrap()
    }
}

個体を表すGene構造体を実装します。

main.rs
type Fitness = f32;

const WORST_SCORE: Fitness = 1_000_000.0;

type GeneParams = Status;

#[derive(Clone, Copy, Debug)]
struct Gene {
    /// ID
    id: Uuid,
    /// 適合度
    fitness: Fitness,
    /// パラメータ
    params: GeneParams,
}

impl Gene {
    fn new(params: GeneParams) -> Self {
        Gene {
            id: Uuid::new_v4(),
            fitness: WORST_SCORE,
            params,
        }
    }
}

次にGAを実装します。

GAの選択方法には、ルーレット選択などいくつかありますが、今回は実装が簡単なエリート選択を使います。エリート選択は適合度の良い順に、個体を次世代へ引き継がせる方法です。ここでは、個体数( gene_num )に選択率( selection_rate )を掛けた個数だけ選択するようにしています。

交叉方法もいくつかやり方があるのですが、今回は一様交叉を使います。一様交叉は、各フィールドごとに50%の確率で親1と親2の値を入れ替えます。

突然変異も色々やり方があるのですが、今回は各フィールドごとに突然変異率( mutation_rate )の確率でランダムな値をセットするようにしています。

この実装では、終了条件は世代数が上限( generation_max )に達したとき、終了するようにしています。

GAのコード
main.rs
struct GeneticAlgorithm {
    config: Config,
    genes: Vec<Gene>,
}

impl GeneticAlgorithm {
    fn new(config: Config) -> Self {
        let genes: Vec<Gene> = vec![];
        GeneticAlgorithm {
            config,
            genes,
        }
    }

    /// 次世代に残す個体の数を返します
    fn selection_num(&self) -> usize {
        (self.config.gene_num as f32 * self.config.selection_rate).floor() as usize
    }

    /// ベストスコアを返します
    fn best_score(&self) -> Fitness {
        self.genes[0].fitness
    }

    /// 先頭から指定個数分の個体を返します
    fn head(&self, num: usize) -> Vec<Gene> {
        (&self.genes[..num]).to_vec()
    }

    /// ランダムで選ばれた1つの個体を返します
    fn sample(&self) -> Gene {
        let mut rng = rand::thread_rng();
        let idx = Uniform::from(0..self.genes.len());
        self.genes[idx.sample(&mut rng)].clone()
    }

    /// アルゴリズムを実行します
    fn exec(&mut self) {
        let gene_num = self.config.gene_num as usize;

        // 次世代に残す個体の数
        let selection_num = self.selection_num();

        // 初期世代の生成
        for _ in 0..gene_num {
            self.genes.push(self.generate());
        }

        let ff = FitnessFunc::new(self.config.clone());

        // 適合度計算
        for gene in self.genes.iter_mut() {
            gene.fitness = ff.calc(&gene.params).0;
        }

        // 現在のベストスコア
        let mut cur_best_score = WORST_SCORE;
        // 現在の世代
        let mut generation = 1;
        loop {
            // 適合度降順(優良順)にソート (優良順はfitnessの値が小さい順)
            self.genes.sort_by(|a, b| a.fitness.partial_cmp(&b.fitness).unwrap());

            let best_score = self.best_score();
            if cur_best_score != best_score {
                cur_best_score = best_score;
                println!("{}G: {}", generation, best_score);
            }

            if generation >= self.config.generation_max {
                // Finish
                break;
            }

            // 選択
            // 優良個体を次世代に残す
            let mut new_genes = self.head(selection_num);

            // 選択されなかった個数分、交叉・突然変異により生成する
            loop {
                // 両親の選択
                let parents = self.select_parents();
                // 交叉
                let children = self.crossover(&parents.0, &parents.1);

                // 子1
                // 突然変異
                let mut g1 = self.mutated(&children.0, self.config.mutation_rate);
                // 適合度計算
                g1.fitness = ff.calc(&g1.params).0;
                new_genes.push(g1);
                if new_genes.len() == gene_num {
                    break;
                }

                // 子2
                // 突然変異
                let mut g2 = self.mutated(&children.1, self.config.mutation_rate);
                // 適合度計算
                g2.fitness = ff.calc(&g2.params).0;
                new_genes.push(g2);
                if new_genes.len() == gene_num {
                    break;
                }
            }
            self.genes = new_genes;
            assert_eq!(self.genes.len(), gene_num);

            generation += 1;
        }
    }

    /// ランダムに個体を生成します
    fn generate(&self) -> Gene {
        let min = &self.config.min_status;
        let max = &self.config.max_status;
        let mut rng = rand::thread_rng();
        let hp = Uniform::from(min.max_hp..=max.max_hp);
        let atk = Uniform::from(min.atk..=max.atk);
        let def = Uniform::from(min.def..=max.def);
        let luc = Uniform::from(min.luc..=max.luc);
        let speed = Uniform::from(min.speed..=max.speed);
        let params = GeneParams {
            max_hp: hp.sample(&mut rng),
            atk: atk.sample(&mut rng),
            def: def.sample(&mut rng),
            luc: luc.sample(&mut rng),
            speed: speed.sample(&mut rng),
        };
        Gene::new(params)
    }

    /// ランダムに親を選出します
    fn select_parents(&self) -> (Gene, Gene) {
        let p1 = self.sample();
        let p2 = loop {
            let p2 = self.sample();
            if p1.id != p2.id {
                break p2;
            }
        };
        (p1, p2)
    }

    /// 親1と親2を交叉して新しい個体を生成します
    ///
    /// # Arguments
    /// * `p1` - Parent 1
    /// * `p2` - Parent 2
    fn crossover(&self, p1: &Gene, p2: &Gene) -> (Gene, Gene) {
        let mask = GeneMask::new();

        // 一様交叉
        let params1 = GeneParams {
            max_hp: if mask.max_hp { p2.params.max_hp } else { p1.params.max_hp },
            atk: if mask.atk { p2.params.atk } else { p1.params.atk },
            def: if mask.def { p2.params.def } else { p1.params.def },
            luc: if mask.luc { p2.params.luc } else { p1.params.luc },
            speed: if mask.speed { p2.params.speed } else { p1.params.speed },
        };
        let params2 = GeneParams {
            max_hp: if mask.max_hp { p1.params.max_hp } else { p2.params.max_hp },
            atk: if mask.atk { p1.params.atk } else { p2.params.atk },
            def: if mask.def { p1.params.def } else { p2.params.def },
            luc: if mask.luc { p1.params.luc } else { p2.params.luc },
            speed: if mask.speed { p1.params.speed } else { p2.params.speed },
        };
        (Gene::new(params1), Gene::new(params2))
    }

    /// 突然変異させます
    fn mutated(&self, gene: &Gene, rate: f32) -> Gene {
        let min = &self.config.min_status;
        let max = &self.config.max_status;
        let mut rng = rand::thread_rng();
        let hp = Uniform::from(min.max_hp..=max.max_hp);
        let atk = Uniform::from(min.atk..=max.atk);
        let def = Uniform::from(min.def..=max.def);
        let luc = Uniform::from(min.luc..=max.luc);
        let speed = Uniform::from(min.speed..=max.speed);
        let mut params = gene.params.clone();

        // rng.gen::<f32>() -> 0 <= p < 1.0
        if rng.gen::<f32>() <= rate {
            params.max_hp = hp.sample(&mut rng);
        }
        if rng.gen::<f32>() <= rate {
            params.atk = atk.sample(&mut rng);
        }
        if rng.gen::<f32>() <= rate {
            params.def = def.sample(&mut rng);
        }
        if rng.gen::<f32>() <= rate {
            params.luc = luc.sample(&mut rng);
        }
        if rng.gen::<f32>() <= rate {
            params.speed = speed.sample(&mut rng);
        }

        Gene::new(params)
    }
}

struct GeneMask {
    max_hp: bool,
    atk: bool,
    def: bool,
    luc: bool,
    speed: bool,
}

impl GeneMask {
    /// 各フィールドごとにランダムでtrue or falseのマスクを生成します
    fn new() -> Self {
        let mut rng = rand::thread_rng();
        GeneMask {
            max_hp: rng.gen(),
            atk: rng.gen(),
            def: rng.gen(),
            luc: rng.gen(),
            speed: rng.gen(),
        }
    }
}

最後に適合度関数の実装です。適合度関数は、バトルシステムの仕様に沿ってゴリゴリ書いていきます!

適合度関数のコード
main.rs
struct FitnessFunc {
    config: Config,
}

impl FitnessFunc {
    fn new(config: Config) -> FitnessFunc {
        FitnessFunc {
            config,
        }
    }

    pub fn calc(&self, monster_status: &Status) -> (Fitness, BattleResult) {
        // プレイヤーキャラ生成
        let mut character = Unit::character_from(&self.config.character_status);
        // モンスター生成
        let monster = Unit::monster_from(&monster_status);

        // バトル!
        let (result, turn) = battle(&mut character, monster, &self.config);

        // 残りHPの割合
        let hp_ratio = character.hp as f32 / character.max_hp as f32;

        // 適合度
        let score = if result == BattleResult::GameOver {
            WORST_SCORE
        } else if result == BattleResult::Draw {
            WORST_SCORE - 1.0
        } else if turn < self.config.turn_min {
            WORST_SCORE - 1.0
        } else {
            hp_ratio
        };

        (score, result)
    }
}

#[derive(Clone, Copy, Debug)]
struct Unit {
    id: Uuid,
    is_monster: bool,
    max_hp: i32,
    hp: i32,
    atk: i32,
    def: i32,
    luc: i32,
    speed: i32,
}

impl Unit {
    fn character_from(status: &Status) -> Unit {
        Unit {
            id: Uuid::new_v4(),
            is_monster: false,
            max_hp: status.max_hp,
            hp: status.max_hp,
            atk: status.atk,
            def: status.def,
            luc: status.luc,
            speed: status.speed,
        }
    }

    fn monster_from(status: &Status) -> Unit {
        Unit {
            id: Uuid::new_v4(),
            is_monster: true,
            max_hp: status.max_hp,
            hp: status.max_hp,
            atk: status.atk,
            def: status.def,
            luc: status.luc,
            speed: status.speed,
        }
    }
}

#[derive(PartialEq, Debug)]
enum BattleResult {
    Win,
    GameOver,
    Draw,
}

/// # Returns
/// BattleResultと終了ターン数のタプルを返します
fn battle(character: &mut Unit, monster: Unit, config: &Config) -> (BattleResult, i32) {
    let mut rng = rand::thread_rng();

    let mut units: Vec<Unit> = vec![
        character.clone(),
        monster.clone(),
    ];
    // speedが速い順にソート
    units.sort_by(|a, b| b.speed.cmp(&a.speed));

    let mut hp_map: HashMap<Uuid, i32> = HashMap::new();
    for u in units.iter() {
        hp_map.insert(u.id, u.hp);
    }

    let mut turn = 0;
    let result = loop {
        turn += 1;
        if turn > config.turn_max {
            break BattleResult::Draw;
        }

        let mut stop: Option<BattleResult> = None;

        for attacker in units.iter() {
            if *hp_map.get(&attacker.id).unwrap() <= 0 {
                // Already dead
                continue;
            }

            // 攻撃対象
            let defender = if attacker.is_monster {
                character.clone()
            } else {
                monster.clone()
            };

            let mut hp = *hp_map.get(&defender.id).unwrap();
            hp -= calc_damage(&attacker, &defender, &mut rng);
            hp = cmp::max(0, hp);
            hp_map.insert(defender.id, hp);

            if *hp_map.get(&defender.id).unwrap() <= 0 {
                if defender.is_monster {
                    stop = Some(BattleResult::Win);
                    break;
                } else {
                    stop = Some(BattleResult::GameOver);
                    break;
                }
            }
        }

        match stop {
            Some(res) => break res,
            None => {}
        };
    };

    character.hp = *hp_map.get(&character.id).unwrap();

    (result, turn)
}

fn calc_damage(attacker: &Unit, defender: &Unit, rng: &mut ThreadRng) -> i32 {
    let luc = attacker.luc as f32 / 100.0;
    let c = if rng.gen::<f32>() <= luc { 2.0 } else { 1.0 };
    let atk = attacker.atk as f32;
    let def = defender.def as f32;
    let damage = ((atk - def * 0.5) * c).floor() as i32;
    cmp::max(0, damage)
}

結果

設定値

実験で使用した各設定値は以下になります。

設定 変数名 値
個体数 gene_num 50
選択率 selection_rate 30%
突然変異率 mutation_rate 0.5%
最大世代数 generation_max 500,000
最小ターン数 turn_min 3
最大ターン数 turn_max 10
モンスターパラメータの下限 min_status { max_hp=1 atk=1 def=0 luc=0 speed=1 }
モンスターパラメータの上限 max_status { max_hp=1000 atk=1000 def=1000 luc=10 speed=255 }
プレイヤーキャラのステータス character_status { max_hp=200 atk=15 def=10 luc=0 speed=50 }

実行環境は以下になります。

値
OS macOS Sonoma 14.0
Model Name MacBook Air
Chip Apple M2
Memory 24 GB

生成されたモンスターパラメータ (出力された解)

以下はGAによって生成された解です。

fitness=0.01 { max_hp=36 atk=27 def=22 luc=6 speed=232 }

それっぽい解ですね。実際に手計算でバトルを追ってみます。プレイヤーのHPを c.hp 、モンスターのHPを m.hp とします。クリティカルヒットは一旦無視してダメージ計算します。

Turn 1
先攻: Monster
damage = floor(27 - 10 * 0.5) = 22
c.hp = 200 - damage = 178
後攻: Player
damage = floor(15 - 22 * 0.5) = 4
m.hp = 36 - damage = 32
Turn 2 (以降はHPのみ記す)
c.hp = 156
m.hp = 28
Turn 3
c.hp = 134
m.hp = 24
Turn 4
c.hp = 112
m.hp = 20
Turn 5
c.hp = 90
m.hp = 16
Turn 6
c.hp = 68
m.hp = 12
Turn 7
c.hp = 46
m.hp = 8
Turn 8
c.hp = 24
m.hp = 4
Turn 9
c.hp = 2
m.hp = 0

期待した通り、HPをギリギリ残した状態で勝利しました。

他の解も見てみましょう。

fitness=0.01 { max_hp=6 atk=71 def=26 luc=10 speed=52 }

HPが少なく攻撃と防御に極振りした感じのパラメータになりました。こちらも実際に手計算で確認してみます。

Turn 1
c.hp = 200 - 66 = 134
m.hp = 6 - 2 = 4
Turn 2
c.hp = 68
m.hp = 2
Turn 3
c.hp = 2
m.hp = 0

極振りパラメータでも期待した通りになりました。おもしろいですね!

世代経過の観察

プログラムではベストスコアが更新されたときに println! するようにしているので、経過を見てみましょう。

46G: 999999
15014G: 0.66
15020G: 0.575
15034G: 0.49
15072G: 0.355
15076G: 0.14
15155G: 0.1
17155G: 0.04
21816G: 0.025
29336G: 0.01

世代経過とともにベストスコアが更新、つまり解がどんどん良くなっていることがわかります。

他の試行も見てみます。

1G: 999999
250202G: 0.9
250206G: 0.88
250214G: 0.86
250219G: 0.2
250230G: 0.04
251105G: 0.01

このときは25万世代もの間、まったく進化しませんでした。GAはランダムな要素があるため、こういうこともあり得ます。このようなケースが多いときは、個体数を増やす、選択方法を変える、突然変異率を高くする、適合度関数を見直す、などの調整が必要になるかもしれません。

Pythonとの実行時間の比較

PythonコードもGitHubにアップしてあります。

以下は同じ設定値、同じ環境下で10回試行した結果です。

Rust Python
実行時間の平均値 [秒] 36.491 359.847
変動係数(CV) 0.31 0.28
実行時間の最小値 [秒] 19.969 244.065
実行時間の最大値 [秒] 57.007 602.864

Pythonの実行時間はRustの約10倍で、Rustが著しく速いという結果が得られました。また、RustとPythonの変動係数は互いに近いことから、両言語の実行時間の相対的な安定性は、ほぼ同等という結果になりました。

Pythonコードは、ほぼGPT-4を使いRustから機械的に変換したものです。そのため、実装方法によってはもっと速くなる可能性があります。

まとめ

GAは試行回数が物言う世界だと僕は思っています。(こう言うと専門家には怒られそうですが、アタリが出るまでガチャを回してる感が否めない)
何度も試行とチューニングを繰り返すため、一回に掛かる実行時間は重要です。そういう点でもRustとの相性は良いと考えています。

参考文献

  1. マッチ箱の脳 - 使える人工知能のお話
  2. 図解即戦力 機械学習&ディープラーニングのしくみと技術がこれ1冊でしっかりわかる教科書
10
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?