オセロにコンピューター対戦を実装する。

##はじめに
　Pythonでオセロのコードを書き、コンピューターと対戦できるモードを実装します。
　今後はディープラーニングを用いたコンピューター対戦モード等の機能を追加していきたいです。


##目次
1. はじめに
2. 遊び方
3. コードの説明
    1. 石の設定と辞書
    2. オセロ盤面を再現（参考文献[1]）
    3. モード切替とゲームの進行
    4. クラス継承とdeepcopy関数
    5. コンピューターモード（参考文献[4])
4. 感想
5. 参考文献


##遊び方
　選択肢が以下のように表示されます。
　put to: [0:(2, 3), 1:(3, 2), 2:(4, 5), 3:(5, 4)]
　(2, 3)に置きたい場合は0を入力すればokです。

![オセロ_遊び方.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402787/20351bc2-3bac-1132-2aca-0cde4a3a96bc.png)

##コードの説明
　コンピューターモードを説明する前に、まずはオセロをするための基本的なプログラムから説明していきます(参考文献[[1]](https://katoh4u.hatenablog.com/entry/2018/03/22/130105),[[2]](https://qiita.com/shiracamus/items/f03127819fff0f1a4349))。

####1. 石の設定と辞書
　後でdeepcopy関数を使いたいのでcopyをインポートしておきます。石の設定と石を白黒で切り替えるときに便利な辞書を作っています。

```python:othello_CPU.py
import copy

# 石の設定と辞書
BLACK = 1
WHITE = -1
STONE = {1:'BLACK', -1:'WHITE'}
OPPONENT = {BLACK: WHITE, WHITE: BLACK}
```

####2. オセロ盤面を再現（参考文献[1]）
このクラスは、[文献[1]]
(https://katoh4u.hatenablog.com/entry/2018/03/22/130105)のほぼパクリです。すみません。for文の勉強のためにボードを表示する部分を少し自分で変えました(show_board(self,turn)の部分)。

・何ターン目なのか表示する。
・右に何マス、下に何マスの場所に石があるのかわかるようにする。

という変更を加えさせていただきました。

---
　boardクラスは、以下の要素を持っています。
　　・8×8の何もない平面を作る。
　　・石の初期配置をする。
　　・オセロ盤を表示する。
　　・石を置くことができる場所を探す。
　　・ひっくり返せる石を探す。


```python:othello_CPU.py
class Board:
    def __init__(self):
        # 8×8の何もない平面を作る。
        self.cells = []
        for i in range(8):
            self.cells.append([None for i in range(8)])

        # 4つの石を初期配置する
        self.cells[3][3] = WHITE
        self.cells[3][4] = BLACK
        self.cells[4][3] = BLACK
        self.cells[4][4] = WHITE

    # 石を置く処理
    def put(self, x, y, stone):
        flippable = self.list_flippable_disks(x, y, stone)
        self.cells[y][x] = stone
        for x,y in flippable:
            self.cells[y][x] = stone

        return True

    # ボードを表示する。
    def show_board(self,turn):
        print("--" * 20)
        print(str(turn) + "ターン目")
        print("  ", end="")   # ,end=""は改行を防ぐ。
        for i in range(8):
            print(i, end="")
            print(" ", end="")
        print("\n", end="")

        j = 0
        for i in self.cells:
            print(j, end="")
            print(" ", end="")
            j += 1
            for cell in i:
                if cell == WHITE:
                    print("W", end=" ")
                elif cell == BLACK:
                    print("B", end=" ")
                else:
                    print("*", end=" ")
            print("\n", end="")

    # 石を置くことができる場所を探す。
    def list_possible_cells(self, stone):
        possible = []
        for x in range(8):
            for y in range(8):
                if self.cells[y][x] is not None:
                    continue
                if self.list_flippable_disks(x, y, stone) == []:
                    continue
                else:
                    possible.append((x, y))
        return possible

    # ひっくり返せる石を探す。
    def list_flippable_disks(self, x, y, stone):
        PREV = -1
        NEXT = 1
        DIRECTION = [PREV, 0, NEXT]
        flippable = []

        for dx in DIRECTION:
            for dy in DIRECTION:
                if dx == 0 and dy == 0:
                    continue

                tmp = []
                depth = 0
                while(True):
                    depth += 1

                    # 方向 × 深さ(距離)を要求座標に加算し直線的な探査をする
                    rx = x + (dx * depth)
                    ry = y + (dy * depth)

                    # 調べる座標(rx, ry)がボードの範囲内ならば
                    if 0 <= rx < 8 and 0 <= ry < 8:

                        request = self.cells[ry][rx]

                        # Noneを獲得することはできない
                        if request is None:
                            break

                        if request == stone:  # 自分の石が見つかったとき
                            if tmp != []:      # 探査した範囲内に獲得可能な石があれば
                                flippable.extend(tmp) # flippableに追加
                            else:              #探査した範囲内に獲得可能な石がなければ
                                break

                        # 相手の石が見つかったとき
                        else:
                            tmp.append((rx, ry))  # 獲得可能な石として一時保存
                    else:
                        break
        return flippable
```


####3. モード切替とゲームの進行
　ここからはオリジナルです(笑)。
　対人戦モード、コンピューター対戦モードが選べるようにしたかったので、モード切替を実装しました。モード切替とゲームの進行は同じクラスにしました。これによって、self.player1とself.player2がモードの設定をゲーム進行に引き継いでくれます。新しいモードを実装したいときに、追加しやすいようにしています。

---
　ゲームの進行のクラスには、以下の要素を書きました。
　　・モード選択。
　　・勝敗の決定。
　　・プレイヤーのターンを回す。
　　・パスのときどうするか。
　　・硬直状態になったら決着とする。
　　・選ばれた場所に石を置く。
　　・現在の盤面のコピーを作る。(次の節で解説)

```python:othello_CPU.py
class Othello:

    # モード切替
    def mode_option(self, mode):
        if mode == 0:
            self.player1 = User(BLACK, "PLAYER1")
            self.player2 = User(WHITE, "PLAYER2")
        elif mode == 1:
            self.player1 = User(BLACK, "あなた")
            self.player2 = Mini_method(WHITE, "Mini-method")
        elif mode == 2:
            self.player1 = User(BLACK, "あなた")
            self.player2 = Max_method(WHITE, "Max-method")
        """この下に書き加えれば新しいモードを増やせる。今後はコンピュータ同士で戦わせたりしたい。"""

    # ゲームの進行
    def play(self):
        board = Board()
        turn = 1
        pass_turn = 0 # お互いにpassしかない硬直状態になったら終わらせるため。
        mode = int(input("mode select: 0)PvP 1)vs.Mini_method 2)vs.Max_method > "))
        self.mode_option(mode)

        while(True):
            board.show_board(turn)
            black_count = 0
            white_count = 0
            for x in range(8):
                for y in range(8):
                    if board.cells[y][x] == BLACK:
                        black_count += 1
                    elif board.cells[y][x] == WHITE:
                        white_count += 1

            # 石がすべて置かれた、または硬直状態、またはどちらかの全滅で決着とする。
            if (black_count + white_count == 64
                or pass_turn == 2
                or black_count == 0
                or white_count == 0):
                print("--" * 10+ "finished!!" + "--" * 10)
                if black_count > white_count:
                      print("WINNER BLACK!!")
                elif black_count < white_count:
                      print("WINNER WHITE!!")
                else:
                      print("Draw")

                print("results:  " + "B: " + str(black_count) + ", W: " + str(white_count))
                break

            # Player1のターン
            elif turn % 2 == 1:
                stone = BLACK
                possible = board.list_possible_cells(stone)
                if possible == []:  # 置ける場所がなければpass
                    pass
                else:  # 置ける場所があるならどこに置くか決める。
                    index = self.player1.main(possible)  # 判断材料としてpossibleを送る。

            # Player2のターン(Player1と同様)
            elif turn % 2 == 0:
                stone = WHITE
                possible = board.list_possible_cells(stone)
                if possible == []:
                    pass
                else:
                    index = self.player2.main(possible)

            # pass
            if possible == []:
                print("pass")
                pass_turn += 1
                pass
            # Playerが決めた場所に石を置く
            else:
                board.put(*possible[index],stone)
                self.player1.copy_board(possible,index,stone)
                self.player2.copy_board(possible,index,stone)
                pass_turn = 0

            turn += 1
```

####4. クラス継承とdeepcopy関数
　人が入力するときに使うのがUserクラス。コンピューターが考えるためのMini_methodクラスとMax_methodクラス(次の節で登場)。この３つのクラスに共通していることをBasePlayerクラスにまとめました。

　pythonがもつクラス継承の機能を使っています。「class 'クラス名'(継承元クラス):」と書くことで新しいクラスに前に書いたクラスの中身を持ってくる(継承)ことができます。
　例) class User(BasePlayer):

　BasePlayerクラスには、importしておいたdeepcopy関数を使っています。deepcopy関数でself.boardのコピーを取り、リセット時はself.boardをコピーと同じにしています。deepcopy関数は[参考文献[3]](https://qiita.com/Kaz_K/items/a3d619b9e670e689b6db
)にて詳しく説明されています。具体例を用意しました。BasePlayerクラスにあるdeepcopy関数をcopy関数に変えた場合のコンピューターが考える過程をgif画像にしました。

![オセロ.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402787/eb0d63c6-cb6a-d204-6f74-954b0e39994f.gif)

これはcopy関数が全然ダメって言いたいわけではなくて、今回の使い方だとこういう違いが起こると言いたいだけです。実際、copy関数は便利です。では、今回なぜこのような違いが出たのか。簡単にいうと、「copy関数はコピーしたもの or コピー元を編集すると、もう片方も変えてしまうから」です。このプログラムだとreset_board(self)で使うcopy_cellsがどんどん変わっていってしまいます。だから、copy関数の方は正常にリセットできませんでした。

```python:othello_CPU.py
# すべてのPlayer(人とコンピューター)に共通するクラス
class BasePlayer:

    # 自分の名前と石の色を把握する。
    def __init__(self,stone,name):
        self.stone = stone
        self.name = name
        self.board = Board()
        self.copy_cells = []

    # 実際の盤面のコピーを作る。(CPU用)
    def copy_board(self,possible,index,stone):
        self.board.put(*possible[index],stone)
        self.copy_cells = copy.deepcopy(self.board.cells)

    # 計算後に盤面をもとに戻す。(CPU用)
    def reset_board(self):
        self.board.cells = copy.deepcopy(self.copy_cells)

# 人の入力を受け付けて石を置く。(人)
class User(BasePlayer):

    def main(self,possible):
        print("player: " + self.name + " (" + STONE[self.stone] + ")")
        print("put to: ", end="[")   # ,end=""は改行を防ぐ。
        for i in range(len(possible) - 1): # 選択肢を表示する。
            print(str(i) + ":" + str(possible[i]), end=", ")
        print(str(len(possible) - 1) + ":" + str(possible[len(possible) - 1]) + "]")
        index = int(input("choose: "))  #Userが石を置く場所を選ぶ。
        print("You put:" + str(possible[index]))
        return index  # 選ばれた選択肢の番号を返す。
```

####5. コンピューターモード
　モード１か２が選ばれたときに、コンピューター対戦ができます。ゲーム進行から、置ける場所のリスト(possible)をコンピューターは受け取って考えています。以下に２種類のコンピューターのアルゴリズムを説明します。[(参考文献[4])](https://ja.wikipedia.org/wiki/ミニマックス法)


---
#####Mini_method
　Mini_methodは「相手が置ける場所がなくなるように手を打とうとするアルゴリズム」です。オセロをやってみるとわかるのですが、置ける場所の選択肢が減るとキツいです。そういう意味でいうと「相手が不利になるように手を打つアルゴリズム」であるとも言えます。以下にMini_methodのフローチャートを示します。角を取られないような考え方も入れておかないとさすがに弱かったので追加しています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402787/d5326494-293b-1081-592c-b97ae68a17b2.png)


```python:othello_CPU.py
# 次相手が打つ手のパターン(opponent_possible)が少なくなるように石を置く。(CPU)
class Mini_method(BasePlayer):

    def main(self,possible):
        min_count = 30
        index = 0  # 最悪0番目の選択肢を選ぶ。(バグ防止)

        # 選択肢をしらみつぶしに調べていく。
        for i in range(len(possible)):
            self.board.put(*possible[i],self.stone)  # i番目の選択肢で仮で置いてみる。
            # その時の相手が取れる選択肢を調べる。
            opponent_possible = self.board.list_possible_cells(OPPONENT[self.stone])

            # 角トラレタクナイ
            if ((0,0) in opponent_possible
                or (0,7) in opponent_possible
                or (7,0) in opponent_possible
                or (7,7) in opponent_possible):
                pass  #角が取られる選択肢を捨てる。

            # 相手の選択肢(opponent_possible)が最小のときのiを保存する。
            elif len(opponent_possible) <= min_count:
                min_count = len(opponent_possible) # より少ないものがあれば最小値を更新。
                index = i  # 自分の手(i)をindexに保存。
            # 相手の選択肢が最小じゃないならスルー。
            else:
                pass

            self.reset_board()  # 仮で置いた石をリセット。

        # CPUが選んだ選択肢などを表示。
        print("player: " + self.name + " (" + STONE[self.stone] + ")")
        print("put to: ", end="[")
        for i in range(len(possible) - 1):
            print(str(i) + ":" + str(possible[i]), end=", ")
        print(str(len(possible) - 1) + ":" + str(possible[len(possible) - 1]) + "]")
        print("choose: " + str(index), end=":")
        print(possible[index])

        return index  # 選ばれた選択肢の番号を返す。
```

---
#####Max_method
　Max_methodは「自分が置ける場所が増えるように手を打つアルゴリズム」です。Mini_methodと逆で「自分が有利になるように手を打つアルゴリズム」と言えます。こちらも同様に角取り防止を付けています。フローチャートは以下の通りです。プログラムをそのまま図にすると複雑になりすぎてしまうので少し省略しています。すみません。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/402787/922e1836-8106-7beb-c31b-8ea6e82cb743.png)


```python:othello_CPU.py
# 次の自分の打つ手(next_possible)が多くなるように石を置く。(CPU)
class Max_method(BasePlayer):

    def main(self,possible):
        max_count = 0
        count = 0
        index = 0  # 最悪0番目の選択肢を選ぶ。(バグ防止)

        # 選択肢をしらみつぶしに調べていく。
        for i in range(len(possible)):
            self.board.put(*possible[i],self.stone)  # i番目の選択肢で仮で置いてみる。
            # その時の相手が取れる選択肢の個数を調べる。後でもう一度書くのはリセットされてしまうため。
            # ここでopponent_possibleを調べるのはjの繰り返しの上限を決めるため。
            opponent_possible = self.board.list_possible_cells(OPPONENT[self.stone])
            self.reset_board()  # 一旦リセット。

            # 角トラレタクナイ
            if ((0,0) in opponent_possible
                or (0,7) in opponent_possible
                or (7,0) in opponent_possible
                or (7,7) in opponent_possible):
                continue  #角が取られる選択肢を捨てる。
            else:
                pass

            # 自分の手(i)に対する相手の手(j)を調べる。
            for j in range(len(opponent_possible)):
                self.board.put(*possible[i],self.stone)  #リセットされているのでもう一度。
                opponent_possible = self.board.list_possible_cells(OPPONENT[self.stone])
                # 相手の手(j)を仮で置く。
                self.board.put(*opponent_possible[j],OPPONENT[self.stone])
                # その次の自分の打つ手(next_possible)を調べる。
                next_possible = self.board.list_possible_cells(self.stone)
                count += len(next_possible) # i番目のnext_possibleの長さを合計する。
                self.reset_board() # 一旦リセット。

            # next_possibleの合計(count)が最大のiを保存する。
            if count >= max_count:
                max_count = count  #より大きいものがあれば最大値を更新。
                index = i  # 自分の手(i)をindexに保存。
            # 相手の選択肢が最小じゃないならスルー。
            else:
                pass

        # CPUが選んだ選択肢などを表示。
        print("player: " + self.name + " (" + STONE[self.stone] + ")")
        print("put to: ", end="[")
        for i in range(len(possible) - 1):
            print(str(i) + ":" + str(possible[i]), end=", ")
        print(str(len(possible) - 1) + ":" + str(possible[len(possible) - 1]) + "]")
        print("choose: " + str(index), end=":")
        print(possible[index])

        return index  # 選ばれた選択肢の番号を返す。
```

####おまけ
　メイン文です。ゲーム進行のクラスを呼び出してくれます。

```python:othello_CPU.py
# メイン文
if __name__ == "__main__":
    Othello().play()
```


##感想
　自分は、1年間C言語をやっていたのですが、ディープラーニングをやってみたくてpythonの勉強を始めました。Cと比べて圧倒的に短く書けて感動しました(笑)。ほぼ英語なので直感的に覚えやすかったです。逆にわかりづらかった点もありました。始めたばかりの頃は他の人のコードを見ても、どれがpythonで元から使える関数で、どれが定義した関数なのかよくわかりませんでした。~~多分、共感してくれる人いるはず（笑）。~~自分でコードを書いてみて初めて違いがちゃんとわかりました。
　今の自分はimportを使いこなせていない感じがして、もっとpythonの便利機能を使って短くシンプルなコードを書けるようになることが今後の課題です。
　ここまで読んでくださってありがとうございました！！

##参考文献
1. [Python初心者は練習問題としてリバーシ(オセロ)を実装するべき](https://katoh4u.hatenablog.com/entry/2018/03/22/130105)
2. [「プログラミング初心者がpythonの勉強がてら、オセロAIを作ってみた」をリファクタリングさせていただいた](https://qiita.com/shiracamus/items/f03127819fff0f1a4349
)
3. [Pythonのcopyとdeepcopyについて](https://qiita.com/Kaz_K/items/a3d619b9e670e689b6db
)
4. [ミニマックス法 wikipedia](https://ja.wikipedia.org/wiki/ミニマックス法
)
5. [はじめてのディープラーニング -Pythonで学ぶニューラルネットワークとバックプロパゲーション-](https://www.amazon.co.jp/はじめてのディープラーニング-Pythonで学ぶニューラルネットワークとバックプロパゲーション-Machine-Learning-我妻/dp/4797396814/ref=sr_1_1?hvadid=335573538199&hvdev=c&jp-ad-ap=0&keywords=%E3%81%AF%E3%81%98%E3%82%81%E3%81%A6%E3%81%AE%E3%83%87%E3%82%A3%E3%83%BC%E3%83%97%E3%83%A9%E3%83%BC%E3%83%8B%E3%83%B3%E3%82%B0&qid=1555824135&s=gateway&sr=8-1)