Rebase newer branch

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