俺の備忘録

個人的な備忘録です。

Pythonの勉強がてらオセロAIを作ってみる①

はじめに

Alpha碁の活躍で機械学習が一気に有名になった。
恥ずかしながら、機械学習について全く知らない。 調べてみると、機械学習のライブラリはPythonが充実しているらしい。

そこで、Pythonの勉強がてら機械学習なるものを勉強してみる。 題材としてはオセロを選んでみた。 ちなみにPythonも初だし、AIも初なので上手く行くかは未知数。 ただいきなり機械学習なんて無理だと思うので、 まずは機械学習なしのAI作成から始める。

大体以下の予定で進める予定。

  1. オセロの基本ロジックの実装
  2. 完全ランダムな手で打つAIの実装 <= 本稿はココ
  3. 今現在、最もたくさん石が取れる手を選ぶAIの実装
  4. ちょっとだけオセロの定石を知ってるAIの実装
  5. もうちょっとオセロの定石を知っているAIの実装
  6. MinMax法で打つAIの実装
  7. AlphaBeta法で打つAIの実装
  8. モンテカルロ法で打つAIの実装
  9. モンテカルロ木探索?で打つAIの実装
  10. (このあたりで機械学習を取り入れたい?)

オセロの基本ロジックの実装

基本ロジック

AIを作ったときに共通で使いそうなロジックをまとめたもの
ReverseCommon.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
import copy

# 定数
# 何も置かれていない
NONE = None
# 白
WHITE = False
# 黒
BLACK = True

# Common Functions


def get_score(board, color):
    """ 指定した色の現在のスコアを返す """
    score = 0
    for i in range(0, 8):
        for j in range(0, 8):
            if board[i][j] == color:
                score += 1
    return score


def get_remain(board):
    """ 何も置かれていない場所の数を返す """
    count = 0
    for i in range(0, 8):
        for j in range(0, 8):
            if board[i][j] is None:
                count += 1
    return count


def has_right_reversible_stone(board, i, j, color):
    """ 指定座標の右側に返せる石があるか調べる """
    enemy = not(bool(color))
    if j <= 5 and board[i][j+1] == enemy:
        for k in range(j + 2, 8):
            if board[i][k] == color:
                return True
            elif board[i][k] == NONE:
                break
    return False


def has_left_reversible_stone(board, i, j, color):
    """ 指定座標の左側に返せる石があるか調べる """
    enemy = not(bool(color))
    if j >=2 and board[i][j-1] == enemy:
        for k in range(j - 2, -1, -1):
            if board[i][k] == color:
                return True
            elif board[i][k] == NONE:
                break
    return False


def has_upper_reversible_stone(board, i, j, color):
    """ 指定座標の上に返せる石があるか調べる """
    enemy = not(bool(color))
    if i >= 2 and board[i-1][j] == enemy:
        for k in range(i - 2, -1, -1):
            if board[k][j] == color:
                return True
            elif board[k][j] == NONE:
                break
    return False


def has_lower_reversible_stone(board, i, j, color):
    """ 指定座標の下に返せる石があるか調べる """
    enemy = not(bool(color))
    if i <= 5 and board[i+1][j] == enemy:
        for k in range(i + 2, 8):
            if board[k][j] == color:
                return True
            elif board[k][j] == NONE:
                break
    return False


def has_right_upper_reversible_stone(board, i, j, color):
    """ 指定座標の右上に返せる石があるか調べる """
    enemy = not(bool(color))
    if i >= 2 and j <= 5 and board[i-1][j+1] == enemy:
        k = 2
        while i - k >= 0 and j + k < 8:
            if board[i-k][j+k] == color:
                return True
            elif board[i-k][j+k] == NONE:
                break
            k += 1
    return False


def has_left_lower_reversible_stone(board, i, j, color):
    """ 指定座標の左下に返せる石があるか調べる """
    enemy = not(bool(color))
    if j >= 2 and i <= 5 and board[i+1][j-1] == enemy:
        k = 2
        while i + k < 8 and j - k >= 0:
            if board[i+k][j-k] == color:
                return True
            elif board[i+k][j-k] == NONE:
                break
            k += 1
    return False


def has_left_upper_reversible_stone(board, i, j, color):
    """ 指定座標の左上に返せる石があるか調べる """
    enemy = not(bool(color))
    if i >= 2 and j >= 2 and board[i-1][j-1] == enemy:
        k = 2
        while i - k >= 0 and j - k >= 0:
            if board[i-k][j-k] == color:
                return True
            elif board[i-k][j-k] == NONE:
                break
            k += 1
    return False


