はじめに
RPGにおいて、モンスターのパラメータは、重要な要素の一つです。モンスターが強すぎるとゲームが過度に困難になり、弱すぎると退屈になる恐れがあります。楽しさと達成感をバランス良く保つためには、モンスターパラメータの調整が鍵となります。
このモンスターパラメータの調整は、修正とテストプレイを繰り返し、"いい感じ"の値を見つける作業です。例えば、攻撃力を上げてテスト、HPを減らしてテストなど。これらをすべて手作業で行うのは非常に大変なので、何らかテクニックがほしいところです。
そこで本稿では、RPGのバトルシステムを模倣し、 遺伝的アルゴリズム(Genetic Algorithm, GA) を使ってモンスターのパラメータを求めてみます。
実装は実行速度が速いRustを使います。また、Pythonでも実装し、実行時間を比較した結果を最後に載せます。
遺伝的アルゴリズムとは
遺伝的アルゴリズムは、自然の進化のプロセスに基づいた最適化アルゴリズムです。主なプロセスには、選択、交叉、突然変異があり、これらのプロセスを繰り返すことで、最終的に最適解を見つけます。
以下はGAの基本的なプロセスです。
- 初期化: 解の集合(個体群)をランダムに生成
- 評価: 各個体の適合度を評価する関数を使用して各個体を評価
- 選択: 適合度に基づいて、次の世代に進む個体を選択
- 交叉: 選択された個体間で情報を交換し、新しい個体を生成
- 突然変異: 確率で個体の一部をランダムに変更
- 終了条件の確認: 指定された世代数や適合度の閾値に到達したら終了。そうでなければ、ステップ2に戻る
イメージ的には、
- 探索空間にランダムに個体をばらまく(このとき、各個体はどこに最適解があるか知らない)
- 個体群は情報をアップデートしながら、徐々に最適解へ近づいていく
- 最終的に最適解に収束する
という感じです。
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との相性は良いと考えています。