Garev Project

〜遺伝的アルゴリズムでオセロを強くする〜

注意:
 以下の内容は、遺伝的アルゴリズム(GA)をあまりよく知らない素人が 行ったシミュレーションの結果です。これを元に遺伝的アルゴリズムについて 何か知ったつもりになったり、他の人に知ったかぶりした時などに 起きた損害、かいた恥などには一切責任を取りませんのであしからず。


イントロダクション

 プログラムは小学生の頃から組んでいたが、まともに組み出したのは 中学生くらいからだろうか。当時プログラムという趣味はかなり マニアックで、「プログラマー=オタク」という図式がほぼ成り立っている頃 だった。僕らは非力なコンピューターを駆使し、ゲームを作ったり パズルを解くプログラムを作って速度を競ったりといろいろやったものだ。

 さて、プログラムというと、普通考えるのはアルゴリズムの事だろう。 アルゴリズムとはある問題を解くとき場合の手順を抽象化したもので、 プログラムで表現するとほとんど整数を扱うコードになる。 ちなみにこの研究室に入ってから使っている数値計算では、ほとんど 浮動少数を使っている。さて高校生の時、僕が一番はまったのは 再帰プログラムによるアルゴリズムであった。再帰とは、関数が もう一度自分を呼ぶプログラムの事で、迷路などのパズルを解いたり、 コンピューターの思考ルーチンを表現するのに有効なアルゴリズムだ。 僕はプログラムが勝手にパズルを解くのが うれしくて、いろんなプログラムを組んだものだ。 その中に進化するオセロ、というものがあった。

 およそコンピューターの思考ルーチンというと、まずオセロの 思考ルーチンを例に取る場合が多い。将棋やチェスと違って必ず有限手数(60手) で勝負がつき、囲碁と違って形勢判断がしやすいからだろう。 そんなわけで、僕も再帰ルーチンを使ってオセロの思考ルーチンを 組んでみた。そして、単にオセロを組むだけで飽き足らず、遺伝アルゴリズムの 原理を使って勝手にコンピューターが強くなる、という事に挑戦したのだった。 時に高校二年。現在の「Garev Project」につながるプログラムである。

原理

 後に詳述するが、オセロの思考ルーチンの基本は形勢判断用の ポイントマップに依存する。ポイントマップとは、端はなるべく 取ったほうが良い、端から2番目はあまり取らないほうが 良い等の情報を数値化したマップで、オセロであれば 対称性から10個の数字を用いる。この10個の数字の組み合わせにより 思考ルーチンの強さが決まるわけだ。

 そこで、最初に適当な数字の組み合わせからスタートし、 そこからミューテーションさせた子供とオセロの勝負をさせて 勝った方をまた親とする。これをずっと繰り返していれば、最後には 強い思考ルーチンが残るはず、という理屈であった。 10個の数字を遺伝子とみなし、それぞれの思考ルーチンを 生命だと思えば、勝負に勝てなくては生き残れない弱肉強食の 世界を表現したことになる。ダーウィニズムに基づいた サバイバルをさせることで最適な10個の数字列を得るという 遺伝アルゴリズム(Genetic Algorithms、以下GAと呼ぶ) になるわけだ。もちろん高校生の時にはGA等という言葉は知らず、 自己訓練プログラム(英訳するなら Self Training Agentとでもなるだろうか) と呼び、夜プログラムをスタートして、朝を楽しみにしながら眠りについた。

結果

 さて、目が覚め、ファンの音からパソコンが動きつづけていることを 知り、オセロプログラムを走らせていたことを思い出す。 わくわくしながら結果を見ると・・・およそ強いとは思えない 数字が並んでいた。実際に戦ってみると非常に弱い。そんなはずは・・・と 思い、プログラムのログを調べてみると興味深いことがわかった。

 しばらく戦国の世が続いたかと思うと、しばらく勝ちつづける 強者があらわれる。しかし数連勝したあと暫定王者にのみ 勝てる弱者が現れ、再び戦国の世に戻ってしまうのだ。GAの 言葉を使って表現するなら単一の種からなる生態系は 外乱(Mutation)に弱いということだろう。さらにオセロの思考ルーチン (ミニマックス法を用いていた)が決定論的であったのも災いしたのだろう。 どんなに強いエージェントが生まれても、決定論であるが故に必ずそいつにだけ勝てる 弱者の存在があるのだ。

そして大学院へ

 当時の僕はこう反省した。まず、勝ち抜きであったのが良くない。 リーグ戦にして、最も好成績を残したものを勝者とするべきだろう。 また、思考ルーチンが決定論的であったのも良くないので、 ある程度の幅を持たせた、ランダムの要素を加えた プログラミングが必要だ。いつかそんなプログラムを作ろうと 思いつつ、大学受験が始まり、このプロジェクトはそのままに なってしまった。


・・・・続く・・・

トップページへ戻る