-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimax.html
147 lines (128 loc) · 4.69 KB
/
minimax.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
<!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>