複雑系・人工知能ゲーム

人間などの生命体の振る舞いは非常に複雑であり、いまだになぜこのような複雑さが出てくるのかは解明されていません。

「複雑系」や「複雑適応系」の学問は、これを解明していくことを主眼にしていますが、このページは、「広く、浅く、楽しく」複雑系の世界をのぞいていきます。

強化学習
Richard S.Sutton, Andrew G.Barto, 三上 貞芳, 皆川 雅章
おすすめ平均
人工知能・ニューラルネットワークにともなう学習方法に関して勉強するなら、この本がかなりお勧め。
Amazonで詳しく見る
複雑系―科学革命の震源地・サンタフェ研究所の天才たち
M.ミッチェル ワールドロップ, M.Mitchell Worldrop, 田中 三彦, 遠山 峻征
おすすめ平均
この本で複雑系に目覚めた人もおおいはず。複雑系のおもしろさを語る名著!!
Amazonで詳しく見る

複雑系に興味を持った

最近、遅れ馳せながら『複雑系』というものに興味を持ち始めています。細かくは、『複雑系』、『複雑適応系』などと分かれるようですが、私は素人なので漠然と『複雑系』として思い付いたことを書いて、実験していきたいと思います。

分子、細胞、生命体、社会、経済などはすべて『複雑系』システムであるといわれています。これは、いったいどういうことか、私なりに以下にまとめます。

カオス創発実験-森林火災シミュレーション

局所ルールと相互作用の創発実験として、有名な森林火災のシミュレーションを書いてみました。

ルールは、以下の通りです。

以下のリンクに実験javaアプレットがありますのでどのような現象が起こるか確認してください。

森林火災シミュレーション

あまりにも遅いので、シングル版を作りました。

森林火災シミュレーション2

単純な局所ルールと相互作用によりカオス的な複雑な現象が創発するのが確認できたでしょうか?
また、木の生成確率により、ランダム(カオス的)な現象(確率0.05)、収束する現象(確率1, 0.013)が確認できたでしょうか?
また、確率0.013の時は、クリックを何回かすることにより、偶発的にカオス的な現象に移行することが確認できたでしょうか?
残念ながら、第1回で書いたようなカオスの縁と呼ばれるような現象がどのあたりの確率で出てくるのか、またどのように見えるのか、私にはわかりませんでした。

非常に汚いですが、ソースを載せます。

森林火災シミュレーションsource

複雑適応系に興味を持った

『複雑系』と『複雑適応系』とは明確に分かれる分野だということが、ようやく理解できてきた今日このごろです。

以下に私の理解を書きます。

個人的には、最近になって『複雑系』全般への興味から『複雑適応系』への興味に移行しつつあります。
大きな理由としては、『複雑系』より『複雑適応系』のほうが個人としての成果物(例えば『人工知能』を用いたゲームなど)が挙げやすいというところです。
やはり『マンデルブロー集合』の描画より『人工知能オセロ』のほうが趣味でやっていく分には面白そうだというところでしょうか。
その他の興味として『エージェント・シミュレーション』(Boid, SimCityなど)がありますが、これがどちらのカテゴリに属するかは、いまだ不明です。

さて、『複雑適応系』に話しを絞って考えた場合、系の特徴としてどのようなものを備えてなければならないでしょうか。

現在研究されているいろいろな『複雑適応系』によりそのアルゴリズムは異なりますが、『解の探索』、『汎化』、『適応度学習』といったことが行われていると考えられます。

この他にもいろいろな系(クラシファイア・システム、強化学習システムなど)がありますが、『人間の脳』には、まだ遠いようです。

複雑適応系に興味を持った2

前回では、代表的な『複雑適応系』のアルゴリズムとして遺伝的アルゴリズムとニューラル・ネットワークを挙げましたが、最近『強化学習』という本を購入したので、そちらの紹介もしようと思います。

強化学習/ニューラルネットワークを利用したゲーム制作: ハムレット

理論ばかり読んでいてもつまらないので、実際ゲームを作ってみようと思います。

今回作成するのは『ハムレット』というゲームです(この名前は、ツクダオリジナルの登録商標のようなので、他では『立体4目並べ』、『Win4』などと呼ばれています)。 このゲームの選定理由は、『3目並べ』よりゲームに幅があり、『オセロ(これも登録商標。。。Reversi)』よりゲームに幅がないという理由です。

