用python实现Monte Carlo Tic-Tac-Toe（井字游戏）

lidonghe

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) tuple
114     """
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 -= 1
127         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 for
138 # 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         # diags
102         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 lines
109         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 draw
117         if len(self.get_empty_squares()) == 0:
118             return DRAW
119
120         # game is still in progress
121         return None
122            
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 PLAYERO
137     else:
138         return PLAYERX
139
140 def play_game(mc_move_function, ntrials, reverse = False):
141     """
142     Function to play a game with two MC players.
143     """
144     # Setup game
145     board = TTTBoard(3, reverse)
146     curplayer = PLAYERX
147     winner = None
148     
149     # Run game
150     while winner == None:
151         # Move
152         row, col = mc_move_function(board, curplayer, ntrials)
153         board.move(row, col, curplayer)
154
155         # Update state
156         winner = board.check_win()
157         curplayer = switch_player(curplayer)
158
159         # Display board
160         print board
161         print
162         
163     # Print winner
164     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' moves
106         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 necessary
116         if not self._wait:
117             self.aimove()
118         else:
119             self._wait = False
120                 
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._aiplayer
130                 winner = self._board.check_win()
131                 if winner is not None:
132                     self.game_over(winner)
133                 self._wait = True
134                 
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._humanplayer
146             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 over
153         """
154         # Display winner
155         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 progress
163         self._inprogress = False
164
165     def get_coords_from_grid(self, row, col):
166         """
167         Given a grid position in the form (row, col), returns
168         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), # x
173                 self._bar_spacing * (row + 1.0/2.0)) # y
174     
175     def get_grid_from_coords(self, position):
176         """
177         Given coordinates on a canvas, gets the indices of
178         the grid.
179         """
180         posx, posy = position
181         return (posy // self._bar_spacing, # row
182                 posx // self._bar_spacing) # col
183
184
185 def run_gui(board_size, ai_player, ai_function, ntrials, reverse = False):
186     """
187     Instantiate and run the GUI
188     """
189     gui = TicTacGUI(board_size, ai_player, ai_function, ntrials, reverse)
190     gui.start()