TIM Labs

2013年7月アーカイブ

遺伝的アルゴリズムの例として、ナンバーエリア(四角に切れ)の自動生成を説明している。
前回は、新しい問題候補(染色体)を生み出す方法として、交叉の実装例を説明した。

しかし、交叉だけでは、両親に似たような子供しか生まれてこない。そして、これが延々と続くと、世代が進むごとに、ますます似たような染色体だらけになって、進化が停滞してしまう。

打開に必要なのは、イノベーションで、両親のどちらにも無かったような形質をもった染色体を作る必要がある。

ということで、次の問題(染色体)から、新しい突然変異した染色体を作ってみよう。

na-ga11.png

簡単な方法は、どこか適当に選んで、その付近の長方形を何個か消去し、再度分割してみることである。

これで、確かに、突然変異は起きるのだが、かなり都合が悪い状況になる。

この方法では、進化ではなく、退化した染色体ができる確率が極めて高い。生物界での突然変異は、ほとんどダメな染色外ができて、ほとんど環境に適応できずに死滅するはず。この方法だと、同じようなことになり、突然変異で環境により適した染色体ができる割合が著しく低くなってしまう。

これでも上手く突然変異を利用するには、大量の突然変異を起こし、ほんのわずかの環境に適応する染色体を見つけることだが、そのためには大量の突然変異を起こさねばならなくて、計算時間が膨大になる。また、個体数も増やしておいた方が可能性が増えるのであるが、やはりメモリや計算時間を食いつぶす。

ということで、かなり効果的な、自然な突然変異ではなく、かなり恣意的な突然変異を考えないと、実用的なプログラムにはなりそうもない。

ということで、次回までに、恣意的な突然変異の方法を考えることにしよう。

これまでのあらすじ

一人二役の寂しいオセロから脱却すべく、 オセロの対戦が務まるAIの作成を始めた。 しかし、一通り動きはするものの、このAIは形勢判断を全くせずにテキトーに手を選んでいるだけなので非常に弱い。

オセロってこんな早く終わるゲームじゃないと思うんですけど!?

なので少しは歯ごたえのあるまともなAIを作ろうと思うのであった。

これまでのあらすじ

新人の力量を測るための課題としてオセロの作成を指示したが、 指示した当人が作れないようでは話にならないので実際に作り始めた。 盤面が4x4で黒も白も人間が指す一人二役の寂しいオセロは実装でき、 遅延評価を導入して性能の改善と実装の簡潔さの両立を図った。

しかし一人二役はいくらなんでも虚しい。 なので AI を実装して一人でも遊べるようにしようと思うのであった。

これまでのあらすじ

新人の力量を測るための課題としてオセロの作成を指示したが、 指示した当人が作れないようでは話にならないので実際に作り始めた。 一先ず盤面が4x4で黒も白も人間が指す一人二役の寂しいオセロは実装できたのだが、 快適に遊ぶには大きな問題が潜んでいたのであった。

問題

今年も弊社に新卒採用で入社された方が何名かいます。 採用情報ページに記載されているように、 弊社ではメンター制度が設けられており、 誰かしら指導役の社員が面倒を見たり見なかったりします。 ただ指導するにはまず相手の力量を測る必要があります。 技術者として採用された方を相手にするなら、 適当な課題を与えて、それに対して作り上げたモノを見るのが一番手っ取り早いです。

と言う訳で「適当な課題」として今回は「オセロを実装する」ことにしました。 しかしこれだけではテキトー過ぎるので、以下のように段階を設定しました:

  1. 黒も白も人間が指す一人二役の寂しいオセロを実装する。
    • 盤面のサイズは4x4とする。
    • 外観やUIは凝らなくてよい。
    • 実装はJavaScriptで行い、Webブラウザで遊べるものにする。
  2. 仮AIを実装する。このAIの手筋は以下の通り:
    • 取り得る手のうち最も上の行に石を置ける手を選ぶ。
    • 同一行に指せる手が複数あるなら最も左の列に石を置ける手を選ぶ。
  3. 本格的なAIを実装する。このAIの手筋は以下の通り:
    • 最大4手先まで読み、取り得る盤面のうち最も「優勢」な盤面に辿り着く手を選ぶ。
      • AIの手番を読む時はAIにとって最も「優勢」な盤面になる手を選ぶ。
      • 人間の手番を読む時は人間にとって最も「優勢」な盤面になる手を選ぶ。
    • AIは同じ盤面に対して常に同じ手を指す。
    • 「優勢」度合いの判定は凝らなくてよい。
  4. 盤面を6x6や8x8に拡大する。
    • 拡大に伴って処理すべきデータ量が増大するのでパフォーマンスが落ちる。快適に遊べるようパフォーマンスを改善すること。

各段階での狙いとしては

  1. オセロくらいのロジックはサクサク組める。
  2. 「誰が手を指すのか」を見越して抽象化した処理を書ける。
  3. 再帰的なロジックがサクサク組める。
  4. ボトルネックを見つけ出して適切な対処を取ることができる。

といったところです。

が、課題を設定した人間がこれくらいサクサク書けなくては話になりませんよね。 と言う訳で実際に実装してみることにしましょう。 できれば昨今のビッグウェーブであるところの 関数型プログラミング に乗っかった形で書けばかっこいいんじゃないでしょうか。

(なお、 実際に作成したオセロのソースコードは GitHubで公開されており、 完成品で遊ぶこともできます)

このアーカイブについて

このページには、2013年7月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2013年6月です。

次のアーカイブは2013年8月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。