54 //////////////////////////////////////////////////////////////// |
54 //////////////////////////////////////////////////////////////// |
55 // Blind random AI. |
55 // Blind random AI. |
56 //////////////////////////////////////////////////////////////// |
56 //////////////////////////////////////////////////////////////// |
57 |
57 |
58 /** Blind random AI. |
58 /** Blind random AI. |
59 * @param {Board} brdEngine board engine from board.js |
59 * @param {Board} brd board engine from board.js |
60 * @constructor */ |
60 * @constructor */ |
61 ai.BlindRandom = function(brdEngine) { |
61 ai.BlindRandom = function(brd) { |
62 this.brdEngine = brdEngine; |
62 this.brd = brd; |
63 } |
63 } |
64 /** Select best direction for next step. */ |
64 /** Select best direction for next step. */ |
65 ai.BlindRandom.prototype.analyse = function(brd2d) { |
65 ai.BlindRandom.prototype.analyse = function(brd2d) { |
66 var origBrd = new this.brdEngine(brd2d); |
66 var origBrd = new this.brd(brd2d); |
67 while (true) { |
67 while (true) { |
68 var rnd = Math.floor(Math.random()*4); |
68 var rnd = Math.floor(Math.random()*4); |
69 if (origBrd[ai.canFn[rnd]]()) |
69 if (origBrd[ai.canFn[rnd]]()) |
70 return ai.dirs[rnd]; |
70 return ai.dirs[rnd]; |
71 } |
71 } |
87 * @property {number} up weight |
87 * @property {number} up weight |
88 * @property {number} down weight |
88 * @property {number} down weight |
89 */ |
89 */ |
90 |
90 |
91 /** Blind weight random AI. |
91 /** Blind weight random AI. |
92 * @param {Board} brdEngine board engine from board.js |
92 * @param {Board} brd board engine from board.js |
93 * @param {ai.BlindWeightRandom.cfg} cfg configuration settings |
93 * @param {ai.BlindWeightRandom.cfg} cfg configuration settings |
94 * @constructor */ |
94 * @constructor */ |
95 ai.BlindWeightRandom = function(brdEngine, cfg) { |
95 ai.BlindWeightRandom = function(brd, cfg) { |
96 this.brdEngine = brdEngine; |
96 this.brd = brd; |
97 this.cfg = ai.copyObj(ai.BlindWeightRandom.bestCfg); |
97 this.cfg = ai.copyObj(ai.BlindWeightRandom.bestCfg); |
98 ai.copyObj(cfg, this.cfg); |
98 ai.copyObj(cfg, this.cfg); |
99 var total = this.cfg.left + this.cfg.right + this.cfg.up + this.cfg.down; |
99 var total = this.cfg.left + this.cfg.right + this.cfg.up + this.cfg.down; |
100 this.threshold1 = this.cfg.left/total; |
100 this.threshold1 = this.cfg.left/total; |
101 this.threshold2 = (this.cfg.left + this.cfg.down)/total; |
101 this.threshold2 = (this.cfg.left + this.cfg.down)/total; |
102 this.threshold3 = (this.cfg.left + this.cfg.down + this.cfg.right)/total; |
102 this.threshold3 = (this.cfg.left + this.cfg.down + this.cfg.right)/total; |
103 } |
103 } |
104 ai.BlindWeightRandom.bestCfg = { left: 1, right: 16, up: 4, down: 8 }; |
104 ai.BlindWeightRandom.bestCfg = { left: 1, right: 16, up: 4, down: 8 }; |
105 /** Select best direction for next step. */ |
105 /** Select best direction for next step. */ |
106 ai.BlindWeightRandom.prototype.analyse = function(brd2d) { |
106 ai.BlindWeightRandom.prototype.analyse = function(brd2d) { |
107 var origBrd = new this.brdEngine(brd2d); |
107 var origBrd = new this.brd(brd2d); |
108 while (true) { |
108 while (true) { |
109 var rnd = Math.random(); |
109 var rnd = Math.random(); |
110 if (rnd < this.threshold1) |
110 if (rnd < this.threshold1) |
111 var dir = 0; |
111 var dir = 0; |
112 else if (rnd < this.threshold2) |
112 else if (rnd < this.threshold2) |
134 * @property {boolean} whilePossible move in one direction while possible |
134 * @property {boolean} whilePossible move in one direction while possible |
135 * @property {boolean} down switch direction clockwise |
135 * @property {boolean} down switch direction clockwise |
136 */ |
136 */ |
137 |
137 |
138 /** Blind cycle AI. |
138 /** Blind cycle AI. |
139 * @param {Board} brdEngine board engine from board.js |
139 * @param {Board} brd board engine from board.js |
140 * @param {ai.BlindCycle.cfg} cfg configuration settings |
140 * @param {ai.BlindCycle.cfg} cfg configuration settings |
141 * @constructor */ |
141 * @constructor */ |
142 ai.BlindCycle = function(brdEngine, cfg) { |
142 ai.BlindCycle = function(brd, cfg) { |
143 this.brdEngine = brdEngine; |
143 this.brd = brd; |
144 this.cfg = cfg || {}; |
144 this.cfg = cfg || {}; |
145 this.cfg.whilePossible = this.cfg.whilePossible || false; |
145 this.cfg.whilePossible = this.cfg.whilePossible || false; |
146 this.cfg.clockwise = this.cfg.clockwise || false; |
146 this.cfg.clockwise = this.cfg.clockwise || false; |
147 } |
147 } |
148 ai.BlindCycle.dirs = ["left", "down", "right", "up"]; |
148 ai.BlindCycle.dirs = ["left", "down", "right", "up"]; |
153 else |
153 else |
154 return (dir + 1) % 4; |
154 return (dir + 1) % 4; |
155 } |
155 } |
156 /** Select best direction for next step. */ |
156 /** Select best direction for next step. */ |
157 ai.BlindCycle.prototype.analyse = function(brd2d) { |
157 ai.BlindCycle.prototype.analyse = function(brd2d) { |
158 var origBrd = new this.brdEngine(brd2d); |
158 var origBrd = new this.brd(brd2d); |
159 this.prevDir = this.prevDir || 0; |
159 this.prevDir = this.prevDir || 0; |
160 if (!this.cfg.whilePossible) |
160 if (!this.cfg.whilePossible) |
161 this.prevDir = this.nextDir(this.prevDir); |
161 this.prevDir = this.nextDir(this.prevDir); |
162 while (true) { |
162 while (true) { |
163 if (origBrd[ai.BlindCycle.canFn[this.prevDir]]()) |
163 if (origBrd[ai.BlindCycle.canFn[this.prevDir]]()) |
188 * @property {number} edgeBonus bonus for max value at board edge |
188 * @property {number} edgeBonus bonus for max value at board edge |
189 * @property {number} freeBonus bonus for each free cell |
189 * @property {number} freeBonus bonus for each free cell |
190 */ |
190 */ |
191 |
191 |
192 /** 1 step deep with * AI. |
192 /** 1 step deep with * AI. |
193 * @param {Board} brdEngine board engine from board.js |
193 * @param {Board} brd board engine from board.js |
194 * @param {ai.OneStepAhead.cfg} cfg configuration settings |
194 * @param {ai.OneStepAhead.cfg} cfg configuration settings |
195 * @constructor */ |
195 * @constructor */ |
196 ai.OneStepAhead = function(brdEngine, cfg) { |
196 ai.OneStepAhead = function(brd, cfg) { |
197 this.brdEngine = brdEngine; |
197 this.brd = brd; |
198 this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg); |
198 this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg); |
199 ai.copyObj(cfg, this.cfg); |
199 ai.copyObj(cfg, this.cfg); |
200 } |
200 } |
201 ai.OneStepAhead.bestCfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0}; |
201 ai.OneStepAhead.bestCfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0}; |
202 ai.OneStepAhead.prototype.utility = function(brd) { |
202 ai.OneStepAhead.prototype.utility = function(brd) { |
214 utility += this.cfg.freeBonus * brd.freeCnt(); |
214 utility += this.cfg.freeBonus * brd.freeCnt(); |
215 return utility; |
215 return utility; |
216 } |
216 } |
217 /** Select best direction for next step. */ |
217 /** Select best direction for next step. */ |
218 ai.OneStepAhead.prototype.analyse = function(brd2d) { |
218 ai.OneStepAhead.prototype.analyse = function(brd2d) { |
219 var origBrd = new this.brdEngine(brd2d); |
219 var origBrd = new this.brd(brd2d); |
220 var nextBrd = new this.brdEngine(); |
220 var nextBrd = new this.brd(); |
221 var maxUtility = -1; |
221 var maxUtility = -1; |
222 var bestDir; |
222 var bestDir; |
223 for (var i = 0; i < ai.dirs.length; i++) { |
223 for (var i = 0; i < ai.dirs.length; i++) { |
224 var dir = ai.dirs[i]; |
224 var dir = ai.dirs[i]; |
225 if (origBrd[dir](nextBrd)) { |
225 if (origBrd[dir](nextBrd)) { |
251 * @property {number} edgeBonus bonus for max value at board edge |
251 * @property {number} edgeBonus bonus for max value at board edge |
252 * @property {number} freeBonus bonus for each free cell |
252 * @property {number} freeBonus bonus for each free cell |
253 */ |
253 */ |
254 |
254 |
255 /** Deep merges AI without random simulation. |
255 /** Deep merges AI without random simulation. |
256 * @param {Board} brdEngine board engine from board.js |
256 * @param {Board} brd board engine from board.js |
257 * @param {Object} cfg configuration settings |
257 * @param {Object} cfg configuration settings |
258 * @constructor */ |
258 * @constructor */ |
259 ai.StaticDeepMerges = function(brdEngine, cfg) { |
259 ai.StaticDeepMerges = function(brd, cfg) { |
260 this.brdEngine = brdEngine; |
260 this.brd = brd; |
261 this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg); |
261 this.cfg = ai.copyObj(ai.OneStepAhead.bestCfg); |
262 ai.copyObj(cfg, this.cfg); |
262 ai.copyObj(cfg, this.cfg); |
263 } |
263 } |
264 ai.StaticDeepMerges.bestCfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, utilityThreshold: 10}; |
264 ai.StaticDeepMerges.bestCfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, utilityThreshold: 10}; |
265 ai.StaticDeepMerges.prototype.utility = function(brd) { |
265 ai.StaticDeepMerges.prototype.utility = function(brd) { |
277 utility += this.cfg.freeBonus * brd.freeCnt(); |
277 utility += this.cfg.freeBonus * brd.freeCnt(); |
278 return utility; |
278 return utility; |
279 } |
279 } |
280 /** Select best direction for next step. */ |
280 /** Select best direction for next step. */ |
281 ai.StaticDeepMerges.prototype.analyse = function(brd2d) { |
281 ai.StaticDeepMerges.prototype.analyse = function(brd2d) { |
282 var origBrd = new this.brdEngine(brd2d); |
282 var origBrd = new this.brd(brd2d); |
283 var nextBrd = new this.brdEngine(); |
283 var nextBrd = new this.brd(); |
284 var prevScore = -1, nextScore = -1; |
284 var prevScore = -1, nextScore = -1; |
285 var maxUtility = -1; |
285 var maxUtility = -1; |
286 var bestDir; |
286 var bestDir; |
287 for (var i = 0; i < ai.dirs.length; i++) { |
287 for (var i = 0; i < ai.dirs.length; i++) { |
288 var dir = ai.dirs[i]; |
288 var dir = ai.dirs[i]; |
303 return bestDir; |
303 return bestDir; |
304 } |
304 } |
305 ai.StaticDeepMerges.prototype.evalFn = function(brd) { |
305 ai.StaticDeepMerges.prototype.evalFn = function(brd) { |
306 var currScore = brd.score(); |
306 var currScore = brd.score(); |
307 var maxUtility = currScore; |
307 var maxUtility = currScore; |
308 var nextBrd = new this.brdEngine(); |
308 var nextBrd = new this.brd(); |
309 for (var i = 0; i < ai.dirs.length; i++) { |
309 for (var i = 0; i < ai.dirs.length; i++) { |
310 if (brd[ai.dirs[i]](nextBrd)) { |
310 if (brd[ai.dirs[i]](nextBrd)) { |
311 var score = nextBrd.score(); |
311 var score = nextBrd.score(); |
312 if (score > currScore) |
312 if (score > currScore) |
313 maxUtility = Math.max(maxUtility, this.evalFn(nextBrd)); |
313 maxUtility = Math.max(maxUtility, this.evalFn(nextBrd)); |
334 * @property {number} edgeBonus bonus for max value at board edge |
334 * @property {number} edgeBonus bonus for max value at board edge |
335 * @property {number} freeBonus bonus for each free cell |
335 * @property {number} freeBonus bonus for each free cell |
336 */ |
336 */ |
337 |
337 |
338 /** N level deep with random simulation. |
338 /** N level deep with random simulation. |
339 * @param {Board} brdEngine board engine from board.js |
339 * @param {Board} brd board engine from board.js |
340 * @param {ai.expectimax.cfg} cfg configuration settings |
340 * @param {ai.expectimax.cfg} cfg configuration settings |
341 * @constructor */ |
341 * @constructor */ |
342 ai.expectimax = function(brdEngine, cfg) { |
342 ai.expectimax = function(brd, cfg) { |
343 this.brdEngine = brdEngine; |
343 this.brd = brd; |
344 this.cfg = ai.copyObj(ai.expectimax.bestCfg); |
344 this.cfg = ai.copyObj(ai.expectimax.bestCfg); |
345 ai.copyObj(cfg, this.cfg); |
345 ai.copyObj(cfg, this.cfg); |
346 if (this.cfg.balance <= 0) |
346 if (this.cfg.balance <= 0) |
347 this.cfg.balance = ai.expectimax.bestCfg.balance; |
347 this.cfg.balance = ai.expectimax.bestCfg.balance; |
348 if ( this.cfg.balance > 1) |
348 if ( this.cfg.balance > 1) |
372 return score; |
372 return score; |
373 } |
373 } |
374 /** Select best direction for next step. */ |
374 /** Select best direction for next step. */ |
375 ai.expectimax.prototype.analyse = function(brd2d) { |
375 ai.expectimax.prototype.analyse = function(brd2d) { |
376 this.brdCache = new ai.brdCache(); |
376 this.brdCache = new ai.brdCache(); |
377 var origBrd = new this.brdEngine(brd2d); |
377 var origBrd = new this.brd(brd2d); |
378 var nextBrd = new this.brdEngine(); |
378 var nextBrd = new this.brd(); |
379 var maxW = -1; |
379 var maxW = -1; |
380 var bestDir; |
380 var bestDir; |
381 this.cleanup(); |
381 this.cleanup(); |
382 this.depthLimit = this.cfg.depth; |
382 this.depthLimit = this.cfg.depth; |
383 var freeCnt = origBrd.freeCnt(); |
383 var freeCnt = origBrd.freeCnt(); |
401 return this.utility(brd); |
401 return this.utility(brd); |
402 var wCached = this.brdCache.get(brd); |
402 var wCached = this.brdCache.get(brd); |
403 if (wCached) |
403 if (wCached) |
404 return wCached; |
404 return wCached; |
405 var wMin = +Infinity; |
405 var wMin = +Infinity; |
406 var randBoard = new this.brdEngine(); |
406 var randBoard = new this.brd(); |
407 var nextBrd = new this.brdEngine(); |
407 var nextBrd = new this.brd(); |
408 for (var i = 0; i < 3; i++) { |
408 for (var i = 0; i < 3; i++) { |
409 for (var j = 0; j < 3; j++) { |
409 for (var j = 0; j < 3; j++) { |
410 if (brd.get(i, j) === 0) { |
410 if (brd.get(i, j) === 0) { |
411 brd.copy(randBoard); |
411 brd.copy(randBoard); |
412 randBoard.set(i, j, 1); |
412 randBoard.set(i, j, 1); |
451 * @property {number} edgeBonus bonus for max value at board edge |
451 * @property {number} edgeBonus bonus for max value at board edge |
452 * @property {number} freeBonus bonus for each free cell |
452 * @property {number} freeBonus bonus for each free cell |
453 */ |
453 */ |
454 |
454 |
455 /** N level deep with random simulation. |
455 /** N level deep with random simulation. |
456 * @param {Board} brdEngine board engine from board.js |
456 * @param {Board} brd board engine from board.js |
457 * @param {ai.survive.cfg} cfg configuration settings |
457 * @param {ai.survive.cfg} cfg configuration settings |
458 * @constructor */ |
458 * @constructor */ |
459 ai.survive = function(brdEngine, cfg) { |
459 ai.survive = function(brd, cfg) { |
460 this.brdEngine = brdEngine; |
460 this.brd = brd; |
461 this.cfg = ai.copyObj(ai.survive.bestCfg); |
461 this.cfg = ai.copyObj(ai.survive.bestCfg); |
462 ai.copyObj(cfg, this.cfg); |
462 ai.copyObj(cfg, this.cfg); |
463 if (this.cfg.freeCells <= 0) |
463 if (this.cfg.freeCells <= 0) |
464 this.cfg.freeCells = ai.survive.bestCfg.freeCells; |
464 this.cfg.freeCells = ai.survive.bestCfg.freeCells; |
465 if (!this.cfg.maxDepth || this.cfg.maxDepth < 0 || 20 <= this.cfg.maxDepth) |
465 if (!this.cfg.maxDepth || this.cfg.maxDepth < 0 || 20 <= this.cfg.maxDepth) |
466 this.cfg.maxDepth = ai.survive.bestCfg.maxDepth; |
466 this.cfg.maxDepth = ai.survive.bestCfg.maxDepth; |
467 this.cfg.altAI = new ai.StaticDeepMerges(brdEngine, ai.survive.altAICfg); |
467 this.cfg.altAI = new ai.StaticDeepMerges(brd, ai.survive.altAICfg); |
468 } |
468 } |
469 ai.survive.bestCfg = {freeCells: 8, maxDepth: 5}; |
469 ai.survive.bestCfg = {freeCells: 8, maxDepth: 5}; |
470 ai.survive.altAICfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, utilityThreshold: 0}; |
470 ai.survive.altAICfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, utilityThreshold: 0}; |
471 /** Select best direction for next step. */ |
471 /** Select best direction for next step. */ |
472 ai.survive.prototype.analyse = function(brd2d) { |
472 ai.survive.prototype.analyse = function(brd2d) { |
473 var origBrd = new this.brdEngine(brd2d); |
473 var origBrd = new this.brd(brd2d); |
474 var nextBrd = new this.brdEngine(); |
474 var nextBrd = new this.brd(); |
475 var bestW = -2; |
475 var bestW = -2; |
476 var bestDir; |
476 var bestDir; |
477 var freeCnt = origBrd.freeCnt(); |
477 var freeCnt = origBrd.freeCnt(); |
478 if (freeCnt >= this.cfg.freeCells) |
478 if (freeCnt >= this.cfg.freeCells) |
479 return this.cfg.altAI.analyse(brd2d); |
479 return this.cfg.altAI.analyse(brd2d); |
493 if (brd.freeCnt() >= this.cfg.freeCells) |
493 if (brd.freeCnt() >= this.cfg.freeCells) |
494 return 1; |
494 return 1; |
495 if (depth >= this.cfg.maxDepth) |
495 if (depth >= this.cfg.maxDepth) |
496 return 0; |
496 return 0; |
497 var wMin = +Infinity; |
497 var wMin = +Infinity; |
498 var randBoard = new this.brdEngine(); |
498 var randBoard = new this.brd(); |
499 var nextBrd = new this.brdEngine(); |
499 var nextBrd = new this.brd(); |
500 exit: |
500 exit: |
501 for (var i = 0; i < 3; i++) { |
501 for (var i = 0; i < 3; i++) { |
502 for (var j = 0; j < 3; j++) { |
502 for (var j = 0; j < 3; j++) { |
503 if (brd.get(i, j) !== 0) |
503 if (brd.get(i, j) !== 0) |
504 continue; |
504 continue; |