Evolutionary Game Design

論文誌: IEEE Transactions on Computational Intelligence and AI in Games (CIAIG)

公開日: 2011/3

付箋は個人的な解釈を述べたもの

概要

自己対戦と57のゲームデザイン評価基準による評価

最終的にどれも五目並べライクになる模様

遺伝的アルゴリズムにより既存のゲーム(囲碁、オセロ、五目並べなど)を学習

It is easy to create new combinatorial games but more difficult to predict those that will interest human players.

組み合わせゲームを開発することは簡単だが、それが人間のプレイヤーにとって面白いかどうか予測するのは相当難しい。

We examine the concept of game quality, its automated measurement through self-play simulations, and its use in the evolutionary search for new high quality games.

私たちはゲームのクオリティという概念を研究した。それは自分のプレイをシミュレーションすることで自動的に測定されるもので、新しいハイクオリティなゲームを探索する画期的な方法である。

A general game system called Ludi is described and experiments conducted to test its ability to synthesise and evaluate new games.

Ludiという汎用的ゲームシステムを提案し、新しいゲームを生成し評価することの有用性をテストする実験をした。

Results demonstrate the validity of the approach through the automated creation of novel, interesting and publishable games.

結果として、ストーリーや面白く売れそうなゲームを自動生成するためのアプローチに価値があることを証明した。

イントロダクション

Introduction

ゲームに関する研究は注目されAIの発展に寄与しているが、ゲームのクオリティを評価することにはあまり興味を持たれない

このような質問をもたれる

面白いゲームを作る要素は何か

従来のゲームのようになるといえるのか

売れるゲームかどうか利益を考えてテストして判断するには時間がかかる

自動的にゲームのクオリティを評価するようなツールがあればゲームデザイナーやゲーム産業にとって大きく貢献できる気がする

しかも新しいルールの組み合わせを自動探索できて、価値のある完全な新しいゲームを生み出すメリットをデザイナーにもたらす

Ludi

組み合わせゲームを評価し生成するためのフレームワーク

以下の仮説の有用性とシステムのテストのために3つの実験をした

基本的(かつ評価可能)なゲームのクオリティを数値化できること

新しい高品質なゲームを直接的に探索することに利用できること

ゲームの定義

Defining Games

ゲームを定義するいくつもの方法として、SalenとZimmermanは次の有益な意見をしている

Ludiのデザインの中心となる概念

ゲームの基礎的な分析モデル

組み合わせゲーム

Combinatorial Games

以下の組み合わせゲームに焦点を当てた

プレイ人数に関して

2人用という条件で必要なのは、ソリティアのようなパズルは組み合わせゲームなのかといったような議論が可能であること

ある意味ではパズルの回答者はnullプレイヤーと対戦し、間接的にこのゲームをデザインした人とも対戦しているといえる

マルチプレイゲーム(3人以上)はプレイヤー同士の衝突という起こりうる社会的側面があるため、組み合わせプレイの範疇の外に陥りやすい

研究方針

この研究では自己プレイシミュレーションを実現する方法以外でAIプレイヤーは研究の対象外である

意味のあるプレイアウトまでできる十分な強さが必要ではあるが、プレイヤーのクオリティよりもゲーム自体のクオリティに対して優先的に注力する

Ludemes

あるゲームの要素を元に新しいゲームが生み出されていくことでゲームが拡張されていく

ゲームが拡張されていく例

ボードを定義するにはこのような要素を記述する

code:sample board 1a

(tiling square)

(size 3 3)

概念的に近い要素はカプセル化され、このようにより高度なludemesを形成する

code:sample board 1b

(board

(tiling square)

(size 3 3)

)

二人用Tic-Tac-Toeはこのように記述される

code: tic-tac-toe

(game Tic-Tac-Toe

(board

(tiling square)

(size 3 3)

)

(win (in-a-row 3))

)

Tic-Tac-Toeのゲーム例

https://gyazo.com/e9b55134ac8eed49c786df6a645e6263

Ludemesの成功例

Tic-Tac-Toeのマスを六角形にし、盤を拡張したもの

Ludemesの成功例として最も有名

ゲームの組み替え

Recombination Games

Ludemicなゲームにおいては、拡張したり新しいゲームを生み出したりするルールを作ることは簡単である

Tic-Tac-Toeの組み替え

ボードサイズを変える

(size 2 2)

勝利条件を変える

