Mac OS 10.9上でのHaskellゲーム開発環境を整えるまで
そんなこんなでゲームを書く事になって、free-gameのようなライブラリも有るとの事なのでHasellでゲームを作ろうとして環境構築に時間がかかった話。
普通にプロジェクトを立ち上げてライブラリを整備する
まずはお約束の呪文
git init
今時はどの言語もグローバル環境(/usr/libとか)に言語のライブラリを配置する事が少なくなりましたね。
Haskellではcabal sandboxを使うとよいそうです。*1
cabal sandbox init
で、この上でcabal installをすればプロジェクトローカルな場所にインストールしてくれるそうです。
cabal install free-game
あとはどっかのプロジェクトから.cabalファイルをパクって自分のプロジェクト仕様にしましょう。
何が起きた
で、幸せになれたなら世界は平和なのですが、道を外れた人に厳しいのはどの世界も同じな様で。いくつかの問題が出ました。
- cabalが古いのでsandbox機能が無い
- iconvが無いそうだ
- そもそもfree-gameのインストールに失敗した
直すのにやたら時間がかかったのでメモ
cabalが古い?
cabal update
cabal install cabal-update
で十分かと思ったらghcも古い。macportsのhaskell-platformがずいぶん古い。仕方無いので直接haskell-platformを入れようとした。
sudo port uninstall --follow-dependencies haskell-platform
iconvが無い
_iconvという関数がないとldさんから怒られる問題が有りまして。
Macportsを使ってインストールされるlibiconvと元々のlibiconvとは名前が変わっているそうだ。*3
この場合は/usr/libの方のiconvを読んでもらえば良いので、常にそっちがパスにくるように設定する。正確には、~/.cabal/configに以下の様に書き加える。
program-default-options ghc-options: -L/usr/lib
ライブラリ入らんやん
どうも入っているOpenGLRawが1.5.0.0で必要なのが1.4.0.0らしい。バージョン名を指定しながらインストール出来るのは良い時代ですね。プロジェクトローカルにcabal install。
[ 3 of 200] Compiling Graphics.Rendering.OpenGL.Raw.EXT.SceneMarker ( src/Graphics/Rendering/OpenGL/Raw/EXT/SceneMarker.hs, dist/build/Graphics/Rendering/OpenGL/Raw/EXT/SceneMarker.o ) src/Graphics/Rendering/OpenGL/Raw/EXT/SceneMarker.hs:30:44: parse error on input `glBeginScene'
なんとC言語っぽいところでコンパイルエラー。この問題はとうの昔に報告されていて、Macのgccが内部的にはclang(!)で有る事に由来する問題だそうです。*4
解決法も示されていて、Macportsとかでインストールしたgccをプリプロセッサに使うようにghcを書き換えてしまえば良いそうです。
すなわち、/Library/Frameworks/GHC.framework/Versions/Current/usr/lib/ghc-7.8.3/settingsにある(バージョン次第)設定ファイルを
("C compiler command","/usr/bin/gcc") ("Haskell CPP command","/usr/bin/gcc")
から
("C compiler command","/opt/local/bin/gcc") ("Haskell CPP command","/opt/local/bin/gcc")
に書き換えてやれば良い事になります。(Macportsでgccを入れたなら)
私の環境ではこれでやっとこ入りました。
遺伝的アルゴリズムで画像をベジェ曲線の塊に近似する奴
これってGAじゃなくね?ってことで私が本当のGAを見せてやりますよしたら死んだ(Cross Originなんとかは滅べ)
ということで供養
Macのシステム環境設定をコマンドラインの環境設定に反映する奴
これは?
前日書いた奴の逆。システム環境設定をコマンドラインに反映するツール。
不思議な事に、rsyncやwgetなどといったツールは、OSの基本設定とかあまり読んでくれないようです。なのでシステム環境設定で「プロキシの自動設定」とか設定していても、wgetはダイレクト接続しようとしてくる訳ですね。せめてブラウザ的にシステムの設定を読むオプションぐらい有っても良い気はするのですが。
さて、ではプロキシの自動設定によって設定されるプロキシをHTTP_PROXYなりに設定すれば良いじゃんって話なのかというとそうでも無いようで、プロキシの自動設定の仕様では、案外(wgetから見たら)楽ではない事が分かります。自動設定プロキシは、実際には"http://wpad/wpad.dat"というURLのファイルを探し、存在するならば取得します。ここで問題なのは、wpad.datはJavascriptで書かれている上に、「与えたURLに対して適切なプロキシのリストを返すスクリプト」である事です。よってJSの実行環境を持たない単純なコマンド程度ではどうしようも無い訳ですね。ネイティブアプリとかでは対応しているくらいですからOSの仕事です。
とりあえず適当なURLからそれに使われるプロキシの一覧はMacのフレームワークを使えば取れるので、せめて一般的なプロキシ設定からHTTP_PROXYを設定するようなのを書いた。
使う
scwrap cmd [cmdargs..]
cmdをenvとして実行すると、(設定されているなら)HTTP_PROXYが上書きされていると思います。
こまめにネットワーク環境を変更する人とかは、毎回HTTP_PROXYを設定しなくて済むので楽になると思います。
ネットワーク環境をコマンドラインから設定する
Macではプロキシや使用するインターフェース(Eithernetとかwifiとか)などの設定を、全て「システム環境設定.app」の「ネットワーク」で管理します。ここで行う設定は、CocoaアプリケーションやChromeなどのシステムの設定を参照するアプリケーションには自動的に反映されます。
また、この設定画面では「ネットワーク環境」という機能を用いて、複数の設定を名前を付けて管理する事が出来ます。また、ネットワーク環境は、メニューバーのリンゴから切り替える事が出来るようになっています。例えば、特定のサイトにアクセスするときだけプロキシの設定を変える必要が有るといった場合は、現在のネットワーク環境を複製し、プロキシの設定を変更したものを別途作成しておく事で、わざわざ環境設定でプロキシをオンオフしなくてもネットワーク環境を切り替えるだけで済みます。
この切り替えは環境設定.appとメニューバーのリンゴ以外に、scselectコマンドを用いる事でコマンドラインからでも行う事が出来ます。scselectは引数無しで実行した場合は存在するネットワーク環境の一覧を表示し、ネットワーク環境名を与える事でそれを設定してくれます。
scselect [location-name]
関連するコマンドにscutilという物が有り、環境設定.appと同じような機能を持つようですので、気が向いたら記事にするかもしれません。また、SystemConfiguration.frameworkが対応するフレームワークだそうです。
ついでに、だいぶ前にwifiネットワーク名の変化を検知してネットワーク環境の切り替えを行うアプリケーションを作ったのでここで紹介しておきます。u-e-d/AngelSwitcher · GitHub
2048のAIを書かなかった話。あるいは遺伝的プログラミングの話
序
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と3は確率低めにして、2をメインで行う事が多いようです。
交叉とは、普通の遺伝子の話ではお互いに遺伝子を入れ替える話でした。遺伝的プログラミングでもそうです。先ほど言った通りプログラムは木ですので、一部を切り出してもプログラムになります。そこで、二つの木から、交換する箇所を選んで取り替えてもそれぞれは全く新しい木になりプログラムとして成立します。
交叉の方法にもいろいろ有るようですが、最も単純なのが木の節がすべて一様に選択される確率を持つ普通の交叉なのでソレを採用するのがよいのではないでしょうか。他の方法は後述します。
1には優秀な遺伝子を残す狙いが有りますが、確率を高める事には探索に意味を無くす点、3を高めるとランダム探索と相違が無くなる点を考えれば、基本的に2が90%で3が1%とかの確率設定が目安のようです。
遺伝子の選択とか
適当に良さげな遺伝子を選択すると言いましたが、どうするのが良いのでしょう。いくつか紹介します。
全体の適合度の構成割合をそのまま選択確率を見なす方法が有ります。ある遺伝子iの適合度をfiと呼ぶならばfi/Σfjを選択確率とすれば良い訳ですね。この手法は、ある値が突出しやすい場合に使うと過学習の原因となりますが、均一の場合はあまり優秀でない遺伝子もたまに選択できる点は元の遺伝子の仕組みに近いですね。
トーナメント方式と呼ばれる方法は、ランダムに選んだ集団の中から最も優秀な遺伝子を選択する手法です。優秀な遺伝子の選択されやすさを手動でコントロールできる点が強みですね。本質を見失っている気もしますが。また、N個の集団から一位を選び出した集団からトーナメントを行う段階的な手法も有るようです。
ほかにもいくつかはwikipediaとかに乗ってるらしいので適宜参照ください。
ブロート問題
一般に遺伝的プログラミングによる出力は、精度の上昇速度に対して木の大きさの爆発があまりにも大きくなりやすく、割に合わない状態になりやすいと言われています。この現象をブロートと言います。木の大きさと精度の相関は低い事を考えると、出来るだけ木の大きさを押さえた方が計算時間もメモリ消費も押さえられ、世代が稼げます。
なぜ木が爆発するのかと言えば、交叉の仕方に有ります。大きめの木の小さい箇所に大きな木を接ぎ木する事で木は大きく成長します。元々選択候補に上がるほど優秀な遺伝子ですので、小さい箇所を変えた程度では能力が落ちる事は少なく、結果的に大きい物が生き残りやすくなります。
交叉の仕方はいくつか提案されています。
- 前述の一様に枝を選択する特に名前のない交叉
- 二つの木の形についての共通箇所に注目し、その境界についてのみ交叉を行う「一様交叉」
- 二つの木の共通箇所内での同じ点で交叉を行う「一点交叉」
- 片方で選んだ部分木と同じ大きさの木を交換する「サイズ依存交叉」
- 深さに応じて選択確率が減少する「深さ依存交叉」
これらは、それぞれ木の大きさを制限した交叉の仕方ですので、木の生長は遅くなりますが、逆に十分な木の大きさが得られにくいため、初期に生成する木の大きさが重要となります。
本題
最初に言ったように今回は2048を最も上手く解くAIの評価関数を自動生成します。
盤面に対する評価関数ですので、引数には盤面を丸ごと与える事にしましょう。ここでは、2048の盤面を左上からジグザグにb0、b1…b15まで割り降る事にします。つまり終端記号(値)と非終端記号(演算子)はそれぞれこのように設定してみます。
- 終端記号: 0~9, b0~b15
- 非終端記号(1引数): log2, ^2, abs
- 非終端記号(2引数): +, *, -, /
適合度は十回2048をプレイしたうちの上位三回の平均とします。その他のパラメータは以下の通り。
- 遺伝子数: 1000
- 交叉確率: 75%
- 突然変異率: 5%
- 世代数: 無制限
ソースコードは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
だいたい収束してきた感じですね。
という事でグラフを貼っておきます。
まとめ
評価関数職人の呪いからは逃れる事は出来ない。
遺伝的プログラミングでは交叉の仕方や遺伝子選択アルゴリズム、そして終端記号の選び方に大きく依存する事が分かりました。すなわち、都合の良いパラメータを見つけ出すパラメータを見つける事で最強のAIが作れそうだという知見が得られたわけですね。
暇があったら終端記号に手を入れたバージョンについても公開したいと考えています。
参考図書
- 作者: 伊庭斉志
- 出版社/メーカー: 東京大学出版会
- 発売日: 2001/07
- メディア: 単行本
- クリック: 2回
- この商品を含むブログ (1件) を見る
重み付きrandom.choice
速度が必要になった結果、Pythonのコードを全部C++で書き直す羽目になった@Angelworm_です。
配列から要素をランダムに一個取ってくる様なコードってPythonならこう。
x = random.choice([1,2,3,4,5])
で、Cとかだとこんな感じだとか(rand()が良くないのは置いておいて)。 乱数を配列のサイズで割ったあまりがランダムなインデックスだ。みたいな。
int array[] = {1,2,3,4,5}; int x = array[rand() % sizeof(array)];
さてさて、このそれぞれの要素に重みが有って、ソレを踏まえてランダムに要素が欲しい。
重み付き乱択といえば、長さ1の直線を発生確率毎に切って、[0, 1)な乱数の落ちた所の要素を選ぶというのが一般的なアルゴリズムだそうだ*1。ならば実装すればいいじゃんって話だけど、C++11ならライブラリに有ったので使う*2。
対象の配列と確率列が別にある場合だとこんな感じかも。
template<class S, class T, class Gen> S w_choice(std::vector<S>& data, std::vector<T>& pr, Gen& g) { std::discrete_distribution<int> gen(pr.begin(), pr.end()); return data[gen(g)]; }
prで与えられた重み列に基づいてdataからいい感じに取ってくる感じ。