スポンサーサイト

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
Guide
  •  …この記事と同じカテゴリの前後記事へのページナビ
  •  …この記事の前後に投稿された記事へのページナビ
  • Edit
  • TB(-)|
  • CO(-) 
 
 

【ウディタAI企画2】「Make 10 Path」へ参加しました。

【ウディタAI企画2】「Make 10 Path」へ参加しました。

tohさん主催の「ウディタAI企画2」へ参加しました。

かなり要約すると、ボード上を歩くAIを皆で持ち寄って、点数を競うゲームですね。
詳しくは「ウディタAI企画2」の方に記載されています。



ウディタAI企画2_01_結果
↑対戦後の結果
先に結果を書くと、私こと「 ぴけの戦闘力:」AIは、見事世界 4位の大健闘でした!
戦闘力 700 超えなら、まぁ当然ですよね!

1位は1344点と破格の点数。
2位は1000点ジャストで会場を盛り上げてくれました。
3位は私のAIと抜きつ抜かれつの白熱のバトルを繰り広げましたが、残念ながら途中でスタミナ不足で負けてしまいました。

対戦の経過はLivetube配信上でライブ中継されており、中々楽しませて頂きました。

製作期間は2週間、ウディタの使用時間は、「36:26(13:48)」との事。
想定よりかなり(とても)時間が掛かってしまいましたが、何とか形になって一安心。
自分の課題も見えてきたので、もう少し勉強が必要ですね。


さて、本題です。
今回作ったアルゴリズムについて、軽く説明したいと思います(備忘録を兼ねて)。
予め書きますが、専門用語は知りません。
作成方法についても調べて無いので、訳の分からない事を書いていても見守って居て下さい。


■1. アルゴリズム概要
今回使用したアルゴリズムは「先行乗除整数化処理 + 左手探索法」と勝手に命名しています。
「左手探索法」は、迷路を左手壁沿いに移動していく探索方法です(勝手に命名しました)。
「左手探索法」の具体的な説明は省略します。

以降、「先行乗除整数化処理」の説明をさせて頂きます。

加算・減算だけなら移動する度に計算すれば良いので(比較的)簡単です。
しかし、乗算・除算が絡むと、そちらを先に計算する必要が生じ、処理が複雑になります。

そこで、「先に乗除を計算して整数化(部品化)してしまおう!」という主旨で作成しました。


■2. 先行乗除整数化処理(勝手に命名)

例を書きます。
ウディタAI企画2_02_シード82201
これはシード値「82201」の盤面の左上のマスの画像です。
座標( 1, 0 )に乗算(×)が有るのが分かります。

このマスの上下左右4マスを基点として、乗除・除算の探索を行います。
この時、加算・減算のマスへは進ませません。

処理の流れを以下に記します。

1. 呼出元( 1, 0 )隣接する、座標( 2, 0 )を基点とし、呼出元( 1, 0 )へ移動
2. 「↑・←・↓」へ探索(→から来たので、→への探索はしない)
2-1. 「↑」は盤外のため、除外
2-2. 「←」は進める為、進む
2-2-1[ 座標(0, 0): 値:7 ]. 「↑・←・↓」へ探索
2-2-2. 「↑」は盤外のため、除外
2-2-3. 「←」は盤外のため、除外
2-2-4. 「↓」は進める為、進む
2-2-4-1[ 座標(0, 1): 値:× ]. 「←・↓・→」へ探索(↑から来たので、↑への探索はしない)

…といった感じで、再起的に探索します。

これを繰り返す事で、
ウディタAI企画2_03_乗除探索_ルート視覚化
↑の様な探索ルートを見つけます。
これをデータベース(CDB[ 乗除Blk ])へ格納します。

ウディタAI企画2_04_乗除探索
↑格納するデータは、こんな感じです。
赤字で囲った部分が、先の画像の「6 → * → 7 → * → 8」の部分ですね。

その他にも「6 → * → 0 → * 7」等といった進行ケースも有るので、同様にDBへ格納します。
全てのマスに対して同様の乗除探索を行ったら、準備完了です。

乗除登録した座標(上記ケースの場合、座標(2, 0)から座標(1, 0))へ移動した際、
CDB[ 乗除Blk ] を参照し、下記情報を取り出します。

1. 移動先 (値:LLDD)
2. 計算値 (値:336)

取り出した情報を元に、計算値を加算(減算)し、移動し、探索を継続します。
また、上記の移動を終えて戻ってきた際、再度 CDB[ 乗除Blk ] を参照し、別のルートへ移動します。

※尚、CDB[ 乗除Blk ]への参照は、全データの総ナメでは無く、当該座標の先頭データを別途保持しています。



■3. 最適なルートのみ保持
探索していき、合計値が 10 丁度になったら、その時のルートを保持し、探索を継続します。
最も点数の高いルートのみを保持し、最終的にそのルートを結果として返します。



■4. CDB(可変データベース)について
今回、CDBは4つ用意しました。
ウディタAI企画2_05_CDB

1. 仮想盤面
 … データ数10(x) * 項目数10(y)の情報を持つ。
 … 移動時に深さ(歩数)を指定座標に代入。

2. 乗除盤面
 … データ数10(x) * 項目数10(y)の情報を持つ。
 … CDB[ 乗除Blk ] への参照。 当該座標と紐付いたスタック値の先頭データ番号を代入。

3. 通った場所
 … 移動する度に座標や点数等の情報をスタック(追加)する。
 … 探索し尽くした際、1つずつ戻り、別ルートの探索を行う。

4. 乗除ブロック (乗除Blk)
 … 先行乗除整数化処理実行時、1ルート毎に情報をスタックする。
 … もし盤面に [ 乗算 | 除算 ] が存在しない場合、データ数は 0 となる。
 … 詳しくは [ ■2. 先行乗除整数化処理 ] 参照。


ざっと書いてみましたが、以上になります。
ここまで考えていたものの、結果として全ての実装は期日までに間に合いませんでした。
製作時間と自分の技術力を考慮し、もう少し計画を練った方が良かったかもしれません。

今後の課題としては、
 ・アルゴリズムの学習
 ・制作に対する計画性の向上
 ・汎用性の高い処理の作成・流用 (要はプログラムを別の作品にも流用できる仕組みづくり)
といった所でしょうか。

もし不明点が有れば、Twitterかコメントにてお願いします。
(Twitterの方が反応は早いです)



(追記4/11 22:24)
Q. 乗除ブロックの個数はいくつあるの?
A. 上記盤面と同シード値「82201」で、437個です。
ウディタAI企画2_06_乗除ブロック数
↑乗除ブロックの出力ログ(末尾のみ抜粋)
スポンサーサイト
Guide
  •  …この記事と同じカテゴリの前後記事へのページナビ
  •  …この記事の前後に投稿された記事へのページナビ
 

~ Comment ~

  ※コメントの編集用
  シークレットコメントにする (管理者のみ表示)

~ Trackback ~

卜ラックバックURL


この記事にトラックバックする(FC2ブログユーザー)

MENU anime_down3.gif

同じカテゴリの記事が一覧表示されます
同じタグの記事が一覧表示されます
更新月別の記事が一覧表示されます
キーワードで記事を検索
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。