こんにちは。オインクゲームズの新藤です。

先日、弊社のデジタルゲーム第二弾となる「OLYM」がリリースされました。OLYM はターン制限のあるパズルゲームで、各ステージごとに決められたターン数が設けられてています。このターン数以内に目標を達成できないと、クリア失敗になってしまいます。そのため、このターン数をどう決めるかが、難易度に大きく影響する一因となっています。OLYM では、ステージごとのターン数を決定するのに遺伝的アルゴリズムを活用したので、今日はそれをご紹介します。

最終的にやったことは非常にシンプルです。端的に言えば、AI に実際にパズル解かせて、何手で解けたかをレベルデザインの参考にするということです。この AI を作る際に、遺伝的アルゴリズムを活用しました。そもそもは「自動でパズル解いてくれる AI がいたら面白いよね」程度の話だったと思うのですが、思いの外うまくいきました。

戦略としては次の通りです。全ステージ共通で使える優秀な AI を作るのは茨の道だと感じたので早々に諦めて、各ステージごとに学習させることにしました。

1. 遺伝子を50 個生成
2. 遺伝子を元にパズルを解かせる
3. 結果によってスコア付け
4. スコアが高い遺伝子ほど次の手順で選ばれやすいよう重み付け
5. 60% の確率で交配、5% の確率で突然変異、35% の確率でコピーして次の世代を作る
6. 以上を 1 世代として 30 世代まで進化させる

まず遺伝子ですが、ここも割り切っていて、盤面の状況を見るというようなことは全く考慮していません。どのようにしているかというと、100手分の行動データをランダムに生成して、それを遺伝子としています。行動データとは、「スタック可能な候補のうち N 番目をスタックする」とか「UP をする」とか (「とか」と言いましたがこれで全て) です。単純な配列のデータとなります。これを 50 個分生成し、最初の遺伝子とします。

生成された遺伝子を元に、パズルを解かせます。これはもう単純に、行動データ (遺伝子) に従って行動するだけです。OLYM のアプリケーションコードの 90% 以上は Lua で書かれており、かつ、モデルとビューも綺麗に分離されているので、この遺伝子データを元に機械的な入力情報をモデルのコントローラに対して送る Lua スクリプトを作成し、コマンドライン上の clua で動くようにしました。次のような感じのコードです。

local act = gene[cp]
if act ~= nil then
  -- Stack
  if #candidates > 0 and act[1] == 1 then
    cp = cp + 1
    local p = choice(candidates, act[2])
    c:stack(p.x, p.y)
    return
  end
  -- Up
  if act[1] == 0 then
    cp = cp + 1
    c:up()
    return
  end
end

これを動作させると、クリアできたかどうかや、残りターン数や、達成した目標の数などが標準出力に吐かれるので、それを拾ってスコア付けをします。スコア付けの方針としては、

• クリアできた
• 残りターン数が多い
• 達成できた目標が多い

ぐらいの順序で重み付けして数値化することで、それとなく良い感じになりました。このスコアを元に、10点、30点、50点の遺伝子が、次の手順の抽選で 10:30:50 の比率で選ばれるよう重み付けをしておきます。これによって、優秀な遺伝子ほど子孫を残しやすくなります。

最後に、次の世代を作る作業です。「交配」は、重み付けに従って抽選された二つの遺伝子 (これはデータ的には配列だということを思い出してください) の、各要素を 50% の確率で入れ替えて、その二つの遺伝子を次の世代に残します。「突然変異」は、重み付けに従って抽選された一つの遺伝子の、各要素を 50% の確率で全く別の値に変更して、その遺伝子を次の世代に残します。「コピー」は、重み付けに従って抽選された一つの遺伝子を、そのまま次の世代に残します。これで、新たな 50 個の遺伝子を作ります。

以上を 30 世代ぐらいまで繰り返して進化させると、だいたい収束し、結果もいい感じのものが得られました。

