-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtreesearch.py
137 lines (101 loc) · 3.81 KB
/
treesearch.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
""" Module containing various tree searching algorithms """
import chess
# Performance statistics
states_visited = 0
leaves_visited = 0
def minimax_root(s, v, depth, pruning=True):
""" Root function for minimax to handle first call and return best move. """
global states_visited
global leaves_visited
leaves_visited = 0
states_visited = 0
v.cache_misses = 0
possible_next_moves = list(s.board.legal_moves)
best_val = v.MAX_VAL
best_move = None
for x in possible_next_moves:
move = chess.Move.from_uci(str(x))
s.board.push(move)
if(pruning):
value = minimax(s, v, depth - 1, v.MIN_VAL, v.MAX_VAL)
else:
value = minimax_no_pruning(s,v, depth - 1)
s.board.pop()
if(value <= best_val):
best_val = value
best_move = move
#print("current move", move)
#print("move_val", value)
#print("best move ", move)
#print("-------------")
print("-----------------------")
print("Info")
print("-----------------------")
print("States visited:", states_visited)
print("leaves visited:", leaves_visited)
print("cache hits:",leaves_visited - v.cache_misses)
print("Best computer move:", best_move)
print("best val:", best_val)
print("------------------------")
return best_move
def minimax(s, v, depth, alpha, beta):
""" Minimax with alpha-beta pruning. """
global states_visited
global leaves_visited
states_visited+=1
# Stop at a defined maximum depth (chess decision tree too big!) or if game over.
if(depth == 0 or s.board.is_game_over()):
leaves_visited += 1
return v(s);
turn = s.board.turn;
# White is the maximising player, black is the minimizing.
if turn == chess.WHITE:
max_eval = v.MIN_VAL + 1
possible_next_moves = list(s.board.legal_moves)
for move in possible_next_moves:
s.board.push(move)
max_eval = max(minimax(s, v, depth - 1, alpha, beta), max_eval)
s.board.pop()
alpha = max(alpha, max_eval)
if beta <= alpha:
return max_eval
return max_eval
else:
min_eval = v.MAX_VAL - 1
possible_next_moves = list(s.board.legal_moves)
for move in possible_next_moves:
s.board.push(move)
min_eval = min(minimax(s, v, depth - 1, alpha, beta), min_eval)
s.board.pop()
beta = min(beta, min_eval)
if beta <= alpha:
return min_eval
return min_eval
def minimax_no_pruning(s, v, depth):
""" Minimax with no pruning to demonstrate efficiency of pruning. """
global states_visited
global leaves_visited
states_visited+=1
# Stop at a defined maximum depth (chess decision tree too big!) or if game over.
if(depth == 0 or s.board.is_game_over()):
leaves_visited += 1
return v(s);
turn = s.board.turn;
# White is the maximising player, black is the minimizing.
if turn == chess.WHITE:
max_eval = v.MIN_VAL + 1
possible_next_moves = list(s.board.legal_moves)
for move in possible_next_moves:
s.board.push(move)
max_eval = max(minimax_no_pruning(s, v, depth - 1), max_eval)
s.board.pop()
return max_eval
else:
min_eval = v.MAX_VAL - 1
possible_next_moves = list(s.board.legal_moves)
for move in possible_next_moves:
s.board.push(move)
min_eval = min(minimax_no_pruning(s, v, depth - 1), min_eval)
s.board.pop()
return min_eval
#def bns(s, v, alpha, beta):