(win (in-a-row 2))

ただ、わずかな変化がゲームを崩壊させることに繋がることもある

最初のケースにおいて勝てなくなる

2番目のケースにおいてあまり勝てなくなる

3次元ボードに拡張する

(size 3 3 3)

勝利例

https://gyazo.com/a4c21b9ec709eb40eb6d4fb1db08929d

(lose (in-a-row 3))

組み合わせゲームのルールにわずかでも変更を与えるとゲームが崩壊してしまうことがある

ルールが壊れないかつ奥が深い遊び方ができるような単純なルールを作る必要がある

人工的な要素を生成することは簡単だが、人間の求める高いクオリティという目標に到達するのは非常に難しい

ゲームの組み替えによって生まれる面白さ

確実なアプローチは他のゲームのルールと組み合わせて、面白さや今まで生まれなかった新しいルールの組み合わせを見つけることである

どうやって潜在的で広大なデザインの余地を効率的に探索するか

ゲームの相違

Game Distance

ルールの重複している部分や違い、もしくは全く新しいかどうかを判定するために、既存のゲームと新しく編み出されたルールセットとの違いを測ることは有益

Ludemes形式のゲームならルールをツリー構造にして2つのルールの木の重みを比較すれば違いが明確になる

Ludemes形式ならルールを継承(拡張)していき新しいルールが生成できるので必ず親ノードが存在する

ルールのパラメータの違いはあまりないのに、ルール自体の構造的な違いは非常に大きい

ハイレベルなルールは一般的に広く応用できる上に重要

汎用的なゲームプレイヤー

General Game Players

いくつものルールセットを作り出す可能性があるなら、自己プレイによって自動でルールをテストできることが望ましい

General Game Players(GGPs)は何か一つのゲームを高度にプレイするというよりもある範囲のゲームをそれなりにプレイするためのソフトウェアであり、この目的にとっては理想的

Game Description Language

GGPの中心にあるのがGDL

GDLを定義することは微妙なバランスの上で成り立っている

GDLは様々な既知や未知のゲームをカバーするには強力で拡張性が高い上に、なおかつ効率的で素晴らしく人間のゲームデザイナーにとって理解しやすい

Windows用のアブストラクトゲームがいくつも遊べるソフトウェア

ZRFの作者はを予約語を用いたLispライクな文法でゲームを定義した

マクロを使って複雑なルール構造をプログラムを通して作り出すことができる

Ludiのシステム

THE LUDI SYSTEM

LudiはGDLの範囲内でゲームを評価し生成するプレイのためのシステム

https://gyazo.com/bf8ecab94456ea9cda7b4743ee85d53e

Ludiシステムのフレームワーク

要素

GDL: ゲームの範囲を定義する

GGP: ゲームを解釈しプレイを調整する

手筋モジュール: どう手を打つか計画する

評価モジュール: ゲームのクオリティを測る

生成モジュール: 新たなゲームを生成する

https://gyazo.com/a6337b948bf157de32bb1440149a0279

基本的なゲームモデル

means -> Equipment/Rules

ends -> Outcomes

Ludi GGP

GGPはLudiシステムの中核である

C++で実行される

以下の機能を持つ

ルールの構文解析

Ludi GDLで定義されたゲームを解析する

ludemeツリーを構築し、ゲームオブジェクトが初期化される

ゲームオブジェクト

現在の盤の状態を持つ

合法手の生成や終了条件のテストができる

UI

現在のルールセットを分かりやすい英語に翻訳される

プレイヤーにとって新しいゲームを理解しやすくなるチュートリアルモードが提供される

プレイ管理

1～8人の人間やAIプレイヤー用のプレイを調整する

ただし本研究では2人のみ対象とする

手を予約する

入力を操作する

無限ループ、全プレイヤーのパスなどを防ぐために繰り返しテストする

AIプレイヤーはαβ探索で手を選択する

https://gyazo.com/ebcdb1c37ea5d3de4dabe14a094c4383

LudiのUI

手筋モジュール

盤の座標に対してそれぞれのプレイヤーにとっての価値を推定する

指導者(Advisor)

https://gyazo.com/d564ea22a98c13d90b86f86d9e48818b

Advisorのモデル

方策(Policies)

$ E(s) = w_1f_1(s)+w_2f_2(s)+...+w_nf_n(s)=\sum_{i=1}^n w_if_i(s)

