1_part/3_01_RL_Chess_1_Policy_Iteration.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"Reinforcement_Learning_Chess_1_Policy Iteration.ipynb","provenance":[],"collapsed_sections":[],"toc_visible":true,"authorship_tag":"ABX9TyMEoIpjFc7ASrIHBI3mmXix"},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"uVs5c1lT6Cyk","colab_type":"text"},"source":["# 0. 강화학습을 이용한 체스 (Reinforcement Learning Chess)\n","\n","※본 커널은 캐글을 통해 공유된 https://www.kaggle.com/arjanso/reinforcement-learning-chess-1-policy-iteration 의 내용을 기반으로 작성되었습니다.\n","\n","체스를 다루는 것은 거대한 상태공간(state-space)을 다루는 일이기 때문에 매우 도전적인 일(challenge)입니다. (이제는 훨씬 더 거대한 상태공간을 갖는 바둑의 세계도 점령당했지만요!) 간단한 형태의 체스로 시작하여 기본 강화학습 기술로 이러한 문제를 해결합니다. 점진적으로 체스의 실제 게임을 이해할 수 있는 체스 AI로 점차 확장할 것입니다. 여기서 말하는 간단한 형태의 체스는 다음과 같습니다.\n","\n","1. 체스 말 움직이기\n","- 목표: 체스 판에서 두 사각형 사이의 최단 경로를 찾는 법을 배웁니다.\n","- 동기: 체스 말을 움직이는 것은 상태공간이 작기 때문에 간단한 강화학습 알고리즘으로 해결할 수 있습니다.\n","- 개념: 동적 프로그래밍(Dynamic Programming), 정책 평가(Poliy Evaluation), 정책 개선(Policy Improvement), 정책 반복(Policy Iteration), 가치 반복(Value Iteration), 동기 및 비동기 백업(Synchronous & Asynchronous back-ups), 몬테 카를로(Monte Carlo) 예측, MC 제어, 시간 차이(Temporal Difference) 학습, TD 제어, TD-람다(lambda), SARSA(-max)\n","2. 체스 말 잡기\n","- 목표: 총 이동수(fullmoves) n 내에서 상대방으로부터 많은 조각을 잡는 것\n","- 동기: 체스 말을 잡는 것은 win-lose-draw 이벤트보다 더 자주 발생합니다. 이를 통해 알고리즘에게 추가 정보가 제공됩니다.\n","- 개념: Q-러닝(Q-learning), 가치 함수 근사(value function approximation), 재실험(experience replay), 고정 q-목표(fixed-q-targets), 정책 그래디언트(policy gradients), REINFORCE, 행위자 비평(actor-critic)\n","3. 실제 체스\n","- 목표: 인간 초보자와 경쟁하여 체스를 둡니다.\n","- 동기: 강화학습 체스 AI\n","- 개념: 몬테 카를로 탐색 트리(Monte Carlo Tree Search)\n","\n","이 커널에서는 강화학습 이론을 설명하고 참고하지만, 완전히 설명하지는 않습니다. 관련하여서는 다음의 유튜브와 책을 참조해주세요.\n","1. Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto, 1st Edition, MIT Press, march 1998\n","2. [RL Course by David Silver: Lecture playlist] (https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ)\n"]},{"cell_type":"markdown","metadata":{"id":"FpzD3Xp8AcOb","colab_type":"text"},"source":["# 1. 체스 말 움직이기\n","\n","먼저 심플한 첫번째 문제입니다. 체스 말을 움직이는 것입니다. 체스 환경을 다룰  수 있는 python-chess라는 패키지와 RLC라는 강화학습 패키지를 활용합니다."]},{"cell_type":"code","metadata":{"id":"LEmkiAcx2_it","colab_type":"code","outputId":"29bdb912-8412-4db1-b945-6884ac9c8764","executionInfo":{"status":"ok","timestamp":1581571606007,"user_tz":-540,"elapsed":12233,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":215}},"source":["import numpy as np \n","import pandas as pd \n","import os\n","import inspect\n","\n","!pip install python-chess  \n","!pip install --upgrade git+https://github.com/arjangroen/RLC.git  "],"execution_count":0,"outputs":[{"output_type":"stream","text":["Requirement already satisfied: python-chess in /usr/local/lib/python3.6/dist-packages (0.23.11)\n","Collecting git+https://github.com/arjangroen/RLC.git\n","  Cloning https://github.com/arjangroen/RLC.git to /tmp/pip-req-build-52pgzt6m\n","  Running command git clone -q https://github.com/arjangroen/RLC.git /tmp/pip-req-build-52pgzt6m\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=8e9dfaad23ae5a756e9d544ab6ed6b13725530976610b0212d507db2c8bffec4\n","  Stored in directory: /tmp/pip-ephem-wheel-cache-t86c3h4v/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":"G4tZtawNAzLh","colab_type":"code","outputId":"5b313f59-08f2-4970-adb5-cce483f0c8d4","executionInfo":{"status":"ok","timestamp":1581572180794,"user_tz":-540,"elapsed":639,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":53}},"source":["%load_ext autoreload\n","%autoreload 2"],"execution_count":0,"outputs":[{"output_type":"stream","text":["The autoreload extension is already loaded. To reload it, use:\n","  %reload_ext autoreload\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"Zluyj6xsA_Za","colab_type":"text"},"source":["여기서 제가 평소에 보지 못했던 2개의 매직 셀 커멘드들이 사용되었습니다.\n","\n","첫번째 \n","\n","두번째 `%autoreload`의 경우, 모듈을 자동적으로 리로드(reload)하는 것인데요, pip install과 같이 ipynb 내에서 설치를 하였을 경우 새로 설치된 모듈을 제대로 불러오지 못하는 경우가 있습니다. 특히 여기서는 RLC 깃으로부터 설치하는 부분이 그러할 것으로 생각되네요. 이를 위해서 사용하는 것으로 보입니다. autoreload에 파라미터를 전달할 수 있습니다.\n","\n","- `%autoreload`: 지금 바로 자동적으로 모든 모듈을 리로드합니다. 모든 모듈을 리로드합니다.(`%aimport`에서 제외된 모듈을 제외하고)\n","- `%autoreload 0`: 자동 리로딩 기능을 끕니다.\n","- `%autoreload 1`: 파이썬 코드를 실행하기 전에 매번 `%aimport` 내의 모든 모듈들을 리로드합니다.\n","- `%autoreload 2`: 파이썬 코드를 실행하기 전에 매번 모든 모듈을 리로드합니다.(`%aimport`에서 제외된 모듈을 제외하고)\n","\n","새로운게 또 등장했네요,\n","\n","`%aimport`는 자동적으로 import할 또는 하지 않을 모듈의 리스트를 나타냅니다. 여기서는 특별히 사용하지 않는 것으로 보아, 모든 모듈을 리로드하는 것으로 볼 수 있습니다."]},{"cell_type":"markdown","metadata":{"id":"azlQuKhOD9a5","colab_type":"text"},"source":["## 1.0.1 환경 (Environment)"]},{"cell_type":"markdown","metadata":{"id":"oKyFdbdzEFyI","colab_type":"text"},"source":["- 상태공간은 8x8의 그리드입니다\n","- 시작 상태 S는 왼쪽 위 사각형 (0, 0)을 기준으로 합니다.\n","- 종료 상태 F의 좌표는 (5, 7) 입니다.\n","- 한 상태에서 다른 상태로 이동할 때마다 보상(reward)을 1 감소시킵니다.\n","- 이 환경에 대한 최상의 정책은 가장 적은 수의 움직임으로 S로부터 F까지 움직이는 것입니다."]},{"cell_type":"code","metadata":{"id":"Ck0cNADXA-cx","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":"code","metadata":{"id":"MvtH7gc1DO0y","colab_type":"code","outputId":"4c4e611a-ec19-4e6f-e285-15d825a3ef47","executionInfo":{"status":"ok","timestamp":1581572673323,"user_tz":-540,"elapsed":733,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":161}},"source":["env = Board()\n","env.render()\n","env.visual_board"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[['[S]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[ ]'],\n"," ['[ ]', '[ ]', '[ ]', '[ ]', '[ ]', '[F]', '[ ]', '[ ]']]"]},"metadata":{"tags":[]},"execution_count":8}]},{"cell_type":"markdown","metadata":{"id":"8JBIBBLmEodB","colab_type":"text"},"source":["Board는 위에서 말한 체스판의 환경을 구성하는 클래스입니다. render()를 실행하지 않으면, env는 visual_board를 갖고 있지 않습니다. render() 함수는 시각화를 위한 초기화 함수로 보아도 좋을 것 같습니다. 즉, 내부적으로 움직일 때에는 시각화를 위한 연산까지는 필요하지 않기 때문에 기본적으로는 render()를 실행하지 않아서 연산을 최소화합니다."]},{"cell_type":"markdown","metadata":{"id":"CFPoRirpFQS6","colab_type":"text"},"source":["## 1.0.2. 에이전트(Agent)\n","\n","- 체스에서 에이전트는 체스 말입니다. (킹, 퀸, 룩, 나이트, 비숍 등)\n","- 에이전트는 에이전트가 어떤 상태에서 무엇을 하는지 결정하는 행동 정책을 갖고 있습니다."]},{"cell_type":"code","metadata":{"id":"Yj3zBNvaElqZ","colab_type":"code","outputId":"54e42891-054e-4eff-b2cb-e82a6b069cbd","executionInfo":{"status":"ok","timestamp":1581572878273,"user_tz":-540,"elapsed":756,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":35}},"source":["p = Piece(piece='king')\n","print(p)"],"execution_count":0,"outputs":[{"output_type":"stream","text":["<RLC.move_chess.agent.Piece object at 0x7f2a03db11d0>\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"38u1aGWUFyE6","colab_type":"text"},"source":["## 1.0.3. 강화 (Reinforce)\n","\n","- 강화 객체에는 체스 말을 움직이는 문제를 해결하기 위한 알고리즘이 포함되어있습니다.\n","- 에이전트와 환경은 강화 객체의 속성(attributes)입니다."]},{"cell_type":"code","metadata":{"id":"i1zoA6MrFmyh","colab_type":"code","colab":{}},"source":["r = Reinforce(p,env)"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"cXgXVvSGOCBY","colab_type":"text"},"source":["# 1.1. 상태 평가(State Evaluation)"]},{"cell_type":"markdown","metadata":{"id":"-ydINbiNHE6Z","colab_type":"text"},"source":["## 1.1.1. 이론\n","\n","에이전트가 보상을 최적화하도록 하려면, 보상 정책이 가치가 가장 높은 상태를 향한 행동을 유도하기를 원합니다. 이 값은 부트스트랩(bootstrap)을 사용하여 추정할 수 있습니다.\n","\n","상태(s)는 후속 상태(s')와 s에서 s'으로 가는 것에 대한 보상(R)만큼 가치(V)가 있습니다. 여러 동작(a)과 후속 상태가 있을 수 있으므로 확률(pi)로 가중합됩니다. \n","(비결정적(non-deterministic) 환경에서 주어진 행동(action)은 여러 후속 상태를 초래할 수 있습니다. 체스 말을 움직이는 것은 결정적인(deterministic) 게임이기 때문에 이 문제를 고려할 필요는 없습니다.)\n","\n","후속 상태값은 0과 1사이의 할인 요소(discount factor; gammar)로 할인됩니다.\n","\n","이것을 수식화하면 다음과 같습니다.\n","\n","(수식1)\n","\n","참고:\n","- 후속 상태 값도 예측(estimate)입니다.\n","- 다른 예측값을 기반으로 예측을 하기 때문에 상태 평가가 부트스트랩됩니다.\n","- 이 코드에는 정책 평가 섹션의 뒷부분에서 설명할 동기(synchronous) 매개변수가 있습니다.\n"]},{"cell_type":"markdown","metadata":{"id":"mfB-P79vOG-H","colab_type":"text"},"source":["## 1.1.2. 구현"]},{"cell_type":"code","metadata":{"id":"4WpCaAazGD-R","colab_type":"code","outputId":"d69bbc73-e9e2-49d4-b902-b18bd5ecd718","executionInfo":{"status":"ok","timestamp":1581574703767,"user_tz":-540,"elapsed":637,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":503}},"source":["print(inspect.getsource(r.evaluate_state))"],"execution_count":0,"outputs":[{"output_type":"stream","text":["    def evaluate_state(self, state, gamma=0.9, synchronous=True):\n","        \"\"\"\n","        Calculates the value of a state based on the successor states and the immediate rewards.\n","        Args:\n","            state: tuple of 2 integers 0-7 representing the state\n","            gamma: float, discount factor\n","            synchronous: Boolean\n","\n","        Returns: The expected value of the state under the current policy.\n","\n","        \"\"\"\n","        greedy_action_value = np.max(self.agent.policy[state[0], state[1], :])\n","        greedy_indices = [i for i, a in enumerate(self.agent.policy[state[0], state[1], :]) if\n","                          a == greedy_action_value]  # List of all greedy actions\n","        prob = 1 / len(greedy_indices)  # probability of an action occuring\n","        state_value = 0\n","        for i in greedy_indices:\n","            self.env.state = state  # reset state to the one being evaluated\n","            reward, episode_end = self.env.step(self.agent.action_space[i])\n","            if synchronous:\n","                successor_state_value = self.agent.value_function_prev[self.env.state]\n","            else:\n","                successor_state_value = self.agent.value_function[self.env.state]\n","            state_value += (prob * (\n","                    reward + gamma * successor_state_value))  # sum up rewards and discounted successor state value\n","        return state_value\n","\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"fkelBHmYMy0Y","colab_type":"text"},"source":["inspect라는 파이썬 패키지는 함수의 소스를 보고 싶을 때 사용할 수 있습니다.\n","`inspect(getsource(함수 이름))`를 통해 함수가 어떻게 정의되었는지 볼 수 있습니다. 문서를 이리저리 찾아볼 필요 없이 이 함수를 통해 쉽게 찾아볼 수 있습니다.\n","\n","여기서는 `r.evaluate_state`함수를 출력하여, RLC.movechess에서 상태평가가 어떻게 구현되어있는지 살펴볼 수 있습니다. "]},{"cell_type":"markdown","metadata":{"id":"wQPG12OlOJv4","colab_type":"text"},"source":["## 1.1.3. 데모\n","\n","- 초기 value_function은 각 상태에 0을 할당합니다\n","- 초기 정책은 각 행동에 대해 동일한 확률을 제공합니다.\n","- 상태 (0,0)을 평가합니다."]},{"cell_type":"code","metadata":{"id":"r9Jx1ep9Msep","colab_type":"code","outputId":"eab7c678-2a1f-490b-c85b-908dc5309faf","executionInfo":{"status":"ok","timestamp":1581579126623,"user_tz":-540,"elapsed":564,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":161}},"source":["r.agent.value_function.astype(int)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([[0, 0, 0, 0, 0, 0, 0, 0],\n","       [0, 0, 0, 0, 0, 0, 0, 0],\n","       [0, 0, 0, 0, 0, 0, 0, 0],\n","       [0, 0, 0, 0, 0, 0, 0, 0],\n","       [0, 0, 0, 0, 0, 0, 0, 0],\n","       [0, 0, 0, 0, 0, 0, 0, 0],\n","       [0, 0, 0, 0, 0, 0, 0, 0],\n","       [0, 0, 0, 0, 0, 0, 0, 0]])"]},"metadata":{"tags":[]},"execution_count":13}]},{"cell_type":"markdown","metadata":{"id":"hgNAySw_dz6N","colab_type":"text"},"source":["상태 (0,0)을 평가합니다."]},{"cell_type":"code","metadata":{"id":"Wl-amex8dkTP","colab_type":"code","colab":{}},"source":["state = (0,0)\n","r.agent.value_function[0,0] = r.evaluate_state(state,gamma=1)"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"q05qdJfddl5l","colab_type":"code","outputId":"bf0c7d33-4b86-48d4-eb1d-6b760f644384","executionInfo":{"status":"ok","timestamp":1581579213144,"user_tz":-540,"elapsed":595,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":161}},"source":["r.agent.value_function.astype(int)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([[-1,  0,  0,  0,  0,  0,  0,  0],\n","       [ 0,  0,  0,  0,  0,  0,  0,  0],\n","       [ 0,  0,  0,  0,  0,  0,  0,  0],\n","       [ 0,  0,  0,  0,  0,  0,  0,  0],\n","       [ 0,  0,  0,  0,  0,  0,  0,  0],\n","       [ 0,  0,  0,  0,  0,  0,  0,  0],\n","       [ 0,  0,  0,  0,  0,  0,  0,  0],\n","       [ 0,  0,  0,  0,  0,  0,  0,  0]])"]},"metadata":{"tags":[]},"execution_count":17}]},{"cell_type":"markdown","metadata":{"id":"WjtzZEkGd83W","colab_type":"text"},"source":["# 1.2. 정책 평가\n","\n","- 정책 평가는 상태공간에서 각 상태에 대한 doe 상태 평가 행위입니다.\n","- 모든 상태를 반복하고 value_function을 업데이트합니다.\n","- 이것은 Sutton과 Barto가 제공하는 알고리즘 입니다.\n","\n","(그림2)\n","\n"]},{"cell_type":"code","metadata":{"id":"rFf_-NAEdo7t","colab_type":"code","outputId":"0365b1d7-2d4c-4612-9714-e0d25588c76f","executionInfo":{"status":"ok","timestamp":1581579364631,"user_tz":-540,"elapsed":563,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":143}},"source":["print(inspect.getsource(r.evaluate_policy))"],"execution_count":0,"outputs":[{"output_type":"stream","text":["    def evaluate_policy(self, gamma=0.9, synchronous=True):\n","        self.agent.value_function_prev = self.agent.value_function.copy()  # For synchronous updates\n","        for row in range(self.agent.value_function.shape[0]):\n","            for col in range(self.agent.value_function.shape[1]):\n","                self.agent.value_function[row, col] = self.evaluate_state((row, col), gamma=gamma,\n","                                                                          synchronous=synchronous)\n","\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"k_-Ve01Refbc","colab_type":"text"},"source":["inspect.getsource()함수를 이용하여 RLC.movechess에서 정책평가가 어떻게 구현되어있는지 살펴볼 수 있습니다."]},{"cell_type":"code","metadata":{"id":"byewM-cfeeZv","colab_type":"code","colab":{}},"source":["r.evaluate_policy(gamma=1)"],"execution_count":0,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"3FseatxQesj-","colab_type":"text"},"source":["정책 평가를 실행합니다. 그러면 value_function의 결과는 다음과 같이 종료 상태를 제외한 모든 상태가 -1이 됩니다."]},{"cell_type":"code","metadata":{"id":"lFQWFxAYeoM1","colab_type":"code","outputId":"0a7470bb-8f92-4dc4-fa94-42f0b315df04","executionInfo":{"status":"ok","timestamp":1581579474017,"user_tz":-540,"elapsed":549,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":161}},"source":["r.agent.value_function.astype(int)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([[-1, -1, -1, -1, -1, -1, -1, -1],\n","       [-1, -1, -1, -1, -1, -1, -1, -1],\n","       [-1, -1, -1, -1, -1, -1, -1, -1],\n","       [-1, -1, -1, -1, -1, -1, -1, -1],\n","       [-1, -1, -1, -1, -1, -1, -1, -1],\n","       [-1, -1, -1, -1, -1, -1, -1, -1],\n","       [-1, -1, -1, -1, -1, -1, -1, -1],\n","       [-1, -1, -1, -1, -1,  0, -1, -1]])"]},"metadata":{"tags":[]},"execution_count":20}]},{"cell_type":"markdown","metadata":{"id":"rSyUd6ZEfAF1","colab_type":"text"},"source":["## 1.2.3. 데모"]},{"cell_type":"markdown","metadata":{"id":"GDjkG6rLfcVt","colab_type":"text"},"source":["k_max: 반복 최대 횟수\n","value_delta_max: 이전 상태의 value_function과 현재 상태의 value_function의 차이가 최대가 되는 값\n","eps: value_function의 변화량의 최대(value_delta_max)를 측정하여 수렴할지 여부를 판단할 기준값"]},{"cell_type":"code","metadata":{"id":"TMXwZUD7e5Hl","colab_type":"code","outputId":"8c917ed2-d844-4033-9855-21f349071ee1","executionInfo":{"status":"ok","timestamp":1581579809511,"user_tz":-540,"elapsed":1599,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":35}},"source":["eps=0.1\n","k_max = 1000\n","value_delta_max = 0\n","gamma = 1\n","synchronous=True\n","value_delta_max = 0\n","for k in range(k_max):\n","    r.evaluate_policy(gamma=gamma,synchronous=synchronous)\n","    value_delta = np.max(np.abs(r.agent.value_function_prev - r.agent.value_function))\n","    value_delta_max = value_delta\n","    if value_delta_max < eps:\n","        print('converged at iter',k)\n","        break"],"execution_count":0,"outputs":[{"output_type":"stream","text":["converged at iter 0\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"K2LpokKffb0s","colab_type":"text"},"source":[""]},{"cell_type":"code","metadata":{"id":"LJdEo7wSfYjE","colab_type":"code","outputId":"6db898db-1b9b-45ba-baac-cd5e697fb959","executionInfo":{"status":"ok","timestamp":1581579819400,"user_tz":-540,"elapsed":1249,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":161}},"source":["r.agent.value_function.astype(int)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([[-185, -183, -181, -179, -177, -175, -175, -175],\n","       [-183, -181, -179, -177, -174, -172, -171, -171],\n","       [-179, -177, -175, -172, -169, -166, -165, -164],\n","       [-174, -172, -169, -164, -160, -156, -154, -154],\n","       [-169, -167, -161, -155, -147, -142, -139, -139],\n","       [-164, -161, -154, -143, -131, -122, -120, -120],\n","       [-161, -157, -147, -131, -106,  -93,  -92, -102],\n","       [-160, -156, -145, -126,  -93,    0,  -77,  -93]])"]},"metadata":{"tags":[]},"execution_count":23}]},{"cell_type":"markdown","metadata":{"id":"etDf6uadgP2U","colab_type":"text"},"source":["# 1.3. 정책 개선\n","\n","이제 우리는 상태의 값을 알고있으므로, 행동이 가장 가치가 높은 상태를 향하도록 정책을 개선하고자 합니다. 정책 개선은 단순히 value function과 관련하여 정책을 탐욕스럽게 만드는 행위입니다. 가장 가치있는 상태로 이끄는 동작의 값을 1로하고, 나머지는 0으로 유지하여 이 작업을 수행합니다.\n"]},{"cell_type":"code","metadata":{"id":"uN-URyQcgPMv","colab_type":"code","outputId":"3596ddfb-e231-4dce-f45b-e9c412934e47","executionInfo":{"status":"ok","timestamp":1581579950710,"user_tz":-540,"elapsed":609,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":359}},"source":["print(inspect.getsource(r.improve_policy))"],"execution_count":0,"outputs":[{"output_type":"stream","text":["    def improve_policy(self):\n","        \"\"\"\n","        Finds the greedy policy w.r.t. the current value function\n","        \"\"\"\n","\n","        self.agent.policy_prev = self.agent.policy.copy()\n","        for row in range(self.agent.action_function.shape[0]):\n","            for col in range(self.agent.action_function.shape[1]):\n","                for action in range(self.agent.action_function.shape[2]):\n","                    self.env.state = (row, col)  # reset state to the one being evaluated\n","                    reward, episode_end = self.env.step(self.agent.action_space[action])\n","                    successor_state_value = 0 if episode_end else self.agent.value_function[self.env.state]\n","                    self.agent.policy[row, col, action] = reward + successor_state_value\n","\n","                max_policy_value = np.max(self.agent.policy[row, col, :])\n","                max_indices = [i for i, a in enumerate(self.agent.policy[row, col, :]) if a == max_policy_value]\n","                for idx in max_indices:\n","                    self.agent.policy[row, col, idx] = 1\n","\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"tvXeaaafgNRF","colab_type":"code","outputId":"e7962d3f-6028-41a2-b449-82a929ed12bb","executionInfo":{"status":"ok","timestamp":1581579956508,"user_tz":-540,"elapsed":506,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":161}},"source":["r.improve_policy()\n","r.visualize_policy()"],"execution_count":0,"outputs":[{"output_type":"stream","text":["[['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↓', '↙', '↙'],\n"," ['→', '→', '→', '→', '→', 'F', '←', '←']]\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"VrixcwcKgzJ8","colab_type":"text"},"source":["# 1.4. 정책 반복\n","\n","이제 정책이 안정될 때까지 정책 평가 및 정책 개선을 수행하여 최적의 정책을 찾도록 합니다.\n","\n","(그림3)\n"]},{"cell_type":"markdown","metadata":{"id":"F8PvfT0Bh1q8","colab_type":"text"},"source":["## 1.4.2. 구현"]},{"cell_type":"code","metadata":{"id":"MFJUhdh5gu61","colab_type":"code","outputId":"76f541e6-6c80-4808-bb62-fb50732bbdc5","executionInfo":{"status":"ok","timestamp":1581580262259,"user_tz":-540,"elapsed":622,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":773}},"source":["print(inspect.getsource(r.policy_iteration))"],"execution_count":0,"outputs":[{"output_type":"stream","text":["    def policy_iteration(self, eps=0.1, gamma=0.9, iteration=1, k=32, synchronous=True):\n","        \"\"\"\n","        Finds the optimal policy\n","        Args:\n","            eps: float, exploration rate\n","            gamma: float, discount factor\n","            iteration: the iteration number\n","            k: (int) maximum amount of policy evaluation iterations\n","            synchronous: (Boolean) whether to use synchronous are asynchronous back-ups \n","\n","        Returns:\n","\n","        \"\"\"\n","        policy_stable = True\n","        print(\"\\n\\n______iteration:\", iteration, \"______\")\n","        print(\"\\n policy:\")\n","        self.visualize_policy()\n","\n","        print(\"\")\n","        value_delta_max = 0\n","        for _ in range(k):\n","            self.evaluate_policy(gamma=gamma, synchronous=synchronous)\n","            value_delta = np.max(np.abs(self.agent.value_function_prev - self.agent.value_function))\n","            value_delta_max = value_delta\n","            if value_delta_max < eps:\n","                break\n","        print(\"Value function for this policy:\")\n","        print(self.agent.value_function.round().astype(int))\n","        action_function_prev = self.agent.action_function.copy()\n","        print(\"\\n Improving policy:\")\n","        self.improve_policy()\n","        policy_stable = self.agent.compare_policies() < 1\n","        print(\"policy diff:\", policy_stable)\n","\n","        if not policy_stable and iteration < 1000:\n","            iteration += 1\n","            self.policy_iteration(iteration=iteration)\n","        elif policy_stable:\n","            print(\"Optimal policy found in\", iteration, \"steps of policy evaluation\")\n","        else:\n","            print(\"failed to converge.\")\n","\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"-iV3TMKKh71n","colab_type":"text"},"source":["## 1.4.3. 데모"]},{"cell_type":"code","metadata":{"id":"pxmutz9kh5i1","colab_type":"code","outputId":"ee6a9a57-c38a-486f-f434-46476be6f012","executionInfo":{"status":"ok","timestamp":1581580277627,"user_tz":-540,"elapsed":852,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":971}},"source":["r.policy_iteration()"],"execution_count":0,"outputs":[{"output_type":"stream","text":["\n","\n","______iteration: 1 ______\n","\n"," policy:\n","[['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↓', '↙', '↙'],\n"," ['→', '→', '→', '→', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-4 -4 -4 -4 -4 -4 -4 -4]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -2 -2 -2 -2 -2]\n"," [-4 -3 -3 -2 -1 -1 -1 -2]\n"," [-4 -3 -3 -2 -1  0 -1 -2]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 2 ______\n","\n"," policy:\n","[['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['→', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '→', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '↗', '→', '↘', '↘', '↘', '↓', '↙'],\n"," ['↗', '↗', '↗', '→', '↘', '↓', '↙', '↙'],\n"," ['↗', '↗', '↗', '↗', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-4 -4 -4 -4 -4 -4 -4 -4]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -2 -2 -2 -2 -2]\n"," [-4 -3 -3 -2 -1 -1 -1 -2]\n"," [-4 -3 -3 -2 -1  0 -1 -2]]\n","\n"," Improving policy:\n","policy diff: True\n","Optimal policy found in 2 steps of policy evaluation\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"1Sw_s8yQjo50","colab_type":"text"},"source":["# 1.5. 비동기 정책 반복\n","\n"]},{"cell_type":"markdown","metadata":{"id":"qoIcCfxNjy7O","colab_type":"text"},"source":["## 1.5.1. 이론\n","\n","정책평가로 부트스트랩을 사용했습니다. 다른 추정치를 기반으로 추청했습니다. 그래서 우리는 어떤 추정을 하는가요?\n","\n","이전 정책 평가로부터 부트스트랩을 합니다. 이는 각 상태 값 추정 업데이트가 동일한 정책 평가 반복을 기반으로 한다는 것을 의미합니다. 이를 동기 정책 반복이라고 합니다. \n","\n","가장 최근의 추정으로부터 부트스트랩을 합니다. 즉, 추정 업데이트는 이전 또는 현재 value function 또는 이 둘의 조합을 기반으로 할 수 있습니다. 이를 비동기 정책 반복이라고 합니다.\n","\n","구현은 정책 반복과 동일하며, synchronous=False 인수만 전달해주면 됩니다."]},{"cell_type":"markdown","metadata":{"id":"uozDSVL8kiaF","colab_type":"text"},"source":["## 1.5.3. 데모"]},{"cell_type":"code","metadata":{"id":"0lv9tV1KjywE","colab_type":"code","colab":{}},"source":["agent = Piece(piece='king')\n","r = Reinforce(agent,env)"],"execution_count":0,"outputs":[]},{"cell_type":"code","metadata":{"id":"io1qrFHSh9Pf","colab_type":"code","outputId":"6ca1352f-01e7-4012-86db-c5a26f9c1b32","executionInfo":{"status":"ok","timestamp":1581580967127,"user_tz":-540,"elapsed":1202,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":1000}},"source":["r.policy_iteration(gamma=1,synchronous=False)"],"execution_count":0,"outputs":[{"output_type":"stream","text":["\n","\n","______iteration: 1 ______\n","\n"," policy:\n","[['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', 'F', '↑', '↑']]\n","\n","Value function for this policy:\n","[[-47 -48 -48 -49 -48 -48 -48 -48]\n"," [-48 -49 -49 -49 -49 -49 -49 -49]\n"," [-49 -49 -49 -49 -49 -49 -48 -48]\n"," [-49 -49 -49 -49 -48 -47 -47 -47]\n"," [-49 -49 -48 -47 -46 -45 -44 -44]\n"," [-48 -48 -47 -44 -42 -40 -39 -39]\n"," [-48 -48 -46 -42 -34 -31 -31 -35]\n"," [-48 -48 -45 -41 -31   0 -27 -33]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 2 ______\n","\n"," policy:\n","[['↑', '←', '←', '←', '→', '→', '→', '↑'],\n"," ['↑', '↖', '↖', '↖', '↗', '↗', '↗', '↑'],\n"," ['↑', '↖', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↓', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↓', '↙', '↙'],\n"," ['→', '→', '→', '→', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-11 -11 -11 -11 -11 -11 -11 -11]\n"," [-11 -11 -11 -11 -11 -11 -11 -11]\n"," [-11 -11  -4  -4  -4  -4  -4  -4]\n"," [ -5  -3  -3  -3  -3  -3  -3  -3]\n"," [ -4  -3  -3  -3  -3  -3  -3  -3]\n"," [ -4  -3  -3  -2  -2  -2  -2  -2]\n"," [ -4  -3  -3  -2  -1  -1  -1  -2]\n"," [ -4  -3  -3  -2  -1   0  -1  -2]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 3 ______\n","\n"," policy:\n","[['↑', '↑', '↑', '↑', '↙', '↑', '↑', '↑'],\n"," ['↑', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['→', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '→', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '↗', '→', '↘', '↘', '↘', '↓', '↙'],\n"," ['↗', '↗', '↗', '→', '↘', '↓', '↙', '↙'],\n"," ['↗', '↗', '↗', '↗', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-7 -6 -6 -6 -6 -6 -6 -6]\n"," [-6 -5 -5 -5 -5 -5 -5 -5]\n"," [-4 -4 -4 -4 -4 -4 -4 -4]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -2 -2 -2 -2 -2]\n"," [-4 -3 -3 -2 -1 -1 -1 -2]\n"," [-4 -3 -3 -2 -1  0 -1 -2]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 4 ______\n","\n"," policy:\n","[['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['→', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '→', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '↗', '→', '↘', '↘', '↘', '↓', '↙'],\n"," ['↗', '↗', '↗', '→', '↘', '↓', '↙', '↙'],\n"," ['↗', '↗', '↗', '↗', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-4 -4 -4 -4 -4 -4 -4 -4]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -2 -2 -2 -2 -2]\n"," [-4 -3 -3 -2 -1 -1 -1 -2]\n"," [-4 -3 -3 -2 -1  0 -1 -2]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 5 ______\n","\n"," policy:\n","[['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↓', '↙'],\n"," ['↘', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['→', '↘', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '→', '↘', '↘', '↘', '↘', '↘', '↓'],\n"," ['↗', '↗', '→', '↘', '↘', '↘', '↓', '↙'],\n"," ['↗', '↗', '↗', '→', '↘', '↓', '↙', '↙'],\n"," ['↗', '↗', '↗', '↗', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-5 -5 -5 -5 -5 -5 -5 -5]\n"," [-4 -4 -4 -4 -4 -4 -4 -4]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -3 -3 -3 -3 -3]\n"," [-4 -3 -3 -2 -2 -2 -2 -2]\n"," [-4 -3 -3 -2 -1 -1 -1 -2]\n"," [-4 -3 -3 -2 -1  0 -1 -2]]\n","\n"," Improving policy:\n","policy diff: True\n","Optimal policy found in 5 steps of policy evaluation\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"DynH-bttklfc","colab_type":"code","outputId":"f23c80b3-9010-47ff-bfcd-6b6699be6e24","executionInfo":{"status":"ok","timestamp":1581580985132,"user_tz":-540,"elapsed":686,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":161}},"source":["r.agent.value_function.astype(int)"],"execution_count":0,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([[-5, -5, -5, -5, -5, -5, -5, -5],\n","       [-4, -4, -4, -4, -4, -4, -4, -4],\n","       [-4, -4, -4, -4, -4, -4, -4, -4],\n","       [-4, -3, -3, -3, -3, -3, -3, -3],\n","       [-4, -3, -2, -2, -2, -2, -2, -2],\n","       [-4, -3, -2, -1, -1, -1, -1, -1],\n","       [-4, -3, -2, -1, -1, -1, -1, -1],\n","       [-4, -3, -2, -1, -1,  0, -1, -1]])"]},"metadata":{"tags":[]},"execution_count":30}]},{"cell_type":"markdown","metadata":{"id":"2DBmshOgkrt1","colab_type":"text"},"source":["# 1.6 가치 반복"]},{"cell_type":"markdown","metadata":{"id":"adGRTC7zkwGV","colab_type":"text"},"source":["## 1.6.1. 이론\n","\n","가치 반복은 정책 반복에 대한 간단한 매개 변수 수정에 지나지 않습니다. 정책 반복은 정책 평가 및 정책 개선으로 구성됩니다. 정책을 개선하기 전에 수렴될 때까지 정책 평가 단계를 반드시 반복할 필요는 없습니다. 위의 정책 반복이 수렴하는데 428번의 반복이 수행되었습니다(1.2.3. 참고). 대신 1번만 반복하면, 이것을 가치 반복이라고 부릅니다."]},{"cell_type":"markdown","metadata":{"id":"PBZTJIeClc_1","colab_type":"text"},"source":["## 1.6.3. 데모"]},{"cell_type":"markdown","metadata":{"id":"ioskDR8TlheF","colab_type":"text"},"source":["이번 데모에서는 루크를 선택해 변화를 살펴봅시다. k_max는 최대 반복횟수를 입력하는 것이었습니다. 여기서는 1번만 반복하기 위해서 1로 설정해줍니다."]},{"cell_type":"code","metadata":{"id":"fCOrXV_pkqAs","colab_type":"code","outputId":"21fe97d0-66bf-44a9-ecda-b192603b001b","executionInfo":{"status":"ok","timestamp":1581581200641,"user_tz":-540,"elapsed":889,"user":{"displayName":"High Score","photoUrl":"https://lh3.googleusercontent.com/a-/AAuE7mCh-oy47G4mQPfiC6fFDlX7Sjjl2zWhyxZTvbWUew=s64","userId":"09035638064630994320"}},"colab":{"base_uri":"https://localhost:8080/","height":1000}},"source":["agent = Piece(piece='rook') \n","r = Reinforce(agent,env)\n","r.policy_iteration(k=1,gamma=1)  "],"execution_count":0,"outputs":[{"output_type":"stream","text":["\n","\n","______iteration: 1 ______\n","\n"," policy:\n","[['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↑', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', 'F', '↑', '↑']]\n","\n","Value function for this policy:\n","[[-1 -1 -1 -1 -1 -1 -1 -1]\n"," [-1 -1 -1 -1 -1 -1 -1 -1]\n"," [-1 -1 -1 -1 -1 -1 -1 -1]\n"," [-1 -1 -1 -1 -1 -1 -1 -1]\n"," [-1 -1 -1 -1 -1 -1 -1 -1]\n"," [-1 -1 -1 -1 -1 -1 -1 -1]\n"," [-1 -1 -1 -1 -1 -1 -1 -1]\n"," [-1 -1 -1 -1 -1  0 -1 -1]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 2 ______\n","\n"," policy:\n","[['↑', '↑', '↑', '↑', '↑', '↓', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↓', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↓', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↓', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↓', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↓', '↑', '↑'],\n"," ['↑', '↑', '↑', '↑', '↑', '↓', '↑', '↑'],\n"," ['→', '→', '→', '→', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-6 -6 -6 -6 -6 -1 -6 -6]\n"," [-6 -6 -6 -6 -6 -1 -6 -6]\n"," [-6 -6 -6 -6 -6 -1 -6 -6]\n"," [-6 -6 -6 -6 -6 -1 -6 -6]\n"," [-6 -6 -6 -6 -6 -1 -6 -6]\n"," [-6 -6 -6 -6 -6 -1 -6 -6]\n"," [-6 -6 -6 -6 -6 -1 -6 -6]\n"," [-1 -1 -1 -1 -1  0 -1 -1]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 3 ______\n","\n"," policy:\n","[['→', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['→', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['→', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['↓', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['↓', '↓', '→', '→', '→', '↓', '←', '←'],\n"," ['↓', '↓', '↓', '→', '→', '↓', '←', '↓'],\n"," ['↓', '↓', '↓', '↓', '→', '↓', '↓', '↓'],\n"," ['→', '→', '→', '→', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-1 -1 -1 -1 -1  0 -1 -1]]\n","\n"," Improving policy:\n","policy diff: False\n","\n","\n","______iteration: 4 ______\n","\n"," policy:\n","[['→', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['→', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['→', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['↓', '→', '→', '→', '→', '↓', '←', '←'],\n"," ['↓', '↓', '→', '→', '→', '↓', '←', '←'],\n"," ['↓', '↓', '↓', '→', '→', '↓', '←', '↓'],\n"," ['↓', '↓', '↓', '↓', '→', '↓', '↓', '↓'],\n"," ['→', '→', '→', '→', '→', 'F', '←', '←']]\n","\n","Value function for this policy:\n","[[-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-2 -2 -2 -2 -2 -1 -2 -2]\n"," [-1 -1 -1 -1 -1  0 -1 -1]]\n","\n"," Improving policy:\n","policy diff: True\n","Optimal policy found in 4 steps of policy evaluation\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"CiRo-rF8luPT","colab_type":"text"},"source":["# 1.7. 다음 이야기\n","\n","다음에는 Monte Carlo 및 Temporal Difference 기반 방법같이 모델이 없는 방법을 다룰 것입니다. 이러한 방법은 Markov 의사 결정 프로세스의 전환 확률을 모를 때 도움이됩니다.\n","\n"]},{"cell_type":"code","metadata":{"id":"xxbqefotmWQj","colab_type":"code","colab":{}},"source":[""],"execution_count":0,"outputs":[]}]}