強化学習でハノイの塔AIを作る（個人的メモ）

この記事は、以下の記事のハノイの塔バージョンの翻訳です。
基本的に元記事の方が分かりやすいので、この記事をざっと読んだ後は元記事を読む事をお勧めします。
https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/!

# 強化学習とは？
機械学習の分野の一つです。
試行錯誤を通じて「価値を最大化するような行動」の学習に適しています。
例えば囲碁のアルファ碁、自動車の自動運転、株式の自動売買など、自分で考えるAUを作るのに適しています。

今回は、強化学習における入門によく使われるのQ-learningを使用してハノイの塔を解くAIを作成します。

# Q-learningとは?
以下の式です。
数式にすると難しそうですが、純粋なpythonでも数行で表現出来るほど、恐ろしくシンプルな実装になります。
![スクリーンショット 2021-01-12 20.55.41.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183835/15006266-22ce-8c34-efe9-ce0fbabbaeb3.png)

```python

q_table[state_id][action] = (1 - alpha) * old_reward + alpha * (current_reward + gamma * next_max_reward)
```

# 強化学習の基本
ハノイの塔を例にして説明します。
ここに、３個縁があるハノイの塔があります。
[hanoi.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183835/1f02f0eb-2736-f1fd-cea1-7450b3da8bf3.png)
ハノイの塔のルールは以下です。
・積み上げられた円盤を，すべて他の棒に移すこと。
・その際に，１回に１枚しか動かしてはならない。 また，小さな円盤の上にそれより大きな円盤を乗せてはならない。
・すべてこの３本の棒を使って移すこと。 棒以外のところに円盤を置いてはならない。

強化学習で重要な３つの概念について学びます。
 1. エージェント
 ハノイの塔を動かすAIの事です。
 2. 報酬
 エージェントは報酬が最大になるようにアクションを行います。
・　エージェントは、ハノイの塔をクリアした時、大きなプラスの報酬を得ます。
・　エージェントは、無効なアクションを行った時、マイナスの報酬を得ます。
・　エージェントは、円盤を一回移動させるたびに、わずかなマイナスの報酬を得ます。　これは、エージェントに、最短経路でハノイの塔をクリアさせるためです。
3. StateとAction
強化学習では、エージェントは、State(状態)の中にいます。そして、Stateに対応したアクションを行います。
例えば、以下のStateについて考えます。
![スクリーンショット 2021-01-14 23.05.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183835/23614bee-9911-ca9d-a50d-c398f4d115b9.png)
この時エージェントが選択できるアクションは、
・「１」を右端に動かす
・「２」を中央に動かす
の二通りだけです。
4. State Space
全てのStateの集合です。
ハノイのとうは、３つの円盤が、３本の棒に刺さっているので、 3 * 3の盤面があります。
5. Action Space
実行可能なアクションの選択肢です。
ハノイの塔では
1. 左端の円盤を中央へ移動
2. 左端の円盤を右端へ移動
3. 中央の円盤を左端へ移動
4. 中央の円盤を右端へ移動
5. 右端の円盤を左端へ移動
6. 右端の円盤を中央へ移動
の６種類のアクションが、選択可能で、このリストをAction Spaceと言います。

# Q-learningの考え方。
必要な知識が揃いました。
Q-learningでハノイの塔を解いていきましょう。
強化学習では、行動のことを「アクション」。アクションを行うプログラムを、「エージェント」と言います。
我々はエージェントに、「報酬」や「罰」を与える事でより賢くなっていきます。
このエージェントをQ学習で作りましょう。

# 報酬と罰
まず、ハノイの塔における「報酬」と「罰」について考えましょう。
報酬ですが、ハノイの塔をクリア（円盤を左から右に移し終えた）瞬間に＋１００を与えましょう。
罰は、エージェントが無効な動作（小さい円盤の上に大きい円盤を置く。円盤がない場所から円盤を動かそうとする）をしたら-10の罰を与ます。
また、なるべく少ないアクションでクリアして欲しいため、一回移動すると-0.1の罰を与えましょう。クリアまでのターン * -0.1のペナルティを与えます。

# Q-table
Q学習では、エージェントの行動をQ-tableというテーブル（配列）に入れます。
エージェントはQ-tableを元にアクションを行います。

試行錯誤しながらAIを進化させるため、エージェントは10%はランダムな行動を行います。
この10%を学習率と言います。

割引率 =　今回のアクションで報酬を得た場合、一つ前のアクションに報酬を与える割合。
例えばハノイの塔をクリアした時、クリアする一手前のアクションBにも 100 * 割引率報酬を与えます。

