diff options
author | Matt Strapp <strap012@umn.edu> | 2021-04-26 10:53:43 -0500 |
---|---|---|
committer | Matt Strapp <strap012@umn.edu> | 2021-04-26 15:03:12 -0500 |
commit | d311af01feb32550aaae8638d4cc167948f5464c (patch) | |
tree | 3c0b8606a7a5267e3e890a63b8565c5c27f10438 /python/alphaBeta.py | |
parent | actually add files (diff) | |
download | csci4511w-d311af01feb32550aaae8638d4cc167948f5464c.tar csci4511w-d311af01feb32550aaae8638d4cc167948f5464c.tar.gz csci4511w-d311af01feb32550aaae8638d4cc167948f5464c.tar.bz2 csci4511w-d311af01feb32550aaae8638d4cc167948f5464c.tar.lz csci4511w-d311af01feb32550aaae8638d4cc167948f5464c.tar.xz csci4511w-d311af01feb32550aaae8638d4cc167948f5464c.tar.zst csci4511w-d311af01feb32550aaae8638d4cc167948f5464c.zip |
Rebase newer branch
Diffstat (limited to '')
-rw-r--r-- | python/alphaBeta.py | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/python/alphaBeta.py b/python/alphaBeta.py new file mode 100644 index 0000000..01f82cf --- /dev/null +++ b/python/alphaBeta.py @@ -0,0 +1,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 |