読者です 読者をやめる 読者になる 読者になる

isEOL(@Angelworm_)

this method describes @Angelworm_ is End Of Life

2048のAIを書かなかった話。あるいは遺伝的プログラミングの話

programming C++

KMCでは2048のAIを作って戦わせるコンテストである「第一回2048AIコンテスト 結果報告 - KMC活動ブログ」が開催たそうですね。これを見て2048AIを私も作ってみたくなりました。

ところで、ボードゲーム上でAIとはおおよそ「勝率が最も高まる手を現在の状況を元に出力する」ものだと思います。チェスなどのゲームに置いて有名な「ミニマックス法」などは相手が最も自分に取って都合が悪い選択をして、自分が最高の選択をし続けた場合一番最初に選ぶべき最高の手を出力するアルゴリズムです。
このような次におこる状況を予測して手を決定するアルゴリズムは、探索アルゴリズムなんて呼ばれたりしています。

探索アルゴリズムを利用する上で大事なのは、読みの深さと評価関数の良さです。読みの深さとは、言葉の通りゲームの状況を何手先まで読む事が出来るかを表し、深ければ深いほどより大局的な戦い方が出来るようになるわけですね。

さて、もう一つ重要な要素、評価関数。これは、「盤面がどれだけ都合が良いか」を表す関数です。プログラムにチェス版を見せたらどっちが有利か教えてくれるイイ奴ですね。探索アルゴリズムの基本は、数手先の盤面が最も不運でも最も良いものが得られる物を探す事にある関係から、盤面の善し悪しを間違える事は致命傷となります。

二つの要素、深読みと評価関数。これらはそれぞれ細かい試行錯誤や調整の上に成り立つ事が多い要素となります。そんな泥臭い事をやるのは人間の仕事ではないと考えるのが情報学徒の常ですよね。そこで今回は適当に探索アルゴリズムを持ってくるとして、評価関数をなんとか上手い事コンピュータに生成してもらおうと思います。

遺伝的プログラミングとは

ここまでだいぶ紙面を割いてしまいましたが本題です。今回適切な評価関数の生成に「遺伝的プログラミング」を利用してみようと思います。

遺伝的プログラミングとは、遺伝的アルゴリズムの派生だそうです。遺伝的アルゴリズムといえばかの伝説的動画投稿者むにむに教授の動画「遺伝的アルゴリズムでブランコの漕ぎ方を学習させた。 ‐ ニコニコ動画:GINZA」にくわしいですね。今回は遺伝的アルゴリズム遺伝的プログラミングは遺伝子の形が違うだけでほとんど同じですのでまとめて解説します。

遺伝的アルゴリズムではある値の列の事を遺伝子と呼びます。先の動画では「時間経過でしゃがむか立つかの列」がソレに当たります。また、この列がどれほど問題に対して有効かを表す指標を適合度と呼んだりします。先の動画では「どれほど高く揺らせるか」ですね。

それに対し、遺伝的プログラミングでは関数やプログラムを遺伝子と呼びます。例えば、「ある関数f(x)を中身を見ずに再現せよ」といった問題のときは、関数fとの誤差の逆数を取れば適合度と表現できます。

関数を生成する?

しれっと「関数を遺伝子と呼ぶ」と表現してしまいました。もしかしたら、関数を値として扱うことに慣れてない方もいらっしゃるかも知れません。

例えば以下のような式をどのように解釈するでしょうか。

  1 + 2 * 3 - 4

もちろん、演算子結合の優先度から2*3を先に計算して、1+6、7−4と計算しますね。すなわち馬鹿正直に括弧を付けると次のようになる訳です。

  (1 + (2 * 3)) - 4

このように書いてみると、この式とは「式と式を演算子で組み合わせたもの」と表現できる気がします。1とか2とかの値も式です。構造体とかで書いてみると分かりやすいですね。

struct tree {
  std::string op;
  struct tree *opr[2];
}

すなわち式は木として表せるという事でした。何となくLispをやる人がプログラムはリストから出来ていると言い出す理由が分かりますね。

このように書き表せば関数も木として表せる訳で、遺伝的プログラミングというのは遺伝子のデータ構造がリストから木に進化したものと考えるだけで良さそうですね。

遺伝的アルゴリズムのしくみ

話がそれました。遺伝的なんとかでは遺伝子が有って、遺伝子には適合度が有って、適合度を比較し合うひとまとまりの集団を世代なんて呼んだりするという話でした。

