λ Minimax

======= Algorithm ======= <syntax js> function minimax(node, maximisingPlayer) { var bestValue; if (node.children.length === 0) { bestValue = node.data; } else if (maximisingPlayer) { bestValue = -Number.MAX_VALUE; // Recurse for all children of node. for (var i=0, c=node.children.length; i<c; i++) { var childValue = minimax(node.children[i], false); bestValue = Math.max(bestValue, childValue); } } else { bestValue = Number.MAX_VALUE; // Recurse for all children of node. for (var i=0, c=node.children.length; i<c; i++) { var childValue = minimax(node.children[i], true); bestValue = Math.min(bestValue, childValue); } } return bestValue; } </syntax> ======= Support ======= <syntax js> function run(root) { return minimax(root, true); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Minimax", "height":"390px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> g.node { font-family: Verdana, Helvetica; font-size: 12px; 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.current circle.node-dot { fill: #FFF; stroke: blue; } path.link { fill: none; stroke: gray; } .bar { font-family: Verdana, Helvetica; font-size: 12px; } rect.min { fill: #E0EDFD; } rect.max { fill: #F8CCCD; } body {margin:0px} </style> <script src="http://d3js.org/d3.v2.js"></script> <script> var maxNodes = 15; var treeData; function newTree() { treeData = {data:Math.floor(Math.random()*20), children:[], depth:0}; var allNodes = [treeData]; var levels = [treeData]; // generate a random tree for (var i=0; i<maxNodes; i++) { var child = {data:Math.floor(Math.random()*20), children:[]}; var parent; do { parent = allNodes[Math.floor(allNodes.length*Math.random())]; } while (parent.depth > 2 || parent.children.length > 3); parent.children.push(child); delete parent.data; child.depth = parent.depth+1; allNodes.push(child); if (levels.length <= child.depth) { levels.push(child); } } buildTree("#tree-container"); // Add horizontal slices to show min and max levels. var bars = d3.select("g").selectAll("rect").data(levels); var levelHeight = 300/4; var yBarStart = function(d, i) { if (i===0) { return -20; } if (i>=levels.length) { return 300; } return (levels[i-1].y+levels[i].y*3)/4; } bars = bars.enter().insert("g", ":first-child"); bars.attr("class", "bar"); bars.append("rect") .attr("y", yBarStart) .attr("height", function(d, i) { return yBarStart(null, i+1)-yBarStart(null, i); }) .attr("width", 300) .attr("x", -20) .attr("class", function(d, i) { return i%2? "min" : "max";}) bars.append("svg:text") .attr("dy", function(d, i) {return yBarStart(null, i)+20;}) .attr("dx", -15) .text(function(d, i) { return i===levels.length-1? "" : i%2? "Min" : "Max"; }) if (window.reset) reset(); } var layoutRoot = null; function buildTree(containerName) { // size of the diagram var size = { width:300, height: 300}; var tree = d3.layout.tree() .sort(null) .size([size.width-20, size.height-60]) .children(function(d) { return d.children; }); var nodes = tree.nodes(treeData); var links = tree.links(nodes); // root if (!layoutRoot) { layoutRoot = d3.select(containerName) .append("svg:svg").attr("width", size.width).attr("height", size.height) .append("svg:g") .attr("class", "container") .attr("transform", "translate(20,20)"); } else { layoutRoot.selectAll("path.link").remove(); layoutRoot.selectAll("g.node").remove(); } // Edges between nodes as a <path class="link" /> var link = d3.svg.diagonal(); layoutRoot.selectAll("path.link") .data(links) .enter() .append("svg:path") .attr("class", "link") .attr("d", link); layoutRoot.selectAll("path.link").each(function(d) {d.link = this;}); // nodes var nodeGroup = layoutRoot.selectAll("g.node") .data(nodes) .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 + ")"; }); nodeGroup.append("svg:circle") .attr("class", "node-dot") .attr("r", 15); nodeGroup.append("svg:text") .attr("dy", 4) .text(function(d) { return d.data; }) .attr("text-anchor", "middle"); } 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 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; console.log(node.depth, oldData, bestValue, x.lookupInScope("childValue")); if (typeof bestValue === "number") { node.data = bestValue; var str = (bestValue === -Number.MAX_VALUE || bestValue === Number.MAX_VALUE)? "" : ""+bestValue; d3Node.selectAll("text").text(str); } 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;}); return newPrev; } function args() { return treeData; } </script> </head> <body onload="newTree()"> <button onclick="newTree()">New Tree</button> <div id="tree-container" style="position:relative"> </div> </body> </html> </syntax>