// Cloned by Enhanced on 7 Aug 2018 from World "Chess : Mind vs Simple AI (a bit of random)" by Mathias Bazin // Please leave this clone trail here. // Cloned by Mathias Bazin on 1 Aug 2018 from World "Chess : Mind vs Simple AI - Depth 1" by Mathias Bazin // Please leave this clone trail here. // Cloned by Mathias Bazin on 1 Aug 2018 from World "Chess : Mind vs Random" by Mathias Bazin // Please leave this clone trail here. //=== Explanations ============================================================= //The Score system //Currently the scoring system works as follows : // - The Mind starts with a base score of 200 (in other words, 200 is the neutral score for a perfect draw) // - The Mind earns 100 points for winning the game (checkmate), loses 100 points for loosing (gets checkmated) // - The Mind earns an amount of points for each of his pieces left and loses the same for each opposing pieces left at the end of the game // Values of the pieces : // pawn : 1 // rook : 5 // bishop : 3 // knight : 3 // queen : 9 // - If the game ends before turn 100, additional points for speed are added (in the case of a win) or removed (a lose) // Formula for the time points : timePoints = 2 * ( 100 - turn ) //Avoiding threefold repetition //In chess and some other abstract strategy games, the threefold repetition rule (also known as repetition of position) //states that a player can claim a draw if the same position occurs three times, or will occur after their next move, //with the same player to move. The repeated positions do not need to occur in succession. //The idea behind the rule is that if the position occurs three times, no progress is being made. //When 2 AIs play against each other it is very common that they enter a cycle and start doing the same moves over and over again, //causing a draw because of this rule. To prevent this, the black AI will choose a random move rather than causing a threefold repetition to happen. //Random //Some random has to be put in the opponent playstyle or else the games will always be strictly the same. //For now, the first move of the black player is picked randomly so that makes only 18 different possible openings so 18 //possible games. I have to think of a better way to do this. Maybe choosing rando;ly a turn at the beginning of the game //and makig Black play random at this turn. //TODO //Make the AIs play multiple games and take the average score as the final one //============================================================================== AB.clockTick = 60; function World() { let depth = 1; //This sets how many moves the opponent's AI will look ahead //when computing its move. Therefore, it influences greatly the //strength of the opponent. //Its value should be within 1 and 3. If going farther than 3, //the game will take a lot of time to compute, at least on a standard //browser allowing only 1 CPU core per tab. let chess; let scl = 40; let xoff = 100; let yoff = $(document).height()/2; let turn = 0; let preventRepetition = true; let randomTurn; let ctx; let self = this; let bk, bq, bn, br, bb, bp, wk, wq, wn, wr, wb, wp, board; let fens = []; function drawBoard(board) { let square = 0; for(let cur of board) { switch(cur) { case "r": ctx.drawImage(br, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "n": ctx.drawImage(bn, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "b": ctx.drawImage(bb, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "q": ctx.drawImage(bq, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "k": ctx.drawImage(bk, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "p": ctx.drawImage(bp, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "R": ctx.drawImage(wr, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "N": ctx.drawImage(wn, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "B": ctx.drawImage(wb, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "Q": ctx.drawImage(wq, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "K": ctx.drawImage(wk, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "P": ctx.drawImage(wp, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); // text(cur, xoff + scl*(square%8), yoff + scl*(Math.floor(square/8))); square++; break; case "/": break; case " ": return; case "1": case "2": case "3": case "4": case "5": case "6": case "7": case "8": square += +cur; break; default: console.log("Error in drawBoard"); } } } function drawGrid() { ctx.drawImage(board,xoff,yoff); } this.newRun = function() { threeworld.init ( "white" ); ctx = threeworld.getContext ( "2d" ); AB.runReady = false; $.getScript ( "https://cdnjs.cloudflare.com/ajax/libs/chess.js/0.10.2/chess.js", function() { console.log("chess loaded"); chess = new Chess(); drawBoard(chess.fen()); AB.runReady = true; }); bk = new Image(); bk.src = '/uploads/mathias/bk.png'; bq = new Image(); bq.src = '/uploads/mathias/bq.png'; bn = new Image(); bn.src = '/uploads/mathias/bn.png'; br = new Image(); br.src = '/uploads/mathias/br.png'; bb = new Image(); bb.src = '/uploads/mathias/bb.png'; bp = new Image(); bp.src = '/uploads/mathias/bp.png'; wk = new Image(); wk.src = '/uploads/mathias/wk.png'; wq = new Image(); wq.src = '/uploads/mathias/wq.png'; wn = new Image(); wn.src = '/uploads/mathias/wn.png'; wr = new Image(); wr.src = '/uploads/mathias/wr.png'; wb = new Image(); wb.src = '/uploads/mathias/wb.png'; wp = new Image(); wp.src = '/uploads/mathias/wp.png'; board = new Image(); board.src = '/uploads/mathias/board.png' randomTurn = AB.randomIntAtoB(1,10); let s = "Your mind plays against a depth " + depth + " AI"; $("#user_span1").html("
"+s+"
"); console.log(s); console.log("Random turn for Black has been chosen to be turn", randomTurn); }; this.takeAction = function ( action ) { if (!chess.game_over()) { if(chess.turn() == 'w') { turn++; $("#user_span2").html("Turn " + turn + "
Black has to make a move
"); //must write black here so it is actually displayed at the right time, don't really know why if (chess.move(action) === null) { console.log("White tried to make an illegal move"); } } else //Black player makes his move { $("#user_span2").html("Turn " + turn + "
White has to make a move
"); if (turn == randomTurn) //at turn chosen randomly do a random move so games may vary { console.log("Black plays randomly"); let moves = chess.moves(); let move = moves[Math.floor(Math.random() * moves.length)]; chess.move(move); //random legal move } else { let move = minimaxRoot(depth, chess, true); chess.move(move); while (preventRepetition && in_threefold_repetition(chess)) { console.log("Black tries to avoid threefold repetition"); chess.undo(); let moves = chess.moves(); move = moves[Math.floor(Math.random() * moves.length)]; chess.move(move); //random legal move } } } drawGrid(); drawBoard(chess.fen()); // console.log(chess.ascii()); } else { ABRun.abortRun = true; } }; this.getState = function() { return chess.fen(); }; this.getScore = function() { let score = 200; //base score let fen = chess.fen(); let i = 0; //points for the pieces while (fen[i] != " ") { switch(fen[i]) { case 'r': score -= 5; break; case 'n': case 'b': score -= 3; break; case 'p': score -= 1; break; case 'q': score -= 9; break; case 'R': score += 5; break; case 'N': case 'B': score += 3; break; case 'P': score += 1; break; case 'Q': score += 9; break; } i++; } console.log("pieces points : ", score - 200); //points for the win/lose and time if(chess.in_checkmate()) { let timePoints = 100 - turn; if (timePoints < 0) timePoints = 0; timePoints *= 2; if (chess.turn() == 'b') { console.log("time points : ", timePoints); console.log("win points : ", 100); score += 100; score += timePoints; } else { console.log("time points : ", -timePoints); console.log("lose points : ", -100); score -= 100; score -= timePoints; } } return score; } this.endRun = function() { let s = "Game Over"; if (chess.in_draw()) { s += " : Draw"; if (chess.insufficient_material()) s += " (insufficient material)"; if (chess.in_stalemate()) s += " (stalemate)"; if (in_threefold_repetition(chess)) s += " (threefold repetition)"; } else if(chess.in_checkmate()) { if (chess.turn() == 'b') s+= " : White wins (Black has been checkmated)"; else s+= " : Black wins (White has been checkmated)"; } console.log(s); $("#user_span3").html("" + s + "
"); ctx.font = "20px Arial"; ctx.fillText(s,xoff,yoff - 20); $("#user_span3").html("" + s + "
Score : " + self.getScore() + "
"); $("#user_span4").html(""); $("#replay").on("click", startReplay); } function startReplay() { let moves = chess.history(); let chess1 = new Chess(); fens.push( chess1.fen() ); for (let move of moves) { chess1.move(move); fens.push( chess1.fen() ); } $("#user_span2").html("In total : "+ turn + " turns, " + fens.length + " moves.
" ); $("#user_span4").html("Move # :
"); $("#replayMove").on("keyPress", updateReplay); $("#replayMove").on("change", updateReplay); drawGrid(); drawBoard(fens[0]); } function updateReplay() { let moveIndex = $("#replayMove").val() - 1; drawGrid(); drawBoard(fens[moveIndex]); } /*=========================The "AI" part starts here *====================*/ let positionCount; let minimaxRoot =function(depth, game, isMaximisingPlayer) { let newGameMoves = game.moves(); let bestMove = -9999; let bestMoveFound; for(let i = 0; i < newGameMoves.length; i++) { let newGameMove = newGameMoves[i] game.move(newGameMove); let value = minimax(depth - 1, game, -10000, 10000, !isMaximisingPlayer); game.undo(); if(value >= bestMove) { bestMove = value; bestMoveFound = newGameMove; } } return bestMoveFound; }; let minimax = function (depth, game, alpha, beta, isMaximisingPlayer) { positionCount++; if (depth === 0) { return -evaluateBoard(toBoard(game)); } let newGameMoves = game.moves(); if (isMaximisingPlayer) { let bestMove = -9999; for (let i = 0; i < newGameMoves.length; i++) { game.move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer)); game.undo(); alpha = Math.max(alpha, bestMove); if (beta <= alpha) { return bestMove; } } return bestMove; } else { let bestMove = 9999; for (let i = 0; i < newGameMoves.length; i++) { game.move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer)); game.undo(); beta = Math.min(beta, bestMove); if (beta <= alpha) { return bestMove; } } return bestMove; } }; let evaluateBoard = function (board) { let totalEvaluation = 0; for (let i = 0; i < 8; i++) { for (let j = 0; j < 8; j++) { totalEvaluation = totalEvaluation + getPieceValue(board[i][j], i ,j); } } return totalEvaluation; }; let reverseArray = function(array) { return array.slice().reverse(); }; let pawnEvalWhite = [ [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0], [1.0, 1.0, 2.0, 3.0, 3.0, 2.0, 1.0, 1.0], [0.5, 0.5, 1.0, 2.5, 2.5, 1.0, 0.5, 0.5], [0.0, 0.0, 0.0, 2.0, 2.0, 0.0, 0.0, 0.0], [0.5, -0.5, -1.0, 0.0, 0.0, -1.0, -0.5, 0.5], [0.5, 1.0, 1.0, -2.0, -2.0, 1.0, 1.0, 0.5], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] ]; let pawnEvalBlack = reverseArray(pawnEvalWhite); let knightEval = [ [-5.0, -4.0, -3.0, -3.0, -3.0, -3.0, -4.0, -5.0], [-4.0, -2.0, 0.0, 0.0, 0.0, 0.0, -2.0, -4.0], [-3.0, 0.0, 1.0, 1.5, 1.5, 1.0, 0.0, -3.0], [-3.0, 0.5, 1.5, 2.0, 2.0, 1.5, 0.5, -3.0], [-3.0, 0.0, 1.5, 2.0, 2.0, 1.5, 0.0, -3.0], [-3.0, 0.5, 1.0, 1.5, 1.5, 1.0, 0.5, -3.0], [-4.0, -2.0, 0.0, 0.5, 0.5, 0.0, -2.0, -4.0], [-5.0, -4.0, -3.0, -3.0, -3.0, -3.0, -4.0, -5.0] ]; let bishopEvalWhite = [ [ -2.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -2.0], [ -1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -1.0], [ -1.0, 0.0, 0.5, 1.0, 1.0, 0.5, 0.0, -1.0], [ -1.0, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, -1.0], [ -1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0, -1.0], [ -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, -1.0], [ -1.0, 0.5, 0.0, 0.0, 0.0, 0.0, 0.5, -1.0], [ -2.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -2.0] ]; let bishopEvalBlack = reverseArray(bishopEvalWhite); let rookEvalWhite = [ [ 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [ 0.5, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.5], [ -0.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -0.5], [ -0.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -0.5], [ -0.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -0.5], [ -0.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -0.5], [ -0.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -0.5], [ 0.0, 0.0, 0.0, 0.5, 0.5, 0.0, 0.0, 0.0] ]; let rookEvalBlack = reverseArray(rookEvalWhite); let evalQueen = [ [ -2.0, -1.0, -1.0, -0.5, -0.5, -1.0, -1.0, -2.0], [ -1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -1.0], [ -1.0, 0.0, 0.5, 0.5, 0.5, 0.5, 0.0, -1.0], [ -0.5, 0.0, 0.5, 0.5, 0.5, 0.5, 0.0, -0.5], [ 0.0, 0.0, 0.5, 0.5, 0.5, 0.5, 0.0, -0.5], [ -1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.0, -1.0], [ -1.0, 0.0, 0.5, 0.0, 0.0, 0.0, 0.0, -1.0], [ -2.0, -1.0, -1.0, -0.5, -0.5, -1.0, -1.0, -2.0] ]; let kingEvalWhite = [ [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0], [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0], [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0], [ -3.0, -4.0, -4.0, -5.0, -5.0, -4.0, -4.0, -3.0], [ -2.0, -3.0, -3.0, -4.0, -4.0, -3.0, -3.0, -2.0], [ -1.0, -2.0, -2.0, -2.0, -2.0, -2.0, -2.0, -1.0], [ 2.0, 2.0, 0.0, 0.0, 0.0, 0.0, 2.0, 2.0 ], [ 2.0, 3.0, 1.0, 0.0, 0.0, 1.0, 3.0, 2.0 ] ]; let kingEvalBlack = reverseArray(kingEvalWhite); let getPieceValue = function (piece, x, y) { if (piece === null) { return 0; } let getAbsoluteValue = function (piece, isWhite, x ,y) { if (piece.type === 'p') { return 10 + ( isWhite ? pawnEvalWhite[y][x] : pawnEvalBlack[y][x] ); } else if (piece.type === 'r') { return 50 + ( isWhite ? rookEvalWhite[y][x] : rookEvalBlack[y][x] ); } else if (piece.type === 'n') { return 30 + knightEval[y][x]; } else if (piece.type === 'b') { return 30 + ( isWhite ? bishopEvalWhite[y][x] : bishopEvalBlack[y][x] ); } else if (piece.type === 'q') { return 90 + evalQueen[y][x]; } else if (piece.type === 'k') { return 900 + ( isWhite ? kingEvalWhite[y][x] : kingEvalBlack[y][x] ); } throw "Unknown piece type: " + piece.type; }; let absoluteValue = getAbsoluteValue(piece, piece.color === 'w', x ,y); return piece.color === 'w' ? absoluteValue : -absoluteValue; }; function toBoard(game) { let letters = ['a','b','c','d','e','f','g','h']; let nbs = ['8','7','6','5','4','3','2','1']; let b = new Array(8); for (let i =0; i<8; i++) { b[i] = new Array(8); for (let j = 0; j <8; j++) { let square = letters[j] + nbs[i]; b[i][j] = game.get(square); } } return b; } function boardToString(b) { let s = ""; for (let i = 0; i<8; i++) { for (let j = 0; j<8; j++) { if (b[i][j] === null) s += " "; else { if (b[i][j].color == 'b') s += b[i][j].type; else s += b[i][j].type.toUpperCase(); } } s += "\n"; } return s; } function in_threefold_repetition(game) { /* to do: while this function is fine for casual use, a better implementation would use a Zobrist key (instead of FEN). the Zobrist key would be maintained in the make_move/undo_move functions, avoiding the costly that we do below. */ var moves = []; var positions = {}; var repetition = false; while (true) { var move = game.undo(); if (!move) break; moves.push(move); } while (true) { /* remove the last two fields in the FEN string, they're not needed * when checking for draw by rep */ var fen = game.fen().split(' ').slice(0,4).join(' '); /* has the position occurred three or move times */ positions[fen] = (fen in positions) ? positions[fen] + 1 : 1; if (positions[fen] >= 3) { repetition = true; } if (!moves.length) { break; } game.move(moves.pop()); } return repetition; } }