このアルゴリズムが遺伝的と名に冠する理由は、次の世代の作り方に有ります。それは、世代から選んだ遺伝子に対して以下のどれかを行う事で次の世代の遺伝子とする事から来ています。

  1. そのまま受け継ぐ
  2. もう一つ選び、交叉する
  3. 一部をランダムに置き換える(突然変異)

基本的に1と3は確率低めにして、2をメインで行う事が多いようです。

交叉とは、普通の遺伝子の話ではお互いに遺伝子を入れ替える話でした。遺伝的プログラミングでもそうです。先ほど言った通りプログラムは木ですので、一部を切り出してもプログラムになります。そこで、二つの木から、交換する箇所を選んで取り替えてもそれぞれは全く新しい木になりプログラムとして成立します。

交叉の方法にもいろいろ有るようですが、最も単純なのが木の節がすべて一様に選択される確率を持つ普通の交叉なのでソレを採用するのがよいのではないでしょうか。他の方法は後述します。

1には優秀な遺伝子を残す狙いが有りますが、確率を高める事には探索に意味を無くす点、3を高めるとランダム探索と相違が無くなる点を考えれば、基本的に2が90%で3が1%とかの確率設定が目安のようです。

遺伝子の選択とか

適当に良さげな遺伝子を選択すると言いましたが、どうするのが良いのでしょう。いくつか紹介します。

全体の適合度の構成割合をそのまま選択確率を見なす方法が有ります。ある遺伝子iの適合度をfiと呼ぶならばfi/Σfjを選択確率とすれば良い訳ですね。この手法は、ある値が突出しやすい場合に使うと過学習の原因となりますが、均一の場合はあまり優秀でない遺伝子もたまに選択できる点は元の遺伝子の仕組みに近いですね。

トーナメント方式と呼ばれる方法は、ランダムに選んだ集団の中から最も優秀な遺伝子を選択する手法です。優秀な遺伝子の選択されやすさを手動でコントロールできる点が強みですね。本質を見失っている気もしますが。また、N個の集団から一位を選び出した集団からトーナメントを行う段階的な手法も有るようです。

ほかにもいくつかはwikipediaとかに乗ってるらしいので適宜参照ください。

ブロート問題

一般に遺伝的プログラミングによる出力は、精度の上昇速度に対して木の大きさの爆発があまりにも大きくなりやすく、割に合わない状態になりやすいと言われています。この現象をブロートと言います。木の大きさと精度の相関は低い事を考えると、出来るだけ木の大きさを押さえた方が計算時間もメモリ消費も押さえられ、世代が稼げます。

なぜ木が爆発するのかと言えば、交叉の仕方に有ります。大きめの木の小さい箇所に大きな木を接ぎ木する事で木は大きく成長します。元々選択候補に上がるほど優秀な遺伝子ですので、小さい箇所を変えた程度では能力が落ちる事は少なく、結果的に大きい物が生き残りやすくなります。

交叉の仕方はいくつか提案されています。

  1. 前述の一様に枝を選択する特に名前のない交叉
  2. 二つの木の形についての共通箇所に注目し、その境界についてのみ交叉を行う「一様交叉」
  3. 二つの木の共通箇所内での同じ点で交叉を行う「一点交叉」
  4. 片方で選んだ部分木と同じ大きさの木を交換する「サイズ依存交叉」
  5. 深さに応じて選択確率が減少する「深さ依存交叉」

これらは、それぞれ木の大きさを制限した交叉の仕方ですので、木の生長は遅くなりますが、逆に十分な木の大きさが得られにくいため、初期に生成する木の大きさが重要となります。

本題

最初に言ったように今回は2048を最も上手く解くAIの評価関数を自動生成します。

盤面に対する評価関数ですので、引数には盤面を丸ごと与える事にしましょう。ここでは、2048の盤面を左上からジグザグにb0、b1…b15まで割り降る事にします。つまり終端記号(値)と非終端記号(演算子)はそれぞれこのように設定してみます。

  1. 終端記号: 0~9, b0~b15
  2. 非終端記号(1引数): log2, ^2, abs
  3. 非終端記号(2引数): +, *, -, /

適合度は十回2048をプレイしたうちの上位三回の平均とします。その他のパラメータは以下の通り。

  1. 遺伝子数: 1000
  2. 交叉確率: 75%
  3. 突然変異率: 5%
  4. 世代数: 無制限

ソースコード2048ai/gp.cpp at gp-full · u-e-d/2048ai · GitHubにあります。

結果

スクロールして成長具合をお楽しみください。

第一世代目の評価関数

