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
344 lines (273 loc) · 11.2 KB
/
Copy pathgames.py
File metadata and controls
344 lines (273 loc) · 11.2 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
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
"""Games, or Adversarial Search (Chapter 5)"""
from collections import namedtuple
import random
from utils import argmax
infinity = float('inf')
GameState = namedtuple('GameState', 'to_move, utility, board, moves')
# ______________________________________________________________________________
# 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. [Figure 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),
key=lambda a: min_value(game.result(state, a)))
# ______________________________________________________________________________
def alphabeta_search(state, game):
"""Search game to determine best action; use alpha-beta pruning.
As in [Figure 5.7], this version searches all the way to the leaves."""
player = game.to_move(state)
# Functions used by alphabeta
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_cutoff_search:
best_score = -infinity
beta = infinity
best_action = None
for a in game.actions(state):
v = min_value(game.result(state, a), best_score, beta)
if v > best_score:
best_score = v
best_action = a
return best_action
def alphabeta_cutoff_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)
# Functions used by alphabeta
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_cutoff_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))
best_score = -infinity
beta = infinity
best_action = None
for a in game.actions(state):
v = min_value(game.result(state, a), best_score, beta, 1)
if v > best_score:
best_score = v
best_action = a
return best_action
# ______________________________________________________________________________
# Players for Games
def query_player(game, state):
"""Make a move by querying standard input."""
print("current state:")
game.display(state)
print("available moves: {}".format(game.actions(state)))
print("")
move_string = input('Your move? ')
try:
move = eval(move_string)
except NameError:
move = move_string
return 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)
# ______________________________________________________________________________
# 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."""
raise NotImplementedError
def result(self, state, move):
"""Return the state that results from making a move from a state."""
raise NotImplementedError
def utility(self, state, player):
"""Return the value of this final state to player."""
raise NotImplementedError
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 '<{}>'.format(self.__class__.__name__)
def play_game(self, *players):
"""Play an n-person, move-alternating game."""
state = self.initial
while True:
for player in players:
move = player(self, state)
state = self.result(state, move)
if self.terminal_test(state):
self.display(state)
return self.utility(state, self.to_move(self.initial))
class Fig52Game(Game):
"""The game represented in [Figure 5.2]. Serves as a simple test case."""
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 list(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 'MIN' if state in 'BCD' else 'MAX'
class Fig52Extended(Game):
"""Similar to Fig52Game but bigger. Useful for visualisation"""
succs = {i:dict(l=i*3+1, m=i*3+2, r=i*3+3) for i in range(13)}
utils = dict()
def actions(self, state):
return sorted(list(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 range(13)
def to_move(self, state):
return 'MIN' if state in {1, 2, 3} else '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):
self.h = h
self.v = v
self.k = k
moves = [(x, y) for x in range(1, h + 1)
for y in range(1, v + 1)]
self.initial = GameState(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 GameState(to_move=('O' if state.to_move == 'X' else '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 state.utility if player == 'X' else -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), '.'), end=' ')
print()
def compute_utility(self, board, move, player):
"""If 'X' wins with this move, return 1; if 'O' wins 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 +1 if player == 'X' else -1
else:
return 0
def k_in_row(self, board, move, player, delta_x_y):
"""Return true if there is a line through move on board for player."""
(delta_x, delta_y) = delta_x_y
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 == 1 or (x, y - 1) in state.board]
You can’t perform that action at this time.