Upgrade Chess.js to a version that supports Chess960 castling.
[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 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[0].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.a1 + (black_frc_columns[0].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 all pseudo-legal moves (this includes moves that allow the king
712      * to be captured)
713      */
714     if (!legal) {
715       return moves;
716     }
717
718     /* filter out illegal moves */
719     var legal_moves = [];
720     for (var i = 0, len = moves.length; i < len; i++) {
721       make_move(moves[i]);
722       if (!king_attacked(us)) {
723         legal_moves.push(moves[i]);
724       }
725       undo_move();
726     }
727
728     return legal_moves;
729   }
730
731   function is_rook(piece, color) {
732     return (typeof piece !== 'undefined' && piece !== null &&
733             piece.type === ROOK && piece.color == color);
734   }
735
736   function search_rook(board, us, flag) {
737     for (var i = 0, len = rooks[us].length; i < len; i++) {
738       if (flag & rooks[us][i].flag) {
739         return rooks[us][i].square;
740       }
741     }
742     return null;
743   }
744
745   function is_outermost_rook(board, us, flag, sq) {
746     var end_sq;
747     if (flag == BITS.KSIDE_CASTLE) {
748       var end_sq = (us == WHITE) ? SQUARES.h1 : SQUARES.h8;
749       while (++sq <= end_sq) {
750         if (is_rook(board[sq], us)) {
751            return false;
752         }
753       }
754     } else {
755       var end_sq = (us == WHITE) ? SQUARES.a1 : SQUARES.a8;
756       while (--sq >= end_sq) {
757         if (is_rook(board[sq], us)) {
758            return false;
759         }
760       }
761     }
762     return true;
763   }
764
765   /* convert a move from 0x88 coordinates to Standard Algebraic Notation
766    * (SAN)
767    *
768    * @param {boolean} sloppy Use the sloppy SAN generator to work around over
769    * disambiguation bugs in Fritz and Chessbase.  See below:
770    *
771    * r1bqkbnr/ppp2ppp/2n5/1B1pP3/4P3/8/PPPP2PP/RNBQK1NR b KQkq - 2 4
772    * 4. ... Nge7 is overly disambiguated because the knight on c6 is pinned
773    * 4. ... Ne7 is technically the valid SAN
774    */
775   function move_to_san(move, sloppy) {
776
777     var output = '';
778
779     if (move.flags & BITS.KSIDE_CASTLE) {
780       output = 'O-O';
781     } else if (move.flags & BITS.QSIDE_CASTLE) {
782       output = 'O-O-O';
783     } else {
784       var disambiguator = get_disambiguator(move, sloppy);
785
786       if (move.piece !== PAWN) {
787         output += move.piece.toUpperCase() + disambiguator;
788       }
789
790       if (move.flags & (BITS.CAPTURE | BITS.EP_CAPTURE)) {
791         if (move.piece === PAWN) {
792           output += algebraic(move.from)[0];
793         }
794         output += 'x';
795       }
796
797       output += algebraic(move.to);
798
799       if (move.flags & BITS.PROMOTION) {
800         output += '=' + move.promotion.toUpperCase();
801       }
802     }
803
804     make_move(move);
805     if (in_check()) {
806       if (in_checkmate()) {
807         output += '#';
808       } else {
809         output += '+';
810       }
811     }
812     undo_move();
813
814     return output;
815   }
816
817   // parses all of the decorators out of a SAN string
818   function stripped_san(move) {
819     return move.replace(/=/,'').replace(/[+#]?[?!]*$/,'');
820   }
821
822   function attacked(color, square) {
823     for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
824       /* did we run off the end of the board */
825       if (i & 0x88) { i += 7; continue; }
826
827       /* if empty square or wrong color */
828       if (board[i] == null || board[i].color !== color) continue;
829
830       var piece = board[i];
831       var difference = i - square;
832       var index = difference + 119;
833
834       if (ATTACKS[index] & (1 << SHIFTS[piece.type])) {
835         if (piece.type === PAWN) {
836           if (difference > 0) {
837             if (piece.color === WHITE) return true;
838           } else {
839             if (piece.color === BLACK) return true;
840           }
841           continue;
842         }
843
844         /* if the piece is a knight or a king */
845         if (piece.type === 'n' || piece.type === 'k') return true;
846
847         var offset = RAYS[index];
848         var j = i + offset;
849
850         var blocked = false;
851         while (j !== square) {
852           if (board[j] != null) { blocked = true; break; }
853           j += offset;
854         }
855
856         if (!blocked) return true;
857       }
858     }
859
860     return false;
861   }
862
863   function king_attacked(color) {
864     return attacked(swap_color(color), kings[color]);
865   }
866
867   function in_check() {
868     return king_attacked(turn);
869   }
870
871   function in_checkmate() {
872     return in_check() && generate_moves().length === 0;
873   }
874
875   function in_stalemate() {
876     return !in_check() && generate_moves().length === 0;
877   }
878
879   function insufficient_material() {
880     var pieces = {};
881     var bishops = [];
882     var num_pieces = 0;
883     var sq_color = 0;
884
885     for (var i = SQUARES.a8; i<= SQUARES.h1; i++) {
886       sq_color = (sq_color + 1) % 2;
887       if (i & 0x88) { i += 7; continue; }
888
889       var piece = board[i];
890       if (piece) {
891         pieces[piece.type] = (piece.type in pieces) ?
892                               pieces[piece.type] + 1 : 1;
893         if (piece.type === BISHOP) {
894           bishops.push(sq_color);
895         }
896         num_pieces++;
897       }
898     }
899
900     /* k vs. k */
901     if (num_pieces === 2) { return true; }
902
903     /* k vs. kn .... or .... k vs. kb */
904     else if (num_pieces === 3 && (pieces[BISHOP] === 1 ||
905                                  pieces[KNIGHT] === 1)) { return true; }
906
907     /* kb vs. kb where any number of bishops are all on the same color */
908     else if (num_pieces === pieces[BISHOP] + 2) {
909       var sum = 0;
910       var len = bishops.length;
911       for (var i = 0; i < len; i++) {
912         sum += bishops[i];
913       }
914       if (sum === 0 || sum === len) { return true; }
915     }
916
917     return false;
918   }
919
920   function in_threefold_repetition() {
921     /* TODO: while this function is fine for casual use, a better
922      * implementation would use a Zobrist key (instead of FEN). the
923      * Zobrist key would be maintained in the make_move/undo_move functions,
924      * avoiding the costly that we do below.
925      */
926     var moves = [];
927     var positions = {};
928     var repetition = false;
929
930     while (true) {
931       var move = undo_move();
932       if (!move) break;
933       moves.push(move);
934     }
935
936     while (true) {
937       /* remove the last two fields in the FEN string, they're not needed
938        * when checking for draw by rep */
939       var fen = generate_fen().split(' ').slice(0,4).join(' ');
940
941       /* has the position occurred three or move times */
942       positions[fen] = (fen in positions) ? positions[fen] + 1 : 1;
943       if (positions[fen] >= 3) {
944         repetition = true;
945       }
946
947       if (!moves.length) {
948         break;
949       }
950       make_move(moves.pop());
951     }
952
953     return repetition;
954   }
955
956   function push(move) {
957     history.push({
958       move: move,
959       kings: {b: kings.b, w: kings.w},
960       turn: turn,
961       castling: {b: castling.b, w: castling.w},
962       ep_square: ep_square,
963       half_moves: half_moves,
964       move_number: move_number
965     });
966   }
967
968   function make_move(move) {
969     var us = turn;
970     var them = swap_color(us);
971     var old_to = board[move.to];
972     push(move);
973
974     board[move.to] = board[move.from];
975     board[move.from] = null;
976
977     /* if ep capture, remove the captured pawn */
978     if (move.flags & BITS.EP_CAPTURE) {
979       if (turn === BLACK) {
980         board[move.to - 16] = null;
981       } else {
982         board[move.to + 16] = null;
983       }
984     }
985
986     /* if pawn promotion, replace with new piece */
987     if (move.flags & BITS.PROMOTION) {
988       board[move.to] = {type: move.promotion, color: us};
989     }
990
991     /* if we moved the king */
992     if (board[move.to].type === KING) {
993       kings[board[move.to].color] = move.to;
994
995       /* if we castled, move the rook next to the king */
996       if (move.flags & BITS.KSIDE_CASTLE) {
997         var castling_to = move.to - 1;
998         var castling_from = move.rook_sq;
999         board[castling_to] = old_to===null ? board[castling_from] : old_to;
1000         if(castling_from !== move.to)
1001           board[castling_from] = null;
1002       } else if (move.flags & BITS.QSIDE_CASTLE) {
1003         var castling_to = move.to + 1;
1004         var castling_from = move.rook_sq;
1005         board[castling_to] = old_to===null ? board[castling_from] : old_to;
1006         if(castling_from !== move.to)
1007           board[castling_from] = null;
1008       }
1009
1010       /* turn off castling */
1011       castling[us] = '';
1012     }
1013
1014     /* turn off castling if we move a rook */
1015     if (castling[us]) {
1016       for (var i = 0, len = rooks[us].length; i < len; i++) {
1017         if (move.from === rooks[us][i].square &&
1018             castling[us] & rooks[us][i].flag) {
1019           castling[us] ^= rooks[us][i].flag;
1020           break;
1021         }
1022       }
1023     }
1024
1025     /* turn off castling if we capture a rook */
1026     if (castling[them]) {
1027       for (var i = 0, len = rooks[them].length; i < len; i++) {
1028         if (move.to === rooks[them][i].square &&
1029             castling[them] & rooks[them][i].flag) {
1030           castling[them] ^= rooks[them][i].flag;
1031           break;
1032         }
1033       }
1034     }
1035
1036     /* if big pawn move, update the en passant square */
1037     if (move.flags & BITS.BIG_PAWN) {
1038       if (turn === 'b') {
1039         ep_square = move.to - 16;
1040       } else {
1041         ep_square = move.to + 16;
1042       }
1043     } else {
1044       ep_square = EMPTY;
1045     }
1046
1047     /* reset the 50 move counter if a pawn is moved or a piece is captured */
1048     if (move.piece === PAWN) {
1049       half_moves = 0;
1050     } else if (move.flags & (BITS.CAPTURE | BITS.EP_CAPTURE)) {
1051       half_moves = 0;
1052     } else {
1053       half_moves++;
1054     }
1055
1056     if (turn === BLACK) {
1057       move_number++;
1058     }
1059     turn = swap_color(turn);
1060   }
1061
1062   function undo_move() {
1063     var old = history.pop();
1064     if (old == null) { return null; }
1065
1066     var move = old.move;
1067     kings = old.kings;
1068     turn = old.turn;
1069     castling = old.castling;
1070     ep_square = old.ep_square;
1071     half_moves = old.half_moves;
1072     move_number = old.move_number;
1073
1074     var us = turn;
1075     var them = swap_color(turn);
1076
1077     var old_from = board[move.from];
1078
1079     board[move.from] = board[move.to];
1080     board[move.from].type = move.piece;  // to undo any promotions
1081     board[move.to] = null;
1082
1083     if (move.flags & BITS.CAPTURE) {
1084       board[move.to] = {type: move.captured, color: them};
1085     } else if (move.flags & BITS.EP_CAPTURE) {
1086       var index;
1087       if (us === BLACK) {
1088         index = move.to - 16;
1089       } else {
1090         index = move.to + 16;
1091       }
1092       board[index] = {type: PAWN, color: them};
1093     }
1094
1095
1096     if (move.flags & (BITS.KSIDE_CASTLE | BITS.QSIDE_CASTLE)) {
1097       var castling_to, castling_from;
1098       if (move.flags & BITS.KSIDE_CASTLE) {
1099         castling_to = move.rook_sq;
1100         castling_from = move.to - 1;
1101       } else if (move.flags & BITS.QSIDE_CASTLE) {
1102         castling_to = move.rook_sq;
1103         castling_from = move.to + 1;
1104       }
1105
1106       board[castling_to] = old_from===null ? board[castling_from] : old_from;
1107       if(castling_from !== move.from)
1108         board[castling_from] = null;
1109     }
1110
1111     return move;
1112   }
1113
1114   /* this function is used to uniquely identify ambiguous moves */
1115   function get_disambiguator(move, sloppy) {
1116     var moves = generate_moves({legal: !sloppy});
1117
1118     var from = move.from;
1119     var to = move.to;
1120     var piece = move.piece;
1121
1122     var ambiguities = 0;
1123     var same_rank = 0;
1124     var same_file = 0;
1125
1126     for (var i = 0, len = moves.length; i < len; i++) {
1127       var ambig_from = moves[i].from;
1128       var ambig_to = moves[i].to;
1129       var ambig_piece = moves[i].piece;
1130
1131       /* if a move of the same piece type ends on the same to square, we'll
1132        * need to add a disambiguator to the algebraic notation
1133        */
1134       if (piece === ambig_piece && from !== ambig_from && to === ambig_to) {
1135         ambiguities++;
1136
1137         if (rank(from) === rank(ambig_from)) {
1138           same_rank++;
1139         }
1140
1141         if (file(from) === file(ambig_from)) {
1142           same_file++;
1143         }
1144       }
1145     }
1146
1147     if (ambiguities > 0) {
1148       /* if there exists a similar moving piece on the same rank and file as
1149        * the move in question, use the square as the disambiguator
1150        */
1151       if (same_rank > 0 && same_file > 0) {
1152         return algebraic(from);
1153       }
1154       /* if the moving piece rests on the same file, use the rank symbol as the
1155        * disambiguator
1156        */
1157       else if (same_file > 0) {
1158         return algebraic(from).charAt(1);
1159       }
1160       /* else use the file symbol */
1161       else {
1162         return algebraic(from).charAt(0);
1163       }
1164     }
1165
1166     return '';
1167   }
1168
1169   function ascii() {
1170     var s = '   +------------------------+\n';
1171     for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
1172       /* display the rank */
1173       if (file(i) === 0) {
1174         s += ' ' + '87654321'[rank(i)] + ' |';
1175       }
1176
1177       /* empty piece */
1178       if (board[i] == null) {
1179         s += ' . ';
1180       } else {
1181         var piece = board[i].type;
1182         var color = board[i].color;
1183         var symbol = (color === WHITE) ?
1184                      piece.toUpperCase() : piece.toLowerCase();
1185         s += ' ' + symbol + ' ';
1186       }
1187
1188       if ((i + 1) & 0x88) {
1189         s += '|\n';
1190         i += 8;
1191       }
1192     }
1193     s += '   +------------------------+\n';
1194     s += '     a  b  c  d  e  f  g  h\n';
1195
1196     return s;
1197   }
1198
1199   // convert a move from Standard Algebraic Notation (SAN) to 0x88 coordinates
1200   function move_from_san(move, sloppy) {
1201     // strip off any move decorations: e.g Nf3+?!
1202     var clean_move = stripped_san(move);
1203
1204     // if we're using the sloppy parser run a regex to grab piece, to, and from
1205     // this should parse invalid SAN like: Pe2-e4, Rc1c4, Qf3xf7
1206     if (sloppy) {
1207       var matches = clean_move.match(/([pnbrqkPNBRQK])?([a-h][1-8])x?-?([a-h][1-8])([qrbnQRBN])?/);
1208       if (matches) {
1209         var piece = matches[1];
1210         var from = matches[2];
1211         var to = matches[3];
1212         var promotion = matches[4];
1213       }
1214     }
1215
1216     var moves = generate_moves();
1217     for (var i = 0, len = moves.length; i < len; i++) {
1218       // try the strict parser first, then the sloppy parser if requested
1219       // by the user
1220       if ((clean_move === stripped_san(move_to_san(moves[i]))) ||
1221           (sloppy && clean_move === stripped_san(move_to_san(moves[i], true)))) {
1222         return moves[i];
1223       } else {
1224         if (matches &&
1225             (!piece || piece.toLowerCase() == moves[i].piece) &&
1226             SQUARES[from] == moves[i].from &&
1227             SQUARES[to] == moves[i].to &&
1228             (!promotion || promotion.toLowerCase() == moves[i].promotion)) {
1229           return moves[i];
1230         }
1231       }
1232     }
1233
1234     return null;
1235   }
1236
1237
1238   /*****************************************************************************
1239    * UTILITY FUNCTIONS
1240    ****************************************************************************/
1241   function rank(i) {
1242     return i >> 4;
1243   }
1244
1245   function file(i) {
1246     return i & 15;
1247   }
1248
1249   function algebraic(i){
1250     var f = file(i), r = rank(i);
1251     return 'abcdefgh'.substring(f,f+1) + '87654321'.substring(r,r+1);
1252   }
1253
1254   function swap_color(c) {
1255     return c === WHITE ? BLACK : WHITE;
1256   }
1257
1258   function is_digit(c) {
1259     return '0123456789'.indexOf(c) !== -1;
1260   }
1261
1262   /* pretty = external move object */
1263   function make_pretty(ugly_move) {
1264     var move = clone(ugly_move);
1265     move.san = move_to_san(move, false);
1266     move.to = algebraic(move.to);
1267     move.from = algebraic(move.from);
1268
1269     var flags = '';
1270
1271     for (var flag in BITS) {
1272       if (BITS[flag] & move.flags) {
1273         flags += FLAGS[flag];
1274       }
1275     }
1276     move.flags = flags;
1277
1278     return move;
1279   }
1280
1281   function clone(obj) {
1282     var dupe = (obj instanceof Array) ? [] : {};
1283
1284     for (var property in obj) {
1285       if (typeof property === 'object') {
1286         dupe[property] = clone(obj[property]);
1287       } else {
1288         dupe[property] = obj[property];
1289       }
1290     }
1291
1292     return dupe;
1293   }
1294
1295   function trim(str) {
1296     return str.replace(/^\s+|\s+$/g, '');
1297   }
1298
1299   /*****************************************************************************
1300    * DEBUGGING UTILITIES
1301    ****************************************************************************/
1302   function perft(depth) {
1303     var moves = generate_moves({legal: false});
1304     var nodes = 0;
1305     var color = turn;
1306
1307     for (var i = 0, len = moves.length; i < len; i++) {
1308       make_move(moves[i]);
1309       if (!king_attacked(color)) {
1310         if (depth - 1 > 0) {
1311           var child_nodes = perft(depth - 1);
1312           nodes += child_nodes;
1313         } else {
1314           nodes++;
1315         }
1316       }
1317       undo_move();
1318     }
1319
1320     return nodes;
1321   }
1322
1323   return {
1324     /***************************************************************************
1325      * PUBLIC CONSTANTS (is there a better way to do this?)
1326      **************************************************************************/
1327     WHITE: WHITE,
1328     BLACK: BLACK,
1329     PAWN: PAWN,
1330     KNIGHT: KNIGHT,
1331     BISHOP: BISHOP,
1332     ROOK: ROOK,
1333     QUEEN: QUEEN,
1334     KING: KING,
1335     SQUARES: (function() {
1336                 /* from the ECMA-262 spec (section 12.6.4):
1337                  * "The mechanics of enumerating the properties ... is
1338                  * implementation dependent"
1339                  * so: for (var sq in SQUARES) { keys.push(sq); } might not be
1340                  * ordered correctly
1341                  */
1342                 var keys = [];
1343                 for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
1344                   if (i & 0x88) { i += 7; continue; }
1345                   keys.push(algebraic(i));
1346                 }
1347                 return keys;
1348               })(),
1349     FLAGS: FLAGS,
1350
1351     /***************************************************************************
1352      * PUBLIC API
1353      **************************************************************************/
1354     load: function(fen) {
1355       return load(fen);
1356     },
1357
1358     reset: function() {
1359       return reset();
1360     },
1361
1362     moves: function(options) {
1363       /* The internal representation of a chess move is in 0x88 format, and
1364        * not meant to be human-readable.  The code below converts the 0x88
1365        * square coordinates to algebraic coordinates.  It also prunes an
1366        * unnecessary move keys resulting from a verbose call.
1367        */
1368
1369       var ugly_moves = generate_moves(options);
1370       var moves = [];
1371
1372       for (var i = 0, len = ugly_moves.length; i < len; i++) {
1373
1374         /* does the user want a full move object (most likely not), or just
1375          * SAN
1376          */
1377         if (typeof options !== 'undefined' && 'verbose' in options &&
1378             options.verbose) {
1379           moves.push(make_pretty(ugly_moves[i]));
1380         } else {
1381           moves.push(move_to_san(ugly_moves[i], false));
1382         }
1383       }
1384
1385       return moves;
1386     },
1387
1388     in_check: function() {
1389       return in_check();
1390     },
1391
1392     in_checkmate: function() {
1393       return in_checkmate();
1394     },
1395
1396     in_stalemate: function() {
1397       return in_stalemate();
1398     },
1399
1400     in_draw: function() {
1401       return half_moves >= 100 ||
1402              in_stalemate() ||
1403              insufficient_material() ||
1404              in_threefold_repetition();
1405     },
1406
1407     insufficient_material: function() {
1408       return insufficient_material();
1409     },
1410
1411     in_threefold_repetition: function() {
1412       return in_threefold_repetition();
1413     },
1414
1415     game_over: function() {
1416       return half_moves >= 100 ||
1417              in_checkmate() ||
1418              in_stalemate() ||
1419              insufficient_material() ||
1420              in_threefold_repetition();
1421     },
1422
1423     validate_fen: function(fen) {
1424       return validate_fen(fen);
1425     },
1426
1427     fen: function() {
1428       return generate_fen();
1429     },
1430
1431     board: function() {
1432       var output = [],
1433           row    = [];
1434
1435       for (var i = SQUARES.a8; i <= SQUARES.h1; i++) {
1436         if (board[i] == null) {
1437           row.push(null)
1438         } else {
1439           row.push({type: board[i].type, color: board[i].color})
1440         }
1441         if ((i + 1) & 0x88) {
1442           output.push(row);
1443           row = []
1444           i += 8;
1445         }
1446       }
1447
1448       return output;
1449     },
1450
1451     pgn: function(options) {
1452       /* using the specification from http://www.chessclub.com/help/PGN-spec
1453        * example for html usage: .pgn({ max_width: 72, newline_char: "<br />" })
1454        */
1455       var newline = (typeof options === 'object' &&
1456                      typeof options.newline_char === 'string') ?
1457                      options.newline_char : '\n';
1458       var max_width = (typeof options === 'object' &&
1459                        typeof options.max_width === 'number') ?
1460                        options.max_width : 0;
1461       var result = [];
1462       var header_exists = false;
1463
1464       /* add the PGN header headerrmation */
1465       for (var i in header) {
1466         /* TODO: order of enumerated properties in header object is not
1467          * guaranteed, see ECMA-262 spec (section 12.6.4)
1468          */
1469         result.push('[' + i + ' \"' + header[i] + '\"]' + newline);
1470         header_exists = true;
1471       }
1472
1473       if (header_exists && history.length) {
1474         result.push(newline);
1475       }
1476
1477       /* pop all of history onto reversed_history */
1478       var reversed_history = [];
1479       while (history.length > 0) {
1480         reversed_history.push(undo_move());
1481       }
1482
1483       var moves = [];
1484       var move_string = '';
1485
1486       /* build the list of moves.  a move_string looks like: "3. e3 e6" */
1487       while (reversed_history.length > 0) {
1488         var move = reversed_history.pop();
1489
1490         /* if the position started with black to move, start PGN with 1. ... */
1491         if (!history.length && move.color === 'b') {
1492           move_string = move_number + '. ...';
1493         } else if (move.color === 'w') {
1494           /* store the previous generated move_string if we have one */
1495           if (move_string.length) {
1496             moves.push(move_string);
1497           }
1498           move_string = move_number + '.';
1499         }
1500
1501         move_string = move_string + ' ' + move_to_san(move, false);
1502         make_move(move);
1503       }
1504
1505       /* are there any other leftover moves? */
1506       if (move_string.length) {
1507         moves.push(move_string);
1508       }
1509
1510       /* is there a result? */
1511       if (typeof header.Result !== 'undefined') {
1512         moves.push(header.Result);
1513       }
1514
1515       /* history should be back to what is was before we started generating PGN,
1516        * so join together moves
1517        */
1518       if (max_width === 0) {
1519         return result.join('') + moves.join(' ');
1520       }
1521
1522       /* wrap the PGN output at max_width */
1523       var current_width = 0;
1524       for (var i = 0; i < moves.length; i++) {
1525         /* if the current move will push past max_width */
1526         if (current_width + moves[i].length > max_width && i !== 0) {
1527
1528           /* don't end the line with whitespace */
1529           if (result[result.length - 1] === ' ') {
1530             result.pop();
1531           }
1532
1533           result.push(newline);
1534           current_width = 0;
1535         } else if (i !== 0) {
1536           result.push(' ');
1537           current_width++;
1538         }
1539         result.push(moves[i]);
1540         current_width += moves[i].length;
1541       }
1542
1543       return result.join('');
1544     },
1545
1546     load_pgn: function(pgn, options) {
1547       // allow the user to specify the sloppy move parser to work around over
1548       // disambiguation bugs in Fritz and Chessbase
1549       var sloppy = (typeof options !== 'undefined' && 'sloppy' in options) ?
1550                     options.sloppy : false;
1551
1552       function mask(str) {
1553         return str.replace(/\\/g, '\\');
1554       }
1555
1556       function has_keys(object) {
1557         for (var key in object) {
1558           return true;
1559         }
1560         return false;
1561       }
1562
1563       function parse_pgn_header(header, options) {
1564         var newline_char = (typeof options === 'object' &&
1565                             typeof options.newline_char === 'string') ?
1566                             options.newline_char : '\r?\n';
1567         var header_obj = {};
1568         var headers = header.split(new RegExp(mask(newline_char)));
1569         var key = '';
1570         var value = '';
1571
1572         for (var i = 0; i < headers.length; i++) {
1573           key = headers[i].replace(/^\[([A-Z][A-Za-z]*)\s.*\]$/, '$1');
1574           value = headers[i].replace(/^\[[A-Za-z]+\s"(.*)"\]$/, '$1');
1575           if (trim(key).length > 0) {
1576             header_obj[key] = value;
1577           }
1578         }
1579
1580         return header_obj;
1581       }
1582
1583       var newline_char = (typeof options === 'object' &&
1584                           typeof options.newline_char === 'string') ?
1585                           options.newline_char : '\r?\n';
1586       var regex = new RegExp('^(\\[(.|' + mask(newline_char) + ')*\\])' +
1587                              '(' + mask(newline_char) + ')*' +
1588                              '1.(' + mask(newline_char) + '|.)*$', 'g');
1589
1590       /* get header part of the PGN file */
1591       var header_string = pgn.replace(regex, '$1');
1592
1593       /* no info part given, begins with moves */
1594       if (header_string[0] !== '[') {
1595         header_string = '';
1596       }
1597
1598       reset();
1599
1600       /* parse PGN header */
1601       var headers = parse_pgn_header(header_string, options);
1602       for (var key in headers) {
1603         set_header([key, headers[key]]);
1604       }
1605
1606       /* load the starting position indicated by [Setup '1'] and
1607       * [FEN position] */
1608       if (headers['SetUp'] === '1') {
1609           if (!(('FEN' in headers) && load(headers['FEN'], true ))) { // second argument to load: don't clear the headers
1610             return false;
1611           }
1612       }
1613
1614       /* delete header to get the moves */
1615       var ms = pgn.replace(header_string, '').replace(new RegExp(mask(newline_char), 'g'), ' ');
1616
1617       /* delete comments */
1618       ms = ms.replace(/(\{[^}]+\})+?/g, '');
1619
1620       /* delete recursive annotation variations */
1621       var rav_regex = /(\([^\(\)]+\))+?/g
1622       while (rav_regex.test(ms)) {
1623         ms = ms.replace(rav_regex, '');
1624       }
1625
1626       /* delete move numbers */
1627       ms = ms.replace(/\d+\.(\.\.)?/g, '');
1628
1629       /* delete ... indicating black to move */
1630       ms = ms.replace(/\.\.\./g, '');
1631
1632       /* delete numeric annotation glyphs */
1633       ms = ms.replace(/\$\d+/g, '');
1634
1635       /* trim and get array of moves */
1636       var moves = trim(ms).split(new RegExp(/\s+/));
1637
1638       /* delete empty entries */
1639       moves = moves.join(',').replace(/,,+/g, ',').split(',');
1640       var move = '';
1641
1642       for (var half_move = 0; half_move < moves.length - 1; half_move++) {
1643         move = move_from_san(moves[half_move], sloppy);
1644
1645         /* move not possible! (don't clear the board to examine to show the
1646          * latest valid position)
1647          */
1648         if (move == null) {
1649           return false;
1650         } else {
1651           make_move(move);
1652         }
1653       }
1654
1655       /* examine last move */
1656       move = moves[moves.length - 1];
1657       if (POSSIBLE_RESULTS.indexOf(move) > -1) {
1658         if (has_keys(header) && typeof header.Result === 'undefined') {
1659           set_header(['Result', move]);
1660         }
1661       }
1662       else {
1663         move = move_from_san(move, sloppy);
1664         if (move == null) {
1665           return false;
1666         } else {
1667           make_move(move);
1668         }
1669       }
1670       return true;
1671     },
1672
1673     header: function() {
1674       return set_header(arguments);
1675     },
1676
1677     ascii: function() {
1678       return ascii();
1679     },
1680
1681     turn: function() {
1682       return turn;
1683     },
1684
1685     move: function(move, options) {
1686       /* The move function can be called with in the following parameters:
1687        *
1688        * .move('Nxb7')      <- where 'move' is a case-sensitive SAN string
1689        *
1690        * .move({ from: 'h7', <- where the 'move' is a move object (additional
1691        *         to :'h8',      fields are ignored)
1692        *         promotion: 'q',
1693        *      })
1694        */
1695
1696       // allow the user to specify the sloppy move parser to work around over
1697       // disambiguation bugs in Fritz and Chessbase
1698       var sloppy = (typeof options !== 'undefined' && 'sloppy' in options) ?
1699                     options.sloppy : false;
1700
1701       var move_obj = null;
1702
1703       if (typeof move === 'string') {
1704         move_obj = move_from_san(move, sloppy);
1705       } else if (typeof move === 'object') {
1706         var moves = generate_moves();
1707
1708         /* convert the pretty move object to an ugly move object */
1709         for (var i = 0, len = moves.length; i < len; i++) {
1710           if (move.from === algebraic(moves[i].from) &&
1711               move.to === algebraic(moves[i].to) &&
1712               (!('promotion' in moves[i]) ||
1713               move.promotion === moves[i].promotion)) {
1714             move_obj = moves[i];
1715             break;
1716           }
1717         }
1718       }
1719
1720       /* failed to find move */
1721       if (!move_obj) {
1722         return null;
1723       }
1724
1725       /* need to make a copy of move because we can't generate SAN after the
1726        * move is made
1727        */
1728       var pretty_move = make_pretty(move_obj);
1729
1730       make_move(move_obj);
1731
1732       return pretty_move;
1733     },
1734
1735     undo: function() {
1736       var move = undo_move();
1737       return (move) ? make_pretty(move) : null;
1738     },
1739
1740     clear: function() {
1741       return clear();
1742     },
1743
1744     put: function(piece, square) {
1745       return put(piece, square);
1746     },
1747
1748     get: function(square) {
1749       return get(square);
1750     },
1751
1752     remove: function(square) {
1753       return remove(square);
1754     },
1755
1756     perft: function(depth) {
1757       return perft(depth);
1758     },
1759
1760     square_color: function(square) {
1761       if (square in SQUARES) {
1762         var sq_0x88 = SQUARES[square];
1763         return ((rank(sq_0x88) + file(sq_0x88)) % 2 === 0) ? 'light' : 'dark';
1764       }
1765
1766       return null;
1767     },
1768
1769     history: function(options) {
1770       var reversed_history = [];
1771       var move_history = [];
1772       var verbose = (typeof options !== 'undefined' && 'verbose' in options &&
1773                      options.verbose);
1774
1775       while (history.length > 0) {
1776         reversed_history.push(undo_move());
1777       }
1778
1779       while (reversed_history.length > 0) {
1780         var move = reversed_history.pop();
1781         if (verbose) {
1782           move_history.push(make_pretty(move));
1783         } else {
1784           move_history.push(move_to_san(move));
1785         }
1786         make_move(move);
1787       }
1788
1789       return move_history;
1790     }
1791
1792   };
1793 };
1794
1795 /* export Chess object if using node or any other CommonJS compatible
1796  * environment */
1797 if (typeof exports !== 'undefined') exports.Chess = Chess;
1798 /* export Chess object for any RequireJS compatible environment */
1799 if (typeof define !== 'undefined') define( function () { return Chess;  });