2 |
2 |
3 /** @fileOverview AI modules. */ |
3 /** @fileOverview AI modules. */ |
4 |
4 |
5 /** @module */ |
5 /** @module */ |
6 var ai = {}; |
6 var ai = {}; |
|
7 |
7 /** Directions. @constant */ |
8 /** Directions. @constant */ |
8 ai.dirs = ["up", "right", "down", "left"]; |
9 ai.dirs = ["up", "right", "down", "left"]; |
|
10 /** Directions in random order. */ |
|
11 ai.randDirs = function() { |
|
12 var idxs = [0, 1, 2, 3]; |
|
13 for (var i = idxs.length - 1; i > 0; i--) { |
|
14 var j = Math.floor(Math.random()*(i+1)); |
|
15 var swap = idxs[j]; idxs[j] = idxs[i]; idxs[i] = swap; |
|
16 } |
|
17 return [ai.dirs[idxs[0]], ai.dirs[idxs[1]], ai.dirs[idxs[2]], ai.dirs[idxs[3]]]; |
|
18 } |
|
19 |
9 /** Possible direction check function names ordered by ai.dirs. @constant */ |
20 /** Possible direction check function names ordered by ai.dirs. @constant */ |
10 ai.canFn = ["canUp", "canRight", "canDown", "canLeft"]; |
21 ai.canFn = ["canUp", "canRight", "canDown", "canLeft"]; |
11 /** Possible merge function names ordered by ai.dirs. @constant */ |
22 /** Possible merge function names ordered by ai.dirs. @constant */ |
12 ai.mergeFn = ["upMerges", "rightMerges", "downMerges", "leftMerges"]; |
23 ai.mergeFn = ["upMerges", "rightMerges", "downMerges", "leftMerges"]; |
13 |
24 |
528 } |
539 } |
529 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */ |
540 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */ |
530 ai.survive.prototype.cleanup = function() { |
541 ai.survive.prototype.cleanup = function() { |
531 } |
542 } |
532 |
543 |
|
544 |
|
545 |
|
546 //////////////////////////////////////////////////////////////// |
|
547 // MonteCarlo simulations. |
|
548 //////////////////////////////////////////////////////////////// |
|
549 |
|
550 /** |
|
551 * Defines coefficient for linear resulted weight function. |
|
552 * @name ai.MonteCarlo.cfg |
|
553 * @namespace |
|
554 * @property {number} maxDepth depth limit |
|
555 * @property {number} simulations simulation count limit |
|
556 */ |
|
557 |
|
558 /** MonteCarlo simulations. |
|
559 * @param {Board} brd board engine from board.js |
|
560 * @param {ai.MonteCarlo.cfg} cfg configuration settings |
|
561 * @constructor */ |
|
562 ai.MonteCarlo = function(brd, cfg) { |
|
563 this.brd = brd; |
|
564 this.cfg = ai.copyObj(ai.MonteCarlo.bestCfg); |
|
565 ai.copyObj(cfg, this.cfg); |
|
566 if (this.cfg.simulations <= 0) |
|
567 this.cfg.simulations = ai.MonteCarlo.bestCfg.simulations; |
|
568 if (!this.cfg.maxDepth || this.cfg.maxDepth <= 0 || 20 <= this.cfg.maxDepth) |
|
569 this.cfg.maxDepth = ai.MonteCarlo.bestCfg.maxDepth; |
|
570 } |
|
571 ai.MonteCarlo.bestCfg = {simulations: 1000, maxDepth: 20}; |
|
572 /** Select best direction for next step. */ |
|
573 ai.MonteCarlo.prototype.analyse = function(brd2d) { |
|
574 var origBrd = new this.brd(brd2d); |
|
575 var nextBrd = new this.brd(); |
|
576 var bestW = - this.cfg.simulations; |
|
577 var bestDir; |
|
578 var freeCnt = origBrd.freeCnt(); |
|
579 for (var i = 0; i < ai.dirs.length; i++) { |
|
580 var dir = ai.dirs[i]; |
|
581 if (origBrd[dir](nextBrd)) { |
|
582 var w = 0; |
|
583 for (var gameCnt = this.cfg.simulations; gameCnt > 0; gameCnt--) { |
|
584 var tmpBrd = nextBrd.copy(); |
|
585 w += this.play(tmpBrd, this.cfg.maxDepth); |
|
586 } |
|
587 if (w > bestW) { |
|
588 bestW = w; |
|
589 bestDir = dir; |
|
590 } |
|
591 } |
|
592 } |
|
593 return bestDir; |
|
594 } |
|
595 ai.MonteCarlo.prototype.play = function(brd, depth) { |
|
596 if (depth <= 0) { |
|
597 return brd.freeCnt(); |
|
598 } |
|
599 brd.rnd(1); |
|
600 var dirs = ai.randDirs(); |
|
601 for (var i = 0; i < 4; i++) { |
|
602 var dir = dirs[i]; |
|
603 var nextBrd = new brd.constructor(); |
|
604 if (brd[dir](nextBrd)) { |
|
605 return this.play(nextBrd, depth-1); |
|
606 } |
|
607 } |
|
608 return -1; |
|
609 } |
|
610 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */ |
|
611 ai.MonteCarlo.prototype.cleanup = function() { |
|
612 } |
|
613 |