(e_mul (e_log (e_abs (e_b7))) (e_add (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_0)) (e_po2 (e_sub (e_abs (e_log (e_b0))) (e_mul (e_po2 (e_b3)) (e_add (e_log (e_add (e_mul (e_abs (e_b1)) (e_7)) (e_div (e_log (e_mul (e_1) (e_po2 (e_0)))) (e_4)))) (e_b13)))))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_add (e_mul (e_b2) (e_mul (e_b5) (e_b2))) (e_b15)))))))) (e_b3)) (e_po2 (e_div (e_b13) (e_sub (e_abs (e_div (e_b4) (e_b3))) (e_b5))))) (e_b6))) (e_8)))

スコア: 12995(2048も出来ない程度)

第54世代目

(e_mul (e_log (e_abs (e_b7))) (e_add (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_0)) (e_po2 (e_div (e_abs (e_0)) (e_mul (e_sub (e_b14) (e_b14)) (e_mul (e_po2 (e_sub (e_b10) (e_b3))) (e_div (e_1) (e_sub (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_b4) (e_b15)))))) (e_log (e_sub (e_po2 (e_div (e_b14) (e_abs (e_0)))) (e_po2 (e_mul (e_b11) (e_add (e_add (e_b15) (e_po2 (e_b4))) (e_b14))))))) (e_mul (e_po2 (e_log (e_div (e_b12) (e_b14)))) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_div (e_add (e_2) (e_sub (e_abs (e_sub (e_add (e_log (e_po2 (e_sub (e_b10) (e_4)))) (e_div (e_b12) (e_b2))) (e_b12))) (e_add (e_abs (e_mul (e_b5) (e_abs (e_abs (e_7))))) (e_div (e_abs (e_0)) (e_b14))))) (e_abs (e_abs (e_add (e_abs (e_b11)) (e_abs (e_mul (e_div (e_b7) (e_po2 (e_add (e_log (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3))))))) (e_po2 (e_div (e_abs (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_abs (e_sub (e_add (e_log (e_po2 (e_b3))) (e_div (e_b12) (e_po2 (e_po2 (e_3))))) (e_b12))))) (e_b3)) (e_po2 (e_div (e_b1) (e_sub (e_abs (e_abs (e_po2 (e_8)))) (e_abs (e_0)))))) (e_b11)))) (e_mul (e_div (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11))) (e_div (e_log (e_b8)) (e_div (e_add (e_6) (e_b9)) (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_po2 (e_po2 (e_po2 (e_sub (e_3) (e_mul (e_po2 (e_sub (e_b2) (e_b8))) (e_abs (e_po2 (e_b14)))))))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_add (e_abs (e_mul (e_abs (e_log (e_b0))) (e_9))) (e_2))))) (e_po2 (e_po2 (e_po2 (e_b12))))))) (e_b3))))) (e_b11))))))) (e_0)))))))))) (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11)))))))))) (e_add (e_5) (e_log (e_abs (e_mul (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_5)) (e_po2 (e_div (e_abs (e_0)) (e_mul (e_sub (e_b14) (e_b2)) (e_mul (e_po2 (e_sub (e_b10) (e_b3))) (e_div (e_1) (e_b15))))))) (e_add (e_b3) (e_log (e_abs (e_mul (e_sub (e_po2 (e_5)) (e_b1)) (e_mul (e_po2 (e_mul (e_9) (e_b2))) (e_b8))))))))) (e_b3)) (e_abs (e_mul (e_sub (e_9) (e_b11)) (e_mul (e_po2 (e_log (e_b4))) (e_b8))))) (e_b11))) (e_mul (e_po2 (e_log (e_b4))) (e_b8))))))))) (e_b3)) (e_po2 (e_div (e_b13) (e_mul (e_sub (e_po2 (e_log (e_add (e_mul (e_b14) (e_1)) (e_log (e_mul (e_mul (e_abs (e_div (e_div (e_b12) (e_add (e_b4) (e_b10))) (e_b12))) (e_b6)) (e_add (e_add (e_2) (e_add (e_b11) (e_mul (e_add (e_add (e_mul (e_b1) (e_b11)) (e_mul (e_b2) (e_sub (e_b1) (e_abs (e_abs (e_log (e_po2 (e_8)))))))) (e_div (e_sub (e_b3) (e_b6)) (e_abs (e_b11)))) (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_b2)) (e_div (e_add (e_add (e_po2 (e_b11)) (e_po2 (e_sub (e_abs (e_log (e_b0))) (e_mul (e_po2 (e_b3)) (e_add (e_log (e_log (e_sub (e_abs (e_po2 (e_sub (e_po2 (e_3)) (e_b4)))) (e_mul (e_b2) (e_mul (e_log (e_mul (e_log (e_b0)) (e_po2 (e_0)))) (e_div (e_add (e_add (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_abs (e_0))) (e_add (e_6) (e_b9))))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_sub (e_mul (e_b4) (e_0)) (e_b14)))))) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_add (e_sub (e_add (e_abs (e_7)) (e_b3)) (e_b14)) (e_abs (e_b11)))))) (e_po2 (e_div (e_abs (e_po2 (e_sub (e_b10) (e_4)))) (e_9)))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_log (e_7)) (e_mul (e_po2 (e_log (e_po2 (e_sub (e_add (e_abs (e_mul (e_b6) (e_sub (e_b10) (e_4)))) (e_2)) (e_po2 (e_log (e_po2 (e_mul (e_9) (e_4))))))))) (e_b8))))))) (e_b3))))))) (e_b13)))))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_add (e_mul (e_2) (e_b15)) (e_b15)))))) (e_b15)))))))) (e_div (e_log (e_log (e_log (e_7)))) (e_abs (e_mul (e_3) (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3))))))))))))))) (e_8)) (e_abs (e_abs (e_po2 (e_8)))))))) (e_b11))) (e_div (e_log (e_log (e_7))) (e_div (e_add (e_6) (e_b9)) (e_mul (e_sub (e_2) (e_log (e_add (e_b12) (e_0)))) (e_b3))))))