簡単ですね。
例えば以下の状況の時
エージェントは、以下の報酬を受け取ります。
可能な移動 = -0.1
無効な移動 = -10
ゲームクリア = +100
1. 左端の円盤を中央へ移動 = -0.1
2. 左端の円盤を右端へ移動 = +100
3. 中央の円盤を左端へ移動 = -10
4. 中央の円盤を右端へ移動 = -10
5. 右端の円盤を左端へ移動 = -10
6. 右端の円盤を中央へ移動 = -0.1
![スクリーンショット 2021-01-14 23.19.29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183835/a3258255-8040-812e-b3f4-ad1babbc77c2.png)

ゲームをクリアする2を選択した時、この盤面に到一個前の行動に対して、q学習の式を使用して報酬を与えます。
これを繰り返していき、AIを進化させていきます。
これから作るAIの報酬リストの事をq-tableと言います。
![スクリーンショット 2021-01-12 20.55.41.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183835/15006266-22ce-8c34-efe9-ce0fbabbaeb3.png)

```python

q_table[state_id][action] = (1 - alpha) * old_reward + alpha * (current_reward + gamma * next_max_reward)


# openAI gym
openAI gymとは、強化学習のために作られた環境の事です。
マリオや、ルービックキューブなどが使いやすく統一されたAPIでラップされてあります。
今回は、ハノイの塔バージョンのhttps://github.com/RobertTLange/gym-hanoi
を使用します。

# 実装

```python
# logic.py
import operator
from random import randrange
import gym
import gym_hanoi

def random_action():
    return randrange(5)

def generate_unique_state_id(tup):
    return str(tup[0]) + str(tup[1]) + str(tup[2])

def get_max_reward_of_action(dit):
    # dictのvalueの中の最大値のkeyを返す
    return max(dit.items(), key=operator.itemgetter(1))[0]

def initialize_3_disks_q_table():
  q_table = {}
  for i in range(3):
    for j in range(3):
      for k in range(3):
        state_id = generate_unique_state_id((i, j, k))
        q_table[state_id] = {}
        for action in range(6):
          q_table[state_id][action] = 0
  return q_table

def get_max_reward(q_table, state_id):
  # dictのvalueの最大値を返す。
  return max(q_table[state_id].values())

def show_q_table_animation(q_table):
  env = gym.make("Hanoi-v0")
  # ディスクを３枚、移動を間違える確率を0%に設定
  env.set_env_parameters(num_disks=3, env_noise=0)

  state = env.reset() # 初期 state は、(0, 0, 0)
  
  while True:
    print(state)

    state_id = generate_unique_state_id(state)
    best_action = get_max_reward_of_action(q_table[state_id])
    next_state, raw_reward, done, info = env.step(best_action)
    if done:
      break
    state = next_state
```

```python
# main.py
import random
from random import randrange
from IPython.display import clear_output
import gym
import gym_hanoi
import numpy as np
from logic import random_action, generate_unique_state_id, get_max_reward_of_action, initialize_3_disks_q_table, get_max_reward, show_q_table_animation


env = gym.make("Hanoi-v0")
# ディスクを３枚、移動を間違える確率を0%に設定
env.set_env_parameters(num_disks=3, env_noise=0)

# Q-table 2次元配列だと、tupleをstringへと変換したものが入れられないのでq-tableをdictで作成
q_table = initialize_3_disks_q_table()

# ハイパーパラメーター
alpha = 0.1 # 学習率
gamma = 0.6 # 割引率
epsilon = 0.1

for i in range(1, 800):
    state = env.reset()

    state_id = generate_unique_state_id(state)

    current_reward = 0
    
    while True:
        # 10% ランダムなアクションを選択
        # 90% 一番高い報酬のactionを返す。
        action = random_action() if random.uniform(0, 1) < epsilon else get_max_reward_of_action(q_table[state_id])

        next_state, reward, done, info = env.step(action)
        if done:
            break # ハノイの塔がクリアされた時点で学習終了

        next_state_id = generate_unique_state_id(next_state)
        next_max_reward = get_max_reward(q_table, next_state_id)
        current_reward = -0.1 if reward == 0 else reward # 一回の移動にわずかなペナルティを加える。
        old_reward = q_table[state_id][action]
        
# 以下一行が、q学習のキモ。
        q_table[state_id][action] = (1 - alpha) * old_reward + alpha * (current_reward + gamma * next_max_reward)

        state_id = next_state_id


print("Training finished.\n")
print(q_table)

show_q_table_animation(q_table)
```