376 * @param {Board} brdEngine board engine from board.js |
376 * @param {Board} brdEngine board engine from board.js |
377 * @param {ai.expectimax.cfg} cfg configuration settings |
377 * @param {ai.expectimax.cfg} cfg configuration settings |
378 * @constructor */ |
378 * @constructor */ |
379 ai.expectimax = function(brdEngine, cfg) { |
379 ai.expectimax = function(brdEngine, cfg) { |
380 this.brdEngine = brdEngine; |
380 this.brdEngine = brdEngine; |
381 this.cfg = cfg || {}; |
381 this.cfg = ai.copyObj(ai.expectimax.bestCfg); |
382 this.cfg.balance = this.cfg.balance || .9; |
382 ai.copyObj(cfg, this.cfg); |
|
383 if (this.cfg.balance <= 0) |
|
384 this.cfg.balance = ai.expectimax.bestCfg.balance; |
|
385 if ( this.cfg.balance > 1) |
|
386 this.cfg.balance = 1; |
383 if (!this.cfg.depth || this.cfg.depth < 0 || 8 <= this.cfg.depth) |
387 if (!this.cfg.depth || this.cfg.depth < 0 || 8 <= this.cfg.depth) |
384 this.cfg.depth = 5; |
388 this.cfg.depth = ai.expectimax.bestCfg.depth; |
385 this.cfg.cornerBonus = this.cfg.cornerBonus || 20000; |
389 } |
386 this.cfg.edgeBonus = this.cfg.edgeBonus || 100; |
390 ai.expectimax.bestCfg = {balance: .9, depth: 3, scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, weightPriority: 10}; |
387 this.cfg.freeBonus = this.cfg.edgeBonus || 100; |
391 ai.expectimax.prototype.weight = function(brd) { |
388 this.cfg.weightPriority = this.cfg.weightPriority || 10; |
392 var score = 0; |
389 } |
393 if (this.cfg.scoreCoef > 0) |
390 ai.expectimax.prototype.lvl1Score = function(brd) { |
394 score += this.cfg.scoreCoef * brd.score(); |
391 var score = brd.score(); |
|
392 var max = brd.max(); |
395 var max = brd.max(); |
393 if (brd.atCorner(max)) |
396 if (this.cfg.maxValCoef > 0) |
394 score += this.cfg.cornerBonus; |
397 score += this.cfg.maxValCoef * max; |
395 else if (brd.atEdge(max)) |
398 if (this.cfg.cornerBonus > 0) |
396 score += this.cfg.edgeBonus; |
399 if (brd.atCorner(max)) |
397 score += brd.free() * this.cfg.freeBonus; |
400 score += this.cfg.cornerBonus; |
398 return score; |
401 if (this.cfg.edgeBonus > 0) |
399 } |
402 if (brd.atEdge(max)) |
400 ai.expectimax.prototype.lvlnScore = function(brd) { |
403 score += this.cfg.edgeBonus; |
401 var score = brd.score(); |
404 if (this.cfg.freeBonus > 0) |
402 // var max = brd.max(); |
405 score += this.cfg.freeBonus * brd.free(); |
403 // if (brd.atCorner(max)) |
|
404 // score += this.cfg.cornerBonus; |
|
405 // else if (brd.atEdge(max)) |
|
406 // score += this.cfg.edgeBonus; |
|
407 // score += brd.free() * this.cfg.freeBonus; |
|
408 return score; |
406 return score; |
409 } |
407 } |
410 ai.expectimax.prototype.analyse = function(brd) { |
408 ai.expectimax.prototype.analyse = function(brd) { |
411 var origBrd = new this.brdEngine(brd); |
409 var origBrd = new this.brdEngine(brd); |
412 var nextBrd = new this.brdEngine(); |
410 var nextBrd = new this.brdEngine(); |
415 var bestDir; |
413 var bestDir; |
416 this.cleanup(); |
414 this.cleanup(); |
417 for (var i = 0; i < ai.dirs.length; i++) { |
415 for (var i = 0; i < ai.dirs.length; i++) { |
418 var dir = ai.dirs[i]; |
416 var dir = ai.dirs[i]; |
419 if (origBrd[dir](nextBrd)) { |
417 if (origBrd[dir](nextBrd)) { |
420 nextScore = this.lvl1Score(nextBrd); |
418 var weight = this.recWeight(nextBrd, 1); |
421 var weight = this.weight(nextBrd, 0); |
419 var ok = (weight - maxWeight) > this.cfg.weightPriority; |
422 // console.log("dir: %o, prevScore: %o, nextScore: %o, maxWeight: %o, weight: %o", dir, prevScore, nextScore, maxWeight, weight); |
420 if ( ! ok && maxWeight <= weight) { |
423 if (maxWeight + this.cfg.weightPriority < weight || (maxWeight <= weight && prevScore < nextScore)) { |
421 nextScore = this.weight(nextBrd); |
|
422 ok = prevScore < nextScore; |
|
423 } |
|
424 if (ok) { |
424 prevScore = nextScore; |
425 prevScore = nextScore; |
425 maxWeight = weight; |
426 maxWeight = weight; |
426 bestDir = dir; |
427 bestDir = dir; |
427 } |
428 } |
428 } |
429 } |
429 } |
430 } |
430 this.cleanup(); |
431 this.cleanup(); |
431 return bestDir; |
432 return bestDir; |
432 } |
433 } |
433 ai.expectimax.prototype.weight = function(brd, depth) { |
434 ai.expectimax.prototype.recWeight = function(brd, depth) { |
434 if (depth === this.cfg.depth) |
435 if (depth >= this.cfg.depth) |
435 return this.lvlnScore(brd); |
436 return this.weight(brd); |
436 if (this.cache[depth]) { |
437 if (this.cache[depth]) { |
437 var cache = this.cache[depth]; |
438 var cache = this.cache[depth]; |
438 for (var i = cache.length-1; i >= 0; i--) { |
439 for (var i = cache.length-1; i >= 0; i--) { |
439 if (brd.equals(cache[i].brd)) |
440 if (brd.equals(cache[i].brd)) |
440 return cache[i].weight; |
441 return cache[i].weight; |
451 randBoard.set(i, j, 1); |
452 randBoard.set(i, j, 1); |
452 var nextBrd = new this.brdEngine(); |
453 var nextBrd = new this.brdEngine(); |
453 var n = 0, w = 0; |
454 var n = 0, w = 0; |
454 for (var diri = 0; diri < ai.dirs.length; diri++) { |
455 for (var diri = 0; diri < ai.dirs.length; diri++) { |
455 if (randBoard[ai.dirs[diri]](nextBrd)) { |
456 if (randBoard[ai.dirs[diri]](nextBrd)) { |
456 w += this.weight(nextBrd, depth+1); |
457 w += this.recWeight(nextBrd, depth+1); |
457 n++; |
458 n++; |
458 } |
459 } |
459 } |
460 } |
460 if (n > 0) |
461 if (n > 0) |
461 w = w / n; |
462 w = w / n; |
462 weight += this.cfg.balance * w; |
463 weight += this.cfg.balance * w; |
463 randBoard.set(i, j, 2); |
464 if (this.cfg.balance < 1) { |
464 var n = 0, w = 0; |
465 randBoard.set(i, j, 2); |
465 for (var diri = 0; diri < ai.dirs.length; diri++) { |
466 var n = 0, w = 0; |
466 if (randBoard[ai.dirs[diri]](nextBrd)) { |
467 for (var diri = 0; diri < ai.dirs.length; diri++) { |
467 w += this.weight(nextBrd, depth+1); |
468 if (randBoard[ai.dirs[diri]](nextBrd)) { |
468 n++; |
469 w += this.recWeight(nextBrd, depth+1); |
|
470 n++; |
|
471 } |
469 } |
472 } |
|
473 if (n > 0) |
|
474 w = w / n; |
|
475 weight += this.cfg.balance * w; |
470 } |
476 } |
471 if (n > 0) |
|
472 w = w / n; |
|
473 weight += this.cfg.balance * w; |
|
474 free++; |
477 free++; |
475 } |
478 } |
476 } |
479 } |
477 } |
480 } |
478 if (free > 0) |
481 if (free > 0) |