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()