オセロ〜「実装　ディープラーニング」の三目並べより(2)

# 概要
前回の続き、コードの説明を行いたいと思います。
前回はこちらです。
オセロ～「実装　ディープラーニング」の三目並べより(1)
http://qiita.com/Kumapapa2012/items/cb89d73782ddda618c99
後続の記事はこちら。
オセロ～「実装　ディープラーニング」の三目並べより(3)
http://qiita.com/Kumapapa2012/items/3cc20a75c745dc91e826
オセロ～「実装　ディープラーニング」の三目並べより(4)[終]
http://qiita.com/Kumapapa2012/items/9cec4e6d2c935d11f108

ソースコードはこちらです。
https://github.com/Kumapapa2012/Learning-Machine-Learning/tree/master/Reversi

説明するとはいったものの、そもそもこれは書籍「実装 ディープラーニング」の三目並べサンプルに、オセロゲームを付けてみただけのものです。
このため本稿ではサンプルからの変更点と、作成したオセロのコードの説明だけを行います。
各スクリプトファイルの意味や役割、動作の流れや、Deep Q-Leaning のくわしい説明は、書籍「実装 ディープラーニング」をご覧ください。

またきちんと勉強を始めてから、まだ 3 ヶ月くらいなので、間違いがあるかもしれません。
間違いのご指摘やご意見、ご不明点、ご質問などありましたら、コメントいただければ幸いです。

# 前提条件
下記の各スクリプトを実行する前に、「実装 ディープラーニング」の、三目並べのサンプルを実行できるように環境が構築済である必要があります。
スクリプトは、書籍「実装 ディープラーニング」に記載されているように、以下のようなコマンドを実行し、 Anaconda の環境に入ってから実施する必要があります。

> . activate main
(もしくは、source activate main)

また、各スクリプトの実行前には、RL_Glue が起動済である必要があります
("Game_Reversi_Test.py" を除く)。

# agent.py
機械学習を行う「エージェント」です。
## Usage:  
>python agent.py [--gpu &lt;gpu id&gt;] [--size &lt;board size&gt;]
    --gpu : GPU ID(省略した場合または負の値の場合、CPU を使用します。)
    --size : オセロのボードサイズ(省略した場合 既定値6。)  

## Description:  
DQN を用いて教科学習を行うエージェントです。  
ボードサイズは environment.py を起動時の指定と一致しなければなりません。[^1]
RL_Glue を通して、environment.py から以下の内容を 1 次元配列として受け取り、DQN により最良の手を判断し、RL_Glue に返します。

|層|内容                   |
|:---|:-------------------|
|0 |自分のコマの位置(Agent) |
|1 |相手のコマの位置(Environment)|
|2 |自分がコマを置ける位置|
|3 |相手がコマを置ける位置|

層 2 に置ける場所が示されている限り、エージェントは コマを置き続けます。
もし、層 2 自分のコマを置ける場所がない場合、エージェントはパスします。

例)6x6 盤 で以下のような状態の場合:  

|-|0|1|2|3|4|5|
|:--|:--|:--|:--|:--|:--|:--|
|0|0|0|0|0|0|0|
|1|0|0|0|0|0|0|
|2|0|1|-1|0|0|0|
|3|0|1|1|0|0|0|
|4|0|1|0|0|0|0|
|5|0|0|0|0|0|0|

入力内容は以下  
#### 0層
|-|0|1|2|3|4|5|
|:--|:--|:--|:--|:--|:--|:--|
|0|0|0|0|0|0|0|
|1|0|0|0|0|0|0|
|2|0|1|0|0|0|0|
|3|0|1|1|0|0|0|
|4|0|1|0|0|0|0|
|5|0|0|0|0|0|0|

#### 1層
|-|0|1|2|3|4|5|
|:--|:--|:--|:--|:--|:--|:--|
|0|0|0|0|0|0|0|
|1|0|0|0|0|0|0|
|2|0|0|1|0|0|0|
|3|0|0|0|0|0|0|
|4|0|0|0|0|0|0|
|5|0|0|0|0|0|0|

#### 2層
|-|0|1|2|3|4|5|
|:--|:--|:--|:--|:--|:--|:--|
|0|0|0|0|0|0|0|
|1|0|0|1|1|0|0|
|2|0|0|0|1|0|0|
|3|0|0|0|0|0|0|
|4|0|0|0|0|0|0|
|5|0|0|0|0|0|0|

