Minecraftとタートルと僕

PCゲームMinecraftのMOD「ComputerCraft」の情報を集めたニッチなブログです。

タートルにAIを組み込もう(rule-basedプログラミングのすすめ)

はじめに

関数型プログラミング? オブジェクト指向? いえ、時代はルールベースですよ!! (ある意味逆行してます)

今回は、手続き型とも、関数型とも、オブジェクト指向とも違う、新しいプログラミングパラダイムについてご紹介したいと思います。

ルールベースシステムとは

ルールベースシステムとは、別名プロダクションシステムとも呼ばれ、人間のように推論するコンピュータを目指して考案されたコンピュータシステムです。

人工知能(AI)研究分野では、もっともよく知られたアーキテクチャの一つであり、AIと言えばルールベースシステムというくらい有名です(ちょっと大げさかも)。

このルールベースシステムを応用してプログラミングすることにより、タートルがまるで推論しながら行動しているかのように振舞います。

「タートルにAIを組み込む」と言うと、少しだけロマンを感じませんか? 

ロマンを感じた方は、この記事を読んで、ルールベースプログラミングに少しだけ触れてみましょう。

ルールベースと一般のプログラミングとの違い

一般的なプログラミングでは、何かを実現するために、その手続き(HowTo)を記述します。

条件分岐(IF文など)や繰り返し文(FORやWHILEなど)を使って一連の手続きを記述し、その内容をコンピュータが逐次実行します。そのため手続き型プログラミングと呼ばれることがあります。

それに対してルールベースのプログラミングでは、何を行うか(What)という個別のルールを記述していきます。そのため先の手続き型に対し、宣言型プログラミングと呼ばれることもあります。

誤解を恐れずできるだけ簡単に説明すると、 「Aならば、Bをせよ」「Cならば、Dをせよ」「EかつFならば、Gをせよ」のように、条件(IF)とそのときすること(THEN)をセットにしたルールをシステムに複数記憶させておけば、状況に合わせてシステムがうまくルールを選択・実行して目的を達成してくれます。

えー?そんなうまくいくの? とお思いのみなさん。 いくつかのポイントさえ押さえておけば案外うまくいくのですよ。

ルールベースシステムの仕組み

ルールベースシステムは大きく3つの要素からなっています。できるだけわかりやすく説明するために、タートルに知能があると仮定してルールベースシステムの枠組みでたとえ話をしてみましょう。

f:id:hevohevo:20140830004436p:plain

1つめの要素 「ワーキングメモリー」

まず1つめは、「ワーキングメモリー」です。

かしこいタートル君は、自分の現在状態や自分を取り巻く世界の状態を認知し、それら情報を記憶しておくことができます。その記憶しておく場所あるいは仕組みをワーキングメモリーと呼んでいます(たとえば現在の位置や向きなどの情報をワーキングメモリーの中に記憶しています)。

とはいえタートルが外部情報を入手する手段は少ないので、ワーキングメモリーの中身は必然的に乏しくなります。

我々ユーザーが見ているマイクラ世界よりもタートルが認知できる世界が小さい(貧弱な)のはプログラミングする上でも残念なことです。

2つ目の要素「ルールメモリー」

無垢なタートル君は、最初は何のルールも持っていないまっさらな状態なのですが、プログラマが教えてくれたルールは全て覚えています。このルールを記憶しておく場所がルールメモリーです。

1つのルールは、IF部とTHEN部から成り立っています。

IF部にはワーキングメモリーの内容を判断基準として「現在このルールが実行可能かどうか」を記述します。 たとえば、ワーキングメモリー内の現在位置情報を使って「x座標が3とあるときこのルールは実行可能」のような記述をします。

THEN部では実際に行う行動を記述します。たとえばワーキングメモリーの中身を直接書き換えたり、あるいはタートルを動かして何かの操作をしたりと様々な行動を記述することができます。

このようなIF-THENというセットを持ったルールをたくさん記憶させることで、タートルは複雑な推論を行い問題を解決することができます。

3つ目の要素「推論エンジン」

ワーキングメモリーとルールメモリーの2つを使って、現在はどのルールを実行できるかを照合(認知)、そして実行可能な複数のルールからどれを実行するかの判断(競合解消)、そしてそのルールを使って実際に行動(実行)、というサイクルを動かすのが推論エンジンです。

専門用語で言うと認知―実行サイクルと呼ぶのですが、難しい話は抜きにしましょう。

ポイントは、(1)全てのルールのIF部を見て実行可能なルールを調べる、(2)実行可能な複数のルールから「競合解消戦略」を使って実行するルールを1つだけ選ぶ、(3)そのルールのTHENを実行するという一連の流れを1サイクルとして、このサイクルを何度も繰り返していくところにあります。

補足)「競合解消戦略」とは

複数あるルールからどのような戦略で1つ選ぶ?というお話なのですが、戦略の種類は多岐にわたり、その特色やら諸々で1冊の本が書けてしまうほど深いお話になってしまいます。

