python 翻转棋（othello）

利用上一篇的框架，再写了个翻转棋的程序，为了调试minimax算法，花了两天的时间。

几点改进说明：

拆分成四个文件：board.py，player.py，ai.py，othello.py。使得整个结构更清晰，更通用，更易于维护。
AI 的水平跟 minimax 的递归深度，以及评价函数有关。基于此，我把 minimax 和评价函数都放到 AI 类里面
AIPlayer 使用了多重继承。继承了 Player 与 AI 两个类
Game 类中把原run函数里的生成两个玩家的部分提出来，写成一个函数make_two_players，使得 run函数结构更清晰
AI 玩家等级不要选择 0：beginer。会报错，还没调试好

board.py



'''

作者：hhh5460

时间：2017年7月1日

'''

class Board(object):

    def __init__(self):

        self.empty = '.'

        self._board = [[self.empty for _ in range(8)] for _ in range(8)] # 规格：8*8

        self._board[3][4], self._board[4][3] = 'X', 'X'

        self._board[3][3], self._board[4][4] = 'O', 'O'

    # 增加 Board[][] 索引语法

    def __getitem__(self, index):

        return self._board[index]

    # 打印棋盘

    def print_b(self):

        board = self._board

        print(' ', ' '.join(list('ABCDEFGH')))

        for i in range(8):

            print(str(i+1),' '.join(board[i]))

    # 棋局终止

    def teminate(self):

        list1 = list(self.get_legal_actions('X'))

        list2 = list(self.get_legal_actions('O'))

        return [False, True][len(list1) == 0 and len(list2) == 0]

    # 判断赢家

    def get_winner(self):

        s1, s2 = 0, 0

        for i in range(8):

            for j in range(8):

                if self._board[i][j] == 'X':

                    s1 += 1

                if self._board[i][j] == 'O':

                    s2 += 1

        if s1 > s2:

            return 0 # 黑胜

        elif s1 < s2:

            return 1 # 白胜

        elif s1 == s2:

            return 2 # 平局

    # 落子

    def _move(self, action, color):

        x,y = action

        self._board[x][y] = color

        return self._flip(action, color)

    # 翻子（返回list）

    def _flip(self, action, color):

        flipped_pos = []

        for line in self._get_lines(action):

            for i,p in enumerate(line):

                if self._board[p[0]][p[1]] == self.empty:

                    break

                elif self._board[p[0]][p[1]] == color:

                    flipped_pos.extend(line[:i])

                    break

        for p in flipped_pos:

            self._board[p[0]][p[1]] = color

        return flipped_pos

    # 撤销

    def _unmove(self, action, flipped_pos, color):

        self._board[action[0]][action[1]] = self.empty

        uncolor = ['X', 'O'][color=='X']

        for p in flipped_pos:

            self._board[p[0]][p[1]] = uncolor

    # 生成8个方向的下标数组，方便后续操作

    def _get_lines(self, action):

        '''说明：刚开始我是用一维棋盘来考虑的，后来改为二维棋盘。偷懒，不想推倒重来，简单地修改了一下'''

        board_coord = [(i,j) for i in range(8) for j in range(8)] # 棋盘坐标

        r,c = action

        ix = r*8 + c

        r, c = ix//8, ix%8

        left = board_coord[r*8:ix] # 要反转

        right = board_coord[ix+1:(r+1)*8]

        top = board_coord[c:ix:8] # 要反转

        bottom = board_coord[ix+8:8*8:8]

        if r <= c:

            lefttop = board_coord[c-r:ix:9] # 要反转

            rightbottom = board_coord[ix+9:(7-(c-r))*8+7+1:9]

        else:

            lefttop = board_coord[(r-c)*8:ix:9] # 要反转

            rightbottom = board_coord[ix+9:7*8+(7-(c-r))+1:9]

        if r+c<=7:

            leftbottom = board_coord[ix+7:(r+c)*8:7]

            righttop = board_coord[r+c:ix:7] # 要反转

        else:

            leftbottom = board_coord[ix+7:7*8+(r+c)-7+1:7]

            righttop = board_coord[((r+c)-7)*8+7:ix:7] # 要反转

        # 有四个要反转，方便判断

        left.reverse()

        top.reverse()

        lefttop.reverse()

        righttop.reverse()

        lines = [left, top, lefttop, righttop, right, bottom, leftbottom, rightbottom]

        return lines

    # 检测，位置是否有子可翻

    def _can_fliped(self, action, color):

        flipped_pos = []

        for line in self._get_lines(action):

            for i,p in enumerate(line):

                if self._board[p[0]][p[1]] == self.empty:

                    break

                elif self._board[p[0]][p[1]] == color:

                    flipped_pos.extend(line[:i])

                    break

        return [False, True][len(flipped_pos) > 0]

    # 合法走法

    def get_legal_actions(self, color):

        uncolor = ['X', 'O'][color=='X']

        uncolor_near_points = [] # 反色邻近的空位

        board = self._board

        for i in range(8):

            for j in range(8):

                if board[i][j] == uncolor:

                    for dx,dy in [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]:

                        x, y = i+dx, j+dy

                        if 0 <= x <=7 and 0 <= y <=7 and board[x][y] == self.empty and (x, y) not in uncolor_near_points:

                            uncolor_near_points.append((x, y))

        for p in uncolor_near_points:

            if self._can_fliped(p, color):

                yield p

