Skip to content
Navigation Menu
{{ message }}
forked from aimacode/aima-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgames.py
More file actions
292 lines (242 loc) · 9.94 KB
/
Copy pathgames.py
File metadata and controls
292 lines (242 loc) · 9.94 KB
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
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
"""Games, or Adversarial Search. (Chapter 5)
"""
from utils import *
import random
#______________________________________________________________________________
# Minimax Search
def minimax_decision(state, game):
"""Given a state in a game, calculate the best move by searching
forward all the way to the terminal states. [Fig. 5.3]"""
player = game.to_move(state)
def max_value(state):
if game.terminal_test(state):
return game.utility(state, player)
v = -infinity
for a in game.actions(state):
v = max(v, min_value(game.result(state, a)))
return v
def min_value(state):
if game.terminal_test(state):
return game.utility(state, player)
v = infinity
for a in game.actions(state):
v = min(v, max_value(game.result(state, a)))
return v
# Body of minimax_decision:
return argmax(game.actions(state),
lambda a: min_value(game.result(state, a)))
#______________________________________________________________________________
def alphabeta_full_search(state, game):
"""Search game to determine best action; use alpha-beta pruning.
As in [Fig. 5.7], this version searches all the way to the leaves."""
player = game.to_move(state)
def max_value(state, alpha, beta):
if game.terminal_test(state):
return game.utility(state, player)
v = -infinity
for a in game.actions(state):
v = max(v, min_value(game.result(state, a), alpha, beta))
if v >= beta:
return v
alpha = max(alpha, v)
return v
def min_value(state, alpha, beta):
if game.terminal_test(state):
return game.utility(state, player)
v = infinity
for a in game.actions(state):
v = min(v, max_value(game.result(state, a), alpha, beta))
if v <= alpha:
return v
beta = min(beta, v)
return v
# Body of alphabeta_search:
return argmax(game.actions(state),
lambda a: min_value(game.result(state, a),
-infinity, infinity))
def alphabeta_search(state, game, d=4, cutoff_test=None, eval_fn=None):
"""Search game to determine best action; use alpha-beta pruning.
This version cuts off search and uses an evaluation function."""
player = game.to_move(state)
def max_value(state, alpha, beta, depth):
if cutoff_test(state, depth):
return eval_fn(state)
v = -infinity
for a in game.actions(state):
v = max(v, min_value(game.result(state, a),
alpha, beta, depth+1))
if v >= beta:
return v
alpha = max(alpha, v)
return v
def min_value(state, alpha, beta, depth):
if cutoff_test(state, depth):
return eval_fn(state)
v = infinity
for a in game.actions(state):
v = min(v, max_value(game.result(state, a),
alpha, beta, depth+1))
if v <= alpha:
return v
beta = min(beta, v)
return v
# Body of alphabeta_search starts here:
# The default test cuts off at depth d or at a terminal state
cutoff_test = (cutoff_test or
(lambda state,depth: depth>d or game.terminal_test(state)))
eval_fn = eval_fn or (lambda state: game.utility(state, player))
return argmax(game.actions(state),
lambda a: min_value(game.result(state, a),
-infinity, infinity, 0))
#______________________________________________________________________________
# Players for Games
def query_player(game, state):
"Make a move by querying standard input."
game.display(state)
return num_or_str(raw_input('Your move? '))
def random_player(game, state):
"A player that chooses a legal move at random."
return random.choice(game.actions(state))
def alphabeta_player(game, state):
return alphabeta_search(state, game)
def play_game(game, *players):
"""Play an n-person, move-alternating game.
>>> play_game(Fig52Game(), alphabeta_player, alphabeta_player)
3
"""
state = game.initial
while True:
for player in players:
move = player(game, state)
state = game.result(state, move)
if game.terminal_test(state):
return game.utility(state, game.to_move(game.initial))
#______________________________________________________________________________
# Some Sample Games
class Game:
"""A game is similar to a problem, but it has a utility for each
state and a terminal test instead of a path cost and a goal
test. To create a game, subclass this class and implement actions,
result, utility, and terminal_test. You may override display and
successors or you can inherit their default methods. You will also
need to set the .initial attribute to the initial state; this can
be done in the constructor."""
def actions(self, state):
"Return a list of the allowable moves at this point."
abstract
def result(self, state, move):
"Return the state that results from making a move from a state."
abstract
def utility(self, state, player):
"Return the value of this final state to player."
abstract
def terminal_test(self, state):
"Return True if this is a final state for the game."
return not self.actions(state)
def to_move(self, state):
"Return the player whose move it is in this state."
return state.to_move
def display(self, state):
"Print or otherwise display the state."
print state
def __repr__(self):
return '<%s>' % self.__class__.__name__
class Fig52Game(Game):
"""The game represented in [Fig. 5.2]. Serves as a simple test case.
>>> g = Fig52Game()
>>> minimax_decision('A', g)
'a1'
>>> alphabeta_full_search('A', g)
'a1'
>>> alphabeta_search('A', g)
'a1'
"""
succs = dict(A=dict(a1='B', a2='C', a3='D'),
B=dict(b1='B1', b2='B2', b3='B3'),
C=dict(c1='C1', c2='C2', c3='C3'),
D=dict(d1='D1', d2='D2', d3='D3'))
utils = Dict(B1=3, B2=12, B3=8, C1=2, C2=4, C3=6, D1=14, D2=5, D3=2)
initial = 'A'
def actions(self, state):
return self.succs.get(state, {}).keys()
def result(self, state, move):
return self.succs[state][move]
def utility(self, state, player):
if player == 'MAX':
return self.utils[state]
else:
return -self.utils[state]
def terminal_test(self, state):
return state not in ('A', 'B', 'C', 'D')
def to_move(self, state):
return if_(state in 'BCD', 'MIN', 'MAX')
class TicTacToe(Game):
"""Play TicTacToe on an h x v board, with Max (first player) playing 'X'.
A state has the player to move, a cached utility, a list of moves in
the form of a list of (x, y) positions, and a board, in the form of
a dict of {(x, y): Player} entries, where Player is 'X' or 'O'."""
def __init__(self, h=3, v=3, k=3):
update(self, h=h, v=v, k=k)
moves = [(x, y) for x in range(1, h+1)
for y in range(1, v+1)]
self.initial = Struct(to_move='X', utility=0, board={}, moves=moves)
def actions(self, state):
"Legal moves are any square not yet taken."
return state.moves
def result(self, state, move):
if move not in state.moves:
return state # Illegal move has no effect
board = state.board.copy(); board[move] = state.to_move
moves = list(state.moves); moves.remove(move)
return Struct(to_move=if_(state.to_move == 'X', 'O', 'X'),
utility=self.compute_utility(board, move, state.to_move),
board=board, moves=moves)
def utility(self, state, player):
"Return the value to player; 1 for win, -1 for loss, 0 otherwise."
return if_(player == 'X', state.utility, -state.utility)
def terminal_test(self, state):
"A state is terminal if it is won or there are no empty squares."
return state.utility != 0 or len(state.moves) == 0
def display(self, state):
board = state.board
for x in range(1, self.h+1):
for y in range(1, self.v+1):
print board.get((x, y), '.'),
print
def compute_utility(self, board, move, player):
"If X wins with this move, return 1; if O return -1; else return 0."
if (self.k_in_row(board, move, player, (0, 1)) or
self.k_in_row(board, move, player, (1, 0)) or
self.k_in_row(board, move, player, (1, -1)) or
self.k_in_row(board, move, player, (1, 1))):
return if_(player == 'X', +1, -1)
else:
return 0
def k_in_row(self, board, move, player, (delta_x, delta_y)):
"Return true if there is a line through move on board for player."
x, y = move
n = 0 # n is number of moves in row
while board.get((x, y)) == player:
n += 1
x, y = x + delta_x, y + delta_y
x, y = move
while board.get((x, y)) == player:
n += 1
x, y = x - delta_x, y - delta_y
n -= 1 # Because we counted move itself twice
return n >= self.k
class ConnectFour(TicTacToe):
"""A TicTacToe-like game in which you can only make a move on the bottom
row, or in a square directly above an occupied square. Traditionally
played on a 7x6 board and requiring 4 in a row."""
def __init__(self, h=7, v=6, k=4):
TicTacToe.__init__(self, h, v, k)
def actions(self, state):
return [(x, y) for (x, y) in state.moves
if y == 0 or (x, y-1) in state.board]
__doc__ += random_tests("""
>>> play_game(Fig52Game(), random_player, random_player)
6
>>> play_game(TicTacToe(), random_player, random_player)
0
""")
You can’t perform that action at this time.