今回紹介するAPIでは、以下の戦略を選んで実装したということでご理解ください。

  1. ルールには優先度(priority)をあらかじめ設定でき、優先度が高い(priority値が小さい)ものほど優先する
  2. もし優先度が同じだったら、最近実行したことがあるルールは優先度を下げる(つまり一度も実行したことないルールを最優先
  3. それでも一緒ならば(たとえばどのルールも実行したことない)、最初に記憶させたルールほど優先する

TurtleAI APIダウンロード

コマンドで以下を実行する

> pastebin get BzGqtgVa turtleAI

今回は、APIのソースコード解説をしません。むしろ、その使い方に重点を置いて解説をします。

TurtleAI APIの使い方

基本は以下の流れです。

  1. aiオブジェクトを作る
  2. aiオブジェクトに、ルール(プログラム中ではtaskと呼んでいます)を追加する
  3. そのルールのIF部(canRun(info)メソッド)をカスタマイズする
  4. そのルールのTHEN部(run(ctrl)メソッド)をカスタマイズする
  5. 上記2,3,4を繰り返して好きなだけルールを追加する
  6. イテレータを使って推論エンジンを回す
-- #################################################
-- rule-based プログラミング例
-- 5歩進んだら後ろを向き、を繰り返してひたすら往復する

os.loadAPI("turtleAI")
 
-- まずはAIオブジェクトを作る
local ai = turtleAI.newAI()


-- #################################################
-- [fwd-task追加] AIオブジェクトにタスクを追加する
 
-- ai:addTask(タスク名,優先度) 値が小さいほど優先度は高い
-- 優先度を省略するとデフォルト0
local fwd = ai:addTask('fwd',0)
 
-- タスクが現在の状況で実行可能かどうか(true/false)を返すメソッドを追加。IF部。
-- なお省略も可能。デフォルトでは常にtrueを返す。function task_obj:canRun(info) return true end
function fwd:canRun(info)
  -- info テーブルはタートルの情報が詰まったワーキングメモリーです
  if info.getFuelLevel() > 0 then
    return true
  else 
    return false
  end
  -- return info.getFuelLevel() > 0 -- と書いても良い
end
 
-- タスクが実際に行う内容を書く。THEN部。
function fwd:run(ctrl)
  -- ctrlテーブルの中にはタートルを操作する関数が詰まっています
  ctrl:forward()
  return true -- trueを返すとこのタスク実行後にターンが進む。falseなら進まない。
end
 
-- #################################################
-- [turnAround-task] AIオブジェクトにタスクを追加する

-- ai:addTask(タスク名,優先度) 値が小さいほど優先度は高い
-- 優先度を省略するとデフォルト0
local turnAround= ai:addTask('turnAround',0)

-- タスクが現在の状況で実行可能かどうか(true/false)を返すメソッドを追加。IF部。
function turnAround:canRun(info)
  -- info テーブルはタートルの情報が詰まったワーキングメモリーです
  return (info.coord.z==5) or (info.coord.z==0)
end

-- タスクが実際に行う内容を書く。THEN部。
function turnAround:run(ctrl)
  ctrl:turnRight()
  ctrl:turnRight()
  return true -- trueを返すとこのタスク実行後にターンが進む。falseなら進まない。
end

-- #################################################
-- [fin-task追加] AIオブジェクトにタスクを追加する

local fin = ai:addTask('fin',-1)
 
function fin:canRun(info)
  return info.getBurnOutFuelLevel() >= 20  -- 燃料を20以上使ったら実行可能
end
 
function fin:run(ctrl)
  return "quit" -- quitを返すことでルールベースエンジン終了
end
 
 
-- #################################################
-- 推論エンジンの実行
-- for文でぐるぐる回す。ai:iterate(50)で50ターンまで回して終了
for task, turn in ai:generate(50) do
  print("Turn: ",turn) -- 現在のターン
  print(ai:tasksToString(ai.runable_tasks)) -- 実行可能なタスク一覧
  print(" ran-task: ",task.name) -- その中から実際に実行したタスク
  print(ai.info:toString()) -- 現在位置や燃料情報など
end
 
print("Quit")

API使用例の解説

AIの作成

まず最初にlocal ai = turtleAI.newAI()のようにして、AIオブジェクトを作成しましょう。

そして、ai:addTask(タスク名,優先度)を使って、タスク(ルール)を追加します。

"fwd-task"

ひたすら前へ進む"fwd-task"を追加しています。燃料があるときだけ実行可能というIF条件(canRun(info)メソッド)を定義していますが、この場合、省略してもさほど問題ありません。

どのタスクにも以下のメソッドがデフォルトで定義されているため、canRun(info)メソッドのカスタマイズを省略すると、デフォルトでtrueが返り常に実行可能なルールということになります。

function task_obj:canRun(info) 
  return true 
end

またTHEN部(canRun(info)メソッド)の引数であるinfoテーブルには、タートルの様々な情報が詰まっています。つまりこのテーブルはワーキングメモリーに該当します。

  • infoテーブル内の情報(変数や関数)
    • info.coord (開始時の座標を{x=0, y=0, z=0}としたテーブル)
    • info.direction(開始時の向きを0として時計回りで0-3)
    • info.turn (現在の推論ターン)
    • info.initial_fuel (開始時の燃料)
    • info:getBurnOutFuelLevel() (開始後に現在までに使った燃料)
    • など、詳細はAPIソースを確認のこと

実際に行動するrun(ctrl)では、ctrlテーブル内に含まれている関数を使って1歩前に前進します。つまりctrlテーブルはタートルを操作するためのコントローラです。

なお、標準のturtle APIを使って移動するのは避けてください。ワーキングメモリ内に記憶した現在座標などがおかしくなってしまいますので。

  • ctrlテーブル内の関数
    • ctrl:forward(n)
    • ctrl:turnRight(n)
    • ctrl:back(n)
    • など、タートル移動系の関数、詳細はAPI確認のこと

"turnAround-task"

そして、5歩進んだら180度振り返る"turnAround-task"です。

IF部(canRun(info))で、Z座標が5のときと0のときに実行可能なようにtrueを返します。

THEN部(run(ctrl))では、ctrl:turnRight()を使うことで振り返っています。

ここで注意したいのはZ座標が0のときの挙動です。

プログラム開始直後のZ座標0のときは、"turnAround-task"と"fwd-task"の両方が実行可能です。 このとき競合解消戦略により、(1)優先度は同じなので同等、(2)両方とも未実行なので履歴からも同等、(3)登録順から見て"fwd-task"が優先と判断されます。

そして、一旦Z座標5まで行って戻ってくることでZ座標0になったとき、このときも"turnAround-task"と"fwd-task"の両方が実行可能です。 このとき競合解消戦略により、(1)優先度は同じなので同等、(2)直前に"fwd-task"が実行されたので優先度下げて"turnAround-task"を優先と判断されます。

このように競合解消戦略をしっかりと理解して優先度を使いこなさないとスムーズなルールベースプログラミングができないのでご注意ください。

"fin-task"

最後に終了タスクを必ず作りましょう。

最後の推論エンジンの実行(for文を使ったイテレータ)で50ターンと指定しているのでとんでもない暴走は無いはずですけどね。

今回の終了タスク"fin-task"は、canRun(info)がtrueを返すときに絶対に止まってほしいので優先度を高め(-1)にしています。

また、推論エンジンを停止するには、run(ctrl)メソッドが"quit"という文字列を返すようにしてください。

おわりに

今回の記事は非常に長く、専門的な内容も多いので戸惑う方も多いと思います。しかし考え方は非常にシンプルなので実際にプログラミングしてみると良いでしょう。

また、今回の例は目的自体がシンプルなので、次回はもう少し複雑な行動をするプログラムをルールベースで組んでみたいところです。

たとえば、指定した範囲の床材を貼り換えるプログラムなどはいかがでしょうか。

実は、スムーズなプログラミングのために必要だけれどもまだ実装していない機能がいくつかあるので、それも一緒に実装して紹介する予定です。

  • ワーキングメモリに任意の情報を記録する機能
  • あるタスクを実行後、次に優先実行したいタスクを指定する機能(コンボ機能)

質問、感想、コメントなどお待ちしております。

次回をお楽しみに。

補足という名の言い訳(AIをかじったことある人向けの内容)

ここで紹介したルールベースAPIは、AIを勉強した人が見ると首を傾げるような機構をいくつか持っています。

これは主に、実用性と実装上の手抜き*1のための改変であり、ルールベースシステムというよりもオレオレベースシステムに近くなっていることをご了承ください。

特に大きな相違は認知-実行サイクルにおけるマッチングの部分を大きく省略していることです*2

たとえばルールのIF部では、ワーキングメモリーとの照合パターンではなくチェックしたい条件をプログラムで直接記述します。

これは手抜き・・・というだけではなく、柔軟なプログラミングを可能にする実用性のための改変でもあります。例えばワーキングメモリ内に存在しない情報であっても、その場で関数を使って新たに情報を入手することが可能です(例: 正面にブロックがあるかどうかをturtle.detect()を使ってチェックできる)。

また、ルールのTHEN部では、ワーキングメモリーの内容変更だけでなく、タートルを直接操作する関数を記述できます。

ワーキングメモリー範囲外から情報を入手したり、あるいはワーキングメモリーではなくタートル自身を操作するという機能は純粋なルールベースシステムからは少々逸脱していますが、実用上必要な機能拡張であると考えています。

*1:どちらが主であるか僕のこれまでの記事を読んだあなたならわかりますね?

*2:マッチングこそがルールベースの花形だろうが!!!という意見を持つあなた。あなたとはおいしいお酒が飲めそうです。今回は実装していませんが、推論処理の効率化の為に将来的には実装したいですね。