# 测试

if __name__ == '__main__':

    board = Board()

    board.print_b()

    print(list(board.get_legal_actions('X')))

player.py



from ai import AI

'''

作者：hhh5460

时间：2017年7月1日

'''

# 玩家

class Player(object):

    def __init__(self, color):

        self.color = color

    # 思考

    def think(self, board):

        pass

    # 落子

    def move(self, board, action):

        flipped_pos = board._move(action, self.color)

        return flipped_pos

    # 悔子

    def unmove(self, board, action, flipped_pos):

        board._unmove(action, flipped_pos, self.color)

# 人类玩家

class HumanPlayer(Player):

    def __init__(self, color):

        super().__init__(color)

    def think(self, board):

        while True:

            action = input("Turn to '{}'. \nPlease input a point.(such as 'A1'): ".format(self.color)) # A1~H8

            r, c = action[1], action[0].upper()

            if  r in '12345678' and c in 'ABCDEFGH': # 合法性检查1

                x, y = '12345678'.index(r), 'ABCDEFGH'.index(c)

                if (x,y) in board.get_legal_actions(self.color):  # 合法性检查2

                    return x, y

# 电脑玩家（多重继承）

class AIPlayer(Player, AI):

    def __init__(self, color, level_ix=0):

        super().__init__(color)              # init Player

        super(Player, self).__init__(level_ix)  # init AI

    def think(self, board):

        print("Turn to '{}'. \nPlease wait a moment. AI is thinking...".format(self.color))

        uncolor = ['X','O'][self.color=='X']

        opfor = AIPlayer(uncolor) # 假想敌，陪练

        action = self.brain(board, opfor, 4)

        return action

ai.py



import random

'''

作者：hhh5460

时间：2017年7月1日

'''

