From 1ef133c52d12daf3fdad1d979e5a71cb39fa0d2e Mon Sep 17 00:00:00 2001 From: Yann Granjon Date: Wed, 5 Jun 2013 16:13:15 +0200 Subject: Initial Commit --- js/AI/boardui.js | 409 + js/AI/garbochess.js | 2738 +++ js/AI/garbochess_unclean.js | 2538 ++ js/Cell.js | 116 + js/chess.js | 596 + js/factory.js | 420 + js/geoPieces.js | 279 + js/gui.js | 545 + js/jquery/jquery-1.9.1.js | 9597 ++++++++ js/jquery/jquery-ui-1.10.3.custom.js | 14971 ++++++++++++ js/jquery/jquery-ui-1.10.3.custom.min.js | 7 + js/lib/OrbitAndPanControls.js | 456 + js/lib/three.js | 36506 +++++++++++++++++++++++++++++ js/lib/three.min.js | 710 + js/loading.js | 308 + js/pgnParser.js | 122 + js/three-extend.js | 27 + 17 files changed, 70345 insertions(+) create mode 100644 js/AI/boardui.js create mode 100644 js/AI/garbochess.js create mode 100644 js/AI/garbochess_unclean.js create mode 100644 js/Cell.js create mode 100644 js/chess.js create mode 100644 js/factory.js create mode 100644 js/geoPieces.js create mode 100644 js/gui.js create mode 100644 js/jquery/jquery-1.9.1.js create mode 100644 js/jquery/jquery-ui-1.10.3.custom.js create mode 100644 js/jquery/jquery-ui-1.10.3.custom.min.js create mode 100644 js/lib/OrbitAndPanControls.js create mode 100644 js/lib/three.js create mode 100644 js/lib/three.min.js create mode 100644 js/loading.js create mode 100644 js/pgnParser.js create mode 100644 js/three-extend.js (limited to 'js') diff --git a/js/AI/boardui.js b/js/AI/boardui.js new file mode 100644 index 0000000..795958a --- /dev/null +++ b/js/AI/boardui.js @@ -0,0 +1,409 @@ +var g_startOffset = null; +var g_selectedPiece = null; +var moveNumber = 1; + +var g_allMoves = []; +var g_playerWhite = true; +var g_changingFen = false; +var g_analyzing = false; + +var g_uiBoard; +var g_cellSize = 45; + +function UINewGame() { + moveNumber = 1; + + var pgnTextBox = document.getElementById("PgnTextBox"); // + pgnTextBox.value = ""; + + EnsureAnalysisStopped(); // UI (terminate and destroy worker) + ResetGame(); // shouldn't work + if (InitializeBackgroundEngine()) { + g_backgroundEngine.postMessage("go"); + } + g_allMoves = []; + RedrawBoard(); //UI + + // if player is black play the first move + if (!g_playerWhite) { + SearchAndRedraw(); //UI + } +} + +function EnsureAnalysisStopped() { + if (g_analyzing && g_backgroundEngine != null) { + g_backgroundEngine.terminate(); + g_backgroundEngine = null; + } +} + +function UIAnalyzeToggle() { + if (InitializeBackgroundEngine()) { + if (!g_analyzing) { + g_backgroundEngine.postMessage("analyze"); + } else { + EnsureAnalysisStopped(); + } + g_analyzing = !g_analyzing; + document.getElementById("AnalysisToggleLink").innerText = g_analyzing ? "Analysis: On" : "Analysis: Off"; + } else { + alert("Your browser must support web workers for analysis - (chrome4, ff4, safari)"); + } +} + +function UIChangeFEN() { + if (!g_changingFen) { + var fenTextBox = document.getElementById("FenTextBox"); + var result = InitializeFromFen(fenTextBox.value); + if (result.length != 0) { + UpdatePVDisplay(result); + return; + } else { + UpdatePVDisplay(''); + } + g_allMoves = []; + + EnsureAnalysisStopped(); + InitializeBackgroundEngine(); + + g_playerWhite = !!g_toMove; + g_backgroundEngine.postMessage("position " + GetFen()); + + RedrawBoard(); + } +} + +function UIChangeStartPlayer() { + g_playerWhite = !g_playerWhite; + RedrawBoard(); +} + +function UpdatePgnTextBox(move) { + var pgnTextBox = document.getElementById("PgnTextBox"); + if (g_toMove != 0) { + pgnTextBox.value += moveNumber + ". "; + moveNumber++; + } + pgnTextBox.value += GetMoveSAN(move) + " "; +} + +function UIChangeTimePerMove() { + var timePerMove = document.getElementById("TimePerMove"); + g_timeout = parseInt(timePerMove.value, 10); +} + +function FinishMove(bestMove, value, timeTaken, ply) { + if (bestMove != null) { + UIPlayMove(bestMove, BuildPVMessage(bestMove, value, timeTaken, ply)); + } else { + alert("Checkmate!"); + } +} + +function UIPlayMove(move, pv) { + UpdatePgnTextBox(move); + + g_allMoves[g_allMoves.length] = move; + MakeMove(move); + + UpdatePVDisplay(pv); + + UpdateFromMove(move); +} + + +// buggy doesn't update the pgn properly +function UIUndoMove() { + if (g_allMoves.length == 0) { + return; + } + + if (g_backgroundEngine != null) { + g_backgroundEngine.terminate(); + g_backgroundEngine = null; + } + + UnmakeMove(g_allMoves[g_allMoves.length - 1]); + g_allMoves.pop(); + + if (g_playerWhite !== !!g_toMove && g_allMoves.length !== 0) { + UnmakeMove(g_allMoves[g_allMoves.length - 1]); + g_allMoves.pop(); + } + + RedrawBoard(); +} + +function UpdatePVDisplay(pv) { + if (pv != null) { + var outputDiv = document.getElementById("output"); + if (outputDiv.firstChild != null) { + outputDiv.removeChild(outputDiv.firstChild); + } + outputDiv.appendChild(document.createTextNode(pv)); + } +} + +function SearchAndRedraw() { + if (g_analyzing) { + EnsureAnalysisStopped(); + InitializeBackgroundEngine(); + g_backgroundEngine.postMessage("position " + GetFen()); + g_backgroundEngine.postMessage("analyze"); + return; + } + + if (InitializeBackgroundEngine()) { + g_backgroundEngine.postMessage("search " + g_timeout); + } else { + Search(FinishMove, 99, null); // unasynchronous version fall back + } +} + +var g_backgroundEngineValid = true; +var g_backgroundEngine; + +function InitializeBackgroundEngine() { + if (!g_backgroundEngineValid) { + return false; + } + + if (g_backgroundEngine == null) { + g_backgroundEngineValid = true; + try { + g_backgroundEngine = new Worker("js/garbochess.js"); + g_backgroundEngine.onmessage = function (e) { + if (e.data.match("^pv") == "pv") { + UpdatePVDisplay(e.data.substr(3, e.data.length - 3)); + } else if (e.data.match("^message") == "message") { + EnsureAnalysisStopped(); + UpdatePVDisplay(e.data.substr(8, e.data.length - 8)); + } else { + UIPlayMove(GetMoveFromString(e.data), null); + } + } + g_backgroundEngine.error = function (e) { + alert("Error from background worker:" + e.message); + } + g_backgroundEngine.postMessage("position " + GetFen()); + } catch (error) { + g_backgroundEngineValid = false; + } + } + + return g_backgroundEngineValid; +} + +function UpdateFromMove(move) { + var fromX = (move & 0xF) - 4; + var fromY = ((move >> 4) & 0xF) - 2; + var toX = ((move >> 8) & 0xF) - 4; + var toY = ((move >> 12) & 0xF) - 2; + + if (!g_playerWhite) { + fromY = 7 - fromY; + toY = 7 - toY; + fromX = 7 - fromX; + toX = 7 - toX; + } + + if ((move & moveflagCastleKing) || + (move & moveflagCastleQueen) || + (move & moveflagEPC) || + (move & moveflagPromotion)) { + // more than one piece was moved + // or one piece was modified + // -> entire redraw + RedrawPieces(); + } else { + // simply swap piece parents + var fromSquare = g_uiBoard[fromY * 8 + fromX]; + $(g_uiBoard[toY * 8 + toX]) + .empty() + .append($(fromSquare).children()); + } +} + +function RedrawPieces() { + for (y = 0; y < 8; ++y) { + for (x = 0; x < 8; ++x) { + var td = g_uiBoard[y * 8 + x]; + var pieceY = g_playerWhite ? y : 7 - y; + var piece = g_board[((pieceY + 2) * 0x10) + (g_playerWhite ? x : 7 - x) + 4]; + var pieceName = null; + switch (piece & 0x7) { + case piecePawn: pieceName = "pawn"; break; + case pieceKnight: pieceName = "knight"; break; + case pieceBishop: pieceName = "bishop"; break; + case pieceRook: pieceName = "rook"; break; + case pieceQueen: pieceName = "queen"; break; + case pieceKing: pieceName = "king"; break; + } + if (pieceName != null) { + pieceName += "_"; + pieceName += (piece & 0x8) ? "white" : "black"; + } + + if (pieceName != null) { + var img = document.createElement("div"); + $(img).addClass('sprite-' + pieceName); + img.style.backgroundImage = "url('img/sprites.png')"; + img.width = g_cellSize; + img.height = g_cellSize; + var divimg = document.createElement("div"); + divimg.appendChild(img); + + $(divimg).draggable({ start: function (e, ui) { + if (g_selectedPiece === null) { + g_selectedPiece = this; + var offset = $(this).closest('table').offset(); + g_startOffset = { + left: e.pageX - offset.left, + top: e.pageY - offset.top + }; + } else { + return g_selectedPiece == this; + } + }}); + + $(divimg).mousedown(function(e) { + if (g_selectedPiece === null) { + var offset = $(this).closest('table').offset(); + g_startOffset = { + left: e.pageX - offset.left, + top: e.pageY - offset.top + }; + e.stopPropagation(); + g_selectedPiece = this; + g_selectedPiece.style.backgroundImage = "url('img/transpBlue50.png')"; + } else if (g_selectedPiece === this) { + g_selectedPiece.style.backgroundImage = null; + g_selectedPiece = null; + } + }); + + $(td).empty().append(divimg); + } else { + $(td).empty(); + } + } + } +} + +function RedrawBoard() { + var div = $("#board")[0]; + + var table = document.createElement("table"); + table.cellPadding = "0px"; + table.cellSpacing = "0px"; + $(table).addClass('no-highlight'); + + var tbody = document.createElement("tbody"); + + g_uiBoard = []; + + var dropPiece = function (e, ui) { + // retrive start -> end move + var endX = e.pageX - $(table).offset().left; + var endY = e.pageY - $(table).offset().top; + + endX = Math.floor(endX / g_cellSize); + endY = Math.floor(endY / g_cellSize); + + var startX = Math.floor(g_startOffset.left / g_cellSize); + var startY = Math.floor(g_startOffset.top / g_cellSize); + + // convert coordinates to white-space + if (!g_playerWhite) { + startY = 7 - startY; + endY = 7 - endY; + startX = 7 - startX; + endX = 7 - endX; + } + + // gather all possible valid moves + var moves = GenerateValidMoves(); + var move = null; + // check if the move is valid + for (var i = 0; i < moves.length; i++) { + if ((moves[i] & 0xFF) == MakeSquare(startY, startX) && + ((moves[i] >> 8) & 0xFF) == MakeSquare(endY, endX)) { + move = moves[i]; + } + } + + // convert coordinates back to black-space + if (!g_playerWhite) { + startY = 7 - startY; + endY = 7 - endY; + startX = 7 - startX; + endX = 7 - endX; + } + + // put the html object back to its original position + // whether the move is valid or not + g_selectedPiece.style.left = 0; + g_selectedPiece.style.top = 0; + + if (!(startX == endX && startY == endY) && move != null) { + // if the move is valid + // we add the move to the png texbox + UpdatePgnTextBox(move); + + // we save the move in our worker + if (InitializeBackgroundEngine()) { + g_backgroundEngine.postMessage(FormatMove(move)); + } + + // we add the move to the move list + g_allMoves[g_allMoves.length] = move; + + // we apply the move + MakeMove(move); + + UpdateFromMove(move); + + // update the fen text box + var fen = GetFen(); + document.getElementById("FenTextBox").value = fen; + + setTimeout("SearchAndRedraw()", 0); + } + // whether the move is valid or not, we remove highlight and clear selection + g_selectedPiece.style.backgroundImage = null; + g_selectedPiece = null; + }; + + for (y = 0; y < 8; ++y) { + var tr = document.createElement("tr"); + + for (x = 0; x < 8; ++x) { + var td = document.createElement("td"); + td.style.width = g_cellSize + "px"; + td.style.height = g_cellSize + "px"; + td.style.backgroundColor = ((y ^ x) & 1) ? "#D18947" : "#FFCE9E"; + tr.appendChild(td); + g_uiBoard[y * 8 + x] = td; + } + + tbody.appendChild(tr); + } + + table.appendChild(tbody); + + $('body').droppable({ drop: dropPiece }); + $(table).mousedown(function(e) { + if (g_selectedPiece !== null) { + dropPiece(e); + } + }); + + RedrawPieces(); + + $(div).empty(); + div.appendChild(table); + + g_changingFen = true; + document.getElementById("FenTextBox").value = GetFen(); + g_changingFen = false; +} diff --git a/js/AI/garbochess.js b/js/AI/garbochess.js new file mode 100644 index 0000000..ef0ff9b --- /dev/null +++ b/js/AI/garbochess.js @@ -0,0 +1,2738 @@ +/* +This Chess AI comes from here +https://github.com/glinscott/Garbochess-JS + +Copyright (c) 2011 Gary Linscott +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met: +1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. +2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. +3. The name of the author may not be used to endorse or promote products + derived from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +// Perf TODO: +// Merge material updating with psq values +// Put move scoring inline in generator +// Remove need for fliptable in psq tables. Access them by color +// Optimize pawn move generation + +// Non-perf todo: +// Checks in first q? +// Pawn eval. +// Better king evaluation +// Better move sorting in PV nodes (especially root) + + +// ECMAScript 5 strict mode +/* jshint globalstrict: true*/ +/* jslint newcap: true */ +/* global postMessage, self */ +"use strict"; + +var g_debug = false; +var g_timeout = 40; +var g_maxply = 99; +var worker = false; +try { + // not sure this will work on any browser + // and since it's just for debug, + // a try catch should be good enough + if ( self.constructor.name === "DedicatedWorkerContext") { + worker = true; + } +} catch(e) {} + +debug ("worker = "+worker); + +function GetFen() { + var result = ""; + for (var row = 0; row < 8; row++) { + if (row !== 0) { + result += '/'; + } + var empty = 0; + for (var col = 0; col < 8; col++) { + var piece = g_board[((row + 2) << 4) + col + 4]; + if (piece === 0) { + empty++; + } else { + if (empty !== 0) { + result += empty; + } + empty = 0; + + var pieceChar = [" ", "p", "n", "b", "r", "q", "k", " "][(piece & 0x7)]; + result += ((piece & colorWhite) !== 0) ? pieceChar.toUpperCase() : pieceChar; + } + } + if (empty !== 0) { + result += empty; + } + } + + result += g_toMove == colorWhite ? " w" : " b"; + result += " "; + if (g_castleRights === 0) { + result += "-"; + } + else { + if ((g_castleRights & 1) !== 0) + result += "K"; + if ((g_castleRights & 2) !== 0) + result += "Q"; + if ((g_castleRights & 4) !== 0) + result += "k"; + if ((g_castleRights & 8) !== 0) + result += "q"; + } + + result += " "; + + if (g_enPassentSquare == -1) { + result += '-'; + } + else { + result += FormatSquare(g_enPassentSquare); + } + + return result; +} + + +function GetMoveSAN(move, validMoves) { + var from = move & 0xFF; + var to = (move >> 8) & 0xFF; + + if (move & moveflagCastleKing) return "O-O"; + if (move & moveflagCastleQueen) return "O-O-O"; + + var pieceType = g_board[from] & 0x7; + var result = ["", "", "N", "B", "R", "Q", "K", ""][pieceType]; + + var dupe = false, rowDiff = true, colDiff = true; + if (validMoves === undefined) { + validMoves = GenerateValidMoves(); + } + for (var i = 0; i < validMoves.length; i++) { + var moveFrom = validMoves[i] & 0xFF; + var moveTo = (validMoves[i] >> 8) & 0xFF; + if (moveFrom != from && + moveTo == to && + (g_board[moveFrom] & 0x7) == pieceType) { + dupe = true; + if ((moveFrom & 0xF0) == (from & 0xF0)) { + rowDiff = false; + } + if ((moveFrom & 0x0F) == (from & 0x0F)) { + colDiff = false; + } + } + } + + if (dupe) { + if (colDiff) { + result += FormatSquare(from).charAt(0); + } else if (rowDiff) { + result += FormatSquare(from).charAt(1); + } else { + result += FormatSquare(from); + } + } else if (pieceType === piecePawn && (g_board[to] !== 0 || (move & moveflagEPC))) { + result += FormatSquare(from).charAt(0); + } + + if (g_board[to] !== 0 || (move & moveflagEPC)) { + result += "x"; + } + + result += FormatSquare(to); + + if (move & moveflagPromotion) { + if (move & moveflagPromoteBishop) result += "=B"; + else if (move & moveflagPromoteKnight) result += "=N"; + else if (move & moveflagPromoteQueen) result += "=Q"; + else result += "=R"; + } + + MakeMove(move); + if (g_inCheck) { + result += GenerateValidMoves().length === 0 ? "#" : "+"; + } + UnmakeMove(move); + + return result; +} + +function FormatSquare(square) { + var letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']; + return letters[(square & 0xF) - 4] + ((9 - (square >> 4)) + 1); +} + +function FormatMove(move) { + var result = FormatSquare(move & 0xFF) + FormatSquare((move >> 8) & 0xFF); + if (move & moveflagPromotion) { + if (move & moveflagPromoteBishop) result += "b"; + else if (move & moveflagPromoteKnight) result += "n"; + else if (move & moveflagPromoteQueen) result += "q"; + else result += "r"; + } + return result; +} + +function GetMoveFromString(moveString) { + var moves = GenerateValidMoves(); + for (var i = 0; i < moves.length; i++) { + if (FormatMove(moves[i]) == moveString) { + return moves[i]; + } + } + alert("busted! ->" + moveString + " fen:" + GetFen()); +} + +function PVFromHash(move, ply) { + if (ply === 0) + return ""; + + if (move === 0) { + if (g_inCheck) return "checkmate"; + return "stalemate"; + } + + var pvString = " " + GetMoveSAN(move); + MakeMove(move); + + var hashNode = g_hashTable[g_hashKeyLow & g_hashMask]; + if (hashNode !== undefined && hashNode.lock === g_hashKeyHigh && hashNode.bestMove !== undefined) { + pvString += PVFromHash(hashNode.bestMove, ply - 1); + } + + UnmakeMove(move); + + return pvString; +} + +// +// Searching code +// + +var g_startTime; + +var g_nodeCount; +var g_qNodeCount; +var g_searchValid; +var g_globalPly = 0; + +function Search(finishMoveCallback, maxPly, finishPlyCallback) { + debug("start search with maxPly:"+maxPly+" and timeout "+g_timeout); + + if (GenerateValidMoves().length === 0) { + debug( g_inCheck ? 'Checkmate' : 'Stalemate' ); + return false; + } + + var lastEval; + var alpha = minEval; + var beta = maxEval; + + g_globalPly++; + g_nodeCount = 0; + g_qNodeCount = 0; + g_searchValid = true; + + var bestMove = 0; + var value; + + g_startTime = (new Date()).getTime(); + + var i; + for (i = 1; i <= maxPly && g_searchValid; i++) { + var tmp = AlphaBeta(i, 0, alpha, beta); + if (!g_searchValid) break; + + value = tmp; + + if (value > alpha && value < beta) { + alpha = value - 500; + beta = value + 500; + + if (alpha < minEval) alpha = minEval; + if (beta > maxEval) beta = maxEval; + } else if (alpha != minEval) { + alpha = minEval; + beta = maxEval; + i--; + } + + if (g_hashTable[g_hashKeyLow & g_hashMask] !== undefined) { + bestMove = g_hashTable[g_hashKeyLow & g_hashMask].bestMove; + } + + if (finishPlyCallback !== undefined) { + finishPlyCallback(bestMove, value, (new Date()).getTime() - g_startTime, i); + } + } + + if (finishMoveCallback !== undefined) { + finishMoveCallback(bestMove, value, (new Date()).getTime() - g_startTime, i - 1); + } +} + +var minEval = -2000000; +var maxEval = +2000000; + +var minMateBuffer = minEval + 2000; +var maxMateBuffer = maxEval - 2000; + +var materialTable = [0, 800, 3350, 3450, 5000, 9750, 600000]; + +var pawnAdj = + [ + 0, 0, 0, 0, 0, 0, 0, 0, + -25, 105, 135, 270, 270, 135, 105, -25, + -80, 0, 30, 176, 176, 30, 0, -80, + -85, -5, 25, 175, 175, 25, -5, -85, + -90, -10, 20, 125, 125, 20, -10, -90, + -95, -15, 15, 75, 75, 15, -15, -95, + -100, -20, 10, 70, 70, 10, -20, -100, + 0, 0, 0, 0, 0, 0, 0, 0 + ]; + +var knightAdj = + [ + -200, -100, -50, -50, -50, -50, -100, -200, + -100, 0, 0, 0, 0, 0, 0, -100, + -50, 0, 60, 60, 60, 60, 0, -50, + -50, 0, 30, 60, 60, 30, 0, -50, + -50, 0, 30, 60, 60, 30, 0, -50, + -50, 0, 30, 30, 30, 30, 0, -50, + -100, 0, 0, 0, 0, 0, 0, -100, + -200, -50, -25, -25, -25, -25, -50, -200 + ]; + +var bishopAdj = + [ + -50,-50,-25,-10,-10,-25,-50,-50, + -50,-25,-10, 0, 0,-10,-25,-50, + -25,-10, 0, 25, 25, 0,-10,-25, + -10, 0, 25, 40, 40, 25, 0,-10, + -10, 0, 25, 40, 40, 25, 0,-10, + -25,-10, 0, 25, 25, 0,-10,-25, + -50,-25,-10, 0, 0,-10,-25,-50, + -50,-50,-25,-10,-10,-25,-50,-50 + ]; + +var rookAdj = + [ + -60, -30, -10, 20, 20, -10, -30, -60, + 40, 70, 90,120,120, 90, 70, 40, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60 + ]; + +var kingAdj = + [ + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 150, 250, 75, -25, -25, 75, 250, 150 + ]; + +var emptyAdj = + [ + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0 + ]; + +var pieceSquareAdj = new Array(8); + +// Returns the square flipped +var flipTable = new Array(256); + +function PawnEval(color) { + var pieceIdx = (color | 1) << 4; + var from = g_pieceList[pieceIdx++]; + while (from !== 0) { + from = g_pieceList[pieceIdx++]; + } +} + +function Mobility(color) { + var result = 0; + var from, to, mob, pieceIdx; + var enemy = color == 8 ? 0x10 : 0x8; + var mobUnit = color == 8 ? g_mobUnit[0] : g_mobUnit[1]; + + // Knight mobility + mob = -3; + pieceIdx = (color | 2) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + mob += mobUnit[g_board[from + 31]]; + mob += mobUnit[g_board[from + 33]]; + mob += mobUnit[g_board[from + 14]]; + mob += mobUnit[g_board[from - 14]]; + mob += mobUnit[g_board[from - 31]]; + mob += mobUnit[g_board[from - 33]]; + mob += mobUnit[g_board[from + 18]]; + mob += mobUnit[g_board[from - 18]]; + from = g_pieceList[pieceIdx++]; + } + result += 65 * mob; + + // Bishop mobility + mob = -4; + pieceIdx = (color | 3) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from - 15; + while (g_board[to] === 0) { to -= 15; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to -= 15; + while (g_board[to] === 0) to -= 15; + mob += mobUnit[g_board[to]] << 2; + } + } + + to = from - 17; + while (g_board[to] === 0) { to -= 17; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to -= 17; + while (g_board[to] === 0) to -= 17; + mob += mobUnit[g_board[to]] << 2; + } + } + + to = from + 15; + while (g_board[to] === 0) { to += 15; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to += 15; + while (g_board[to] === 0) to += 15; + mob += mobUnit[g_board[to]] << 2; + } + } + + to = from + 17; + while (g_board[to] === 0) { to += 17; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to += 17; + while (g_board[to] === 0) to += 17; + mob += mobUnit[g_board[to]] << 2; + } + } + + from = g_pieceList[pieceIdx++]; + } + result += 44 * mob; + + // Rook mobility + mob = -4; + pieceIdx = (color | 4) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from - 1; + while (g_board[to] === 0) { to--; mob++;} + if (g_board[to] & enemy) mob++; + to = from + 1; + while (g_board[to] === 0) { to++; mob++; } + if (g_board[to] & enemy) mob++; + to = from + 16; + while (g_board[to] === 0) { to += 16; mob++; } + if (g_board[to] & enemy) mob++; + to = from - 16; + while (g_board[to] === 0) { to -= 16; mob++; } + if (g_board[to] & enemy) mob++; + from = g_pieceList[pieceIdx++]; + } + result += 25 * mob; + + // Queen mobility + mob = -2; + pieceIdx = (color | 5) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from - 15; + while (g_board[to] === 0) { to -= 15; mob++; } + if (g_board[to] & enemy) mob++; + to = from - 17; + while (g_board[to] === 0) { to -= 17; mob++; } + if (g_board[to] & enemy) mob++; + to = from + 15; + while (g_board[to] === 0) { to += 15; mob++; } + if (g_board[to] & enemy) mob++; + to = from + 17; + while (g_board[to] === 0) { to += 17; mob++; } + if (g_board[to] & enemy) mob++; + to = from - 1; + while (g_board[to] === 0) { to--; mob++; } + if (g_board[to] & enemy) mob++; + to = from + 1; + while (g_board[to] === 0) { to++; mob++; } + if (g_board[to] & enemy) mob++; + to = from + 16; + while (g_board[to] === 0) { to += 16; mob++; } + if (g_board[to] & enemy) mob++; + to = from - 16; + while (g_board[to] === 0) { to -= 16; mob++; } + if (g_board[to] & enemy) mob++; + from = g_pieceList[pieceIdx++]; + } + result += 22 * mob; + + return result; +} + +function Evaluate() { + var curEval = g_baseEval; + + var evalAdjust = 0; + // Black queen gone, then cancel white's penalty for king movement + if (g_pieceList[pieceQueen << 4] === 0) + evalAdjust -= pieceSquareAdj[pieceKing][g_pieceList[(colorWhite | pieceKing) << 4]]; + // White queen gone, then cancel black's penalty for king movement + if (g_pieceList[(colorWhite | pieceQueen) << 4] === 0) + evalAdjust += pieceSquareAdj[pieceKing][flipTable[g_pieceList[pieceKing << 4]]]; + + // Black bishop pair + if (g_pieceCount[pieceBishop] >= 2) + evalAdjust -= 500; + // White bishop pair + if (g_pieceCount[pieceBishop | colorWhite] >= 2) + evalAdjust += 500; + + var mobility = Mobility(8) - Mobility(0); + + if (g_toMove === 0) { + // Black + curEval -= mobility; + curEval -= evalAdjust; + } + else { + curEval += mobility; + curEval += evalAdjust; + } + + return curEval; +} + +function ScoreMove(move){ + var moveTo = (move >> 8) & 0xFF; + var captured = g_board[moveTo] & 0x7; + var piece = g_board[move & 0xFF]; + var score; + if (captured !== 0) { + var pieceType = piece & 0x7; + score = (captured << 5) - pieceType; + } else { + score = historyTable[piece & 0xF][moveTo]; + } + return score; +} + +function QSearch(alpha, beta, ply) { + g_qNodeCount++; + + var realEval = g_inCheck ? (minEval + 1) : Evaluate(); + + if (realEval >= beta) + return realEval; + + if (realEval > alpha) + alpha = realEval; + + var moves = []; + var moveScores = []; + var wasInCheck = g_inCheck; + var i; + + if (wasInCheck) { + // TODO: Fast check escape generator and fast checking moves generator + GenerateCaptureMoves(moves, null); + GenerateAllMoves(moves); + + for (i = 0; i < moves.length; i++) { + moveScores[i] = ScoreMove(moves[i]); + } + } else { + GenerateCaptureMoves(moves, null); + + for (i = 0; i < moves.length; i++) { + var captured = g_board[(moves[i] >> 8) & 0xFF] & 0x7; + var pieceType = g_board[moves[i] & 0xFF] & 0x7; + + moveScores[i] = (captured << 5) - pieceType; + } + } + + for (i = 0; i < moves.length; i++) { + var bestMove = i; + for (var j = moves.length - 1; j > i; j--) { + if (moveScores[j] > moveScores[bestMove]) { + bestMove = j; + } + } + + var tmpMove = moves[i]; + moves[i] = moves[bestMove]; + moves[bestMove] = tmpMove; + + var tmpScore = moveScores[i]; + moveScores[i] = moveScores[bestMove]; + moveScores[bestMove] = tmpScore; + + if (!wasInCheck && !See(moves[i])) { + continue; + } + + if (!MakeMove(moves[i])) { + continue; + } + + var value = -QSearch(-beta, -alpha, ply - 1); + + UnmakeMove(moves[i]); + + if (value > realEval) { + if (value >= beta) + return value; + + if (value > alpha) + alpha = value; + + realEval = value; + } + } + + /* Disable checks... Too slow currently + + if (ply == 0 && !wasInCheck) { + moves = []; + GenerateAllMoves(moves); + + for (var i = 0; i < moves.length; i++) { + moveScores[i] = ScoreMove(moves[i]); + } + + for (var i = 0; i < moves.length; i++) { + var bestMove = i; + for (var j = moves.length - 1; j > i; j--) { + if (moveScores[j] > moveScores[bestMove]) { + bestMove = j; + } + } + { + var tmpMove = moves[i]; + moves[i] = moves[bestMove]; + moves[bestMove] = tmpMove; + + var tmpScore = moveScores[i]; + moveScores[i] = moveScores[bestMove]; + moveScores[bestMove] = tmpScore; + } + + if (!MakeMove(moves[i])) { + continue; + } + var checking = g_inCheck; + UnmakeMove(moves[i]); + + if (!checking) { + continue; + } + + if (!See(moves[i])) { + continue; + } + + MakeMove(moves[i]); + + var value = -QSearch(-beta, -alpha, ply - 1); + + UnmakeMove(moves[i]); + + if (value > realEval) { + if (value >= beta) + return value; + + if (value > alpha) + alpha = value; + + realEval = value; + } + } + } + */ + + return realEval; +} + +function StoreHash(value, flags, ply, move, depth) { + if (value >= maxMateBuffer) + value += depth; + else if (value <= minMateBuffer) + value -= depth; + g_hashTable[g_hashKeyLow & g_hashMask] = new HashEntry(g_hashKeyHigh, value, flags, ply, move); +} + +function IsHashMoveValid(hashMove) { + var from = hashMove & 0xFF; + var to = (hashMove >> 8) & 0xFF; + var ourPiece = g_board[from]; + var pieceType = ourPiece & 0x7; + if (pieceType < piecePawn || pieceType > pieceKing) return false; + // Can't move a piece we don't control + if (g_toMove != (ourPiece & 0x8)) + return false; + // Can't move to a square that has something of the same color + if (g_board[to] !== 0 && (g_toMove == (g_board[to] & 0x8))) + return false; + if (pieceType == piecePawn) { + if (hashMove & moveflagEPC) { + return false; + } + + // Valid moves are push, capture, double push, promotions + var dir = to - from; + if ((g_toMove == colorWhite) != (dir < 0)) { + // Pawns have to move in the right direction + return false; + } + + var row = to & 0xF0; + if (((row == 0x90 && !g_toMove) || + (row == 0x20 && g_toMove)) !== (hashMove & moveflagPromotion)) { + // Handle promotions + return false; + } + + if (dir === -16 || dir === 16) { + // White/Black push + return g_board[to] === 0; + } else if (dir === -15 || dir === -17 || dir === 15 || dir === 17) { + // White/Black capture + return g_board[to] !== 0; + } else if (dir === -32) { + // Double white push + if (row !== 0x60) return false; + if (g_board[to] !== 0) return false; + if (g_board[from - 16] !== 0) return false; + } else if (dir == 32) { + // Double black push + if (row !== 0x50) return false; + if (g_board[to] !== 0) return false; + if (g_board[from + 16] !== 0) return false; + } else { + return false; + } + + return true; + } else { + // This validates that this piece type can actually make the attack + if (hashMove >> 16) return false; + return IsSquareAttackableFrom(to, from); + } +} + +function IsRepDraw() { + var stop = g_moveCount - 1 - g_move50; + stop = stop < 0 ? 0 : stop; + for (var i = g_moveCount - 5; i >= stop; i -= 2) { + if (g_repMoveStack[i] == g_hashKeyLow) + return true; + } + return false; +} + +function MovePicker(hashMove, depth, killer1, killer2) { + this.hashMove = hashMove; + this.depth = depth; + this.killer1 = killer1; + this.killer2 = killer2; + + this.moves = []; + this.losingCaptures = null; + this.moveCount = 0; + this.atMove = -1; + this.moveScores = null; + this.stage = 0; + + this.nextMove = function () { + var i; + if (++this.atMove == this.moveCount) { + this.stage++; + if (this.stage == 1) { + if (this.hashMove !== undefined && IsHashMoveValid(hashMove)) { + this.moves[0] = hashMove; + this.moveCount = 1; + } + if (this.moveCount != 1) { + this.hashMove = undefined; + this.stage++; + } + } + + if (this.stage == 2) { + GenerateCaptureMoves(this.moves, null); + this.moveCount = this.moves.length; + this.moveScores = new Array(this.moveCount); + // Move ordering + for (i = this.atMove; i < this.moveCount; i++) { + var captured = g_board[(this.moves[i] >> 8) & 0xFF] & 0x7; + var pieceType = g_board[this.moves[i] & 0xFF] & 0x7; + this.moveScores[i] = (captured << 5) - pieceType; + } + // No moves, onto next stage + if (this.atMove == this.moveCount) this.stage++; + } + + if (this.stage == 3) { + if (IsHashMoveValid(this.killer1) && + this.killer1 != this.hashMove) { + this.moves[this.moves.length] = this.killer1; + this.moveCount = this.moves.length; + } else { + this.killer1 = 0; + this.stage++; + } + } + + if (this.stage == 4) { + if (IsHashMoveValid(this.killer2) && + this.killer2 != this.hashMove) { + this.moves[this.moves.length] = this.killer2; + this.moveCount = this.moves.length; + } else { + this.killer2 = 0; + this.stage++; + } + } + + if (this.stage == 5) { + GenerateAllMoves(this.moves); + this.moveCount = this.moves.length; + // Move ordering + for (i = this.atMove; i < this.moveCount; i++) this.moveScores[i] = ScoreMove(this.moves[i]); + // No moves, onto next stage + if (this.atMove === this.moveCount) this.stage++; + } + + if (this.stage === 6) { + // Losing captures + if (this.losingCaptures !== null) { + for (i = 0; i < this.losingCaptures.length; i++) { + this.moves[this.moves.length] = this.losingCaptures[i]; + } + for (i = this.atMove; i < this.moveCount; i++) this.moveScores[i] = ScoreMove(this.moves[i]); + this.moveCount = this.moves.length; + } + // No moves, onto next stage + if (this.atMove === this.moveCount) this.stage++; + } + + if (this.stage === 7) + return 0; + } + + var bestMove = this.atMove; + for (var j = this.atMove + 1; j < this.moveCount; j++) { + if (this.moveScores[j] > this.moveScores[bestMove]) { + bestMove = j; + } + } + + if (bestMove != this.atMove) { + var tmpMove = this.moves[this.atMove]; + this.moves[this.atMove] = this.moves[bestMove]; + this.moves[bestMove] = tmpMove; + + var tmpScore = this.moveScores[this.atMove]; + this.moveScores[this.atMove] = this.moveScores[bestMove]; + this.moveScores[bestMove] = tmpScore; + } + + var candidateMove = this.moves[this.atMove]; + if ((this.stage > 1 && candidateMove == this.hashMove) || + (this.stage > 3 && candidateMove == this.killer1) || + (this.stage > 4 && candidateMove == this.killer2)) { + return this.nextMove(); + } + + if (this.stage === 2 && !See(candidateMove)) { + if (this.losingCaptures === null) { + this.losingCaptures = []; + } + this.losingCaptures[this.losingCaptures.length] = candidateMove; + return this.nextMove(); + } + + return this.moves[this.atMove]; + }; +} + +function AllCutNode(ply, depth, beta, allowNull) { + if (ply <= 0) { + return QSearch(beta - 1, beta, 0); + } + + if ((g_nodeCount & 127) == 127) { + if ((new Date()).getTime() - g_startTime > g_timeout) { + // Time cutoff + g_searchValid = false; + return beta - 1; + } + } + + g_nodeCount++; + + if (IsRepDraw()) + return 0; + + // Mate distance pruning + if (minEval + depth >= beta) + return beta; + + if (maxEval - (depth + 1) < beta) + return beta - 1; + + var hashMove = null; + var hashNode = g_hashTable[g_hashKeyLow & g_hashMask]; + if (hashNode !== undefined && hashNode.lock === g_hashKeyHigh) { + hashMove = hashNode.bestMove; + if (hashNode.hashDepth >= ply) { + var hashValue = hashNode.value; + + // Fixup mate scores + if (hashValue >= maxMateBuffer) + hashValue -= depth; + else if (hashValue <= minMateBuffer) + hashValue += depth; + + if (hashNode.flags === hashflagExact) + return hashValue; + if (hashNode.flags === hashflagAlpha && hashValue < beta) + return hashValue; + if (hashNode.flags === hashflagBeta && hashValue >= beta) + return hashValue; + } + } + + // TODO - positional gain? + var value; + if (!g_inCheck && + allowNull && + beta > minMateBuffer && + beta < maxMateBuffer) { + // Try some razoring + if (hashMove === undefined && + ply < 4) { + var razorMargin = 2500 + 200 * ply; + if (g_baseEval < beta - razorMargin) { + var razorBeta = beta - razorMargin; + var v = QSearch(razorBeta - 1, razorBeta, 0); + if (v < razorBeta) + return v; + } + } + + // TODO - static null move + + // Null move + if (ply > 1 && + g_baseEval >= beta - (ply >= 4 ? 2500 : 0) && + // Disable null move if potential zugzwang (no big pieces) + (g_pieceCount[pieceBishop | g_toMove] !== 0 || + g_pieceCount[pieceKnight | g_toMove] !== 0 || + g_pieceCount[pieceRook | g_toMove] !== 0 || + g_pieceCount[pieceQueen | g_toMove] !== 0)) { + var r = 3 + (ply >= 5 ? 1 : ply / 4); + if (g_baseEval - beta > 1500) r++; + + g_toMove = 8 - g_toMove; + g_baseEval = -g_baseEval; + g_hashKeyLow ^= g_zobristBlackLow; + g_hashKeyHigh ^= g_zobristBlackHigh; + + value = -AllCutNode(ply - r, depth + 1, -(beta - 1), false); + + g_hashKeyLow ^= g_zobristBlackLow; + g_hashKeyHigh ^= g_zobristBlackHigh; + g_toMove = 8 - g_toMove; + g_baseEval = -g_baseEval; + + if (value >= beta) + return beta; + } + } + + var moveMade = false; + var realEval = minEval - 1; + var inCheck = g_inCheck; + + var movePicker = new MovePicker(hashMove, depth, g_killers[depth][0], g_killers[depth][1]); + + for (;;) { + var currentMove = movePicker.nextMove(); + if (currentMove === 0) { + break; + } + + var plyToSearch = ply - 1; + + if (!MakeMove(currentMove)) { + continue; + } + + value = null; + var doFullSearch = true; + + if (g_inCheck) { + // Check extensions + plyToSearch++; + } else { + var reduced = plyToSearch - (movePicker.atMove > 14 ? 2 : 1); + + // Futility pruning +/* if (movePicker.stage == 5 && !inCheck) { + if (movePicker.atMove >= (15 + (1 << (5 * ply) >> 2)) && + realEval > minMateBuffer) { + UnmakeMove(currentMove); + continue; + } + + if (ply < 7) { + var reducedPly = reduced <= 0 ? 0 : reduced; + var futilityValue = -g_baseEval + (900 * (reducedPly + 2)) - (movePicker.atMove * 10); + if (futilityValue < beta) { + if (futilityValue > realEval) { + realEval = futilityValue; + } + UnmakeMove(currentMove); + continue; + } + } + }*/ + + // Late move reductions + if (movePicker.stage == 5 && movePicker.atMove > 5 && ply >= 3) { + value = -AllCutNode(reduced, depth + 1, -(beta - 1), true); + doFullSearch = (value >= beta); + } + } + + if (doFullSearch) { + value = -AllCutNode(plyToSearch, depth + 1, -(beta - 1), true); + } + + moveMade = true; + + UnmakeMove(currentMove); + + if (!g_searchValid) { + return beta - 1; + } + + if (value > realEval) { + if (value >= beta) { + var histTo = (currentMove >> 8) & 0xFF; + if (g_board[histTo] === 0) { + var histPiece = g_board[currentMove & 0xFF] & 0xF; + historyTable[histPiece][histTo] += ply * ply; + if (historyTable[histPiece][histTo] > 32767) { + historyTable[histPiece][histTo] >>= 1; + } + + if (g_killers[depth][0] != currentMove) { + g_killers[depth][1] = g_killers[depth][0]; + g_killers[depth][0] = currentMove; + } + } + + StoreHash(value, hashflagBeta, ply, currentMove, depth); + return value; + } + + realEval = value; + hashMove = currentMove; + } + } + + if (!moveMade) { + // If we have no valid moves it's either stalemate or checkmate + if (g_inCheck) + // Checkmate. + return minEval + depth; + else + // Stalemate + return 0; + } + + StoreHash(realEval, hashflagAlpha, ply, hashMove, depth); + + return realEval; +} + +function AlphaBeta(ply, depth, alpha, beta) { + if (ply <= 0) { + return QSearch(alpha, beta, 0); + } + + g_nodeCount++; + + if (depth > 0 && IsRepDraw()) + return 0; + + // Mate distance pruning + var oldAlpha = alpha; + alpha = alpha < minEval + depth ? alpha : minEval + depth; + beta = beta > maxEval - (depth + 1) ? beta : maxEval - (depth + 1); + if (alpha >= beta) + return alpha; + + var hashMove = null; + var hashFlag = hashflagAlpha; + var hashNode = g_hashTable[g_hashKeyLow & g_hashMask]; + if (hashNode !== undefined && hashNode.lock === g_hashKeyHigh) { + hashMove = hashNode.bestMove; + } + + var inCheck = g_inCheck; + + var moveMade = false; + var realEval = minEval; + + var movePicker = new MovePicker(hashMove, depth, g_killers[depth][0], g_killers[depth][1]); + + for (;;) { + var currentMove = movePicker.nextMove(); + if (currentMove === 0) { + break; + } + + var plyToSearch = ply - 1; + + if (!MakeMove(currentMove)) { + continue; + } + + if (g_inCheck) { + // Check extensions + plyToSearch++; + } + + var value; + if (moveMade) { + value = -AllCutNode(plyToSearch, depth + 1, -alpha, true); + if (value > alpha) { + value = -AlphaBeta(plyToSearch, depth + 1, -beta, -alpha); + } + } else { + value = -AlphaBeta(plyToSearch, depth + 1, -beta, -alpha); + } + + moveMade = true; + + UnmakeMove(currentMove); + + if (!g_searchValid) { + return alpha; + } + + if (value > realEval) { + if (value >= beta) { + var histTo = (currentMove >> 8) & 0xFF; + if (g_board[histTo] === 0) { + var histPiece = g_board[currentMove & 0xFF] & 0xF; + historyTable[histPiece][histTo] += ply * ply; + if (historyTable[histPiece][histTo] > 32767) { + historyTable[histPiece][histTo] >>= 1; + } + + if (g_killers[depth][0] !== currentMove) { + g_killers[depth][1] = g_killers[depth][0]; + g_killers[depth][0] = currentMove; + } + } + + StoreHash(value, hashflagBeta, ply, currentMove, depth); + return value; + } + + if (value > oldAlpha) { + hashFlag = hashflagExact; + alpha = value; + } + + realEval = value; + hashMove = currentMove; + } + } + + if (!moveMade) { + // If we have no valid moves it's either stalemate or checkmate + if (inCheck) + // Checkmate. + return minEval + depth; + else + // Stalemate + return 0; + } + + StoreHash(realEval, hashFlag, ply, hashMove, depth); + + return realEval; +} + +// +// Board code +// + +// This somewhat funky scheme means that a piece is indexed by it's lower 4 bits when accessing in arrays. The fifth bit (black bit) +// is used to allow quick edge testing on the board. +var colorBlack = 0x10; +var colorWhite = 0x08; + +var pieceEmpty = 0x00; +var piecePawn = 0x01; +var pieceKnight = 0x02; +var pieceBishop = 0x03; +var pieceRook = 0x04; +var pieceQueen = 0x05; +var pieceKing = 0x06; + +var g_vectorDelta = new Array(256); + +var g_bishopDeltas = [-15, -17, 15, 17]; +var g_knightDeltas = [31, 33, 14, -14, -31, -33, 18, -18]; +var g_rookDeltas = [-1, +1, -16, +16]; +var g_queenDeltas = [-1, +1, -15, +15, -17, +17, -16, +16]; + +var g_castleRightsMask = [ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 7,15,15,15, 3,15,15,11, 0, 0, 0, 0, + 0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, + 0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, + 0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, + 0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, + 0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, + 0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, + 0, 0, 0, 0,13,15,15,15,12,15,15,14, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 +]; + +var moveflagEPC = 0x2 << 16; +var moveflagCastleKing = 0x4 << 16; +var moveflagCastleQueen = 0x8 << 16; +var moveflagPromotion = 0x10 << 16; +var moveflagPromoteRook = 0x00 << 16; +var moveflagPromoteKnight = 0x20 << 16; +var moveflagPromoteQueen = 0x40 << 16; +var moveflagPromoteBishop = 0x80 << 16; + +function MT() { + var N = 624; + var M = 397; + var MAG01 = [0x0, 0x9908b0df]; + + this.mt = new Array(N); + this.mti = N + 1; + + this.setSeed = function() + { + var a = arguments; + var i,s,k; + switch (a.length) { + case 1: + if (a[0].constructor === Number) { + this.mt[0]= a[0]; + for (i = 1; i < N; ++i) { + s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30); + this.mt[i] = ( + (1812433253 * ((s & 0xffff0000) >>> 16)) + << 16 + ) + + 1812433253 * (s & 0x0000ffff) + + i; + } + this.mti = N; + return; + } + + this.setSeed(19650218); + + var l = a[0].length; + var j = 0; + i = 1; + + for (k = N > l ? N : l; k !== 0; --k) { + s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30); + this.mt[i] = ( + this.mt[i] ^ + ( + ((1664525 * ((s & 0xffff0000) >>> 16)) << 16) + + 1664525 * (s & 0x0000ffff) + ) + ) + a[0][j] + j; + if (++i >= N) { + this.mt[0] = this.mt[N - 1]; + i = 1; + } + if (++j >= l) { + j = 0; + } + } + + for (k = N - 1; k !== 0; --k) { + s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30); + this.mt[i] = ( + this.mt[i] ^ + ( + ((1566083941 * ((s & 0xffff0000) >>> 16)) << 16) + + 1566083941 * (s & 0x0000ffff) + ) + ) - i; + + if (++i >= N) { + this.mt[0] = this.mt[N-1]; + i = 1; + } + } + + this.mt[0] = 0x80000000; + return; + default: + var seeds = []; + for (i = 0; i < a.length; ++i) { + seeds.push(a[i]); + } + this.setSeed(seeds); + return; + } + }; + + this.setSeed(0x1BADF00D); + + this.next = function (bits) + { + var k; + if (this.mti >= N) { + var x = 0; + + for (k = 0; k < N - M; ++k) { + x = (this.mt[k] & 0x80000000) | (this.mt[k + 1] & 0x7fffffff); + this.mt[k] = this.mt[k + M] ^ (x >>> 1) ^ MAG01[x & 0x1]; + } + for (k = N - M; k < N - 1; ++k) { + x = (this.mt[k] & 0x80000000) | (this.mt[k + 1] & 0x7fffffff); + this.mt[k] = this.mt[k + (M - N)] ^ (x >>> 1) ^ MAG01[x & 0x1]; + } + x = (this.mt[N - 1] & 0x80000000) | (this.mt[0] & 0x7fffffff); + this.mt[N - 1] = this.mt[M - 1] ^ (x >>> 1) ^ MAG01[x & 0x1]; + + this.mti = 0; + } + + var y = this.mt[this.mti++]; + y ^= y >>> 11; + y ^= (y << 7) & 0x9d2c5680; + y ^= (y << 15) & 0xefc60000; + y ^= y >>> 18; + return (y >>> (32 - bits)) & 0xFFFFFFFF; + }; +} + +// Position variables +var g_board = new Array(256); // Sentinel 0x80, pieces are in low 4 bits, 0x8 for color, 0x7 bits for piece type +var g_toMove; // side to move, 0 or 8, 0 = black, 8 = white +var g_castleRights; // bitmask representing castling rights, 1 = wk, 2 = wq, 4 = bk, 8 = bq +var g_enPassentSquare; +var g_baseEval; +var g_hashKeyLow, g_hashKeyHigh; +var g_inCheck; + +// Utility variables +var g_moveCount = 0; +var g_moveUndoStack = []; + +var g_move50 = 0; +var g_repMoveStack = []; + +var g_hashSize = 1 << 22; +var g_hashMask = g_hashSize - 1; +var g_hashTable; + +var g_killers; +var historyTable = new Array(32); + +var g_zobristLow; +var g_zobristHigh; +var g_zobristBlackLow; +var g_zobristBlackHigh; + +// Evaulation variables +var g_mobUnit; + +var hashflagAlpha = 1; +var hashflagBeta = 2; +var hashflagExact = 3; + +function HashEntry(lock, value, flags, hashDepth, bestMove, globalPly) { + this.lock = lock; + this.value = value; + this.flags = flags; + this.hashDepth = hashDepth; + this.bestMove = bestMove; +} + +function MakeSquare(row, column) { + return ((row + 2) << 4) | (column + 4); +} + +function MakeTable(table) { + var result = new Array(256); + for (var i = 0; i < 256; i++) { + result[i] = 0; + } + for (var row = 0; row < 8; row++) { + for (var col = 0; col < 8; col++) { + result[MakeSquare(row, col)] = table[row * 8 + col]; + } + } + return result; +} + +function ResetGame(fen) { + var i,j; + var row, col; + var square; + g_killers = new Array(128); + + for (i = 0; i < 128; i++) { + g_killers[i] = [0, 0]; + } + + g_hashTable = new Array(g_hashSize); + + for (i = 0; i < 32; i++) { + historyTable[i] = new Array(256); + for (j = 0; j < 256; j++) + historyTable[i][j] = 0; + } + + var mt = new MT(0x1badf00d); + + g_zobristLow = new Array(256); + g_zobristHigh = new Array(256); + for (i = 0; i < 256; i++) { + g_zobristLow[i] = new Array(16); + g_zobristHigh[i] = new Array(16); + for (j = 0; j < 16; j++) { + g_zobristLow[i][j] = mt.next(32); + g_zobristHigh[i][j] = mt.next(32); + } + } + g_zobristBlackLow = mt.next(32); + g_zobristBlackHigh = mt.next(32); + + for (row = 0; row < 8; row++) { + for (col = 0; col < 8; col++) { + square = MakeSquare(row, col); + flipTable[square] = MakeSquare(7 - row, col); + } + } + + pieceSquareAdj[piecePawn] = MakeTable(pawnAdj); + pieceSquareAdj[pieceKnight] = MakeTable(knightAdj); + pieceSquareAdj[pieceBishop] = MakeTable(bishopAdj); + pieceSquareAdj[pieceRook] = MakeTable(rookAdj); + pieceSquareAdj[pieceQueen] = MakeTable(emptyAdj); + pieceSquareAdj[pieceKing] = MakeTable(kingAdj); + + var pieceDeltas = [[], [], g_knightDeltas, g_bishopDeltas, g_rookDeltas, g_queenDeltas, g_queenDeltas]; + + for (i = 0; i < 256; i++) { + g_vectorDelta[i] = {}; + g_vectorDelta[i].delta = 0; + g_vectorDelta[i].pieceMask = new Array(2); + g_vectorDelta[i].pieceMask[0] = 0; + g_vectorDelta[i].pieceMask[1] = 0; + } + + // Initialize the vector delta table + for (row = 0; row < 0x80; row += 0x10) + for (col = 0; col < 0x8; col++) { + square = row | col; + // Pawn moves + var index = square - (square - 17) + 128; + g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn); + index = square - (square - 15) + 128; + g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn); + + index = square - (square + 17) + 128; + g_vectorDelta[index].pieceMask[0] |= (1 << piecePawn); + index = square - (square + 15) + 128; + g_vectorDelta[index].pieceMask[0] |= (1 << piecePawn); + + for (i = pieceKnight; i <= pieceKing; i++) { + for (var dir = 0; dir < pieceDeltas[i].length; dir++) { + var target = square + pieceDeltas[i][dir]; + while (!(target & 0x88)) { + index = square - target + 128; + + g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << i); + g_vectorDelta[index].pieceMask[0] |= (1 << i); + + var flip = -1; + if (square < target) + flip = 1; + + if ((square & 0xF0) == (target & 0xF0)) { + // On the same row + g_vectorDelta[index].delta = flip * 1; + } else if ((square & 0x0F) == (target & 0x0F)) { + // On the same column + g_vectorDelta[index].delta = flip * 16; + } else if ((square % 15) == (target % 15)) { + g_vectorDelta[index].delta = flip * 15; + } else if ((square % 17) == (target % 17)) { + g_vectorDelta[index].delta = flip * 17; + } + + if (i == pieceKnight) { + g_vectorDelta[index].delta = pieceDeltas[i][dir]; + break; + } + + if (i == pieceKing) + break; + + target += pieceDeltas[i][dir]; + } + } + } + } + + InitializeEval(); + InitializeFromFen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"); +} + +function InitializeEval() { + g_mobUnit = new Array(2); + for (var i = 0; i < 2; i++) { + g_mobUnit[i] = []; + var enemy = i === 0 ? 0x10 : 8; + var friend = i === 0 ? 8 : 0x10; + g_mobUnit[i][0] = 1; + g_mobUnit[i][0x80] = 0; + g_mobUnit[i][enemy | piecePawn] = 1; + g_mobUnit[i][enemy | pieceBishop] = 2; + g_mobUnit[i][enemy | pieceKnight] = 2; + g_mobUnit[i][enemy | pieceRook] = 4; + g_mobUnit[i][enemy | pieceQueen] = 6; + g_mobUnit[i][enemy | pieceKing] = 6; + g_mobUnit[i][friend | piecePawn] = 0; + g_mobUnit[i][friend | pieceBishop] = 0; + g_mobUnit[i][friend | pieceKnight] = 0; + g_mobUnit[i][friend | pieceRook] = 0; + g_mobUnit[i][friend | pieceQueen] = 0; + g_mobUnit[i][friend | pieceKing] = 0; + } +} + +function SetHash() { + var result = {}; + result.hashKeyLow = 0; + result.hashKeyHigh = 0; + + for (var i = 0; i < 256; i++) { + var piece = g_board[i]; + if (piece & 0x18) { + result.hashKeyLow ^= g_zobristLow[i][piece & 0xF]; + result.hashKeyHigh ^= g_zobristHigh[i][piece & 0xF]; + } + } + + if (!g_toMove) { + result.hashKeyLow ^= g_zobristBlackLow; + result.hashKeyHigh ^= g_zobristBlackHigh; + } + + return result; +} + +function InitializeFromFen(fen) { + var i; + var row = 0; + var col = 0; + var chunks = fen.split(' '); + + for (i = 0; i < 256; i++) + g_board[i] = 0x80; + + + var pieces = chunks[0]; + for (i = 0; i < pieces.length; i++) { + var c = pieces.charAt(i); + + if (c == '/') { + row++; + col = 0; + } + else { + if (c >= '0' && c <= '9') { + for (var j = 0; j < parseInt(c,10); j++) { + g_board[MakeSquare(row, col)] = 0; + col++; + } + } + else { + var isBlack = c >= 'a' && c <= 'z'; + var piece = isBlack ? colorBlack : colorWhite; + if (!isBlack) + c = pieces.toLowerCase().charAt(i); + switch (c) { + case 'p': + piece |= piecePawn; + break; + case 'b': + piece |= pieceBishop; + break; + case 'n': + piece |= pieceKnight; + break; + case 'r': + piece |= pieceRook; + break; + case 'q': + piece |= pieceQueen; + break; + case 'k': + piece |= pieceKing; + break; + } + + g_board[MakeSquare(row, col)] = piece; + col++; + } + } + } + + InitializePieceList(); + + g_toMove = chunks[1].charAt(0) == 'w' ? colorWhite : 0; + var them = 8 - g_toMove; + + g_castleRights = 0; + if (chunks[2].indexOf('K') != -1) { + if (g_board[MakeSquare(7, 4)] != (pieceKing | colorWhite) || + g_board[MakeSquare(7, 7)] != (pieceRook | colorWhite)) { + return 'Invalid FEN: White kingside castling not allowed'; + } + g_castleRights |= 1; + } + if (chunks[2].indexOf('Q') != -1) { + if (g_board[MakeSquare(7, 4)] != (pieceKing | colorWhite) || + g_board[MakeSquare(7, 0)] != (pieceRook | colorWhite)) { + return 'Invalid FEN: White queenside castling not allowed'; + } + g_castleRights |= 2; + } + if (chunks[2].indexOf('k') != -1) { + if (g_board[MakeSquare(0, 4)] != (pieceKing | colorBlack) || + g_board[MakeSquare(0, 7)] != (pieceRook | colorBlack)) { + return 'Invalid FEN: Black kingside castling not allowed'; + } + g_castleRights |= 4; + } + if (chunks[2].indexOf('q') != -1) { + if (g_board[MakeSquare(0, 4)] != (pieceKing | colorBlack) || + g_board[MakeSquare(0, 0)] != (pieceRook | colorBlack)) { + return 'Invalid FEN: Black queenside castling not allowed'; + } + g_castleRights |= 8; + } + + g_enPassentSquare = -1; + if (chunks[3].indexOf('-') == -1) { + col = chunks[3].charAt(0).charCodeAt() - 'a'.charCodeAt(); + row = 8 - (chunks[3].charAt(1).charCodeAt() - '0'.charCodeAt()); + g_enPassentSquare = MakeSquare(row, col); + } + + var hashResult = SetHash(); + g_hashKeyLow = hashResult.hashKeyLow; + g_hashKeyHigh = hashResult.hashKeyHigh; + + g_baseEval = 0; + for (i = 0; i < 256; i++) { + if (g_board[i] & colorWhite) { + g_baseEval += pieceSquareAdj[g_board[i] & 0x7][i]; + g_baseEval += materialTable[g_board[i] & 0x7]; + } else if (g_board[i] & colorBlack) { + g_baseEval -= pieceSquareAdj[g_board[i] & 0x7][flipTable[i]]; + g_baseEval -= materialTable[g_board[i] & 0x7]; + } + } + if (!g_toMove) g_baseEval = -g_baseEval; + + g_move50 = 0; + g_inCheck = IsSquareAttackable(g_pieceList[(g_toMove | pieceKing) << 4], them); + + // Check for king capture (invalid FEN) + if (IsSquareAttackable(g_pieceList[(them | pieceKing) << 4], g_toMove)) { + return 'Invalid FEN: Can capture king'; + } + + // Checkmate/stalemate + if (GenerateValidMoves().length === 0) { + return g_inCheck ? 'Checkmate' : 'Stalemate'; + } + + return ''; +} + +var g_pieceIndex = new Array(256); +var g_pieceList = new Array(2 * 8 * 16); +var g_pieceCount = new Array(2 * 8); + +function InitializePieceList() { + var i; + for (i = 0; i < 16; i++) { + g_pieceCount[i] = 0; + for (var j = 0; j < 16; j++) { + // 0 is used as the terminator for piece lists + g_pieceList[(i << 4) | j] = 0; + } + } + + for (i = 0; i < 256; i++) { + g_pieceIndex[i] = 0; + if (g_board[i] & (colorWhite | colorBlack)) { + var piece = g_board[i] & 0xF; + + g_pieceList[(piece << 4) | g_pieceCount[piece]] = i; + g_pieceIndex[i] = g_pieceCount[piece]; + g_pieceCount[piece]++; + } + } +} + +function MakeMove(move){ + // move format: + // --flags-- ---to---- --from--- + // 0000 0000 0000 0000 0000 0000 + + // g_board is a 256x256 array + // representing the chess board + // right in the middle of it + + // moveflagEPC = 0000 0010 0000 0000 0000 0000 + // moveflagCastleKing = 0000 0100 0000 0000 0000 0000 + // moveflagCastleQueen = 0000 1000 0000 0000 0000 0000 + + // moveflagPromotion = 0001 0000 0000 0000 0000 0000 + // moveflagPromoteRook = 0000 0000 0000 0000 0000 0000 + // moveflagPromoteKnight = 0010 0000 0000 0000 0000 0000 + // moveflagPromoteQueen = 0100 0000 0000 0000 0000 0000 + // moveflagPromoteBishop = 1000 0000 0000 0000 0000 0000 + + + var me = g_toMove >> 3; + var otherColor = 8 - g_toMove; + + var flags = move & 0xFF0000; + var to = (move >> 8) & 0xFF; + var from = move & 0xFF; + var captured = g_board[to]; + var piece = g_board[from]; + var epcEnd = to; + var rook, rookIndex; + + if (flags & moveflagEPC) { + epcEnd = me ? (to + 0x10) : (to - 0x10); + captured = g_board[epcEnd]; + g_board[epcEnd] = pieceEmpty; + } + + g_moveUndoStack[g_moveCount] = new UndoHistory(g_enPassentSquare, g_castleRights, g_inCheck, g_baseEval, g_hashKeyLow, g_hashKeyHigh, g_move50, captured); + g_moveCount++; + + g_enPassentSquare = -1; + + if (flags) { + if (flags & moveflagCastleKing) { + if (IsSquareAttackable(from + 1, otherColor) || + IsSquareAttackable(from + 2, otherColor)) { + g_moveCount--; + return false; + } + + rook = g_board[to + 1]; + + g_hashKeyLow ^= g_zobristLow[to + 1][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to + 1][rook & 0xF]; + g_hashKeyLow ^= g_zobristLow[to - 1][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to - 1][rook & 0xF]; + + g_board[to - 1] = rook; + g_board[to + 1] = pieceEmpty; + + g_baseEval -= pieceSquareAdj[rook & 0x7][me === 0 ? flipTable[to + 1] : (to + 1)]; + g_baseEval += pieceSquareAdj[rook & 0x7][me === 0 ? flipTable[to - 1] : (to - 1)]; + + rookIndex = g_pieceIndex[to + 1]; + g_pieceIndex[to - 1] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to - 1; + } else if (flags & moveflagCastleQueen) { + if (IsSquareAttackable(from - 1, otherColor) || + IsSquareAttackable(from - 2, otherColor)) { + g_moveCount--; + return false; + } + + rook = g_board[to - 2]; + + g_hashKeyLow ^= g_zobristLow[to -2][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to - 2][rook & 0xF]; + g_hashKeyLow ^= g_zobristLow[to + 1][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to + 1][rook & 0xF]; + + g_board[to + 1] = rook; + g_board[to - 2] = pieceEmpty; + + g_baseEval -= pieceSquareAdj[rook & 0x7][me === 0 ? flipTable[to - 2] : (to - 2)]; + g_baseEval += pieceSquareAdj[rook & 0x7][me === 0 ? flipTable[to + 1] : (to + 1)]; + + rookIndex = g_pieceIndex[to - 2]; + g_pieceIndex[to + 1] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to + 1; + } + } + + if ((captured & 0x7) > 0) { + // Remove our piece from the piece list + var capturedType = captured & 0xF; + g_pieceCount[capturedType]--; + var lastPieceSquare = g_pieceList[(capturedType << 4) | g_pieceCount[capturedType]]; + g_pieceIndex[lastPieceSquare] = g_pieceIndex[epcEnd]; + g_pieceList[(capturedType << 4) | g_pieceIndex[lastPieceSquare]] = lastPieceSquare; + g_pieceList[(capturedType << 4) | g_pieceCount[capturedType]] = 0; + + g_baseEval += materialTable[captured & 0x7]; + g_baseEval += pieceSquareAdj[captured & 0x7][me ? flipTable[epcEnd] : epcEnd]; + + g_hashKeyLow ^= g_zobristLow[epcEnd][capturedType]; + g_hashKeyHigh ^= g_zobristHigh[epcEnd][capturedType]; + g_move50 = 0; + } else if ((piece & 0x7) == piecePawn) { + var diff = to - from; + if (diff < 0) diff = -diff; + if (diff > 16) { + g_enPassentSquare = me ? (to + 0x10) : (to - 0x10); + } + g_move50 = 0; + } + + g_hashKeyLow ^= g_zobristLow[from][piece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[from][piece & 0xF]; + g_hashKeyLow ^= g_zobristLow[to][piece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to][piece & 0xF]; + g_hashKeyLow ^= g_zobristBlackLow; + g_hashKeyHigh ^= g_zobristBlackHigh; + + g_castleRights &= g_castleRightsMask[from] & g_castleRightsMask[to]; + + g_baseEval -= pieceSquareAdj[piece & 0x7][me === 0 ? flipTable[from] : from]; + + // Move our piece in the piece list + g_pieceIndex[to] = g_pieceIndex[from]; + g_pieceList[((piece & 0xF) << 4) | g_pieceIndex[to]] = to; + + if (flags & moveflagPromotion) { + var newPiece = piece & (~0x7); + if (flags & moveflagPromoteKnight) + newPiece |= pieceKnight; + else if (flags & moveflagPromoteQueen) + newPiece |= pieceQueen; + else if (flags & moveflagPromoteBishop) + newPiece |= pieceBishop; + else + newPiece |= pieceRook; + + g_hashKeyLow ^= g_zobristLow[to][piece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to][piece & 0xF]; + g_board[to] = newPiece; + g_hashKeyLow ^= g_zobristLow[to][newPiece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to][newPiece & 0xF]; + + g_baseEval += pieceSquareAdj[newPiece & 0x7][me === 0 ? flipTable[to] : to]; + g_baseEval -= materialTable[piecePawn]; + g_baseEval += materialTable[newPiece & 0x7]; + + var pawnType = piece & 0xF; + var promoteType = newPiece & 0xF; + + g_pieceCount[pawnType]--; + + var lastPawnSquare = g_pieceList[(pawnType << 4) | g_pieceCount[pawnType]]; + g_pieceIndex[lastPawnSquare] = g_pieceIndex[to]; + g_pieceList[(pawnType << 4) | g_pieceIndex[lastPawnSquare]] = lastPawnSquare; + g_pieceList[(pawnType << 4) | g_pieceCount[pawnType]] = 0; + g_pieceIndex[to] = g_pieceCount[promoteType]; + g_pieceList[(promoteType << 4) | g_pieceIndex[to]] = to; + g_pieceCount[promoteType]++; + } else { + g_board[to] = g_board[from]; + + g_baseEval += pieceSquareAdj[piece & 0x7][me === 0 ? flipTable[to] : to]; + } + g_board[from] = pieceEmpty; + + g_toMove = otherColor; + g_baseEval = -g_baseEval; + + if ((piece & 0x7) == pieceKing || g_inCheck) { + if (IsSquareAttackable(g_pieceList[(pieceKing | (8 - g_toMove)) << 4], otherColor)) { + UnmakeMove(move); + return false; + } + } else { + var kingPos = g_pieceList[(pieceKing | (8 - g_toMove)) << 4]; + + if (ExposesCheck(from, kingPos)) { + UnmakeMove(move); + return false; + } + + if (epcEnd != to) { + if (ExposesCheck(epcEnd, kingPos)) { + UnmakeMove(move); + return false; + } + } + } + + g_inCheck = false; + + if (flags <= moveflagEPC) { + var theirKingPos = g_pieceList[(pieceKing | g_toMove) << 4]; + + // First check if the piece we moved can attack the enemy king + g_inCheck = IsSquareAttackableFrom(theirKingPos, to); + + if (!g_inCheck) { + // Now check if the square we moved from exposes check on the enemy king + g_inCheck = ExposesCheck(from, theirKingPos); + + if (!g_inCheck) { + // Finally, ep. capture can cause another square to be exposed + if (epcEnd != to) { + g_inCheck = ExposesCheck(epcEnd, theirKingPos); + } + } + } + } + else { + // Castle or promotion, slow check + g_inCheck = IsSquareAttackable(g_pieceList[(pieceKing | g_toMove) << 4], 8 - g_toMove); + } + + g_repMoveStack[g_moveCount - 1] = g_hashKeyLow; + g_move50++; + + return true; +} + +function UnmakeMove(move){ + + g_toMove = 8 - g_toMove; + g_baseEval = -g_baseEval; + + g_moveCount--; + g_enPassentSquare = g_moveUndoStack[g_moveCount].ep; + g_castleRights = g_moveUndoStack[g_moveCount].castleRights; + g_inCheck = g_moveUndoStack[g_moveCount].inCheck; + g_baseEval = g_moveUndoStack[g_moveCount].baseEval; + g_hashKeyLow = g_moveUndoStack[g_moveCount].hashKeyLow; + g_hashKeyHigh = g_moveUndoStack[g_moveCount].hashKeyHigh; + g_move50 = g_moveUndoStack[g_moveCount].move50; + + var otherColor = 8 - g_toMove; + var me = g_toMove >> 3; + var them = otherColor >> 3; + + var flags = move & 0xFF0000; + var captured = g_moveUndoStack[g_moveCount].captured; + var to = (move >> 8) & 0xFF; + var from = move & 0xFF; + + var piece = g_board[to]; + var rook,rookIndex; + + if (flags) { + if (flags & moveflagCastleKing) { + rook = g_board[to - 1]; + g_board[to + 1] = rook; + g_board[to - 1] = pieceEmpty; + + rookIndex = g_pieceIndex[to - 1]; + g_pieceIndex[to + 1] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to + 1; + } + else if (flags & moveflagCastleQueen) { + rook = g_board[to + 1]; + g_board[to - 2] = rook; + g_board[to + 1] = pieceEmpty; + + rookIndex = g_pieceIndex[to + 1]; + g_pieceIndex[to - 2] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to - 2; + } + } + + if (flags & moveflagPromotion) { + piece = (g_board[to] & (~0x7)) | piecePawn; + g_board[from] = piece; + + var pawnType = g_board[from] & 0xF; + var promoteType = g_board[to] & 0xF; + + g_pieceCount[promoteType]--; + + var lastPromoteSquare = g_pieceList[(promoteType << 4) | g_pieceCount[promoteType]]; + g_pieceIndex[lastPromoteSquare] = g_pieceIndex[to]; + g_pieceList[(promoteType << 4) | g_pieceIndex[lastPromoteSquare]] = lastPromoteSquare; + g_pieceList[(promoteType << 4) | g_pieceCount[promoteType]] = 0; + g_pieceIndex[to] = g_pieceCount[pawnType]; + g_pieceList[(pawnType << 4) | g_pieceIndex[to]] = to; + g_pieceCount[pawnType]++; + } + else { + g_board[from] = g_board[to]; + } + + var epcEnd = to; + if (flags & moveflagEPC) { + if (g_toMove == colorWhite) + epcEnd = to + 0x10; + else + epcEnd = to - 0x10; + g_board[to] = pieceEmpty; + } + + g_board[epcEnd] = captured; + + // Move our piece in the piece list + g_pieceIndex[from] = g_pieceIndex[to]; + g_pieceList[((piece & 0xF) << 4) | g_pieceIndex[from]] = from; + + if (captured) { + // Restore our piece to the piece list + var captureType = captured & 0xF; + g_pieceIndex[epcEnd] = g_pieceCount[captureType]; + g_pieceList[(captureType << 4) | g_pieceCount[captureType]] = epcEnd; + g_pieceCount[captureType]++; + } +} + +function ExposesCheck(from, kingPos){ + var index = kingPos - from + 128; + // If a queen can't reach it, nobody can! + if ((g_vectorDelta[index].pieceMask[0] & (1 << (pieceQueen))) !== 0) { + var delta = g_vectorDelta[index].delta; + var pos = kingPos + delta; + while (g_board[pos] === 0) pos += delta; + + var piece = g_board[pos]; + if (((piece & (g_board[kingPos] ^ 0x18)) & 0x18) === 0) + return false; + + // Now see if the piece can actually attack the king + var backwardIndex = pos - kingPos + 128; + return (g_vectorDelta[backwardIndex].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) !== 0; + } + return false; +} + +function IsSquareOnPieceLine(target, from) { + var index = from - target + 128; + var piece = g_board[from]; + return (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) ? true : false; +} + +function IsSquareAttackableFrom(target, from){ + var index = from - target + 128; + var piece = g_board[from]; + if (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) { + // Yes, this square is pseudo-attackable. Now, check for real attack + var inc = g_vectorDelta[index].delta; + do { + from += inc; + if (from == target) + return true; + } while (g_board[from] === 0); + } + + return false; +} + +function IsSquareAttackable(target, color) { + // Attackable by pawns? + var inc = color ? -16 : 16; + var pawn = (color ? colorWhite : colorBlack) | 1; + if (g_board[target - (inc - 1)] == pawn) + return true; + if (g_board[target - (inc + 1)] == pawn) + return true; + + // Attackable by pieces? + for (var i = 2; i <= 6; i++) { + var index = (color | i) << 4; + var square = g_pieceList[index]; + while (square !== 0) { + if (IsSquareAttackableFrom(target, square)) + return true; + square = g_pieceList[++index]; + } + } + return false; +} + +function GenerateMove(from, to) { + return from | (to << 8); +} + +function GenerateMove(from, to, flags){ + return from | (to << 8) | flags; +} + +function GenerateValidMoves() { + var moveList = []; + var allMoves = []; + GenerateCaptureMoves(allMoves, null); + GenerateAllMoves(allMoves); + + for (var i = allMoves.length - 1; i >= 0; i--) { + if (MakeMove(allMoves[i])) { + moveList[moveList.length] = allMoves[i]; + UnmakeMove(allMoves[i]); + } else { + } + } + + return moveList; +} + +function GenerateAllMoves(moveStack) { + var from, to, piece, pieceIdx; + + // Pawn quiet moves + pieceIdx = (g_toMove | 1) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + GeneratePawnMoves(moveStack, from); + from = g_pieceList[pieceIdx++]; + } + + // Knight quiet moves + pieceIdx = (g_toMove | 2) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from + 31; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 33; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 14; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 14; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 31; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 33; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 18; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 18; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Bishop quiet moves + pieceIdx = (g_toMove | 3) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from - 15; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 15; } + to = from - 17; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 17; } + to = from + 15; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 15; } + to = from + 17; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 17; } + from = g_pieceList[pieceIdx++]; + } + + // Rook quiet moves + pieceIdx = (g_toMove | 4) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from - 1; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to--; } + to = from + 1; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to++; } + to = from + 16; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 16; } + to = from - 16; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 16; } + from = g_pieceList[pieceIdx++]; + } + + // Queen quiet moves + pieceIdx = (g_toMove | 5) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from - 15; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 15; } + to = from - 17; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 17; } + to = from + 15; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 15; } + to = from + 17; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 17; } + to = from - 1; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to--; } + to = from + 1; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to++; } + to = from + 16; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 16; } + to = from - 16; + while (g_board[to] === 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 16; } + from = g_pieceList[pieceIdx++]; + } + + // King quiet moves + pieceIdx = (g_toMove | 6) << 4; + from = g_pieceList[pieceIdx]; + to = from - 15; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 17; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 15; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 17; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 1; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 1; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 16; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 16; + if (g_board[to] === 0) moveStack[moveStack.length] = GenerateMove(from, to); + + if (!g_inCheck) { + var castleRights = g_castleRights; + if (!g_toMove) + castleRights >>= 2; + if (castleRights & 1) { + // Kingside castle + if (g_board[from + 1] == pieceEmpty && g_board[from + 2] == pieceEmpty) { + moveStack[moveStack.length] = GenerateMove(from, from + 0x02, moveflagCastleKing); + } + } + if (castleRights & 2) { + // Queenside castle + if (g_board[from - 1] == pieceEmpty && g_board[from - 2] == pieceEmpty && g_board[from - 3] == pieceEmpty) { + moveStack[moveStack.length] = GenerateMove(from, from - 0x02, moveflagCastleQueen); + } + } + } +} + +function GenerateCaptureMoves(moveStack, moveScores) { + var from, to, piece, pieceIdx; + var inc = (g_toMove == 8) ? -16 : 16; + var enemy = g_toMove == 8 ? 0x10 : 0x8; + + // Pawn captures + pieceIdx = (g_toMove | 1) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from + inc - 1; + if (g_board[to] & enemy) { + MovePawnTo(moveStack, from, to); + } + + to = from + inc + 1; + if (g_board[to] & enemy) { + MovePawnTo(moveStack, from, to); + } + + from = g_pieceList[pieceIdx++]; + } + + if (g_enPassentSquare !== -1) { + inc = (g_toMove === colorWhite) ? -16 : 16; + var pawn = g_toMove | piecePawn; + + from = g_enPassentSquare - (inc + 1); + if ((g_board[from] & 0xF) === pawn) { + moveStack[moveStack.length] = GenerateMove(from, g_enPassentSquare, moveflagEPC); + } + + from = g_enPassentSquare - (inc - 1); + if ((g_board[from] & 0xF) === pawn) { + moveStack[moveStack.length] = GenerateMove(from, g_enPassentSquare, moveflagEPC); + } + } + + // Knight captures + pieceIdx = (g_toMove | 2) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from + 31; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 33; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 14; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 14; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 31; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 33; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 18; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 18; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Bishop captures + pieceIdx = (g_toMove | 3) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from; + do { to -= 15; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to -= 17; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to += 15; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to += 17; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Rook captures + pieceIdx = (g_toMove | 4) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from; + do { to--; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to++; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to -= 16; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to += 16; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Queen captures + pieceIdx = (g_toMove | 5) << 4; + from = g_pieceList[pieceIdx++]; + while (from !== 0) { + to = from; + do { to -= 15; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to -= 17; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to += 15; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to += 17; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to--; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to++; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to -= 16; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; + do { to += 16; } while (g_board[to] === 0); + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // King captures + pieceIdx = (g_toMove | 6) << 4; + from = g_pieceList[pieceIdx]; + to = from - 15; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 17; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 15; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 17; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 1; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 1; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 16; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 16; + if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); +} + +function MovePawnTo(moveStack, start, square) { + var row = square & 0xF0; + if ((row == 0x90) || (row == 0x20)) { + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteQueen); + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteKnight); + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteBishop); + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion); + } + else { + moveStack[moveStack.length] = GenerateMove(start, square, 0); + } +} + +function GeneratePawnMoves(moveStack, from) { + var piece = g_board[from]; + var color = piece & colorWhite; + var inc = (color === colorWhite) ? -16 : 16; + + // Quiet pawn moves + var to = from + inc; + if (g_board[to] === 0) { + MovePawnTo(moveStack, from, to, pieceEmpty); + + // Check if we can do a 2 square jump + if ((((from & 0xF0) === 0x30) && color !== colorWhite) || + (((from & 0xF0) === 0x80) && color === colorWhite)) { + to += inc; + if (g_board[to] === 0) { + moveStack[moveStack.length] = GenerateMove(from, to); + } + } + } +} + +function UndoHistory(ep, castleRights, inCheck, baseEval, hashKeyLow, hashKeyHigh, move50, captured) { + this.ep = ep; + this.castleRights = castleRights; + this.inCheck = inCheck; + this.baseEval = baseEval; + this.hashKeyLow = hashKeyLow; + this.hashKeyHigh = hashKeyHigh; + this.move50 = move50; + this.captured = captured; +} + +var g_seeValues = [ 0, 1, 3, 3, 5, 9, 900, 0, + 0, 1, 3, 3, 5, 9, 900, 0]; + +function See(move) { + var from = move & 0xFF; + var to = (move >> 8) & 0xFF; + + var fromPiece = g_board[from]; + + var fromValue = g_seeValues[fromPiece & 0xF]; + var toValue = g_seeValues[g_board[to] & 0xF]; + var pieceType,pieceValue,i; + + if (fromValue <= toValue) { + return true; + } + + if (move >> 16) { + // Castles, promotion, ep are always good + return true; + } + + var us = (fromPiece & colorWhite) ? colorWhite : 0; + var them = 8 - us; + + // Pawn attacks + // If any opponent pawns can capture back, this capture is probably not worthwhile (as we must be using knight or above). + var inc = (fromPiece & colorWhite) ? -16 : 16; // Note: this is capture direction from to, so reversed from normal move direction + if (((g_board[to + inc + 1] & 0xF) == (piecePawn | them)) || + ((g_board[to + inc - 1] & 0xF) == (piecePawn | them))) { + return false; + } + + var themAttacks = []; + + // Knight attacks + // If any opponent knights can capture back, and the deficit we have to make up is greater than the knights value, + // it's not worth it. We can capture on this square again, and the opponent doesn't have to capture back. + var captureDeficit = fromValue - toValue; + SeeAddKnightAttacks(to, them, themAttacks); + if (themAttacks.length !== 0 && captureDeficit > g_seeValues[pieceKnight]) { + return false; + } + + // Slider attacks + g_board[from] = 0; + for (pieceType = pieceBishop; pieceType <= pieceQueen; pieceType++) { + if (SeeAddSliderAttacks(to, them, themAttacks, pieceType)) { + if (captureDeficit > g_seeValues[pieceType]) { + g_board[from] = fromPiece; + return false; + } + } + } + + // Pawn defenses + // At this point, we are sure we are making a "losing" capture. The opponent can not capture back with a + // pawn. They cannot capture back with a minor/major and stand pat either. So, if we can capture with + // a pawn, it's got to be a winning or equal capture. + if (((g_board[to - inc + 1] & 0xF) === (piecePawn | us)) || + ((g_board[to - inc - 1] & 0xF) === (piecePawn | us))) { + g_board[from] = fromPiece; + return true; + } + + // King attacks + SeeAddSliderAttacks(to, them, themAttacks, pieceKing); + + // Our attacks + var usAttacks = []; + SeeAddKnightAttacks(to, us, usAttacks); + for (pieceType = pieceBishop; pieceType <= pieceKing; pieceType++) { + SeeAddSliderAttacks(to, us, usAttacks, pieceType); + } + + g_board[from] = fromPiece; + + // We are currently winning the amount of material of the captured piece, time to see if the opponent + // can get it back somehow. We assume the opponent can capture our current piece in this score, which + // simplifies the later code considerably. + var seeValue = toValue - fromValue; + + for (; ; ) { + var capturingPieceValue = 1000; + var capturingPieceIndex = -1; + + // Find the least valuable piece of the opponent that can attack the square + for (i = 0; i < themAttacks.length; i++) { + if (themAttacks[i] !== 0) { + pieceValue = g_seeValues[g_board[themAttacks[i]] & 0x7]; + if (pieceValue < capturingPieceValue) { + capturingPieceValue = pieceValue; + capturingPieceIndex = i; + } + } + } + + if (capturingPieceIndex == -1) { + // Opponent can't capture back, we win + return true; + } + + // Now, if seeValue < 0, the opponent is winning. If even after we take their piece, + // we can't bring it back to 0, then we have lost this battle. + seeValue += capturingPieceValue; + if (seeValue < 0) { + return false; + } + + var capturingPieceSquare = themAttacks[capturingPieceIndex]; + themAttacks[capturingPieceIndex] = 0; + + // Add any x-ray attackers + SeeAddXrayAttack(to, capturingPieceSquare, us, usAttacks, themAttacks); + + // Our turn to capture + capturingPieceValue = 1000; + capturingPieceIndex = -1; + + // Find our least valuable piece that can attack the square + for (i = 0; i < usAttacks.length; i++) { + if (usAttacks[i] !== 0) { + pieceValue = g_seeValues[g_board[usAttacks[i]] & 0x7]; + if (pieceValue < capturingPieceValue) { + capturingPieceValue = pieceValue; + capturingPieceIndex = i; + } + } + } + + if (capturingPieceIndex == -1) { + // We can't capture back, we lose :( + return false; + } + + // Assume our opponent can capture us back, and if we are still winning, we can stand-pat + // here, and assume we've won. + seeValue -= capturingPieceValue; + if (seeValue >= 0) { + return true; + } + + capturingPieceSquare = usAttacks[capturingPieceIndex]; + usAttacks[capturingPieceIndex] = 0; + + // Add any x-ray attackers + SeeAddXrayAttack(to, capturingPieceSquare, us, usAttacks, themAttacks); + } +} + +function SeeAddXrayAttack(target, square, us, usAttacks, themAttacks) { + var index = square - target + 128; + var delta = -g_vectorDelta[index].delta; + if (delta === 0) + return; + square += delta; + while (g_board[square] === 0) { + square += delta; + } + + if ((g_board[square] & 0x18) && IsSquareOnPieceLine(target, square)) { + if ((g_board[square] & 8) == us) { + usAttacks[usAttacks.length] = square; + } else { + themAttacks[themAttacks.length] = square; + } + } +} + +// target = attacking square, us = color of knights to look for, attacks = array to add squares to +function SeeAddKnightAttacks(target, us, attacks) { + var pieceIdx = (us | pieceKnight) << 4; + var attackerSq = g_pieceList[pieceIdx++]; + + while (attackerSq !== 0) { + if (IsSquareOnPieceLine(target, attackerSq)) { + attacks[attacks.length] = attackerSq; + } + attackerSq = g_pieceList[pieceIdx++]; + } +} + +function SeeAddSliderAttacks(target, us, attacks, pieceType) { + var pieceIdx = (us | pieceType) << 4; + var attackerSq = g_pieceList[pieceIdx++]; + var hit = false; + + while (attackerSq !== 0) { + if (IsSquareAttackableFrom(target, attackerSq)) { + attacks[attacks.length] = attackerSq; + hit = true; + } + attackerSq = g_pieceList[pieceIdx++]; + } + + return hit; +} + +function BuildPVMessage(bestMove, value, timeTaken, ply) { + var totalNodes = g_nodeCount + g_qNodeCount; + return "Ply:" + ply + " Score:" + value + " Nodes:" + totalNodes + " NPS:" + ((totalNodes / (timeTaken / 1000)) | 0) + " " + PVFromHash(bestMove, 15); +} + +////////////////////////////////////////////////// +// Test Harness +////////////////////////////////////////////////// +function FinishPlyCallback(bestMove, value, timeTaken, ply) { + postMessage("pv " + BuildPVMessage(bestMove, value, timeTaken, ply)); +} + +function FinishMoveLocalTesting(bestMove, value, timeTaken, ply) { + if (bestMove !== undefined) { + MakeMove(bestMove); + postMessage(FormatMove(bestMove)); + } +} + +var needsReset = true; +self.onmessage = function (e) { + if (e.data == "go" || needsReset) { + ResetGame(); + needsReset = false; + if (e.data == "go") return; + } + if (e.data.match("^position") == "position") { + ResetGame(); + var result = InitializeFromFen(e.data.substr(9, e.data.length - 9)); + if (result.length !== 0) { + postMessage("message " + result); + } + } else if (e.data.match("^search") == "search") { + var level = e.data.substr(7,e.data.length-7).split(","); + g_timeout = parseInt(level[0], 10); + g_maxply = parseInt(level[1], 10); + Search(FinishMoveLocalTesting, g_maxply, FinishPlyCallback); + } else if (e.data == "analyze") { + g_timeout = 99999999999; + Search(null, g_maxply, FinishPlyCallback); + } else { + MakeMove(GetMoveFromString(e.data)); + } +}; + +function debug(msg) { + if (g_debug) { + if(worker) { + postMessage("console: "+msg); + } else { + console.log(msg); + } + } +} \ No newline at end of file diff --git a/js/AI/garbochess_unclean.js b/js/AI/garbochess_unclean.js new file mode 100644 index 0000000..cc95bc1 --- /dev/null +++ b/js/AI/garbochess_unclean.js @@ -0,0 +1,2538 @@ +"use strict"; + +// Perf TODO: +// Merge material updating with psq values +// Put move scoring inline in generator +// Remove need for fliptable in psq tables. Access them by color +// Optimize pawn move generation + +// Non-perf todo: +// Checks in first q? +// Pawn eval. +// Better king evaluation +// Better move sorting in PV nodes (especially root) + +var g_debug = true; +var g_timeout = 40; + +function GetFen(){ + var result = ""; + for (var row = 0; row < 8; row++) { + if (row != 0) + result += '/'; + var empty = 0; + for (var col = 0; col < 8; col++) { + var piece = g_board[((row + 2) << 4) + col + 4]; + if (piece == 0) { + empty++; + } + else { + if (empty != 0) + result += empty; + empty = 0; + + var pieceChar = [" ", "p", "n", "b", "r", "q", "k", " "][(piece & 0x7)]; + result += ((piece & colorWhite) != 0) ? pieceChar.toUpperCase() : pieceChar; + } + } + if (empty != 0) { + result += empty; + } + } + + result += g_toMove == colorWhite ? " w" : " b"; + result += " "; + if (g_castleRights == 0) { + result += "-"; + } + else { + if ((g_castleRights & 1) != 0) + result += "K"; + if ((g_castleRights & 2) != 0) + result += "Q"; + if ((g_castleRights & 4) != 0) + result += "k"; + if ((g_castleRights & 8) != 0) + result += "q"; + } + + result += " "; + + if (g_enPassentSquare == -1) { + result += '-'; + } + else { + result += FormatSquare(g_enPassentSquare); + } + + return result; +} + + +function GetMoveSAN(move, validMoves) { + var from = move & 0xFF; + var to = (move >> 8) & 0xFF; + + if (move & moveflagCastleKing) return "O-O"; + if (move & moveflagCastleQueen) return "O-O-O"; + + var pieceType = g_board[from] & 0x7; + var result = ["", "", "N", "B", "R", "Q", "K", ""][pieceType]; + + var dupe = false, rowDiff = true, colDiff = true; + if (validMoves == null) { + validMoves = GenerateValidMoves(); + } + for (var i = 0; i < validMoves.length; i++) { + var moveFrom = validMoves[i] & 0xFF; + var moveTo = (validMoves[i] >> 8) & 0xFF; + if (moveFrom != from && + moveTo == to && + (g_board[moveFrom] & 0x7) == pieceType) { + dupe = true; + if ((moveFrom & 0xF0) == (from & 0xF0)) { + rowDiff = false; + } + if ((moveFrom & 0x0F) == (from & 0x0F)) { + colDiff = false; + } + } + } + + if (dupe) { + if (colDiff) { + result += FormatSquare(from).charAt(0); + } else if (rowDiff) { + result += FormatSquare(from).charAt(1); + } else { + result += FormatSquare(from); + } + } else if (pieceType == piecePawn && (g_board[to] != 0 || (move & moveflagEPC))) { + result += FormatSquare(from).charAt(0); + } + + if (g_board[to] != 0 || (move & moveflagEPC)) { + result += "x"; + } + + result += FormatSquare(to); + + if (move & moveflagPromotion) { + if (move & moveflagPromoteBishop) result += "=B"; + else if (move & moveflagPromoteKnight) result += "=N"; + else if (move & moveflagPromoteQueen) result += "=Q"; + else result += "=R"; + } + + MakeMove(move); + if (g_inCheck) { + result += GenerateValidMoves().length == 0 ? "#" : "+"; + } + UnmakeMove(move); + + return result; +} + +function FormatSquare(square) { + var letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']; + return letters[(square & 0xF) - 4] + ((9 - (square >> 4)) + 1); +} + +function FormatMove(move) { + var result = FormatSquare(move & 0xFF) + FormatSquare((move >> 8) & 0xFF); + if (move & moveflagPromotion) { + if (move & moveflagPromoteBishop) result += "b"; + else if (move & moveflagPromoteKnight) result += "n"; + else if (move & moveflagPromoteQueen) result += "q"; + else result += "r"; + } + return result; +} + +function GetMoveFromString(moveString) { + var moves = GenerateValidMoves(); + for (var i = 0; i < moves.length; i++) { + if (FormatMove(moves[i]) == moveString) { + return moves[i]; + } + } + alert("busted! ->" + moveString + " fen:" + GetFen()); +} + +function PVFromHash(move, ply) { + if (ply == 0) + return ""; + + if (move == 0) { + if (g_inCheck) return "checkmate"; + return "stalemate"; + } + + var pvString = " " + GetMoveSAN(move); + MakeMove(move); + + var hashNode = g_hashTable[g_hashKeyLow & g_hashMask]; + if (hashNode != null && hashNode.lock == g_hashKeyHigh && hashNode.bestMove != null) { + pvString += PVFromHash(hashNode.bestMove, ply - 1); + } + + UnmakeMove(move); + + return pvString; +} + +// +// Searching code +// + +var g_startTime; + +var g_nodeCount; +var g_qNodeCount; +var g_searchValid; +var g_globalPly = 0; + +function Search(finishMoveCallback, maxPly, finishPlyCallback) { + var lastEval; + var alpha = minEval; + var beta = maxEval; + + g_globalPly++; + g_nodeCount = 0; + g_qNodeCount = 0; + g_searchValid = true; + + var bestMove = 0; + var value; + + g_startTime = (new Date()).getTime(); + + var i; + for (i = 1; i <= maxPly && g_searchValid; i++) { + var tmp = AlphaBeta(i, 0, alpha, beta); + if (!g_searchValid) break; + + value = tmp; + + if (value > alpha && value < beta) { + alpha = value - 500; + beta = value + 500; + + if (alpha < minEval) alpha = minEval; + if (beta > maxEval) beta = maxEval; + } else if (alpha != minEval) { + alpha = minEval; + beta = maxEval; + i--; + } + + if (g_hashTable[g_hashKeyLow & g_hashMask] != null) { + bestMove = g_hashTable[g_hashKeyLow & g_hashMask].bestMove; + } + + if (finishPlyCallback != null) { + finishPlyCallback(bestMove, value, (new Date()).getTime() - g_startTime, i); + } + } + + if (finishMoveCallback != null) { + finishMoveCallback(bestMove, value, (new Date()).getTime() - g_startTime, i - 1); + } +} + +var minEval = -2000000; +var maxEval = +2000000; + +var minMateBuffer = minEval + 2000; +var maxMateBuffer = maxEval - 2000; + +var materialTable = [0, 800, 3350, 3450, 5000, 9750, 600000]; + +var pawnAdj = +[ + 0, 0, 0, 0, 0, 0, 0, 0, + -25, 105, 135, 270, 270, 135, 105, -25, + -80, 0, 30, 176, 176, 30, 0, -80, + -85, -5, 25, 175, 175, 25, -5, -85, + -90, -10, 20, 125, 125, 20, -10, -90, + -95, -15, 15, 75, 75, 15, -15, -95, + -100, -20, 10, 70, 70, 10, -20, -100, + 0, 0, 0, 0, 0, 0, 0, 0 +]; + +var knightAdj = + [-200, -100, -50, -50, -50, -50, -100, -200, + -100, 0, 0, 0, 0, 0, 0, -100, + -50, 0, 60, 60, 60, 60, 0, -50, + -50, 0, 30, 60, 60, 30, 0, -50, + -50, 0, 30, 60, 60, 30, 0, -50, + -50, 0, 30, 30, 30, 30, 0, -50, + -100, 0, 0, 0, 0, 0, 0, -100, + -200, -50, -25, -25, -25, -25, -50, -200 + ]; + +var bishopAdj = + [ -50,-50,-25,-10,-10,-25,-50,-50, + -50,-25,-10, 0, 0,-10,-25,-50, + -25,-10, 0, 25, 25, 0,-10,-25, + -10, 0, 25, 40, 40, 25, 0,-10, + -10, 0, 25, 40, 40, 25, 0,-10, + -25,-10, 0, 25, 25, 0,-10,-25, + -50,-25,-10, 0, 0,-10,-25,-50, + -50,-50,-25,-10,-10,-25,-50,-50 + ]; + +var rookAdj = + [ -60, -30, -10, 20, 20, -10, -30, -60, + 40, 70, 90,120,120, 90, 70, 40, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60, + -60, -30, -10, 20, 20, -10, -30, -60 + ]; + +var kingAdj = + [ 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 50, 150, -25, -125, -125, -25, 150, 50, + 150, 250, 75, -25, -25, 75, 250, 150 + ]; + +var emptyAdj = + [0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + ]; + +var pieceSquareAdj = new Array(8); + +// Returns the square flipped +var flipTable = new Array(256); + +function PawnEval(color) { + var pieceIdx = (color | 1) << 4; + var from = g_pieceList[pieceIdx++]; + while (from != 0) { + from = g_pieceList[pieceIdx++]; + } +} + +function Mobility(color) { + var result = 0; + var from, to, mob, pieceIdx; + var enemy = color == 8 ? 0x10 : 0x8 + var mobUnit = color == 8 ? g_mobUnit[0] : g_mobUnit[1]; + + // Knight mobility + mob = -3; + pieceIdx = (color | 2) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + mob += mobUnit[g_board[from + 31]]; + mob += mobUnit[g_board[from + 33]]; + mob += mobUnit[g_board[from + 14]]; + mob += mobUnit[g_board[from - 14]]; + mob += mobUnit[g_board[from - 31]]; + mob += mobUnit[g_board[from - 33]]; + mob += mobUnit[g_board[from + 18]]; + mob += mobUnit[g_board[from - 18]]; + from = g_pieceList[pieceIdx++]; + } + result += 65 * mob; + + // Bishop mobility + mob = -4; + pieceIdx = (color | 3) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from - 15; while (g_board[to] == 0) { to -= 15; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to -= 15; while (g_board[to] == 0) to -= 15; + mob += mobUnit[g_board[to]] << 2; + } + } + + to = from - 17; while (g_board[to] == 0) { to -= 17; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to -= 17; while (g_board[to] == 0) to -= 17; + mob += mobUnit[g_board[to]] << 2; + } + } + + to = from + 15; while (g_board[to] == 0) { to += 15; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to += 15; while (g_board[to] == 0) to += 15; + mob += mobUnit[g_board[to]] << 2; + } + } + + to = from + 17; while (g_board[to] == 0) { to += 17; mob++; } + if (g_board[to] & enemy) { + mob++; + if (!(g_board[to] & piecePawn)) { + to += 17; while (g_board[to] == 0) to += 17; + mob += mobUnit[g_board[to]] << 2; + } + } + + from = g_pieceList[pieceIdx++]; + } + result += 44 * mob; + + // Rook mobility + mob = -4; + pieceIdx = (color | 4) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from - 1; while (g_board[to] == 0) { to--; mob++;} if (g_board[to] & enemy) mob++; + to = from + 1; while (g_board[to] == 0) { to++; mob++; } if (g_board[to] & enemy) mob++; + to = from + 16; while (g_board[to] == 0) { to += 16; mob++; } if (g_board[to] & enemy) mob++; + to = from - 16; while (g_board[to] == 0) { to -= 16; mob++; } if (g_board[to] & enemy) mob++; + from = g_pieceList[pieceIdx++]; + } + result += 25 * mob; + + // Queen mobility + mob = -2; + pieceIdx = (color | 5) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from - 15; while (g_board[to] == 0) { to -= 15; mob++; } if (g_board[to] & enemy) mob++; + to = from - 17; while (g_board[to] == 0) { to -= 17; mob++; } if (g_board[to] & enemy) mob++; + to = from + 15; while (g_board[to] == 0) { to += 15; mob++; } if (g_board[to] & enemy) mob++; + to = from + 17; while (g_board[to] == 0) { to += 17; mob++; } if (g_board[to] & enemy) mob++; + to = from - 1; while (g_board[to] == 0) { to--; mob++; } if (g_board[to] & enemy) mob++; + to = from + 1; while (g_board[to] == 0) { to++; mob++; } if (g_board[to] & enemy) mob++; + to = from + 16; while (g_board[to] == 0) { to += 16; mob++; } if (g_board[to] & enemy) mob++; + to = from - 16; while (g_board[to] == 0) { to -= 16; mob++; } if (g_board[to] & enemy) mob++; + from = g_pieceList[pieceIdx++]; + } + result += 22 * mob; + + return result; +} + +function Evaluate() { + var curEval = g_baseEval; + + var evalAdjust = 0; + // Black queen gone, then cancel white's penalty for king movement + if (g_pieceList[pieceQueen << 4] == 0) + evalAdjust -= pieceSquareAdj[pieceKing][g_pieceList[(colorWhite | pieceKing) << 4]]; + // White queen gone, then cancel black's penalty for king movement + if (g_pieceList[(colorWhite | pieceQueen) << 4] == 0) + evalAdjust += pieceSquareAdj[pieceKing][flipTable[g_pieceList[pieceKing << 4]]]; + + // Black bishop pair + if (g_pieceCount[pieceBishop] >= 2) + evalAdjust -= 500; + // White bishop pair + if (g_pieceCount[pieceBishop | colorWhite] >= 2) + evalAdjust += 500; + + var mobility = Mobility(8) - Mobility(0); + + if (g_toMove == 0) { + // Black + curEval -= mobility; + curEval -= evalAdjust; + } + else { + curEval += mobility; + curEval += evalAdjust; + } + + return curEval; +} + +function ScoreMove(move){ + var moveTo = (move >> 8) & 0xFF; + var captured = g_board[moveTo] & 0x7; + var piece = g_board[move & 0xFF]; + var score; + if (captured != 0) { + var pieceType = piece & 0x7; + score = (captured << 5) - pieceType; + } else { + score = historyTable[piece & 0xF][moveTo]; + } + return score; +} + +function QSearch(alpha, beta, ply) { + g_qNodeCount++; + + var realEval = g_inCheck ? (minEval + 1) : Evaluate(); + + if (realEval >= beta) + return realEval; + + if (realEval > alpha) + alpha = realEval; + + var moves = new Array(); + var moveScores = new Array(); + var wasInCheck = g_inCheck; + + if (wasInCheck) { + // TODO: Fast check escape generator and fast checking moves generator + GenerateCaptureMoves(moves, null); + GenerateAllMoves(moves); + + for (var i = 0; i < moves.length; i++) { + moveScores[i] = ScoreMove(moves[i]); + } + } else { + GenerateCaptureMoves(moves, null); + + for (var i = 0; i < moves.length; i++) { + var captured = g_board[(moves[i] >> 8) & 0xFF] & 0x7; + var pieceType = g_board[moves[i] & 0xFF] & 0x7; + + moveScores[i] = (captured << 5) - pieceType; + } + } + + for (var i = 0; i < moves.length; i++) { + var bestMove = i; + for (var j = moves.length - 1; j > i; j--) { + if (moveScores[j] > moveScores[bestMove]) { + bestMove = j; + } + } + { + var tmpMove = moves[i]; + moves[i] = moves[bestMove]; + moves[bestMove] = tmpMove; + + var tmpScore = moveScores[i]; + moveScores[i] = moveScores[bestMove]; + moveScores[bestMove] = tmpScore; + } + + if (!wasInCheck && !See(moves[i])) { + continue; + } + + if (!MakeMove(moves[i])) { + continue; + } + + var value = -QSearch(-beta, -alpha, ply - 1); + + UnmakeMove(moves[i]); + + if (value > realEval) { + if (value >= beta) + return value; + + if (value > alpha) + alpha = value; + + realEval = value; + } + } + + /* Disable checks... Too slow currently + + if (ply == 0 && !wasInCheck) { + moves = new Array(); + GenerateAllMoves(moves); + + for (var i = 0; i < moves.length; i++) { + moveScores[i] = ScoreMove(moves[i]); + } + + for (var i = 0; i < moves.length; i++) { + var bestMove = i; + for (var j = moves.length - 1; j > i; j--) { + if (moveScores[j] > moveScores[bestMove]) { + bestMove = j; + } + } + { + var tmpMove = moves[i]; + moves[i] = moves[bestMove]; + moves[bestMove] = tmpMove; + + var tmpScore = moveScores[i]; + moveScores[i] = moveScores[bestMove]; + moveScores[bestMove] = tmpScore; + } + + if (!MakeMove(moves[i])) { + continue; + } + var checking = g_inCheck; + UnmakeMove(moves[i]); + + if (!checking) { + continue; + } + + if (!See(moves[i])) { + continue; + } + + MakeMove(moves[i]); + + var value = -QSearch(-beta, -alpha, ply - 1); + + UnmakeMove(moves[i]); + + if (value > realEval) { + if (value >= beta) + return value; + + if (value > alpha) + alpha = value; + + realEval = value; + } + } + } + */ + + return realEval; +} + +function StoreHash(value, flags, ply, move, depth) { + if (value >= maxMateBuffer) + value += depth; + else if (value <= minMateBuffer) + value -= depth; + g_hashTable[g_hashKeyLow & g_hashMask] = new HashEntry(g_hashKeyHigh, value, flags, ply, move); +} + +function IsHashMoveValid(hashMove) { + var from = hashMove & 0xFF; + var to = (hashMove >> 8) & 0xFF; + var ourPiece = g_board[from]; + var pieceType = ourPiece & 0x7; + if (pieceType < piecePawn || pieceType > pieceKing) return false; + // Can't move a piece we don't control + if (g_toMove != (ourPiece & 0x8)) + return false; + // Can't move to a square that has something of the same color + if (g_board[to] != 0 && (g_toMove == (g_board[to] & 0x8))) + return false; + if (pieceType == piecePawn) { + if (hashMove & moveflagEPC) { + return false; + } + + // Valid moves are push, capture, double push, promotions + var dir = to - from; + if ((g_toMove == colorWhite) != (dir < 0)) { + // Pawns have to move in the right direction + return false; + } + + var row = to & 0xF0; + if (((row == 0x90 && !g_toMove) || + (row == 0x20 && g_toMove)) != (hashMove & moveflagPromotion)) { + // Handle promotions + return false; + } + + if (dir == -16 || dir == 16) { + // White/Black push + return g_board[to] == 0; + } else if (dir == -15 || dir == -17 || dir == 15 || dir == 17) { + // White/Black capture + return g_board[to] != 0; + } else if (dir == -32) { + // Double white push + if (row != 0x60) return false; + if (g_board[to] != 0) return false; + if (g_board[from - 16] != 0) return false; + } else if (dir == 32) { + // Double black push + if (row != 0x50) return false; + if (g_board[to] != 0) return false; + if (g_board[from + 16] != 0) return false; + } else { + return false; + } + + return true; + } else { + // This validates that this piece type can actually make the attack + if (hashMove >> 16) return false; + return IsSquareAttackableFrom(to, from); + } +} + +function IsRepDraw() { + var stop = g_moveCount - 1 - g_move50; + stop = stop < 0 ? 0 : stop; + for (var i = g_moveCount - 5; i >= stop; i -= 2) { + if (g_repMoveStack[i] == g_hashKeyLow) + return true; + } + return false; +} + +function MovePicker(hashMove, depth, killer1, killer2) { + this.hashMove = hashMove; + this.depth = depth; + this.killer1 = killer1; + this.killer2 = killer2; + + this.moves = new Array(); + this.losingCaptures = null; + this.moveCount = 0; + this.atMove = -1; + this.moveScores = null; + this.stage = 0; + + this.nextMove = function () { + if (++this.atMove == this.moveCount) { + this.stage++; + if (this.stage == 1) { + if (this.hashMove != null && IsHashMoveValid(hashMove)) { + this.moves[0] = hashMove; + this.moveCount = 1; + } + if (this.moveCount != 1) { + this.hashMove = null; + this.stage++; + } + } + + if (this.stage == 2) { + GenerateCaptureMoves(this.moves, null); + this.moveCount = this.moves.length; + this.moveScores = new Array(this.moveCount); + // Move ordering + for (var i = this.atMove; i < this.moveCount; i++) { + var captured = g_board[(this.moves[i] >> 8) & 0xFF] & 0x7; + var pieceType = g_board[this.moves[i] & 0xFF] & 0x7; + this.moveScores[i] = (captured << 5) - pieceType; + } + // No moves, onto next stage + if (this.atMove == this.moveCount) this.stage++; + } + + if (this.stage == 3) { + if (IsHashMoveValid(this.killer1) && + this.killer1 != this.hashMove) { + this.moves[this.moves.length] = this.killer1; + this.moveCount = this.moves.length; + } else { + this.killer1 = 0; + this.stage++; + } + } + + if (this.stage == 4) { + if (IsHashMoveValid(this.killer2) && + this.killer2 != this.hashMove) { + this.moves[this.moves.length] = this.killer2; + this.moveCount = this.moves.length; + } else { + this.killer2 = 0; + this.stage++; + } + } + + if (this.stage == 5) { + GenerateAllMoves(this.moves); + this.moveCount = this.moves.length; + // Move ordering + for (var i = this.atMove; i < this.moveCount; i++) this.moveScores[i] = ScoreMove(this.moves[i]); + // No moves, onto next stage + if (this.atMove == this.moveCount) this.stage++; + } + + if (this.stage == 6) { + // Losing captures + if (this.losingCaptures != null) { + for (var i = 0; i < this.losingCaptures.length; i++) { + this.moves[this.moves.length] = this.losingCaptures[i]; + } + for (var i = this.atMove; i < this.moveCount; i++) this.moveScores[i] = ScoreMove(this.moves[i]); + this.moveCount = this.moves.length; + } + // No moves, onto next stage + if (this.atMove == this.moveCount) this.stage++; + } + + if (this.stage == 7) + return 0; + } + + var bestMove = this.atMove; + for (var j = this.atMove + 1; j < this.moveCount; j++) { + if (this.moveScores[j] > this.moveScores[bestMove]) { + bestMove = j; + } + } + + if (bestMove != this.atMove) { + var tmpMove = this.moves[this.atMove]; + this.moves[this.atMove] = this.moves[bestMove]; + this.moves[bestMove] = tmpMove; + + var tmpScore = this.moveScores[this.atMove]; + this.moveScores[this.atMove] = this.moveScores[bestMove]; + this.moveScores[bestMove] = tmpScore; + } + + var candidateMove = this.moves[this.atMove]; + if ((this.stage > 1 && candidateMove == this.hashMove) || + (this.stage > 3 && candidateMove == this.killer1) || + (this.stage > 4 && candidateMove == this.killer2)) { + return this.nextMove(); + } + + if (this.stage == 2 && !See(candidateMove)) { + if (this.losingCaptures == null) { + this.losingCaptures = new Array(); + } + this.losingCaptures[this.losingCaptures.length] = candidateMove; + return this.nextMove(); + } + + return this.moves[this.atMove]; + } +} + +function AllCutNode(ply, depth, beta, allowNull) { + if (ply <= 0) { + return QSearch(beta - 1, beta, 0); + } + + if ((g_nodeCount & 127) == 127) { + if ((new Date()).getTime() - g_startTime > g_timeout) { + // Time cutoff + g_searchValid = false; + return beta - 1; + } + } + + g_nodeCount++; + + if (IsRepDraw()) + return 0; + + // Mate distance pruning + if (minEval + depth >= beta) + return beta; + + if (maxEval - (depth + 1) < beta) + return beta - 1; + + var hashMove = null; + var hashNode = g_hashTable[g_hashKeyLow & g_hashMask]; + if (hashNode != null && hashNode.lock == g_hashKeyHigh) { + hashMove = hashNode.bestMove; + if (hashNode.hashDepth >= ply) { + var hashValue = hashNode.value; + + // Fixup mate scores + if (hashValue >= maxMateBuffer) + hashValue -= depth; + else if (hashValue <= minMateBuffer) + hashValue += depth; + + if (hashNode.flags == hashflagExact) + return hashValue; + if (hashNode.flags == hashflagAlpha && hashValue < beta) + return hashValue; + if (hashNode.flags == hashflagBeta && hashValue >= beta) + return hashValue; + } + } + + // TODO - positional gain? + + if (!g_inCheck && + allowNull && + beta > minMateBuffer && + beta < maxMateBuffer) { + // Try some razoring + if (hashMove == null && + ply < 4) { + var razorMargin = 2500 + 200 * ply; + if (g_baseEval < beta - razorMargin) { + var razorBeta = beta - razorMargin; + var v = QSearch(razorBeta - 1, razorBeta, 0); + if (v < razorBeta) + return v; + } + } + + // TODO - static null move + + // Null move + if (ply > 1 && + g_baseEval >= beta - (ply >= 4 ? 2500 : 0) && + // Disable null move if potential zugzwang (no big pieces) + (g_pieceCount[pieceBishop | g_toMove] != 0 || + g_pieceCount[pieceKnight | g_toMove] != 0 || + g_pieceCount[pieceRook | g_toMove] != 0 || + g_pieceCount[pieceQueen | g_toMove] != 0)) { + var r = 3 + (ply >= 5 ? 1 : ply / 4); + if (g_baseEval - beta > 1500) r++; + + g_toMove = 8 - g_toMove; + g_baseEval = -g_baseEval; + g_hashKeyLow ^= g_zobristBlackLow; + g_hashKeyHigh ^= g_zobristBlackHigh; + + var value = -AllCutNode(ply - r, depth + 1, -(beta - 1), false); + + g_hashKeyLow ^= g_zobristBlackLow; + g_hashKeyHigh ^= g_zobristBlackHigh; + g_toMove = 8 - g_toMove; + g_baseEval = -g_baseEval; + + if (value >= beta) + return beta; + } + } + + var moveMade = false; + var realEval = minEval - 1; + var inCheck = g_inCheck; + + var movePicker = new MovePicker(hashMove, depth, g_killers[depth][0], g_killers[depth][1]); + + for (;;) { + var currentMove = movePicker.nextMove(); + if (currentMove == 0) { + break; + } + + var plyToSearch = ply - 1; + + if (!MakeMove(currentMove)) { + continue; + } + + var value; + var doFullSearch = true; + + if (g_inCheck) { + // Check extensions + plyToSearch++; + } else { + var reduced = plyToSearch - (movePicker.atMove > 14 ? 2 : 1); + + // Futility pruning +/* if (movePicker.stage == 5 && !inCheck) { + if (movePicker.atMove >= (15 + (1 << (5 * ply) >> 2)) && + realEval > minMateBuffer) { + UnmakeMove(currentMove); + continue; + } + + if (ply < 7) { + var reducedPly = reduced <= 0 ? 0 : reduced; + var futilityValue = -g_baseEval + (900 * (reducedPly + 2)) - (movePicker.atMove * 10); + if (futilityValue < beta) { + if (futilityValue > realEval) { + realEval = futilityValue; + } + UnmakeMove(currentMove); + continue; + } + } + }*/ + + // Late move reductions + if (movePicker.stage == 5 && movePicker.atMove > 5 && ply >= 3) { + value = -AllCutNode(reduced, depth + 1, -(beta - 1), true); + doFullSearch = (value >= beta); + } + } + + if (doFullSearch) { + value = -AllCutNode(plyToSearch, depth + 1, -(beta - 1), true); + } + + moveMade = true; + + UnmakeMove(currentMove); + + if (!g_searchValid) { + return beta - 1; + } + + if (value > realEval) { + if (value >= beta) { + var histTo = (currentMove >> 8) & 0xFF; + if (g_board[histTo] == 0) { + var histPiece = g_board[currentMove & 0xFF] & 0xF; + historyTable[histPiece][histTo] += ply * ply; + if (historyTable[histPiece][histTo] > 32767) { + historyTable[histPiece][histTo] >>= 1; + } + + if (g_killers[depth][0] != currentMove) { + g_killers[depth][1] = g_killers[depth][0]; + g_killers[depth][0] = currentMove; + } + } + + StoreHash(value, hashflagBeta, ply, currentMove, depth); + return value; + } + + realEval = value; + hashMove = currentMove; + } + } + + if (!moveMade) { + // If we have no valid moves it's either stalemate or checkmate + if (g_inCheck) + // Checkmate. + return minEval + depth; + else + // Stalemate + return 0; + } + + StoreHash(realEval, hashflagAlpha, ply, hashMove, depth); + + return realEval; +} + +function AlphaBeta(ply, depth, alpha, beta) { + if (ply <= 0) { + return QSearch(alpha, beta, 0); + } + + g_nodeCount++; + + if (depth > 0 && IsRepDraw()) + return 0; + + // Mate distance pruning + var oldAlpha = alpha; + alpha = alpha < minEval + depth ? alpha : minEval + depth; + beta = beta > maxEval - (depth + 1) ? beta : maxEval - (depth + 1); + if (alpha >= beta) + return alpha; + + var hashMove = null; + var hashFlag = hashflagAlpha; + var hashNode = g_hashTable[g_hashKeyLow & g_hashMask]; + if (hashNode != null && hashNode.lock == g_hashKeyHigh) { + hashMove = hashNode.bestMove; + } + + var inCheck = g_inCheck; + + var moveMade = false; + var realEval = minEval; + + var movePicker = new MovePicker(hashMove, depth, g_killers[depth][0], g_killers[depth][1]); + + for (;;) { + var currentMove = movePicker.nextMove(); + if (currentMove == 0) { + break; + } + + var plyToSearch = ply - 1; + + if (!MakeMove(currentMove)) { + continue; + } + + if (g_inCheck) { + // Check extensions + plyToSearch++; + } + + var value; + if (moveMade) { + value = -AllCutNode(plyToSearch, depth + 1, -alpha, true); + if (value > alpha) { + value = -AlphaBeta(plyToSearch, depth + 1, -beta, -alpha); + } + } else { + value = -AlphaBeta(plyToSearch, depth + 1, -beta, -alpha); + } + + moveMade = true; + + UnmakeMove(currentMove); + + if (!g_searchValid) { + return alpha; + } + + if (value > realEval) { + if (value >= beta) { + var histTo = (currentMove >> 8) & 0xFF; + if (g_board[histTo] == 0) { + var histPiece = g_board[currentMove & 0xFF] & 0xF; + historyTable[histPiece][histTo] += ply * ply; + if (historyTable[histPiece][histTo] > 32767) { + historyTable[histPiece][histTo] >>= 1; + } + + if (g_killers[depth][0] != currentMove) { + g_killers[depth][1] = g_killers[depth][0]; + g_killers[depth][0] = currentMove; + } + } + + StoreHash(value, hashflagBeta, ply, currentMove, depth); + return value; + } + + if (value > oldAlpha) { + hashFlag = hashflagExact; + alpha = value; + } + + realEval = value; + hashMove = currentMove; + } + } + + if (!moveMade) { + // If we have no valid moves it's either stalemate or checkmate + if (inCheck) + // Checkmate. + return minEval + depth; + else + // Stalemate + return 0; + } + + StoreHash(realEval, hashFlag, ply, hashMove, depth); + + return realEval; +} + +// +// Board code +// + +// This somewhat funky scheme means that a piece is indexed by it's lower 4 bits when accessing in arrays. The fifth bit (black bit) +// is used to allow quick edge testing on the board. +var colorBlack = 0x10; +var colorWhite = 0x08; + +var pieceEmpty = 0x00; +var piecePawn = 0x01; +var pieceKnight = 0x02; +var pieceBishop = 0x03; +var pieceRook = 0x04; +var pieceQueen = 0x05; +var pieceKing = 0x06; + +var g_vectorDelta = new Array(256); + +var g_bishopDeltas = [-15, -17, 15, 17]; +var g_knightDeltas = [31, 33, 14, -14, -31, -33, 18, -18]; +var g_rookDeltas = [-1, +1, -16, +16]; +var g_queenDeltas = [-1, +1, -15, +15, -17, +17, -16, +16]; + +var g_castleRightsMask = [ +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +0, 0, 0, 0, 7,15,15,15, 3,15,15,11, 0, 0, 0, 0, +0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, +0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, +0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, +0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, +0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, +0, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0, +0, 0, 0, 0,13,15,15,15,12,15,15,14, 0, 0, 0, 0, +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; + +var moveflagEPC = 0x2 << 16; +var moveflagCastleKing = 0x4 << 16; +var moveflagCastleQueen = 0x8 << 16; +var moveflagPromotion = 0x10 << 16; +var moveflagPromoteRook = 0x00 << 16; +var moveflagPromoteKnight = 0x20 << 16; +var moveflagPromoteQueen = 0x40 << 16; +var moveflagPromoteBishop = 0x80 << 16; + +function MT() { + var N = 624; + var M = 397; + var MAG01 = [0x0, 0x9908b0df]; + + this.mt = new Array(N); + this.mti = N + 1; + + this.setSeed = function() + { + var a = arguments; + switch (a.length) { + case 1: + if (a[0].constructor === Number) { + this.mt[0]= a[0]; + for (var i = 1; i < N; ++i) { + var s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30); + this.mt[i] = ((1812433253 * ((s & 0xffff0000) >>> 16)) + << 16) + + 1812433253 * (s & 0x0000ffff) + + i; + } + this.mti = N; + return; + } + + this.setSeed(19650218); + + var l = a[0].length; + var i = 1; + var j = 0; + + for (var k = N > l ? N : l; k != 0; --k) { + var s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30) + this.mt[i] = (this.mt[i] + ^ (((1664525 * ((s & 0xffff0000) >>> 16)) << 16) + + 1664525 * (s & 0x0000ffff))) + + a[0][j] + + j; + if (++i >= N) { + this.mt[0] = this.mt[N - 1]; + i = 1; + } + if (++j >= l) { + j = 0; + } + } + + for (var k = N - 1; k != 0; --k) { + var s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30); + this.mt[i] = (this.mt[i] + ^ (((1566083941 * ((s & 0xffff0000) >>> 16)) << 16) + + 1566083941 * (s & 0x0000ffff))) + - i; + if (++i >= N) { + this.mt[0] = this.mt[N-1]; + i = 1; + } + } + + this.mt[0] = 0x80000000; + return; + default: + var seeds = new Array(); + for (var i = 0; i < a.length; ++i) { + seeds.push(a[i]); + } + this.setSeed(seeds); + return; + } + } + + this.setSeed(0x1BADF00D); + + this.next = function (bits) + { + if (this.mti >= N) { + var x = 0; + + for (var k = 0; k < N - M; ++k) { + x = (this.mt[k] & 0x80000000) | (this.mt[k + 1] & 0x7fffffff); + this.mt[k] = this.mt[k + M] ^ (x >>> 1) ^ MAG01[x & 0x1]; + } + for (var k = N - M; k < N - 1; ++k) { + x = (this.mt[k] & 0x80000000) | (this.mt[k + 1] & 0x7fffffff); + this.mt[k] = this.mt[k + (M - N)] ^ (x >>> 1) ^ MAG01[x & 0x1]; + } + x = (this.mt[N - 1] & 0x80000000) | (this.mt[0] & 0x7fffffff); + this.mt[N - 1] = this.mt[M - 1] ^ (x >>> 1) ^ MAG01[x & 0x1]; + + this.mti = 0; + } + + var y = this.mt[this.mti++]; + y ^= y >>> 11; + y ^= (y << 7) & 0x9d2c5680; + y ^= (y << 15) & 0xefc60000; + y ^= y >>> 18; + return (y >>> (32 - bits)) & 0xFFFFFFFF; + } +} + +// Position variables +var g_board = new Array(256); // Sentinel 0x80, pieces are in low 4 bits, 0x8 for color, 0x7 bits for piece type +var g_toMove; // side to move, 0 or 8, 0 = black, 8 = white +var g_castleRights; // bitmask representing castling rights, 1 = wk, 2 = wq, 4 = bk, 8 = bq +var g_enPassentSquare; +var g_baseEval; +var g_hashKeyLow, g_hashKeyHigh; +var g_inCheck; + +// Utility variables +var g_moveCount = 0; +var g_moveUndoStack = new Array(); + +var g_move50 = 0; +var g_repMoveStack = new Array(); + +var g_hashSize = 1 << 22; +var g_hashMask = g_hashSize - 1; +var g_hashTable; + +var g_killers; +var historyTable = new Array(32); + +var g_zobristLow; +var g_zobristHigh; +var g_zobristBlackLow; +var g_zobristBlackHigh; + +// Evaulation variables +var g_mobUnit; + +var hashflagAlpha = 1; +var hashflagBeta = 2; +var hashflagExact = 3; + +function HashEntry(lock, value, flags, hashDepth, bestMove, globalPly) { + this.lock = lock; + this.value = value; + this.flags = flags; + this.hashDepth = hashDepth; + this.bestMove = bestMove; +} + +function MakeSquare(row, column) { + return ((row + 2) << 4) | (column + 4); +} + +function MakeTable(table) { + var result = new Array(256); + for (var i = 0; i < 256; i++) { + result[i] = 0; + } + for (var row = 0; row < 8; row++) { + for (var col = 0; col < 8; col++) { + result[MakeSquare(row, col)] = table[row * 8 + col]; + } + } + return result; +} + +function ResetGame(fen) { + g_killers = new Array(128); + for (var i = 0; i < 128; i++) { + g_killers[i] = [0, 0]; + } + + g_hashTable = new Array(g_hashSize); + + for (var i = 0; i < 32; i++) { + historyTable[i] = new Array(256); + for (var j = 0; j < 256; j++) + historyTable[i][j] = 0; + } + + var mt = new MT(0x1badf00d); + + g_zobristLow = new Array(256); + g_zobristHigh = new Array(256); + for (var i = 0; i < 256; i++) { + g_zobristLow[i] = new Array(16); + g_zobristHigh[i] = new Array(16); + for (var j = 0; j < 16; j++) { + g_zobristLow[i][j] = mt.next(32); + g_zobristHigh[i][j] = mt.next(32); + } + } + g_zobristBlackLow = mt.next(32); + g_zobristBlackHigh = mt.next(32); + + for (var row = 0; row < 8; row++) { + for (var col = 0; col < 8; col++) { + var square = MakeSquare(row, col); + flipTable[square] = MakeSquare(7 - row, col); + } + } + + pieceSquareAdj[piecePawn] = MakeTable(pawnAdj); + pieceSquareAdj[pieceKnight] = MakeTable(knightAdj); + pieceSquareAdj[pieceBishop] = MakeTable(bishopAdj); + pieceSquareAdj[pieceRook] = MakeTable(rookAdj); + pieceSquareAdj[pieceQueen] = MakeTable(emptyAdj); + pieceSquareAdj[pieceKing] = MakeTable(kingAdj); + + var pieceDeltas = [[], [], g_knightDeltas, g_bishopDeltas, g_rookDeltas, g_queenDeltas, g_queenDeltas]; + + for (var i = 0; i < 256; i++) { + g_vectorDelta[i] = new Object(); + g_vectorDelta[i].delta = 0; + g_vectorDelta[i].pieceMask = new Array(2); + g_vectorDelta[i].pieceMask[0] = 0; + g_vectorDelta[i].pieceMask[1] = 0; + } + + // Initialize the vector delta table + for (var row = 0; row < 0x80; row += 0x10) + for (var col = 0; col < 0x8; col++) { + var square = row | col; + + // Pawn moves + var index = square - (square - 17) + 128; + g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn); + index = square - (square - 15) + 128; + g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn); + + index = square - (square + 17) + 128; + g_vectorDelta[index].pieceMask[0] |= (1 << piecePawn); + index = square - (square + 15) + 128; + g_vectorDelta[index].pieceMask[0] |= (1 << piecePawn); + + for (var i = pieceKnight; i <= pieceKing; i++) { + for (var dir = 0; dir < pieceDeltas[i].length; dir++) { + var target = square + pieceDeltas[i][dir]; + while (!(target & 0x88)) { + index = square - target + 128; + + g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << i); + g_vectorDelta[index].pieceMask[0] |= (1 << i); + + var flip = -1; + if (square < target) + flip = 1; + + if ((square & 0xF0) == (target & 0xF0)) { + // On the same row + g_vectorDelta[index].delta = flip * 1; + } else if ((square & 0x0F) == (target & 0x0F)) { + // On the same column + g_vectorDelta[index].delta = flip * 16; + } else if ((square % 15) == (target % 15)) { + g_vectorDelta[index].delta = flip * 15; + } else if ((square % 17) == (target % 17)) { + g_vectorDelta[index].delta = flip * 17; + } + + if (i == pieceKnight) { + g_vectorDelta[index].delta = pieceDeltas[i][dir]; + break; + } + + if (i == pieceKing) + break; + + target += pieceDeltas[i][dir]; + } + } + } + } + + InitializeEval(); + InitializeFromFen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"); +} + +function InitializeEval() { + g_mobUnit = new Array(2); + for (var i = 0; i < 2; i++) { + g_mobUnit[i] = new Array(); + var enemy = i == 0 ? 0x10 : 8; + var friend = i == 0 ? 8 : 0x10; + g_mobUnit[i][0] = 1; + g_mobUnit[i][0x80] = 0; + g_mobUnit[i][enemy | piecePawn] = 1; + g_mobUnit[i][enemy | pieceBishop] = 2; + g_mobUnit[i][enemy | pieceKnight] = 2; + g_mobUnit[i][enemy | pieceRook] = 4; + g_mobUnit[i][enemy | pieceQueen] = 6; + g_mobUnit[i][enemy | pieceKing] = 6; + g_mobUnit[i][friend | piecePawn] = 0; + g_mobUnit[i][friend | pieceBishop] = 0; + g_mobUnit[i][friend | pieceKnight] = 0; + g_mobUnit[i][friend | pieceRook] = 0; + g_mobUnit[i][friend | pieceQueen] = 0; + g_mobUnit[i][friend | pieceKing] = 0; + } +} + +function SetHash() { + var result = new Object(); + result.hashKeyLow = 0; + result.hashKeyHigh = 0; + + for (var i = 0; i < 256; i++) { + var piece = g_board[i]; + if (piece & 0x18) { + result.hashKeyLow ^= g_zobristLow[i][piece & 0xF] + result.hashKeyHigh ^= g_zobristHigh[i][piece & 0xF] + } + } + + if (!g_toMove) { + result.hashKeyLow ^= g_zobristBlackLow; + result.hashKeyHigh ^= g_zobristBlackHigh; + } + + return result; +} + +function InitializeFromFen(fen) { + var chunks = fen.split(' '); + + for (var i = 0; i < 256; i++) + g_board[i] = 0x80; + + var row = 0; + var col = 0; + + var pieces = chunks[0]; + for (var i = 0; i < pieces.length; i++) { + var c = pieces.charAt(i); + + if (c == '/') { + row++; + col = 0; + } + else { + if (c >= '0' && c <= '9') { + for (var j = 0; j < parseInt(c); j++) { + g_board[MakeSquare(row, col)] = 0; + col++; + } + } + else { + var isBlack = c >= 'a' && c <= 'z'; + var piece = isBlack ? colorBlack : colorWhite; + if (!isBlack) + c = pieces.toLowerCase().charAt(i); + switch (c) { + case 'p': + piece |= piecePawn; + break; + case 'b': + piece |= pieceBishop; + break; + case 'n': + piece |= pieceKnight; + break; + case 'r': + piece |= pieceRook; + break; + case 'q': + piece |= pieceQueen; + break; + case 'k': + piece |= pieceKing; + break; + } + + g_board[MakeSquare(row, col)] = piece; + col++; + } + } + } + + InitializePieceList(); + + g_toMove = chunks[1].charAt(0) == 'w' ? colorWhite : 0; + var them = 8 - g_toMove; + + g_castleRights = 0; + if (chunks[2].indexOf('K') != -1) { + if (g_board[MakeSquare(7, 4)] != (pieceKing | colorWhite) || + g_board[MakeSquare(7, 7)] != (pieceRook | colorWhite)) { + return 'Invalid FEN: White kingside castling not allowed'; + } + g_castleRights |= 1; + } + if (chunks[2].indexOf('Q') != -1) { + if (g_board[MakeSquare(7, 4)] != (pieceKing | colorWhite) || + g_board[MakeSquare(7, 0)] != (pieceRook | colorWhite)) { + return 'Invalid FEN: White queenside castling not allowed'; + } + g_castleRights |= 2; + } + if (chunks[2].indexOf('k') != -1) { + if (g_board[MakeSquare(0, 4)] != (pieceKing | colorBlack) || + g_board[MakeSquare(0, 7)] != (pieceRook | colorBlack)) { + return 'Invalid FEN: Black kingside castling not allowed'; + } + g_castleRights |= 4; + } + if (chunks[2].indexOf('q') != -1) { + if (g_board[MakeSquare(0, 4)] != (pieceKing | colorBlack) || + g_board[MakeSquare(0, 0)] != (pieceRook | colorBlack)) { + return 'Invalid FEN: Black queenside castling not allowed'; + } + g_castleRights |= 8; + } + + g_enPassentSquare = -1; + if (chunks[3].indexOf('-') == -1) { + var col = chunks[3].charAt(0).charCodeAt() - 'a'.charCodeAt(); + var row = 8 - (chunks[3].charAt(1).charCodeAt() - '0'.charCodeAt()); + g_enPassentSquare = MakeSquare(row, col); + } + + var hashResult = SetHash(); + g_hashKeyLow = hashResult.hashKeyLow; + g_hashKeyHigh = hashResult.hashKeyHigh; + + g_baseEval = 0; + for (var i = 0; i < 256; i++) { + if (g_board[i] & colorWhite) { + g_baseEval += pieceSquareAdj[g_board[i] & 0x7][i]; + g_baseEval += materialTable[g_board[i] & 0x7]; + } else if (g_board[i] & colorBlack) { + g_baseEval -= pieceSquareAdj[g_board[i] & 0x7][flipTable[i]]; + g_baseEval -= materialTable[g_board[i] & 0x7]; + } + } + if (!g_toMove) g_baseEval = -g_baseEval; + + g_move50 = 0; + g_inCheck = IsSquareAttackable(g_pieceList[(g_toMove | pieceKing) << 4], them); + + // Check for king capture (invalid FEN) + if (IsSquareAttackable(g_pieceList[(them | pieceKing) << 4], g_toMove)) { + return 'Invalid FEN: Can capture king'; + } + + // Checkmate/stalemate + if (GenerateValidMoves().length == 0) { + return g_inCheck ? 'Checkmate' : 'Stalemate'; + } + + return ''; +} + +var g_pieceIndex = new Array(256); +var g_pieceList = new Array(2 * 8 * 16); +var g_pieceCount = new Array(2 * 8); + +function InitializePieceList() { + for (var i = 0; i < 16; i++) { + g_pieceCount[i] = 0; + for (var j = 0; j < 16; j++) { + // 0 is used as the terminator for piece lists + g_pieceList[(i << 4) | j] = 0; + } + } + + for (var i = 0; i < 256; i++) { + g_pieceIndex[i] = 0; + if (g_board[i] & (colorWhite | colorBlack)) { + var piece = g_board[i] & 0xF; + + g_pieceList[(piece << 4) | g_pieceCount[piece]] = i; + g_pieceIndex[i] = g_pieceCount[piece]; + g_pieceCount[piece]++; + } + } +} + +function MakeMove(move){ + // move format: + // --flags-- ---to---- --from--- + // 0000 0000 0000 0000 0000 0000 + + // g_board is a 256x256 array + // representing the chess board + // right in the middle of it + + // moveflagEPC = 0000 0010 0000 0000 0000 0000 + // moveflagCastleKing = 0000 0100 0000 0000 0000 0000 + // moveflagCastleQueen = 0000 1000 0000 0000 0000 0000 + + // moveflagPromotion = 0001 0000 0000 0000 0000 0000 + // moveflagPromoteRook = 0000 0000 0000 0000 0000 0000 + // moveflagPromoteKnight = 0010 0000 0000 0000 0000 0000 + // moveflagPromoteQueen = 0100 0000 0000 0000 0000 0000 + // moveflagPromoteBishop = 1000 0000 0000 0000 0000 0000 + + + var me = g_toMove >> 3; + var otherColor = 8 - g_toMove; + + var flags = move & 0xFF0000; + var to = (move >> 8) & 0xFF; + var from = move & 0xFF; + var captured = g_board[to]; + var piece = g_board[from]; + var epcEnd = to; + + if (flags & moveflagEPC) { + epcEnd = me ? (to + 0x10) : (to - 0x10); + captured = g_board[epcEnd]; + g_board[epcEnd] = pieceEmpty; + } + + g_moveUndoStack[g_moveCount] = new UndoHistory(g_enPassentSquare, g_castleRights, g_inCheck, g_baseEval, g_hashKeyLow, g_hashKeyHigh, g_move50, captured); + g_moveCount++; + + g_enPassentSquare = -1; + + if (flags) { + if (flags & moveflagCastleKing) { + if (IsSquareAttackable(from + 1, otherColor) || + IsSquareAttackable(from + 2, otherColor)) { + g_moveCount--; + return false; + } + + var rook = g_board[to + 1]; + + g_hashKeyLow ^= g_zobristLow[to + 1][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to + 1][rook & 0xF]; + g_hashKeyLow ^= g_zobristLow[to - 1][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to - 1][rook & 0xF]; + + g_board[to - 1] = rook; + g_board[to + 1] = pieceEmpty; + + g_baseEval -= pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to + 1] : (to + 1)]; + g_baseEval += pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to - 1] : (to - 1)]; + + var rookIndex = g_pieceIndex[to + 1]; + g_pieceIndex[to - 1] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to - 1; + } else if (flags & moveflagCastleQueen) { + if (IsSquareAttackable(from - 1, otherColor) || + IsSquareAttackable(from - 2, otherColor)) { + g_moveCount--; + return false; + } + + var rook = g_board[to - 2]; + + g_hashKeyLow ^= g_zobristLow[to -2][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to - 2][rook & 0xF]; + g_hashKeyLow ^= g_zobristLow[to + 1][rook & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to + 1][rook & 0xF]; + + g_board[to + 1] = rook; + g_board[to - 2] = pieceEmpty; + + g_baseEval -= pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to - 2] : (to - 2)]; + g_baseEval += pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to + 1] : (to + 1)]; + + var rookIndex = g_pieceIndex[to - 2]; + g_pieceIndex[to + 1] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to + 1; + } + } + + if (captured) { + // Remove our piece from the piece list + var capturedType = captured & 0xF; + g_pieceCount[capturedType]--; + var lastPieceSquare = g_pieceList[(capturedType << 4) | g_pieceCount[capturedType]]; + g_pieceIndex[lastPieceSquare] = g_pieceIndex[epcEnd]; + g_pieceList[(capturedType << 4) | g_pieceIndex[lastPieceSquare]] = lastPieceSquare; + g_pieceList[(capturedType << 4) | g_pieceCount[capturedType]] = 0; + + g_baseEval += materialTable[captured & 0x7]; + g_baseEval += pieceSquareAdj[captured & 0x7][me ? flipTable[epcEnd] : epcEnd]; + + g_hashKeyLow ^= g_zobristLow[epcEnd][capturedType]; + g_hashKeyHigh ^= g_zobristHigh[epcEnd][capturedType]; + g_move50 = 0; + } else if ((piece & 0x7) == piecePawn) { + var diff = to - from; + if (diff < 0) diff = -diff; + if (diff > 16) { + g_enPassentSquare = me ? (to + 0x10) : (to - 0x10); + } + g_move50 = 0; + } + + g_hashKeyLow ^= g_zobristLow[from][piece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[from][piece & 0xF]; + g_hashKeyLow ^= g_zobristLow[to][piece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to][piece & 0xF]; + g_hashKeyLow ^= g_zobristBlackLow; + g_hashKeyHigh ^= g_zobristBlackHigh; + + g_castleRights &= g_castleRightsMask[from] & g_castleRightsMask[to]; + + g_baseEval -= pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[from] : from]; + + // Move our piece in the piece list + g_pieceIndex[to] = g_pieceIndex[from]; + g_pieceList[((piece & 0xF) << 4) | g_pieceIndex[to]] = to; + + if (flags & moveflagPromotion) { + var newPiece = piece & (~0x7); + if (flags & moveflagPromoteKnight) + newPiece |= pieceKnight; + else if (flags & moveflagPromoteQueen) + newPiece |= pieceQueen; + else if (flags & moveflagPromoteBishop) + newPiece |= pieceBishop; + else + newPiece |= pieceRook; + + g_hashKeyLow ^= g_zobristLow[to][piece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to][piece & 0xF]; + g_board[to] = newPiece; + g_hashKeyLow ^= g_zobristLow[to][newPiece & 0xF]; + g_hashKeyHigh ^= g_zobristHigh[to][newPiece & 0xF]; + + g_baseEval += pieceSquareAdj[newPiece & 0x7][me == 0 ? flipTable[to] : to]; + g_baseEval -= materialTable[piecePawn]; + g_baseEval += materialTable[newPiece & 0x7]; + + var pawnType = piece & 0xF; + var promoteType = newPiece & 0xF; + + g_pieceCount[pawnType]--; + + var lastPawnSquare = g_pieceList[(pawnType << 4) | g_pieceCount[pawnType]]; + g_pieceIndex[lastPawnSquare] = g_pieceIndex[to]; + g_pieceList[(pawnType << 4) | g_pieceIndex[lastPawnSquare]] = lastPawnSquare; + g_pieceList[(pawnType << 4) | g_pieceCount[pawnType]] = 0; + g_pieceIndex[to] = g_pieceCount[promoteType]; + g_pieceList[(promoteType << 4) | g_pieceIndex[to]] = to; + g_pieceCount[promoteType]++; + } else { + g_board[to] = g_board[from]; + + g_baseEval += pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[to] : to]; + } + g_board[from] = pieceEmpty; + + g_toMove = otherColor; + g_baseEval = -g_baseEval; + + if ((piece & 0x7) == pieceKing || g_inCheck) { + if (IsSquareAttackable(g_pieceList[(pieceKing | (8 - g_toMove)) << 4], otherColor)) { + UnmakeMove(move); + return false; + } + } else { + var kingPos = g_pieceList[(pieceKing | (8 - g_toMove)) << 4]; + + if (ExposesCheck(from, kingPos)) { + UnmakeMove(move); + return false; + } + + if (epcEnd != to) { + if (ExposesCheck(epcEnd, kingPos)) { + UnmakeMove(move); + return false; + } + } + } + + g_inCheck = false; + + if (flags <= moveflagEPC) { + var theirKingPos = g_pieceList[(pieceKing | g_toMove) << 4]; + + // First check if the piece we moved can attack the enemy king + g_inCheck = IsSquareAttackableFrom(theirKingPos, to); + + if (!g_inCheck) { + // Now check if the square we moved from exposes check on the enemy king + g_inCheck = ExposesCheck(from, theirKingPos); + + if (!g_inCheck) { + // Finally, ep. capture can cause another square to be exposed + if (epcEnd != to) { + g_inCheck = ExposesCheck(epcEnd, theirKingPos); + } + } + } + } + else { + // Castle or promotion, slow check + g_inCheck = IsSquareAttackable(g_pieceList[(pieceKing | g_toMove) << 4], 8 - g_toMove); + } + + g_repMoveStack[g_moveCount - 1] = g_hashKeyLow; + g_move50++; + + return true; +} + +function UnmakeMove(move){ + + g_toMove = 8 - g_toMove; + g_baseEval = -g_baseEval; + + g_moveCount--; + g_enPassentSquare = g_moveUndoStack[g_moveCount].ep; + g_castleRights = g_moveUndoStack[g_moveCount].castleRights; + g_inCheck = g_moveUndoStack[g_moveCount].inCheck; + g_baseEval = g_moveUndoStack[g_moveCount].baseEval; + g_hashKeyLow = g_moveUndoStack[g_moveCount].hashKeyLow; + g_hashKeyHigh = g_moveUndoStack[g_moveCount].hashKeyHigh; + g_move50 = g_moveUndoStack[g_moveCount].move50; + + var otherColor = 8 - g_toMove; + var me = g_toMove >> 3; + var them = otherColor >> 3; + + var flags = move & 0xFF0000; + var captured = g_moveUndoStack[g_moveCount].captured; + var to = (move >> 8) & 0xFF; + var from = move & 0xFF; + + var piece = g_board[to]; + + if (flags) { + if (flags & moveflagCastleKing) { + var rook = g_board[to - 1]; + g_board[to + 1] = rook; + g_board[to - 1] = pieceEmpty; + + var rookIndex = g_pieceIndex[to - 1]; + g_pieceIndex[to + 1] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to + 1; + } + else if (flags & moveflagCastleQueen) { + var rook = g_board[to + 1]; + g_board[to - 2] = rook; + g_board[to + 1] = pieceEmpty; + + var rookIndex = g_pieceIndex[to + 1]; + g_pieceIndex[to - 2] = rookIndex; + g_pieceList[((rook & 0xF) << 4) | rookIndex] = to - 2; + } + } + + if (flags & moveflagPromotion) { + piece = (g_board[to] & (~0x7)) | piecePawn; + g_board[from] = piece; + + var pawnType = g_board[from] & 0xF; + var promoteType = g_board[to] & 0xF; + + g_pieceCount[promoteType]--; + + var lastPromoteSquare = g_pieceList[(promoteType << 4) | g_pieceCount[promoteType]]; + g_pieceIndex[lastPromoteSquare] = g_pieceIndex[to]; + g_pieceList[(promoteType << 4) | g_pieceIndex[lastPromoteSquare]] = lastPromoteSquare; + g_pieceList[(promoteType << 4) | g_pieceCount[promoteType]] = 0; + g_pieceIndex[to] = g_pieceCount[pawnType]; + g_pieceList[(pawnType << 4) | g_pieceIndex[to]] = to; + g_pieceCount[pawnType]++; + } + else { + g_board[from] = g_board[to]; + } + + var epcEnd = to; + if (flags & moveflagEPC) { + if (g_toMove == colorWhite) + epcEnd = to + 0x10; + else + epcEnd = to - 0x10; + g_board[to] = pieceEmpty; + } + + g_board[epcEnd] = captured; + + // Move our piece in the piece list + g_pieceIndex[from] = g_pieceIndex[to]; + g_pieceList[((piece & 0xF) << 4) | g_pieceIndex[from]] = from; + + if (captured) { + // Restore our piece to the piece list + var captureType = captured & 0xF; + g_pieceIndex[epcEnd] = g_pieceCount[captureType]; + g_pieceList[(captureType << 4) | g_pieceCount[captureType]] = epcEnd; + g_pieceCount[captureType]++; + } +} + +function ExposesCheck(from, kingPos){ + var index = kingPos - from + 128; + // If a queen can't reach it, nobody can! + if ((g_vectorDelta[index].pieceMask[0] & (1 << (pieceQueen))) != 0) { + var delta = g_vectorDelta[index].delta; + var pos = kingPos + delta; + while (g_board[pos] == 0) pos += delta; + + var piece = g_board[pos]; + if (((piece & (g_board[kingPos] ^ 0x18)) & 0x18) == 0) + return false; + + // Now see if the piece can actually attack the king + var backwardIndex = pos - kingPos + 128; + return (g_vectorDelta[backwardIndex].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) != 0; + } + return false; +} + +function IsSquareOnPieceLine(target, from) { + var index = from - target + 128; + var piece = g_board[from]; + return (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) ? true : false; +} + +function IsSquareAttackableFrom(target, from){ + var index = from - target + 128; + var piece = g_board[from]; + if (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) { + // Yes, this square is pseudo-attackable. Now, check for real attack + var inc = g_vectorDelta[index].delta; + do { + from += inc; + if (from == target) + return true; + } while (g_board[from] == 0); + } + + return false; +} + +function IsSquareAttackable(target, color) { + // Attackable by pawns? + var inc = color ? -16 : 16; + var pawn = (color ? colorWhite : colorBlack) | 1; + if (g_board[target - (inc - 1)] == pawn) + return true; + if (g_board[target - (inc + 1)] == pawn) + return true; + + // Attackable by pieces? + for (var i = 2; i <= 6; i++) { + var index = (color | i) << 4; + var square = g_pieceList[index]; + while (square != 0) { + if (IsSquareAttackableFrom(target, square)) + return true; + square = g_pieceList[++index]; + } + } + return false; +} + +function GenerateMove(from, to) { + return from | (to << 8); +} + +function GenerateMove(from, to, flags){ + return from | (to << 8) | flags; +} + +function GenerateValidMoves() { + var moveList = new Array(); + var allMoves = new Array(); + GenerateCaptureMoves(allMoves, null); + GenerateAllMoves(allMoves); + + for (var i = allMoves.length - 1; i >= 0; i--) { + if (MakeMove(allMoves[i])) { + moveList[moveList.length] = allMoves[i]; + UnmakeMove(allMoves[i]); + } else { + } + } + + return moveList; +} + +function GenerateAllMoves(moveStack) { + var from, to, piece, pieceIdx; + + // Pawn quiet moves + pieceIdx = (g_toMove | 1) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + GeneratePawnMoves(moveStack, from); + from = g_pieceList[pieceIdx++]; + } + + // Knight quiet moves + pieceIdx = (g_toMove | 2) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from + 31; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 33; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 14; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 14; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 31; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 33; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 18; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 18; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Bishop quiet moves + pieceIdx = (g_toMove | 3) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from - 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 15; } + to = from - 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 17; } + to = from + 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 15; } + to = from + 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 17; } + from = g_pieceList[pieceIdx++]; + } + + // Rook quiet moves + pieceIdx = (g_toMove | 4) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from - 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to--; } + to = from + 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to++; } + to = from + 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 16; } + to = from - 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 16; } + from = g_pieceList[pieceIdx++]; + } + + // Queen quiet moves + pieceIdx = (g_toMove | 5) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from - 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 15; } + to = from - 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 17; } + to = from + 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 15; } + to = from + 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 17; } + to = from - 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to--; } + to = from + 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to++; } + to = from + 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 16; } + to = from - 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 16; } + from = g_pieceList[pieceIdx++]; + } + + // King quiet moves + { + pieceIdx = (g_toMove | 6) << 4; + from = g_pieceList[pieceIdx]; + to = from - 15; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 17; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 15; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 17; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 1; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 1; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 16; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 16; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to); + + if (!g_inCheck) { + var castleRights = g_castleRights; + if (!g_toMove) + castleRights >>= 2; + if (castleRights & 1) { + // Kingside castle + if (g_board[from + 1] == pieceEmpty && g_board[from + 2] == pieceEmpty) { + moveStack[moveStack.length] = GenerateMove(from, from + 0x02, moveflagCastleKing); + } + } + if (castleRights & 2) { + // Queenside castle + if (g_board[from - 1] == pieceEmpty && g_board[from - 2] == pieceEmpty && g_board[from - 3] == pieceEmpty) { + moveStack[moveStack.length] = GenerateMove(from, from - 0x02, moveflagCastleQueen); + } + } + } + } +} + +function GenerateCaptureMoves(moveStack, moveScores) { + var from, to, piece, pieceIdx; + var inc = (g_toMove == 8) ? -16 : 16; + var enemy = g_toMove == 8 ? 0x10 : 0x8; + + // Pawn captures + pieceIdx = (g_toMove | 1) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from + inc - 1; + if (g_board[to] & enemy) { + MovePawnTo(moveStack, from, to); + } + + to = from + inc + 1; + if (g_board[to] & enemy) { + MovePawnTo(moveStack, from, to); + } + + from = g_pieceList[pieceIdx++]; + } + + if (g_enPassentSquare != -1) { + var inc = (g_toMove == colorWhite) ? -16 : 16; + var pawn = g_toMove | piecePawn; + + var from = g_enPassentSquare - (inc + 1); + if ((g_board[from] & 0xF) == pawn) { + moveStack[moveStack.length] = GenerateMove(from, g_enPassentSquare, moveflagEPC); + } + + from = g_enPassentSquare - (inc - 1); + if ((g_board[from] & 0xF) == pawn) { + moveStack[moveStack.length] = GenerateMove(from, g_enPassentSquare, moveflagEPC); + } + } + + // Knight captures + pieceIdx = (g_toMove | 2) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from + 31; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 33; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 14; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 14; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 31; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 33; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 18; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 18; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Bishop captures + pieceIdx = (g_toMove | 3) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from; do { to -= 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to -= 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to += 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to += 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Rook captures + pieceIdx = (g_toMove | 4) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from; do { to--; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to++; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to -= 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to += 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // Queen captures + pieceIdx = (g_toMove | 5) << 4; + from = g_pieceList[pieceIdx++]; + while (from != 0) { + to = from; do { to -= 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to -= 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to += 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to += 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to--; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to++; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to -= 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from; do { to += 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + from = g_pieceList[pieceIdx++]; + } + + // King captures + { + pieceIdx = (g_toMove | 6) << 4; + from = g_pieceList[pieceIdx]; + to = from - 15; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 17; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 15; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 17; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 1; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 1; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from - 16; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + to = from + 16; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to); + } +} + +function MovePawnTo(moveStack, start, square) { + var row = square & 0xF0; + if ((row == 0x90) || (row == 0x20)) { + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteQueen); + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteKnight); + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteBishop); + moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion); + } + else { + moveStack[moveStack.length] = GenerateMove(start, square, 0); + } +} + +function GeneratePawnMoves(moveStack, from) { + var piece = g_board[from]; + var color = piece & colorWhite; + var inc = (color == colorWhite) ? -16 : 16; + + // Quiet pawn moves + var to = from + inc; + if (g_board[to] == 0) { + MovePawnTo(moveStack, from, to, pieceEmpty); + + // Check if we can do a 2 square jump + if ((((from & 0xF0) == 0x30) && color != colorWhite) || + (((from & 0xF0) == 0x80) && color == colorWhite)) { + to += inc; + if (g_board[to] == 0) { + moveStack[moveStack.length] = GenerateMove(from, to); + } + } + } +} + +function UndoHistory(ep, castleRights, inCheck, baseEval, hashKeyLow, hashKeyHigh, move50, captured) { + this.ep = ep; + this.castleRights = castleRights; + this.inCheck = inCheck; + this.baseEval = baseEval; + this.hashKeyLow = hashKeyLow; + this.hashKeyHigh = hashKeyHigh; + this.move50 = move50; + this.captured = captured; +} + +var g_seeValues = [0, 1, 3, 3, 5, 9, 900, 0, + 0, 1, 3, 3, 5, 9, 900, 0]; + +function See(move) { + var from = move & 0xFF; + var to = (move >> 8) & 0xFF; + + var fromPiece = g_board[from]; + + var fromValue = g_seeValues[fromPiece & 0xF]; + var toValue = g_seeValues[g_board[to] & 0xF]; + + if (fromValue <= toValue) { + return true; + } + + if (move >> 16) { + // Castles, promotion, ep are always good + return true; + } + + var us = (fromPiece & colorWhite) ? colorWhite : 0; + var them = 8 - us; + + // Pawn attacks + // If any opponent pawns can capture back, this capture is probably not worthwhile (as we must be using knight or above). + var inc = (fromPiece & colorWhite) ? -16 : 16; // Note: this is capture direction from to, so reversed from normal move direction + if (((g_board[to + inc + 1] & 0xF) == (piecePawn | them)) || + ((g_board[to + inc - 1] & 0xF) == (piecePawn | them))) { + return false; + } + + var themAttacks = new Array(); + + // Knight attacks + // If any opponent knights can capture back, and the deficit we have to make up is greater than the knights value, + // it's not worth it. We can capture on this square again, and the opponent doesn't have to capture back. + var captureDeficit = fromValue - toValue; + SeeAddKnightAttacks(to, them, themAttacks); + if (themAttacks.length != 0 && captureDeficit > g_seeValues[pieceKnight]) { + return false; + } + + // Slider attacks + g_board[from] = 0; + for (var pieceType = pieceBishop; pieceType <= pieceQueen; pieceType++) { + if (SeeAddSliderAttacks(to, them, themAttacks, pieceType)) { + if (captureDeficit > g_seeValues[pieceType]) { + g_board[from] = fromPiece; + return false; + } + } + } + + // Pawn defenses + // At this point, we are sure we are making a "losing" capture. The opponent can not capture back with a + // pawn. They cannot capture back with a minor/major and stand pat either. So, if we can capture with + // a pawn, it's got to be a winning or equal capture. + if (((g_board[to - inc + 1] & 0xF) == (piecePawn | us)) || + ((g_board[to - inc - 1] & 0xF) == (piecePawn | us))) { + g_board[from] = fromPiece; + return true; + } + + // King attacks + SeeAddSliderAttacks(to, them, themAttacks, pieceKing); + + // Our attacks + var usAttacks = new Array(); + SeeAddKnightAttacks(to, us, usAttacks); + for (var pieceType = pieceBishop; pieceType <= pieceKing; pieceType++) { + SeeAddSliderAttacks(to, us, usAttacks, pieceType); + } + + g_board[from] = fromPiece; + + // We are currently winning the amount of material of the captured piece, time to see if the opponent + // can get it back somehow. We assume the opponent can capture our current piece in this score, which + // simplifies the later code considerably. + var seeValue = toValue - fromValue; + + for (; ; ) { + var capturingPieceValue = 1000; + var capturingPieceIndex = -1; + + // Find the least valuable piece of the opponent that can attack the square + for (var i = 0; i < themAttacks.length; i++) { + if (themAttacks[i] != 0) { + var pieceValue = g_seeValues[g_board[themAttacks[i]] & 0x7]; + if (pieceValue < capturingPieceValue) { + capturingPieceValue = pieceValue; + capturingPieceIndex = i; + } + } + } + + if (capturingPieceIndex == -1) { + // Opponent can't capture back, we win + return true; + } + + // Now, if seeValue < 0, the opponent is winning. If even after we take their piece, + // we can't bring it back to 0, then we have lost this battle. + seeValue += capturingPieceValue; + if (seeValue < 0) { + return false; + } + + var capturingPieceSquare = themAttacks[capturingPieceIndex]; + themAttacks[capturingPieceIndex] = 0; + + // Add any x-ray attackers + SeeAddXrayAttack(to, capturingPieceSquare, us, usAttacks, themAttacks); + + // Our turn to capture + capturingPieceValue = 1000; + capturingPieceIndex = -1; + + // Find our least valuable piece that can attack the square + for (var i = 0; i < usAttacks.length; i++) { + if (usAttacks[i] != 0) { + var pieceValue = g_seeValues[g_board[usAttacks[i]] & 0x7]; + if (pieceValue < capturingPieceValue) { + capturingPieceValue = pieceValue; + capturingPieceIndex = i; + } + } + } + + if (capturingPieceIndex == -1) { + // We can't capture back, we lose :( + return false; + } + + // Assume our opponent can capture us back, and if we are still winning, we can stand-pat + // here, and assume we've won. + seeValue -= capturingPieceValue; + if (seeValue >= 0) { + return true; + } + + capturingPieceSquare = usAttacks[capturingPieceIndex]; + usAttacks[capturingPieceIndex] = 0; + + // Add any x-ray attackers + SeeAddXrayAttack(to, capturingPieceSquare, us, usAttacks, themAttacks); + } +} + +function SeeAddXrayAttack(target, square, us, usAttacks, themAttacks) { + var index = square - target + 128; + var delta = -g_vectorDelta[index].delta; + if (delta == 0) + return; + square += delta; + while (g_board[square] == 0) { + square += delta; + } + + if ((g_board[square] & 0x18) && IsSquareOnPieceLine(target, square)) { + if ((g_board[square] & 8) == us) { + usAttacks[usAttacks.length] = square; + } else { + themAttacks[themAttacks.length] = square; + } + } +} + +// target = attacking square, us = color of knights to look for, attacks = array to add squares to +function SeeAddKnightAttacks(target, us, attacks) { + var pieceIdx = (us | pieceKnight) << 4; + var attackerSq = g_pieceList[pieceIdx++]; + + while (attackerSq != 0) { + if (IsSquareOnPieceLine(target, attackerSq)) { + attacks[attacks.length] = attackerSq; + } + attackerSq = g_pieceList[pieceIdx++]; + } +} + +function SeeAddSliderAttacks(target, us, attacks, pieceType) { + var pieceIdx = (us | pieceType) << 4; + var attackerSq = g_pieceList[pieceIdx++]; + var hit = false; + + while (attackerSq != 0) { + if (IsSquareAttackableFrom(target, attackerSq)) { + attacks[attacks.length] = attackerSq; + hit = true; + } + attackerSq = g_pieceList[pieceIdx++]; + } + + return hit; +} + +function BuildPVMessage(bestMove, value, timeTaken, ply) { + var totalNodes = g_nodeCount + g_qNodeCount; + return "Ply:" + ply + " Score:" + value + " Nodes:" + totalNodes + " NPS:" + ((totalNodes / (timeTaken / 1000)) | 0) + " " + PVFromHash(bestMove, 15); +} + +////////////////////////////////////////////////// +// Test Harness +////////////////////////////////////////////////// +function FinishPlyCallback(bestMove, value, timeTaken, ply) { + postMessage("pv " + BuildPVMessage(bestMove, value, timeTaken, ply)); +} + +function FinishMoveLocalTesting(bestMove, value, timeTaken, ply) { + if (bestMove != null) { + MakeMove(bestMove); + postMessage(FormatMove(bestMove)); + } +} + +var needsReset = true; +self.onmessage = function (e) { + if (e.data == "go" || needsReset) { + ResetGame(); + needsReset = false; + if (e.data == "go") return; + } + if (e.data.match("^position") == "position") { + ResetGame(); + var result = InitializeFromFen(e.data.substr(9, e.data.length - 9)); + if (result.length != 0) { + postMessage("message " + result); + } + } else if (e.data.match("^search") == "search") { + g_timeout = parseInt(e.data.substr(7, e.data.length - 7), 10); + Search(FinishMoveLocalTesting, 99, FinishPlyCallback); + } else if (e.data == "analyze") { + g_timeout = 99999999999; + Search(null, 99, FinishPlyCallback); + } else { + MakeMove(GetMoveFromString(e.data)); + } +} diff --git a/js/Cell.js b/js/Cell.js new file mode 100644 index 0000000..cb734dd --- /dev/null +++ b/js/Cell.js @@ -0,0 +1,116 @@ +// ECMAScript 5 strict mode +/* jshint globalstrict: true*/ +/* global THREE,BOARD_SIZE, COLS,ROWS*/ +"use strict"; +(function () { + var a = "a".charCodeAt(0); + function Cell() { + this.position = null; + this.index = null; + this.x = null; + this.y = null; + var coordinates = null; + if( arguments.length === 1) { + + if (typeof(arguments[0]) === "string" && arguments[0].match(/[a-h][1-8]/) ) { + // position like "a1", "b4", "e7" + this.position = arguments[0]; + coordinates = getCoordinatesFromPosition( + this.position + ); + this.x = coordinates.x; + this.y = coordinates.y; + this.index = this.x + this.y * COLS; + } else if (arguments[0] >= 0 && arguments[0] < ROWS*COLS) { + // array index + this.index = arguments[0]; + coordinates = getCoordinatesFromIndex( + this.index + ); + this.x = coordinates.x; + this.y = coordinates.y; + this.position = getPositionFromCoordinates( + this.x,this.y + ); + } + } else if( arguments.length === 2 && + isValid(arguments[0],arguments[1]) ) { + // x and y position (0-based + this.x = arguments[0]; + this.y = arguments[1]; + this.index = this.x + this.y * COLS; + this.position = getPositionFromCoordinates( + this.x,this.y + ); + } else { + throw arguments[0]; + } + } + + Cell.prototype.toString = function() { + return this.position; + }; + + Cell.prototype.equals = function () { + if(arguments.length === 1) { + var cell = arguments[0]; + if(cell instanceof Cell) { + // it's a Cell object + return cell.position === this.position; + } else { + // it's a string position + return cell === this.position; + } + } else if (arguments.length === 2) { + // it's x,y coordinates + return this.x === arguments[0] && + this.y === arguments[1]; + } + + }; + + Cell.prototype.getWorldPosition = function() { + var cs = BOARD_SIZE / ROWS; + var middle = (BOARD_SIZE-cs)/2; + + + return new THREE.Vector3( + this.x * cs - middle, + 0, + (this.y * cs - middle) + ); + }; + + // private + function getPositionFromCoordinates(x,y) { + return String.fromCharCode(x+a)+(7-y+1); + } + + function getCoordinatesFromPosition(position) { + return { + x: position.charCodeAt(0) - a, + y: 7-(parseInt(position.charAt(1),10)-1) + }; + } + + function getCoordinatesFromIndex(index) { + return { + x: index%COLS, + y: Math.floor(index/COLS) // have to flip y since 3D starts from bottom left + }; + } + + function isValid() { + if( arguments.length == 2) { + var x = arguments[0]; + var y = arguments[1]; + + return x >= 0 && x < COLS && + y >= 0 && y < ROWS; + } + return false; + } + + window.Cell = Cell; + +})(); diff --git a/js/chess.js b/js/chess.js new file mode 100644 index 0000000..be0e11e --- /dev/null +++ b/js/chess.js @@ -0,0 +1,596 @@ +// ECMAScript 5 strict mode +/* jshint globalstrict: true*/ +/* jslint newcap: true */ +/* global THREE, $, document, window, console */ +/* global LOADING_BAR_SCALE,ROWS,COLS,PIECE_SIZE, BOARD_SIZE, FLOOR_SIZE, WIREFRAME, DEBUG, Cell, WHITE, BLACK, FEEDBACK, SHADOW */ +/* global textures, geometries, removeLoader */ +/* global initGUI, initInfo, addToPGN, displayCheck, newGame */ +/* global initPieceFactory,initCellFactory,createCell,createPiece,createChessBoard, createFloor, createValidCellMaterial,createSelectedMaterial, validCellMaterial, selectedMaterial */ + /*global Search,FormatSquare,GenerateMove,MakeMove,GetMoveSAN,MakeSquare,UnmakeMove, FormatMove, ResetGame, GetFen, GetMoveFromString, alert, InitializeFromFen, GenerateValidMoves */ + /*global g_inCheck,g_board,g_pieceList, g_toMove, g_timeout:true,g_maxply:true */ + /*global moveflagCastleKing, moveflagCastleQueen, moveflagEPC, moveflagPromotion, colorWhite*/ + /*global moveflagPromoteQueen,moveflagPromoteRook,moveflagPromoteBishop,moveflagPromoteKnight*/ + /*global piecePawn, pieceKnight, pieceBishop, pieceRook, pieceQueen, pieceKing */ + +"use strict"; + + + +var camera; +// list of valid move after each move +// used mostly for cell highlighting +var validMoves = null; +// chess game variables +var g_allMoves = []; +// default promotion +var promotion = moveflagPromoteQueen; + +var g_playerWhite = false; +var g_backgroundEngine; + +// settings for AI level +var levels = [ + {timeout:0,maxply:1}, + {timeout:12,maxply:20}, + {timeout:25,maxply:40}, + {timeout:50,maxply:60}, + {timeout:100,maxply:80}, + {timeout:200,maxply:100}, + {timeout:400,maxply:120}, + {timeout:800,maxply:140}, + {timeout:1600,maxply:160}, + {timeout:3200,maxply:180} +]; + + +(function() { + // general setup + var scene, renderer; + var cameraControls, effectController; + // for picking + var projector; + // 3D board representation + var chessBoard; + // for proper timing + var clock = new THREE.Clock(); + + var g_backgroundEngineValid = true; + + // array for picking + var board3D = []; + + + // hold current selection + var selectedPiece = null; + var selectedCell = null; + + // default values for AI level + g_timeout = 1600; + g_maxply = 49; + + + /* + * BASIC SETUP + */ + function init() { + // initialize everything for 3D + + // CANVAS PARAMETERS + var canvasWidth = window.innerWidth; + var canvasHeight = window.innerHeight; + var canvasRatio = canvasWidth / canvasHeight; + + // RENDERER + renderer = new THREE.WebGLRenderer( { antialias: true } ); + renderer.gammaInput = true; + renderer.gammaOutput = true; + renderer.setSize(canvasWidth, canvasHeight); + + if ( SHADOW ) { + renderer.shadowMapEnabled = true; + renderer.shadowMapType = THREE.PCFSoftShadowMap; + renderer.shadowMapCascade = true; + } + + // black background + renderer.setClearColor( 0x000000, 1.0 ); + document.body.appendChild( renderer.domElement ); + + // CAMERA + camera = new THREE.PerspectiveCamera( 45, canvasRatio, 1, 40000 ); + // CONTROLS + cameraControls = new THREE.OrbitAndPanControls(camera, renderer.domElement); + // limitations + cameraControls.minPolarAngle = 0; + cameraControls.maxPolarAngle = 80 * Math.PI/180; + cameraControls.minDistance = 10; + cameraControls.maxDistance = 200; + cameraControls.userZoomSpeed = 1.0; + // default position behind white + // (might want to change that according to color selection) + camera.position.set( 0, 100, 100 ); + + + // LIGHTING + var spotlight = new THREE.SpotLight( 0xFFFFFF, 1.0); + spotlight.position.set( 0, 300, 0 ); + spotlight.angle = Math.PI / 2; + spotlight.exponent = 50.0; + spotlight.target.position.set( 0, 0, 0 ); + + if ( SHADOW ) { + spotlight.castShadow = true; + spotlight.shadowDarkness = 0.5; + //spotlight.shadowMapWidth = 4096; // yeah crazy testing + //spotlight.shadowMapHeight = 4096; + spotlight.shadowBias = -0.001; + } + + + var whiteLight = new THREE.PointLight( 0xFFEEDD, 0.2); + whiteLight.position.set(0,0,100); + var blackLight = new THREE.PointLight( 0xFFEEDD, 0.2); + blackLight.position.set(0,0,-100); + + // generate createPiece and createCell functions + initPieceFactory(); + initCellFactory(); + + // we let chessBoard in global scope to use it for picking + chessBoard = createChessBoard(BOARD_SIZE); + var floor = createFloor(FLOOR_SIZE,BOARD_SIZE); + + //floor.position.y = -5*BOARD_SIZE/100; + floor.position.y = chessBoard.height; + + // create and fill the scene with default stuff + scene = new THREE.Scene(); + scene.add(floor); + scene.add(spotlight); + scene.add(whiteLight); + scene.add(blackLight); + scene.add(chessBoard); + + // to make everything black in the background + scene.fog = new THREE.FogExp2( 0x000000, 0.001 ); + // little reddish to fake a bit of bounce lighting + scene.add(new THREE.AmbientLight(0x330000)); + + // for picking + projector = new THREE.Projector(); + + // Menu + initGUI(); + // Check feedback + initInfo(); + + createValidCellMaterial(); + createSelectedMaterial(); + + // picking event + document.addEventListener( 'mousedown', onDocumentMouseDown, false ); + document.addEventListener( 'mousemove', onDocumentMouseMove, false ); + + // avoid stretching + window.addEventListener('resize',onResize,false); + } + + function onResize() { + var canvas = renderer.domElement; + var w = window.innerWidth; + var h = window.innerHeight; + renderer.setSize(w,h); + // have to change the projection + // else the image will be stretched + camera.aspect = w/h; + camera.updateProjectionMatrix(); + } + + function animate() { + window.requestAnimationFrame(animate); + render(); + } + + function render() { + var delta = clock.getDelta(); + cameraControls.update(delta); + renderer.render(scene, camera); + } + + + function UIPlayMove(move,silent) { + // we play the move here by + // adding it to the png list (for display) + addToPGN(move); + // and to the move list (for undos) + g_allMoves[g_allMoves.length] = move; + // committing the move + MakeMove(move); + // redrawing + // silent flag is used when simulating moves for loading PGN + if(!silent) { + redrawBoard(); + } + } + + function playMove(piece,cell) { + + if (piece.cell === undefined || cell.name === undefined) { + return false; + } + // get the positions + var start = new Cell(piece.cell); + var end = new Cell(cell.name); + + var startSquare = MakeSquare(start.y, start.x); + var endSquare = MakeSquare(end.y, end.x); + + var move = null; + var testPromotion = false; + var p = g_board[startSquare]; + + if ( ((p & 0x7) === piecePawn) && + (((start.y === 1) && g_playerWhite) || + ( (start.y === 6) && !g_playerWhite)) && + (((p & 0x8) && g_playerWhite) || + (!(p & 0x8) && !g_playerWhite)) + ) { + testPromotion = true; + } + + // check if the move is valid + // validMoves is global and reevaluated after each move + for (var i = 0; i < validMoves.length; i++) { + if (testPromotion) { + // for promotion we one valid move per promotion type + // so we have to be more specific and create the entire move + // with its flag go get it back from validMoves. + // else it's alway a Rook promotion (flag 0x00). + if(validMoves[i] === GenerateMove(startSquare, endSquare, moveflagPromotion | promotion)) { + move = validMoves[i]; + break; + } + } else { + // just checking start and end square allows to cover + // all other special moves like "en passant" capture and + // castling + if ( (validMoves[i] & 0xFF) == startSquare && + ((validMoves[i] >> 8) & 0xFF) == endSquare ) { + move = validMoves[i]; + break; + } + } + } + + + if (!(start.x === end.x && start.y === end.y) && move !== null) { + + // we send the move to our worker + if (InitializeBackgroundEngine()) { + g_backgroundEngine.postMessage(FormatMove(move)); + } + + // we play the actual move + UIPlayMove(move,false); + + + // make the engine play (setTimeOut is used probably to wait for the last postMessage to kick in) + // maybe creating a callback from the worker would be better (more reliable) + setTimeout(SearchAndRedraw, 0); + return true; + } + return false; + } + + + /* + * AI CONTROL + */ + function EnsureAnalysisStopped() { + if (g_backgroundEngine) { + g_backgroundEngine.terminate(); + g_backgroundEngine = null; + } + } + + function SearchAndRedraw() { + // the AI is triggered here + if (InitializeBackgroundEngine()) { + g_backgroundEngine.postMessage("search " + g_timeout + "," + g_maxply); + } else { + Search(FinishMove, g_maxply, null); // unasynchronous version fall back + } + } + + function FinishMove(bestMove, value, timeTaken, ply) { + // used by the fallback Search + if (bestMove !== null) { + UIPlayMove(bestMove,false); + } + } + + function InitializeBackgroundEngine() { + // we initialize the web worker here + if (!g_backgroundEngineValid) { + return false; + } + if (!g_backgroundEngine) { + g_backgroundEngineValid = true; + try { + g_backgroundEngine = new Worker("js/AI/garbochess.js"); + g_backgroundEngine.onmessage = function (e) { + if (e.data.match("^pv") == "pv") { + // legacy + } else if (e.data.match("^message") == "message") { + // legacy + EnsureAnalysisStopped(); + } else if (e.data.match("^console: ") == "console: ") { + // debugging + console.log(e.data.substr(9)); + } else { + // we receive the move from the AI, we play it + UIPlayMove(GetMoveFromString(e.data), false); + } + }; + g_backgroundEngine.error = function (e) { + alert("Error from background worker:" + e.message); + }; + // set up the current board position + g_backgroundEngine.postMessage("position " + GetFen()); + } catch (error) { + g_backgroundEngineValid = false; + } + } + // return false for fallback + return g_backgroundEngineValid; + } + + + /* + * BOARD + */ + + + function updateBoard3D() { + // list all the pieces + board3D = []; + for (var y = 0; y < ROWS; y++) { + for (var x = 0; x < COLS; x++) { + var piece = g_board[MakeSquare(y,x)]; + var pieceColor = (piece & colorWhite) ? WHITE : BLACK; + var pieceName = null; + switch (piece & 0x7) { + case piecePawn: + pieceName = "pawn"; + break; + case pieceKnight: + pieceName = "knight"; + break; + case pieceBishop: + pieceName = "bishop"; + break; + case pieceRook: + pieceName = "rook"; + break; + case pieceQueen: + pieceName = "queen"; + break; + case pieceKing: + pieceName = "king"; + break; + } + + if (pieceName !== null) { + board3D[x+y*COLS] = createPiece(pieceName,pieceColor); + } + } + } + } + + function clearBoard() { + // remove all pieces from the board + var cell; + board3D.forEach(function(piece) { + scene.remove(piece); + cell = new Cell(piece.cell); + }); + } + + function fillBoard() { + // place all the pieces on the board + var cell; + board3D.forEach(function(piece,index) { + cell = new Cell(index); + piece.position = cell.getWorldPosition(); + piece.cell = index; + scene.add(piece); + }); + } + + + + function redrawBoard() { + validMoves = GenerateValidMoves(); + clearBoard(); + updateBoard3D(); + fillBoard(); + displayCheck(); + } + + + /* + * PICKING + */ + function pickPiece(raycaster) { + var intersect = null; + var picked = null; + // intersect piece + var hitList = []; + var hit,piece; + for (var i in board3D) { + if ({}.hasOwnProperty.call(board3D, i)) { + piece = board3D[i]; + intersect = raycaster.intersectObject( piece.children[0], true ); + + if (intersect.length > 0) { + hit = intersect[0]; + if (( g_playerWhite && hit.object.parent.color === WHITE ) || + (!g_playerWhite && hit.object.parent.color === BLACK ) ){ + + // only pick the right color + hitList.push(hit); + } + } + } + } + + // find the closest + hitList.forEach(function(hit) { + if (picked === null || picked.distance > hit.distance) { + picked = hit; + } + }); + + + if (picked) { + return picked.object.parent; + } else { + return null; + } + + } + + function pickCell(raycaster) { + // here we don't need to test the distance since you can't really + // intersect more than one cell at a time. + var intersect = raycaster.intersectObject( chessBoard, true ); + if (intersect.length > 0) { + var pickedCell = intersect[0].object; + return pickedCell; + } + return null; + } + + function getRay(event) { + // get the raycaster object from the mouse position + var zoomLevel = window.devicePixelRatio | 1.0 ; + var canvas = renderer.domElement; + var canvasPosition = canvas.getBoundingClientRect(); + var mouseX = event.clientX*zoomLevel - canvasPosition.left; + var mouseY = event.clientY*zoomLevel - canvasPosition.top; + + var mouseVector = new THREE.Vector3( + 2 * ( mouseX / canvas.width ) - 1, + 1 - 2 * ( mouseY / canvas.height )); + + return projector.pickingRay( mouseVector.clone(), camera ); + } + + function onDocumentMouseMove( event ) { + + var canvas = renderer.domElement; + var raycaster = getRay(event); + var pickedPiece = pickPiece(raycaster); + var pickedCell = pickCell(raycaster); + + + canvas.style.cursor = "default"; + // we are over one of our piece -> hand + if (pickedPiece !== null) { + canvas.style.cursor = "pointer"; + } + + // if a cell is selected, we unselect it by default + if (selectedCell !== null) { + selectedCell.material = selectedCell.baseMaterial; + } + + // if a piece is selected and a cell is picked + if(selectedPiece !== null && pickedCell !== null) { + var start = new Cell(selectedPiece.cell); + var end = new Cell(pickedCell.name); + + var move = null; + // we check if it would be a valid move + for (var i = 0; i < validMoves.length; i++) { + if ( (validMoves[i] & 0xFF) == MakeSquare(start.y, start.x) && + ((validMoves[i] >> 8) & 0xFF) == MakeSquare(end.y, end.x) + ) { + move = validMoves[i]; + break; + } + } + + // then if a piece was clicked and we are on a valide cell + // we highlight it and display a hand cursor + if (pickedCell !== null && move !==null) { + selectedCell = pickedCell; + selectedCell.baseMaterial = selectedCell.material; + selectedCell.material = validCellMaterial[selectedCell.color]; + canvas.style.cursor = "pointer"; + } + } + + } + + function onDocumentMouseDown( event ) { + + var canvas = renderer.domElement; + var raycaster = getRay(event); + + var pickedPiece = pickPiece(raycaster); + var pickedCell = pickCell(raycaster); + + if (selectedPiece !== null && pickedCell !== null) { + if(playMove(selectedPiece,pickedCell)) { + // a move is played, we reset everything + // any selectedPiece will disappear + // since we redraw everything + selectedPiece = null; + pickedPiece = null; + pickedCell = null; + } + } + + // when a click happen, any selected piece gets unselected + if (selectedPiece !== null) { + selectedPiece.children[0].material = selectedPiece.baseMaterial; + //selectedPiece.children[1].material = selectedPiece.baseMaterial; + } + + // then if a piece was clicked, we select it + selectedPiece = pickedPiece; + if (selectedPiece !== null) { + selectedPiece.baseMaterial = selectedPiece.children[0].material; + selectedPiece.children[0].material = selectedMaterial[selectedPiece.color]; + //selectedPiece.children[1].material = selectedMaterial[selectedPiece.color]; + } + } + + + + // all resources (meshs and textures) are loaded + function onLoaded () { + //bar.container.style.display = "none"; + removeLoader(); + + init(); + if (DEBUG) { + window.scene = scene; + window.renderer = renderer; + } + newGame(WHITE); + animate(); + + //setTimeout(loadFEN('8/Q5P1/8/8/8/8/8/2K1k3 w - -'),2000); + + } + + window.SearchAndRedraw = SearchAndRedraw; + window.onLoaded = onLoaded; + window.redrawBoard = redrawBoard; + window.EnsureAnalysisStopped = EnsureAnalysisStopped; + window.InitializeBackgroundEngine = InitializeBackgroundEngine; + window.UIPlayMove = UIPlayMove; + +})(); \ No newline at end of file diff --git a/js/factory.js b/js/factory.js new file mode 100644 index 0000000..2ff37eb --- /dev/null +++ b/js/factory.js @@ -0,0 +1,420 @@ +// ECMAScript 5 strict mode +/* jshint globalstrict: true*/ +/* global THREE, $, document, window, console */ +/* global LOADING_BAR_SCALE,ROWS,COLS,PIECE_SIZE, BOARD_SIZE, FLOOR_SIZE, WIREFRAME, DEBUG, Cell, WHITE, BLACK, FEEDBACK, SHADOW */ +/* global createCell */ + +/* + * initPieceFactory and initCellFactory need to be called after + * all ressources are loaded (geometry and texture) + * + * they will create the createPiece and createCell function + * and keep some texture/material objects in a closure to avoid + * unnecessary cloning + */ + +"use strict"; +var geometries = {}; +var textures = {}; +function initPieceFactory () { + + // common textures + var tiling = 4; + var colors = []; + for(var c = 0; c<2; c++) { + colors[c] = textures['texture/wood-'+c+'.jpg'].clone(); + colors[c].tile(tiling); + } + var norm = textures['texture/wood_N.jpg'].clone(); + norm.tile(tiling); + var spec = textures['texture/wood_S.jpg'].clone(); + spec.tile(tiling); + + function createPiece(name,color) { + var size = BOARD_SIZE/COLS * PIECE_SIZE; + // container for the piece and its reflexion + var piece = new THREE.Object3D(); + // base material for all the piece (only lightmap changes) + var material = new THREE.MeshPhongMaterial({ + color:0xffffff, + specular:0xaaaaaa, + shininess:60.0, + map:colors[color], + normalMap:norm, + specularMap:spec, + wireframe:WIREFRAME + }); + material.normalScale.set(0.3,0.3); + + // urls of geometry and lightmap + var urlJson = '3D/json/'+name+'.json'; + var urlAO = 'texture/'+name+'-ao.jpg'; + + var geo = geometries[urlJson]; + // no need to clone this texture + // since its pretty specific + var light = textures[urlAO]; + light.format = THREE.LuminanceFormat; + + material.lightMap = light; + + var mesh = new THREE.Mesh(geo,material); + if (SHADOW) { + mesh.castShadow = true; + mesh.receiveShadow = true; + } + mesh.scale.set(size,size,size); + // we rotate pieces so they face each other (mostly relevant for knight) + mesh.rotation.y += (color == WHITE) ? -Math.PI/2 : Math.PI/2; + + // we create the reflection + // it's a cloned with a negative scale on the Y axis + var reflexion = mesh.clone(); + reflexion.scale.y *= -1; + reflexion.material = reflexion.material.clone(); + reflexion.material.side = THREE.BackSide; + + piece.add(mesh); + piece.add(reflexion); + + piece.name = name; + piece.color = color; + + return piece; + } + + // make it global + window.createPiece = createPiece; +} + +function initCellFactory() { + + var materials = []; + var tiling = 2; + + + // common textures + var diff; + var norm = textures['texture/wood_N.jpg'].clone(); + norm.tile(tiling); + var spec = textures['texture/wood_S.jpg'].clone(); + spec.tile(tiling); + + for(var c = 0; c<2; c++) { + + diff = textures['texture/wood-'+c+'.jpg'].clone(); + diff.tile(tiling); + + //common material + materials[c] = new THREE.MeshPhongMaterial({ + color:0xffffff, + specular:[0xAAAAAA,0x444444][c], + shininess:30.0, + wireframe:WIREFRAME, + transparent:true, + map:diff, + specularMap:spec, + normalMap:norm, + //blending: THREE.AdditiveBlending, + opacity:0.5 + }); + //materials[c].normalScale.set(0.5,0.5); + } + + function createCell(size,color) { + // container for the cell and its reflexion + var geo = new THREE.PlaneGeometry(size,size); + + // randomize uv offset to ad a bit of variety + var randU = Math.random(); + var randV = Math.random(); + + var uvs = geo.faceVertexUvs[0][0]; + for (var j = 0; j < uvs.length; j++) { + uvs[j].x += randU; + uvs[j].y += randV; + } + + var cell = new THREE.Mesh(geo,materials[color]); + + if (SHADOW) { + cell.receiveShadow = true; + } + + // by default PlaneGeometry is vertical + cell.rotation.x = -Math.PI/2; + cell.color = color; + return cell; + } + + // make it global + window.createCell = createCell; +} + + +function createChessBoard(size) { + // contains everything that makes the board + var lChessBoard = new THREE.Object3D(); + + var cellSize = size/COLS; + var square,cell; + + for(var i=0; i< ROWS*COLS; i++) { + + var col = i%COLS; + var row = Math.floor(i/COLS); + + cell = new Cell(i); + square = createCell(cellSize,1-(i+row)%2); + square.position = cell.getWorldPosition(); + square.name = cell.position; + + lChessBoard.add(square); + } + + // some fake inner environment color for reflexion + var innerBoard = new THREE.Mesh ( + geometries['3D/json/innerBoard.json'], + new THREE.MeshBasicMaterial({ + color:0x783e12 + }) + ); + innerBoard.scale.set(size,size,size); + + /// board borders + var tiling = 6; + var wood = textures['texture/wood-0.jpg'].clone(); + var spec = textures['texture/wood_S.jpg'].clone(); + var norm = textures['texture/wood_N.jpg'].clone(); + wood.tile(tiling); + spec.tile(tiling); + norm.tile(tiling); + + var geo = geometries['3D/json/board.json']; + geo.computeBoundingBox(); + + var board = new THREE.Mesh ( + geo, + new THREE.MeshPhongMaterial({ + color:0xffffff, + map:wood, + specular: 0xffffff, + specularMap: spec, + normalMap: norm, + shininess: 60, + normalScale: new THREE.Vector2(0.2,0.2) + }) + ); + var hCorrection = 0.62; // yeah I should just create a better geometry + board.scale.set(size,size*hCorrection,size); + lChessBoard.height = geo.boundingBox.min.y * board.scale.y; + + if (SHADOW) { + board.receiveShadow = true; + board.castShadow = true; + } + + lChessBoard.add(innerBoard); + lChessBoard.add(board); + + lChessBoard.name = "chessboard"; + return lChessBoard; +} + +function createFloor(size,chessboardSize) { + // The floor is a fake plane with a hole in it to allow + // for the fake reflexion trick to work + // so we build it vertices by vertices + + // material + var tiling = 30*size/1000; + var material = new THREE.MeshPhongMaterial({ + color:0xffffff, + wireframe:WIREFRAME , + specular:0xaaaaaa, + shininess:30 + + }); + var diff = textures['texture/floor.jpg']; + var spec = textures['texture/floor_S.jpg']; + var norm = textures['texture/floor_N.jpg']; + var light = textures['texture/fakeShadow.jpg']; + + diff.tile(tiling); + spec.tile(tiling); + norm.tile(tiling); + light.format = THREE.RGBFormat; + + material.map = diff; + material.normalMap = norm; + material.normalScale.set(0.6,0.6); + material.specularMap = spec; + material.lightMap = light; + + // geometry + var halfBoard = chessboardSize/2; + var halfSize = size/2; + + var floorGeo = new THREE.Geometry(); + // outter vertices + floorGeo.vertices.push(new THREE.Vector3(-halfSize,0,-halfSize)); + floorGeo.vertices.push(new THREE.Vector3( halfSize,0,-halfSize)); + floorGeo.vertices.push(new THREE.Vector3( halfSize,0, halfSize)); + floorGeo.vertices.push(new THREE.Vector3(-halfSize,0, halfSize)); + // hole vertices + floorGeo.vertices.push(new THREE.Vector3(-halfBoard,0,-halfBoard)); + floorGeo.vertices.push(new THREE.Vector3( halfBoard,0,-halfBoard)); + floorGeo.vertices.push(new THREE.Vector3( halfBoard,0, halfBoard)); + floorGeo.vertices.push(new THREE.Vector3(-halfBoard,0, halfBoard)); + + floorGeo.faceVertexUvs[ 0 ] = []; + floorGeo.faceVertexUvs[ 1 ] = []; + + /* + * vertices uvs-lightmap + * 0-----------1 80-----------80 + * |\ /| |\ /| + * | \ / | | \ / | + * | \ / | | \ / | + * | 4---5 | | 0---0 | + * | | | | | | | | + * | 7---6 | | 0---0 | + * | / \ | | / \ | + * | / \ | | / \ | + * |/ \| |/ \| + * 3-----------2 80-----------80 + */ + + // all normals just points upward + var normal = new THREE.Vector3( 0, 1, 0 ); + + // list of vertex index for each face + var faces = [ + [0,4,5,1], + [1,5,6,2], + [2,6,7,3], + [3,7,4,0] + ]; + + faces.forEach( function(f) { + var uvs1 = []; + var uvs2 = []; + var lightU,lightV; + f.forEach(function(v,i) { + // we linearily transform positions + // from a -halfSize-halfSize space + // to a 0-1 space + uvs1.push(new THREE.Vector2( + (floorGeo.vertices[v].x+halfSize)/size, + (floorGeo.vertices[v].z+halfSize)/size + )); + lightU = (v < 4) ? 80 : 0; + lightV = (i < 2) ? 0 : 1; + uvs2.push(new THREE.Vector2(lightU,lightV)); + }); + + // we create a new face folowing the faces list + var face = new THREE.Face4( + f[0],f[1],f[2],f[3] + ); + + // and apply normals (without this, no proper lighting) + face.normal.copy( normal ); + face.vertexNormals.push( + normal.clone(), + normal.clone(), + normal.clone(), + normal.clone() + ); + + // add the face to the geometry's faces list + floorGeo.faces.push(face); + + // add uv coordinates to uv channels. + floorGeo.faceVertexUvs[ 0 ].push(uvs1); // for diffuse/normal + floorGeo.faceVertexUvs[ 1 ].push(uvs2); // for lightmap + + }); + + // not sure it's needed but since it's in THREE.PlaneGeometry... + floorGeo.computeCentroids(); + + var floor = new THREE.Mesh(floorGeo,material); + + if(SHADOW) { + floor.receiveShadow = true; + } + + + floor.name = "floor"; + return floor; +} + +// special highlighting materials +var validCellMaterial = null; +function createValidCellMaterial () { + validCellMaterial = []; + var tiling = 2; + + + // common textures + var diff; + var norm = textures['texture/wood_N.jpg'].clone(); + norm.tile(tiling); + var spec = textures['texture/wood_S.jpg'].clone(); + spec.tile(tiling); + + for(var c = 0; c<2; c++) { + + diff = textures['texture/wood-1.jpg'].clone(); + diff.tile(tiling); + + //common material + validCellMaterial[c] = new THREE.MeshPhongMaterial({ + color:0x00ff00, + specular:0x999999, + shininess:60.0, + wireframe:WIREFRAME, + map:diff, + specularMap:spec, + normalMap:norm + }); + //materials[c].normalScale.set(0.5,0.5); + } +} + +var selectedMaterial = null; +function createSelectedMaterial() { + selectedMaterial = []; + var tiling = 4; + + + // common textures + var diff; + var norm = textures['texture/wood_N.jpg'].clone(); + norm.tile(tiling); + var spec = textures['texture/wood_S.jpg'].clone(); + spec.tile(tiling); + + for(var c = 0; c<2; c++) { + + diff = textures['texture/wood-1.jpg'].clone(); + diff.tile(tiling); + + //common material + selectedMaterial[c] = new THREE.MeshPhongMaterial({ + color:0x00ff00, + emissive:0x009900, + specular:0x999999, + shininess:60.0, + wireframe:WIREFRAME, + transparent:false, + map:diff, + specularMap:spec, + normalMap:norm + //opacity:0.4 + }); + selectedMaterial[c].normalScale.set(0.3,0.3); + } + +} \ No newline at end of file diff --git a/js/geoPieces.js b/js/geoPieces.js new file mode 100644 index 0000000..9e05765 --- /dev/null +++ b/js/geoPieces.js @@ -0,0 +1,279 @@ +// ECMAScript 5 strict mode +/* jshint globalstrict: true*/ +/* global THREE,console,BLACK,WHITE,WIREFRAME */ +"use strict"; +var pieceMaterial = []; +pieceMaterial[BLACK] = new THREE.MeshPhongMaterial({color:0x111111,specular:0xaaaaaa,shininess:30.0,wireframe:WIREFRAME}); +pieceMaterial[WHITE] = new THREE.MeshPhongMaterial({color:0xdddddd,wireframe:WIREFRAME}); +function createPawn(size,color) { + var pawn = new THREE.Object3D(); + var baseHeight = size*0.1; + var baseRadius = size*0.8; + var base = new THREE.Mesh( + new THREE.CylinderGeometry(baseRadius,baseRadius,baseHeight,32,1),pieceMaterial[color]); + base.position.y = baseHeight/2; + + var bodyRadius = size*0.6; + var body = new THREE.Mesh( + new THREE.SphereGeometry(bodyRadius,32,16),pieceMaterial[color]); + body.position.y = baseHeight + bodyRadius; + + var neckHeight = size; + var neckRadius = bodyRadius*0.7; + var neck = new THREE.Mesh( + new THREE.CylinderGeometry(0,neckRadius,neckHeight,32,1),pieceMaterial[color]); + neck.position.y = baseHeight + bodyRadius*2+neckHeight/2; + + var headRadius = size*0.2; + var head = new THREE.Mesh( + new THREE.SphereGeometry(headRadius,32,16),pieceMaterial[color]); + head.position.y = baseHeight + bodyRadius*2 +neckHeight+headRadius/2; + + pawn.add(head); + pawn.add(neck); + pawn.add(body); + pawn.add(base); + pawn.name = "Pawn"; + return pawn; +} + +function createRook(size,color) { + var rook = new THREE.Object3D(); + var baseHeight = size*0.1; + var baseRadius = size*0.8; + var base = new THREE.Mesh( + new THREE.CylinderGeometry(baseRadius,baseRadius,baseHeight,32,1),pieceMaterial[color]); + base.position.y = baseHeight/2; + var bodyRadius = size*0.4; + var bodyHeight = size*1.6; + var body = new THREE.Mesh( + new THREE.CylinderGeometry(bodyRadius*1.2,bodyRadius,bodyHeight,32,16),pieceMaterial[color]); + body.position.y = baseHeight + bodyHeight/2; + + var wedgeHeight = size*0.5; + var wedgeRadius = bodyRadius * 1.5; + var wedge = new THREE.Mesh( + new THREE.CylinderGeometry(wedgeRadius,bodyRadius*1.2,wedgeHeight,32,1),pieceMaterial[color]); + + wedge.position.y = baseHeight + bodyHeight+wedgeHeight/2; + + var teethThickness = size*0.2; + var teethHeight = wedgeHeight; + var teethTilt = size*0.1; + + var obr = wedgeRadius; + var ibr = wedgeRadius-teethThickness; + var otr = obr-teethTilt; + var itr = ibr-teethTilt; + var teethCount = 6; + var subdivision = Math.round(32/(teethCount*2)); + + var teethGeo = new THREE.TubeGeometry(otr,obr,itr,ibr,teethHeight,subdivision,1,0,2*Math.PI/(teethCount*2)); + + for (var i = 0; i < teethCount; i++) { + var teeth = new THREE.Mesh(teethGeo,pieceMaterial[color]); + teeth.position.y = baseHeight+bodyHeight+wedgeHeight+teethHeight/2; + teeth.rotation.y = i*2*Math.PI/teethCount; + rook.add(teeth); + } + + rook.add(wedge); + rook.add(body); + rook.add(base); + rook.name = "Rook"; + return rook; +} + +function createKnight(size,color) { + var knight = new THREE.Object3D(); + var baseHeight = size*0.1; + var baseRadius = size*0.8; + var base = new THREE.Mesh( + new THREE.CylinderGeometry(baseRadius,baseRadius,baseHeight,32,1),pieceMaterial[color]); + base.position.y = baseHeight/2; + + var bodyRadius = size*0.6; + var body = new THREE.Mesh( + new THREE.SphereGeometry(bodyRadius,32,16),pieceMaterial[color]); + + var neckHeight = size*1.2; + var neckBottomRadius = bodyRadius*0.6; + var neckTopRadius = bodyRadius*0.0; + var _neck = new THREE.Mesh( + new THREE.CylinderGeometry(neckTopRadius,neckBottomRadius,neckHeight,32,1),pieceMaterial[color]); + _neck.position.y = bodyRadius+neckHeight/2; + var neck = new THREE.Object3D(); + neck.add(_neck); + neck.rotation.z = -Math.PI/32; + + + var head = new THREE.Object3D(); + + var skullRadius = size*0.6; + var skull = new THREE.Mesh( + new THREE.SphereGeometry(skullRadius,32,16),pieceMaterial[color]); + + var faceHeight = size*1.0; + var faceBottomRadius = skullRadius*0.8; + var faceTopRadius = skullRadius*0.3; + var face = new THREE.Mesh( + new THREE.CylinderGeometry(faceTopRadius,faceBottomRadius,faceHeight,32,1),pieceMaterial[color]); + face.rotation.z = Math.PI/16; + face.position.y = skullRadius; + + var noseRadius = size*0.2; + var nose = new THREE.Mesh( + new THREE.SphereGeometry(noseRadius,32,16),pieceMaterial[color]); + nose.position.y = skullRadius +faceHeight+noseRadius/2; + + head.add(skull); + head.add(face); + //head.add(nose); + head.scale.z = 0.5; + head.rotation.z = 5*Math.PI/8; + head.position.y = bodyRadius+neckHeight; + + + var horse = new THREE.Object3D(); + horse.add(body); + horse.add(neck); + horse.add(head); + horse.rotation.z = -Math.PI/32; + horse.rotation.y = (color == whiteMat) ? -Math.PI/2 : Math.PI/2; + horse.position.y = baseHeight+bodyRadius; + + knight.add(horse); + knight.add(base); + knight.name = "Knight"; + return knight; +} + +function createBishop(size,color) { + var bishop = new THREE.Object3D(); + var baseHeight = size*0.1; + var baseRadius = size*0.8; + var base = new THREE.Mesh( + new THREE.CylinderGeometry(baseRadius,baseRadius,baseHeight,32,1),pieceMaterial[color]); + base.position.y = baseHeight/2; + + var bodyRadius = size*0.6; + var body = new THREE.Mesh( + new THREE.SphereGeometry(bodyRadius,32,16),pieceMaterial[color]); + body.position.y = baseHeight + bodyRadius; + + var neckHeight = size*1.7; + var neckBottomRadius = bodyRadius*0.3; + var neckTopRadius = bodyRadius*0.05; + var neck = new THREE.Mesh( + new THREE.CylinderGeometry(neckTopRadius,neckBottomRadius,neckHeight,32,1),pieceMaterial[color]); + neck.position.y = baseHeight + bodyRadius*2+neckHeight/2; + + var headRadius = size*0.2; + var head = new THREE.Mesh( + new THREE.SphereGeometry(headRadius,32,16),pieceMaterial[color]); + head.scale.y = 1.5; + head.position.y = baseHeight + bodyRadius*2 +neckHeight+headRadius/2; + + bishop.add(head); + bishop.add(neck); + bishop.add(body); + bishop.add(base); + bishop.name = "Bishop"; + return bishop; +} + + + +function createQueen(size,color) { + var queen = new THREE.Object3D(); + var baseHeight = size*0.1; + var baseRadius = size*0.8; + var base = new THREE.Mesh( + new THREE.CylinderGeometry(baseRadius,baseRadius,baseHeight,32,1),pieceMaterial[color]); + base.position.y = baseHeight/2; + + var bodyRadius = size*0.6; + var body = new THREE.Mesh( + new THREE.SphereGeometry(bodyRadius,32,16),pieceMaterial[color]); + body.position.y = baseHeight + bodyRadius; + + var neckHeight = size*2.3; + var neckBottomRadius = bodyRadius*0.3; + var neckTopRadius = bodyRadius*0.05; + var neck = new THREE.Mesh( + new THREE.CylinderGeometry(neckTopRadius,neckBottomRadius,neckHeight,32,1),pieceMaterial[color]); + neck.position.y = baseHeight + bodyRadius*2+neckHeight/2; + + var collarHeight = size* 0.1; + var collarRadius = size* 0.4; + var collar = new THREE.Mesh( + new THREE.CylinderGeometry(collarRadius,collarRadius,collarHeight,32,1),pieceMaterial[color]); + collar.position.y = baseHeight+bodyRadius*2+neckHeight - size*0.1; + + var headRadius = size*0.2; + var head = new THREE.Mesh( + new THREE.SphereGeometry(headRadius,32,16),pieceMaterial[color]); + head.position.y = baseHeight + bodyRadius*2 +neckHeight+headRadius/2; + + queen.add(head); + queen.add(collar); + queen.add(neck); + queen.add(body); + queen.add(base); + queen.name = "Queen"; + return queen; +} + + +function createKing(size,color) { + var king = new THREE.Object3D(); + var baseHeight = size*0.1; + var baseRadius = size*0.8; + var base = new THREE.Mesh( + new THREE.CylinderGeometry(baseRadius,baseRadius,baseHeight,32,1),pieceMaterial[color]); + base.position.y = baseHeight/2; + + var bodyRadius = size*0.6; + var body = new THREE.Mesh( + new THREE.SphereGeometry(bodyRadius,32,16),pieceMaterial[color]); + body.position.y = baseHeight + bodyRadius; + + var neckHeight = size*2.3; + var neckBottomRadius = bodyRadius*0.15; + var neckTopRadius = bodyRadius*0.2; + var neck = new THREE.Mesh( + new THREE.CylinderGeometry(neckTopRadius,neckBottomRadius,neckHeight,32,1),pieceMaterial[color]); + neck.position.y = baseHeight + bodyRadius*2+neckHeight/2; + + var collarHeight = size* 0.4; + var collarBottomRadius = size* 0.25; + var collarTopRadius = size* 0.45; + var collar = new THREE.Mesh( + new THREE.CylinderGeometry(collarTopRadius,collarBottomRadius,collarHeight,32,1),pieceMaterial[color]); + collar.position.y = baseHeight+bodyRadius*2+neckHeight - size*0.1; + + var cross = new THREE.Object3D(); + var crossThickness = size*0.2; + var crossHeight = size*0.8; + var crossGeo = new THREE.CubeGeometry(crossThickness,crossHeight,crossThickness); + + var hCross = new THREE.Mesh(crossGeo,pieceMaterial[color]); + hCross.position.y = crossHeight/2; + var vCross = new THREE.Mesh(crossGeo,pieceMaterial[color]); + vCross.rotation.z = Math.PI/2; + vCross.position.y = crossHeight/2; + + cross.add(hCross); + cross.add(vCross); + cross.position.y = baseHeight+bodyRadius*2 + neckHeight- size*0.1+collarHeight/2; + + + + king.add(cross); + king.add(collar); + king.add(neck); + king.add(body); + king.add(base); + king.name = "King"; + return king; +} \ No newline at end of file diff --git a/js/gui.js b/js/gui.js new file mode 100644 index 0000000..b32bc03 --- /dev/null +++ b/js/gui.js @@ -0,0 +1,545 @@ + +// ECMAScript 5 strict mode +/* jshint globalstrict: true*/ +/* jslint newcap: true */ +/* global THREE, $, document, window, console */ +/* global LOADING_BAR_SCALE,ROWS,COLS,PIECE_SIZE, BOARD_SIZE, FLOOR_SIZE, WIREFRAME, DEBUG, Cell, WHITE, BLACK, FEEDBACK, SHADOW */ +/* global SearchAndRedraw, UIPlayMove, camera, levels, g_allMoves:true, promotion:true, g_backgroundEngine:true, validMoves, InitializeBackgroundEngine, EnsureAnalysisStopped, newGame, redrawBoard, parsePGN, g_playerWhite:true */ + /*global Search,FormatSquare,GenerateMove,MakeMove,GetMoveSAN,MakeSquare,UnmakeMove, FormatMove, ResetGame, GetFen, GetMoveFromString, alert, InitializeFromFen, GenerateValidMoves */ + /*global g_inCheck,g_board,g_pieceList, g_toMove, g_timeout:true,g_maxply:true */ + /*global moveflagCastleKing, moveflagCastleQueen, moveflagEPC, moveflagPromotion, colorWhite*/ + /*global moveflagPromoteQueen,moveflagPromoteRook,moveflagPromoteBishop,moveflagPromoteKnight*/ + /*global piecePawn, pieceKnight, pieceBishop, pieceRook, pieceQueen, pieceKing */ +"use strict"; +(function () { + + // jQuery pgn textarea + var $pgn; + // list of moves in pgn format + var g_pgn = []; + // jQuery check feedback + var $info; + + function initInfo() { + // create the DOM element + // to display Chc + $info = $("
") + .css("position","absolute") + .position({ + of:$("body"), + my:"right top", + at:"right top" + }) + .attr("id","info") + .appendTo($("body")) + .css("left","auto") + .css("right","0"); + } + + + function initGUI() { + var $gui = $("
") + .css("position","absolute") + .position({ + of:$("body"), + my:"left top", + at:"left top" + }) + .width(150) + .attr("id","gui"); + + $("

") + .text("menu") + .appendTo($gui); + + var $menudiv = $("

").appendTo($gui); + + var $menu = $("
    ").appendTo($menudiv); + + makeButton("NewGame",newGameDialog,$menu); + makeButton("Undo",undo,$menu); + makeButton("Load",loadDialog,$menu); + makeButton("Save",save,$menu); + + $("