方策の最適化

省略

ゲームの評価

Game Evaluation

評価モジュールはとある"美の基準"に基づいて自己プレイシミュレーションによってゲームのクオリティを測定する

ゲームのクオリティ

ここでいうクオリティとはそのゲームがヒューマンプレイヤーにとって面白いという可能性があるということ

Depth(奥深さ): ゲームの面白さが続く

Clarity(わかりやすさ): 手筋が混乱しない

Drama(ドラマ): 不利な状況から逆転する可能性がある

Decisiveness(明白さ): 勝者が決まればすぐに終了する

ゲームの美しさのモデル

ここでいうゲームの美しさとはゲームとして理想的で整っているという指標

着手の戦術的な計画を識別するために"play"要素を拡張した

https://gyazo.com/849d49a2ff225d8ccb234e218a680438

プレイヤー中心で考えたゲームの美しさのモデル

美しさの基準

Aesthetic Criteria

このモデルは以下のように分解できる

Intrinsic (固有の): ルールや用品に基づく

Extrinsic (外来の)

Viability: 結果に基づく

Quality: プレイの傾向に基づく

好ましいゲームの長さ

Preferred Game Length

一般的に好ましいゲームの長さは60手である

平均で1手当たり30秒かかる2人では1ゲーム30分ぐらいかかる

美しさの評価

Aesthetic Measurement

美しさの評価はいくつもの自己プレイ試行の中で生み出される

固有の基準 x 16

結果に基づく基準 x11

プレイの傾向に基づく基準 x 30

Viability > Completion(完了)

ゲームは引き分けより勝つ方が多い方がいい

$ A_{comp} = wins / G

Viability > Duration (長さ)

ゲームは短すぎても長すぎてもいけない

$ A_{durn} = 1 - \sum_{g=1}^G\frac{|M_{pref}-M_g|}{M_{pref}}/G

Quality > Drama(ドラマ)

与えられた面白さが維持されているならば、不利な状況から逆転する可能性が少なくともあるべきである

定義は省略

Quality > Uncertainty(不確実性)

与えられた面白さが維持されているならば、できるだけ長く不確定な状況が続くべきである

定義は省略

美しさの基準を判定する効率

Criteria Efficiency

この論文で述べられてない基準のなかには他より評価するのにとても効果が薄いものもあり、それらの基準は別の方法でさらなる試行が必要である

美的係数

Aesthetic Coefficients

定義省略

ゲームの生成

Game Synthesis

生成モジュールでは汎用的プログラミング手法(=GDL)で書かれたルールセットの進化によって新しいゲームを生み出す

ペルは以前に不自然で確率的な脈絡のない生成メソッドをつかってチェスのようなゲームを自動生成した

参考: Development of a Multi-Game Engine, Diploma Thesis (論文不明)

これらのゲームはあるルールによって直接組み立てられている

一方で理解の心揺さぶる方法を使ってゲームを生成することや、組み立てにとって必要なルールについての仮説を作らずに人間にとっての面白さを刺激するゲームを探索することを望んでいる

ゲームの配合

生きている子孫の全てが世代から世代へ至ることはない

ここでいう適合性とは生き延びやすさというよりは秩序を示すもので、新しいルールの組み合わせの出現を促進する

進化は制限に達するか新しいゲームの数が一定数生成されるまで続く

https://gyazo.com/a6c05f40858cc8e6a72351188631e27d

ゲームのライフスタイル

このプロセスは1つの最適な個体よりは興味深い個体をいくつも生み出すことが狙いである

ゲームの集合

Population

初めはよくできた子ノードを繁栄させるためにいくつもの既知のゲームで初期化する

しかし厳密にはランダムなゲームの組み合わせだと存続できるゲームを生みにくい

親の選択

Parent Selection

適正の合理的な基準が維持されている上で遺伝子の多様性を助長しつつ、全範囲からサンプルを選びより適切な個体を頻繁に選ぶ方法

組み替え

Recombination

ハイレベルなLudi GDLを実現するには、階層的なLudemeツリーが理想である

突然変異

Mutation

子ノードの要素は10%の確率で突然変異を起こす

Ludemeツリー上で要素か属性(もしくはその両方)を加えたり変えたり削除したりする

文脈保存の制約を用いることでその変更によって要素のタイプに適合しなくならないこと、また削除された要素が必要なデフォルトの値を置き換えられることを保証する

通例

