python 翻转棋(othello)

简介: 利用上一篇的框架,再写了个翻转棋的程序,为了调试minimax算法,花了两天的时间。几点改进说明:拆分成四个文件:board.py,player.py,ai.py,othello.py。使得整个结构更清晰,更通用,更易于维护。

利用上一篇的框架,再写了个翻转棋的程序,为了调试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()

效果图

img_0f669813db9f1a3f6c28da3521f3702d.jpg

目录
相关文章
|
7月前
|
Python
26: 翻转数的和(python)
26: 翻转数的和(python)
|
7月前
|
程序员 数据安全/隐私保护 Python
Python:翻转字符串
Python:翻转字符串
|
4月前
|
Python
【Leetcode刷题Python】25.K 个一组翻转链表
解决LeetCode "K 个一组翻转链表" 问题的三种方法:使用栈、尾插法和虚拟节点顺序法,并提供了每种方法的Python实现代码。
36 0
|
7月前
|
C++ Python Java
Java每日一练(20230501) 路径交叉、环形链表、被围绕的区域
Java每日一练(20230501) 路径交叉、环形链表、被围绕的区域
61 0
Java每日一练(20230501) 路径交叉、环形链表、被围绕的区域
|
6月前
|
存储 机器学习/深度学习 算法
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
|
6月前
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
40 1
|
6月前
|
Python
python之列表添加、修改、删除、插入、翻转、排序、复制排序
python之列表添加、修改、删除、插入、翻转、排序、复制排序
|
6月前
|
算法 数据挖掘 Python
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
|
7月前
|
Shell Python
python|闲谈2048小游戏和数组的旋转及翻转和转置
python|闲谈2048小游戏和数组的旋转及翻转和转置
76 1
|
7月前
|
Python Java Go
Python每日一练(20230430) 移除元素、删除排序链表中的重复元素、搜索旋转排序数组II
Python每日一练(20230430) 移除元素、删除排序链表中的重复元素、搜索旋转排序数组II
75 0
Python每日一练(20230430) 移除元素、删除排序链表中的重复元素、搜索旋转排序数组II