1_part/3_02_RL_Chess_2_model_free_methods.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"kernelspec":{"display_name":"Python 3","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.6.6"},"colab":{"name":"Reinforcement_Learning_Chess_2_model_free_methods.ipynb","provenance":[],"collapsed_sections":[],"toc_visible":true}},"cells":[{"cell_type":"markdown","metadata":{"colab_type":"text","id":"hhkArxVLKHF4"},"source":["# 0. 강화학습을 이용한 체스 (Reinforcement Learning Chess) - 2\n","\n","※본 커널은 캐글을 통해 공유된 https://www.kaggle.com/arjanso/reinforcement-learning-chess-2-model-free-methods 의 내용을 기반으로 작성되었습니다.\n","\n"]},{"cell_type":"markdown","metadata":{"id":"_gNTIKXYQzBI","colab_type":"text"},"source":["# Reinforcement Learning Chess \n","Reinforcement Learning Chess는 체스 AI를 개발하기 위해 강화 학습 알고리즘을 구현하는 일련의 Notebook입니다. 간단한 방법으로 다루어 질 수 있는 더 단순한 버전 (환경)으로 시작하여 본격적인 체스 인공 지능이 생길 때까지 이러한 개념을 점차적으로 확장합니다.\n","\n","[**Notebook 1: Policy Iteration**](https://www.kaggle.com/arjanso/reinforcement-learning-chess-1-policy-iteration)  \n","[**Notebook 3: Q-networks**](https://www.kaggle.com/arjanso/reinforcement-learning-chess-3-q-networks)  \n","[**Notebook 4: Policy Gradients**](https://www.kaggle.com/arjanso/reinforcement-learning-chess-4-policy-gradients)  \n","[**Notebook 5: Monte Carlo Tree Search**](https://www.kaggle.com/arjanso/reinforcement-learning-chess-5-tree-search)  "]},{"cell_type":"markdown","metadata":{"id":"kfYqSne6QzBM","colab_type":"text"},"source":["# Notebook II: Model-free control\n","이 Notebook에서는 Notebook 1과 동일한 체스말 이동 environment를 사용합니다.이 Notebook에서는 정책평가(policy evaluation)는 후속 상태값(state values)과 전환확률(transition probabilities)을 해당 상태로 백업하여 상태값(state values)을 계산합니다. 문제는 이러한 확률은 일반적으로 실제 문제에서 알 수 없다는 것입니다. 운 좋게 이러한 알 수 없는 environment에서 작동 할 수 있는  기술이 있습니다. 이러한 기술은 environment에 대한 사전 지식을 활용하지 않는 model-free 기술입니다."]},{"cell_type":"code","metadata":{"id":"bFJcLGDrQzBO","colab_type":"code","colab":{}},"source":["%load_ext autoreload\n","%autoreload 2"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","id":"UE1h9EYAQzBS","colab_type":"code","colab":{}},"source":["import numpy as np # linear algebra\n","import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n","import inspect"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","id":"wyLsrKBCQzBX","colab_type":"code","outputId":"26614c03-3f27-448e-f29c-fc98293d69ba","colab":{"base_uri":"https://localhost:8080/","height":200},"executionInfo":{"status":"ok","timestamp":1581998216082,"user_tz":-540,"elapsed":8125,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["!pip install --upgrade git+https://github.com/arjangroen/RLC.git  # RLC is the Reinforcement Learning package"],"execution_count":3,"outputs":[{"output_type":"stream","text":["Collecting git+https://github.com/arjangroen/RLC.git\n","  Cloning https://github.com/arjangroen/RLC.git to /tmp/pip-req-build-p139r2vn\n","  Running command git clone -q https://github.com/arjangroen/RLC.git /tmp/pip-req-build-p139r2vn\n","Building wheels for collected packages: RLC\n","  Building wheel for RLC (setup.py) ... \u001b[?25l\u001b[?25hdone\n","  Created wheel for RLC: filename=RLC-0.3-cp36-none-any.whl size=22568 sha256=a479faa3517ebfb3ef3edc3450b927b7ece5a42c6abfa055583e108f8891d439\n","  Stored in directory: /tmp/pip-ephem-wheel-cache-7z00s2ye/wheels/04/68/a5/cb835cd3d76a49de696a942739c71a56bfe66d0d8ea7b4b446\n","Successfully built RLC\n","Installing collected packages: RLC\n","Successfully installed RLC-0.3\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"tDd9cDy3QzBc","colab_type":"code","colab":{}},"source":["from RLC.move_chess.environment import Board\n","from RLC.move_chess.agent import Piece\n","from RLC.move_chess.learn import Reinforce"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"HuoZfl0IQzBf","colab_type":"text"},"source":["### 2.0.1 The environment\n","- 상태(state) 공간은 8x8의 그리드입니다\n","- 시작 상태(state) S는 왼쪽 위 사각형 (0, 0)을 기준으로 합니다.\n","- 종료 상태(state) F의 좌표는 (5, 7) 입니다.\n","- 한 상태(state)에서 다른 상태(state)로 이동할 때마다 보상(reward)을 1 감소시킵니다.\n","- 이 환경(environment)에 대한 최상의 정책(policy)은 가장 적은 수의 움직임으로 S로부터 F까지 움직이는 것입니다."]},{"cell_type":"code","metadata":{"id":"eBICe7rnQzBh","colab_type":"code","outputId":"ce96e7c6-8704-4e83-b50d-4029ea81704f","colab":{"base_uri":"https://localhost:8080/","height":147},"executionInfo":{"status":"ok","timestamp":1581998223370,"user_tz":-540,"elapsed":633,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["env = Board()\n","env.render()\n","env.visual_board"],"execution_count":5,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[['[S]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[F]', '[ ]', '[ ]']]"]},"metadata":{"tags":[]},"execution_count":5}]},{"cell_type":"markdown","metadata":{"id":"qScLiAspQzBm","colab_type":"text"},"source":["### 2.0.2 The agent\n","- 에이전트(agent)는 체스 말입니다. (킹, 퀸, 룩, 나이트, 비숍 등)\n","- 에이전트(agent)는 에이전트가 어떤 상태(state)에서 무엇을 하는지 결정하는 행동 정책(policy)을 갖고 있습니다."]},{"cell_type":"code","metadata":{"id":"80rZ40_DQzBn","colab_type":"code","colab":{}},"source":["p = Piece(piece='king')"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"UoNzDznlQzBr","colab_type":"text"},"source":["### 2.0.3 Reinforce\n","- 강화(reinforce) 객체에는 체스 말을 움직이는 문제를 해결하기 위한 알고리즘이 포함되어 있습니다.\n","- 에이전트(agent)와 환경(environment)은 강화(reinforce) 객체의 속성(attributes)입니다."]},{"cell_type":"code","metadata":{"id":"_2YSp1q9QzBs","colab_type":"code","colab":{}},"source":["r = Reinforce(p,env)"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"-aIuDC0IQzBw","colab_type":"text"},"source":["# 2.1 Monte Carlo Control"]},{"cell_type":"markdown","metadata":{"id":"7B3Ma54tQzBx","colab_type":"text"},"source":["**Theory**  \n","* 우리는 환경(environment)을 알지 못하므로 현재 정책(policy)을 실행하여 에피소드를 처음부터 끝까지 샘플링합니다.\n","* 상태값(state value)이 아닌 행동값(action value)을 추정하려고합니다. 우리는 모델이 없는(model-free) 상황에서 작업하기 때문에 알려진 상태값(state value)만으로는 최선의 행동(action)을 선택하는 데 도움이 되지 않기 때문입니다.\n","* state-action value의 값은 해당 state-action의 첫 방문으로부터 이후의 return들로 정의됩니다.\n","* 이를 바탕으로 정책(policy)을 개선하고 알고리즘이 수렴 될 때까지 프로세스를 반복할 수 있습니다\n","\n","![](http://incompleteideas.net/book/first/ebook/pseudotmp5.png)"]},{"cell_type":"markdown","metadata":{"id":"UKOKJPFgQzBy","colab_type":"text"},"source":["**Implementation**"]},{"cell_type":"code","metadata":{"id":"7CIqYVyzQzB0","colab_type":"code","outputId":"8fd5e5cd-42c1-421b-9f90-72995809385b","colab":{"base_uri":"https://localhost:8080/","height":472},"executionInfo":{"status":"ok","timestamp":1581998235642,"user_tz":-540,"elapsed":644,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["print(inspect.getsource(r.monte_carlo_learning))"],"execution_count":8,"outputs":[{"output_type":"stream","text":["    def monte_carlo_learning(self, epsilon=0.1):\n","        \"\"\"\n","        Learn move chess through monte carlo control\n","        :param epsilon: exploration rate\n","        :return:\n","        \"\"\"\n","        state = (0, 0)\n","        self.env.state = state\n","\n","        # Play out an episode\n","        states, actions, rewards = self.play_episode(state, epsilon=epsilon)\n","\n","        first_visits = []\n","        for idx, state in enumerate(states):\n","            action_index = actions[idx]\n","            if (state, action_index) in first_visits:\n","                continue\n","            r = np.sum(rewards[idx:])\n","            if (state, action_index) in self.agent.Returns.keys():\n","                self.agent.Returns[(state, action_index)].append(r)\n","            else:\n","                self.agent.Returns[(state, action_index)] = [r]\n","            self.agent.action_function[state[0], state[1], action_index] = \\\n","                np.mean(self.agent.Returns[(state, action_index)])\n","            first_visits.append((state, action_index))\n","        # Update the policy. In Monte Carlo Control, this is greedy behavior with respect to the action function\n","        self.agent.policy = self.agent.action_function.copy()\n","\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"VJ7yWdhqQzB4","colab_type":"text"},"source":["**Demo**  \n","0.5의 높은 탐색 속도를 유지하면서 몬테 카를로 학습을 100 회 반복합니다"]},{"cell_type":"code","metadata":{"id":"gIc-JDDBQzB5","colab_type":"code","colab":{}},"source":["for k in range(100):\n","    eps = 0.5\n","    r.monte_carlo_learning(epsilon=eps)"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"vm806JkFQzB8","colab_type":"code","outputId":"19c8f9ee-ea27-4f05-b533-62a9adc2c495","colab":{"base_uri":"https://localhost:8080/","height":147},"executionInfo":{"status":"ok","timestamp":1581998242452,"user_tz":-540,"elapsed":588,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["r.visualize_policy()"],"execution_count":10,"outputs":[{"output_type":"stream","text":["[['↘', '↘', '→', '↓', '↘', '↖', '←', '↙'],\n"," ['↑', '↘', '→', '↖', '→', '↓', '↑', '↙'],\n"," ['↓', '↘', '→', '→', '↘', '↘', '↓', '↗'],\n"," ['↗', '↓', '↗', '↘', '↗', '↓', '↘', '↘'],\n"," ['←', '↘', '→', '↙', '↓', '↓', '↙', '↙'],\n"," ['↓', '↗', '↑', '↘', '→', '↙', '↓', '↑'],\n"," ['↘', '↓', '↗', '→', '↘', '↓', '↙', '←'],\n"," ['↗', '↙', '→', '↗', '→', 'F', '←', '↑']]\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"W0b5LKayQzCC","colab_type":"text"},"source":["각 상태(state)에 대한 최상의 행동값(action value)"]},{"cell_type":"code","metadata":{"id":"IZ7mRA3aQzCE","colab_type":"code","outputId":"d5cf6482-7c6e-4f10-f6a2-cfcdac24cce1","colab":{"base_uri":"https://localhost:8080/","height":147},"executionInfo":{"status":"ok","timestamp":1581998247349,"user_tz":-540,"elapsed":721,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["r.agent.action_function.max(axis=2).astype(int)"],"execution_count":11,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([[-41, -40, -32, -51, -24, -20, -20, -56],\n","       [-37, -30, -37, -35, -23, -16, -32, -28],\n","       [-37, -24, -26, -19, -14, -13, -19, -51],\n","       [-30, -31, -23, -14, -18, -13, -10, -41],\n","       [-34, -50, -29, -22,  -7,  -9,  -8,  -7],\n","       [-39, -47, -24,  -8,  -4,  -4,  -5, -11],\n","       [-30, -12, -16,  -5,  -1,  -1,  -1,  -2],\n","       [-52, -11, -25,  -4,  -1,   0,  -1,  -4]])"]},"metadata":{"tags":[]},"execution_count":11}]},{"cell_type":"markdown","metadata":{"id":"7l0V6Jj8QzCI","colab_type":"text"},"source":["# 2.2 Temporal Difference Learning "]},{"cell_type":"markdown","metadata":{"id":"D0wWLOa7QzCK","colab_type":"text"},"source":["**Theory**\n","* 정책(Policy) 반복과 마찬가지로 에피소드가 끝나기를 기다리지 않고 후속 상태행동(state-action)에서 상태행동값(state-action value)을 백업 할 수 있습니다.\n","* 후속 상태행동값(state-action value) 방향으로 상태행동값(state-action value)을 업데이트합니다.\n","* 알고리즘을 SARSA : State-Action-Reward-State-Action이라고합니다.\n","* Epsilon이 점차 낮아짐 (GLIE 속성)"]},{"cell_type":"markdown","metadata":{"id":"yAFjJoM0QzCM","colab_type":"text"},"source":["**Implementation**"]},{"cell_type":"code","metadata":{"id":"oYWu2DQGQzCN","colab_type":"code","outputId":"78dc99fb-12b3-4ffd-aea0-74accf190902","colab":{"base_uri":"https://localhost:8080/","height":505},"executionInfo":{"status":"ok","timestamp":1581998253194,"user_tz":-540,"elapsed":590,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["print(inspect.getsource(r.sarsa_td))"],"execution_count":12,"outputs":[{"output_type":"stream","text":["    def sarsa_td(self, n_episodes=1000, alpha=0.01, gamma=0.9):\n","        \"\"\"\n","        Run the sarsa control algorithm (TD0), finding the optimal policy and action function\n","        :param n_episodes: int, amount of episodes to train\n","        :param alpha: learning rate\n","        :param gamma: discount factor of future rewards\n","        :return: finds the optimal policy for move chess\n","        \"\"\"\n","        for k in range(n_episodes):\n","            state = (0, 0)\n","            self.env.state = state\n","            episode_end = False\n","            epsilon = max(1 / (1 + k), 0.05)\n","            while not episode_end:\n","                state = self.env.state\n","                action_index = self.agent.apply_policy(state, epsilon)\n","                action = self.agent.action_space[action_index]\n","                reward, episode_end = self.env.step(action)\n","                successor_state = self.env.state\n","                successor_action_index = self.agent.apply_policy(successor_state, epsilon)\n","\n","                action_value = self.agent.action_function[state[0], state[1], action_index]\n","                successor_action_value = self.agent.action_function[successor_state[0],\n","                                                                    successor_state[1], successor_action_index]\n","\n","                q_update = alpha * (reward + gamma * successor_action_value - action_value)\n","\n","                self.agent.action_function[state[0], state[1], action_index] += q_update\n","                self.agent.policy = self.agent.action_function.copy()\n","\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"3yPaaH2DQzCR","colab_type":"text"},"source":["**Demonstration**"]},{"cell_type":"code","metadata":{"id":"AeUdztizQzCT","colab_type":"code","colab":{}},"source":["p = Piece(piece='king')\n","env = Board()\n","r = Reinforce(p,env)\n","r.sarsa_td(n_episodes=10000,alpha=0.2,gamma=0.9)"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"hCmnXc1sQzCY","colab_type":"code","outputId":"a691dc43-e844-4320-dc8d-f5d784c56c56","colab":{"base_uri":"https://localhost:8080/","height":147},"executionInfo":{"status":"ok","timestamp":1581998269588,"user_tz":-540,"elapsed":585,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["r.visualize_policy()"],"execution_count":14,"outputs":[{"output_type":"stream","text":["[['↓', '↘', '↙', '→', '↖', '→', '↘', '↖'],\n"," ['↘', '↓', '↘', '↘', '↑', '→', '↓', '↗'],\n"," ['↘', '↘', '↘', '↘', '↓', '↙', '↘', '↙'],\n"," ['←', '↘', '↘', '↓', '↘', '↙', '↑', '→'],\n"," ['↓', '↘', '↘', '↘', '↓', '↘', '↙', '↙'],\n"," ['↗', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↙', '↗', '↘', '↘', '↘', '↓', '↙', '↖'],\n"," ['←', '↙', '→', '→', '→', 'F', '←', '←']]\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"TYrwu1FtQzCb","colab_type":"text"},"source":["# 2.3 TD-lambda\n","**Theory**  \n","Monte Carlo에서는 full-depth 백업을 수행하고 Temporal Difference Learning에서는 1-step 백업을 수행합니다. 또한 백업 간격을 n 단계로 선택할 수도 있습니다. 그러나 n에 어떤 값을 선택해야합니까?\n","\n","* TD lambda는 모든 n-step을 사용하고 factor lambda로 할인합니다\n","* 이것을 lambda-return이라고합니다\n","* TD-lambda는 eligibility-trace를 사용하여 이전에 발생한 상태를 추적합니다.\n","* 이런 식으로 행동가치(action-value)는 회고적으로 업데이트 될 수 있습니다"]},{"cell_type":"markdown","metadata":{"id":"KI3ArBrRQzCd","colab_type":"text"},"source":["**Implementation**"]},{"cell_type":"code","metadata":{"id":"z5VBRa2-QzCe","colab_type":"code","outputId":"313555c1-03d2-460d-8eca-ca8532489599","colab":{"base_uri":"https://localhost:8080/","height":618},"executionInfo":{"status":"ok","timestamp":1581998273824,"user_tz":-540,"elapsed":612,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["print(inspect.getsource(r.sarsa_lambda))"],"execution_count":15,"outputs":[{"output_type":"stream","text":["    def sarsa_lambda(self, n_episodes=1000, alpha=0.05, gamma=0.9, lamb=0.8):\n","        \"\"\"\n","        Run the sarsa control algorithm (TD lambda), finding the optimal policy and action function\n","        :param n_episodes: int, amount of episodes to train\n","        :param alpha: learning rate\n","        :param gamma: discount factor of future rewards\n","        :param lamb: lambda parameter describing the decay over n-step returns\n","        :return: finds the optimal move chess policy\n","        \"\"\"\n","        for k in range(n_episodes):\n","            self.agent.E = np.zeros(shape=self.agent.action_function.shape)\n","            state = (0, 0)\n","            self.env.state = state\n","            episode_end = False\n","            epsilon = max(1 / (1 + k), 0.2)\n","            action_index = self.agent.apply_policy(state, epsilon)\n","            action = self.agent.action_space[action_index]\n","            while not episode_end:\n","                reward, episode_end = self.env.step(action)\n","                successor_state = self.env.state\n","                successor_action_index = self.agent.apply_policy(successor_state, epsilon)\n","\n","                action_value = self.agent.action_function[state[0], state[1], action_index]\n","                if not episode_end:\n","                    successor_action_value = self.agent.action_function[successor_state[0],\n","                                                                        successor_state[1], successor_action_index]\n","                else:\n","                    successor_action_value = 0\n","                delta = reward + gamma * successor_action_value - action_value\n","                self.agent.E[state[0], state[1], action_index] += 1\n","                self.agent.action_function = self.agent.action_function + alpha * delta * self.agent.E\n","                self.agent.E = gamma * lamb * self.agent.E\n","                state = successor_state\n","                action = self.agent.action_space[successor_action_index]\n","                action_index = successor_action_index\n","                self.agent.policy = self.agent.action_function.copy()\n","\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"zcLZYu1vQzCj","colab_type":"text"},"source":["**Demonstration**"]},{"cell_type":"code","metadata":{"id":"5EGLhaxcQzCk","colab_type":"code","colab":{}},"source":["p = Piece(piece='king')\n","env = Board()\n","r = Reinforce(p,env)\n","r.sarsa_lambda(n_episodes=10000,alpha=0.2,gamma=0.9)"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"RaeXrn2KQzCp","colab_type":"code","outputId":"f7f53c8d-5926-4e89-bd58-37daec7d0635","colab":{"base_uri":"https://localhost:8080/","height":147},"executionInfo":{"status":"ok","timestamp":1581998285539,"user_tz":-540,"elapsed":5945,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["r.visualize_policy()"],"execution_count":17,"outputs":[{"output_type":"stream","text":["[['↓', '↘', '↘', '↙', '↘', '↙', '↘', '↙'],\n"," ['↘', '↓', '↓', '↓', '↑', '↙', '→', '↓'],\n"," ['↘', '↓', '↘', '↙', '↓', '←', '↓', '↙'],\n"," ['→', '↘', '↘', '↓', '↙', '↘', '↘', '→'],\n"," ['↘', '→', '↘', '↘', '↓', '↓', '↘', '↙'],\n"," ['↗', '↗', '↘', '↘', '↓', '↙', '↓', '↙'],\n"," ['→', '↘', '→', '↘', '↘', '↓', '↙', '↙'],\n"," ['→', '→', '↗', '→', '→', 'F', '←', '↖']]\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"7gMntnpDQzCs","colab_type":"text"},"source":["# 2.4 Q-learning"]},{"cell_type":"markdown","metadata":{"id":"1SQKZ0hMQzCt","colab_type":"text"},"source":["**Theory**\n","* SARSA / TD0 에서는 행동값(action value)을 후속 행동값(action value)으로 백업합니다.\n","* SARSA-max / Q 학습 에서는 최대 행동값(action value)을 사용하여 백업합니다."]},{"cell_type":"markdown","metadata":{"id":"onfC4kxiQzCv","colab_type":"text"},"source":["**Implementation**"]},{"cell_type":"code","metadata":{"id":"dU2ev1n0QzCw","colab_type":"code","outputId":"adc35f6a-338e-4d0a-c486-38125c42b93a","colab":{"base_uri":"https://localhost:8080/","height":618},"executionInfo":{"status":"ok","timestamp":1581998288650,"user_tz":-540,"elapsed":614,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["print(inspect.getsource(r.sarsa_lambda))"],"execution_count":18,"outputs":[{"output_type":"stream","text":["    def sarsa_lambda(self, n_episodes=1000, alpha=0.05, gamma=0.9, lamb=0.8):\n","        \"\"\"\n","        Run the sarsa control algorithm (TD lambda), finding the optimal policy and action function\n","        :param n_episodes: int, amount of episodes to train\n","        :param alpha: learning rate\n","        :param gamma: discount factor of future rewards\n","        :param lamb: lambda parameter describing the decay over n-step returns\n","        :return: finds the optimal move chess policy\n","        \"\"\"\n","        for k in range(n_episodes):\n","            self.agent.E = np.zeros(shape=self.agent.action_function.shape)\n","            state = (0, 0)\n","            self.env.state = state\n","            episode_end = False\n","            epsilon = max(1 / (1 + k), 0.2)\n","            action_index = self.agent.apply_policy(state, epsilon)\n","            action = self.agent.action_space[action_index]\n","            while not episode_end:\n","                reward, episode_end = self.env.step(action)\n","                successor_state = self.env.state\n","                successor_action_index = self.agent.apply_policy(successor_state, epsilon)\n","\n","                action_value = self.agent.action_function[state[0], state[1], action_index]\n","                if not episode_end:\n","                    successor_action_value = self.agent.action_function[successor_state[0],\n","                                                                        successor_state[1], successor_action_index]\n","                else:\n","                    successor_action_value = 0\n","                delta = reward + gamma * successor_action_value - action_value\n","                self.agent.E[state[0], state[1], action_index] += 1\n","                self.agent.action_function = self.agent.action_function + alpha * delta * self.agent.E\n","                self.agent.E = gamma * lamb * self.agent.E\n","                state = successor_state\n","                action = self.agent.action_space[successor_action_index]\n","                action_index = successor_action_index\n","                self.agent.policy = self.agent.action_function.copy()\n","\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"THOqb0b4QzC0","colab_type":"text"},"source":["**Demonstration**"]},{"cell_type":"code","metadata":{"id":"b37qQyOZQzC1","colab_type":"code","colab":{}},"source":["p = Piece(piece='king')\n","env = Board()\n","r = Reinforce(p,env)\n","r.q_learning(n_episodes=1000,alpha=0.2,gamma=0.9)"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"gm-yf7U3QzC4","colab_type":"code","outputId":"9cd8d870-6c7d-4cf7-83b0-dbaf9462a243","colab":{"base_uri":"https://localhost:8080/","height":147},"executionInfo":{"status":"ok","timestamp":1581998293765,"user_tz":-540,"elapsed":1047,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["r.visualize_policy()"],"execution_count":20,"outputs":[{"output_type":"stream","text":["[['↘', '→', '↘', '↘', '↖', '→', '→', '↘'],\n"," ['↘', '↓', '↘', '↘', '↗', '↘', '←', '↗'],\n"," ['↘', '↘', '↘', '↘', '↘', '↓', '→', '←'],\n"," ['↘', '↘', '↓', '↘', '↘', '↓', '↓', '↑'],\n"," ['↗', '↙', '↘', '↘', '↘', '↙', '↘', '↑'],\n"," ['↘', '↓', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↓', '↗', '→', '↘', '↘', '↓', '↙', '↙'],\n"," ['↓', '←', '↙', '→', '→', 'F', '↙', '↖']]\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"c-A0gjiWQzC8","colab_type":"code","outputId":"514a4131-88ff-4004-d208-5762315adbb8","colab":{"base_uri":"https://localhost:8080/","height":147},"executionInfo":{"status":"ok","timestamp":1581998294880,"user_tz":-540,"elapsed":395,"user":{"displayName":"문성채","photoUrl":"","userId":"07687686498757557466"}}},"source":["r.agent.action_function.max(axis=2).round().astype(int)"],"execution_count":21,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([[-5, -5, -5, -4, -4, -4, -4, -4],\n","       [-5, -5, -5, -4, -4, -4, -4, -3],\n","       [-4, -4, -4, -4, -4, -4, -3, -3],\n","       [-4, -3, -3, -3, -3, -3, -3, -3],\n","       [-3, -3, -3, -3, -3, -3, -3, -3],\n","       [-3, -3, -3, -2, -2, -2, -2, -2],\n","       [-3, -3, -2, -2, -1, -1, -1, -2],\n","       [-3, -3, -2, -2, -1,  0, -1, -1]])"]},"metadata":{"tags":[]},"execution_count":21}]},{"cell_type":"markdown","metadata":{"id":"D1rsF1ixQzDA","colab_type":"text"},"source":["# References\n","1. Reinforcement Learning: An Introduction  \n","   Richard S. Sutton and Andrew G. Barto  \n","   1st Edition  \n","   MIT Press, march 1998\n","2. RL Course by David Silver: Lecture playlist  \n","   https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ"]},{"cell_type":"code","metadata":{"id":"rVtpyoD6QzDA","colab_type":"code","colab":{}},"source":[""],"execution_count":0,"outputs":[]}]}