score: 35918(2048とかできるかな)

第96世代(打ち切り)

(e_mul (e_log (e_abs (e_b7))) (e_add (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_0)) (e_po2 (e_div (e_abs (e_0)) (e_mul (e_sub (e_b14) (e_b2)) (e_mul (e_po2 (e_abs (e_abs (e_add (e_po2 (e_sub (e_b10) (e_4))) (e_8))))) (e_div (e_1) (e_sub (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_b4) (e_b15)))))) (e_log (e_sub (e_po2 (e_div (e_b14) (e_abs (e_0)))) (e_po2 (e_mul (e_b11) (e_add (e_add (e_b15) (e_po2 (e_b4))) (e_b14))))))) (e_mul (e_po2 (e_log (e_div (e_b12) (e_b14)))) (e_div (e_add (e_add (e_log (e_0)) (e_po2 (e_add (e_add (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_abs (e_0))) (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_sub (e_b10) (e_4))) (e_8)))) (e_b1)) (e_mul (e_po2 (e_div (e_div (e_mul (e_mul (e_div (e_mul (e_2) (e_b3)) (e_8)) (e_b7)) (e_b15)) (e_add (e_b4) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_mul (e_sub (e_5) (e_9)) (e_po2 (e_5)))) (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_po2 (e_abs (e_2)))) (e_po2 (e_sub (e_abs (e_log (e_b0))) (e_mul (e_po2 (e_b3)) (e_add (e_log (e_log (e_sub (e_abs (e_po2 (e_0))) (e_mul (e_b2) (e_mul (e_b5) (e_div (e_sub (e_po2 (e_3)) (e_div (e_b0) (e_div (e_abs (e_6)) (e_log (e_abs (e_mul (e_sub (e_9) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_mul (e_9) (e_4))))) (e_b8)))))))) (e_b3))))))) (e_po2 (e_div (e_b13) (e_sub (e_abs (e_abs (e_po2 (e_8)))) (e_b5))))))))) (e_abs (e_abs (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_b4) (e_b15))))))))) (e_b3)) (e_po2 (e_po2 (e_b3))))))) (e_b1)) (e_mul (e_po2 (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11)))) (e_div (e_1) (e_b15)))))) (e_b12))) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_add (e_log (e_sub (e_abs (e_po2 (e_sub (e_add (e_5) (e_b7)) (e_b4)))) (e_mul (e_b2) (e_mul (e_b5) (e_div (e_sub (e_po2 (e_3)) (e_div (e_b0) (e_div (e_abs (e_6)) (e_log (e_abs (e_mul (e_sub (e_9) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_mul (e_9) (e_4))))) (e_b8)))))))) (e_b3)))))) (e_log (e_mul (e_mul (e_abs (e_div (e_div (e_mul (e_mul (e_4) (e_b7)) (e_b15)) (e_add (e_b2) (e_b10))) (e_b12))) (e_b6)) (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_sub (e_b10) (e_4))) (e_8)))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_b2)))) (e_div (e_1) (e_b15))))) (e_b1)) (e_mul (e_abs (e_5)) (e_div (e_1) (e_b15))))) (e_po2 (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_0)) (e_po2 (e_div (e_po2 (e_sub (e_abs (e_log (e_b0))) (e_mul (e_po2 (e_b3)) (e_add (e_log (e_log (e_sub (e_abs (e_po2 (e_sub (e_add (e_5) (e_b7)) (e_b4)))) (e_mul (e_b2) (e_mul (e_b5) (e_div (e_sub (e_po2 (e_3)) (e_div (e_b0) (e_div (e_abs (e_6)) (e_log (e_abs (e_mul (e_sub (e_9) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_mul (e_9) (e_4))))) (e_b8)))))))) (e_b3))))))) (e_div (e_1) (e_b15)))))) (e_mul (e_sub (e_b14) (e_b2)) (e_log (e_b3)))))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_sub (e_abs (e_sub (e_abs (e_abs (e_add (e_po2 (e_sub (e_7) (e_4))) (e_8)))) (e_4))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_mul (e_9) (e_b2))))) (e_b8))))))))) (e_b3)) (e_po2 (e_div (e_mul (e_log (e_abs (e_b7))) (e_add (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_2))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_add (e_add (e_log (e_mul (e_log (e_abs (e_b7))) (e_add (e_log (e_po2 (e_b3))) (e_div (e_b12) (e_b2))))) (e_po2 (e_div (e_abs (e_0)) (e_mul (e_sub (e_b1) (e_b14)) (e_mul (e_div (e_add (e_b1) (e_sub (e_2) (e_add (e_log (e_sub (e_po2 (e_div (e_b14) (e_abs (e_log (e_b3))))) (e_po2 (e_mul (e_b11) (e_add (e_log (e_div (e_add (e_2) (e_sub (e_abs (e_sub (e_add (e_log (e_po2 (e_b7))) (e_div (e_b12) (e_b2))) (e_b6))) (e_add (e_mul (e_b14) (e_b11)) (e_log (e_mul (e_mul (e_abs (e_div (e_div (e_mul (e_mul (e_div (e_mul (e_2) (e_b3)) (e_b10)) (e_b7)) (e_b15)) (e_add (e_b4) (e_b10))) (e_b12))) (e_b6)) (e_add (e_add (e_b15) (e_add (e_sub (e_b4) (e_add (e_b15) (e_po2 (e_b4)))) (e_mul (e_add (e_add (e_sub (e_sub (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_0)) (e_b1)) (e_add (e_b4) (e_b10)))) (e_sub (e_5) (e_add (e_log (e_add (e_0) (e_div (e_log (e_mul (e_b15) (e_log (e_2)))) (e_4)))) (e_b12)))) (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11)))) (e_log (e_mul (e_b13) (e_b10)))) (e_mul (e_b2) (e_sub (e_b1) (e_abs (e_abs (e_log (e_po2 (e_b14)))))))) (e_div (e_sub (e_b3) (e_b6)) (e_abs (e_po2 (e_sub (e_b10) (e_b15)))))) (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_1) (e_b15)))))))) (e_div (e_log (e_log (e_log (e_7)))) (e_abs (e_7))))))))) (e_8))) (e_log (e_sub (e_b1) (e_div (e_b13) (e_b12))))))))) (e_po2 (e_div (e_b13) (e_sub (e_b12) (e_log (e_po2 (e_b3))))))))) (e_abs (e_abs (e_b2)))) (e_b14)))))) (e_add (e_log (e_mul (e_sub (e_b14) (e_b2)) (e_mul (e_po2 (e_sub (e_b10) (e_b3))) (e_abs (e_0))))) (e_log (e_abs (e_mul (e_sub (e_9) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_add (e_add (e_po2 (e_b11)) (e_po2 (e_sub (e_abs (e_log (e_b0))) (e_mul (e_po2 (e_b3)) (e_add (e_log (e_log (e_sub (e_abs (e_po2 (e_sub (e_add (e_5) (e_b7)) (e_b4)))) (e_mul (e_b2) (e_mul (e_log (e_mul (e_log (e_b0)) (e_po2 (e_0)))) (e_div (e_add (e_add (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_abs (e_0))) (e_add (e_6) (e_b9))))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_sub (e_mul (e_b6) (e_0)) (e_b14)))))) (e_div (e_1) (e_b15))))) (e_add (e_mul (e_b14) (e_b11)) (e_log (e_mul (e_mul (e_abs (e_div (e_div (e_b12) (e_add (e_b4) (e_b10))) (e_b12))) (e_b6)) (e_add (e_add (e_b15) (e_add (e_sub (e_b10) (e_mul (e_b9) (e_b10))) (e_mul (e_add (e_add (e_log (e_div (e_div (e_b2) (e_abs (e_b3))) (e_mul (e_b15) (e_2)))) (e_mul (e_b2) (e_sub (e_b1) (e_0)))) (e_div (e_sub (e_b3) (e_b6)) (e_abs (e_b11)))) (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_div (e_div (e_b12) (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11)))) (e_b11))) (e_div (e_1) (e_log (e_b8))))))))) (e_div (e_log (e_log (e_log (e_7)))) (e_abs (e_mul (e_3) (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))))))))))) (e_po2 (e_div (e_abs (e_po2 (e_sub (e_b10) (e_4)))) (e_9)))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_log (e_7)) (e_mul (e_po2 (e_log (e_po2 (e_sub (e_add (e_abs (e_mul (e_b6) (e_sub (e_b10) (e_po2 (e_add (e_abs (e_2)) (e_div (e_mul (e_log (e_abs (e_b7))) (e_add (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_0)) (e_po2 (e_abs (e_div (e_1) (e_div (e_log (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3))))))) (e_b12)))))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_sub (e_9) (e_b11)) (e_mul (e_po2 (e_log (e_b4))) (e_b8))))))))) (e_b3)) (e_po2 (e_log (e_mul (e_div (e_b12) (e_7)) (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_sub (e_add (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_log (e_add (e_b10) (e_div (e_mul (e_b5) (e_abs (e_2))) (e_add (e_0) (e_log (e_2))))))) (e_add (e_add (e_log (e_abs (e_mul (e_sub (e_po2 (e_5)) (e_b1)) (e_mul (e_po2 (e_mul (e_9) (e_b2))) (e_b8))))) (e_po2 (e_div (e_abs (e_po2 (e_add (e_sub (e_add (e_abs (e_b11)) (e_log (e_abs (e_add (e_po2 (e_8)) (e_b15))))) (e_po2 (e_3))) (e_b11)))) (e_mul (e_div (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11))) (e_div (e_log (e_b8)) (e_div (e_add (e_6) (e_b9)) (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_div (e_log (e_b6)) (e_abs (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_mul (e_div (e_abs (e_3)) (e_mul (e_sub (e_abs (e_abs (e_add (e_add (e_po2 (e_abs (e_0))) (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_sub (e_b10) (e_4))) (e_8)))) (e_b1)) (e_mul (e_div (e_log (e_log (e_7))) (e_div (e_add (e_6) (e_b9)) (e_mul (e_sub (e_2) (e_log (e_add (e_b12) (e_0)))) (e_b3)))) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_add (e_mul (e_b14) (e_b11)) (e_log (e_mul (e_mul (e_abs (e_div (e_div (e_mul (e_mul (e_div (e_mul (e_2) (e_b3)) (e_8)) (e_b7)) (e_b15)) (e_add (e_b4) (e_b10))) (e_b12))) (e_b6)) (e_add (e_add (e_b15) (e_add (e_sub (e_po2 (e_abs (e_3))) (e_mul (e_b9) (e_b10))) (e_mul (e_add (e_add (e_log (e_div (e_div (e_b2) (e_abs (e_b3))) (e_mul (e_b15) (e_2)))) (e_mul (e_b2) (e_sub (e_b1) (e_abs (e_abs (e_abs (e_2))))))) (e_div (e_sub (e_b3) (e_b6)) (e_abs (e_b11)))) (e_div (e_abs (e_0)) (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11))))))) (e_8))))))))) (e_mul (e_log (e_b2)) (e_po2 (e_log (e_add (e_mul (e_b14) (e_abs (e_0))) (e_log (e_mul (e_mul (e_abs (e_div (e_div (e_b12) (e_add (e_b4) (e_mul (e_log (e_abs (e_b7))) (e_add (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_mul (e_div (e_mul (e_sub (e_9) (e_b11)) (e_mul (e_po2 (e_log (e_b4))) (e_b8))) (e_mul (e_sub (e_abs (e_9)) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_b10)))) (e_po2 (e_div (e_abs (e_div (e_po2 (e_po2 (e_3))) (e_b11))) (e_9)))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_log (e_7)) (e_mul (e_po2 (e_log (e_po2 (e_sub (e_add (e_b1) (e_2)) (e_0))))) (e_b8))))))))) (e_b3)) (e_b14)) (e_b11))) (e_8))))) (e_b12))) (e_b6)) (e_add (e_add (e_b15) (e_add (e_sub (e_b10) (e_b3)) (e_mul (e_add (e_add (e_log (e_div (e_div (e_b2) (e_abs (e_b3))) (e_mul (e_b15) (e_2)))) (e_mul (e_b2) (e_sub (e_b1) (e_abs (e_abs (e_log (e_po2 (e_b14)))))))) (e_div (e_sub (e_b3) (e_b6)) (e_abs (e_b11)))) (e_div (e_2) (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_1) (e_b15)))))))) (e_log (e_po2 (e_po2 (e_po2 (e_3))))))))))))))) (e_b1)) (e_mul (e_0) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_add (e_sub (e_b10) (e_b14)) (e_abs (e_b11)))))) (e_po2 (e_div (e_abs (e_div (e_div (e_b0) (e_b14)) (e_b11))) (e_9)))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_log (e_7)) (e_mul (e_po2 (e_7)) (e_b8))))))))) (e_b3)))) (e_8)))) (e_b1)) (e_mul (e_b11) (e_po2 (e_b12))))) (e_b3))))) (e_b11))))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_abs (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_mul (e_9) (e_4))))) (e_b8))))))))) (e_b3)) (e_po2 (e_div (e_b13) (e_sub (e_abs (e_abs (e_po2 (e_8)))) (e_b5))))) (e_b11))) (e_8)) (e_abs (e_log (e_po2 (e_po2 (e_sub (e_3) (e_7)))))))) (e_8)))) (e_b1)) (e_div (e_b15) (e_log (e_mul (e_po2 (e_add (e_b8) (e_b6))) (e_po2 (e_7))))))))))) (e_b11))) (e_8))) (e_b11))))))) (e_2)) (e_po2 (e_log (e_po2 (e_mul (e_9) (e_4))))))))) (e_b8))))))) (e_b3))))))) (e_b13)))))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_add (e_mul (e_2) (e_b15)) (e_b15))))))))) (e_b8))))))))))) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_b10)))) (e_po2 (e_div (e_abs (e_div (e_div (e_b0) (e_b14)) (e_b11))) (e_9)))) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_log (e_7)) (e_mul (e_po2 (e_log (e_po2 (e_sub (e_add (e_abs (e_mul (e_b6) (e_9))) (e_2)) (e_0))))) (e_b8))))))))) (e_b3)) (e_b14)) (e_b11))) (e_8))) (e_mul (e_po2 (e_div (e_abs (e_0)) (e_log (e_sub (e_po2 (e_div (e_b14) (e_abs (e_0)))) (e_b7))))) (e_div (e_1) (e_b15))))))))))))))))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_b9)))) (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11)))))) (e_po2 (e_log (e_add (e_sub (e_b10) (e_b14)) (e_abs (e_b11)))))) (e_1)) (e_add (e_po2 (e_2)) (e_log (e_abs (e_mul (e_log (e_7)) (e_mul (e_po2 (e_log (e_po2 (e_b9)))) (e_b8))))))))) (e_add (e_5) (e_log (e_abs (e_mul (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_5)) (e_po2 (e_div (e_abs (e_0)) (e_mul (e_sub (e_b14) (e_b2)) (e_mul (e_po2 (e_sub (e_b10) (e_b3))) (e_abs (e_0))))))) (e_div (e_div (e_b12) (e_b14)) (e_b11))))) (e_b3)) (e_abs (e_mul (e_sub (e_9) (e_div (e_div (e_b12) (e_mul (e_sub (e_b9) (e_b1)) (e_b14))) (e_b11))) (e_mul (e_po2 (e_log (e_b4))) (e_b8))))) (e_b11))) (e_mul (e_po2 (e_log (e_b4))) (e_b8))))))) (e_b15))))) (e_add (e_log (e_0)) (e_po2 (e_div (e_abs (e_0)) (e_mul (e_sub (e_b14) (e_b2)) (e_mul (e_po2 (e_sub (e_b10) (e_b3))) (e_div (e_1) (e_sub (e_mul (e_div (e_abs (e_0)) (e_mul (e_abs (e_2)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_1) (e_b15))))) (e_9)) (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11))))))))))) (e_add (e_abs (e_2)) (e_div (e_div (e_b12) (e_b14)) (e_b11)))))))))) (e_add (e_5) (e_log (e_abs (e_mul (e_po2 (e_add (e_sub (e_add (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_5)) (e_po2 (e_div (e_abs (e_0)) (e_mul (e_sub (e_b14) (e_b2)) (e_mul (e_po2 (e_sub (e_b10) (e_b3))) (e_div (e_1) (e_b15))))))) (e_add (e_b3) (e_log (e_abs (e_mul (e_sub (e_po2 (e_5)) (e_b1)) (e_mul (e_po2 (e_mul (e_9) (e_b2))) (e_b8))))))))) (e_b3)) (e_abs (e_mul (e_sub (e_9) (e_b11)) (e_mul (e_po2 (e_log (e_b4))) (e_b8))))) (e_b11))) (e_mul (e_po2 (e_log (e_b4))) (e_b8))))))))) (e_b3)) (e_po2 (e_div (e_b13) (e_mul (e_sub (e_po2 (e_log (e_add (e_mul (e_b14) (e_1)) (e_log (e_mul (e_mul (e_po2 (e_log (e_po2 (e_mul (e_9) (e_4))))) (e_b8)) (e_add (e_add (e_2) (e_add (e_b11) (e_mul (e_add (e_add (e_b2) (e_mul (e_b2) (e_sub (e_b1) (e_abs (e_abs (e_log (e_po2 (e_8)))))))) (e_div (e_sub (e_b3) (e_b6)) (e_abs (e_b11)))) (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_sub (e_abs (e_abs (e_add (e_po2 (e_abs (e_0))) (e_mul (e_div (e_abs (e_0)) (e_mul (e_sub (e_abs (e_abs (e_add (e_po2 (e_sub (e_b10) (e_4))) (e_8)))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_1) (e_b15))))) (e_po2 (e_log (e_add (e_mul (e_b14) (e_b11)) (e_log (e_mul (e_mul (e_abs (e_div (e_div (e_b12) (e_add (e_b4) (e_b10))) (e_b12))) (e_b6)) (e_add (e_add (e_b15) (e_add (e_sub (e_abs (e_div (e_po2 (e_7)) (e_add (e_add (e_log (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3))))))) (e_po2 (e_div (e_abs (e_po2 (e_add (e_b15) (e_b11)))) (e_mul (e_div (e_add (e_mul (e_b14) (e_b1)) (e_div (e_div (e_b12) (e_b14)) (e_b11))) (e_mul (e_sub (e_sub (e_b1) (e_abs (e_log (e_div (e_1) (e_0))))) (e_b1)) (e_mul (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3)))))) (e_div (e_2) (e_b15))))) (e_b11))))) (e_add (e_0) (e_log (e_abs (e_mul (e_abs (e_b1)) (e_mul (e_po2 (e_log (e_log (e_sub (e_b1) (e_4))))) (e_b8))))))))) (e_mul (e_b9) (e_b10))) (e_mul (e_add (e_add (e_log (e_div (e_div (e_b2) (e_abs (e_b3))) (e_mul (e_b15) (e_2)))) (e_mul (e_b2) (e_sub (e_b1) (e_abs (e_abs (e_log (e_po2 (e_b14)))))))) (e_div (e_sub (e_b3) (e_b6)) (e_abs (e_b11)))) (e_div (e_abs (e_b12)) (e_mul (e_sub (e_abs (e_b11)) (e_b1)) (e_mul (e_po2 (e_div (e_div (e_b12) (e_add (e_abs (e_b8)) (e_div (e_div (e_b12) (e_b14)) (e_b11)))) (e_b11))) (e_div (e_1) (e_log (e_b8))))))))) (e_div (e_log (e_log (e_log (e_7)))) (e_abs (e_mul (e_3) (e_div (e_div (e_b12) (e_b14)) (e_b11))))))))))))))) (e_b1))))))) (e_div (e_b4) (e_abs (e_mul (e_3) (e_po2 (e_log (e_po2 (e_po2 (e_po2 (e_3))))))))))))))) (e_8)) (e_abs (e_abs (e_po2 (e_8)))))))) (e_b11))) (e_div (e_log (e_log (e_7))) (e_div (e_add (e_6) (e_b9)) (e_mul (e_sub (e_2) (e_log (e_add (e_b12) (e_0)))) (e_b3))))))

score: 41837

だいたい収束してきた感じですね。

という事でグラフを貼っておきます。
f:id:n-karasu:20140607022422p:plain

まとめ

評価関数職人の呪いからは逃れる事は出来ない。

遺伝的プログラミングでは交叉の仕方や遺伝子選択アルゴリズム、そして終端記号の選び方に大きく依存する事が分かりました。すなわち、都合の良いパラメータを見つけ出すパラメータを見つける事で最強のAIが作れそうだという知見が得られたわけですね。

暇があったら終端記号に手を入れたバージョンについても公開したいと考えています。

ちなみに実践では探索アルゴリズム手書きしたせいで全く本番で性能が上がらず、敗北を喫しました。

参考図書

遺伝的プログラミング入門

遺伝的プログラミング入門

遺伝的アルゴリズム - Wikipedia