石取りゲームで遺伝的アルゴリズムの実験 その5

著者：北本 敦

公開日：2021/04/21

最終更新日：2021/04/20

カテゴリー：技術情報

タグ：石取りゲームで遺伝的アルゴリズムの実験／遺伝的アルゴリズム

北本です。

今回は、前回までに紹介したプログラムを実際に動かした結果を見てみることにします。

本連載のその1でアプリの画面の静止画だけ掲載していましたが、まず、アプリが実際に動いているところを動画で紹介したいと思います。石取りゲームを「1試合実行」「1個体分実行」「1世代分実行」の各パターンで実行する様子、「記録閲覧」ダイアログを表示し「全個体統計」および「遺伝子情報」のデータを閲覧する様子を録画しています。

では、実験結果の発表に参りたいと思いますが、その前にその1で述べた予想について振り返ってみます。

世代交代を繰り返すことで、残り石数(4の倍数+ 1)個の箇所はどのようになるか不明ですが、それ以外の箇所に関しては取る石数が必勝パターンに収束するだろうと予想していました。下表の通りです。

また、残り石数が少ない箇所ほど早い段階で収束していくだろうと予想しました。果たして、実際そのようになってくれたでしょうか？

一つの世代において、ある遺伝子にあるパラメータを持つ個体がどれぐらいの割合を占めているかを表した「全個体統計」のグラフをGIF動画で紹介します。

まず、第1世代から第20世代までの変遷です。

取り終わった石数17～19個(残り石数4～2個)の箇所については、第4～6世代で必勝パターンに収束しました(ここではある遺伝子の箇所が全個体同じパラメータになった状態を「収束」と呼ぶことにします)。そして、取り終わった石数13～15個(残り石数8～6個)の箇所も第5～9世代で収束しています。この収束の速さは私が想像していた以上でした。勝率も第5世代の時点で90%を超え、第11世代から長い期間97%台で遷移しています。

そして、石数9～11個(残り石数12～10個)の箇所は、第11～17世代で収束しますが、取り終わった石数11個の箇所が必勝パターンの「1」(赤色)ではなく「3」(青色)になってしまっています。

続いて、第1世代から第500世代までの変遷です。数が多いので画像の切り替えを高速にしており見づらいかもしれませんがご容赦ください。

先程必勝パターンでない「3」に収束してしまった取り終わった石数11個の箇所ですが、第42世代で突然変異によって「1」に変化した個体が現れます。その「1」が指数関数的に数を増やし第59世代で全個体を染めてしまいました。他にも、取り終わった石数1、2、5、6個の箇所が同様に一度必勝パターンでないパラメータに収束しますが、突然変異を契機に必勝パターンのパラメータに置き換わっていきます。実験前は今回のような単純な内容で突然変異が効果を発揮するのか疑問に思っていましたが、このような結果を見てなかなか侮れないことがわかりました。

では、結果をまとめてみます。

必勝パターンで収束するタイミングは下表のようになりました。

平均勝率については、抜粋で以下のようになりました。

対数関数的に値が増加していきます。第60世代で初めて99%を上回り、第108世代以降は99%を下回ることはありませんでした。99%台後半に入ったあたりからはあまり変化は見られません。突然変異が存在する関係で、平均勝率100%を叩き出すのはどうしても難しいです。

ここまで実験結果を紹介してきましたが、あくまでもこれは一回の試行の結果に過ぎません。実験をやり直してみると、収束するタイミングなどは異なった結果になってきます。早いときには30～40世代目くらい全箇所が必勝パターンに収束することもありました。今回取り上げた結果はかなり収束が遅かったパターンのように思われます。

以上で5回にわたってお送りしてきました連載は終わりとなります。実験の結果は大筋は予想通りとなりました。遺伝的アルゴリズムというものが一応は機能する様子を確認することはできましたが、題材がシンプルなのでその効果を劇的に感じたりするほどには至らなかったかもしれません。機会があれば、もっと複雑な題材でも試してみて、遺伝的アルゴリズムの真価を実感してみたいです。