git.sesse.net Git - remoteglot/blob - www/js/chess.js

   1 /*
   2  * Copyright (c) 2017, Jeff Hlywa (jhlywa@gmail.com)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are met:
   7  *
   8  * 1. Redistributions of source code must retain the above copyright notice,
   9  *    this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright notice,
  11  *    this list of conditions and the following disclaimer in the documentation
  12  *    and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  18  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  24  * POSSIBILITY OF SUCH DAMAGE.
  25  *
  26  *----------------------------------------------------------------------------*/
  27
  28 /* minified license below  */
  29
  30 /* @license
  31  * Copyright (c) 2017, Jeff Hlywa (jhlywa@gmail.com)
  32  * Released under the BSD license
  33  * https://github.com/jhlywa/chess.js/blob/master/LICENSE
  34  */
  35
  36 var Chess = function(fen) {
  37
  38   /* jshint indent: false */
  39
  40   var BLACK = 'b';
  41   var WHITE = 'w';
  42
  43   var EMPTY = -1;
  44
  45   var PAWN = 'p';
  46   var KNIGHT = 'n';
  47   var BISHOP = 'b';
  48   var ROOK = 'r';
  49   var QUEEN = 'q';
  50   var KING = 'k';
  51
  52   var SYMBOLS = 'pnbrqkPNBRQK';
  53
  54   var DEFAULT_POSITION = 'rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1';
  55
  56   var POSSIBLE_RESULTS = ['1-0', '0-1', '1/2-1/2', '*'];
  57
  58   var PAWN_OFFSETS = {
  59     b: [16, 32, 17, 15],
  60     w: [-16, -32, -17, -15]
  61   };
  62
  63   var PIECE_OFFSETS = {
  64     n: [-18, -33, -31, -14,  18, 33, 31,  14],
  65     b: [-17, -15,  17,  15],
  66     r: [-16,   1,  16,  -1],
  67     q: [-17, -16, -15,   1,  17, 16, 15,  -1],
  68     k: [-17, -16, -15,   1,  17, 16, 15,  -1]
  69   };
  70
  71   var ATTACKS = [
  72     20, 0, 0, 0, 0, 0, 0, 24,  0, 0, 0, 0, 0, 0,20, 0,
  73      0,20, 0, 0, 0, 0, 0, 24,  0, 0, 0, 0, 0,20, 0, 0,
  74      0, 0,20, 0, 0, 0, 0, 24,  0, 0, 0, 0,20, 0, 0, 0,
  75      0, 0, 0,20, 0, 0, 0, 24,  0, 0, 0,20, 0, 0, 0, 0,
  76      0, 0, 0, 0,20, 0, 0, 24,  0, 0,20, 0, 0, 0, 0, 0,
  77      0, 0, 0, 0, 0,20, 2, 24,  2,20, 0, 0, 0, 0, 0, 0,
  78      0, 0, 0, 0, 0, 2,53, 56, 53, 2, 0, 0, 0, 0, 0, 0,
  79     24,24,24,24,24,24,56,  0, 56,24,24,24,24,24,24, 0,
  80      0, 0, 0, 0, 0, 2,53, 56, 53, 2, 0, 0, 0, 0, 0, 0,
  81      0, 0, 0, 0, 0,20, 2, 24,  2,20, 0, 0, 0, 0, 0, 0,
  82      0, 0, 0, 0,20, 0, 0, 24,  0, 0,20, 0, 0, 0, 0, 0,
  83      0, 0, 0,20, 0, 0, 0, 24,  0, 0, 0,20, 0, 0, 0, 0,
  84      0, 0,20, 0, 0, 0, 0, 24,  0, 0, 0, 0,20, 0, 0, 0,
  85      0,20, 0, 0, 0, 0, 0, 24,  0, 0, 0, 0, 0,20, 0, 0,
  86     20, 0, 0, 0, 0, 0, 0, 24,  0, 0, 0, 0, 0, 0,20
  87   ];
  88
  89   var RAYS = [
  90      17,  0,  0,  0,  0,  0,  0, 16,  0,  0,  0,  0,  0,  0, 15, 0,
  91       0, 17,  0,  0,  0,  0,  0, 16,  0,  0,  0,  0,  0, 15,  0, 0,
  92       0,  0, 17,  0,  0,  0,  0, 16,  0,  0,  0,  0, 15,  0,  0, 0,
  93       0,  0,  0, 17,  0,  0,  0, 16,  0,  0,  0, 15,  0,  0,  0, 0,
  94       0,  0,  0,  0, 17,  0,  0, 16,  0,  0, 15,  0,  0,  0,  0, 0,
  95       0,  0,  0,  0,  0, 17,  0, 16,  0, 15,  0,  0,  0,  0,  0, 0,
  96       0,  0,  0,  0,  0,  0, 17, 16, 15,  0,  0,  0,  0,  0,  0, 0,
  97       1,  1,  1,  1,  1,  1,  1,  0, -1, -1,  -1,-1, -1, -1, -1, 0,
  98       0,  0,  0,  0,  0,  0,-15,-16,-17,  0,  0,  0,  0,  0,  0, 0,
  99       0,  0,  0,  0,  0,-15,  0,-16,  0,-17,  0,  0,  0,  0,  0, 0,
 100       0,  0,  0,  0,-15,  0,  0,-16,  0,  0,-17,  0,  0,  0,  0, 0,
 101       0,  0,  0,-15,  0,  0,  0,-16,  0,  0,  0,-17,  0,  0,  0, 0,
 102       0,  0,-15,  0,  0,  0,  0,-16,  0,  0,  0,  0,-17,  0,  0, 0,
 103       0,-15,  0,  0,  0,  0,  0,-16,  0,  0,  0,  0,  0,-17,  0, 0,
 104     -15,  0,  0,  0,  0,  0,  0,-16,  0,  0,  0,  0,  0,  0,-17
 105   ];
 106
 107   var SHIFTS = { p: 0, n: 1, b: 2, r: 3, q: 4, k: 5 };
 108
 109   var FLAGS = {
 110     NORMAL: 'n',
 111     CAPTURE: 'c',
 112     BIG_PAWN: 'b',
 113     EP_CAPTURE: 'e',
 114     PROMOTION: 'p',
 115     KSIDE_CASTLE: 'k',
 116     QSIDE_CASTLE: 'q'
 117   };
 118
 119   var BITS = {
 120     NORMAL: 1,
 121     CAPTURE: 2,
 122     BIG_PAWN: 4,
 123     EP_CAPTURE: 8,
 124     PROMOTION: 16,
 125     KSIDE_CASTLE: 32,
 126     QSIDE_CASTLE: 64
 127   };
 128
 129   var RANK_1 = 7;
 130   var RANK_2 = 6;
 131   var RANK_3 = 5;
 132   var RANK_4 = 4;
 133   var RANK_5 = 3;
 134   var RANK_6 = 2;
 135   var RANK_7 = 1;
 136   var RANK_8 = 0;
 137
 138   var SQUARES = {
 139     a8:   0, b8:   1, c8:   2, d8:   3, e8:   4, f8:   5, g8:   6, h8:   7,
 140     a7:  16, b7:  17, c7:  18, d7:  19, e7:  20, f7:  21, g7:  22, h7:  23,
 141     a6:  32, b6:  33, c6:  34, d6:  35, e6:  36, f6:  37, g6:  38, h6:  39,
 142     a5:  48, b5:  49, c5:  50, d5:  51, e5:  52, f5:  53, g5:  54, h5:  55,
 143     a4:  64, b4:  65, c4:  66, d4:  67, e4:  68, f4:  69, g4:  70, h4:  71,
 144     a3:  80, b3:  81, c3:  82, d3:  83, e3:  84, f3:  85, g3:  86, h3:  87,
 145     a2:  96, b2:  97, c2:  98, d2:  99, e2: 100, f2: 101, g2: 102, h2: 103,
 146     a1: 112, b1: 113, c1: 114, d1: 115, e1: 116, f1: 117, g1: 118, h1: 119
 147   };
 148
 149   var board = new Array(128);
 150   var kings = {w: EMPTY, b: EMPTY};
 151   var rooks = {w: [], b: []};
 152   var turn = WHITE;
 153   var castling = {w: 0, b: 0};
 154   var ep_square = EMPTY;
 155   var half_moves = 0;
 156   var move_number = 1;
 157   var history = [];
 158   var header = {};
 159
 160   /* if the user passes in a fen string, load it, else default to
 161    * starting position
 162    */
 163   if (typeof fen === 'undefined') {
 164     load(DEFAULT_POSITION);
 165   } else {
 166     load(fen);
 167   }
 168
 169   function clear(keep_headers) {
 170     if (typeof keep_headers === 'undefined') {
 171       keep_headers = false;
 172     }
 173
 174     board = new Array(128);
 175     kings = {w: EMPTY, b: EMPTY};
 176     turn = WHITE;
 177     castling = {w: 0, b: 0};
 178     ep_square = EMPTY;
 179     half_moves = 0;
 180     move_number = 1;
 181     history = [];
 182     if (!keep_headers) header = {};
 183     update_setup(generate_fen());
 184   }
 185
 186   function reset() {
 187     load(DEFAULT_POSITION);
 188   }
 189
 190   function load(fen, keep_headers) {
 191     if (typeof keep_headers === 'undefined') {
 192       keep_headers = false;
 193     }
 194
 195     var tokens = fen.split(/\s+/);
 196     var position = tokens[0];
 197     var square = 0;
 198
 199     if (!validate_fen(fen).valid) {
 200       return false;
 201     }
 202
 203     clear(keep_headers);
 204
 205     for (var i = 0; i < position.length; i++) {
 206       var piece = position.charAt(i);
 207
 208       if (piece === '/') {
 209         square += 8;
 210       } else if (is_digit(piece)) {
 211         square += parseInt(piece, 10);
 212       } else {
 213         var color = (piece < 'a') ? WHITE : BLACK;
 214         put({type: piece.toLowerCase(), color: color}, algebraic(square));
 215         square++;
 216       }
 217     }
 218
 219     turn = tokens[1];
 220
 221     rooks = {w: [], b: []};
 222
 223     if (tokens[2].indexOf('K') > -1) {
 224       castling.w |= BITS.KSIDE_CASTLE;
 225       for (var sq = SQUARES.h1; sq >= SQUARES.c1; --sq) {
 226         if (is_rook(board[sq], WHITE)) {
 227           rooks[WHITE].push({square: sq, flag: BITS.KSIDE_CASTLE});
 228           break;
 229         }
 230       }
 231     }
 232     if (tokens[2].indexOf('Q') > -1) {
 233       castling.w |= BITS.QSIDE_CASTLE;
 234       for (var sq = SQUARES.a1; sq <= SQUARES.g1; ++sq) {
 235         if (is_rook(board[sq], WHITE)) {
 236           rooks[WHITE].push({square: sq, flag: BITS.QSIDE_CASTLE});
 237           break;
 238         }
 239       }
 240     }
 241     var white_frc_columns = tokens[2].match(/[A-H]/g);
 242     var i, flag;
 243     if (white_frc_columns !== null) {
 244       for (i = 0; i < white_frc_columns.length; ++i) {
 245         var sq = SQUARES.a1 + (white_frc_columns[i].charCodeAt(0) - "A".charCodeAt(0));
 246         flag = sq < kings[WHITE] ? BITS.QSIDE_CASTLE : BITS.KSIDE_CASTLE;
 247         castling.w |= flag;
 248         rooks[WHITE].push({square: sq, flag: flag});
 249       }
 250     }
 251
 252     if (tokens[2].indexOf('k') > -1) {
 253       castling.b |= BITS.KSIDE_CASTLE;
 254       for (var sq = SQUARES.h8; sq >= SQUARES.c8; --sq) {
 255         if (is_rook(board[sq], BLACK)) {
 256           rooks[BLACK].push({square: sq, flag: BITS.KSIDE_CASTLE});
 257           break;
 258         }
 259       }
 260     }
 261     if (tokens[2].indexOf('q') > -1) {
 262       castling.b |= BITS.QSIDE_CASTLE;
 263       for (var sq = SQUARES.a8; sq <= SQUARES.g8; ++sq) {
 264         if (is_rook(board[sq], BLACK)) {
 265           rooks[BLACK].push({square: sq, flag: BITS.QSIDE_CASTLE});
 266           break;
 267         }
 268       }
 269     }
 270     var black_frc_columns = tokens[2].match(/[a-h]/g);
 271     if (black_frc_columns !== null) {
 272       for (i = 0; i < black_frc_columns.length; ++i) {
 273         var sq = SQUARES.a8 + (black_frc_columns[i].charCodeAt(0) - "a".charCodeAt(0));
 274         flag = sq < kings[BLACK] ? BITS.QSIDE_CASTLE : BITS.KSIDE_CASTLE;
 275         castling.b |= flag;
 276         rooks[BLACK].push({square: sq, flag: flag});
 277       }
 278     }
 279
 280     ep_square = (tokens[3] === '-') ? EMPTY : SQUARES[tokens[3]];
 281     half_moves = parseInt(tokens[4], 10);
 282     move_number = parseInt(tokens[5], 10);
 283
 284     update_setup(generate_fen());
 285
 286     return true;
 287   }
 288
 289   /* TODO: this function is pretty much crap - it validates structure but
 290    * completely ignores content (e.g. doesn't verify that each side has a king)
 291    * ... we should rewrite this, and ditch the silly error_number field while
 292    * we're at it
 293    */
 294   function validate_fen(fen) {
 295     var errors = {
 296        0: 'No errors.',
 297        1: 'FEN string must contain six space-delimited fields.',
 298        2: '6th field (move number) must be a positive integer.',
 299        3: '5th field (half move counter) must be a non-negative integer.',
 300        4: '4th field (en-passant square) is invalid.',
 301        5: '3rd field (castling availability) is invalid.',
 302        6: '2nd field (side to move) is invalid.',
 303        7: '1st field (piece positions) does not contain 8 \'/\'-delimited rows.',
 304        8: '1st field (piece positions) is invalid [consecutive numbers].',
 305        9: '1st field (piece positions) is invalid [invalid piece].',
 306       10: '1st field (piece positions) is invalid [row too large].',
 307       11: 'Illegal en-passant square',
 308     };
 309
 310     /* 1st criterion: 6 space-seperated fields? */
 311     var tokens = fen.split(/\s+/);
 312     if (tokens.length !== 6) {
 313       return {valid: false, error_number: 1, error: errors[1]};
 314     }
 315
 316     /* 2nd criterion: move number field is a integer value > 0? */
 317     if (isNaN(tokens[5]) || (parseInt(tokens[5], 10) <= 0)) {
 318       return {valid: false, error_number: 2, error: errors[2]};
 319     }
 320
 321     /* 3rd criterion: half move counter is an integer >= 0? */
 322     if (isNaN(tokens[4]) || (parseInt(tokens[4], 10) < 0)) {
 323       return {valid: false, error_number: 3, error: errors[3]};
 324     }
 325
 326     /* 4th criterion: 4th field is a valid e.p.-string? */
 327     if (!/^(-|[abcdefgh][36])$/.test(tokens[3])) {
 328       return {valid: false, error_number: 4, error: errors[4]};
 329     }
 330
 331     /* 5th criterion: 3th field is a valid castle-string? */
 332     if( !/^[C-HK]?[A-FQ]?[c-hk]?[a-fq]?$/.test(tokens[2]) &&
 333         tokens[2] !== '-') {
 334       return {valid: false, error_number: 5, error: errors[5]};
 335     }
 336
 337     /* 6th criterion: 2nd field is "w" (white) or "b" (black)? */
 338     if (!/^(w|b)$/.test(tokens[1])) {
 339       return {valid: false, error_number: 6, error: errors[6]};
 340     }
 341
 342     /* 7th criterion: 1st field contains 8 rows? */
 343     var rows = tokens[0].split('/');
 344     if (rows.length !== 8) {
 345       return {valid: false, error_number: 7, error: errors[7]};
 346     }
 347
 348     /* 8th criterion: every row is valid? */
 349     for (var i = 0; i < rows.length; i++) {
 350       /* check for right sum of fields AND not two numbers in succession */
 351       var sum_fields = 0;
 352       var previous_was_number = false;
 353
 354       for (var k = 0; k < rows[i].length; k++) {
 355         if (!isNaN(rows[i][k])) {
 356           if (previous_was_number) {
 357             return {valid: false, error_number: 8, error: errors[8]};
 358           }
 359           sum_fields += parseInt(rows[i][k], 10);
 360           previous_was_number = true;
 361         } else {
 362           if (!/^[prnbqkPRNBQK]$/.test(rows[i][k])) {
 363             return {valid: false, error_number: 9, error: errors[9]};
 364           }
 365           sum_fields += 1;
 366           previous_was_number = false;
 367         }
 368       }
 369       if (sum_fields !== 8) {
 370         return {valid: false, error_number: 10, error: errors[10]};
 371       }
 372     }
 373
 374     if ((tokens[3][1] == '3' && tokens[1] == 'w') ||
 375         (tokens[3][1] == '6' && tokens[1] == 'b')) {
 376           return {valid: false, error_number: 11, error: errors[11]};
 377     }
 378
 379     /* everything's okay! */
 380     return {valid: true, error_number: 0, error: errors[0]};
 381   }
 382
 383   function generate_fen() {
 384     var empty = 0;
 385     var fen = '';
 386
 387     for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
 388       if (board[i] == null) {
 389         empty++;
 390       } else {
 391         if (empty > 0) {
 392           fen += empty;
 393           empty = 0;
 394         }
 395         var color = board[i].color;
 396         var piece = board[i].type;
 397
 398         fen += (color === WHITE) ?
 399                  piece.toUpperCase() : piece.toLowerCase();
 400       }
 401
 402       if ((i + 1) & 0x88) {
 403         if (empty > 0) {
 404           fen += empty;
 405         }
 406
 407         if (i !== SQUARES.h1) {
 408           fen += '/';
 409         }
 410
 411         empty = 0;
 412         i += 8;
 413       }
 414     }
 415
 416     var cflags = '';
 417     var sq;
 418     if (castling[WHITE] & BITS.KSIDE_CASTLE) {
 419       sq = search_rook(board, WHITE, BITS.KSIDE_CASTLE);
 420       if (is_outermost_rook(board, WHITE, BITS.KSIDE_CASTLE, sq)) {
 421         cflags += 'K';
 422       } else {
 423         cflags += 'ABCDEFGH'.substring(file(sq), file(sq) + 1);
 424       }
 425     }
 426     if (castling[WHITE] & BITS.QSIDE_CASTLE) {
 427       sq = search_rook(board, WHITE, BITS.QSIDE_CASTLE);
 428       if (is_outermost_rook(board, WHITE, BITS.QSIDE_CASTLE, sq)) {
 429         cflags += 'Q';
 430       } else {
 431         cflags += 'ABCDEFGH'.substring(file(sq), file(sq) + 1);
 432       }
 433     }
 434     if (castling[BLACK] & BITS.KSIDE_CASTLE) {
 435       sq = search_rook(board, BLACK, BITS.KSIDE_CASTLE);
 436       if (is_outermost_rook(board, BLACK, BITS.KSIDE_CASTLE, sq)) {
 437         cflags += 'k';
 438       } else {
 439         cflags += 'abcdefgh'.substring(file(sq), file(sq) + 1);
 440       }
 441     }
 442     if (castling[BLACK] & BITS.QSIDE_CASTLE) {
 443       sq = search_rook(board, BLACK, BITS.QSIDE_CASTLE);
 444       if (is_outermost_rook(board, BLACK, BITS.QSIDE_CASTLE, sq)) {
 445         cflags += 'q';
 446       } else {
 447         cflags += 'abcdefgh'.substring(file(sq), file(sq) + 1);
 448       }
 449     }
 450
 451     /* do we have an empty castling flag? */
 452     cflags = cflags || '-';
 453     var epflags = (ep_square === EMPTY) ? '-' : algebraic(ep_square);
 454
 455     return [fen, turn, cflags, epflags, half_moves, move_number].join(' ');
 456   }
 457
 458   function set_header(args) {
 459     for (var i = 0; i < args.length; i += 2) {
 460       if (typeof args[i] === 'string' &&
 461           typeof args[i + 1] === 'string') {
 462         header[args[i]] = args[i + 1];
 463       }
 464     }
 465     return header;
 466   }
 467
 468   /* called when the initial board setup is changed with put() or remove().
 469    * modifies the SetUp and FEN properties of the header object.  if the FEN is
 470    * equal to the default position, the SetUp and FEN are deleted
 471    * the setup is only updated if history.length is zero, ie moves haven't been
 472    * made.
 473    */
 474   function update_setup(fen) {
 475     if (history.length > 0) return;
 476
 477     if (fen !== DEFAULT_POSITION) {
 478       header['SetUp'] = '1';
 479       header['FEN'] = fen;
 480     } else {
 481       delete header['SetUp'];
 482       delete header['FEN'];
 483     }
 484   }
 485
 486   function get(square) {
 487     var piece = board[SQUARES[square]];
 488     return (piece) ? {type: piece.type, color: piece.color} : null;
 489   }
 490
 491   function put(piece, square) {
 492     /* check for valid piece object */
 493     if (!('type' in piece && 'color' in piece)) {
 494       return false;
 495     }
 496
 497     /* check for piece */
 498     if (SYMBOLS.indexOf(piece.type.toLowerCase()) === -1) {
 499       return false;
 500     }
 501
 502     /* check for valid square */
 503     if (!(square in SQUARES)) {
 504       return false;
 505     }
 506
 507     var sq = SQUARES[square];
 508
 509     /* don't let the user place more than one king */
 510     if (piece.type == KING &&
 511         !(kings[piece.color] == EMPTY || kings[piece.color] == sq)) {
 512       return false;
 513     }
 514
 515     board[sq] = {type: piece.type, color: piece.color};
 516     if (piece.type === KING) {
 517       kings[piece.color] = sq;
 518     }
 519
 520     update_setup(generate_fen());
 521
 522     return true;
 523   }
 524
 525   function remove(square) {
 526     var piece = get(square);
 527     board[SQUARES[square]] = null;
 528     if (piece && piece.type === KING) {
 529       kings[piece.color] = EMPTY;
 530     }
 531
 532     update_setup(generate_fen());
 533
 534     return piece;
 535   }
 536
 537   function build_move(board, from, to, flags, promotion, rook_sq) {
 538     var move = {
 539       color: turn,
 540       from: from,
 541       to: to,
 542       flags: flags,
 543       piece: board[from].type
 544     };
 545
 546     if (promotion) {
 547       move.flags |= BITS.PROMOTION;
 548       move.promotion = promotion;
 549     }
 550
 551     if (flags & (BITS.KSIDE_CASTLE | BITS.QSIDE_CASTLE)) {
 552       move.rook_sq = rook_sq;   // remember the position of the rook
 553     } else if (board[to]) {
 554       move.captured = board[to].type;
 555     } else if (flags & BITS.EP_CAPTURE) {
 556         move.captured = PAWN;
 557     }
 558     return move;
 559   }
 560
 561   function generate_moves(options) {
 562     function add_move(board, moves, from, to, flags, rook_sq) {
 563       /* if pawn promotion */
 564       if (board[from].type === PAWN &&
 565          (rank(to) === RANK_8 || rank(to) === RANK_1)) {
 566           var pieces = [QUEEN, ROOK, BISHOP, KNIGHT];
 567           for (var i = 0, len = pieces.length; i < len; i++) {
 568             moves.push(build_move(board, from, to, flags, pieces[i]));
 569           }
 570       } else {
 571        moves.push(build_move(board, from, to, flags, undefined, rook_sq));
 572       }
 573     }
 574
 575     function check_castle(board, king_from, king_to, rook_from, rook_to, them) {
 576       var sq;
 577
 578       // Check that no pieces are standing between the king and its destination
 579       // square, and also between the rook and its destination square.
 580       var king_left = Math.min(king_from, king_to);
 581       var king_right = Math.max(king_from, king_to);
 582       var left = Math.min(king_left, Math.min(rook_from, rook_to));
 583       var right = Math.max(king_right, Math.max(rook_from, rook_to));
 584       for (sq = left; sq <= right; ++sq) {
 585         if (sq != king_from && sq != rook_from && board[sq]) {
 586           return false;
 587         }
 588       }
 589
 590       // Check that none of the squares on the king's way are under attack.
 591       for (sq = king_left; sq <= king_right; ++sq) {
 592         if (attacked(them, sq)) {
 593           return false;
 594         }
 595       }
 596
 597       return true;
 598     }
 599
 600     var moves = [];
 601     var us = turn;
 602     var them = swap_color(us);
 603     var second_rank = {b: RANK_7, w: RANK_2};
 604
 605     var first_sq = SQUARES.a8;
 606     var last_sq = SQUARES.h1;
 607     var single_square = false;
 608
 609     /* do we want legal moves? */
 610     var legal = (typeof options !== 'undefined' && 'legal' in options) ?
 611                 options.legal : true;
 612
 613     /* are we generating moves for a single square? */
 614     if (typeof options !== 'undefined' && 'square' in options) {
 615       if (options.square in SQUARES) {
 616         first_sq = last_sq = SQUARES[options.square];
 617         single_square = true;
 618       } else {
 619         /* invalid square */
 620         return [];
 621       }
 622     }
 623
 624     for (var i = first_sq; i <= last_sq; i++) {
 625       /* did we run off the end of the board */
 626       if (i & 0x88) { i += 7; continue; }
 627
 628       var piece = board[i];
 629       if (piece == null || piece.color !== us) {
 630         continue;
 631       }
 632
 633       if (piece.type === PAWN) {
 634         /* single square, non-capturing */
 635         var square = i + PAWN_OFFSETS[us][0];
 636         if (board[square] == null) {
 637             add_move(board, moves, i, square, BITS.NORMAL);
 638
 639           /* double square */
 640           var square = i + PAWN_OFFSETS[us][1];
 641           if (second_rank[us] === rank(i) && board[square] == null) {
 642             add_move(board, moves, i, square, BITS.BIG_PAWN);
 643           }
 644         }
 645
 646         /* pawn captures */
 647         for (j = 2; j < 4; j++) {
 648           var square = i + PAWN_OFFSETS[us][j];
 649           if (square & 0x88) continue;
 650
 651           if (board[square] != null &&
 652               board[square].color === them) {
 653               add_move(board, moves, i, square, BITS.CAPTURE);
 654           } else if (square === ep_square) {
 655               add_move(board, moves, i, ep_square, BITS.EP_CAPTURE);
 656           }
 657         }
 658       } else {
 659         for (var j = 0, len = PIECE_OFFSETS[piece.type].length; j < len; j++) {
 660           var offset = PIECE_OFFSETS[piece.type][j];
 661           var square = i;
 662
 663           while (true) {
 664             square += offset;
 665             if (square & 0x88) break;
 666
 667             if (board[square] == null) {
 668               add_move(board, moves, i, square, BITS.NORMAL);
 669             } else {
 670               if (board[square].color === us) break;
 671               add_move(board, moves, i, square, BITS.CAPTURE);
 672               break;
 673             }
 674
 675             /* break, if knight or king */
 676             if (piece.type === 'n' || piece.type === 'k') break;
 677           }
 678         }
 679       }
 680     }
 681
 682     /* check for castling if: a) we're generating all moves, or b) we're doing
 683      * single square move generation on the king's square
 684      */
 685     if ((!single_square) || last_sq === kings[us]) {
 686       /* king-side castling */
 687       if (castling[us] & BITS.KSIDE_CASTLE) {
 688         var king_from = kings[us];
 689         var king_to = us === WHITE ? SQUARES.g1 : SQUARES.g8;
 690         var rook_from = search_rook(board, us, BITS.KSIDE_CASTLE);
 691         var rook_to = king_to - 1;
 692
 693         if (check_castle(board, king_from, king_to, rook_from, rook_to, them)) {
 694           add_move(board, moves, king_from, king_to, BITS.KSIDE_CASTLE, rook_from);
 695         }
 696       }
 697
 698       /* queen-side castling */
 699       if (castling[us] & BITS.QSIDE_CASTLE) {
 700         var king_from = kings[us];
 701         var king_to = us === WHITE ? SQUARES.c1 : SQUARES.c8;
 702         var rook_from = search_rook(board, us, BITS.QSIDE_CASTLE);
 703         var rook_to = king_to + 1;
 704
 705         if (check_castle(board, king_from, king_to, rook_from, rook_to, them)) {
 706           add_move(board, moves, king_from, king_to, BITS.QSIDE_CASTLE, rook_from);
 707         }
 708       }
 709     }
 710
 711     return possibly_filter_moves(moves, us, legal);
 712   }
 713
 714   function possibly_filter_moves(moves, us, legal) {
 715     /* return all pseudo-legal moves (this includes moves that allow the king
 716      * to be captured)
 717      */
 718     if (!legal) {
 719       return moves;
 720     }
 721
 722     /* filter out illegal moves */
 723     var legal_moves = [];
 724     for (var i = 0, len = moves.length; i < len; i++) {
 725       make_move(moves[i]);
 726       if (!king_attacked(us)) {
 727         legal_moves.push(moves[i]);
 728       }
 729       undo_move();
 730     }
 731
 732     return legal_moves;
 733   }
 734
 735   function is_rook(piece, color) {
 736     return (typeof piece !== 'undefined' && piece !== null &&
 737             piece.type === ROOK && piece.color == color);
 738   }
 739
 740   function search_rook(board, us, flag) {
 741     for (var i = 0, len = rooks[us].length; i < len; i++) {
 742       if (flag & rooks[us][i].flag) {
 743         return rooks[us][i].square;
 744       }
 745     }
 746     return null;
 747   }
 748
 749   function is_outermost_rook(board, us, flag, sq) {
 750     var end_sq;
 751     if (flag == BITS.KSIDE_CASTLE) {
 752       var end_sq = (us == WHITE) ? SQUARES.h1 : SQUARES.h8;
 753       while (++sq <= end_sq) {
 754         if (is_rook(board[sq], us)) {
 755            return false;
 756         }
 757       }
 758     } else {
 759       var end_sq = (us == WHITE) ? SQUARES.a1 : SQUARES.a8;
 760       while (--sq >= end_sq) {
 761         if (is_rook(board[sq], us)) {
 762            return false;
 763         }
 764       }
 765     }
 766     return true;
 767   }
 768
 769   /* convert a move from 0x88 coordinates to Standard Algebraic Notation
 770    * (SAN)
 771    *
 772    * @param {boolean} sloppy Use the sloppy SAN generator to work around over
 773    * disambiguation bugs in Fritz and Chessbase.  See below:
 774    *
 775    * r1bqkbnr/ppp2ppp/2n5/1B1pP3/4P3/8/PPPP2PP/RNBQK1NR b KQkq - 2 4
 776    * 4. ... Nge7 is overly disambiguated because the knight on c6 is pinned
 777    * 4. ... Ne7 is technically the valid SAN
 778    */
 779   function move_to_san(move, sloppy) {
 780
 781     var output = '';
 782
 783     if (move.flags & BITS.KSIDE_CASTLE) {
 784       output = 'O-O';
 785     } else if (move.flags & BITS.QSIDE_CASTLE) {
 786       output = 'O-O-O';
 787     } else {
 788       var disambiguator = get_disambiguator(move, sloppy);
 789
 790       if (move.piece !== PAWN) {
 791         output += move.piece.toUpperCase() + disambiguator;
 792       }
 793
 794       if (move.flags & (BITS.CAPTURE | BITS.EP_CAPTURE)) {
 795         if (move.piece === PAWN) {
 796           output += algebraic(move.from)[0];
 797         }
 798         output += 'x';
 799       }
 800
 801       output += algebraic(move.to);
 802
 803       if (move.flags & BITS.PROMOTION) {
 804         output += '=' + move.promotion.toUpperCase();
 805       }
 806     }
 807
 808     make_move(move);
 809     if (in_check()) {
 810       if (in_checkmate()) {
 811         output += '#';
 812       } else {
 813         output += '+';
 814       }
 815     }
 816     undo_move();
 817
 818     return output;
 819   }
 820
 821   // parses all of the decorators out of a SAN string
 822   function stripped_san(move) {
 823     return move.replace(/=/,'').replace(/[+#]?[?!]*$/,'');
 824   }
 825
 826   function attacked(color, square) {
 827     for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
 828       /* did we run off the end of the board */
 829       if (i & 0x88) { i += 7; continue; }
 830
 831       /* if empty square or wrong color */
 832       if (board[i] == null || board[i].color !== color) continue;
 833
 834       var piece = board[i];
 835       var difference = i - square;
 836       var index = difference + 119;
 837
 838       if (ATTACKS[index] & (1 << SHIFTS[piece.type])) {
 839         if (piece.type === PAWN) {
 840           if (difference > 0) {
 841             if (piece.color === WHITE) return true;
 842           } else {
 843             if (piece.color === BLACK) return true;
 844           }
 845           continue;
 846         }
 847
 848         /* if the piece is a knight or a king */
 849         if (piece.type === 'n' || piece.type === 'k') return true;
 850
 851         var offset = RAYS[index];
 852         var j = i + offset;
 853
 854         var blocked = false;
 855         while (j !== square) {
 856           if (board[j] != null) { blocked = true; break; }
 857           j += offset;
 858         }
 859
 860         if (!blocked) return true;
 861       }
 862     }
 863
 864     return false;
 865   }
 866
 867   function king_attacked(color) {
 868     return attacked(swap_color(color), kings[color]);
 869   }
 870
 871   function in_check() {
 872     return king_attacked(turn);
 873   }
 874
 875   function in_checkmate() {
 876     return in_check() && generate_moves().length === 0;
 877   }
 878
 879   function in_stalemate() {
 880     return !in_check() && generate_moves().length === 0;
 881   }
 882
 883   function insufficient_material() {
 884     var pieces = {};
 885     var bishops = [];
 886     var num_pieces = 0;
 887     var sq_color = 0;
 888
 889     for (var i = SQUARES.a8; i<= SQUARES.h1; i++) {
 890       sq_color = (sq_color + 1) % 2;
 891       if (i & 0x88) { i += 7; continue; }
 892
 893       var piece = board[i];
 894       if (piece) {
 895         pieces[piece.type] = (piece.type in pieces) ?
 896                               pieces[piece.type] + 1 : 1;
 897         if (piece.type === BISHOP) {
 898           bishops.push(sq_color);
 899         }
 900         num_pieces++;
 901       }
 902     }
 903
 904     /* k vs. k */
 905     if (num_pieces === 2) { return true; }
 906
 907     /* k vs. kn .... or .... k vs. kb */
 908     else if (num_pieces === 3 && (pieces[BISHOP] === 1 ||
 909                                  pieces[KNIGHT] === 1)) { return true; }
 910
 911     /* kb vs. kb where any number of bishops are all on the same color */
 912     else if (num_pieces === pieces[BISHOP] + 2) {
 913       var sum = 0;
 914       var len = bishops.length;
 915       for (var i = 0; i < len; i++) {
 916         sum += bishops[i];
 917       }
 918       if (sum === 0 || sum === len) { return true; }
 919     }
 920
 921     return false;
 922   }
 923
 924   function in_threefold_repetition() {
 925     /* TODO: while this function is fine for casual use, a better
 926      * implementation would use a Zobrist key (instead of FEN). the
 927      * Zobrist key would be maintained in the make_move/undo_move functions,
 928      * avoiding the costly that we do below.
 929      */
 930     var moves = [];
 931     var positions = {};
 932     var repetition = false;
 933
 934     while (true) {
 935       var move = undo_move();
 936       if (!move) break;
 937       moves.push(move);
 938     }
 939
 940     while (true) {
 941       /* remove the last two fields in the FEN string, they're not needed
 942        * when checking for draw by rep */
 943       var fen = generate_fen().split(' ').slice(0,4).join(' ');
 944
 945       /* has the position occurred three or move times */
 946       positions[fen] = (fen in positions) ? positions[fen] + 1 : 1;
 947       if (positions[fen] >= 3) {
 948         repetition = true;
 949       }
 950
 951       if (!moves.length) {
 952         break;
 953       }
 954       make_move(moves.pop());
 955     }
 956
 957     return repetition;
 958   }
 959
 960   function push(move) {
 961     history.push({
 962       move: move,
 963       kings: {b: kings.b, w: kings.w},
 964       turn: turn,
 965       castling: {b: castling.b, w: castling.w},
 966       ep_square: ep_square,
 967       half_moves: half_moves,
 968       move_number: move_number
 969     });
 970   }
 971
 972   function make_move(move) {
 973     var us = turn;
 974     var them = swap_color(us);
 975     push(move);
 976
 977     board[move.to] = board[move.from];
 978     if (move.from != move.to) {
 979       board[move.from] = null;
 980     }
 981
 982     /* if ep capture, remove the captured pawn */
 983     if (move.flags & BITS.EP_CAPTURE) {
 984       if (turn === BLACK) {
 985         board[move.to - 16] = null;
 986       } else {
 987         board[move.to + 16] = null;
 988       }
 989     }
 990
 991     /* if pawn promotion, replace with new piece */
 992     if (move.flags & BITS.PROMOTION) {
 993       board[move.to] = {type: move.promotion, color: us};
 994     }
 995
 996     /* if we moved the king */
 997     if (board[move.to].type === KING) {
 998       kings[board[move.to].color] = move.to;
 999
1000       /* if we castled, move the rook next to the king */
1001       if (move.flags & BITS.KSIDE_CASTLE) {
1002         var castling_to = move.to - 1;
1003         var castling_from = move.rook_sq;
1004         board[castling_to] = {type: ROOK, color: us};
1005         if(castling_from !== move.to && castling_from !== castling_to)
1006           board[castling_from] = null;
1007       } else if (move.flags & BITS.QSIDE_CASTLE) {
1008         var castling_to = move.to + 1;
1009         var castling_from = move.rook_sq;
1010         board[castling_to] = {type: ROOK, color: us};
1011         if(castling_from !== move.to && castling_from !== castling_to)
1012           board[castling_from] = null;
1013       }
1014
1015       /* turn off castling */
1016       castling[us] = '';
1017     }
1018
1019     /* turn off castling if we move a rook */
1020     if (castling[us]) {
1021       for (var i = 0, len = rooks[us].length; i < len; i++) {
1022         if (move.from === rooks[us][i].square &&
1023             castling[us] & rooks[us][i].flag) {
1024           castling[us] ^= rooks[us][i].flag;
1025           break;
1026         }
1027       }
1028     }
1029
1030     /* turn off castling if we capture a rook */
1031     if (castling[them]) {
1032       for (var i = 0, len = rooks[them].length; i < len; i++) {
1033         if (move.to === rooks[them][i].square &&
1034             castling[them] & rooks[them][i].flag) {
1035           castling[them] ^= rooks[them][i].flag;
1036           break;
1037         }
1038       }
1039     }
1040
1041     /* if big pawn move, update the en passant square */
1042     if (move.flags & BITS.BIG_PAWN) {
1043       if (turn === 'b') {
1044         ep_square = move.to - 16;
1045       } else {
1046         ep_square = move.to + 16;
1047       }
1048     } else {
1049       ep_square = EMPTY;
1050     }
1051
1052     /* reset the 50 move counter if a pawn is moved or a piece is captured */
1053     if (move.piece === PAWN) {
1054       half_moves = 0;
1055     } else if (move.flags & (BITS.CAPTURE | BITS.EP_CAPTURE)) {
1056       half_moves = 0;
1057     } else {
1058       half_moves++;
1059     }
1060
1061     if (turn === BLACK) {
1062       move_number++;
1063     }
1064     turn = swap_color(turn);
1065   }
1066
1067   function undo_move() {
1068     var old = history.pop();
1069     if (old == null) { return null; }
1070
1071     var move = old.move;
1072     kings = old.kings;
1073     turn = old.turn;
1074     castling = old.castling;
1075     ep_square = old.ep_square;
1076     half_moves = old.half_moves;
1077     move_number = old.move_number;
1078
1079     var us = turn;
1080     var them = swap_color(turn);
1081
1082     if (move.from != move.to) {
1083       board[move.from] = board[move.to];
1084       board[move.from].type = move.piece;  // to undo any promotions
1085       board[move.to] = null;
1086     }
1087
1088     if (move.flags & BITS.CAPTURE) {
1089       board[move.to] = {type: move.captured, color: them};
1090     } else if (move.flags & BITS.EP_CAPTURE) {
1091       var index;
1092       if (us === BLACK) {
1093         index = move.to - 16;
1094       } else {
1095         index = move.to + 16;
1096       }
1097       board[index] = {type: PAWN, color: them};
1098     }
1099
1100
1101     if (move.flags & (BITS.KSIDE_CASTLE | BITS.QSIDE_CASTLE)) {
1102       var castling_to, castling_from;
1103       if (move.flags & BITS.KSIDE_CASTLE) {
1104         castling_to = move.rook_sq;
1105         castling_from = move.to - 1;
1106       } else if (move.flags & BITS.QSIDE_CASTLE) {
1107         castling_to = move.rook_sq;
1108         castling_from = move.to + 1;
1109       }
1110
1111       board[castling_to] = {type: ROOK, color: us};
1112       if(castling_from !== move.from && castling_from !== castling_to)
1113         board[castling_from] = null;
1114     }
1115
1116     return move;
1117   }
1118
1119   /* this function is used to uniquely identify ambiguous moves */
1120   function get_disambiguator(move, sloppy) {
1121     var from = move.from;
1122     var to = move.to;
1123     var piece = move.piece;
1124
1125     if (piece === 'p' || piece === 'k') {
1126        // Pawn or king moves are never ambiguous.
1127        return '';
1128     }
1129
1130     let moves = find_attacking_moves(move.to, piece, move.color, sloppy);
1131
1132     var ambiguities = 0;
1133     var same_rank = 0;
1134     var same_file = 0;
1135
1136     for (var i = 0, len = moves.length; i < len; i++) {
1137       var ambig_from = moves[i].from;
1138       var ambig_to = moves[i].to;
1139       var ambig_piece = moves[i].piece;
1140
1141       /* if a move of the same piece type ends on the same to square, we'll
1142        * need to add a disambiguator to the algebraic notation
1143        */
1144       if (piece === ambig_piece && from !== ambig_from && to === ambig_to) {
1145         ambiguities++;
1146
1147         if (rank(from) === rank(ambig_from)) {
1148           same_rank++;
1149         }
1150
1151         if (file(from) === file(ambig_from)) {
1152           same_file++;
1153         }
1154       }
1155     }
1156
1157     if (ambiguities > 0) {
1158       /* if there exists a similar moving piece on the same rank and file as
1159        * the move in question, use the square as the disambiguator
1160        */
1161       if (same_rank > 0 && same_file > 0) {
1162         return algebraic(from);
1163       }
1164       /* if the moving piece rests on the same file, use the rank symbol as the
1165        * disambiguator
1166        */
1167       else if (same_file > 0) {
1168         return algebraic(from).charAt(1);
1169       }
1170       /* else use the file symbol */
1171       else {
1172         return algebraic(from).charAt(0);
1173       }
1174     }
1175
1176     return '';
1177   }
1178
1179   // Find all moves featuring the given piece attacking the given square
1180   // (using symmetry of all non-pawn-or-castle moves, we simply generate
1181   // moves backwards). Does not support kings or pawns. Assumes there's
1182   // not already a piece of our own color on the destination square.
1183   function find_attacking_moves(to, piece, us, sloppy) {
1184     let moves = [];
1185
1186     function add_move(board, moves, from, to, flags, rook_sq) {
1187       moves.push(build_move(board, from, to, flags, undefined, rook_sq));
1188     }
1189     for (let offset of PIECE_OFFSETS[piece]) {
1190       var square = to;
1191
1192       while (true) {
1193         square += offset;
1194         if (square & 0x88) break;
1195
1196         if (board[square] != null) {
1197           if (board[square].color !== us) break;
1198           if (board[to] == null) {
1199             add_move(board, moves, square, to, BITS.NORMAL);
1200           } else {
1201             add_move(board, moves, square, to, BITS.CAPTURE);
1202           }
1203           break;
1204         }
1205
1206         /* break if knight */
1207         if (piece === 'n') break;
1208       }
1209     }
1210
1211     return possibly_filter_moves(moves, us, !sloppy);
1212   }
1213
1214   function ascii() {
1215     var s = '   +------------------------+\n';
1216     for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
1217       /* display the rank */
1218       if (file(i) === 0) {
1219         s += ' ' + '87654321'[rank(i)] + ' |';
1220       }
1221
1222       /* empty piece */
1223       if (board[i] == null) {
1224         s += ' . ';
1225       } else {
1226         var piece = board[i].type;
1227         var color = board[i].color;
1228         var symbol = (color === WHITE) ?
1229                      piece.toUpperCase() : piece.toLowerCase();
1230         s += ' ' + symbol + ' ';
1231       }
1232
1233       if ((i + 1) & 0x88) {
1234         s += '|\n';
1235         i += 8;
1236       }
1237     }
1238     s += '   +------------------------+\n';
1239     s += '     a  b  c  d  e  f  g  h\n';
1240
1241     return s;
1242   }
1243
1244   // convert a move from Standard Algebraic Notation (SAN) to 0x88 coordinates
1245   function move_from_san(move, sloppy) {
1246     // strip off any move decorations: e.g Nf3+?!
1247     var clean_move = stripped_san(move);
1248
1249     // if we're using the sloppy parser run a regex to grab piece, to, and from
1250     // this should parse invalid SAN like: Pe2-e4, Rc1c4, Qf3xf7
1251     if (sloppy) {
1252       var matches = clean_move.match(/([pnbrqkPNBRQK])?([a-h][1-8])x?-?([a-h][1-8])([qrbnQRBN])?/);
1253       if (matches) {
1254         var piece = matches[1];
1255         var from = matches[2];
1256         var to = matches[3];
1257         var promotion = matches[4];
1258       }
1259     }
1260
1261     var moves = generate_moves();
1262     for (var i = 0, len = moves.length; i < len; i++) {
1263       // try the strict parser first, then the sloppy parser if requested
1264       // by the user
1265       if ((clean_move === stripped_san(move_to_san(moves[i]))) ||
1266           (sloppy && clean_move === stripped_san(move_to_san(moves[i], true)))) {
1267         return moves[i];
1268       } else {
1269         if (matches &&
1270             (!piece || piece.toLowerCase() == moves[i].piece) &&
1271             SQUARES[from] == moves[i].from &&
1272             SQUARES[to] == moves[i].to &&
1273             (!promotion || promotion.toLowerCase() == moves[i].promotion)) {
1274           return moves[i];
1275         }
1276       }
1277     }
1278
1279     return null;
1280   }
1281
1282
1283   /*****************************************************************************
1284    * UTILITY FUNCTIONS
1285    ****************************************************************************/
1286   function rank(i) {
1287     return i >> 4;
1288   }
1289
1290   function file(i) {
1291     return i & 15;
1292   }
1293
1294   function algebraic(i){
1295     var f = file(i), r = rank(i);
1296     return 'abcdefgh'.substring(f,f+1) + '87654321'.substring(r,r+1);
1297   }
1298
1299   function swap_color(c) {
1300     return c === WHITE ? BLACK : WHITE;
1301   }
1302
1303   function is_digit(c) {
1304     return '0123456789'.indexOf(c) !== -1;
1305   }
1306
1307   /* pretty = external move object */
1308   function make_pretty(ugly_move) {
1309     var move = clone(ugly_move);
1310     move.san = move_to_san(move, false);
1311     move.to = algebraic(move.to);
1312     move.from = algebraic(move.from);
1313
1314     var flags = '';
1315
1316     for (var flag in BITS) {
1317       if (BITS[flag] & move.flags) {
1318         flags += FLAGS[flag];
1319       }
1320     }
1321     move.flags = flags;
1322
1323     return move;
1324   }
1325
1326   function clone(obj) {
1327     var dupe = (obj instanceof Array) ? [] : {};
1328
1329     for (var property in obj) {
1330       if (typeof property === 'object') {
1331         dupe[property] = clone(obj[property]);
1332       } else {
1333         dupe[property] = obj[property];
1334       }
1335     }
1336
1337     return dupe;
1338   }
1339
1340   function trim(str) {
1341     return str.replace(/^\s+|\s+$/g, '');
1342   }
1343
1344   /*****************************************************************************
1345    * DEBUGGING UTILITIES
1346    ****************************************************************************/
1347   function perft(depth) {
1348     var moves = generate_moves({legal: false});
1349     var nodes = 0;
1350     var color = turn;
1351
1352     for (var i = 0, len = moves.length; i < len; i++) {
1353       make_move(moves[i]);
1354       if (!king_attacked(color)) {
1355         if (depth - 1 > 0) {
1356           var child_nodes = perft(depth - 1);
1357           nodes += child_nodes;
1358         } else {
1359           nodes++;
1360         }
1361       }
1362       undo_move();
1363     }
1364
1365     return nodes;
1366   }
1367
1368   return {
1369     /***************************************************************************
1370      * PUBLIC CONSTANTS (is there a better way to do this?)
1371      **************************************************************************/
1372     WHITE: WHITE,
1373     BLACK: BLACK,
1374     PAWN: PAWN,
1375     KNIGHT: KNIGHT,
1376     BISHOP: BISHOP,
1377     ROOK: ROOK,
1378     QUEEN: QUEEN,
1379     KING: KING,
1380     SQUARES: (function() {
1381                 /* from the ECMA-262 spec (section 12.6.4):
1382                  * "The mechanics of enumerating the properties ... is
1383                  * implementation dependent"
1384                  * so: for (var sq in SQUARES) { keys.push(sq); } might not be
1385                  * ordered correctly
1386                  */
1387                 var keys = [];
1388                 for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
1389                   if (i & 0x88) { i += 7; continue; }
1390                   keys.push(algebraic(i));
1391                 }
1392                 return keys;
1393               })(),
1394     FLAGS: FLAGS,
1395
1396     /***************************************************************************
1397      * PUBLIC API
1398      **************************************************************************/
1399     load: function(fen) {
1400       return load(fen);
1401     },
1402
1403     reset: function() {
1404       return reset();
1405     },
1406
1407     moves: function(options) {
1408       /* The internal representation of a chess move is in 0x88 format, and
1409        * not meant to be human-readable.  The code below converts the 0x88
1410        * square coordinates to algebraic coordinates.  It also prunes an
1411        * unnecessary move keys resulting from a verbose call.
1412        */
1413
1414       var ugly_moves = generate_moves(options);
1415       var moves = [];
1416
1417       for (var i = 0, len = ugly_moves.length; i < len; i++) {
1418
1419         /* does the user want a full move object (most likely not), or just
1420          * SAN
1421          */
1422         if (typeof options !== 'undefined' && 'verbose' in options &&
1423             options.verbose) {
1424           moves.push(make_pretty(ugly_moves[i]));
1425         } else {
1426           moves.push(move_to_san(ugly_moves[i], false));
1427         }
1428       }
1429
1430       return moves;
1431     },
1432
1433     in_check: function() {
1434       return in_check();
1435     },
1436
1437     in_checkmate: function() {
1438       return in_checkmate();
1439     },
1440
1441     in_stalemate: function() {
1442       return in_stalemate();
1443     },
1444
1445     in_draw: function() {
1446       return half_moves >= 100 ||
1447              in_stalemate() ||
1448              insufficient_material() ||
1449              in_threefold_repetition();
1450     },
1451
1452     insufficient_material: function() {
1453       return insufficient_material();
1454     },
1455
1456     in_threefold_repetition: function() {
1457       return in_threefold_repetition();
1458     },
1459
1460     game_over: function() {
1461       return half_moves >= 100 ||
1462              in_checkmate() ||
1463              in_stalemate() ||
1464              insufficient_material() ||
1465              in_threefold_repetition();
1466     },
1467
1468     validate_fen: function(fen) {
1469       return validate_fen(fen);
1470     },
1471
1472     fen: function() {
1473       return generate_fen();
1474     },
1475
1476     board: function() {
1477       var output = [],
1478           row    = [];
1479
1480       for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
1481         if (board[i] == null) {
1482           row.push(null)
1483         } else {
1484           row.push({type: board[i].type, color: board[i].color})
1485         }
1486         if ((i + 1) & 0x88) {
1487           output.push(row);
1488           row = []
1489           i += 8;
1490         }
1491       }
1492
1493       return output;
1494     },
1495
1496     pgn: function(options) {
1497       /* using the specification from http://www.chessclub.com/help/PGN-spec
1498        * example for html usage: .pgn({ max_width: 72, newline_char: "<br />" })
1499        */
1500       var newline = (typeof options === 'object' &&
1501                      typeof options.newline_char === 'string') ?
1502                      options.newline_char : '\n';
1503       var max_width = (typeof options === 'object' &&
1504                        typeof options.max_width === 'number') ?
1505                        options.max_width : 0;
1506       var result = [];
1507       var header_exists = false;
1508
1509       /* add the PGN header headerrmation */
1510       for (var i in header) {
1511         /* TODO: order of enumerated properties in header object is not
1512          * guaranteed, see ECMA-262 spec (section 12.6.4)
1513          */
1514         result.push('[' + i + ' \"' + header[i] + '\"]' + newline);
1515         header_exists = true;
1516       }
1517
1518       if (header_exists && history.length) {
1519         result.push(newline);
1520       }
1521
1522       /* pop all of history onto reversed_history */
1523       var reversed_history = [];
1524       while (history.length > 0) {
1525         reversed_history.push(undo_move());
1526       }
1527
1528       var moves = [];
1529       var move_string = '';
1530
1531       /* build the list of moves.  a move_string looks like: "3. e3 e6" */
1532       while (reversed_history.length > 0) {
1533         var move = reversed_history.pop();
1534
1535         /* if the position started with black to move, start PGN with 1. ... */
1536         if (!history.length && move.color === 'b') {
1537           move_string = move_number + '. ...';
1538         } else if (move.color === 'w') {
1539           /* store the previous generated move_string if we have one */
1540           if (move_string.length) {
1541             moves.push(move_string);
1542           }
1543           move_string = move_number + '.';
1544         }
1545
1546         move_string = move_string + ' ' + move_to_san(move, false);
1547         make_move(move);
1548       }
1549
1550       /* are there any other leftover moves? */
1551       if (move_string.length) {
1552         moves.push(move_string);
1553       }
1554
1555       /* is there a result? */
1556       if (typeof header.Result !== 'undefined') {
1557         moves.push(header.Result);
1558       }
1559
1560       /* history should be back to what is was before we started generating PGN,
1561        * so join together moves
1562        */
1563       if (max_width === 0) {
1564         return result.join('') + moves.join(' ');
1565       }
1566
1567       /* wrap the PGN output at max_width */
1568       var current_width = 0;
1569       for (var i = 0; i < moves.length; i++) {
1570         /* if the current move will push past max_width */
1571         if (current_width + moves[i].length > max_width && i !== 0) {
1572
1573           /* don't end the line with whitespace */
1574           if (result[result.length - 1] === ' ') {
1575             result.pop();
1576           }
1577
1578           result.push(newline);
1579           current_width = 0;
1580         } else if (i !== 0) {
1581           result.push(' ');
1582           current_width++;
1583         }
1584         result.push(moves[i]);
1585         current_width += moves[i].length;
1586       }
1587
1588       return result.join('');
1589     },
1590
1591     load_pgn: function(pgn, options) {
1592       // allow the user to specify the sloppy move parser to work around over
1593       // disambiguation bugs in Fritz and Chessbase
1594       var sloppy = (typeof options !== 'undefined' && 'sloppy' in options) ?
1595                     options.sloppy : false;
1596
1597       function mask(str) {
1598         return str.replace(/\\/g, '\\');
1599       }
1600
1601       function has_keys(object) {
1602         for (var key in object) {
1603           return true;
1604         }
1605         return false;
1606       }
1607
1608       function parse_pgn_header(header, options) {
1609         var newline_char = (typeof options === 'object' &&
1610                             typeof options.newline_char === 'string') ?
1611                             options.newline_char : '\r?\n';
1612         var header_obj = {};
1613         var headers = header.split(new RegExp(mask(newline_char)));
1614         var key = '';
1615         var value = '';
1616
1617         for (var i = 0; i < headers.length; i++) {
1618           key = headers[i].replace(/^\[([A-Z][A-Za-z]*)\s.*\]$/, '$1');
1619           value = headers[i].replace(/^\[[A-Za-z]+\s"(.*)"\]$/, '$1');
1620           if (trim(key).length > 0) {
1621             header_obj[key] = value;
1622           }
1623         }
1624
1625         return header_obj;
1626       }
1627
1628       var newline_char = (typeof options === 'object' &&
1629                           typeof options.newline_char === 'string') ?
1630                           options.newline_char : '\r?\n';
1631       var regex = new RegExp('^(\\[(.|' + mask(newline_char) + ')*\\])' +
1632                              '(' + mask(newline_char) + ')*' +
1633                              '1.(' + mask(newline_char) + '|.)*$', 'g');
1634
1635       /* get header part of the PGN file */
1636       var header_string = pgn.replace(regex, '$1');
1637
1638       /* no info part given, begins with moves */
1639       if (header_string[0] !== '[') {
1640         header_string = '';
1641       }
1642
1643       reset();
1644
1645       /* parse PGN header */
1646       var headers = parse_pgn_header(header_string, options);
1647       for (var key in headers) {
1648         set_header([key, headers[key]]);
1649       }
1650
1651       /* load the starting position indicated by [Setup '1'] and
1652       * [FEN position] */
1653       if (headers['SetUp'] === '1') {
1654           if (!(('FEN' in headers) && load(headers['FEN'], true ))) { // second argument to load: don't clear the headers
1655             return false;
1656           }
1657       }
1658
1659       /* delete header to get the moves */
1660       var ms = pgn.replace(header_string, '').replace(new RegExp(mask(newline_char), 'g'), ' ');
1661
1662       /* delete comments */
1663       ms = ms.replace(/(\{[^}]+\})+?/g, '');
1664
1665       /* delete recursive annotation variations */
1666       var rav_regex = /(\([^\(\)]+\))+?/g
1667       while (rav_regex.test(ms)) {
1668         ms = ms.replace(rav_regex, '');
1669       }
1670
1671       /* delete move numbers */
1672       ms = ms.replace(/\d+\.(\.\.)?/g, '');
1673
1674       /* delete ... indicating black to move */
1675       ms = ms.replace(/\.\.\./g, '');
1676
1677       /* delete numeric annotation glyphs */
1678       ms = ms.replace(/\$\d+/g, '');
1679
1680       /* trim and get array of moves */
1681       var moves = trim(ms).split(new RegExp(/\s+/));
1682
1683       /* delete empty entries */
1684       moves = moves.join(',').replace(/,,+/g, ',').split(',');
1685       var move = '';
1686
1687       for (var half_move = 0; half_move < moves.length - 1; half_move++) {
1688         move = move_from_san(moves[half_move], sloppy);
1689
1690         /* move not possible! (don't clear the board to examine to show the
1691          * latest valid position)
1692          */
1693         if (move == null) {
1694           return false;
1695         } else {
1696           make_move(move);
1697         }
1698       }
1699
1700       /* examine last move */
1701       move = moves[moves.length - 1];
1702       if (POSSIBLE_RESULTS.indexOf(move) > -1) {
1703         if (has_keys(header) && typeof header.Result === 'undefined') {
1704           set_header(['Result', move]);
1705         }
1706       }
1707       else {
1708         move = move_from_san(move, sloppy);
1709         if (move == null) {
1710           return false;
1711         } else {
1712           make_move(move);
1713         }
1714       }
1715       return true;
1716     },
1717
1718     header: function() {
1719       return set_header(arguments);
1720     },
1721
1722     ascii: function() {
1723       return ascii();
1724     },
1725
1726     turn: function() {
1727       return turn;
1728     },
1729
1730     move: function(move, options) {
1731       /* The move function can be called with in the following parameters:
1732        *
1733        * .move('Nxb7')      <- where 'move' is a case-sensitive SAN string
1734        *
1735        * .move({ from: 'h7', <- where the 'move' is a move object (additional
1736        *         to :'h8',      fields are ignored)
1737        *         promotion: 'q',
1738        *      })
1739        */
1740
1741       // allow the user to specify the sloppy move parser to work around over
1742       // disambiguation bugs in Fritz and Chessbase
1743       var sloppy = (typeof options !== 'undefined' && 'sloppy' in options) ?
1744                     options.sloppy : false;
1745
1746       var move_obj = null;
1747
1748       if (typeof move === 'string') {
1749         move_obj = move_from_san(move, sloppy);
1750       } else if (typeof move === 'object') {
1751         var moves = generate_moves();
1752
1753         /* convert the pretty move object to an ugly move object */
1754         for (var i = 0, len = moves.length; i < len; i++) {
1755           if (move.from === algebraic(moves[i].from) &&
1756               move.to === algebraic(moves[i].to) &&
1757               (!('promotion' in moves[i]) ||
1758               move.promotion === moves[i].promotion)) {
1759             move_obj = moves[i];
1760             break;
1761           }
1762         }
1763       }
1764
1765       /* failed to find move */
1766       if (!move_obj) {
1767         return null;
1768       }
1769
1770       /* need to make a copy of move because we can't generate SAN after the
1771        * move is made
1772        */
1773       var pretty_move = make_pretty(move_obj);
1774
1775       make_move(move_obj);
1776
1777       return pretty_move;
1778     },
1779
1780     undo: function() {
1781       var move = undo_move();
1782       return (move) ? make_pretty(move) : null;
1783     },
1784
1785     clear: function() {
1786       return clear();
1787     },
1788
1789     put: function(piece, square) {
1790       return put(piece, square);
1791     },
1792
1793     get: function(square) {
1794       return get(square);
1795     },
1796
1797     remove: function(square) {
1798       return remove(square);
1799     },
1800
1801     perft: function(depth) {
1802       return perft(depth);
1803     },
1804
1805     square_color: function(square) {
1806       if (square in SQUARES) {
1807         var sq_0x88 = SQUARES[square];
1808         return ((rank(sq_0x88) + file(sq_0x88)) % 2 === 0) ? 'light' : 'dark';
1809       }
1810
1811       return null;
1812     },
1813
1814     history: function(options) {
1815       var reversed_history = [];
1816       var move_history = [];
1817       var verbose = (typeof options !== 'undefined' && 'verbose' in options &&
1818                      options.verbose);
1819
1820       while (history.length > 0) {
1821         reversed_history.push(undo_move());
1822       }
1823
1824       while (reversed_history.length > 0) {
1825         var move = reversed_history.pop();
1826         if (verbose) {
1827           move_history.push(make_pretty(move));
1828         } else {
1829           move_history.push(move_to_san(move));
1830         }
1831         make_move(move);
1832       }
1833
1834       return move_history;
1835     }
1836
1837   };
1838 };
1839
1840 /* export Chess object if using node or any other CommonJS compatible
1841  * environment */
1842 if (typeof exports !== 'undefined') exports.Chess = Chess;
1843 /* export Chess object for any RequireJS compatible environment */
1844 if (typeof define !== 'undefined') define( function () { return Chess;  });