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()
效果图
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
赞 (0)