def has_right_lower_reversible_stone(board, i, j, color):
    """ 指定座標の右下に返せる石があるか調べる """
    enemy = not(color)
    if i <= 5 and j <= 5 and board[i+1][j+1] == enemy:
        k = 2
        while i + k < 8 and j + k < 8:
            if board[i+k][j+k] == color:
                return True
            elif board[i+k][j+k] == NONE:
                break
            k += 1
    return False


def is_game_set(board):
    """ ゲーム終了か判定する """
    if len(get_puttable_points(board, WHITE)) == 0 and len(get_puttable_points(board, BLACK)) == 0:
        return True
    return False


def get_puttable_points(board, color):
    """ 指定した色が置ける座標をすべて返す """
    points = []
    for i in range(0, 8):
        for j in range(0, 8):
            if board[i][j] != NONE:
                # 何か置かれている場所はする
                continue

            # 左右に走査
            if has_right_reversible_stone(board, i, j, color) or has_left_reversible_stone(board, i, j, color):
                points.append([i, j])
                continue

            # 上下に走査
            if has_upper_reversible_stone(board, i, j, color) or has_lower_reversible_stone(board, i, j, color):
                points.append([i, j])
                continue

            # 右斜め上、左斜め下
            if has_right_upper_reversible_stone(board, i, j, color) or has_left_lower_reversible_stone(board, i, j, color):
                points.append([i, j])
                continue

            # 左上、右下
            if has_left_upper_reversible_stone(board, i, j, color) or has_right_lower_reversible_stone(board, i, j, color):
                points.append([i, j])
                continue
    return points


def put_stone(board, color, i, j):
    """ ひっくり返す """
    new_board = copy.deepcopy(board)

    # 右側をひっくり返しord[i][k] != color:
    if has_right_reversible_stone(new_board, i, j, color):
        k = j + 1
        while new_board[i][k] != color:
            new_board[i][k] = color
            k += 1

    # 左側をひっくり返していく
    if has_left_reversible_stone(new_board, i, j, color):
        k = j - 1
        while new_board[i][k] != color:
            new_board[i][k] = color
            k -= 1

    # 上側をひっくり返していく
    if has_upper_reversible_stone(new_board, i, j, color):
        k = i - 1
        while new_board[k][j] != color:
            new_board[k][j] = color
            k -= 1

    # 下側をひっくり返していく
    if has_lower_reversible_stone(new_board, i, j, color):
        k = i + 1
        while new_board[k][j] != color:
            new_board[k][j] = color
            k += 1

    # 右下をひっくりかえしていく
    if has_right_lower_reversible_stone(new_board, i, j, color):
        k = 1
        while new_board[i+k][j+k] != color:
            new_board[i+k][j+k] = color
            k += 1

    # 左上をひっくりかえしていく
    if has_left_upper_reversible_stone(new_board, i, j, color):
        k = 1
        while new_board[i-k][j-k] != color:
            new_board[i-k][j-k] = color
            k += 1

    # 右上をひっくりかえしていく
    if has_right_upper_reversible_stone(new_board, i, j, color):
        k = 1
        while new_board[i-k][j+k] != color:
            new_board[i-k][j+k] = color
            k += 1

    # 左下をひっくり返していく
    if has_left_lower_reversible_stone(new_board, i, j, color):
        k = 1
        while new_board[i+k][j-k] != color:
            new_board[i+k][j-k] = color
            k += 1

    new_board[i][j] = color
    return new_board


def print_board(board):
    """盤面表示"""
    print "   0 1 2 3 4 5 6 7"
    for i in range(0, 8):
        row = str(i) + " |"
        for j in range(0, 8):
            if board[i][j] == NONE:
                row += " "
            elif board[i][j] == WHITE:
                row += "W"
            else:
                row += "B"
            row += "|"
        print row
    print ""

盤面の状態や現在のターンを保存するために作ったクラス
ReverseBord.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
import ReverseCommon