#### 3層
|-|0|1|2|3|4|5|
|:--|:--|:--|:--|:--|:--|:--|
|0|0|0|0|0|0|0|
|1|0|0|0|0|0|0|
|2|1|0|0|0|0|0|
|3|0|0|0|0|0|0|
|4|1|0|1|0|0|0|
|5|0|0|0|0|0|0|

ニューラルネットワークは、入力層として、environment.py から取得した上述の情報と同じ要素数 x 学習時にさかのぼるAction数のノードを持ちます。
また今回はクラス QNet の ````__init__```` を変更し、全結合 8 層の隠れ層を持たせています。
出力層はボードサイズと一致する数のノード数を持ちます。
この出力層の各ノードのうち、最も値が高いものが、エージェントが選んだコマの置き場所、ということになります。

このほか、書籍とは以下の違いがあります。

| 値 | 書籍      | 本コード     |説明     |
|:-------|:--------|:------------------------|:--------------|
|self.n_rows|3|size(6以上偶数)|ボードサイズ|
|self.bdim|self.dim * 2|self.dim * 4|学習用データのサイズ|
|self.capacity|1 * 10**4|2 * 10**4|Replay Memory 保持数|
|self.n_frames|3|9|学習時にさかのぼるAction数|
|self.batch_size|32|128|学習時のバッチサイズ|

実装内容について、上記パラメータの変更に合わせて幾つか変更があるものの、動作の流れは書籍の説明と同じです。

# environment.py
エージェントの対戦相手となる「環境」です。
## Usage:  
> python environment.py [--size &lt;board size&gt;]
  --size : オセロのボードサイズ(省略した場合 既定値6。)  

## Description:  
書籍「実装 ディープラーニング」のサンプル "environment.py" から、三目並べのロジックを取り去り、"Game_Reversi.py" にてゲームのロジックを実装しています。
そのため、Game_Reversi のインスタンスを以下のようにして作成し、初期化しています。

```python:environment.py
import Game_Reversi as game_base
#(中略)
    def __init__(self, size):
        self.game= game_base.Game_Reversi(size,size)     
#(以下略)
```
ゲームのボードは指定されたサイズの正方形とし、N x N の Int 配列として、Game_Reversi クラスの g_board に保持されます。
各配列要素には以下のいずれかの値が入ります:

|||
|:--|:--|
|0|空きマス|
|1|エージェント|
|-1|環境|

1 の正負でプレーヤーを表現することで、アクションや判定を、符号を反転するだけで実行できるようにし、最小限のコードでゲームができるようにしています。
"agent.py" で説明したゲームのステータスは、関数 "build_map_from_game" で作成しています。

```python:environment.py
    def build_map_from_game(self):
        
        map_data=[]
        
        #   0： 現在の盤面(Agent=1　のコマの位置)
        board_data=(self.game.g_board.reshape(-1)== self.game.turn).astype(int)
        map_data.extend(board_data)
        
        #   1： 現在の盤面(Environment=-1　のコマの位置)
        board_data=(self.game.g_board.reshape(-1)==-self.game.turn).astype(int)
        map_data.extend(board_data)
        
        #   2： Agent が置ける場所。"turn" の正負でAgent と Environment を表現している。
        #      正なら Agent となる。
        pos_available=np.zeros_like(self.game.g_board)
        l_available=self.game.getPositionAvail(self.game.turn)
        for avail in l_available:
            pos_available[tuple(avail)]=1
        map_data.extend(pos_available.reshape(-1).tolist())
        
        #   3： Environmentの置ける場所
        pos_available=np.zeros_like(self.game.g_board)
        l_available=self.game.getPositionAvail(-self.game.turn)
        for avail in l_available:
            pos_available[tuple(avail)]=1
        map_data.extend(pos_available.reshape(-1).tolist())
        
        return map_data
```

基本的に、ボード状態の作成と、コマを置ける場所の作成を、turn の正負を変えて実行し、一次元配列を作成しているだけです。
ゲームの開始時は、ボードをリセットして上記関数で作成した内容を送るだけです。

````python:environment.py
    def env_start(self):
        #　plan:Reversi ボード初期化
        self.game.resetBoard()
        
        # map データの作成
        self.map=self.build_map_from_game()
#(中略)        
        # 盤の状態をRL_Glueを通してエージェントに渡す
        observation = Observation()
        observation.intArray = self.map
        
        return observation
````

ゲーム開始後は、エージェントからアクション(コマを置く場所)を指定されることで、以下の動作を行います。
1．エージェントのアクションを Game_Reversi に渡す。
2．Game_Reversi が、エージェントの手を実行し、結果を返す。
3．RL_Glue に結果を渡す。

