minimax.html


<!DOCTYPE html>
<html>
<head>
	<meta charset="UTF-8" />
	<meta name="viewport" content="width=device-width" />
	<script src="https://rawgit.com/Canop/hu.js/master/hu.js"></script>
</head>
<body>

<script>
// Minimax + (alpha-beta) pruning algorithm
// Only leaves have initially a score, the other node scores get filled with minimax function
// check the console to see pruned nodes

var maxDepth = 3;
var idCounter = 0;
var radius=15;

// building this tree https://www.youtube.com/watch?v=Ewh-rF7KSEg
var root = {id: 'A', children:[{id:'B',children:[{id:'E',score:4},{id:'F',score:5}]},{id:'C',children:[{id:'G', score:6},{id:'H',children:[{id:'M',score:3},{id:'N',score:3.9}]},{id:'J',children:[{id:'O',score:7},{id:'P',score:9}]}]}, {id:'D',children:[{id:'K',score:3},{id:'L',score:8}]}]};
build(root);
function build(node, depth){
	if(depth===undefined) depth=0;
	if(!node.depth) node.depth = depth;
	if(!node.id) node.id = idCounter++;
	if(node.children)
		for(var c of node.children){
			c.parent = node;
			build(c, depth+1)
		}
}

var levels = [[root]]; // breadth-first levels
for (var depth = 1; depth <= maxDepth; depth++) {
	levels[depth] = [];
	for (var node of levels[depth - 1])
		if (node.children)
			levels[depth] = levels[depth].concat(node.children)
}
//set a score only for leaves
//levels[levels.length-1].forEach(function(node){node.score=Math.floor(Math.random() * 10)})

/*function visitDepthFirst(node){
	var path=[node];
	for(var child of node.children){
		path=path.concat(visitDepthFirst(child))
	}
	if(node.parent) path.push(node.parent)
	return path
}*/

//console.log('visitDepthFirst',visitDepthFirst(root).map(function(x){return x.id}))

function minimax(node){
	// if node.me it's a maximlizer node with a lower bound
	// else it's a minimizer with a higher bound
	if (!node.children || !node.children.length)
		return node.score
		
	var isMaximizer = !(node.depth % 2);
	for(var child of node.children){
		// check if we need to see next child
		// node.score is the current score being updated after each child visit, and it serves as a bound for pruning
		if(node.parent && node.parent.score && (isMaximizer && node.score>=node.parent.score || !isMaximizer && node.score<=node.parent.score)){
			//we don't need to explore other children = pruning
			if (isMaximizer && node.score>=node.parent.score)
				console.log(node.id, "pruning at a maximizer node.score<node.parent.score, it's not worth exploring other children", node.score, node.parent.score)
			else if(!isMaximizer && node.score<=node.parent.score)
				console.log(node.id, "pruning at a minimizer node.score<node.parent.score, it's not worth exploring other children", node.score, node.parent.score)
			break;
		}else {
			var score = minimax(child)
			if(!isNaN(score)){
				if (node.score!==undefined){
					if (isMaximizer)
						node.score=Math.max(node.score, score)
					else
						node.score=Math.min(node.score, score)
				}else
					node.score=score
			}
		}
	}
	return node.score
}

console.log('best:', minimax(root) );

// draw the tree, ToDo DnD events are not working
var svg = ù('<svg>', 'body').css({
	position:'fixed', left:0, top:0, width:'100%', height:'100%'
})

var gradOpponent = svg.def('<linearGradient>').attr({
	x1:0, y1:0, x2:1, y2:1
}).stops(
	{offset:'0%', stopColor:'Tomato', stopOpacity:0.4},
	{offset:'80%', stopColor:'Coral', stopOpacity:0.8}
);
var gradMe = svg.def('<linearGradient>').attr({
	x1:0, y1:0, x2:1, y2:1
}).stops(
	{offset:'0%', stopColor:'CornflowerBlue', stopOpacity:0.4},
	{offset:'80%', stopColor:'CadetBLue', stopOpacity:0.8}
);
var triangleOpponent = 'M 0 0 L 30 0 L 15 30 L 0 0';
var triangleMe = 'M 0 30 L 30 30 L 15 0 L 0 30'

for (var i=0; i<levels.length; i++) {
	for(var j=0; j<levels[i].length; j++){
		var node = levels[i][j];
		var dj=svg.width()/(levels[i].length+1)
		var g = ù('<svg>', svg)
		.attr({x:dj*(j+1), y:60*i+20})
		.attr({width:radius*2,height:radius*2})
		.css({cursor:'pointer'})

		ù('<path>', g)
		.attr('d', node.depth % 2?triangleOpponent:triangleMe)
		.attr('fill', node.depth % 2?gradOpponent:gradMe)
		
		ù('<text>', g)
		.attr({x:radius, y:6, textAnchor:"middle", alignmentBaseline:"middle"})
		.css({fontSize:'10px', fill:'gray'})
		.text(node.id)  
		
		var vText = ù('<text>', g)
		.attr({x:radius, y:radius+5, textAnchor:"middle", alignmentBaseline:"middle"})
		.css({fontSize:'16px', fill:'black', fontWeight:'bold'})
		.text(node.score!==undefined?node.score:'');
		
		if(node.parent){ // a link to the parent
			ù('<line>', svg).attr({
				x1:+node.parent.svg.attr('x')+radius, y1:+node.parent.svg.attr('y')+2*radius, x2:+g.attr('x')+radius, y2:+g.attr('y'),
				stroke:'#aa3333', strokeOpacity:1,
				strokeWidth:1, strokeLinecap:'round'
			})
		}
		node.svg = g;
	}
}
</script>


</body>
</html>