まずは、強化学習を利用するということで、強化学習の基本原理から。

RLの基本的な構造

強化学習は、下図のように、基本的に環境との相互作用で学習していく方式となります。

RLの基本的な構造


                 +--------+
       +-------->|RL Agent|
       |   +---->|        |----+
       |   |     +--------+    |
       |   |                   |
  State|   | Reward            | Action
       |   |                   |
       |   |   +-----------+   |
       |   '---|Environment|<--+
       +-------|           |
               +-----------+

RLをクラスで考える

RLをクラス構造として考えるため、上記のRLの基本構造から流れを追っていきます。

これをそのままクラス図に書くと下図のような感じになります。

RLのクラス図


              +--------+      1 +--------------+
              |RL Agent|--------|Value Function|
              |        |        +--------------+
              |        |      1 +--------------+    1 +-----+
              |        |--------|Environment   |------|State|
              |        |        |(Singleton)   |      +-----+
              +--------+        +--------------+ 

ただし、とれるActionの種類がStateによって変わる場合は、Environment側で次に取れるActionのリストを送るほうが実際的だと思われます。例えばハムレットの場合、上まで駒が入ってしまった列には、それ以上駒が入らないので、StateによりとれるActionが変わるということです。

これを反映させると、RLの構造的には、以下のようになり、

RLの基本的な構造2


                               +--------+
              +--------------->lRL Agent|
              |      +-------->|        |
              |      |   +---->|        |----+
              |      |   |     +--------+    |
              |      |   |                   |
        Action| State|   | Reward            | Action
        List  |      |   |                   |
              |      |   |   +-----------+   |
              |      |   '---|Environment|<--+
              |      +-------|           |
              +--------------|           |
                             +-----------+

クラス図で書くと以下のようになります。

RLのクラス図2


              +--------+      1 +--------------+
              |RL Agent|--------|Value Function|
              |        |        +--------------+
              |        |      1 +--------------+    1 +-----+
              |        |--------|Environment   |------|State|
              |        |        |(Singleton)   |      +-----+
              +--------+        |              |    1 +-----------+       * +-------+
                                |              |------|Action List|---------|Action |
                                +--------------+      +-----------+         +-------+

2playerゲームに適応してみる。

上記を2playerのターン制ゲーム(3目並べ、ハムレット、オセロなど)に適応させることを考えると、あらたにゲーム進行役のクラスが必要となります。

2player gameのクラス図


       +---------+       +--------+      1 +--------------+
       |Game Host|     2 |RL Agent|--------|Value Function|
       |         |-------|        |        +--------------+
       |         |       |        |      1 +--------------+    1 +-----+
       +---------+       |        |--------|Environment   |------|State|
                         |        |        |(Singleton)   |      +-----+
                         +--------+        |              |    1 +-----------+       * +-------+
                                           |              |------|Action List|---------|Action |
                                           +--------------+      +-----------+         +-------+

上記の図を見ていると、EnvironmentとRL Agentの橋渡し(State, Action List, Reward, Actionのやり取り)は、Game Hostの役目にしたほうがよさそうです。

2player gameのクラス図2


       +---------+       +--------+      1 +--------------+
       |Game Host|     2 |RL Agent|--------|Value Function|
       |         |-------|        |        +--------------+
       |         |       +--------+        +--------------+    1 +-----+
       |         |                       1 |Environment   |------|State|
       |         |-------------------------|(Singleton)   |      +-----+
       +---------+                         |              |    1 +-----------+       * +-------+
                                           |              |------|Action List|---------|Action |
                                           +--------------+      +-----------+         +-------+

次回は、それぞれのクラスの設計に移る予定です。

強化学習/ニューラルネットワークを利用したゲーム制作: ハムレット2

今回は、前回出てきたクラスを肉付けしていきます。設計の方針として、以下のことを考慮するようにします。

また、クラスの命名規則は、以下のようにしています。

それでは、それぞれのクラスのインタフェースを考えていきましょう。

Game Host

上記から、mainから呼ばれるメソッドは、

が必要そうです。 以下のように簡単に書いてみます。

