Q-learningで迷路を解く
上記のような迷路をQ-learningで解いていきます。
やり始めたきっかけ
もともとゲーム木探索アルゴリズムで最弱オセロを作っていましたが、機械学習で作りたいと思い、DQNを使う必要がありました。そこで手始めに、簡単なQ-learningを作ってみることにしました。
迷路のルール
- □マークは通過できない
- 何もないマスは通過できて、0.5点の失点
- ×マークのマスは、通過できて、1点の失点
これらのルールをもとに、S(スタート）からG（ゴール）まで、最も失点が少ないルートを探索します。
迷路の環境を実装
以下、迷路の環境のコードです。後ほど解説していきます。
#Maze.py
class Direction():
UP = -12
DOWN = + 12
LEFT = -1
RIGHT = +1
class Maze:
def __init__(self):
self.maze = [
"□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□",
"□", "S", " ", " ", " ", " ", " ", " ", " ", " ", " ", "□",
"□", "□", " ", "×", " ", "□", "□", "□", "□", "□", "□", "□",
"□", "□", " ", "×", " ", "□", " ", " ", " ", "×", " ", "□",
"□", "□", " ", "×", "□", "□", " ", "×", " ", " ", " ", "□",
"□", "□", " ", "×", "□", "□", " ", "□", "□", "□", " ", "□",
"□", "□", " ", " ", "□", "□", " ", "□", "□", "□", " ", "□",
"□", " ", "×", " ", " ", "×", " ", " ", " ", "□", " ", "□",
"□", " ", " ", " ", " ", " ", " ", " ", " ", "□", "G", "□",
"□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□"
]
self.position = 13
def initialize(self):
self.position = 13
def print_map(self):
for y in range(len(self.maze)):
if (y + 1) % 12 != 0:
if y == self.position:
print("P", end='')
else:
print(self.maze[y], end='')
else:
if y == self.position:
print("P")
else:
print(self.maze[y])
def step(self, direction):
if direction + self.position>= 0 and \
direction + self.position <= 120 and \
self.maze[direction + self.position] != "□":
self.position = self.position + direction
def is_goal(self):
if self.maze[self.position] == "G":
return True
else:
return False
def reward(self):
if self.maze[self.position] == "×":
return -1
elif self.maze[self.position] == " " or self.maze[self.position] == "S":
return -0.5
else:
return 0
def get_position(self):
return self.position
迷路を定義
Mazeクラスに迷路を定義します
class Maze:
def __init__(self):
self.maze = [
"□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□",
"□", "S", " ", " ", " ", " ", " ", " ", " ", " ", " ", "□",
"□", "□", " ", "×", " ", "□", "□", "□", "□", "□", "□", "□",
"□", "□", " ", "×", " ", "□", " ", " ", " ", "×", " ", "□",
"□", "□", " ", "×", "□", "□", " ", "×", " ", " ", " ", "□",
"□", "□", " ", "×", "□", "□", " ", "□", "□", "□", " ", "□",
"□", "□", " ", " ", "□", "□", " ", "□", "□", "□", " ", "□",
"□", " ", "×", " ", " ", "×", " ", " ", " ", "□", " ", "□",
"□", " ", " ", " ", " ", " ", " ", " ", " ", "□", "G", "□",
"□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□"
]
self.position = 13
左上から、
0,1,2, ... , 10,11,
12,13, ...,
という順に、１次の配列に格納します。
self.position = 13
は、迷路の"S"地点に初期位置を設定しています。
def initialize(self):
self.position = 13
迷路を１回解き終わったら、初期位置に戻すために、関数を用意しておきます。
class Direction():
UP = -12
DOWN = + 12
LEFT = -1
RIGHT = +1
迷路は12×10のサイズです。下に移動するときは、現在位置に12を加えれば良いです。上下左右に移動するためのクラスDirectionを用意します。
def print_map(self):
for y in range(len(self.maze)):
if (y + 1) % 12 != 0:
if y == self.position:
print("P", end='')
else:
print(self.maze[y], end='')
else:
if y == self.position:
print("P")
else:
print(self.maze[y])
標準出力に、迷路を表示するための関数です。迷路の配列mazeをループさせてprintしますが、現在位置(position)のところだけpをprintします。
def step(self, direction):
if direction + self.position>= 0 and \
direction + self.position <= 120 and \
self.maze[direction + self.position] != "□":
self.position = self.position + directio
引数のDirectionの値を受け取り、その方向にpositionを移動させるstep関数です。□マスの方向には移動できません。
def is_goal(self):
if self.maze[self.position] == "G":
return True
else:
return False
positionが、迷路の"G"と重なったとき、ゴールしたという判定をします。
def reward(self):
if self.maze[self.position] == "×":
return -1
elif self.maze[self.position] == " " or self.maze[self.position] == "S":
return -0.5
else:
return 0
報酬関数rewardです。positionが×の上にいたら-1、空白マスにいたら-0.5を返します。□マスの方向に移動しようとしても、移動することはできず、無駄に-1を食らいます。こうすることで、壁に向かって進もうとしなくなります。
def get_position(self):
return self.position
最後に、positionを返す関数です。
ここまでで、迷路の環境を作りました。まだ強化学習、Q-learningに関するコードは記載していません。次回は、迷路を実際に学習して、解くためのエージェントのコードを紹介します。