λ Minimax alpha-beta pruning

======= Algorithm ======= <syntax js> function alphaBeta(node, alpha, beta, maximisingPlayer) { var bestValue; if (node.children.length === 0) { bestValue = node.data; } else if (maximisingPlayer) { bestValue = alpha; // Recurse for all children of node. for (var i=0, c=node.children.length; i<c; i++) { var childValue = alphaBeta(node.children[i], bestValue, beta, false); bestValue = Math.max(bestValue, childValue); if (beta <= bestValue) { break; } } } else { bestValue = beta; // Recurse for all children of node. for (var i=0, c=node.children.length; i<c; i++) { var childValue = alphaBeta(node.children[i], alpha, bestValue, true); bestValue = Math.min(bestValue, childValue); if (bestValue <= alpha) { break; } } } return bestValue; } </syntax> ======= Support ======= <syntax js> function run(root) { return alphaBeta(root, -Number.MAX_VALUE, Number.MAX_VALUE, true); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Minimax alpha-beta pruning", "height":"450px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> g { font-family: Verdana, Helvetica; font-size: 12px; } g .data { font-weight: bold; } circle.node-dot { fill: white; stroke: red; stroke-width: 1px; } g.min circle.node-dot { fill: white; stroke: red; stroke-width: 1px; } g.selected circle.node-dot { fill: rgb(3, 166, 249);; stroke: blue; } g.culled circle.node-dot { fill: red; stroke: red; } g.current circle.node-dot { fill: #FFF; stroke: blue; } path.link { fill: none; stroke: gray; } rect.min { fill: #E0EDFD; } rect.max { fill: #F8CCCD; } body {margin:0px} </style> </head> <body onload="newTree()"> <button onclick="newTree()">New Tree</button> <button id="ordering-button">Optimal Ordering</button> <div id="tree-container" style="position:relative"> </div> <script src="http://d3js.org/d3.v2.js"></script> <script> var maxNodes = 15; var root; var firstSetup = true; var nodeId = 0; var orderButton = document.getElementById("ordering-button"); orderButton.onclick = order; // Setup tree. var size = { width:348, height: 300}; var tree = d3.layout.tree() .size([size.width-40, size.height-40]); var svg = d3.select("#tree-container") .append("svg:svg").attr("width", size.width).attr("height", size.height) var barGroup = svg.append("g"); svg = svg.append("svg:g") .attr("class", "container") .attr("transform", "translate(20,20)"); function newTree() { root = {id:nodeId++, data:Math.floor(Math.random()*20), children:[], depth:0}; var allNodes = [root]; var levels = [root]; // generate a random tree for (var i=0; i<maxNodes; i++) { var child = {id:nodeId++, data:Math.floor(Math.random()*20), children:[]}; var idx = Math.floor(Math.min(allNodes.length,4)*Math.random()); var parent = allNodes[idx]; parent.children.push(child); delete parent.data; child.depth = parent.depth+1; child.parent = parent; allNodes.push(child); allNodes.sort(function (a,b) {return a.children.length+a.depth - b.children.length-b.depth;}); if (levels.length <= child.depth) { levels.push(child); } } buildTree(); // Add horizontal slices to show min and max levels. var bars = barGroup.selectAll(".bar").data(levels); var yBarStart = function(d, i) { if (i===0) { return 0; } if (i>=levels.length) { return 300; } return (levels[i-1].y+levels[i].y*3)/4+20; } bars.exit().remove(); var newBars = bars.enter().append("g"); newBars.attr("class", "bar"); newBars.append("rect") .attr("width", 400) .attr("x", 0) .attr("class", function(d, i) { return i%2? "min" : "max";}); newBars.append("svg:text") .attr("dx", 5); bars.select("rect") .attr("y", yBarStart) .attr("height", function(d, i) { return yBarStart(null, i+1)-yBarStart(null, i); }); bars.select("text") .attr("dy", function(d, i) {return yBarStart(null, i)+20;}) .attr("height", function(d, i) { return yBarStart(null, i+1)-yBarStart(null, i); }) .text(function(d, i) { return i===levels.length-1? "" : i%2? "Min" : "Max"; }); // Reset Tailspin. if (window.reset) reset(); orderButton.innerText = "Optimal Ordering"; orderButton.onclick = order; } // Function to order all children optimally for pruning. function order(event) { var negamax = function(node, color) { var bestValue; if (node.children.length === 0) { bestValue = color*node.data; } else { bestValue = -Number.MAX_VALUE; // Recurse for all children of node. for (var i=0, c=node.children.length; i<c; i++) { var childValue = -negamax(node.children[i], -color); bestValue = Math.max(bestValue, childValue); } } node.bestValue = bestValue; return bestValue; } // Calculate the actual best value for each node. negamax(root, 1); // Sort each child. var sortChildren = function(node) { if (node.children.length > 0) { delete node.data; node.children.sort(function(a, b) {return a.bestValue - b.bestValue;}); for (var i=0, c=node.children.length; i<c; i++) { sortChildren(node.children[i]); } } } sortChildren(root); buildTree(); // Reset Tailspin. if (window.reset) reset(); event.target.innerText = "Random Ordering"; event.target.onclick = randomOrder; } function randomOrder(event) { function shuffle(a) { for (var i=a.length-1; i>0; i--) { // j is a random integer [0-i] var j = Math.floor(Math.random()*(i+1)); var t=a[j];a[j]=a[i];a[i]=t; } return a; } // Sort each child. var shuffleChildren = function(node) { if (node.children.length > 0) { delete node.data; shuffle(node.children); for (var i=0, c=node.children.length; i<c; i++) { shuffleChildren(node.children[i]); } } } shuffleChildren(root); buildTree(); // Reset Tailspin. if (window.reset) reset(); event.target.innerText = "Optimal Ordering"; event.target.onclick = order; } function buildTree() { var nodes = tree.nodes(root); var links = tree.links(nodes); // Edges between nodes as a <path class="link" /> var diagonal = d3.svg.diagonal(); var svgLinks = svg.selectAll("path.link") .data(links, function(d) { return d.source.id + "-" + d.target.id; }); svgLinks.exit().remove(); svgLinks.enter() .append("svg:path") .attr("class", "link") .attr("d", diagonal); // Nodes var nodeGroup = svg.selectAll("g.node") .data(nodes, function(d) { return d.id; }); nodeGroup.exit().remove(); nodeGroup.attr("class", "node"); var newNodes = nodeGroup.enter() .append("svg:g") .attr("class", "node") .classed("min", function(d) {return d.depth%2;}) .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); newNodes.append("svg:circle") .attr("class", "node-dot") .attr("r", 15); newNodes.append("text") .attr("class", "data") .attr("dy", 4) .attr("text-anchor", "middle"); newNodes.append("text") .attr("class", "alpha") .attr({dx:function(d){return d===root?-35:-20;}}) .attr({dy:function(d){return d===root?4:-15;}}) .attr("text-anchor", "middle"); newNodes.append("text") .attr("class", "beta") .attr({dx:function(d){return d===root?35:20;}}) .attr({dy:function(d){return d===root?4:-15;}}) .attr("text-anchor", "middle"); // Set the text of the node. nodeGroup.select("text") .text(function(d) { return d.data; }); // Transition nodes and links to their new positions. var t = svg.transition().duration(750); t.selectAll(".link") .attr("d", diagonal); t.selectAll(".node") .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); } function update(n, x, isRunning, duration, $prev) { if (x.stack.length < 1 && !x.hasOwnProperty('returnedValue')) { d3.selectAll("g.node").classed("selected", false); } var newPrev = $prev; var node = x.lookupInScope("node"); var bestValue = x.lookupInScope("bestValue"); var childValue = x.lookupInScope("childValue"); var idx = x.lookupInScope("i"); var maximisingPlayer = x.lookupInScope("maximisingPlayer"); var alpha = maximisingPlayer && typeof bestValue === "number" && node.children.length>0? bestValue : x.lookupInScope("alpha"); var beta = !maximisingPlayer && typeof bestValue === "number" && node.children.length>0? bestValue : x.lookupInScope("beta"); var d3Node = node? d3.selectAll("g.node").filter(function(d) {return d===node;}) : null; if (node && d3Node) { var unselectedNode = d3Node.filter(":not(.selected)"); var oldData = node.data; if (typeof bestValue === "number" && bestValue === childValue) { node.data = childValue; var str = (childValue === -Number.MAX_VALUE || childValue === Number.MAX_VALUE)? "" : ""+childValue; d3Node.selectAll("text").text(str); } node.alpha = alpha; node.beta = beta; d3Node.classed("culled", beta<=alpha); unselectedNode.classed("selected", true); newPrev = function(prev) { node.data = oldData; var str = (typeof oldData !== "number" || oldData === -Number.MAX_VALUE || oldData === Number.MAX_VALUE)? "" : ""+oldData; d3Node.selectAll("text").text(str); unselectedNode.classed("selected", false); prev(); }.bind(undefined, newPrev); } d3.selectAll("g.node").classed("current", function(d) {return d===node;}); // Checks if p is a parent of n. var isParent = function (p, n) { if (!n) return false; if (p === n) return true; return isParent(p, n.parent); } // Alpha/beta text updates. d3.selectAll("g.node").select(".alpha") .text(function(d) { if (node && isParent(d, node)) { var aText = typeof d.alpha === "number"? (d.alpha===-Number.MAX_VALUE? "-\u221E" : ""+d.alpha) : ""; aText = d===root? "\u03B1:"+aText : aText; return aText; } return ""; }); d3.selectAll("g.node").select(".beta") .text(function(d) { if (node && isParent(d, node)) { var bText = typeof d.beta === "number"? (d.beta===Number.MAX_VALUE? "\u221E" : ""+d.beta) : ""; bText = d===root? "\u03B2:"+bText : bText; return bText; } return ""; }); return newPrev; } function args() { return root; } </script> </body> </html> </syntax>