Baptism

それぞれの子ノードはそのゲームの集合に特徴のある短い名前が与えられる

Oroth, Galdal, Etherond, Kemeneth, Valindor, Bered, Morなどがある

妥当性のチェック

子ノードは一連の妥当性のチェックを受ける

ルールの安全性

Rule Safety

スピードテスト

Speed Test

手のプランニングに1手あたり15秒以上かかる場合、子ノードは1,2,3,4回の探索を経て捨てられる(？)

スピード制限により複雑なゲームは除かれる

一般的には広いボードに多くのピース、広く枝分かれした要素、1つの子ノードしか生み出せないリスクのあるゲーム

方策の選択

Policy Choice

子のデフォルトの方策と両親ノードの方策を総当たり戦で全て組み合わせて比較したり、最も成功したハイブリッドを選んだりすることでそれなりの方策が得られる

そのゲームに時間がかかりすぎたり勝ち負けが半分以上決まらない子ノードは捨てられる

近親配合

Inbreeding

子ノードはゲームの集合のそれぞれの一員との距離を測られ、非常に近い親戚が見つかれば削除される

再増殖

この時点で生き残っている全ての子ノードはクオリティが評価され、予測された美しさのスコアによって集合の後ろに追加されたものである

このスコアはこの段階では準備段階に過ぎないが目的に順序をつけるには十分

美しさの評価によってゲームを存続できないものだと証明される結果に基づくテストが行われるという副産物が生まれる

存続できないゲーム例

たいてい引き分けの結果になる

プレイヤーのバランスが非常に悪い

先手と後手のアドバンテージの差が開きすぎている

合理的な着手数でゲームが終わらない

発生

Emergence

ルールの最適化が実行されずに、全ての子孫が遺伝子のプールに返れば欠点のあるルールや壊れたゲームの集合が増殖する

ゲームの集合の不適切な部分を除去することで最初の先祖とほんの少し異なる子孫を生み出せる

ルールが壊れやすいため、存続可能で今までにないより優れた子を生み出すため2つの与えられたルールセット同士が再結合したり突然変異したりすることはそれほど起こることはない

実験

Experiments

1. ゲームの順位付け

手法

課題

結果

2. ゲームの評価付け

手法

結果

3. ゲームの生成

手法

課題

結果

議論

Discussion

結論

Conclusion

付録

Appendix

2. 生成したゲームのGDL

code:NDENGROD

(game Ndengrod

(players White Black)

(board (tiling hex) (shape trapezium) (size 7 7))

(pieces

(Piece All

(moves

(move

(pre (empty to))

(action (push))

(post (capture surround))

)

)

)

)

(end (All win (in-a-row 5)))

)

code:YAVALATH

(game Yavalath

(players White Black)

(board (tiling hex) (shape hex) (size 5))

(end

(All win (in-a-row 4))

(All lose (and (in-a-row 3) (not (in-a-row 4))))

)

)

code:TEIGLITH

(game Teiglith

(players White Black)

(board (tiling square) (size 7 7))

(pieces

(Stone All

(moves

(move

(pre

(and

(> (group-size to) (phase to))

(connected)

)

)

(action (pop) (push))

)

)

)

)

(start (place (Stone White) home))

(end (All win (no-move)))

)

code:ELROSTIR

(game Elrostir

(players White Black)

(board (tiling square i-nbors) (size 5 5))

(end (All lose (or (no-move) (in-a-row 3))))

)

code:GORODRUI

(game Gorodrui

(players White Black)

(board (tiling hex) (shape hex) (size 3))

(pieces

(Stone All (state 1)

(moves

(move (pre (empty to)) (action (push)))

(move

(pre

(and

(enemy from) (empty to)

(= (+ (piece-state) 1) (distance))

)

)

(action (pop) (push))

(post (inc-state))

)

)

)

)

(start (in-hand (Stone All) 5))

(end (All lose (no-move)))

)

code:VALION

(game Valion

(players White Black)

(board (tiling square i-nbors) (size 4 4))

(pieces

(Stone All

(moves

(move

(pre (>= (num-nbors to enemy) 1))

(action (push))

)

(move

(pre (and (empty to) (connected)))

(action (push))

)

)

)

)

(start

(place (Stone White) A1)

(place (Stone Black) D4)

)

(end

(All win (in-a-row 3))

(All lose (or (in-a-row 4) (group)))

)

)