エージェントのアクションは整数値となります。6x6 盤ならば -1 ≦ a ≦ 35 の整数となります。-1 はパスになります。
これをボードサイズを使って、ボードの行と列のタプルに変換し、Game_Reversi の step メソッドに渡すことでアクションを実行させます。

````python:environment.py
        if int_action_agent==-1 :
            step_raw_col=(-1,-1)
        else :
            step_raw_col=(int_action_agent//self.n_cols,int_action_agent%self.n_cols)
        
        # step　実行
        step_o, step_r, step_done = self.game.step(step_raw_col
````

アクションが実行されると、ボード状態、報酬とゲームが決着したかどうかのフラグが渡されます。
この時点で Game_Reversi の g_board(盤面) が、エージェントのコマが置かれ、かつ環境のコマが置かれた状態に更新されているので。この状態で関数 "build_map_from_game" を使用してボード状態を作成します。

最終的に、ボード状態、報酬、決着の有無を RL_Glue の Reward_observation_terminal クラスのインスタンス rot に格納し、RL_Glue に返します。

````python:environment.py

# (中略)
        rot = Reward_observation_terminal()
        
        #　build_map_from_game()でマップを作成する。
        self.map=self.build_map_from_game()
        observation = Observation()
        observation.intArray = self.map
        rot.o = observation
        
        #　step_r　は報酬、step_done　は継続の有無
        rot.r=step_r
        rot.terminal = step_done
# (中略)        
        # 決着がついた場合は agentのagent_end
        # 決着がついていない場合は agentのagent_step に続く
        return rot
````

# experiment.py
ゲームの管理を行う「実験」です。
## Usage:  
  + python environment.py [--size &lt;board size&gt;]  

## Description:
このスクリプトについては、書籍「実装 ディープラーニング」の内容から変更していないため、説明を割愛します。

# Game_Reversi.py
オセロゲームの実装です。
## Usage:  
  + (なし。environment.py から参照される。)  

## Description:
オセロゲームのルールを実装しています。
オセロの公式ルールでは、コマを置く場所は、相手のコマをひっくり返すことができる場所に限定されています。
またパスは、自身のコマを置ける場所が無いときに限ります。
このゲームでもこれらのルールに従っています。

ゲームのボードは Numpy の Int 配列で表現しています。このため、主なロジックは配列演算を用いて実装しています。[^2]

動作の流れは以下の通り:
1．初期化。ボードを表す配列を作り、中心の4コマを置く。[^3]
2．エージェントが先手でゲームが開始し、コマを置く場所を指定します。
3．環境は、エージェントが指定した場所にコマを置き、自身(環境)のコマをひっくり返します。パスされた場合何もしません。
4．自身(環境)のコマを置き、エージェントのコマをひっくり返します。置く場所がない場合パスとなり、何もしません。
5．上記の結果に基づいて報酬の決定、終了判定を行い、RL_Glue に返します。

初期化のコードです。

````python:Game_Reversi.py
    def __init__(self,n_rows,n_cols):
        #ボードリセット
        self.n_rows = n_rows
        self.n_cols = n_cols
        
        self.g_board=np.zeros([self.n_rows,self.n_cols],dtype=np.int16)
        # オセロ、中心に最初の4コマを置く
        self.g_board[self.n_rows//2-1,self.n_cols//2-1]=1
        self.g_board[self.n_rows//2-1,self.n_cols//2]=-1
        self.g_board[self.n_rows//2,self.n_cols//2-1]=-1
        self.g_board[self.n_rows//2,self.n_cols//2]=1
````

見ての通り、正方形ではないボードにも対応可能ですが、現在は environment.py 側で、正方形のみでゲームを始めるようにしています。

コマを置き、相手のコマを返すには、まずコマを置ける場所を特定しなければなりません。
これは、isValidMove()で行います。
isValidMove()は、配列演算を使って、コマを置ける場所の判定をします。
例えば、8x8 盤で、以下の X の場所(2,1)に、● がコマを置こうとしたとします。

![image](https://qiita-image-store.s3.amazonaws.com/0/172071/40c53289-4a31-c7b0-650b-98e8df1ac401.png)

以下のような流れで、この場所にコマが置けるかを判断します。
Phase1:
まず、指定した場所で 8 方向の隣接するコマを探します。緑でハイライトした場所に○があるか確認します。
○が1つもなければ、その時点で、その場所に●は置けないと判断し終了します。
この場合、赤で示した場所に ○ があるため、Phase2に進みます。

![image](https://qiita-image-store.s3.amazonaws.com/0/172071/af873c1c-94d7-a9e8-b47f-290f1632388c.png)

Phase2:
見つかった○の方向で ● を探します。探索範囲を黄色でハイライトしています。探索は ○ のある方向に向かって進み、 ● が見つかるか、空白が見つかるか、盤の端に至るまで続けられます。
初めに下方の (3,2) の○については、(5,4) で空白が見つかるため、この○は返せないということになります。
次に (2,2)の○について。右方向に探索をすると、(2,5)に●が見つかります。この時点で、X の位置(2,1)には●を置けるということになります。

![image](https://qiita-image-store.s3.amazonaws.com/0/172071/57046206-b81b-df9b-8dff-b8ab03d839a1.png)

これらを実装したのが以下のコードです。

````python:Game_Reversi.py
        # 指定場所から全方向にチェック。
        # 返せる相手のコマが一つでもあれば終了
        for direction in ([-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]):
            if not (0 <= (pos+direction)[0] < self.n_rows and 0 <= (pos+direction)[1] < self.n_cols ) :
                # 範囲外処理スキップ
                continue
            
            #
            # Phase 1: 隣接するコマの色が指定色の反対か？
            #
            cpos = pos + direction
            if (self.g_board[tuple(cpos)] == -c):
                #
                # Phase 2: その向こうに自コマがあるか
                #
                while (0 <= cpos [0] < self.n_rows and 0 <= cpos [1] < self.n_cols):
                    if (self.g_board[tuple(cpos)] == 0):
                        # 判定がつく前に空のマスなので終了
                        break
                    elif (self.g_board[tuple(cpos)] == -c):
                        # 自コマがこの先あれば、取れる可能性のあるコマ。
                        # 自コマの探索を続ける。
                        cpos = cpos+direction
                        continue
                    elif (self.g_board[tuple(cpos)] == c):
                        # 少なくともコマを一つ返せるため、この時点で探索終了。
                        result=True
                        break
                    else:
                        print("catastorophic failure!!! @ isValidMove")
                        exit()
````

isValidMove()をすべての空白のコマに対して実行することで、コマを置ける場所のリストが得られます。
これは getPositionAvail()関数で実装されています。

````
    def getPositionAvail(self,c):
        temp=np.vstack(np.where(self.g_board==0))
        nullTiles=np.hstack((temp[0].reshape(-1,1),temp[1].reshape(-1,1)))    
        
        # コマが無いマスについて、 IsValidMove()
        can_put=[]
        for p_pos in nullTiles:
            if self.isValidMove(p_pos[0],p_pos[1],c):
                can_put.append(p_pos)
        return can_put
````

エージェント、環境の双方とも、このコマを置ける場所のリストの中から、コマを置く場所を選択します。
またこの関数は、コマの符号を反転させるだけで、相手がコマを置ける場所のリストも得られるようになっています。

putStone()でコマをひっくり返します。
この関数では、isValidMoveと同様、8方向でコマを検索し、Phase 1、Phase 2 を実施します。
自コマと同じ色のコマが見つかったら、その場所から、コマを置いた場所まで遡ってコマをひっくり返します。先ほどの例では、(2,1)にコマを置き、(2,5) に同色コマが見つかっていますので、(2,4)、(2,3)、(2,2) の順番でコマをひっくり返します。
以下のコードです。

````python:Game_Reversi.py
        for dir in ([-1,-1],[-1,0],[-1,1],[ 0,-1],[ 0,1],[ 1,-1],[ 1,0],[ 1,1]):
            f_canFlip=False
            cpos = pos + dir
#(中略)
            # 現在の cpos の位置から、指定した位置まで後進してコマを返す。
            if f_canFlip :
                cpos=cpos-dir #返すコマ一つ目
                while np.array_equal(cpos,pos) == False:
                    board[tuple(cpos)] = c
                    numFlip = numFlip + 1
                    cpos=cpos-dir
````

この関数は、ひっくり返したコマの数を返します。
第 4 引数を True とするとシミュレーションを行うモードになり、ひっくり返した内容をゲームに反映しません。これは事前に、どこにコマを置けば、いくつのコマをひっくり返せるかを確認したい場合に使います。
この関数も、符号を反転させるだけで、ひっくり返すコマの色を変えることができます。

エージェントは、コマを置く場所を DQN で決めますが、環境は、getPosition() でコマを置く場所を決定します。
getPosition() のロジックが、オセロの強さを決めます。
今回のコードでは、以下のロジックでコマを置く場所を決めています。

1. getPositionAvail() でコマを置ける場所のリストを得ます。
2. リストが空なら、置く場所がないため空の配列を返します(結果的にパスになります。)
3. リストに要素がある場合、以下の基準で置く場所を選定します。

|確率|場所|
|:--|:--|
|90%|四隅のいずれか|
|80%|もっとも多くコマをとれる位置|
|10% or 20%|ランダム(四隅のどこかにコマが置ける場合10%、置けない場合 20%)|

以下のコードです。

````python:Game_Reversi.py
        # ランダムとするか決める
        t_rnd=np.random.random()
        
        # 1. 角がある場合は、90% の確率でそこを取る
        if cornerPos != []:
            if t_rnd < 0.9:
                returnPos= cornerPos[np.random.randint(0,len(cornerPos))]
        
        #　2. 次に、80% の確率で最も数が多いものを取得する。
        if returnPos==[]:
            if maxPos != []:
                if t_rnd < 0.8:
                    returnPos= maxPos
        
        #　3. この時点で決まらない場合ランダム(結局　1,2　のものとなる可能性あり。)
        if returnPos==[]:
            returnPos= can_put[np.random.randint(0,len(can_put))]
        
        return returnPos
````

以上で、エージェント、環境双方のアクションが完了したら、終了判定と報酬の計算をします。
終了判定は、双方のコマを置ける場所を探すことで行います。双方、置く場所がなくなった場合にゲーム終了となります。
報酬は、ゲーム継続中は 0、ゲーム終了の場合、双方のコマの数を数えて、同じなら「引き分け」ということで -0.5、エージェントが多い場合、「勝ち」ということで 1.0、エージェントが少なければ「負け」ということで、-1.0 の報酬が与えられます。
以下のコードになります。

````python:Game_Reversi.py
        stonePos_agent = self.getPosition(self.turn)
        stonePos_environment = self.getPosition(-self.turn)
        if stonePos_agent==[] and stonePos_environment==[]:
            done=True
            if self.render : print("****************Finish****************")
        
        if done :
            #　2.　終了ならば報酬計算
            num_agent=len(np.where(self.g_board==self.turn)[1])       
            num_envionment=len(np.where(self.g_board==-self.turn)[1]) 　
            if self.render : print("you:%i/environment:%i" % (num_agent,num_envionment))
            # 判定
            if num_agent > num_envionment :
                reward=1.0
                if self.render : print("you win!")
            elif num_agent < num_envionment :
                reward=-1.0
                if self.render : print("you lose!")
            else :
                reward=-0.5
                if self.render : print("Draw!")
````

# Game_Reversi_Test.py
上記 "Game_Reversi.py" のテスト用です。
エージェントの代わりに人間と対戦出来るようにします。
## Usage:  
> python Game_Reversi_Test.py

## Description:
以下のようにボードサイズが 8x8 でハードコードされていますので適宜、変更して下さい。

````python:Game_Reversi_Test.py
g=game.Game_Reversi(8,8)
````

起動すると、ユーザーの入力待ちになります。コマを置く位置を "2,4" のようにカンマ区切りの整数で指定します。
エージェントへの反応と同様、指定した場所にコマを置き、自身のコマを置きます。そして再度、入力待ちになります。
最終的に両者がコマを置くことができなくなると、終了判定、スコアを表示して終了します。

# おわりに
説明は以上です。お役に立てれば幸いです。
間違いのご指摘やご意見、ご不明点、ご質問などありましたら、コメントいただければ幸いです。

# 参考文献
(書籍)実装　ディープラーニング
http://shop.ohmsha.co.jp/shopdetail/000000004775/  
オセロのルール
http://www.othello.org/lesson/lesson/rule.html
(この他の参考文献については、また後日記載します)


[^1]: しかし、agent_init で RL_Glue から情報を受けとっているので、それを使えばこの引数はいらないかも？
[^2]: またこのため、Cuda の Numpy (cupy) を使用することも可能と思います。
[^3]: ちなみに、先手つまりエージェント(= 1)の色を、公式ルールに従って黒とした場合、「日本オセロ連盟」の定めるルールによると、このクラスの初期のコマの配置は、白黒が逆だそうです。とはいえ 局面が 90 度回転しただけで理論的にはなんら変わりがないので、そのままにしておきます。