class AI(object):

    '''

    三个水平等级：初级（beginner）、中级（intermediate）、高级（advanced）

    '''

    def __init__(self, level_ix =0):

        # 玩家等级

        self.level = ['beginner','intermediate','advanced'][level_ix]

        # 棋盘位置权重，参考：https://github.com/k-time/ai-minimax-agent/blob/master/ksx2101.py

        self.board_weights = [

            [120, -20,  20,   5,   5,  20, -20, 120],

            [-20, -40,  -5,  -5,  -5,  -5, -40, -20],

            [ 20,  -5,  15,   3,   3,  15,  -5,  20],

            [  5,  -5,   3,   3,   3,   3,  -5,   5],

            [  5,  -5,   3,   3,   3,   3,  -5,   5],

            [ 20,  -5,  15,   3,   3,  15,  -5,  20],

            [-20, -40,  -5,  -5,  -5,  -5, -40, -20],

            [120, -20,  20,   5,   5,  20, -20, 120]

        ]

    # 评估函数（仅根据棋盘位置权重）

    def evaluate(self, board, color):

        uncolor = ['X','O'][color=='X']

        score = 0

        for i in range(8):

            for j in range(8):

                if board[i][j] == color:

                    score += self.board_weights[i][j]

                elif board[i][j] == uncolor:

                    score -= self.board_weights[i][j]

        return score

    # AI的大脑

    def brain(self, board, opponent, depth):

        if self.level == 'beginer':         # 初级水平

            _, action = self.randomchoice(board)

        elif self.level == 'intermediate':  # 中级水平

            _, action = self.minimax(board, opponent, depth)

        elif self.level == 'advanced':      # 高级水平

            _, action = self.minimax_alpha_beta(board, opponent, depth)

        assert action is not None, 'action is None'

        return action

    # 随机选（从合法走法列表中随机选）

    def randomchoice(self, board):

        color = self.color

        action_list = list(board.get_legal_actions(color))

        return None, random.choice(action_list)

    # 极大极小算法，限制深度

    def minimax(self, board, opfor, depth=4): # 其中 opfor 是假想敌、陪练

        '''参考：https://github.com/k-time/ai-minimax-agent/blob/master/ksx2101.py'''

        color = self.color

        if depth == 0:

            return self.evaluate(board, color), None

        action_list = list(board.get_legal_actions(color))

        if not action_list:

            return self.evaluate(board, color), None

        best_score = -100000

        best_action = None

        for action in action_list:

            flipped_pos = self.move(board, action) # 落子

            score, _ = opfor.minimax(board, self, depth-1) # 深度优先，轮到陪练

            self.unmove(board, action, flipped_pos) # 回溯

            score = -score

            if score > best_score:

                best_score = score

                best_action = action

        return best_score, best_action

    # 极大极小算法，带alpha-beta剪枝

    def minimax_alpha_beta(self, board, opfor, depth=8, my_best=-float('inf'), opp_best=float('inf')):

        '''参考：https://github.com/k-time/ai-minimax-agent/blob/master/ksx2101.py'''

        color = self.color

        if depth == 0:

            return self.evaluate(board, color), None

        action_list = list(board.get_legal_actions(color))

        if not action_list:

            return self.evaluate(board, color), None

        best_score = my_best

        best_action = None

        for action in action_list:

            flipped_pos = self.move(board, action)  # 落子

            score, _ = opfor.minimax_alpha_beta(board, self, depth-1, -opp_best, -best_score) # 深度优先，轮到陪练

            self.unmove(board, action, flipped_pos) # 回溯

            score = -score

            if score > best_score:

                best_score = score

                best_action = action

            if best_score > opp_best:

                break

        return best_score, best_action

othello.py



from board import Board

from player import HumanPlayer, AIPlayer

'''

作者：hhh5460

时间：2017年7月1日

'''

# 游戏

class Game(object):

    def __init__(self):

        self.board = Board()

        self.current_player = None

    # 生成两个玩家

    def make_two_players(self):

        ps = input("Please select two player's type:\n\t0.Human\n\t1.AI\nSuch as:0 0\n:")

        p1, p2 = [int(p) for p in ps.split(' ')]

        if p1 == 1 or p2 == 1: # 至少有一个AI玩家

            level_ix = int(input("Please select the level of AI player.\n\t0: beginner\n\t1: intermediate\n\t2: advanced\n:"))

            if p1 == 0:

                player1 = HumanPlayer('X')

                player2 = AIPlayer('O', level_ix)

            elif p2 == 0:

                player1 = AIPlayer('X', level_ix)

                player2 = HumanPlayer('O')

            else:

                player1 = AIPlayer('X', level_ix)

                player2 = AIPlayer('O', level_ix)

        else:

            player1, player2 = HumanPlayer('X'), HumanPlayer('O') # 先手执X，后手执O

        return player1, player2

    # 切换玩家（游戏过程中）

    def switch_player(self, player1, player2):

        if self.current_player is None:

            return player1

        else:

            return [player1, player2][self.current_player == player1]

    # 打印赢家

    def print_winner(self, winner): # winner in [0,1,2]

        print(['Winner is player1','Winner is player2','Draw'][winner])

    # 运行游戏

    def run(self):

        # 生成两个玩家

        player1, player2 = self.make_two_players()

        # 游戏开始

        print('\nGame start!\n')

        self.board.print_b() # 显示棋盘

        while True:

            self.current_player = self.switch_player(player1, player2) # 切换当前玩家

            action = self.current_player.think(self.board) # 当前玩家对棋盘进行思考后，得到招法

            if action is not None:

                self.current_player.move(self.board, action)   # 当前玩家执行招法，改变棋盘

            self.board.print_b() # 显示当前棋盘

            if self.board.teminate(): # 根据当前棋盘，判断棋局是否终止

                winner = self.board.get_winner() # 得到赢家 0,1,2

                break

        self.print_winner(winner)

        print('Game over!')

        self.board.print_history()

if __name__ == '__main__':

    Game().run()

巴特西

python 翻转棋（othello）

几点改进说明：

board.py

player.py

ai.py

othello.py

效果图

最新文章

热门文章