勇気ある加藤の猛り

元気はないけど、勇気があります

Python初心者は練習問題としてリバーシ(オセロ)を実装するべき

こんにちは勇気ある加藤です
私がはじめてプログラミングを学んだときは、主に入門サイトで演習問題を解くなどして文法を覚えたのですが、プログラミングの入門ってだいたい、Hello, Worldして、繰り返しで数を列挙して、乱数を使った数あてゲームを作ったりしてーといった感じですよね。
そうして解説などを読みながら「うんうんうん、なるほどね、繰り返す処理とかが得意なんだね、へー……」




で?




de???




ってなりますよね。



そこでリバーシですよ

そこで「脱入門サイト」として、初心者はリバーシの実装をしてみるのがよいでしょう
理由としては以下の通りです
ボードゲームとしてシンプルで実装しやすい
・他のボードゲームへ応用しやすい
・繰り返し処理、二次元配列、(ちょっとした)アルゴリズムなどを実践的に学べる
・出来上がったもので遊べる(たのしい)

ボードクラスの実装

リバーシとは?
リバーシは8×8のマスが描かれた盆上に、白色の面と黒色の面を持つ平たい石を置くなどして、10分程度を浪費する遊戯です。「石」というのは正式名称らしいですが、本当に石を使っている商品を見たことがないと思いませんか。

さて、まずは使いそうな定数を定義します。
白手と黒手のプレイヤーを表現するためにWHITEと>BLACKを定義し、ボードの大きさをBOARD_SIZEとしました。中身はただの数字ですが、名前を付けることで用途が明示的になります。

WHITE = 0
BLACK = 1
BOARD_SIZE = 8

次にボードをクラスとして定義します。
マスは2次元配列(リスト)で表現することにして、初期値はすべてNoneとします。

class ReversiBoard(object):
    def __init__(self):
        # 2次元リストを生成する
        # 各要素の初期値はNone
        self.cells = []
        for i in range(BOARD_SIZE):
            self.cells.append([None for i in range(BOARD_SIZE)])

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


インスタンスを生成して、二次元リストが作られていることを確認してみます

>>> board = ReversiBoard()
>>> board.cells
[[None, None, None, None, None, None, None, None],
 [None, None, None, None, None, None, None, None],
 [None, None, None, None, None, None, None, None],
 [None, None, None, 0, 1, None, None, None],
 [None, None, None, 1, 0, None, None, None],
 [None, None, None, None, None, None, None, None],
 [None, None, None, None, None, None, None, None],
 [None, None, None, None, None, None, None, None]]

石を置くメソッド

さて、ボードができたので次に石を置くメソッドを作ります。
メソッド名はput_diskとします。x座標、y座標、石を置くプレイヤーの3つを引数に取ることにします。

class ReversiBoard(object):
    def put_disk(self, x, y, player):
        """指定した座標に指定したプレイヤーの石を置く
        Args:
            x: 置く石のX座標
            y: 置く石のY座標
            player: 石を置こうとしているプレイヤー(WHITEまたはBLACK)

        Returns:
            True: 関数の成功を意味する. 指定した座標と
                それによって獲得できる石がすべてplayerの色になった場合に返す
            False: 関数が以下のいずれかのケースによって失敗した場合に返す
                ・指定した座標に既に別の石がある
                ・指定した座標に石を置いても相手側の石を獲得できない
        """

        # 既にほかの石があれば置くことができない
        if self.cells[y][x] is not None:
            return False

        # 獲得できる石がない場合も置くことができない
        flippable = self.list_flippable_disks(x, y, player)
        if flippable == []:
            return False

        # 実際に石を置く処理
        self.cells[y][x] = player
        for x,y in flippable:
            self.cells[y][x] = player

        return True

多くの場合、座標を指定するときは(x, y)という形式にすると思うのですが、
self.cells[y][x]のようにY座標から先に指定しています。
これはself.cellsが[ボードの1行目のリスト、2行目の… N行目]というように
ボードの行を要素に持つリストであるためです。

このメソッドは成功したらTrue、失敗したらFalseを返すことにします。
置こうとしている位置に既にほかの石があれば、置くことができないのでメソッドは失敗です。Falseを返します。

self.list_flippable_disks(x, y, player)は次に実装するメソッドです。
このメソッドは「その石を置くことによってひっくりかえせる石のリスト」を返すことにしましょう。
そのリストが空であれば「ひっくりかえすことができる相手の石の数が0」ということなので、指定した場所に石を置くことはできません。Falseを返します。

実際に石を置く処理は、self.cellsの指定の位置に、プレイヤーの色を代入することにしました。
自分の石を置いたことによってひっくり返る、相手の石もここで更新します。


ひっくりかえせる石の数を列挙するメソッド

指定した座標にプレイヤーの石を置いた時、ひっくりかえせる石の座標をリストにして返します

class ReversiBoard(object):
    def list_flippable_disks(self, x, y, player):
        """指定した座標に指定したプレイヤーの石を置いた時、ひっくりかえせる全ての石の座標(タプル)をリストにして返す
        Args:
            x: x座標
            y: y座標
            player: 石を置こうとしているプレイヤー

        Returns:
            ひっくりかえすことができる全ての石の座標(タプル)のリスト
            または空リスト
        """

        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 < BOARD_SIZE and 0 <= ry < BOARD_SIZE:
                        request = self.cells[ry][rx]

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

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

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


