-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlab3.py
executable file
·249 lines (212 loc) · 10.4 KB
/
lab3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
# 6.034 Fall 2010 Lab 3: Games
# Name: < Atanu Ghosh, Bhargava Mourya >
# Email: < Atanu Ghosh <[email protected]>, Bhargava Mourya Venishetty <[email protected]> >
### 1. Multiple choice
# 1.1. Two computerized players are playing a game. Player MM does minimax
# search to depth 6 to decide on a move. Player AB does alpha-beta
# search to depth 6.
# The game is played without a time limit. Which player will play better?
#
# 1. MM will play better than AB.
# 2. AB will play better than MM.
# 3. They will play with the same level of skill.
ANSWER1 = 0
# 1.2. Two computerized players are playing a game with a time limit. Player MM
# does minimax search with iterative deepening, and player AB does alpha-beta
# search with iterative deepening. Each one returns a result after it has used
# 1/3 of its remaining time. Which player will play better?
#
# 1. MM will play better than AB.
# 2. AB will play better than MM.
# 3. They will play with the same level of skill.
ANSWER2 = 0
### 2. Connect Four
from connectfour import *
from basicplayer import *
from util import *
import tree_searcher
## This section will contain occasional lines that you can uncomment to play
## the game interactively. Be sure to re-comment them when you're done with
## them. Please don't turn in a problem set that sits there asking the
## grader-bot to play a game!
##
## Uncomment this line to play a game as white:
#run_game(human_player, basic_player)
## Uncomment this line to play a game as black:
#run_game(human_player, basic_player)
#run_game(basic_player, random_player)
#run_game(basic_player, random_player)
## Or watch the computer play against itself:
#run_game(basic_player, basic_player)
run_game(basic_player, new_player)
from basicplayer import nodes_expanded
print "Nodes Expanded for Minimax: " + str(nodes_expanded)
## Change this evaluation function so that it tries to win as soon as possible,
## or lose as late as possible, when it decides t,hat one side is certain to win.
## You don't have to change how it evaluates non-winning positions.
def focused_evaluate(board):
"""
Given a board, return a numeric rating of how good
that board is for the current player.
A return value >= 1000 means that the current player has won;
a return value <= -1000 means that the current player has lost
"""
raise NotImplementedError
## Create a "player" function that uses the focused_evaluate function
quick_to_win_player = lambda board: minimax(board, depth=4,
eval_fn=focused_evaluate)
## You can try out your new evaluation function by uncommenting this line:
#run_game(basic_player, quick_to_win_player)
nodes_expanded_alpha_beta = 0
def alpha_beta_search_util(board, depth, alpha, beta, is_max, eval_fn,
get_next_moves_fn=get_all_next_moves,
is_terminal_fn=is_terminal):
"""
Runs alpha beta search with pruning on the given board state and return a new board state and its evaluated value.
:param board:
:param depth: Depth till which the search must run
:param alpha:
:param beta:
:param is_max: Maximizing player
:param eval_fn: The evaluation function to use
:param get_next_moves_fn:
:param is_terminal_fn:
:return: (Evaluated value of the board, The board)
"""
global nodes_expanded_alpha_beta
if is_terminal_fn(depth, board):
# Return the evaluate function of the board and the board
return (eval_fn(board),board)
ret_board = board
if is_max == True:
value = NEG_INFINITY
legal_children = get_next_moves_fn(board)
for child in legal_children:
nodes_expanded_alpha_beta = nodes_expanded_alpha_beta + 1
ret_val = alpha_beta_search_util(child[1], depth-1, alpha, beta, False, eval_fn)
if (ret_val[0] > value):
value = ret_val[0]
ret_board = ret_val[1]
alpha = max(alpha, value)
if (beta <= alpha):
break # Beta cutoff
return (value, ret_board)
else:
value = INFINITY
legal_children = get_next_moves_fn(board)
for child in legal_children:
nodes_expanded_alpha_beta = nodes_expanded_alpha_beta + 1
ret_val = alpha_beta_search_util(child[1], depth-1, alpha, beta, True, eval_fn)
if (ret_val[0] < value):
value = ret_val[0]
ret_board = ret_val[1]
beta = min(beta, value)
if (beta <= alpha):
break # Alpha cutoff
return (value,ret_board)
## Write an alpha-beta-search procedure that acts like the minimax-search
## procedure, but uses alpha-beta pruning to avoid searching bad ideas
## that can't improve the result. The tester will check your pruning by
## counting the number of static evaluations you make.
##
## You can use minimax() in basicplayer.py as an example.
def alpha_beta_search(board, depth,
eval_fn,
# NOTE: You should use get_next_moves_fn when generating
# next board configurations, and is_terminal_fn when
# checking game termination.
# The default functions set here will work
# for connect_four.
get_next_moves_fn=get_all_next_moves,
is_terminal_fn=is_terminal):
(score, new_board) = alpha_beta_search_util(board, depth, NEG_INFINITY, INFINITY, True, eval_fn)
return get_diff_in_boards(board, new_board)
# raise NotImplementedError
## Now you should be able to search twice as deep in the same amount of time.
## (Of course, this alpha-beta-player won't work until you've defined
## alpha-beta-search.)
#alphabeta_player = lambda board: alpha_beta_search(board,
# depth=8,
# eval_fn=focused_evaluate)
alphabeta_player = lambda board: alpha_beta_search(board,
depth=4,
eval_fn=new_evaluate)
#alphabeta_player = lambda board: alpha_beta_search(board, depth = 8, eval_fn=new_evaluate)
#alphabeta_player = lambda board: alpha_beta_search(board, depth = 4, eval_fn=new_evaluate)
## This player uses progressive deepening, so it can kick your ass while
## making efficient use of time:
ab_iterative_player = lambda board: \
run_search_function(board,
search_fn=alpha_beta_search,
eval_fn=focused_evaluate, timeout=5)
#run_game(new_player, basic_player)
run_game(alphabeta_player, basic_player)
print "Nodes Expanded for Alpha-Beta: " + str(nodes_expanded_alpha_beta) # Prints for alpha beta
#run_game(alphabeta_player, random_player)
#run_game(human_player, alphabeta_player)
#run_game(human_player, alphabeta_player)
## Finally, come up with a better evaluation function than focused-evaluate.
## By providing a different function, you should be able to beat
## simple-evaluate (or focused-evaluate) while searching to the
## same depth.
#def better_evaluate(board):
# raise NotImplementedError
# Comment this line after you've fully implemented better_evaluate
better_evaluate = memoize(basic_evaluate)
# Uncomment this line to make your better_evaluate run faster.
# better_evaluate = memoize(better_evaluate)
# For debugging: Change this if-guard to True, to unit-test
# your better_evaluate function.
if False:
board_tuples = (( 0,0,0,0,0,0,0 ),
( 0,0,0,0,0,0,0 ),
( 0,0,0,0,0,0,0 ),
( 0,2,2,1,1,2,0 ),
( 0,2,1,2,1,2,0 ),
( 2,1,2,1,1,1,0 ),
)
test_board_1 = ConnectFourBoard(board_array = board_tuples,
current_player = 1)
test_board_2 = ConnectFourBoard(board_array = board_tuples,
current_player = 2)
# better evaluate from player 1
print "%s => %s" %(test_board_1, better_evaluate(test_board_1))
# better evaluate from player 2
print "%s => %s" %(test_board_2, better_evaluate(test_board_2))
## A player that uses alpha-beta and better_evaluate:
your_player = lambda board: run_search_function(board,
search_fn=alpha_beta_search,
eval_fn=better_evaluate,
timeout=5)
#your_player = lambda board: alpha_beta_search(board, depth=4,
# eval_fn=better_evaluate)
## Uncomment to watch your player play a game:
#run_game(your_player, your_player)
## Uncomment this (or run it in the command window) to see how you do
## on the tournament that will be graded.
#run_game(your_player, basic_player)
## These three functions are used by the tester; please don't modify them!
def run_test_game(player1, player2, board):
assert isinstance(globals()[board], ConnectFourBoard), "Error: can't run a game using a non-Board object!"
return run_game(globals()[player1], globals()[player2], globals()[board])
def run_test_search(search, board, depth, eval_fn):
assert isinstance(globals()[board], ConnectFourBoard), "Error: can't run a game using a non-Board object!"
return globals()[search](globals()[board], depth=depth,
eval_fn=globals()[eval_fn])
## This function runs your alpha-beta implementation using a tree as the search
## rather than a live connect four game. This will be easier to debug.
def run_test_tree_search(search, board, depth):
return globals()[search](globals()[board], depth=depth,
eval_fn=tree_searcher.tree_eval,
get_next_moves_fn=tree_searcher.tree_get_next_move,
is_terminal_fn=tree_searcher.is_leaf)
## Do you want us to use your code in a tournament against other students? See
## the description in the problem set. The tournament is completely optional
## and has no effect on your grade.
COMPETE = (None)
## The standard survey questions.
HOW_MANY_HOURS_THIS_PSET_TOOK = "14 hrs"
WHAT_I_FOUND_INTERESTING = "Implementation of minimax and alpha beta from scratch was a great learning experience."
WHAT_I_FOUND_BORING = "Project adapted from MIT. Lots of redundant functions, comments and files"
NAME = "Atanu Ghosh, Bhargava Mourya Venishetty"
EMAIL = "[email protected], [email protected]"