-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimax.py
157 lines (131 loc) · 5.22 KB
/
minimax.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
from typing import Tuple
from board import Board
def evaluate(board, maximizing_player) -> float:
"""
Evaluation function for minimax in mancala
Args:
board (Board): The current board state
maximizing_player (str): The player we are maximizing for
Returns:
(float): The value of the board state
"""
if maximizing_player == "A":
return board.get_player_score("A") - board.get_player_score("B")
else:
return board.get_player_score("B") - board.get_player_score("A")
def minimax(
board: Board,
maximizing_player: str,
current_player: str,
depth: int = 4,
game_over: bool = False,
is_top_level: bool = False,
) -> Tuple[float, int]:
"""Implementation of minimax search algorithm
Args:
board (Board): The current board state
maximizing_player (str): The player we are maximizing for
current_player (str): The player whose turn it is
depth (int): The depth of the search tree. Defaults to 4.
game_over (bool): Whether the game is over. Defaults to False.
is_top_level (bool): Whether this is the top level of the search tree. Defaults to False.
Returns:
best_val (float): The best value for the current player
best_move (int): The best move for the current player
"""
if depth == 0 or game_over:
return evaluate(board, maximizing_player), None
moves = board.get_possible_moves(current_player)
best_move = moves[0] # initialized best move as the first one we see
best_val = float("-inf") if maximizing_player == current_player else float("inf")
for move in moves:
child_board = board.clone()
extra_turn, game_over = child_board.move(move, current_player)
if extra_turn:
next_player = current_player
else:
next_player = "A" if current_player == "B" else "B"
if maximizing_player == current_player:
eval_val = max(
best_val,
minimax(
child_board, maximizing_player, next_player, depth - 1, game_over
)[0],
)
if eval_val > best_val:
best_move = move
best_val = eval_val
else:
best_val = min(
best_val,
minimax(
child_board, maximizing_player, next_player, depth - 1, game_over
)[0],
)
return best_val, best_move
def minimax_alpha_beta(
board: Board,
maximizing_player: str,
current_player: str,
depth: int = 4,
alpha: float = float("-inf"),
beta: float = float("inf"),
game_over: bool = False,
is_top_level: bool = False,
) -> Tuple[float, int]:
"""Implementation of minimax with alpha-beta pruning
Args:
board (Board): The current board state
maximizing_player (str): The player we are maximizing for
current_player (str): The player whose turn it is
depth (int): The depth of the search tree. Defaults to 4.
alpha (float): The alpha value. Defaults to float("-inf").
beta (float): The beta value. Defaults to float("inf").
game_over (bool): Whether the game is over. Defaults to False.
is_top_level (bool): Whether this is the top level of the search tree. Defaults to False.
Returns:
best_val (float): The best value for the current player
best_move (int): The best move for the current player
"""
if depth == 0 or game_over:
return evaluate(board, maximizing_player), None
moves = board.get_possible_moves(current_player)
best_move = (
moves[0] if len(moves) > 0 else None
) # Initialized best move as the first one we see. If no moves, initialize to 0
if maximizing_player == current_player:
best_val = float("-inf")
for move in moves:
child_board = board.clone()
extra_turn, game_over = child_board.move(move, current_player)
next_player = (
current_player if extra_turn else "A" if current_player == "B" else "B"
)
eval_val, _ = minimax_alpha_beta(
child_board, maximizing_player, next_player, depth - 1, alpha, beta
)
if eval_val > best_val:
best_val = eval_val
best_move = move if is_top_level else None
alpha = max(alpha, best_val)
if best_val >= beta:
break # Alpha cutoff
return best_val, best_move
else:
best_val = float("inf")
for move in moves:
child_board = board.clone()
extra_turn, game_over = child_board.move(move, current_player)
next_player = (
current_player if extra_turn else "A" if current_player == "B" else "B"
)
eval_val, _ = minimax_alpha_beta(
child_board, maximizing_player, next_player, depth - 1, alpha, beta
)
if eval_val < best_val:
best_val = eval_val
best_move = move if is_top_level else None
beta = min(beta, best_val)
if best_val <= alpha:
break # Alpha cutoff
return best_val, best_move