DIRECTIONの中身は実際には[-1, 0, 1]というなんてことないリストです。
この値はそれぞれ負の方向、水平垂直、正の方向を表します。これらの組み合わせで図のように方向を決めます。
方向に距離をかけることで8方向への探査を実現しています。
f:id:katoh4u:20180322115258p:plain




if 0 <= rx < BOARD_SIZE and 0 <= ry < BOARD_SIZEの部分ですが、
if文の中は長くelseの中は一行となっています。そのため、条件を変えて以下のようにすると、インデントが深くなりすぎなくてよいのですが

if 0 > rx or rx >= BOARD_SIZE or 0 > ry or ry >= BOARD_SIZE:
    break


個人的には、元の条件式の書き方は図のように、数直線で考えられるので直感的で好きです。
f:id:katoh4u:20180322121126p:plain

ゲームにする

さて、基本的なシステムはほとんど出来ましたが
コマンドラインで操作できるゲームにするためには、
①ボードを文字で表示する
②プレイヤーが置くことができる石のリストを表示する
という機能があるとよいでしょう

    def show_board(self):
        """ボードを表示する"""
        print("--" * 20)
        for i in self.cells:
            for cell in i:
                if cell == WHITE:
                    print("W", end=" ")
                elif cell == BLACK:
                    print("B", end=" ")
                else:
                    print("*", end=" ")
            print("\n", end="")

すべてのマスを調べて、文字を表示するだけなのでむずかしくないですね



プレイヤーが置くことができるマスのリストを返すメソッドもすべてのマスに対してself.list_flippable_disksを呼ぶだけです。

    def list_possible_cells(self, player):
        """指定したプレイやーの石を置くことができる、すべてのマスの座標をリストにして返す
        Args:
            player: 石を置こうとしているプレイヤー

        Returns:
            石を置くことができるマスの座標のリスト
            または空リスト
        """

        possible = []
        for x in range(BOARD_SIZE):
            for y in range(BOARD_SIZE):
                if self.cells[y][x] is not None:
                    continue
                if self.list_flippable_disks(x, y, player) == []:
                    continue
                else:
                    possible.append((x, y))
        return possible

動くか試してみます

if __name__ == "__main__":
    board = ReversiBoard()
    board.show_board()
    board.put_disk(3, 2, BLACK)
    board.show_board()


以下のように表示されました。ちゃんと動いてますね。

----------------------------------------
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * W B * * *
* * * B W * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
----------------------------------------
* * * * * * * *
* * * * * * * *
* * * B * * * *
* * * B B * * *
* * * B W * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *

ゲームクラスをつくる

最後に、勝ち負けの判定や、プレイヤーの手番の管理などをGameというクラスにまとめましょう

ReversiBoardを継承して、いくつかのメソッドを追加します。リバーシのルールでは引き分けを認める場合と、あらかじめどちらかのプレイヤーに「石の数が同じだった場合に勝利する権利」を認める場合があります。今回は引き分けを認める実装にしました。その方が簡単なので。

class Game(ReversiBoard):
    DRAW = -1

    def __init__(self, turn=0, start_player=BLACK):
        super().__init__()
        self.player = start_player
        self.turn = turn
        self.winner = None
        self.was_passed = False

    def is_finished(self):
        return self.winner is not None

    def list_possible_cells(self):
        return super().list_possible_cells(self.player)

    def get_color(self, player):
        if player == WHITE:
            return "WHITE"
        if player == BLACK:
            return "BLACK"
        else:
            return "DRAW"

    def get_current_player(self):
        return self.player

    def get_next_player(self):
        return WHITE if self.player == BLACK else BLACK

    def shift_player(self):
        self.player = self.get_next_player()

    def put_disk(self, x, y):
        if super().put_disk(x, y, self.player):
            self.was_passed = False
            self.player = self.get_next_player()
            self.turn += 1
        else:
            return False

    def pass_moving(self):
        if self.was_passed:
            return self.finish_game()

        self.was_passed = True
        self.shift_player()

    def show_score(self):
        """それぞれのプレイヤーの石の数を表示する"""
        print("{}: {}".format("BLACK", self.disks[BLACK]))
        print("{}: {}".format("WHITE", self.disks[WHITE]))

    def finish_game(self):
        self.disks = self.get_disk_map()
        white = self.disks[WHITE]
        black =self.disks[BLACK]

        if white < black:
            self.winner = BLACK
        elif black < white:
            self.winner = WHITE
        else:
            self.winner = self.on_draw()

        return self.winner

    def on_draw(self):
        """ゲーム終了時に両社の石の数が同数だった時の処理
        デフォルトでは引き分けを認める
        """
        return self.DRAW


メインループはこんな感じにすれば一人二役の悲しいオセロゲームが出来上がりです。

if __name__ == "__main__":
    game = Game()
    while(True):
        possible = game.list_possible_cells()
        player_name = game.get_color(game.get_current_player())

        if game.is_finished():
            game.show_board()
            game.show_score()
            print("Winner: {}".format(game.get_color(game.winner)))
            break

        if possible == []:
            print("player {} can not puts.".format(player_name))
            game.pass_moving()
            continue

        game.show_board()
        print("player: " + player_name)
        print("put to: " + str(possible))
        index = int(input("choose: "))

        game.put_disk(*possible[index])


それでは皆さんよい一人オセロライフを。さよなら