Repository navigation
Expand file tree
/
Copy pathminimax_game_search.py
More file actions
283 lines (234 loc) · 15.1 KB
/
Copy pathminimax_game_search.py
File metadata and controls
283 lines (234 loc) · 15.1 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
"""
A complete minimax game solver with alpha-beta pruning and depth limiting.
"""
# △ AURA Pattern Library — © Reality Optimizer ⟦AE1.PMRGG3ZCHIRFEZLBNRUXI6JAJ5YHI2LNNF5GK4RCFQRG2IR2EJAUKTKBKJFTCIRMEJXCEORCGARCYITQNFSCEORCEIWCE5DNEI5CEQKVKJASAUDBOR2GK4TOEBGGSYTSMFZHSIRMEJ3CEORRPWYSJPXO⟧
#
_AURA_MARK = "AE1.PMRGG3ZCHIRFEZLBNRUXI6JAJ5YHI2LNNF5GK4RCFQRG2IR2EJAUKTKBKJFTCIRMEJXCEORCGARCYITQNFSCEORCEIWCE5DNEI5CEQKVKJASAUDBOR2GK4TOEBGGSYTSMFZHSIRMEJ3CEORRPWYSJPXO"
from abc import ABC, abstractmethod
from typing import List, Optional, Tuple, Any, Union
import copy
class GameState(ABC):
"""Abstract base class for game states."""
@abstractmethod
def get_legal_moves(self) -> List[Any]:
"""Return a list of legal moves from this state."""
pass
@abstractmethod
def make_move(self, move: Any) -> 'GameState':
"""Return a new game state after applying the given move."""
pass
@abstractmethod
def is_terminal(self) -> bool:
"""Return True if this is a terminal state (win/loss/draw)."""
pass
@abstractmethod
def get_result(self) -> Optional[int]:
"""Return the game result if terminal: 1 (win), -1 (loss), 0 (draw), None (not terminal)."""
pass
class Evaluator(ABC):
"""Abstract base class for position evaluation."""
@abstractmethod
def evaluate(self, state: GameState) -> float:
"""Evaluate the given non-terminal state. Higher values favor the maximizing player."""
pass
class TicTacToeState(GameState):
"""Tic-TacToe game state implementation."""
def __init__(self, board: Optional[List[List[Optional[str]]]] = None, player: str = 'X'):
"""Initialize with optional board and current player."""
self.board = board or [[None for _ in range(3)] for _ in range(3)]
self.player = player
def get_legal_moves(self) -> List[Tuple[int, int]]:
"""Return list of empty positions as (row, col) tuples."""
moves = []
for i in range(3):
for j in range(3):
if self.board[i][j] is None:
moves.append((i, j))
return moves
def make_move(self, move: Tuple[int, int]) -> 'TicTacToeState':
"""Return new state with move applied."""
if self.board[move[0]][move[1]] is not None:
raise ValueError("Invalid move")
new_board = copy.deepcopy(self.board)
new_board[move[0]][move[1]] = self.player
next_player = 'O' if self.player == 'X' else 'X'
return TicTacToeState(new_board, next_player)
def is_terminal(self) -> bool:
"""Check if game is over."""
return self.get_result() is not None
def get_result(self) -> Optional[int]:
"""Return 1 if X wins, -1 if O wins, 0 for draw, None for ongoing."""
# Check rows, columns, diagonals for wins
for i in range(3):
# Check rows
if self.board[i][0] == self.board[i][1] == self.board[i][2] and self.board[i][0] is not None:
return 1 if self.board[i][0] == 'X' else -1
# Check columns
if self.board[0][i] == self.board[1][i] == self.board[2][i] and self.board[0][i] is not None:
return 1 if self.board[0][i] == 'X' else -1
# Check diagonals
if self.board[0][0] == self.board[1][1] == self.board[2][2] and self.board[0][0] is not None:
return 1 if self.board[0][0] == 'X' else -1
if self.board[0][2] == self.board[1][1] == self.board[2][0] and self.board[0][2] is not None:
return 1 if self.board[0][2] == 'X' else -1
# Check for draw
if all(self.board[i][j] is not None for i in range(3) for j in range(3)):
return 0
# Game not over
return None
def __str__(self) -> str:
"""String representation of the board."""
result = ""
for i in range(3):
row = "|".join([self.board[i][j] if self.board[i][j] else " " for j in range(3)])
result += row + "\n"
if i < 2:
result += "-----\n"
return result
class TicTacToeEvaluator(Evaluator):
"""Simple evaluator for Tic-TacToe."""
def evaluate(self, state: TicTacToeState) -> float:
"""Evaluate non-terminal state based on potential winning lines."""
if state.is_terminal():
result = state.get_result()
return float('inf') if result == 1 else float('-inf') if result == -1 else 0.0
score = 0
# Check rows
for i in range(3):
x_count = sum(1 for j in range(3) if state.board[i][j] == 'X')
o_count = sum(1 for j in range(3) if state.board[i][j] == 'O')
if x_count > 0 and o_count == 0:
score += 10 ** x_count
elif o_count > 0 and x_count == 0:
score -= 10 ** o_count
# Check columns
for j in range(3):
x_count = sum(1 for i in range(3) if state.board[i][j] == 'X')
o_count = sum(1 for i in range(3) if state.board[i][j] == 'O')
if x_count > 0 and o_count == 0:
score += 10 ** x_count
elif o_count > 0 and x_count == 0:
score -= 10 ** o_count
# Check diagonals
diagonals = [
[(0,0), (1,1), (2,2)],
[(0,2), (1,1), (2,0)]
]
for diag in diagonals:
x_count = sum(1 for i, j in diag if state.board[i][j] == 'X')
o_count = sum(1 for i, j in diag if state.board[i][j] == 'O')
if x_count > 0 and o_count == 0:
score += 10 ** x_count
elif o_count > 0 and x_count == 0:
score -= 10 ** o_count
return float(score)
class MinimaxSolver:
"""Minimax solver with alpha-beta pruning and depth limiting."""
def __init__(self, evaluator: Evaluator):
"""Initialize with an evaluator."""
self.evaluator = evaluator
self.nodes_explored = 0
def solve(self, state: GameState, depth_limit: int = 10,
maximizing: bool = True) -> Tuple[Optional[Any], float]:
"""
Solve the game from the given state.
Args:
state: Current game state
depth_limit: Maximum search depth
maximizing: Whether the side to move maximizes the evaluation.
(This was hardcoded True, so choosing a move for the
minimizing player actually optimized for the OPPONENT.)
Returns:
Tuple of (best_move, best_score)
"""
self.nodes_explored = 0
best_move, best_score = self._minimax(state, depth_limit, maximizing,
float('-inf'), float('inf'))
return best_move, best_score
def _minimax(self, state: GameState, depth: int, maximizing: bool,
alpha: float, beta: float) -> Tuple[Optional[Any], float]:
"""Internal minimax implementation with alpha-beta pruning."""
self.nodes_explored += 1
# Terminal state or depth limit reached
if state.is_terminal() or depth == 0:
if state.is_terminal():
result = state.get_result()
return None, float(result) if result is not None else self.evaluator.evaluate(state)
else:
return None, self.evaluator.evaluate(state)
best_move = None
if maximizing:
max_eval = float('-inf')
for move in state.get_legal_moves():
child_state = state.make_move(move)
_, eval_score = self._minimax(child_state, depth - 1, False, alpha, beta)
if eval_score > max_eval:
max_eval = eval_score
best_move = move
alpha = max(alpha, eval_score)
if beta <= alpha:
break # Beta cutoff
return best_move, max_eval
else:
min_eval = float('inf')
for move in state.get_legal_moves():
child_state = state.make_move(move)
_, eval_score = self._minimax(child_state, depth - 1, True, alpha, beta)
if eval_score < min_eval:
min_eval = eval_score
best_move = move
beta = min(beta, eval_score)
if beta <= alpha:
break # Alpha cutoff
return best_move, min_eval
def main():
"""Self-test against game-theoretic truths of tic-tac-toe: the empty
board is a draw, wins-in-1 are taken, threats are blocked, and perfect
self-play always draws."""
solver = MinimaxSolver(TicTacToeEvaluator())
# Truth 1: tic-tac-toe with perfect play is a DRAW — value exactly 0.
move, score = solver.solve(TicTacToeState(), depth_limit=9, maximizing=True)
assert score == 0, f"game value of tic-tac-toe must be 0, got {score}"
assert move is not None and solver.nodes_explored > 9, \
"search barely explored anything"
# Truth 2: X completes its row immediately (win-in-1).
board = [["X", "X", None], ["O", "O", None], [None, None, None]]
move, score = solver.solve(TicTacToeState(board, "X"), depth_limit=9,
maximizing=True)
assert move == (0, 2), f"X must take the winning square (0,2), chose {move}"
assert score == 1, f"winning position must score 1, got {score}"
assert solver.nodes_explored == 36, \
f"alpha-beta on this position explores exactly 36 nodes, got {solver.nodes_explored}"
# Truth 3: O (the minimizer) must BLOCK X's open row — the exact bug
# this test pins: with maximizing hardcoded True, O helped X win.
board = [["X", "X", None], [None, "O", None], [None, None, None]]
move, score = solver.solve(TicTacToeState(board, "O"), depth_limit=9,
maximizing=False)
assert move == (0, 2), f"O must block at (0,2), chose {move}"
# Truth 4: O to move with a win available — the position's VALUE is a
# forced O win (-1). Several moves force it (immediate (1,2), or block
# (0,2) then fork), so pin the value and verify the chosen move by
# playing the line out.
board = [["X", "X", None], ["O", "O", None], [None, None, "X"]]
move, score = solver.solve(TicTacToeState(board, "O"), depth_limit=9,
maximizing=False)
assert score == -1, f"O-to-move position must be a forced O win (-1), got {score}"
line = TicTacToeState(board, "O").make_move(move)
while not line.is_terminal():
mv, _ = solver.solve(line, depth_limit=9, maximizing=(line.player == "X"))
line = line.make_move(mv)
assert line.get_result() == -1, "the chosen move failed to convert the forced win"
# Truth 5 (the crown): perfect vs perfect self-play ends in a draw,
# from every one of the 9 possible opening moves.
for opening in TicTacToeState().get_legal_moves():
state = TicTacToeState().make_move(opening)
while not state.is_terminal():
mv, _ = solver.solve(state, depth_limit=9,
maximizing=(state.player == "X"))
state = state.make_move(mv)
assert state.get_result() == 0, \
f"perfect self-play after opening {opening} ended {state.get_result()}, not a draw"
print("minimax_game_search: game value 0, win-in-1 taken, block forced, "
"O's win taken, 9/9 perfect self-plays drew — PASS")
if __name__ == "__main__":
main()