首页 > 代码库 > 用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(井字游戏)