IfGameHost


      +------------------------------------------+ 
      |          << interface >>                 |
      |            IfGameHost                    |
      +------------------------------------------+
      +------------------------------------------+
      | public void initialization(Agent, Agent) |
      | pubilc void startGame()                  |
      +------------------------------------------+

しかし、このままではmainがAgentを知っていなければなりません。個人的には、mainは、"Agentの種類"は知っているが、"Agent Class"は知らない。という状態にしたいと思います。これによって、mainが勝手にAgentのメソッドを使用することをなくしたいのです。

そこで、IfGameHostをFactory Methodにし、同時にGameHostの抽象クラスを設計してしまいます。

IfGameHost2, AbsGameHost


      +--------------------------------------------+ 
      |          << interface >>                   |
      |            IfGameHost                      |
      +--------------------------------------------+
      +--------------------------------------------+
      | public void initialization()               |
      | public void initGameAgent(String, String)  |
      | pubilc void startGame()                    |
      +--------------------------------------------+

      +----------------------------------------------+ 
      |          << abstract >>                      |
      |  AbsGameHost implements IfGameHost           |
      +----------------------------------------------+
      | protected Agent _player[]                    |
      | protected Environment _environement          |
      | protected Map _agentList                     |
      +----------------------------------------------+
      | public AbsGameHost()                         | <- Call initialization();
      | public abstract void initialization()        | <- GameHostのConcreteクラスがAgentの全種類を
      |                                              |      singupPlayerを呼び出して、signupする。
      | protected void signupPlayer(String, String)  | <- Call _agentList.put();
      | public void initGameAgent(String, String)    | <- _agentListから該当クラスを見つけ、
      |                                              |       Instanciateし、_player[]に代入。
      | pubilc void startGame()                      | <- gameを進めるメインのメソッド。
      +----------------------------------------------+

Environment

本来なら、拡張性を考え、いろいろなゲーム毎にEnvironmentのサブクラスをインプリするのですが、Singletonなので、サブクラスを作成するのが非常に面倒です。
今回は、サブクラス化は、あきらめてConcreteクラスをいきなり作る方法でインプリすることにします。
インタフェースですが、以下のようなものが必要となりそうです。

IfEnvironment


      +----------------------------------------------+ 
      |          << interface >>                     |
      |           IfEnvironment                      |
      +----------------------------------------------+
      +----------------------------------------------+
      | public static Environement getEnvironment()  | <- Singleton用インスタンス取得
      | public void initState()                      | <- State(盤面の状態)の初期化
      | public void updateToNewState(player, Action) | <- ActionによるStateの更新
      | pubilc double getReward()                    | <- 報酬の計算
      | pubilc ActionArray possibleActions()         | <- 次のターンで取り得るAction
      | pubilc boolean isContinuable()               | <- ゲーム終了かどうか
      |                                              |
      | pubilc State getCurrentStateCopy()           |
      +----------------------------------------------+

最後の"getCurrentStateCopy"は、強化学習(Reinforcement Learning)の学習において、State毎の価値(Value)を学習するということがあるため、Agentで使用する"State"を得るために入れてあります。

State

IfState


      +----------------------------------------------+ 
      |          << interface >>                     |
      |           IfState                            |
      +----------------------------------------------+
      +----------------------------------------------+
      | public void initState()                      | <- Stateの初期化Game開始時に呼ばれる
      |                                              |
      | public State getNewState(player, Action)     | <- Action後の盤面のコピーを返す
      |                                              |     (現状の盤面は、変化しない)
      |                                              |
      | public boolean equals(Object)                | <- Stateオブジェクトの同一性(override)
      | pubilc int hashCode();                       | <- StateのHashTable保持用(override)
      +----------------------------------------------+

真ん中の"getNewState(player, Action)"は、強化学習においては、自分が手を打った後の盤面に対して価値(value)の学習を行うため、実際の盤面を変更せずに"手を打った後の盤面のコピー"が必要となるためいれています。
下の2つは、強化学習においてState毎に価値(value)の学習を行いますが、同一Stateかどうかの判断を行う場合に必要となります。
Environmentから使用するメソッドも含めて抽象クラスを書くと、下記のようになります。

