forked from gabrielecirulli/2048
-
Notifications
You must be signed in to change notification settings - Fork 458
/
ai.js
150 lines (134 loc) · 4.25 KB
/
ai.js
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
148
149
150
function AI(grid) {
this.grid = grid;
}
// static evaluation function
AI.prototype.eval = function() {
var emptyCells = this.grid.availableCells().length;
var smoothWeight = 0.1,
//monoWeight = 0.0,
//islandWeight = 0.0,
mono2Weight = 1.0,
emptyWeight = 2.7,
maxWeight = 1.0;
return this.grid.smoothness() * smoothWeight
//+ this.grid.monotonicity() * monoWeight
//- this.grid.islands() * islandWeight
+ this.grid.monotonicity2() * mono2Weight
+ Math.log(emptyCells) * emptyWeight
+ this.grid.maxValue() * maxWeight;
};
// alpha-beta depth first search
AI.prototype.search = function(depth, alpha, beta, positions, cutoffs) {
var bestScore;
var bestMove = -1;
var result;
// the maxing player
if (this.grid.playerTurn) {
bestScore = alpha;
for (var direction in [0, 1, 2, 3]) {
var newGrid = this.grid.clone();
if (newGrid.move(direction).moved) {
positions++;
if (newGrid.isWin()) {
return { move: direction, score: 10000, positions: positions, cutoffs: cutoffs };
}
var newAI = new AI(newGrid);
if (depth == 0) {
result = { move: direction, score: newAI.eval() };
} else {
result = newAI.search(depth-1, bestScore, beta, positions, cutoffs);
if (result.score > 9900) { // win
result.score--; // to slightly penalize higher depth from win
}
positions = result.positions;
cutoffs = result.cutoffs;
}
if (result.score > bestScore) {
bestScore = result.score;
bestMove = direction;
}
if (bestScore > beta) {
cutoffs++
return { move: bestMove, score: beta, positions: positions, cutoffs: cutoffs };
}
}
}
}
else { // computer's turn, we'll do heavy pruning to keep the branching factor low
bestScore = beta;
// try a 2 and 4 in each cell and measure how annoying it is
// with metrics from eval
var candidates = [];
var cells = this.grid.availableCells();
var scores = { 2: [], 4: [] };
for (var value in scores) {
for (var i in cells) {
scores[value].push(null);
var cell = cells[i];
var tile = new Tile(cell, parseInt(value, 10));
this.grid.insertTile(tile);
scores[value][i] = -this.grid.smoothness() + this.grid.islands();
this.grid.removeTile(cell);
}
}
// now just pick out the most annoying moves
var maxScore = Math.max(Math.max.apply(null, scores[2]), Math.max.apply(null, scores[4]));
for (var value in scores) { // 2 and 4
for (var i=0; i<scores[value].length; i++) {
if (scores[value][i] == maxScore) {
candidates.push( { position: cells[i], value: parseInt(value, 10) } );
}
}
}
// search on each candidate
for (var i=0; i<candidates.length; i++) {
var position = candidates[i].position;
var value = candidates[i].value;
var newGrid = this.grid.clone();
var tile = new Tile(position, value);
newGrid.insertTile(tile);
newGrid.playerTurn = true;
positions++;
newAI = new AI(newGrid);
result = newAI.search(depth, alpha, bestScore, positions, cutoffs);
positions = result.positions;
cutoffs = result.cutoffs;
if (result.score < bestScore) {
bestScore = result.score;
}
if (bestScore < alpha) {
cutoffs++;
return { move: null, score: alpha, positions: positions, cutoffs: cutoffs };
}
}
}
return { move: bestMove, score: bestScore, positions: positions, cutoffs: cutoffs };
}
// performs a search and returns the best move
AI.prototype.getBest = function() {
return this.iterativeDeep();
}
// performs iterative deepening over the alpha-beta search
AI.prototype.iterativeDeep = function() {
var start = (new Date()).getTime();
var depth = 0;
var best;
do {
var newBest = this.search(depth, -10000, 10000, 0 ,0);
if (newBest.move == -1) {
break;
} else {
best = newBest;
}
depth++;
} while ( (new Date()).getTime() - start < minSearchTime);
return best
}
AI.prototype.translate = function(move) {
return {
0: 'up',
1: 'right',
2: 'down',
3: 'left'
}[move];
}