blob: 01f82cfc1fdc9bb6ef6784798f30047b51c48888 (
plain) (
blame)
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
|
def alpha_beta(node, alpha, beta):
# Based on https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning#Pseudocode
# node needs to support three operations: isTerminal(), value(), getChildren(), maximizingPlayer()
if node.isTerminal():
return node.value()
if node.maximizingPlayer():
v = float("-inf")
for child in node.getChildren():
v = max(v, alpha_beta(child, alpha, beta))
alpha = max(alpha, v)
if beta <= alpha:
break
else:
v = float("inf")
for child in node.getChildren():
v = min(v, alpha_beta(child, alpha, beta))
beta = min(beta, v)
if beta <= alpha:
break
return v
|
