tsurutanのつぶやき

これが、破壊的イノベーションだっっっ!!

スポンサーリンク

広告

人工知能を組み込んだパズルゲームを作ってみた

f:id:tsurutan:20150515122712p:plain

現在私が通っている大学で人工知能についての授業をうけました。 この授業をうけて探索の面白さを知りました(小並感)。 ということで、この楽しさを皆さんに分かち合ってもらいたいとおもい人工知能【探索】を組み込んだ8パズルゲームを作ってみました。

実装した探索

幅優先探索

f:id:tsurutan:20150519163158g:plain

幅優先探索 - Wikipedia

幅優先探索(はばゆうせんたんさく、英: breadth first search)はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズムである。

アルゴリズムの流れ

  1. 初期状態、目的状態にフラグを設定
  2. 空欄と隣接するパネルと入れ替える
  3. その状態を記憶
  4. 目的状態であるかを見る
  5. 目的状態ではない場合次の状態を比較する

双方向探索【幅優先探索

双方向探索 - Wikipedia

双方向探索(英: bidirectional search)とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う

アルゴリズムの流れ

  1. 初期状態、目的状態から交互に比較する
  2. 同じ状態に遷移したら計算を終了する。

A*探索

f:id:tsurutan:20150519162744g:plain

A* - Wikipedia

A*(A-star, エースター)探索アルゴリズムは、探索アルゴリズムの一つ。 スタートノードからゴールノードまでの経路を計算する、このとき求める経路が最良(最短)であることを保証しているアルゴリズムである

アルゴリズムの流れ

  1. ヒューリスティックを目的状態からのタイルの距離とする
  2. openにルートノードを加える
  3. openから銭湯のノードNを取り出す
  4. ヒューリスティックが0の場合終了する
  5. ノードの全ての子ノードをopenに追加、open内のノードをヒューリスティックの小さい順に並べ替える

深さ優先探索

f:id:tsurutan:20150519163209g:plain

深さ優先探索 - Wikipedia

深さ優先探索(ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう)は、木やグラフを探索するためのアルゴリズムである。

アルゴリズムの流れ

  1. openにルートノードを加える
  2. openから1つのノードNを取り出す
  3. 取り出したノードNが目標状態の場合終了する
  4. ノードNの全ての子ノードをopenに追加

結果

上記のような感じで探索を8パズルゲームに実装してみました。 またこの探索の早さを比較するため以下の様に定義をしました。

  • Time     探索アルゴリズムが始まり終わるまでの時間
  • Step    状態が目的状態であるかの比較回数

実際に動かしてみるとこのようになりました。

www.youtube.com

f:id:tsurutan:20150515221537p:plain

幅優先探索は圧倒的にStep数が多いですが、双方向から探索することによってStep数を減っています。 またA*探索、深さ優先探索はStep数は多くないですが、TimeがStep数が最も多い幅優先探索より多くなっています。 みなさんもお持ちのAndroidで試してみてはいかがでしょうか?

人工知能を組み込んだ8パズルゲームで遊ぶ

知能の物語

知能の物語

人工知能の基礎 (Computer Science Library)

人工知能の基礎 (Computer Science Library)

スポンサーリンク

広告