カテゴリー別アーカイブ: AI

迷路で眺める探索アルゴリズム

CodeVS2.0(サイト:http://codevs.jp/ 予選の連鎖動画:http://www.nicovideo.jp/watch/sm19873888)の復習をかねてこんなFlashを作りました。



迷路で眺める探索アルゴリズム(Search algorithm visualize)

さまざまなアルゴリズムを使って、迷路探索を行います。
使ったのは基本的な探索アルゴリズム8種とオリジナルのアルゴリズム2種です。

まずは迷路の見方について。

  • 青色(): Sがスタート、Gがゴール
  • 白色(): 未探索のマス
  • 灰色(): 探索済みのマス
  • 赤色(): 探索により発見されて、リストに保持されているの分岐点
  • 橙色(): 枝刈りにより、リストから削除された分岐点
  • マスに書いてある数字は、リスト内のマスにゴールに近い順に順位を付けたものです
    (間違い制限探索のみ異なるので後で解説)

つぎに操作方法について。

  • 左上のコンボボックス[…|+]でから眺めるアルゴリズムを選ぶ
  • [new]で新しい迷路に更新
  • [new]の左隣のチェックボックスで、2種類の迷路(分岐が多いor少ない)を切り替える
  • [speed]のスライドバーで再生速度を選択

さらにFlash下部のデータの読み方です。

  • 探索回数は迷路内で移動した回数です(灰,赤,橙マスの合計数と同じ)。計算時間(CPU Time)に直結します
  • 分岐数は、現在の探索中リストに追加されているマス(赤)の数です。メモリの使用量に直結します

各アルゴリズムの解説

深さ優先探索(Depth-first search)

深さ優先探索 – Wikipedia

ひたすら一本の道を突き進み、行き止まりがあったら、1つ前の未探索の分岐点に戻って再びその道を突き進む探索法。

特徴

  • 知識なし(評価関数を使用しない)
  • 探索範囲が有限の場合は完全(解を必ず見つけられる)。
  • ただし、探索範囲が無限の場合は不完全。
  • 省メモリ

ただし無限に広いフィールドで探索を行うと、ゴールが近くにあっても見逃してしまいゴールを見つけられない場合があります。

幅優先探索(Breadth-first search)

幅優先探索 – Wikipedia

現在までに見つかってる分岐すべてを一回、一回伸ばしていく探索法。

特徴

  • 知識なし(評価関数を使用しない)
  • 完全(解を必ず見つけられる)
  • 探索範囲が無限でも完全
  • 並列化しやすい

一般的には深さ優先探索よりメモリを大量に使う探索ですが、今回ような迷路探索は分岐が少なく行き止まりが多いので深さ優先探索よりも省メモリな探索になってます。

反復深化深さ優先探索(Iterative deeping depth-first search)

反復深化深さ優先探索 – Wikipedia

深さ制限を設けて深さ優先探索を行い、ゴールが見つからなかった場合は深さ制限をゆるめて再度探索する探索法。

特徴

  • 知識なし
  • 完全
  • 探索範囲が無限でも完全
  • 省メモリ

深さ優先探索の省メモリ性をそのままに、無限に広いフィールドでも使えるようにした探索法です。
ただし省メモリな実装を行うと同じ探索を繰り返し行うことになるので、探索時間が長くなります。
また、省メモリでない実装を行うと、幅優先探索と同等のメモリ消費になります。

知識あり探索と知識なし探索

反復深化深さ優先探索は一般的には知識なし探索です。知識なし探索とは評価関数の使わない探索法のことで、この迷路探索の場合ゴールの位置も分からずに盲目的に探索するような手法です。ただし、今回のFlashでは知識あり探索として、反復深化深さ優先探索をおこないました。

ここから先、すべての探索法は知識あり探索ですが、これらすべてで評価関数に現在値とゴールのマンハッタン距離を利用しています。

 マンハッタン距離を使うとゴールまで到達するのに絶対に必要な深さというのがわかります。例えば、スタートからゴールまでの距離が15マスあった場合、最低15回は枝を伸ばさなければゴールに到達できません。これにより、絶対にゴールに到達できない深さ制限というのが分かります。さらにこれにいくらかのマージン(デフォルトでは4)を上乗せした値を深さ制限に使って探索を行うことで計算量を減らしています。

山登り法(Hill climbing)

山登り法 – Wikipedia

ゴールに近い方向へとひたすら進んでいき、行き止まりがあったらそこで断念する探索法。

特徴

  • 知識あり(評価関数を使う)
  • 不完全
  • 省メモリ

今回の迷路探索ではすぐに行き止まりに突っ込むので、あまり使えません。

最良優先探索(Best-first search)

最良優先探索 – Wikipedia

すべての枝を保持して、それらの分岐の中から一番ゴールに近いものを選んで伸ばしいく探索法。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存

今回の迷路の条件と評価関数では、完全な探索方法としては最速になるはずです。

間違い制限探索(Limited discrepancy search)

始めに山登り法で探索を行い、解が見つからなかった場合は1回だけ最良では無い方向に行くことを許容して再び探索を行う。それでも見つからなければ、間違った方向へと進める回数(discrepancy)をさらに増やして探索を繰り返す手法。

注:この探索の赤マスに書かれた数字はそのルートの間違い数(discrepancy)です。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存
  • 省メモリ

反復深化と同様、繰り返し同じ探索を行うことになるため探索に時間がかかります。
ただし、評価関数によっては、省メモリ性、完全性、速度を併せ持つ非常に強力な探索方法となります。

幅優先ビームサーチ(Breadth-first beam search)

幅優先と同じ手順で探索を行い、分岐のリストが事前に決めておいた数(ビーム幅)より長くなった場合に、評価値の悪い枝を枝刈りする。

特徴

  • 知識あり
  • 不完全
  • 並列化しやすい
  • ビーム幅が1の時、山登り法と同じ。
  • ビーム幅が∞(無限)の時、幅優先探索と同じ。

最良優先ビームサーチ(Best-first beam search)

Beam Search – Wikibooks

最良優先と同じ手順で探索を行い、分岐のリストが事前に決めておいた数(ビーム幅)より長くなった場合に、評価値の悪い枝を枝刈りする。

特徴

  • 知識あり
  • 不完全
  • ビーム幅が1の時、山登り法と同じ。
  • ビーム幅が∞(無限)の時、最良優先探索と同じ。

ここまでがある程度知名度のある基本的なアルゴリズムで、次からがオリジナルの探索アルゴリズムになります。

優良優先探索(good-first search)

最良優先探索をより一般化した探索。1度に伸ばす枝の数を、1つに限らず複数にまで拡張した。
例えば、1度に伸ばす枝の数(優先幅)を3に設定した場合、保持されてる枝のうち良い枝から順に3つを延長する操作を繰り返す。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存
  • 優先幅が∞の時、幅優先探索と同じ
  • 優先幅が1の時、最良優先探索と同じ

二重制限探索(Double limit search, Good-first beam search)

優良優先探索にビームサーチを適用したもの。優先幅とビーム幅両方による制限を行う。

ただし、(優先幅)≦(ビーム幅)となる。

特徴

  • 知識あり
  • 不完全
  • 並列化しやすい
  • 優先幅、ビーム幅が共に∞の時、幅優先探索と同じ
  • 優先幅、ビーム幅が共に1の時、山登り法と同じ
  • 優先幅が1、ビーム幅が∞の時、最良優先探索と同じ
  • 優先幅とビーム幅が同じ時、幅優先探索ビームサーチと同じ
  • 優先幅が1の時、最良優先ビームサーチと同じ
  • ビーム幅が∞の時、優良優先探索と同じ

余談

 ここで紹介したアルゴリズムは各種アルゴリズムは迷路だけではなくて、15パズルや、codevsのような落ち物パズル、ソリティアのようなゲームの探索にも利用可能です。
 さらに、一工夫加えればチェスやオセロの様な対戦ゲームで利用することも出来ます。一見、ビームサーチは対戦ゲームでは使えないに見えますが、各手がどの程度良い手かではなく、各手がどの程度打たれやすいのか(この値は評価関数から算出できる)を考えてそれを基準に枝刈りを行えば、ビームサーチと同じような探索が可能です。

 ちなみにcodevsで使った探索法は幅優先ビームサーチでした。幅優先ビームサーチは実装も簡単で、評価関数を作る際にステップ数が異なる盤面の比較を気にする必要もありません。
 ただ一般的な場合でお勧めの探索法は二重制限探索です。実装の簡単さは幅優先ビームサーチとほぼ同じで、一度実装すればパラメータを変更するだけで、幅優先ビームサーチにしたり、最良優先ビームサーチにしたり、幅優先探索と最良優先探索の中間的な性質の探索にしたりできます。また、今回のような最良優先探索有利の課題に対してマルチコアで挑む場合、優先幅をコア数に合わせることで最良優先探索より高速な探索を行うことも可能になります。

あと、迷路生成アルゴリズムは古くて新しい自動迷路生成アルゴリズム – ガジェット通信を参考にクラスタリングアルゴリズムと穴掘り法を使用しました。

※追記:2017/05/27 wonderfl閉鎖によりリンク切れのため「How wonderfl!」へのリンクの差し替えをおこないました

四目並べ5『遺伝的アルゴリズムとあとがき』

四目並べの完成からだいぶ時間があいてしまいましたが、そろそろブログの内容を完結させとかなきゃと思ったので、あとがきみたいなのを残しときます。

ちなみに完成品はこちら

AI量産するのに遺伝的アルゴリズム使ったとか、RTMFPっていうのを使ってオンライン対戦できるようにしたとか、まだ書くつもりだった話はあったんですが、間が空きすぎたのと、完成品の人気が出なかったのと、モチベーションの問題で四目並べのログとしては詳しくは書かないです。

とはいえ全部お蔵入りさせるのももったいないので、遺伝的アルゴリズムについては最後に少しだけ書いときます。

1,遺伝的アルゴリズムとAI

遺伝的アルゴリズムっていうのは簡単に言うと、生物の進化の仕組みをプログラムで使う手法です。

むにむにさんという人が作ってる動画が分かりやすいので、それをみるといいと思います。

ニコニコ動画版:http://www.nicovideo.jp/watch/sm16212939

続きを読む

四目並べ4 『ランダムに手を打たせる』

前回まででだいぶ良くなってきたAIですが、まだ気になる点があります。
それは、

ワンパターンすぎる。

ということ。
ランダム要素が少なすぎるので、一度勝ちパターンを覚えてしまえば負けることはありません。
ですから、今回はAIにランダムに手を打たせる方法を考えてみようと思います。

1. いかにしてランダムに手を打たせるか。

結構な悩みどころです。
ときどき第1候補の手ではなく第2候補や第3候補の手を打たせるようにすればいろいろな手を打つようになるでしょうが、弱くなるのが目に見えてます。モンテカルロ木探索という乱数を使った探索をメインに置いたアルゴリズムもあるのですが、これで強いAIを作るのもなかなか難しいです。

で、思いついたのがこれ。

評価値を付ける際に、ランダムに手を間引いてしまいます。

これだけだと弱くなりそうですが評価値を付けなかった分は高速化されます。その分だけ先読みする手を増やせばうまく相殺できるんじゃないかと考えたわけです。

2. 実践

実際に見てみましょう。

ゲームを開く(swf)

いい感じに手がばらついていますし、さほど弱くなった印象は受けません。
今回のAI(4号)と前回のAI(3号)を対戦させてみると、前回の方がやや勝っている感じがしますが許容範囲内じゃないでしょうか。

とりあえず、今回はここまで。

続くかもしれない。

四目並べ3 『先読みアルゴリズムを組む』

今回は先読みアルゴリズムを組みます。

はじめのAIですべての手を網羅することはできているので、これを繰り返せば2手目、3手目と先読みすることができます。あとは相手もこちらも、自分が有利になるように試合を進めることを踏まえれば、どの手を打てばよいかを決められます。

1. 先読みアルゴリズムの図解

具体的には以下のようなアルゴリズムで、着手を決めます。

  1. 適当な手数を先読みして、起こりうるすべての局面を列挙する。
  2. 最初に最深層にあたる局面に評価値を付ける。
  3. プレーヤーは最も自分が有利になる手を打つと考えて、1つ手前の手に評価値をつける。
  4. 3を繰り返して最上位まで評価値を付けて、自分が最も有利になると考えられる手をうつ。

ネガマックス法図解
3の段階でマイナスを付けて評価値を決めているのは、 相手が不利=自分が有利 だからです。

このような、プレーヤーが自分に有利になるように対局を進めることと、相手が不利=自分が有利であることを利用したアルゴリズムをネガマックス法と言います。

2. 枝刈りで高速化

先ほどのネガマックス法ですが、評価値を付ける順番を工夫すると高速化が行えます。

さっきと同じ局面を例にとって、以下のような順番で評価値をつけてみましょう。

すると、評価値を計算する前にその手が打たれないとわかる場面が出てきます。
枝刈り

上の例の場合、同じような場面がもう一回現れるので、計4回の評価関数の呼び出しが省略できます。
このように必要のない計算を省略して、評価関数を呼び出す回数を減らしたアルゴリズムをネガアルファ法と言います。

3. 実践

以上のアルゴリズムを取り入れたAIを作ってみました。

ゲーム開始(swf)

先読みをしてるのは5手ほど(終盤はもうちょっと増える)ですが、だいぶ良い動きをするようになりました。
こちら(GitHub)にコードを置いておきますが、ネガマックス法やネガアルファ法についてはWikipediaのミニマックス法アルファ・ベータ法の項目にもコード例が載っているのでそちらを参考にするのもいいと思います。

今回はここまで。

きっと続く。