From 9e42b4dd8a70b9593cc44ab181b4df32032ca250 Mon Sep 17 00:00:00 2001 From: Benjamin Auder <benjamin.auder@somewhere> Date: Mon, 26 Nov 2018 12:39:13 +0100 Subject: [PATCH] SPeed-up checkmate and king capture for Magnetic chess --- public/javascripts/base_rules.js | 43 +++++++++++++++++-------- public/javascripts/variants/Magnetic.js | 19 +++++++++++ 2 files changed, 48 insertions(+), 14 deletions(-) diff --git a/public/javascripts/base_rules.js b/public/javascripts/base_rules.js index 85689369..9cfab5ae 100644 --- a/public/javascripts/base_rules.js +++ b/public/javascripts/base_rules.js @@ -785,17 +785,28 @@ class ChessRules }; } + static get INFINITY() { + return 9999; //"checkmate" (unreachable eval) + } + + static get THRESHOLD_MATE() { + // At this value or above, the game is over + return VariantRules.INFINITY; + } + // Assumption: at least one legal move - getComputerMove() + getComputerMove(moves1) //moves1 might be precomputed (Magnetic chess) { + const maxeval = VariantRules.INFINITY; const color = this.turn; - let moves1 = this.getAllValidMoves(); + if (!moves1) + moves1 = this.getAllValidMoves(); // Rank moves using a min-max at depth 2 for (let i=0; i<moves1.length; i++) { - moves1[i].eval = (color=="w" ? -1 : 1) * 1000; //very low, I'm checkmated - let eval2 = (color=="w" ? 1 : -1) * 1000; //initialized with very high (checkmate) value + moves1[i].eval = (color=="w" ? -1 : 1) * maxeval; //very low, I'm checkmated + let eval2 = (color=="w" ? 1 : -1) * maxeval; //initialized with checkmate value this.play(moves1[i]); // Second half-move: let moves2 = this.getAllValidMoves(); @@ -817,39 +828,43 @@ class ChessRules } moves1.sort( (a,b) => { return (color=="w" ? 1 : -1) * (b.eval - a.eval); }); - // TODO: show current analyzed move for depth 3, allow stopping eval (return moves1[0]) - for (let i=0; i<moves1.length; i++) + // Skip depth 3 if we found a checkmate (or if we are checkmated in 1...) + if (Math.abs(moves1[0].eval) < VariantRules.THRESHOLD_MATE) { - this.play(moves1[i]); - // 0.1 * oldEval : heuristic to avoid some bad moves (not all...) - moves1[i].eval = 0.1*moves1[i].eval + this.alphabeta(2, -1000, 1000); - this.undo(moves1[i]); + // TODO: show current analyzed move for depth 3, allow stopping eval (return moves1[0]) + for (let i=0; i<moves1.length; i++) + { + this.play(moves1[i]); + // 0.1 * oldEval : heuristic to avoid some bad moves (not all...) + moves1[i].eval = 0.1*moves1[i].eval + this.alphabeta(2, -maxeval, maxeval); + this.undo(moves1[i]); + } + moves1.sort( (a,b) => { return (color=="w" ? 1 : -1) * (b.eval - a.eval); }); } - moves1.sort( (a,b) => { return (color=="w" ? 1 : -1) * (b.eval - a.eval); }); let candidates = [0]; //indices of candidates moves for (let j=1; j<moves1.length && moves1[j].eval == moves1[0].eval; j++) candidates.push(j); - // console.log(moves1.map(m => { return [this.getNotation(m), m.eval]; })); return moves1[_.sample(candidates, 1)]; } alphabeta(depth, alpha, beta) { + const maxeval = VariantRules.INFINITY; const color = this.turn; if (!this.atLeastOneMove()) { switch (this.checkGameEnd()) { case "1/2": return 0; - default: return color=="w" ? -1000 : 1000; + default: return color=="w" ? -maxeval : maxeval; } } if (depth == 0) return this.evalPosition(); const moves = this.getAllValidMoves(); - let v = color=="w" ? -1000 : 1000; + let v = color=="w" ? -maxeval : maxeval; if (color == "w") { for (let i=0; i<moves.length; i++) diff --git a/public/javascripts/variants/Magnetic.js b/public/javascripts/variants/Magnetic.js index d1436c0f..e126f1ce 100644 --- a/public/javascripts/variants/Magnetic.js +++ b/public/javascripts/variants/Magnetic.js @@ -212,4 +212,23 @@ class MagneticRules extends ChessRules // No valid move: our king disappeared return this.turn == "w" ? "0-1" : "1-0"; } + + static get THRESHOLD_MATE() { + return 500; //checkmates evals may be slightly below 1000 + } + + getComputerMove() + { + let moves1 = this.getAllValidMoves(); + // Can I mate in 1 ? + for (let i of _.shuffle(_.range(moves1.length))) + { + this.play(moves1[i]); + const finish = (Math.abs(this.evalPosition()) >= VariantRules.THRESHOLD_MATE); + this.undo(moves1[i]); + if (finish) + return moves1[i]; + } + return super.getComputerMove(moves1); + } } -- 2.44.0