171 } |
171 } |
172 |
172 |
173 |
173 |
174 |
174 |
175 //////////////////////////////////////////////////////////////// |
175 //////////////////////////////////////////////////////////////// |
176 // 1 step deep with linear weight function on score, max value, |
176 // 1 step deep with linear utility function on score, max value, |
177 // bonuses for max value stay at corner or edge and bonuses |
177 // bonuses for max value stay at corner or edge and bonuses |
178 // for each free field. |
178 // for each free field. |
179 //////////////////////////////////////////////////////////////// |
179 //////////////////////////////////////////////////////////////// |
180 |
180 |
181 /** |
181 /** |
182 * Defines coefficient for linear resulted weight function. |
182 * Defines coefficient for linear resulted utility function. |
183 * @name ai.OneStepAhead.cfg |
183 * @name ai.OneStepAhead.cfg |
184 * @namespace |
184 * @namespace |
185 * @property {number} scoreCoef multiplicator for score |
185 * @property {number} scoreCoef multiplicator for score |
186 * @property {number} maxValCoef multiplicator for max value |
186 * @property {number} maxValCoef multiplicator for max value |
187 * @property {number} cornerBonus bonus for max value at board corner |
187 * @property {number} cornerBonus bonus for max value at board corner |
197 this.brdEngine = brdEngine; |
197 this.brdEngine = brdEngine; |
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.weight = function(brd) { |
202 ai.OneStepAhead.prototype.utility = function(brd) { |
203 var weight = 0; |
203 var utility = 0; |
204 if (this.cfg.scoreCoef > 0) |
204 if (this.cfg.scoreCoef > 0) |
205 weight += this.cfg.scoreCoef * brd.score(); |
205 utility += this.cfg.scoreCoef * brd.score(); |
206 var max = brd.maxVal(); |
206 var max = brd.maxVal(); |
207 if (this.cfg.maxValCoef > 0) |
207 if (this.cfg.maxValCoef > 0) |
208 weight += this.cfg.maxValCoef * max; |
208 utility += this.cfg.maxValCoef * max; |
209 if (this.cfg.cornerBonus > 0 && brd.atCorner(max)) |
209 if (this.cfg.cornerBonus > 0 && brd.atCorner(max)) |
210 weight += this.cfg.cornerBonus; |
210 utility += this.cfg.cornerBonus; |
211 if (this.cfg.edgeBonus > 0 && brd.atEdge(max)) |
211 if (this.cfg.edgeBonus > 0 && brd.atEdge(max)) |
212 weight += this.cfg.edgeBonus; |
212 utility += this.cfg.edgeBonus; |
213 if (this.cfg.freeBonus > 0) |
213 if (this.cfg.freeBonus > 0) |
214 weight += this.cfg.freeBonus * brd.freeCnt(); |
214 utility += this.cfg.freeBonus * brd.freeCnt(); |
215 return weight; |
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.brdEngine(brd2d); |
220 var nextBrd = new this.brdEngine(); |
220 var nextBrd = new this.brdEngine(); |
221 var maxWeight = -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)) { |
226 var weight = this.weight(nextBrd); |
226 var utility = this.utility(nextBrd); |
227 if (maxWeight < weight) { |
227 if (maxUtility < utility) { |
228 bestDir = dir; |
228 bestDir = dir; |
229 maxWeight = weight; |
229 maxUtility = utility; |
230 } |
230 } |
231 } |
231 } |
232 } |
232 } |
233 return bestDir; |
233 return bestDir; |
234 } |
234 } |
259 ai.StaticDeepMerges = function(brdEngine, cfg) { |
259 ai.StaticDeepMerges = function(brdEngine, cfg) { |
260 this.brdEngine = brdEngine; |
260 this.brdEngine = brdEngine; |
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, weightThreshold: 10}; |
264 ai.StaticDeepMerges.bestCfg = {scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0, utilityThreshold: 10}; |
265 ai.StaticDeepMerges.prototype.weight = function(brd) { |
265 ai.StaticDeepMerges.prototype.utility = function(brd) { |
266 var weight = 0; |
266 var utility = 0; |
267 if (this.cfg.scoreCoef > 0) |
267 if (this.cfg.scoreCoef > 0) |
268 weight += this.cfg.scoreCoef * brd.score(); |
268 utility += this.cfg.scoreCoef * brd.score(); |
269 var max = brd.maxVal(); |
269 var max = brd.maxVal(); |
270 if (this.cfg.maxValCoef > 0) |
270 if (this.cfg.maxValCoef > 0) |
271 weight += this.cfg.maxValCoef * max; |
271 utility += this.cfg.maxValCoef * max; |
272 if (this.cfg.cornerBonus > 0 && brd.atCorner(max)) |
272 if (this.cfg.cornerBonus > 0 && brd.atCorner(max)) |
273 weight += this.cfg.cornerBonus; |
273 utility += this.cfg.cornerBonus; |
274 if (this.cfg.edgeBonus > 0 && brd.atEdge(max)) |
274 if (this.cfg.edgeBonus > 0 && brd.atEdge(max)) |
275 weight += this.cfg.edgeBonus; |
275 utility += this.cfg.edgeBonus; |
276 if (this.cfg.freeBonus > 0) |
276 if (this.cfg.freeBonus > 0) |
277 weight += this.cfg.freeBonus * brd.freeCnt(); |
277 utility += this.cfg.freeBonus * brd.freeCnt(); |
278 return weight; |
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.brdEngine(brd2d); |
283 var nextBrd = new this.brdEngine(); |
283 var nextBrd = new this.brdEngine(); |
284 var prevScore = -1, nextScore = -1; |
284 var prevScore = -1, nextScore = -1; |
285 var maxWeight = -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]; |
289 if (origBrd[dir](nextBrd)) { |
289 if (origBrd[dir](nextBrd)) { |
290 var weight = this.evalFn(nextBrd); |
290 var utility = this.evalFn(nextBrd); |
291 var ok = (weight - maxWeight) > this.cfg.weightThreshold; |
291 var ok = (utility - maxUtility) > this.cfg.utilityThreshold; |
292 if ( ! ok && maxWeight <= weight) { |
292 if ( ! ok && maxUtility <= utility) { |
293 nextScore = this.weight(nextBrd); |
293 nextScore = this.utility(nextBrd); |
294 ok = prevScore < nextScore; |
294 ok = prevScore < nextScore; |
295 } |
295 } |
296 if (ok) { |
296 if (ok) { |
297 prevScore = nextScore; |
297 prevScore = nextScore; |
298 maxWeight = weight; |
298 maxUtility = utility; |
299 bestDir = dir; |
299 bestDir = dir; |
300 } |
300 } |
301 } |
301 } |
302 } |
302 } |
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 maxWeight = currScore; |
307 var maxUtility = currScore; |
308 var nextBrd = new this.brdEngine(); |
308 var nextBrd = new this.brdEngine(); |
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 maxWeight = Math.max(maxWeight, this.evalFn(nextBrd)); |
313 maxUtility = Math.max(maxUtility, this.evalFn(nextBrd)); |
314 } |
314 } |
315 } |
315 } |
316 return maxWeight; |
316 return maxUtility; |
317 } |
317 } |
318 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */ |
318 /* Mark that next board will be unrelated to previous, so any stored precompution can be cleared. */ |
319 ai.StaticDeepMerges.prototype.cleanup = function() { } |
319 ai.StaticDeepMerges.prototype.cleanup = function() { } |
320 |
320 |
321 |
321 |
349 this.cfg.balance = 1; |
349 this.cfg.balance = 1; |
350 if (!this.cfg.depth || this.cfg.depth < 0 || 9 <= this.cfg.depth) |
350 if (!this.cfg.depth || this.cfg.depth < 0 || 9 <= this.cfg.depth) |
351 this.cfg.depth = ai.expectimax.bestCfg.depth; |
351 this.cfg.depth = ai.expectimax.bestCfg.depth; |
352 } |
352 } |
353 ai.expectimax.bestCfg = {balance: .9, depth: 5, scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0}; |
353 ai.expectimax.bestCfg = {balance: .9, depth: 5, scoreCoef: 1, maxValCoef: 0, cornerBonus: 0, edgeBonus: 0, freeBonus: 0}; |
354 ai.expectimax.prototype.weight = function(brd) { |
354 ai.expectimax.prototype.utility = function(brd) { |
355 var score = 0; |
355 var score = 0; |
356 var cfg = this.cfg; |
356 var cfg = this.cfg; |
357 if (cfg.scoreCoef > 0) |
357 if (cfg.scoreCoef > 0) |
358 score += cfg.scoreCoef * brd.score(); |
358 score += cfg.scoreCoef * brd.score(); |
359 if (cfg.maxValCoef > 0 || cfg.cornerBonus > 0 || cfg.edgeBonus > 0) { |
359 if (cfg.maxValCoef > 0 || cfg.cornerBonus > 0 || cfg.edgeBonus > 0) { |
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(brdEngine, 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, weightThreshold: 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.brdEngine(brd2d); |
474 var nextBrd = new this.brdEngine(); |
474 var nextBrd = new this.brdEngine(); |
475 var bestW = -2; |
475 var bestW = -2; |