首页 > 代码库 > 用python实现Monte Carlo Tic-Tac-Toe(井字游戏)
用python实现Monte Carlo Tic-Tac-Toe(井字游戏)
1 """ 2 Monte Carlo Tic-Tac-Toe Player
@author dark_guard 3 """ 4 5 import random 6 import poc_ttt_gui 7 import poc_ttt_provided as provided 8 9 # Constants for Monte Carlo simulator 10 # Change as desired 11 NTRIALS = 20 # Number of trials to run 12 MCMATCH = 3.0 # Score for squares played by the machine player 13 MCOTHER = 2.0 # Score for squares played by the other player 14 15 # Add your functions here. 16 class Scores: 17 """ 18 # use this class to keep track of scores 19 """ 20 def __init__(self,board): 21 self._score = [[0 for dummy_row in range(board.get_dim())] for dummy_col in range(board.get_dim())] 22 def __str__(self): 23 return self._score 24 def set_score(self,board): 25 """ 26 # set scores 27 """ 28 for dummy_row in range(board.get_dim()): 29 for dummy_col in range(board.get_dim()): 30 self._score[dummy_row][dummy_col] = board.square(dummy_row,dummy_col) 31 32 33 def get_score(self): 34 """ 35 # use this class to keep track of scores 36 """ 37 return self._score 38 39 def mc_trial(board, player): 40 """ 41 # This function takes a current board 42 # and the next player to move 43 """ 44 45 while True: 46 row = random.choice(range(board.get_dim())) 47 col = random.choice(range(board.get_dim())) 48 if board.square(row,col) == provided.EMPTY: 49 board.move(row,col,player) 50 player = provided.switch_player(player) 51 52 if (board.check_win() != None): 53 break 54 return None 55 56 57 58 def mc_update_scores(scores, board, player): 59 """ 60 # The function should score the completed board 61 # and update the scores grid. 62 # As the function updates the scores grid directly 63 """ 64 65 for dummy_row in range(board.get_dim()): 66 for dummy_col in range(board.get_dim()): 67 if board.check_win() == player: 68 if (board.square(dummy_row,dummy_col) == player): 69 scores[dummy_row][dummy_col] += MCMATCH 70 elif (board.square(dummy_row,dummy_col) == provided.switch_player(player)): 71 scores[dummy_row][dummy_col] -= MCOTHER 72 73 if board.check_win() == provided.switch_player(player): 74 if (board.square(dummy_row,dummy_col) == player): 75 scores[dummy_row][dummy_col] -= MCMATCH 76 elif (board.square(dummy_row,dummy_col) == provided.switch_player(player)): 77 scores[dummy_row][dummy_col] += MCOTHER 78 79 80 81 82 def get_best_move(board, scores): 83 """ 84 # The function find all of the empty squares with the maximum score 85 # and randomly return one of them as a (row, column) tuple 86 """ 87 88 mlst =[] 89 for dummy_row in range(board.get_dim()): 90 for dummy_col in range(board.get_dim()): 91 if (board.square(dummy_row,dummy_col) == provided.EMPTY): 92 mlst.append(scores[dummy_row][dummy_col]) 93 94 big_score = max(mlst) 95 bigtemp_ls = [] 96 smtemp_ls = [] 97 for dummy_row in range(board.get_dim()): 98 for dummy_col in range(board.get_dim()): 99 if (board.square(dummy_row,dummy_col) == provided.EMPTY) and (scores[dummy_row][dummy_col] == big_score):100 bigtemp_ls.append((dummy_row, dummy_col))101 elif (board.square(dummy_row,dummy_col) == provided.EMPTY) and (scores[dummy_row][dummy_col] != big_score):102 smtemp_ls.append((dummy_row, dummy_col))103 104 if len(bigtemp_ls) > 0:105 return random.choice(bigtemp_ls)106 else:107 return random.choice(smtemp_ls)108 109 110 def mc_move(board, player, trials):111 """112 # The function should use the Monte Carlo simulation 113 # return a move for the machine player in the form of a (row, column) tuple114 """115 myboard = board.clone()116 myscores = Scores(myboard)117 118 while trials > 0:119 120 mc_trial(myboard,player)121 if myboard.check_win() == player:122 mc_update_scores(myscores.get_score(),myboard,player) 123 124 elif myboard.check_win() == provided.switch_player(player):125 mc_update_scores(myscores.get_score(),myboard,(provided.switch_player(player))) 126 trials -= 1127 myboard = board.clone()128 129 return get_best_move(board, myscores.get_score())130 131 132 133 134 135 # Test game with the console or the GUI.136 # Uncomment whichever you prefer.137 # Both should be commented out when you submit for138 # testing to save time.139 140 provided.play_game(mc_move, NTRIALS, False) 141 poc_ttt_gui.run_gui(3, provided.PLAYERX, mc_move, NTRIALS, False)
1 """ 2 poc_ttt_provided.py 3 Provided Code for Tic-Tac-Toe 4 @author Rice university 5 """ 6 7 # Constants 8 EMPTY = 1 9 PLAYERX = 2 10 PLAYERO = 3 11 DRAW = 4 12 13 # Map player constants to letters for printing 14 STRMAP = {EMPTY: " ", 15 PLAYERX: "X", 16 PLAYERO: "O"} 17 18 class TTTBoard: 19 """ 20 Class to represent a Tic-Tac-Toe board. 21 """ 22 23 def __init__(self, dim, reverse = False, board = None): 24 self._dim = dim 25 self._reverse = reverse 26 if board == None: 27 # Create empty board 28 self._board = [[EMPTY for dummycol in range(dim)] 29 for dummyrow in range(dim)] 30 else: 31 # Copy board grid 32 self._board = [[board[row][col] for col in range(dim)] 33 for row in range(dim)] 34 35 def __str__(self): 36 """ 37 Human readable representation of the board. 38 """ 39 rep = "" 40 for row in range(self._dim): 41 for col in range(self._dim): 42 rep += STRMAP[self._board[row][col]] 43 if col == self._dim - 1: 44 rep += "\n" 45 else: 46 rep += " | " 47 if row != self._dim - 1: 48 rep += "-" * (4 * self._dim - 3) 49 rep += "\n" 50 return rep 51 52 def get_dim(self): 53 """ 54 Return the dimension of the board. 55 """ 56 return self._dim 57 58 def square(self, row, col): 59 """ 60 Return the status (EMPTY, PLAYERX, PLAYERO) of the square at 61 position (row, col). 62 """ 63 return self._board[row][col] 64 65 def get_empty_squares(self): 66 """ 67 Return a list of (row, col) tuples for all empty squares 68 """ 69 empty = [] 70 for row in range(self._dim): 71 for col in range(self._dim): 72 if self._board[row][col] == EMPTY: 73 empty.append((row, col)) 74 return empty 75 76 def move(self, row, col, player): 77 """ 78 Place player on the board at position (row, col). 79 80 Does nothing if board square is not empty. 81 """ 82 if self._board[row][col] == EMPTY: 83 self._board[row][col] = player 84 85 def check_win(self): 86 """ 87 If someone has won, return player. 88 If game is a draw, return DRAW. 89 If game is in progress, return None. 90 """ 91 lines = [] 92 93 # rows 94 lines.extend(self._board) 95 96 # cols 97 cols = [[self._board[rowidx][colidx] for rowidx in range(self._dim)] 98 for colidx in range(self._dim)] 99 lines.extend(cols)100 101 # diags102 diag1 = [self._board[idx][idx] for idx in range(self._dim)]103 diag2 = [self._board[idx][self._dim - idx -1] 104 for idx in range(self._dim)]105 lines.append(diag1)106 lines.append(diag2)107 108 # check all lines109 for line in lines:110 if len(set(line)) == 1 and line[0] != EMPTY:111 if self._reverse:112 return switch_player(line[0])113 else:114 return line[0]115 116 # no winner, check for draw117 if len(self.get_empty_squares()) == 0:118 return DRAW119 120 # game is still in progress121 return None122 123 def clone(self):124 """125 Return a copy of the board.126 """127 return TTTBoard(self._dim, self._reverse, self._board)128 129 def switch_player(player):130 """131 Convenience function to switch players.132 133 Returns other player.134 """135 if player == PLAYERX:136 return PLAYERO137 else:138 return PLAYERX139 140 def play_game(mc_move_function, ntrials, reverse = False):141 """142 Function to play a game with two MC players.143 """144 # Setup game145 board = TTTBoard(3, reverse)146 curplayer = PLAYERX147 winner = None148 149 # Run game150 while winner == None:151 # Move152 row, col = mc_move_function(board, curplayer, ntrials)153 board.move(row, col, curplayer)154 155 # Update state156 winner = board.check_win()157 curplayer = switch_player(curplayer)158 159 # Display board160 print board161 print162 163 # Print winner164 if winner == PLAYERX:165 print "X wins!"166 elif winner == PLAYERO:167 print "O wins!"168 elif winner == DRAW:169 print "Tie!"170 else:171 print "Error: unknown winner"
1 """ 2 poc_ttt_gui.pu 3 Tic Tac Toe GUI code. 4 @Author Rice University 5 """ 6 7 import simplegui 8 import poc_ttt_provided as provided 9 10 GUI_WIDTH = 400 11 GUI_HEIGHT = GUI_WIDTH 12 BAR_WIDTH = 5 13 14 class TicTacGUI: 15 """ 16 GUI for Tic Tac Toe game. 17 """ 18 19 def __init__(self, size, aiplayer, aifunction, ntrials, reverse = False): 20 # Game board 21 self._size = size 22 self._bar_spacing = GUI_WIDTH // self._size 23 self._turn = provided.PLAYERX 24 self._reverse = reverse 25 26 # AI setup 27 self._humanplayer = provided.switch_player(aiplayer) 28 self._aiplayer = aiplayer 29 self._aifunction = aifunction 30 self._ntrials = ntrials 31 32 # Set up data structures 33 self.setup_frame() 34 35 # Start new game 36 self.newgame() 37 38 def setup_frame(self): 39 """ 40 Create GUI frame and add handlers. 41 """ 42 self._frame = simplegui.create_frame("Tic-Tac-Toe", 43 GUI_WIDTH, 44 GUI_HEIGHT) 45 self._frame.set_canvas_background(‘White‘) 46 47 # Set handlers 48 self._frame.set_draw_handler(self.draw) 49 self._frame.set_mouseclick_handler(self.click) 50 self._frame.add_button("New Game", self.newgame) 51 self._label = self._frame.add_label("") 52 53 def start(self): 54 """ 55 Start the GUI. 56 """ 57 self._frame.start() 58 59 def newgame(self): 60 """ 61 Start new game. 62 """ 63 self._board = provided.TTTBoard(self._size, self._reverse) 64 self._inprogress = True 65 self._wait = False 66 self._turn = provided.PLAYERX 67 self._label.set_text("") 68 69 def drawx(self, canvas, pos): 70 """ 71 Draw an X on the given canvas at the given position. 72 """ 73 halfsize = .4 * self._bar_spacing 74 canvas.draw_line((pos[0]-halfsize, pos[1]-halfsize), 75 (pos[0]+halfsize, pos[1]+halfsize), 76 BAR_WIDTH, ‘Black‘) 77 canvas.draw_line((pos[0]+halfsize, pos[1]-halfsize), 78 (pos[0]-halfsize, pos[1]+halfsize), 79 BAR_WIDTH, ‘Black‘) 80 81 def drawo(self, canvas, pos): 82 """ 83 Draw an O on the given canvas at the given position. 84 """ 85 halfsize = .4 * self._bar_spacing 86 canvas.draw_circle(pos, halfsize, BAR_WIDTH, ‘Black‘) 87 88 def draw(self, canvas): 89 """ 90 Updates the tic-tac-toe GUI. 91 """ 92 # Draw the ‘#‘ symbol 93 for bar_start in range(self._bar_spacing, 94 GUI_WIDTH - 1, 95 self._bar_spacing): 96 canvas.draw_line((bar_start, 0), 97 (bar_start, GUI_HEIGHT), 98 BAR_WIDTH, 99 ‘Black‘)100 canvas.draw_line((0, bar_start),101 (GUI_WIDTH, bar_start),102 BAR_WIDTH,103 ‘Black‘)104 105 # Draw the current players‘ moves106 for row in range(self._size):107 for col in range(self._size):108 symbol = self._board.square(row, col)109 coords = self.get_coords_from_grid(row, col)110 if symbol == provided.PLAYERX:111 self.drawx(canvas, coords)112 elif symbol == provided.PLAYERO:113 self.drawo(canvas, coords)114 115 # Run AI, if necessary116 if not self._wait:117 self.aimove()118 else:119 self._wait = False120 121 def click(self, position):122 """123 Make human move.124 """125 if self._inprogress and (self._turn == self._humanplayer): 126 row, col = self.get_grid_from_coords(position)127 if self._board.square(row, col) == provided.EMPTY:128 self._board.move(row, col, self._humanplayer)129 self._turn = self._aiplayer130 winner = self._board.check_win()131 if winner is not None:132 self.game_over(winner)133 self._wait = True134 135 def aimove(self):136 """137 Make AI move.138 """139 if self._inprogress and (self._turn == self._aiplayer):140 row, col = self._aifunction(self._board, 141 self._aiplayer, 142 self._ntrials)143 if self._board.square(row, col) == provided.EMPTY:144 self._board.move(row, col, self._aiplayer)145 self._turn = self._humanplayer146 winner = self._board.check_win()147 if winner is not None:148 self.game_over(winner) 149 150 def game_over(self, winner):151 """152 Game over153 """154 # Display winner155 if winner == provided.DRAW:156 self._label.set_text("It‘s a tie!")157 elif winner == provided.PLAYERX:158 self._label.set_text("X Wins!")159 elif winner == provided.PLAYERO:160 self._label.set_text("O Wins!") 161 162 # Game is no longer in progress163 self._inprogress = False164 165 def get_coords_from_grid(self, row, col):166 """167 Given a grid position in the form (row, col), returns168 the coordinates on the canvas of the center of the grid.169 """170 # X coordinate = (bar spacing) * (col + 1/2)171 # Y coordinate = height - (bar spacing) * (row + 1/2)172 return (self._bar_spacing * (col + 1.0/2.0), # x173 self._bar_spacing * (row + 1.0/2.0)) # y174 175 def get_grid_from_coords(self, position):176 """177 Given coordinates on a canvas, gets the indices of178 the grid.179 """180 posx, posy = position181 return (posy // self._bar_spacing, # row182 posx // self._bar_spacing) # col183 184 185 def run_gui(board_size, ai_player, ai_function, ntrials, reverse = False):186 """187 Instantiate and run the GUI188 """189 gui = TicTacGUI(board_size, ai_player, ai_function, ntrials, reverse)190 gui.start()
用python实现Monte Carlo Tic-Tac-Toe(井字游戏)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。