AbsState


   +--------------------------------------------------------+ 
   |          << abstract >>                                |
   |           AbsState                                     |
   +--------------------------------------------------------+
   +--------------------------------------------------------+
   | public abstract void initState()                       | <- Stateの初期化Game開始時に呼ばれる
   | public State getNewState(player, Action)               | <- Action後の盤面のコピーを返す
   |                                                        |   (現状の盤面は、変化しない)
   |                                                        |   : getCopy()-->updateToNewState(p,A)
   | public abstract boolean equals(Object)                 | <- Stateオブジェクトの同一性(override)
   | pubilc abstract int hashCode();                        | <- StateのHashTable保持用(override)
   |                                                        |
   | protected abstract void updateToNewState(player,Action)|
   | protected abstract double getReward()                  | <- 報酬の計算
   | protected abstract ActionArray possibleActions()       | <- 次のターンで取り得るAction
   | protected abstract boolean isContinuable()             | <- ゲーム終了かどうか
   | protected abstract State getCopy()                     |
   +--------------------------------------------------------+

AbState側に、possibleActions()や、isContinuable()などをインプリすることにより、、Environment側ではAbStateに委譲するだけというインプリにしています。
このとき、EnvironmentおよびStateからのみ呼ばれているものは"protected"にして保護しておきます。

Action/ActionList

ActionとActionListは、典型的なデータオブジェクトで、getter/setter以外には、メソッドを持ちません。
これらのクラスは、最初からConcreteクラスとしてインプリすることにし、インタフェース・抽象クラスの設計をしません。
(というか、データオブジェクトの抽象クラスの作成ってできるの?)

RL Agent

IfAgent


     +---------------------------------------------+ 
     |          << interface >>                    |
     |           IfAgent                           |
     +---------------------------------------------+
     +---------------------------------------------+
     | public void initAgent()                     | <- Agentの初期化Game開始時に呼ばれる
     | public Action returnAction(ActionList,State)| <- Actionの選択肢リストと現在のState
     |                                             |    から次のActionを返す
     | pubilc double setReward()                   | <- 報酬の受け取りと学習
     +---------------------------------------------+

次回は、強化学習の肝であるValueFunction(価値関数)に関してです。

強化学習/ニューラルネットワークを利用したゲーム制作: ハムレット3

今回は、ValueFunctionに関してです。まずは、強化学習におけるValueFunctionの流れを見てみます。

IfAgent


Case: 後攻の場合
(最初の状態)
       [ ][ ][ ][ ][ ][ ][ ]
       [ ][ ][ ][ ][ ][ ][ ]
       [ ][ ][ ][ ][ ][ ][ ]
       [ ][ ][ ][ ][ ][ ][ ]
       [ ][ ][ ][ ][ ][ ][ ]
       [ ][ ][ ][ ][ ][ ][ ]
       <oldState>
                |
                |
             相手の手
                |
                +-----------------------+-----------------------+--------------------
(自分の手の選択) |                      |                       |
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] ......
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [2][ ][ ][1][ ][ ][ ]   [ ][2][ ][1][ ][ ][ ]   [ ][ ][2][1][ ][ ][ ] 
                              <newState>| (選択された手)
                                        |
                                     相手の手
                                        | <reward(報酬)を得て、valueFunctionのアップデート(学習)>
                                        |
                                        | <oldState=newState>
                +-----------------------+-----------------------+--------------------
(自分の手の選択) |                      |                       |
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] ......
       [ ][ ][ ][1][ ][ ][ ]   [ ][2][ ][1][ ][ ][ ]   [ ][ ][ ][ ][ ][ ][ ] 
       [2][2][ ][1][ ][ ][ ]   [ ][2][ ][1][ ][ ][ ]   [ ][2][2][1][ ][ ][ ] 
                                                      <newState>| (選択された手)
                                                                |
                                                             相手の手
                                                                |
                                                                :


上記図において、ValueFunctionは、2つの働きをしています。

なお、この方式は、TD(0)と呼ばれるもので、これ以外にも"Action(行動)とState(状態)の組"で学習するものや"価値を評価する関数と行動を選択する関数を別にもつもの"などがあります。
今回は、"Stateに対してあるActionを取った場合、次のStateが特定できる"ため、Stateのみの関数で実装します。(TD方式)