class ReverseBoard:
    """ オセロ盤 """
    def __init__(self):
        """ Constructor """
        # ボード初期化
        self._board = [[ReverseCommon.NONE for i in range(8)] for j in range(8)]
        self._board[3][3] = ReverseCommon.WHITE
        self._board[4][4] = ReverseCommon.WHITE
        self._board[3][4] = ReverseCommon.BLACK
        self._board[4][3] = ReverseCommon.BLACK
        # 黒のターンに初期化
        self._turn = ReverseCommon.BLACK

    def change_turn(self):
        """ 交代 """
        if self._turn == ReverseCommon.WHITE:
            self._turn = ReverseCommon.BLACK
        else:
            self._turn = ReverseCommon.WHITE

    def put_stone(self, color, i, j):
        """ 置く & ひっくり返す """
        self._board = ReverseCommon.put_stone(self._board, color, i, j)

        # プレーヤ交代
        enemy = not(color)
        if len(ReverseCommon.get_puttable_points(self._board, enemy)) > 0:
            self.change_turn()

    def is_game_set(self):
        """ ゲームセットか返す """
        return ReverseCommon.is_game_set(self._board)

    def is_my_turn(self, color):
        """ 自分のターンか返す """
        if self._turn == color:
            return True
        return False

    @property
    def board(self):
        """ 盤面を返す"""
        return self._board


class CustomReverseBoard(ReverseBoard):
    """ 途中状態の盤面を作るようのクラス """
    def __init__(self, board, turn):
        self._board = board
        self._turn = turn

簡単なAIの実装

ランダムに手を選ぶAIの実装してみた

Player.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

import copy
import random
import ReverseCommon
import ReverseBoard
import Game


class Player:
    """ プレーヤの基盤クラス(AIも含む) """

    def __init__(self, color):
        """ コンストラクタ """
        self._color = color

    def next_move(self, board):
        """ 次の手を返す """
        pass

    @property
    def color(self):
        """ 自分の色を返す """
        return self._color


class RandomAi(Player):
"""ランダムで石を置くAI"""

def next_move(self, board):
    all_candidates = ReverseCommon.get_puttable_points(board, self._color)
    # ランダムで次の手を選ぶ
    index = random.randint(0, len(all_candidates) - 1)
    return all_candidates[index]

戦わせてみる

以下のコードで戦わせてみた。結果は
黒の勝数:1627
白の勝数:1373

少し先手(黒)の勝ちが多い。 まぁどう考えてもオセロは先手有利っぽそうなので、きっとそのせいだと思う。

プレーヤ(AI)を戦わせるクラス。 Game.py

##!/usr/bin/python
# -*- coding: utf-8 -*-

import ReverseCommon


class Game:
    """ オセロゲーム """
    def __init__(self, player1, player2, reverse_board):
        self._player1 = player1
        self._player2 = player2
        self._reverse_board = reverse_board

    def play(self, output_board):
        if output_board:
            ReverseCommon.print_board(self._reverse_board.board)

        # 勝負
        while True:
            # 置けなくなったら終了
            if self._reverse_board.is_game_set():
                break

            # プレーヤ1
            if self._reverse_board.is_my_turn(self._player1.color):
                next_move = self._player1.next_move(self._reverse_board.board)
                self._reverse_board.put_stone(self._player1.color, next_move[0], next_move[1])
                if output_board:
                    ReverseCommon.print_board(self._reverse_board.board)

            # 置けなくなったら終了
            if self._reverse_board.is_game_set():
                break

            # プレーヤ2
            if self._reverse_board.is_my_turn(self._player2.color):
                next_move = self._player2.next_move(self._reverse_board.board)
                self._reverse_board.put_stone(self._player2.color, next_move[0], next_move[1])
                if output_board:
                    ReverseCommon.print_board(self._reverse_board.board)

    def get_winner(self):
        # 勝者を返す
        player1_score = ReverseCommon.get_score(self._reverse_board.board, self._player1.color)
        player2_score = ReverseCommon.get_score(self._reverse_board.board, self._player2.color)

        if player1_score > player2_score:
            return self._player1
        else:
            return self._player2

メイン関数 Main.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

# Main function
import ReverseBoard
import Player
import ReverseCommon
import Game
import datetime

if __name__ == "__main__":
    # 勝利数
    black_win = 0
    white_win = 0

    # 試行回数
    times = 3000

    # 盤面を出力するか
    output = False

    print "start:", datetime.datetime.today()

    # 勝負
    for i in range(0, times):

        # 盤面作成
        reverse_board = ReverseBoard.ReverseBoard()

        # プレイヤー
        black_player = Player.RandomAi(ReverseCommon.BLACK)
        white_player = Player.RandomAi(ReverseCommon.WHITE)

        # ゲーム開始
        game = Game.Game(black_player, white_player, reverse_board)
        game.play(output)

        # 勝者判定
        if game.get_winner() == black_player:
            black_win += 1
        else:
            white_win += 1

    print "end", datetime.datetime.today()

    # 各AIの勝利数
    print "black:", black_win, ", white:", white_win