maze_Astar_dqn_15x15.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving Maze with A-star algorithm, Q-learning and Deep Q-network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Objective of this notebook is to solve self-made maze with A-star algorithm, Q-learning and Deep Q-network.\n",
    "### The maze is in square shape, consists of start point, goal point and tiles in the mid of them.\n",
    "### Each tile has numericals as its point. In other words, if you step on to the tile with -1, you get 1 point subtracted.\n",
    "### The maze has blocks to prevent you from taking the route."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pds\n",
    "import random\n",
    "import copy\n",
    "from keras.models import Sequential\n",
    "from keras.layers import Dense, Activation, Flatten\n",
    "from keras.optimizers import Adam, RMSprop\n",
    "from collections import deque\n",
    "from keras import backend as K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maze Class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Maze(object):\n",
    "    def __init__(self, size=10, blocks_rate=0.1):\n",
    "        self.size = size if size > 3 else 10\n",
    "        self.blocks = int((size ** 2) * blocks_rate) \n",
    "        self.s_list = []\n",
    "        self.maze_list = []\n",
    "        self.e_list = []\n",
    "\n",
    "    def create_mid_lines(self, k):\n",
    "        if k == 0: self.maze_list.append(self.s_list)\n",
    "        elif k == self.size - 1: self.maze_list.append(self.e_list)\n",
    "        else:\n",
    "            tmp_list = []\n",
    "            for l in range(0,self.size):\n",
    "                if l == 0: tmp_list.extend(\"#\")\n",
    "                elif l == self.size-1: tmp_list.extend(\"#\")\n",
    "                else:\n",
    "                    a = random.randint(-1, 0)\n",
    "                    tmp_list.extend([a])\n",
    "            self.maze_list.append(tmp_list)\n",
    "\n",
    "    def insert_blocks(self, k, s_r, e_r):\n",
    "        b_y = random.randint(1, self.size-2)\n",
    "        b_x = random.randint(1, self.size-2)\n",
    "        if [b_y, b_x] == [1, s_r] or [b_y, b_x] == [self.size - 2, e_r]: k = k-1\n",
    "        else: self.maze_list[b_y][b_x] = \"#\"\n",
    "            \n",
    "    def generate_maze(self): \n",
    "        s_r = random.randint(1, int((self.size / 2)) - 1)\n",
    "        for i in range(0, self.size):\n",
    "            if i == s_r: self.s_list.extend(\"S\")\n",
    "            else: self.s_list.extend(\"#\")\n",
    "        start_point = [0, s_r]\n",
    "\n",
    "        e_r = random.randint(int((self.size / 2)) + 1, self.size - 2)\n",
    "        for j in range(0, self.size):\n",
    "            if j == e_r: self.e_list.extend([50])\n",
    "            else: self.e_list.extend(\"#\")\n",
    "        goal_point = [self.size - 1, e_r]\n",
    "\n",
    "        for k in range(0, self.size):\n",
    "            self.create_mid_lines(k)\n",
    "        \n",
    "        for k in range(self.blocks):\n",
    "            self.insert_blocks(k, s_r, e_r)\n",
    "\n",
    "        return self.maze_list, start_point, goal_point"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maze functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Field(object):\n",
    "    def __init__(self, maze, start_point, goal_point):\n",
    "        self.maze = maze\n",
    "        self.start_point = start_point\n",
    "        self.goal_point = goal_point\n",
    "        self.movable_vec = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "\n",
    "    def display(self, point=None):\n",
    "        field_data = copy.deepcopy(self.maze)\n",
    "        if not point is None:\n",
    "                y, x = point\n",
    "                field_data[y][x] = \"@@\"\n",
    "        else:\n",
    "                point = \"\"\n",
    "        for line in field_data:\n",
    "                print (\"\\t\" + \"%3s \" * len(line) % tuple(line))\n",
    "\n",
    "    def get_actions(self, state):\n",
    "        movables = []\n",
    "        if state == self.start_point:\n",
    "            y = state[0] + 1\n",
    "            x = state[1]\n",
    "            a = [[y, x]]\n",
    "            return a\n",
    "        else:\n",
    "            for v in self.movable_vec:\n",
    "                y = state[0] + v[0]\n",
    "                x = state[1] + v[1]\n",
    "                if not(0 < x < len(self.maze) and\n",
    "                       0 <= y <= len(self.maze) - 1 and\n",
    "                       maze[y][x] != \"#\" and\n",
    "                       maze[y][x] != \"S\"):\n",
    "                    continue\n",
    "                movables.append([y,x])\n",
    "            if len(movables) != 0:\n",
    "                return movables\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "    def get_val(self, state):\n",
    "        y, x = state\n",
    "        if state == self.start_point: return 0, False\n",
    "        else:\n",
    "            v = float(self.maze[y][x])\n",
    "            if state == self.goal_point: \n",
    "                return v, True\n",
    "            else: \n",
    "                return v, False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generate a maze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n"
     ]
    }
   ],
   "source": [
    "size = 15\n",
    "barriar_rate = 0.1\n",
    "\n",
    "maze_1 = Maze(size, barriar_rate)\n",
    "maze, start_point, goal_point = maze_1.generate_maze()\n",
    "maze_field = Field(maze, start_point, goal_point)\n",
    "\n",
    "maze_field.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the maze with A-star algorithm\n",
    "### https://en.wikipedia.org/wiki/A*_search_algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Node(object):    \n",
    "    def __init__(self, state, start_point, goal_point):\n",
    "        self.state = state\n",
    "        self.start_point = start_point\n",
    "        self.goal_point = goal_point\n",
    "        self.hs = (self.state[0] - self.goal_point[0]) ** 2 + (self.state[1] - self.goal_point[1]) ** 2\n",
    "        self.fs = 0\n",
    "        self.parent_node = None\n",
    "    \n",
    "    def confirm_goal(self):\n",
    "        if self.goal_point == self.state: return True\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class NodeList(list):\n",
    "    def find_nodelist(self, state):\n",
    "        node_list = [t for t in self if t.state==state]\n",
    "        return node_list[0] if node_list != [] else None\n",
    "    def remove_from_nodelist(self, node):\n",
    "        del self[self.index(node)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Aster_Solver(object):\n",
    "    def __init__(self, maze, start_point, goal_point, display=False):\n",
    "        self.Field = maze\n",
    "        self.start_point = start_point\n",
    "        self.goal_point = goal_point\n",
    "        self.open_list = NodeList()\n",
    "        self.close_list = NodeList()\n",
    "        self.steps = 0\n",
    "        self.score = 0\n",
    "        self.display = display\n",
    "        \n",
    "    def set_initial_node(self):\n",
    "        node = Node(self.start_point, self.start_point, self.goal_point)\n",
    "        node.start_point = self.start_point\n",
    "        node.goal_point = self.goal_point \n",
    "        return node\n",
    "                \n",
    "    def go_next(self, next_actions, node):\n",
    "        node_gs = node.fs - node.hs\n",
    "        for action in next_actions:\n",
    "            open_list = self.open_list.find_nodelist(action)\n",
    "            dist = (node.state[0] - action[0]) ** 2 + (node.state[1] - action[1]) ** 2\n",
    "            if open_list:\n",
    "                if open_list.fs > node_gs + open_list.hs + dist:\n",
    "                    open_list.fs = node_gs + open_list.hs + dist\n",
    "                    open_list.parent_node = node\n",
    "            else:\n",
    "                open_list = self.close_list.find_nodelist(action)\n",
    "                if open_list:\n",
    "                    if open_list.fs > node_gs + open_list.hs + dist:\n",
    "                        open_list.fs = node_gs + open_list.hs + dist\n",
    "                        open_list.parent_node = node\n",
    "                        self.open_list.append(open_list)\n",
    "                        self.close_list.remove_from_nodelist(open_list)\n",
    "                else:\n",
    "                    open_list = Node(action, self.start_point, self.goal_point)\n",
    "                    open_list.fs = node_gs + open_list.hs + dist\n",
    "                    open_list.parent_node = node\n",
    "                    self.open_list.append(open_list)\n",
    "    \n",
    "    def solve_maze(self):\n",
    "        node = self.set_initial_node()\n",
    "        node.fs = node.hs\n",
    "        self.open_list.append(node)\n",
    "        \n",
    "        while True:            \n",
    "            node = min(self.open_list, key = lambda node:node.fs)\n",
    "            print (\"current state:  {0}\".format(node.state))\n",
    "            \n",
    "            if self.display:\n",
    "                self.Field.display(node.state)\n",
    "            \n",
    "            reward, tf = self.Field.get_val(node.state)\n",
    "            self.score =  self.score + reward\n",
    "            print(\"current step: {0} \\t score: {1} \\n\".format(self.steps, self.score))\n",
    "            self.steps += 1\n",
    "            if tf == True:\n",
    "                print(\"Goal!\")\n",
    "                break\n",
    "\n",
    "            self.open_list.remove_from_nodelist(node)\n",
    "            self.close_list.append(node)\n",
    "            \n",
    "            next_actions = self.Field.get_actions(node.state)   \n",
    "            self.go_next(next_actions, node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current state:  [0, 1]\n",
      "\t  #  @@   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 0 \t score: 0 \n",
      "\n",
      "current state:  [1, 1]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #  @@   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 1 \t score: 0.0 \n",
      "\n",
      "current state:  [2, 1]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #  @@  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 2 \t score: 0.0 \n",
      "\n",
      "current state:  [2, 2]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  @@   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 3 \t score: -1.0 \n",
      "\n",
      "current state:  [3, 2]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  @@   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 4 \t score: -2.0 \n",
      "\n",
      "current state:  [4, 2]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  @@  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 5 \t score: -3.0 \n",
      "\n",
      "current state:  [5, 2]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0  @@  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 6 \t score: -3.0 \n",
      "\n",
      "current state:  [5, 3]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  @@   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 7 \t score: -4.0 \n",
      "\n",
      "current state:  [6, 3]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1  @@   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 8 \t score: -4.0 \n",
      "\n",
      "current state:  [7, 3]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  @@  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 9 \t score: -5.0 \n",
      "\n",
      "current state:  [7, 4]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  @@   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 10 \t score: -6.0 \n",
      "\n",
      "current state:  [7, 5]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1  @@   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 11 \t score: -6.0 \n",
      "\n",
      "current state:  [8, 5]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  @@   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 12 \t score: -7.0 \n",
      "\n",
      "current state:  [8, 6]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1  @@   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 13 \t score: -7.0 \n",
      "\n",
      "current state:  [9, 6]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0  @@   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 14 \t score: -7.0 \n",
      "\n",
      "current state:  [9, 7]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0  @@   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 15 \t score: -7.0 \n",
      "\n",
      "current state:  [10, 7]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1  @@   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 16 \t score: -7.0 \n",
      "\n",
      "current state:  [10, 8]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0  @@   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 17 \t score: -7.0 \n",
      "\n",
      "current state:  [11, 8]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0  @@   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 18 \t score: -7.0 \n",
      "\n",
      "current state:  [12, 8]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0  @@   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 19 \t score: -7.0 \n",
      "\n",
      "current state:  [12, 9]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0  @@  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 20 \t score: -7.0 \n",
      "\n",
      "current state:  [12, 10]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  @@  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 21 \t score: -8.0 \n",
      "\n",
      "current state:  [13, 10]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  @@  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 22 \t score: -9.0 \n",
      "\n",
      "current state:  [13, 11]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  @@  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 23 \t score: -10.0 \n",
      "\n",
      "current state:  [13, 12]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  @@  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 24 \t score: -11.0 \n",
      "\n",
      "current state:  [14, 12]\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  @@   #   # \n",
      "current step: 25 \t score: 39.0 \n",
      "\n",
      "Goal!\n"
     ]
    }
   ],
   "source": [
    "astar_Solver = Aster_Solver(maze_field, start_point, goal_point, display=True)\n",
    "astar_Solver.solve_maze()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Solving the maze in Q-learning\n",
    "### https://en.wikipedia.org/wiki/Q-learning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class QLearning_Solver(object):\n",
    "    def __init__(self, maze, display=False):\n",
    "        self.Qvalue = {}\n",
    "        self.Field = maze\n",
    "        self.alpha = 0.2\n",
    "        self.gamma  = 0.9\n",
    "        self.epsilon = 0.2\n",
    "        self.steps = 0\n",
    "        self.score = 0\n",
    "        self.display = display\n",
    "\n",
    "    def qlearn(self, greedy_flg=False):\n",
    "        state = self.Field.start_point\n",
    "        while True:\n",
    "            if greedy_flg:\n",
    "                self.steps += 1\n",
    "                action = self.choose_action_greedy(state)\n",
    "                print(\"current state: {0} -> action: {1} \".format(state, action))\n",
    "                if self.display:\n",
    "                    self.Field.display(action)\n",
    "                reward, tf = self.Field.get_val(action)\n",
    "                self.score =  self.score + reward\n",
    "                print(\"current step: {0} \\t score: {1}\\n\".format(self.steps, self.score))\n",
    "                if tf == True:\n",
    "                    print(\"Goal!\")\n",
    "                    break\n",
    "            else:\n",
    "                action = self.choose_action(state)    \n",
    "            if self.update_Qvalue(state, action):\n",
    "                break\n",
    "            else:\n",
    "                state = action\n",
    "\n",
    "    def update_Qvalue(self, state, action):\n",
    "        Q_s_a = self.get_Qvalue(state, action)\n",
    "        mQ_s_a = max([self.get_Qvalue(action, n_action) for n_action in self.Field.get_actions(action)])\n",
    "        r_s_a, finish_flg = self.Field.get_val(action)\n",
    "        q_value = Q_s_a + self.alpha * ( r_s_a +  self.gamma * mQ_s_a - Q_s_a)\n",
    "        self.set_Qvalue(state, action, q_value)\n",
    "        return finish_flg\n",
    "\n",
    "\n",
    "    def get_Qvalue(self, state, action):\n",
    "        state = (state[0],state[1])\n",
    "        action = (action[0],action[1])\n",
    "        try:\n",
    "            return self.Qvalue[state][action]\n",
    "        except KeyError:\n",
    "            return 0.0\n",
    "\n",
    "    def set_Qvalue(self, state, action, q_value):\n",
    "        state = (state[0],state[1])\n",
    "        action = (action[0],action[1])\n",
    "        self.Qvalue.setdefault(state,{})\n",
    "        self.Qvalue[state][action] = q_value\n",
    "\n",
    "    def choose_action(self, state):\n",
    "        if self.epsilon < random.random():\n",
    "            return random.choice(self.Field.get_actions(state))\n",
    "        else:\n",
    "            return self.choose_action_greedy(state)\n",
    "\n",
    "    def choose_action_greedy(self, state):\n",
    "        best_actions = []\n",
    "        max_q_value = -100\n",
    "        for a in self.Field.get_actions(state):\n",
    "            q_value = self.get_Qvalue(state, a)\n",
    "            if q_value > max_q_value:\n",
    "                best_actions = [a,]\n",
    "                max_q_value = q_value\n",
    "            elif q_value == max_q_value:\n",
    "                best_actions.append(a)\n",
    "        return random.choice(best_actions)\n",
    "\n",
    "    def dump_Qvalue(self):\n",
    "        print(\"##### Dump Qvalue #####\")\n",
    "        for i, s in enumerate(self.Qvalue.keys()):\n",
    "            for a in self.Qvalue[s].keys():\n",
    "                print(\"\\t\\tQ(s, a): Q(%s, %s): %s\" % (str(s), str(a), str(self.Qvalue[s][a])))\n",
    "            if i != len(self.Qvalue.keys())-1: \n",
    "                print('\\t------------------state   action   reward')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "##### Dump Qvalue #####\n",
      "\t\tQ(s, a): Q((7, 3), (6, 3)): 6.08962977410946\n",
      "\t\tQ(s, a): Q((7, 3), (7, 4)): 8.529172560868327\n",
      "\t\tQ(s, a): Q((7, 3), (8, 3)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((7, 3), (7, 2)): 6.989629774215398\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 9), (5, 9)): 9.587969511928073\n",
      "\t\tQ(s, a): Q((6, 9), (6, 8)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((6, 9), (7, 9)): 12.151566227454845\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 3), (1, 2)): 2.3362789368857797\n",
      "\t\tQ(s, a): Q((1, 3), (2, 3)): 3.995406094920718\n",
      "\t\tQ(s, a): Q((1, 3), (1, 4)): 3.095406094920719\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 13), (9, 13)): 25.981559999999945\n",
      "\t\tQ(s, a): Q((8, 13), (7, 13)): 21.045063599999946\n",
      "\t\tQ(s, a): Q((8, 13), (8, 12)): 20.045063599999946\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 11), (10, 11)): 27.868399999999944\n",
      "\t\tQ(s, a): Q((11, 11), (11, 12)): 35.63999999999995\n",
      "\t\tQ(s, a): Q((11, 11), (12, 11)): 34.63999999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 12), (6, 12)): 15.14650148265882\n",
      "\t\tQ(s, a): Q((7, 12), (7, 13)): 21.045063599999946\n",
      "\t\tQ(s, a): Q((7, 12), (7, 11)): 15.236501515917695\n",
      "\t\tQ(s, a): Q((7, 12), (8, 12)): 20.045063599999704\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 8), (2, 7)): 5.089619947293549\n",
      "\t\tQ(s, a): Q((2, 8), (3, 8)): 6.089629774302521\n",
      "\t\tQ(s, a): Q((2, 8), (1, 8)): 4.932486764175616\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 8), (10, 8)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((9, 8), (8, 8)): 16.137737405999943\n",
      "\t\tQ(s, a): Q((9, 8), (9, 9)): 16.137737405999943\n",
      "\t\tQ(s, a): Q((9, 8), (9, 7)): 16.137737405999943\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 12), (12, 13)): 35.63999999999995\n",
      "\t\tQ(s, a): Q((12, 12), (13, 12)): 43.99999999999997\n",
      "\t\tQ(s, a): Q((12, 12), (11, 12)): 35.63999999999995\n",
      "\t\tQ(s, a): Q((12, 12), (12, 11)): 34.63999999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 1), (12, 2)): 11.261286392916295\n",
      "\t\tQ(s, a): Q((12, 1), (11, 1)): 8.11104904124649\n",
      "\t\tQ(s, a): Q((12, 1), (13, 1)): 7.969849090223142\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 6), (12, 5)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((12, 6), (13, 6)): 19.426813999999947\n",
      "\t\tQ(s, a): Q((12, 6), (12, 7)): 22.136813999999944\n",
      "\t\tQ(s, a): Q((12, 6), (11, 6)): 17.930819339999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 2), (6, 3)): 6.089629773929884\n",
      "\t\tQ(s, a): Q((6, 2), (6, 1)): 3.7616000398886213\n",
      "\t\tQ(s, a): Q((6, 2), (5, 2)): 4.761600062758689\n",
      "\t\tQ(s, a): Q((6, 2), (7, 2)): 6.989629774303795\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 6), (2, 6)): 5.39066679687267\n",
      "\t\tQ(s, a): Q((1, 6), (1, 7)): 4.580666621777187\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 7), (3, 8)): 6.0896297743038\n",
      "\t\tQ(s, a): Q((3, 7), (2, 7)): 5.0896297743038\n",
      "\t\tQ(s, a): Q((3, 7), (4, 7)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((3, 7), (3, 6)): 5.9896297743038005\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 5), (2, 6)): 5.390666796873419\n",
      "\t\tQ(s, a): Q((2, 5), (2, 4)): 3.4393401054674597\n",
      "\t\tQ(s, a): Q((2, 5), (3, 5)): 4.390666796873413\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 11), (1, 10)): 2.022999200590183\n",
      "\t\tQ(s, a): Q((1, 11), (2, 11)): 5.702103448502183\n",
      "\t\tQ(s, a): Q((1, 11), (1, 12)): -0.44857961213968905\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 5), (9, 5)): 13.071567298855273\n",
      "\t\tQ(s, a): Q((8, 5), (7, 5)): 10.587969512071421\n",
      "\t\tQ(s, a): Q((8, 5), (8, 6)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((8, 5), (8, 4)): 9.58796951188175\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 8), (5, 9)): 9.587969512076551\n",
      "\t\tQ(s, a): Q((5, 8), (5, 7)): 9.587969512076551\n",
      "\t\tQ(s, a): Q((5, 8), (6, 8)): 13.071567298859947\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 13), (12, 13)): 35.63999999999995\n",
      "\t\tQ(s, a): Q((13, 13), (13, 12)): 43.99999999999997\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 8), (10, 7)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((10, 8), (11, 8)): 22.136813999999944\n",
      "\t\tQ(s, a): Q((10, 8), (9, 8)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((10, 8), (10, 9)): 17.930819339999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 12), (14, 12)): 49.999999999999986\n",
      "\t\tQ(s, a): Q((13, 12), (12, 12)): 39.59999999999996\n",
      "\t\tQ(s, a): Q((13, 12), (13, 13)): 38.59999999999996\n",
      "\t\tQ(s, a): Q((13, 12), (13, 11)): 38.59999999999996\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 7), (5, 7)): 9.587969512076551\n",
      "\t\tQ(s, a): Q((6, 7), (6, 6)): 9.587969512076551\n",
      "\t\tQ(s, a): Q((6, 7), (6, 8)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((6, 7), (7, 7)): 13.071567298859947\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 5), (5, 6)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((5, 5), (4, 5)): 5.9896297743038005\n",
      "\t\tQ(s, a): Q((5, 5), (5, 4)): 6.0896297743038\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 7), (11, 7)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((10, 7), (10, 6)): 15.137737405999946\n",
      "\t\tQ(s, a): Q((10, 7), (10, 8)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((10, 7), (9, 7)): 16.137737405999943\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 10), (12, 10)): 30.17599999999995\n",
      "\t\tQ(s, a): Q((13, 10), (13, 9)): 30.36599999999995\n",
      "\t\tQ(s, a): Q((13, 10), (13, 11)): 38.59999999999996\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 10), (4, 10)): 9.00157888763055\n",
      "\t\tQ(s, a): Q((3, 10), (3, 9)): 6.76544093405018\n",
      "\t\tQ(s, a): Q((3, 10), (3, 11)): 8.104715354619378\n",
      "\t\tQ(s, a): Q((3, 10), (2, 10)): 5.431014786818861\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 10), (8, 9)): 13.612851364399946\n",
      "\t\tQ(s, a): Q((8, 10), (9, 10)): 13.612851364399946\n",
      "\t\tQ(s, a): Q((8, 10), (8, 11)): 18.040557239999945\n",
      "\t\tQ(s, a): Q((8, 10), (7, 10)): 14.612851364399946\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 13), (4, 12)): 12.26062684995352\n",
      "\t\tQ(s, a): Q((4, 13), (3, 13)): 6.387109106057342\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 13), (1, 13)): -1.2525994483232985\n",
      "\t\tQ(s, a): Q((2, 13), (2, 12)): -0.35604087118063066\n",
      "\t\tQ(s, a): Q((2, 13), (3, 13)): 6.105436157382291\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 7), (13, 6)): 19.426813999999947\n",
      "\t\tQ(s, a): Q((13, 7), (12, 7)): 22.136813999999944\n",
      "\t\tQ(s, a): Q((13, 7), (13, 8)): 26.32939999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 5), (12, 4)): 15.137737405999946\n",
      "\t\tQ(s, a): Q((12, 5), (12, 6)): 19.923132599999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 9), (8, 9)): 13.61285136439969\n",
      "\t\tQ(s, a): Q((7, 9), (6, 9)): 11.764410568973577\n",
      "\t\tQ(s, a): Q((7, 9), (7, 8)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((7, 9), (7, 10)): 14.612851364399946\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 1), (1, 2)): 2.3362789368857797\n",
      "\t\tQ(s, a): Q((1, 1), (2, 1)): 2.3362789368857797\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 3), (12, 2)): 11.261556474546065\n",
      "\t\tQ(s, a): Q((12, 3), (12, 4)): 15.137737405999943\n",
      "\t\tQ(s, a): Q((12, 3), (11, 3)): 12.261566999143627\n",
      "\t\tQ(s, a): Q((12, 3), (13, 3)): 12.261566656172905\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 13), (12, 13)): 35.63999999999995\n",
      "\t\tQ(s, a): Q((11, 13), (10, 13)): 28.868399999999944\n",
      "\t\tQ(s, a): Q((11, 13), (11, 12)): 35.63999999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 10), (5, 10)): 8.629172522379962\n",
      "\t\tQ(s, a): Q((4, 10), (3, 10)): 7.964920203840742\n",
      "\t\tQ(s, a): Q((4, 10), (4, 9)): 8.629163104839545\n",
      "\t\tQ(s, a): Q((4, 10), (4, 11)): 10.03691072173747\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 2), (4, 2)): 3.2854401054654616\n",
      "\t\tQ(s, a): Q((3, 2), (3, 3)): 4.4393401054674655\n",
      "\t\tQ(s, a): Q((3, 2), (2, 2)): 2.595865485428645\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 6), (2, 7)): 5.089629774303546\n",
      "\t\tQ(s, a): Q((2, 6), (2, 5)): 3.8516001171849563\n",
      "\t\tQ(s, a): Q((2, 6), (1, 6)): 3.8516001171828425\n",
      "\t\tQ(s, a): Q((2, 6), (3, 6)): 5.9896297743038005\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 2), (12, 2)): 11.259760602236558\n",
      "\t\tQ(s, a): Q((13, 2), (13, 1)): 7.993497907959563\n",
      "\t\tQ(s, a): Q((13, 2), (13, 3)): 12.261566275403666\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 6), (3, 7)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((3, 6), (2, 6)): 5.390666796873419\n",
      "\t\tQ(s, a): Q((3, 6), (4, 6)): 7.766255304782002\n",
      "\t\tQ(s, a): Q((3, 6), (3, 5)): 4.390666796873419\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 1), (12, 1)): 9.860458969875827\n",
      "\t\tQ(s, a): Q((13, 1), (13, 2)): 10.034219732124425\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 5), (4, 6)): 7.766255304782002\n",
      "\t\tQ(s, a): Q((4, 5), (4, 4)): 5.480666796873418\n",
      "\t\tQ(s, a): Q((4, 5), (5, 5)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((4, 5), (3, 5)): 4.390666796873419\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 13), (9, 13)): 25.981559999999945\n",
      "\t\tQ(s, a): Q((10, 13), (11, 13)): 32.075999999999944\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 4), (1, 3)): 2.595865485428645\n",
      "\t\tQ(s, a): Q((1, 4), (2, 4)): 3.4393401054674664\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 11), (2, 11)): 6.635623547051392\n",
      "\t\tQ(s, a): Q((3, 11), (3, 10)): 7.87481455306925\n",
      "\t\tQ(s, a): Q((3, 11), (3, 12)): 9.342799611099853\n",
      "\t\tQ(s, a): Q((3, 11), (4, 11)): 10.016692603622827\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 4), (12, 5)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((12, 4), (13, 4)): 13.623963665399932\n",
      "\t\tQ(s, a): Q((12, 4), (11, 4)): 12.623963665399927\n",
      "\t\tQ(s, a): Q((12, 4), (12, 3)): 13.623963665396445\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 5), (7, 4)): 8.529172560868892\n",
      "\t\tQ(s, a): Q((7, 5), (7, 6)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((7, 5), (8, 5)): 10.764410568973892\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 3), (2, 2)): 2.595865485428645\n",
      "\t\tQ(s, a): Q((2, 3), (1, 3)): 2.595865485428645\n",
      "\t\tQ(s, a): Q((2, 3), (2, 4)): 3.4393401054674664\n",
      "\t\tQ(s, a): Q((2, 3), (3, 3)): 4.4393401054674655\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 9), (1, 10)): 2.4499107656648085\n",
      "\t\tQ(s, a): Q((1, 9), (1, 8)): 4.924020572371647\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 7), (8, 6)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((8, 7), (8, 8)): 16.137737405999943\n",
      "\t\tQ(s, a): Q((8, 7), (7, 7)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((8, 7), (9, 7)): 16.137737405999943\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 10), (13, 10)): 33.73999999999995\n",
      "\t\tQ(s, a): Q((12, 10), (12, 9)): 27.32939999999995\n",
      "\t\tQ(s, a): Q((12, 10), (12, 11)): 34.63999999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 2), (4, 1)): 3.8568960437992015\n",
      "\t\tQ(s, a): Q((4, 2), (3, 2)): 2.9954060949201406\n",
      "\t\tQ(s, a): Q((4, 2), (5, 2)): 4.761600117185979\n",
      "\t\tQ(s, a): Q((4, 2), (4, 3)): 3.932600117186065\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 6), (8, 6)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((9, 6), (10, 6)): 15.137737405999946\n",
      "\t\tQ(s, a): Q((9, 6), (9, 5)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((9, 6), (9, 7)): 16.137737405999943\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 3), (6, 3)): 6.089629774303755\n",
      "\t\tQ(s, a): Q((5, 3), (5, 4)): 6.0896297743038\n",
      "\t\tQ(s, a): Q((5, 3), (5, 2)): 4.761600117141877\n",
      "\t\tQ(s, a): Q((5, 3), (4, 3)): 3.932600117186076\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((0, 1), (1, 1)): 2.1026510431972008\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 7), (11, 8)): 22.136813999999944\n",
      "\t\tQ(s, a): Q((11, 7), (10, 7)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((11, 7), (12, 7)): 22.136813999999944\n",
      "\t\tQ(s, a): Q((11, 7), (11, 6)): 17.930819339999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 5), (9, 5)): 13.071567298859934\n",
      "\t\tQ(s, a): Q((10, 5), (10, 6)): 15.137737405999946\n",
      "\t\tQ(s, a): Q((10, 5), (10, 4)): 12.261567298858996\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 2), (13, 2)): 10.03370770939021\n",
      "\t\tQ(s, a): Q((12, 2), (12, 1)): 10.131931878330082\n",
      "\t\tQ(s, a): Q((12, 2), (12, 3)): 13.62396313728927\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 12), (3, 11)): 8.296312717337155\n",
      "\t\tQ(s, a): Q((3, 12), (4, 12)): 12.249583435933978\n",
      "\t\tQ(s, a): Q((3, 12), (2, 12)): 3.212520391462248\n",
      "\t\tQ(s, a): Q((3, 12), (3, 13)): 7.396314665285513\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 8), (7, 8)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((6, 8), (6, 9)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((6, 8), (6, 7)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((6, 8), (5, 8)): 11.764410568973949\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 12), (1, 13)): -0.9368997478718943\n",
      "\t\tQ(s, a): Q((1, 12), (1, 11)): 2.11760074428092\n",
      "\t\tQ(s, a): Q((1, 12), (2, 12)): 1.6188502703648866\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 12), (7, 12)): 17.94055723999984\n",
      "\t\tQ(s, a): Q((8, 12), (8, 11)): 18.040557239999945\n",
      "\t\tQ(s, a): Q((8, 12), (8, 13)): 23.383403999999945\n",
      "\t\tQ(s, a): Q((8, 12), (9, 12)): 23.383403999999945\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 8), (11, 7)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((11, 8), (10, 8)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((11, 8), (12, 8)): 24.596459999999947\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 13), (7, 12)): 17.94055723999959\n",
      "\t\tQ(s, a): Q((7, 13), (8, 13)): 23.383403999999945\n",
      "\t\tQ(s, a): Q((7, 13), (6, 13)): 17.940557239999837\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 6), (13, 7)): 22.69645999999995\n",
      "\t\tQ(s, a): Q((13, 6), (12, 6)): 19.923132599999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 9), (8, 9)): 13.612851364399946\n",
      "\t\tQ(s, a): Q((9, 9), (9, 10)): 13.612851364399946\n",
      "\t\tQ(s, a): Q((9, 9), (9, 8)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((9, 9), (10, 9)): 17.930819339999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 13), (6, 12)): 15.146501515893885\n",
      "\t\tQ(s, a): Q((6, 13), (7, 13)): 21.045063599999946\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 7), (2, 7)): 5.089629774297353\n",
      "\t\tQ(s, a): Q((1, 7), (1, 8)): 4.932542432758921\n",
      "\t\tQ(s, a): Q((1, 7), (1, 6)): 3.851598464839325\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 11), (13, 12)): 43.99999999999997\n",
      "\t\tQ(s, a): Q((13, 11), (13, 10)): 33.73999999999995\n",
      "\t\tQ(s, a): Q((13, 11), (12, 11)): 34.63999999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 8), (8, 8)): 16.137737405999943\n",
      "\t\tQ(s, a): Q((7, 8), (6, 8)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((7, 8), (7, 7)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((7, 8), (7, 9)): 12.151566227959949\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 4), (3, 4)): 4.932600117186075\n",
      "\t\tQ(s, a): Q((2, 4), (2, 5)): 3.8516001171860763\n",
      "\t\tQ(s, a): Q((2, 4), (2, 3)): 3.995406094920718\n",
      "\t\tQ(s, a): Q((2, 4), (1, 4)): 3.095406094920719\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 12), (9, 13)): 25.981559999999945\n",
      "\t\tQ(s, a): Q((9, 12), (8, 12)): 20.045063599999946\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 4), (7, 4)): 8.529172560852011\n",
      "\t\tQ(s, a): Q((8, 4), (8, 3)): 8.629172560864767\n",
      "\t\tQ(s, a): Q((8, 4), (8, 5)): 10.764410568855396\n",
      "\t\tQ(s, a): Q((8, 4), (9, 4)): 11.764410568973949\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 9), (4, 9)): 8.629172554796211\n",
      "\t\tQ(s, a): Q((5, 9), (6, 9)): 11.764410568573972\n",
      "\t\tQ(s, a): Q((5, 9), (5, 10)): 8.62917255879704\n",
      "\t\tQ(s, a): Q((5, 9), (5, 8)): 11.764410568973949\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 7), (3, 7)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((4, 7), (5, 7)): 9.587969512076551\n",
      "\t\tQ(s, a): Q((4, 7), (4, 6)): 7.766255304782002\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 11), (11, 11)): 32.075999999999944\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 1), (8, 1)): 6.989141669128701\n",
      "\t\tQ(s, a): Q((9, 1), (9, 2)): 6.225292944862386\n",
      "\t\tQ(s, a): Q((9, 1), (10, 1)): 7.285821223125983\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 6), (5, 6)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((6, 6), (7, 6)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((6, 6), (6, 7)): 11.764410568973949\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 6), (5, 5)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((5, 6), (5, 7)): 9.587969512076551\n",
      "\t\tQ(s, a): Q((5, 6), (4, 6)): 7.766255304782002\n",
      "\t\tQ(s, a): Q((5, 6), (6, 6)): 9.587969512076551\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 11), (1, 11)): 2.2511349260742097\n",
      "\t\tQ(s, a): Q((2, 11), (3, 11)): 8.906759732070153\n",
      "\t\tQ(s, a): Q((2, 11), (2, 10)): 5.182758677356786\n",
      "\t\tQ(s, a): Q((2, 11), (2, 12)): 2.7037774567021446\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 6), (10, 7)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((10, 6), (10, 5)): 13.623963665399948\n",
      "\t\tQ(s, a): Q((10, 6), (9, 6)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((10, 6), (11, 6)): 17.930819339999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 7), (7, 8)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((7, 7), (7, 6)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((7, 7), (6, 7)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((7, 7), (8, 7)): 14.523963665399945\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 1), (1, 1)): 2.1026510431972008\n",
      "\t\tQ(s, a): Q((2, 1), (2, 2)): 2.595865485428645\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 9), (8, 10)): 16.236501515999944\n",
      "\t\tQ(s, a): Q((8, 9), (8, 8)): 16.137737405999943\n",
      "\t\tQ(s, a): Q((8, 9), (9, 9)): 16.137737405999943\n",
      "\t\tQ(s, a): Q((8, 9), (7, 9)): 12.151566227959558\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 12), (4, 13)): 10.945586155445403\n",
      "\t\tQ(s, a): Q((4, 12), (5, 12)): 13.63184972055372\n",
      "\t\tQ(s, a): Q((4, 12), (3, 12)): 9.952417885742184\n",
      "\t\tQ(s, a): Q((4, 12), (4, 11)): 10.02765245383349\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 12), (3, 12)): 7.560986894890597\n",
      "\t\tQ(s, a): Q((2, 12), (2, 13)): 1.3908253960232533\n",
      "\t\tQ(s, a): Q((2, 12), (2, 11)): 5.250114300123109\n",
      "\t\tQ(s, a): Q((2, 12), (1, 12)): -0.8261517262033193\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 4), (9, 5)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((9, 4), (10, 4)): 12.261567298859879\n",
      "\t\tQ(s, a): Q((9, 4), (8, 4)): 9.587969511903765\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 11), (7, 12)): 17.940557239351687\n",
      "\t\tQ(s, a): Q((7, 11), (8, 11)): 18.040557239999945\n",
      "\t\tQ(s, a): Q((7, 11), (7, 10)): 14.612851364399601\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 1), (4, 1)): 3.856890708982685\n",
      "\t\tQ(s, a): Q((5, 1), (6, 1)): 3.761550019745572\n",
      "\t\tQ(s, a): Q((5, 1), (5, 2)): 4.761600117184287\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 3), (11, 3)): 12.26155582552441\n",
      "\t\tQ(s, a): Q((10, 3), (10, 4)): 12.261567298853842\n",
      "\t\tQ(s, a): Q((10, 3), (10, 2)): 8.031859322807337\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 2), (7, 3)): 6.76625530478067\n",
      "\t\tQ(s, a): Q((7, 2), (6, 2)): 5.290666792195735\n",
      "\t\tQ(s, a): Q((7, 2), (8, 2)): 7.766255304782002\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 2), (8, 1)): 6.989623035318418\n",
      "\t\tQ(s, a): Q((8, 2), (9, 2)): 6.228673444049012\n",
      "\t\tQ(s, a): Q((8, 2), (8, 3)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((8, 2), (7, 2)): 6.989629678751605\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 2), (1, 3)): 2.595865485428645\n",
      "\t\tQ(s, a): Q((1, 2), (1, 1)): 2.1026510431972008\n",
      "\t\tQ(s, a): Q((1, 2), (2, 2)): 2.595865485428645\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 4), (7, 3)): 6.766255304600132\n",
      "\t\tQ(s, a): Q((7, 4), (7, 5)): 10.587969512076551\n",
      "\t\tQ(s, a): Q((7, 4), (8, 4)): 9.587969511811963\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 9), (5, 9)): 9.587969512065827\n",
      "\t\tQ(s, a): Q((4, 9), (3, 9)): 6.766249547291626\n",
      "\t\tQ(s, a): Q((4, 9), (4, 10)): 9.000244556782338\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 3), (2, 3)): 3.995406094920718\n",
      "\t\tQ(s, a): Q((3, 3), (3, 2)): 2.995406094920718\n",
      "\t\tQ(s, a): Q((3, 3), (3, 4)): 4.932600117186075\n",
      "\t\tQ(s, a): Q((3, 3), (4, 3)): 3.932600117186076\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 3), (13, 4)): 13.62396366539596\n",
      "\t\tQ(s, a): Q((13, 3), (13, 2)): 10.035317398641517\n",
      "\t\tQ(s, a): Q((13, 3), (12, 3)): 13.623962955128912\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 1), (8, 2)): 7.766254640455475\n",
      "\t\tQ(s, a): Q((8, 1), (9, 1)): 6.5148109082351455\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 9), (13, 9)): 30.36599999999995\n",
      "\t\tQ(s, a): Q((12, 9), (12, 10)): 30.17599999999995\n",
      "\t\tQ(s, a): Q((12, 9), (12, 8)): 24.596459999999947\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 12), (6, 12)): 15.146501515829385\n",
      "\t\tQ(s, a): Q((5, 12), (4, 12)): 12.268557744405353\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 4), (4, 5)): 5.9896297743038005\n",
      "\t\tQ(s, a): Q((4, 4), (5, 4)): 6.0896297743038\n",
      "\t\tQ(s, a): Q((4, 4), (3, 4)): 4.932600117186075\n",
      "\t\tQ(s, a): Q((4, 4), (4, 3)): 3.932600117186076\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 3), (7, 3)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((6, 3), (6, 2)): 5.290666700819661\n",
      "\t\tQ(s, a): Q((6, 3), (5, 3)): 4.480666796872504\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 8), (8, 9)): 13.612851364399946\n",
      "\t\tQ(s, a): Q((8, 8), (9, 8)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((8, 8), (7, 8)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((8, 8), (8, 7)): 14.523963665399945\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 4), (12, 4)): 15.137737405999946\n",
      "\t\tQ(s, a): Q((13, 4), (13, 3)): 12.261567297780923\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 10), (7, 11)): 15.236501515999946\n",
      "\t\tQ(s, a): Q((7, 10), (8, 10)): 16.236501515999944\n",
      "\t\tQ(s, a): Q((7, 10), (7, 9)): 12.151566227959767\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 2), (1, 2)): 2.3362789368857797\n",
      "\t\tQ(s, a): Q((2, 2), (3, 2)): 2.995406094920718\n",
      "\t\tQ(s, a): Q((2, 2), (2, 3)): 3.995406094920718\n",
      "\t\tQ(s, a): Q((2, 2), (2, 1)): 2.3362789368857797\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 10), (1, 11)): 1.9382376914175274\n",
      "\t\tQ(s, a): Q((1, 10), (1, 9)): 4.061435254907328\n",
      "\t\tQ(s, a): Q((1, 10), (2, 10)): 4.997181527411714\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 6), (8, 5)): 10.764410568973949\n",
      "\t\tQ(s, a): Q((8, 6), (7, 6)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((8, 6), (9, 6)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((8, 6), (8, 7)): 14.523963665399945\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 1), (4, 2)): 3.2854400509960704\n",
      "\t\tQ(s, a): Q((4, 1), (5, 1)): 4.285440094876422\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 11), (7, 11)): 15.236501515999947\n",
      "\t\tQ(s, a): Q((8, 11), (8, 10)): 16.236501515999944\n",
      "\t\tQ(s, a): Q((8, 11), (8, 12)): 20.045063599999946\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 9), (10, 8)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((10, 9), (9, 9)): 16.137737405999943\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 7), (10, 7)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((9, 7), (9, 8)): 17.930819339999942\n",
      "\t\tQ(s, a): Q((9, 7), (9, 6)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((9, 7), (8, 7)): 14.523963665399945\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 4), (4, 4)): 5.480666796873418\n",
      "\t\tQ(s, a): Q((5, 4), (5, 5)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((5, 4), (5, 3)): 4.480666796873418\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 4), (12, 4)): 15.137737405999946\n",
      "\t\tQ(s, a): Q((11, 4), (11, 3)): 12.261565646046707\n",
      "\t\tQ(s, a): Q((11, 4), (10, 4)): 12.261567157810315\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 4), (11, 4)): 12.623963664180664\n",
      "\t\tQ(s, a): Q((10, 4), (10, 5)): 13.623963665399948\n",
      "\t\tQ(s, a): Q((10, 4), (10, 3)): 10.035410555821395\n",
      "\t\tQ(s, a): Q((10, 4), (9, 4)): 11.764410364112514\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 13), (4, 13)): 10.209099268143577\n",
      "\t\tQ(s, a): Q((3, 13), (2, 13)): 1.2171719551303446\n",
      "\t\tQ(s, a): Q((3, 13), (3, 12)): 8.461262012650055\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 13), (2, 13)): 1.0388385235435007\n",
      "\t\tQ(s, a): Q((1, 13), (1, 12)): -0.27176320720805436\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 7), (11, 7)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((12, 7), (13, 7)): 22.69645999999995\n",
      "\t\tQ(s, a): Q((12, 7), (12, 6)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((12, 7), (12, 8)): 24.596459999999947\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 11), (12, 10)): 30.17599999999995\n",
      "\t\tQ(s, a): Q((12, 11), (12, 12)): 39.59999999999996\n",
      "\t\tQ(s, a): Q((12, 11), (11, 11)): 32.075999999999944\n",
      "\t\tQ(s, a): Q((12, 11), (13, 11)): 38.59999999999996\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 1), (12, 1)): 10.133736568025602\n",
      "\t\tQ(s, a): Q((11, 1), (10, 1)): 7.287793269487306\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 10), (1, 10)): 2.80731787575435\n",
      "\t\tQ(s, a): Q((2, 10), (3, 10)): 7.6191194546795264\n",
      "\t\tQ(s, a): Q((2, 10), (2, 11)): 5.88325886235407\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 10), (9, 9)): 16.137737405999943\n",
      "\t\tQ(s, a): Q((9, 10), (8, 10)): 16.236501515999944\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 8), (13, 9)): 30.36599999999995\n",
      "\t\tQ(s, a): Q((13, 8), (13, 7)): 22.69645999999995\n",
      "\t\tQ(s, a): Q((13, 8), (12, 8)): 24.596459999999947\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((13, 9), (13, 10)): 33.73999999999995\n",
      "\t\tQ(s, a): Q((13, 9), (12, 9)): 27.32939999999995\n",
      "\t\tQ(s, a): Q((13, 9), (13, 8)): 26.32939999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 12), (7, 12)): 17.940556980527983\n",
      "\t\tQ(s, a): Q((6, 12), (5, 12)): 13.631851343352055\n",
      "\t\tQ(s, a): Q((6, 12), (6, 13)): 17.940557239999848\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 12), (12, 12)): 39.59999999999996\n",
      "\t\tQ(s, a): Q((11, 12), (11, 11)): 32.075999999999944\n",
      "\t\tQ(s, a): Q((11, 12), (11, 13)): 32.075999999999944\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 11), (4, 10)): 8.995063375536166\n",
      "\t\tQ(s, a): Q((4, 11), (4, 12)): 12.26796424946557\n",
      "\t\tQ(s, a): Q((4, 11), (3, 11)): 8.971902987527042\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 5), (4, 5)): 5.9896297743038005\n",
      "\t\tQ(s, a): Q((3, 5), (2, 5)): 3.8516001171860763\n",
      "\t\tQ(s, a): Q((3, 5), (3, 4)): 4.932600117186075\n",
      "\t\tQ(s, a): Q((3, 5), (3, 6)): 5.9896297743038005\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((2, 7), (3, 7)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((2, 7), (2, 6)): 5.39066679671355\n",
      "\t\tQ(s, a): Q((2, 7), (2, 8)): 5.480666674418735\n",
      "\t\tQ(s, a): Q((2, 7), (1, 7)): 4.58066679638875\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 13), (10, 13)): 28.868399999999944\n",
      "\t\tQ(s, a): Q((9, 13), (8, 13)): 23.383403999999945\n",
      "\t\tQ(s, a): Q((9, 13), (9, 12)): 23.383403999999945\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((8, 3), (7, 3)): 6.766255304781967\n",
      "\t\tQ(s, a): Q((8, 3), (8, 2)): 7.76625530478051\n",
      "\t\tQ(s, a): Q((8, 3), (8, 4)): 9.587969512076551\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 1), (11, 1)): 8.115175441724814\n",
      "\t\tQ(s, a): Q((10, 1), (9, 1)): 6.529130313849249\n",
      "\t\tQ(s, a): Q((10, 1), (10, 2)): 8.03186323935532\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 10), (5, 9)): 9.587969512009101\n",
      "\t\tQ(s, a): Q((5, 10), (4, 10)): 9.007662623301739\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 6), (4, 5)): 5.9896297743038005\n",
      "\t\tQ(s, a): Q((4, 6), (5, 6)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((4, 6), (4, 7)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((4, 6), (3, 6)): 5.9896297743038005\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 2), (9, 1)): 6.533344198798328\n",
      "\t\tQ(s, a): Q((9, 2), (8, 2)): 7.766153396296672\n",
      "\t\tQ(s, a): Q((9, 2), (10, 2)): 8.031867772084851\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 4), (2, 4)): 3.4393401054674664\n",
      "\t\tQ(s, a): Q((3, 4), (4, 4)): 5.480666796873418\n",
      "\t\tQ(s, a): Q((3, 4), (3, 3)): 4.4393401054674655\n",
      "\t\tQ(s, a): Q((3, 4), (3, 5)): 4.390666796873419\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((6, 1), (5, 1)): 4.28543154158554\n",
      "\t\tQ(s, a): Q((6, 1), (6, 2)): 5.290666784589486\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 7), (5, 6)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((5, 7), (4, 7)): 8.629172560868893\n",
      "\t\tQ(s, a): Q((5, 7), (6, 7)): 11.764410568973949\n",
      "\t\tQ(s, a): Q((5, 7), (5, 8)): 11.764410568973949\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 3), (10, 3)): 10.035395613771726\n",
      "\t\tQ(s, a): Q((11, 3), (11, 4)): 12.623955122917335\n",
      "\t\tQ(s, a): Q((11, 3), (12, 3)): 13.623963664686293\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 8), (3, 7)): 6.766255304782002\n",
      "\t\tQ(s, a): Q((3, 8), (3, 9)): 6.766251886318812\n",
      "\t\tQ(s, a): Q((3, 8), (2, 8)): 5.480666779272024\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 13), (12, 12)): 39.59999999999996\n",
      "\t\tQ(s, a): Q((12, 13), (13, 13)): 38.59999999999996\n",
      "\t\tQ(s, a): Q((12, 13), (11, 13)): 32.075999999999944\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((1, 8), (2, 8)): 5.4806656032998085\n",
      "\t\tQ(s, a): Q((1, 8), (1, 9)): 4.3949810538507075\n",
      "\t\tQ(s, a): Q((1, 8), (1, 7)): 4.580345237870564\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((3, 9), (3, 8)): 6.089500727929055\n",
      "\t\tQ(s, a): Q((3, 9), (3, 10)): 7.957189279731195\n",
      "\t\tQ(s, a): Q((3, 9), (4, 9)): 8.62917253131752\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((4, 3), (4, 2)): 3.2854401054280125\n",
      "\t\tQ(s, a): Q((4, 3), (4, 4)): 5.480666796873418\n",
      "\t\tQ(s, a): Q((4, 3), (3, 3)): 4.4393401054674655\n",
      "\t\tQ(s, a): Q((4, 3), (5, 3)): 4.480666796873418\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((9, 5), (8, 5)): 10.764410568973949\n",
      "\t\tQ(s, a): Q((9, 5), (10, 5)): 13.623963665399948\n",
      "\t\tQ(s, a): Q((9, 5), (9, 6)): 14.523963665399945\n",
      "\t\tQ(s, a): Q((9, 5), (9, 4)): 11.764410568966648\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((12, 8), (11, 8)): 22.136813999999944\n",
      "\t\tQ(s, a): Q((12, 8), (12, 7)): 22.136813999999944\n",
      "\t\tQ(s, a): Q((12, 8), (12, 9)): 27.32939999999995\n",
      "\t\tQ(s, a): Q((12, 8), (13, 8)): 26.32939999999995\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((5, 2), (5, 1)): 4.285440097284288\n",
      "\t\tQ(s, a): Q((5, 2), (6, 2)): 5.290666796873388\n",
      "\t\tQ(s, a): Q((5, 2), (4, 2)): 3.2854401029146745\n",
      "\t\tQ(s, a): Q((5, 2), (5, 3)): 4.480666796873418\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((7, 6), (8, 6)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((7, 6), (7, 5)): 10.587969512076551\n",
      "\t\tQ(s, a): Q((7, 6), (7, 7)): 13.071567298859947\n",
      "\t\tQ(s, a): Q((7, 6), (6, 6)): 9.587969512076551\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((11, 6), (11, 7)): 19.923132599999942\n",
      "\t\tQ(s, a): Q((11, 6), (10, 6)): 15.137737405999946\n",
      "\t\tQ(s, a): Q((11, 6), (12, 6)): 19.923132599999942\n",
      "\t------------------state   action   reward\n",
      "\t\tQ(s, a): Q((10, 2), (9, 2)): 6.228357465208626\n",
      "\t\tQ(s, a): Q((10, 2), (10, 3)): 10.035410562805302\n",
      "\t\tQ(s, a): Q((10, 2), (10, 1)): 7.291350868799238\n"
     ]
    }
   ],
   "source": [
    "learning_count = 1000\n",
    "QL_solver = QLearning_Solver(maze_field, display=True)\n",
    "for i in range(learning_count):\n",
    "    QL_solver.qlearn()\n",
    "\n",
    "QL_solver.dump_Qvalue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current state: [0, 1] -> action: [1, 1] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #  @@   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 1 \t score: 0.0\n",
      "\n",
      "current state: [1, 1] -> action: [2, 1] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #  @@  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 2 \t score: 0.0\n",
      "\n",
      "current state: [2, 1] -> action: [2, 2] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  @@   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 3 \t score: -1.0\n",
      "\n",
      "current state: [2, 2] -> action: [2, 3] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1  @@  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 4 \t score: -1.0\n",
      "\n",
      "current state: [2, 3] -> action: [3, 3] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1  @@   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 5 \t score: -1.0\n",
      "\n",
      "current state: [3, 3] -> action: [3, 4] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0  @@  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 6 \t score: -1.0\n",
      "\n",
      "current state: [3, 4] -> action: [4, 4] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1  @@  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 7 \t score: -1.0\n",
      "\n",
      "current state: [4, 4] -> action: [5, 4] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1  @@  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 8 \t score: -1.0\n",
      "\n",
      "current state: [5, 4] -> action: [5, 5] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  @@   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 9 \t score: -2.0\n",
      "\n",
      "current state: [5, 5] -> action: [5, 6] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1  @@  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 10 \t score: -2.0\n",
      "\n",
      "current state: [5, 6] -> action: [6, 6] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  @@   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 11 \t score: -3.0\n",
      "\n",
      "current state: [6, 6] -> action: [6, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1  @@   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 12 \t score: -3.0\n",
      "\n",
      "current state: [6, 7] -> action: [6, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0  @@   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 13 \t score: -3.0\n",
      "\n",
      "current state: [6, 8] -> action: [7, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0  @@  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 14 \t score: -3.0\n",
      "\n",
      "current state: [7, 8] -> action: [8, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0  @@  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 15 \t score: -3.0\n",
      "\n",
      "current state: [8, 8] -> action: [9, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0  @@   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 16 \t score: -3.0\n",
      "\n",
      "current state: [9, 8] -> action: [10, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0  @@   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 17 \t score: -3.0\n",
      "\n",
      "current state: [10, 8] -> action: [11, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0  @@   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 18 \t score: -3.0\n",
      "\n",
      "current state: [11, 8] -> action: [12, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0  @@   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 19 \t score: -3.0\n",
      "\n",
      "current state: [12, 8] -> action: [12, 9] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0  @@  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 20 \t score: -3.0\n",
      "\n",
      "current state: [12, 9] -> action: [13, 9] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1  @@  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 21 \t score: -3.0\n",
      "\n",
      "current state: [13, 9] -> action: [13, 10] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  @@  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 22 \t score: -4.0\n",
      "\n",
      "current state: [13, 10] -> action: [13, 11] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  @@  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 23 \t score: -5.0\n",
      "\n",
      "current state: [13, 11] -> action: [13, 12] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  @@  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 24 \t score: -6.0\n",
      "\n",
      "current state: [13, 12] -> action: [14, 12] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  @@   #   # \n",
      "current step: 25 \t score: 44.0\n",
      "\n",
      "Goal!\n"
     ]
    }
   ],
   "source": [
    "QL_solver.qlearn(greedy_flg=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Solving the maze in Deep Q-learning\n",
    "### https://deepmind.com/research/dqn/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class DQN_Solver:\n",
    "    def __init__(self, state_size, action_size):\n",
    "        self.state_size = state_size # list size of state\n",
    "        self.action_size = action_size # list size of action\n",
    "        self.memory = deque(maxlen=100000) # memory space\n",
    "        self.gamma = 0.9 # discount rate\n",
    "        self.epsilon = 1.0 # randomness of choosing random action or the best one\n",
    "        self.e_decay = 0.9999 # epsilon decay rate\n",
    "        self.e_min = 0.01 # minimum rate of epsilon\n",
    "        self.learning_rate = 0.0001 # learning rate of neural network\n",
    "        self.model = self.build_model() # model\n",
    "        self.model.summary() # model summary\n",
    "\n",
    "    # model for neural network\n",
    "    def build_model(self):\n",
    "        model = Sequential()\n",
    "        model.add(Dense(128, input_shape=(2,2), activation='tanh'))\n",
    "        model.add(Flatten())\n",
    "        model.add(Dense(128, activation='tanh'))\n",
    "        model.add(Dense(128, activation='tanh'))\n",
    "        model.add(Dense(1, activation='linear'))\n",
    "        model.compile(loss=\"mse\", optimizer=RMSprop(lr=self.learning_rate))\n",
    "        return model\n",
    "\n",
    "    # remember state, action, its reward, next state and next possible action. done means boolean for goal\n",
    "    def remember_memory(self, state, action, reward, next_state, next_movables, done):\n",
    "        self.memory.append((state, action, reward, next_state, next_movables, done))\n",
    "\n",
    "    # choosing action depending on epsilon\n",
    "    def choose_action(self, state, movables):\n",
    "        if self.epsilon >= random.random():\n",
    "            # randomly choosing action\n",
    "            return random.choice(movables)\n",
    "        else:\n",
    "            # choosing the best action from model.predict()\n",
    "            return self.choose_best_action(state, movables)\n",
    "        \n",
    "    # choose the best action to maximize reward expectation\n",
    "    def choose_best_action(self, state, movables):\n",
    "        best_actions = []\n",
    "        max_act_value = -100\n",
    "        for a in movables:\n",
    "            np_action = np.array([[state, a]])\n",
    "            act_value = self.model.predict(np_action)\n",
    "            if act_value > max_act_value:\n",
    "                best_actions = [a,]\n",
    "                max_act_value = act_value\n",
    "            elif act_value == max_act_value:\n",
    "                best_actions.append(a)\n",
    "        return random.choice(best_actions)\n",
    "\n",
    "    # this experience replay is going to train the model from memorized states, actions and rewards\n",
    "    def replay_experience(self, batch_size):\n",
    "        batch_size = min(batch_size, len(self.memory))\n",
    "        minibatch = random.sample(self.memory, batch_size)\n",
    "        X = []\n",
    "        Y = []\n",
    "        for i in range(batch_size):\n",
    "            state, action, reward, next_state, next_movables, done = minibatch[i]\n",
    "            input_action = [state, action]\n",
    "            if done:\n",
    "                target_f = reward\n",
    "            else:\n",
    "                next_rewards = []\n",
    "                for i in next_movables:\n",
    "                    np_next_s_a = np.array([[next_state, i]])\n",
    "                    next_rewards.append(self.model.predict(np_next_s_a))\n",
    "                np_n_r_max = np.amax(np.array(next_rewards))\n",
    "                target_f = reward + self.gamma * np_n_r_max\n",
    "            X.append(input_action)\n",
    "            Y.append(target_f)\n",
    "        np_X = np.array(X)\n",
    "        np_Y = np.array([Y]).T\n",
    "        self.model.fit(np_X, np_Y, epochs=1, verbose=0)\n",
    "        if self.epsilon > self.e_min:\n",
    "            self.epsilon *= self.e_decay"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "_________________________________________________________________\n",
      "Layer (type)                 Output Shape              Param #   \n",
      "=================================================================\n",
      "dense_13 (Dense)             (None, 2, 128)            384       \n",
      "_________________________________________________________________\n",
      "flatten_4 (Flatten)          (None, 256)               0         \n",
      "_________________________________________________________________\n",
      "dense_14 (Dense)             (None, 128)               32896     \n",
      "_________________________________________________________________\n",
      "dense_15 (Dense)             (None, 128)               16512     \n",
      "_________________________________________________________________\n",
      "dense_16 (Dense)             (None, 1)                 129       \n",
      "=================================================================\n",
      "Total params: 49,921.0\n",
      "Trainable params: 49,921.0\n",
      "Non-trainable params: 0.0\n",
      "_________________________________________________________________\n",
      "episode: 0/20000, score: 12.0, e: 1.0 \t @ 156\n",
      "episode: 500/20000, score: -209.0, e: 0.95 \t @ 644\n",
      "episode: 1000/20000, score: -118.0, e: 0.9 \t @ 494\n",
      "episode: 1500/20000, score: -20.0, e: 0.86 \t @ 228\n",
      "episode: 2000/20000, score: 6.0, e: 0.82 \t @ 128\n",
      "episode: 2500/20000, score: 11.0, e: 0.78 \t @ 98\n",
      "episode: 3000/20000, score: -38.0, e: 0.74 \t @ 192\n",
      "episode: 3500/20000, score: 9.0, e: 0.7 \t @ 112\n",
      "episode: 4000/20000, score: 10.0, e: 0.67 \t @ 120\n",
      "episode: 4500/20000, score: 20.0, e: 0.64 \t @ 100\n",
      "episode: 5000/20000, score: 8.0, e: 0.61 \t @ 122\n",
      "episode: 5500/20000, score: 32.0, e: 0.58 \t @ 40\n",
      "episode: 6000/20000, score: 38.0, e: 0.55 \t @ 36\n",
      "episode: 6500/20000, score: 23.0, e: 0.52 \t @ 90\n",
      "episode: 7000/20000, score: 35.0, e: 0.5 \t @ 54\n",
      "episode: 7500/20000, score: 36.0, e: 0.47 \t @ 38\n",
      "episode: 8000/20000, score: 38.0, e: 0.45 \t @ 46\n",
      "episode: 8500/20000, score: 38.0, e: 0.43 \t @ 46\n",
      "episode: 9000/20000, score: 41.0, e: 0.41 \t @ 34\n",
      "episode: 9500/20000, score: 35.0, e: 0.39 \t @ 40\n",
      "episode: 10000/20000, score: 40.0, e: 0.37 \t @ 30\n",
      "episode: 10500/20000, score: 36.0, e: 0.35 \t @ 44\n",
      "episode: 11000/20000, score: 42.0, e: 0.33 \t @ 28\n",
      "episode: 11500/20000, score: 35.0, e: 0.32 \t @ 34\n",
      "episode: 12000/20000, score: 37.0, e: 0.3 \t @ 38\n",
      "episode: 12500/20000, score: 39.0, e: 0.29 \t @ 42\n",
      "episode: 13000/20000, score: 43.0, e: 0.27 \t @ 26\n",
      "episode: 13500/20000, score: 40.0, e: 0.26 \t @ 30\n",
      "episode: 14000/20000, score: 43.0, e: 0.25 \t @ 28\n",
      "episode: 14500/20000, score: 39.0, e: 0.23 \t @ 30\n",
      "episode: 15000/20000, score: 43.0, e: 0.22 \t @ 26\n",
      "episode: 15500/20000, score: 43.0, e: 0.21 \t @ 28\n",
      "episode: 16000/20000, score: 44.0, e: 0.2 \t @ 24\n",
      "episode: 16500/20000, score: 42.0, e: 0.19 \t @ 28\n",
      "episode: 17000/20000, score: 43.0, e: 0.18 \t @ 28\n",
      "episode: 17500/20000, score: 44.0, e: 0.17 \t @ 24\n",
      "episode: 18000/20000, score: 40.0, e: 0.17 \t @ 30\n",
      "episode: 18500/20000, score: 44.0, e: 0.16 \t @ 24\n",
      "episode: 19000/20000, score: 39.0, e: 0.15 \t @ 30\n",
      "episode: 19500/20000, score: 42.0, e: 0.14 \t @ 28\n"
     ]
    }
   ],
   "source": [
    "state_size = 2\n",
    "action_size = 2\n",
    "dql_solver = DQN_Solver(state_size, action_size)\n",
    "\n",
    "# number of episodes to run training\n",
    "episodes = 20000\n",
    "\n",
    "# number of times to sample the combination of state, action and reward\n",
    "times = 1000\n",
    "\n",
    "for e in range(episodes):\n",
    "    state = start_point\n",
    "    score = 0\n",
    "    for time in range(times):\n",
    "        movables = maze_field.get_actions(state)\n",
    "        action = dql_solver.choose_action(state, movables)\n",
    "        reward, done = maze_field.get_val(action)\n",
    "        score = score + reward\n",
    "        next_state = action\n",
    "        next_movables = maze_field.get_actions(next_state)\n",
    "        dql_solver.remember_memory(state, action, reward, next_state, next_movables, done)\n",
    "        if done or time == (times - 1):\n",
    "            if e % 500 == 0:\n",
    "                print(\"episode: {}/{}, score: {}, e: {:.2} \\t @ {}\"\n",
    "                        .format(e, episodes, score, dql_solver.epsilon, time))\n",
    "            break\n",
    "        state = next_state\n",
    "    # run experience replay after sampling the state, action and reward for defined times\n",
    "    dql_solver.replay_experience(32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current state: [0, 1] -> action: [1, 1] \n",
      "\t  #  @@   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 1 \t score: 0.0\n",
      "\n",
      "current state: [1, 1] -> action: [1, 2] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #  @@   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 2 \t score: 0.0\n",
      "\n",
      "current state: [1, 2] -> action: [2, 2] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0  @@  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 3 \t score: -1.0\n",
      "\n",
      "current state: [2, 2] -> action: [2, 3] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  @@   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 4 \t score: -1.0\n",
      "\n",
      "current state: [2, 3] -> action: [3, 3] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1  @@  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 5 \t score: -1.0\n",
      "\n",
      "current state: [3, 3] -> action: [3, 4] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1  @@   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 6 \t score: -1.0\n",
      "\n",
      "current state: [3, 4] -> action: [4, 4] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0  @@  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 7 \t score: -1.0\n",
      "\n",
      "current state: [4, 4] -> action: [5, 4] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1  @@  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 8 \t score: -1.0\n",
      "\n",
      "current state: [5, 4] -> action: [5, 5] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1  @@  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 9 \t score: -2.0\n",
      "\n",
      "current state: [5, 5] -> action: [5, 6] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  @@   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 10 \t score: -2.0\n",
      "\n",
      "current state: [5, 6] -> action: [5, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1  @@  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 11 \t score: -3.0\n",
      "\n",
      "current state: [5, 7] -> action: [6, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  @@   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 12 \t score: -3.0\n",
      "\n",
      "current state: [6, 7] -> action: [7, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1  @@   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 13 \t score: -3.0\n",
      "\n",
      "current state: [7, 7] -> action: [8, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0  @@   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 14 \t score: -3.0\n",
      "\n",
      "current state: [8, 7] -> action: [9, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0  @@   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 15 \t score: -3.0\n",
      "\n",
      "current state: [9, 7] -> action: [10, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0  @@   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 16 \t score: -3.0\n",
      "\n",
      "current state: [10, 7] -> action: [11, 7] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1  @@   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 17 \t score: -3.0\n",
      "\n",
      "current state: [11, 7] -> action: [11, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0  @@   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 18 \t score: -3.0\n",
      "\n",
      "current state: [11, 8] -> action: [12, 8] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0  @@   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 19 \t score: -3.0\n",
      "\n",
      "current state: [12, 8] -> action: [12, 9] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0  @@   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 20 \t score: -3.0\n",
      "\n",
      "current state: [12, 9] -> action: [13, 9] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0  @@  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 21 \t score: -3.0\n",
      "\n",
      "current state: [13, 9] -> action: [13, 10] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1  @@  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 22 \t score: -4.0\n",
      "\n",
      "current state: [13, 10] -> action: [13, 11] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  @@  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 23 \t score: -5.0\n",
      "\n",
      "current state: [13, 11] -> action: [13, 12] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  @@  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 24 \t score: -6.0\n",
      "\n",
      "current state: [13, 12] -> action: [14, 12] \n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  @@  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  50   #   # \n",
      "current step: 25 \t score: 44.0\n",
      "\n",
      "\t  #   S   #   #   #   #   #   #   #   #   #   #   #   #   # \n",
      "\t  #   0   0  -1   0   #  -1   0   0   0  -1  -1  -1  -1   # \n",
      "\t  #   0  -1   0  -1  -1   0  -1   0   #  -1  -1  -1  -1   # \n",
      "\t  #   #  -1   0   0  -1  -1  -1   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1  -1   0  -1   0   0   #   0   0  -1   0   0   # \n",
      "\t  #   0   0  -1   0  -1   0  -1   0  -1   0   #   0   #   # \n",
      "\t  #  -1  -1   0   #   #  -1   0   0   0   #   #  -1  -1   # \n",
      "\t  #   #   0  -1  -1   0   0   0   0  -1   0  -1  -1   0   # \n",
      "\t  #   0   0   0  -1  -1   0   0   0  -1   0   0  -1   0   # \n",
      "\t  #   0  -1   #   0   0   0   0   0   0  -1   #   0   0   # \n",
      "\t  #   0  -1  -1   0   0  -1   0   0   0   #  -1   #   0   # \n",
      "\t  #  -1   #   0  -1   #   0   0   0   #   #   0   0   0   # \n",
      "\t  #   0  -1   0  -1   0   0   0   0   0  -1  -1   0   0   # \n",
      "\t  #  -1  -1   0   0   #  -1  -1  -1   0  -1  -1  -1  -1   # \n",
      "\t  #   #   #   #   #   #   #   #   #   #   #   #  @@   #   # \n",
      "goal!\n"
     ]
    }
   ],
   "source": [
    "# try the model\n",
    "state = start_point\n",
    "score = 0\n",
    "steps = 0\n",
    "while True:\n",
    "    steps += 1\n",
    "    movables = maze_field.get_actions(state)\n",
    "    action = dql_solver.choose_best_action(state, movables)\n",
    "    print(\"current state: {0} -> action: {1} \".format(state, action))\n",
    "    reward, done = maze_field.get_val(action)\n",
    "    maze_field.display(state)\n",
    "    score = score + reward\n",
    "    state = action\n",
    "    print(\"current step: {0} \\t score: {1}\\n\".format(steps, score))\n",
    "    if done:\n",
    "        maze_field.display(action)\n",
    "        print(\"goal!\")\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}