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