この方針だと、ステージごとにこれをやらなければならないので、初期配置のランダム性も考慮して、以上のサイクルを、「ステージの初期配置 (ステージのシード値) を変えて 3 回」 * 「遺伝子の初期配列 (遺伝子のシード値) を変えて 2 回」の計 6 回繰り返して集計し、結果としました。この部分は Ruby のスクリプトとして書いています。

ここまでのスクリプトを Jenkins のジョブとして登録し、レベルデザイナーが特定のステージや、範囲指定したステージで自動的にこの bot が回せるようにしました。

これを実行すると、例えば次のようなデータが得られます。

Stage 10 (Seed: 7270314)
  Gene Seed: 2318623
  Generation 1
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 11.04 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 2
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.64 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 3
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.62 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 4
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 9.76 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 5
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.24 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 6
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 11.48 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 7
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 11.6 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 8
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 11.18 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 9
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.98 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 10
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.32 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 11
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.86 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 12
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.26 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 13
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.44 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 14
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.42 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 15
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 9.74 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 16
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 8.69 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:) 
  Generation 17
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.0 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 18
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.1 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 19
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 10.0 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 20
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 11.3 (best:6) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 21
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 9.69 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 22
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 9.82 (best:5) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 23
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 9.98 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 24
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 9.8 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 25
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 9.94 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 26
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 8.52 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 27
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 8.74 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 28
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 7.8 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 29
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 7.8 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)
  Generation 30
    => Clear: 50/50 (100.0%) <Clear> Filled avg: 3.0 (best:3), Moves avg: 6.2 (best:4) / <Failed> Filled avg: 0.0 (best:), Moves avg: 0.0 (best:)

これはステージ 10 の学習結果です。中央の Moves avg: に注目して欲しいのですが、これは「何手でクリアできたかの平均」です。最初 11 手前後だったのが、学習によって 6 手前後に縮まっています。最終的に多くの遺伝子がこのぐらいでクリアできるようになったということです。その右の best: は最短を示していて、最速 4 手でクリアした遺伝子がいたことを示しています。

このようなデータを元に、レベルデザイナーが最終的な制限ターン数を決めていきました。

レベルデザイナー曰く、「最適ターン数が (ほぼ) 自動的に計算できるようになったことで、ステージの『制作意図』に重きを置いて、短時間でたくさんのステージを作ることができた。また、現実的にクリア不可能なステージや、設定ミスのチェックにもなった。今後のプロジェクトでも活用していきたい」とのこと。結果的に、自動テストの意味合いも出てきたのは興味深いですね。

現状、100ステージとかを計算させると10時間以上掛かるので、その点の最適化が今後の課題です。

それでは！

- oinkgms 

#development 

1. asus4 reblogged this from oinkgms
2. crazykohei0123 reblogged this from oinkgms
3. objectx liked this
4. velvet-mimizu liked this
5. livedooor reblogged this from ararky
6. k-a-i-r-i reblogged this from ararky
7. k-a-i-r-i liked this
8. ararky reblogged this from oinkgms
9. kaz-com liked this
10. solute reblogged this from oinkgms
11. t8ph reblogged this from oinkgms
12. sarasarari liked this
13. sshojyo reblogged this from meiiti
14. hojyo reblogged this from meiiti
15. maytaro reblogged this from mug-g
16. kuboji liked this
17. meiiti reblogged this from mug-g
18. meiiti liked this
19. mug-g reblogged this from oinkgms
20. qsai reblogged this from migi
21. burabutar reblogged this from migi
22. taizona reblogged this from oinkgms
23. asaic-cube liked this
24. discoveringmusic liked this
25. roamingsheep reblogged this from oinkgms
26. matubuse liked this
27. migi reblogged this from oinkgms
28. wenoog liked this
29. nknk2-blog liked this
30. t0mmy-tan reblogged this from oinkgms
31. t0mmy-tan liked this
32. yorunohimawari reblogged this from oinkgms
33. robamimi-tokoya liked this
34. hara3 liked this
35. djan5 reblogged this from iwadon
36. djan5 liked this
37. iwadon reblogged this from oinkgms
38. iwadon liked this
39. uriuriuriu liked this
40. oinkgms posted this