8f875e4f918d727d99a2e5e404c30703bc5f5f3b
[vchess.git] / public / javascripts / base_rules.js
1 // (Orthodox) Chess rules are defined in ChessRules class.
2 // Variants generally inherit from it, and modify some parts.
3
4 class PiPo //Piece+Position
5 {
6 // o: {piece[p], color[c], posX[x], posY[y]}
7 constructor(o)
8 {
9 this.p = o.p;
10 this.c = o.c;
11 this.x = o.x;
12 this.y = o.y;
13 }
14 }
15
16 // TODO: for animation, moves should contains "moving" and "fading" maybe...
17 class Move
18 {
19 // o: {appear, vanish, [start,] [end,]}
20 // appear,vanish = arrays of PiPo
21 // start,end = coordinates to apply to trigger move visually (think castle)
22 constructor(o)
23 {
24 this.appear = o.appear;
25 this.vanish = o.vanish;
26 this.start = !!o.start ? o.start : {x:o.vanish[0].x, y:o.vanish[0].y};
27 this.end = !!o.end ? o.end : {x:o.appear[0].x, y:o.appear[0].y};
28 }
29 }
30
31 // NOTE: x coords = top to bottom; y = left to right (from white player perspective)
32 class ChessRules
33 {
34 //////////////
35 // MISC UTILS
36
37 static get HasFlags() { return true; } //some variants don't have flags
38
39 static get HasEnpassant() { return true; } //some variants don't have ep.
40
41 // Path to pieces
42 static getPpath(b)
43 {
44 return b; //usual pieces in pieces/ folder
45 }
46
47 // Turn "wb" into "B" (for FEN)
48 static board2fen(b)
49 {
50 return b[0]=='w' ? b[1].toUpperCase() : b[1];
51 }
52
53 // Turn "p" into "bp" (for board)
54 static fen2board(f)
55 {
56 return f.charCodeAt()<=90 ? "w"+f.toLowerCase() : "b"+f;
57 }
58
59 // Check if FEN describe a position
60 static IsGoodFen(fen)
61 {
62 const fenParsed = V.ParseFen(fen);
63 // 1) Check position
64 if (!V.IsGoodPosition(fenParsed.position))
65 return false;
66 // 2) Check turn
67 if (!fenParsed.turn || !V.IsGoodTurn(fenParsed.turn))
68 return false;
69 // 3) Check flags
70 if (V.HasFlags && (!fenParsed.flags || !V.IsGoodFlags(fenParsed.flags)))
71 return false;
72 // 4) Check enpassant
73 if (V.HasEnpassant &&
74 (!fenParsed.enpassant || !V.IsGoodEnpassant(fenParsed.enpassant)))
75 {
76 return false;
77 }
78 return true;
79 }
80
81 // Is position part of the FEN a priori correct?
82 static IsGoodPosition(position)
83 {
84 if (position.length == 0)
85 return false;
86 const rows = position.split("/");
87 if (rows.length != V.size.x)
88 return false;
89 for (let row of rows)
90 {
91 let sumElts = 0;
92 for (let i=0; i<row.length; i++)
93 {
94 if (V.PIECES.includes(row[i].toLowerCase()))
95 sumElts++;
96 else
97 {
98 const num = parseInt(row[i]);
99 if (isNaN(num))
100 return false;
101 sumElts += num;
102 }
103 }
104 if (sumElts != V.size.y)
105 return false;
106 }
107 return true;
108 }
109
110 // For FEN checking
111 static IsGoodTurn(turn)
112 {
113 return ["w","b"].includes(turn);
114 }
115
116 // For FEN checking
117 static IsGoodFlags(flags)
118 {
119 return !!flags.match(/^[01]{4,4}$/);
120 }
121
122 static IsGoodEnpassant(enpassant)
123 {
124 if (enpassant != "-")
125 {
126 const ep = V.SquareToCoords(fenParsed.enpassant);
127 if (isNaN(ep.x) || !V.OnBoard(ep))
128 return false;
129 }
130 return true;
131 }
132
133 // 3 --> d (column number to letter)
134 static CoordToColumn(colnum)
135 {
136 return String.fromCharCode(97 + colnum);
137 }
138
139 // d --> 3 (column letter to number)
140 static ColumnToCoord(column)
141 {
142 return column.charCodeAt(0) - 97;
143 }
144
145 // a4 --> {x:3,y:0}
146 static SquareToCoords(sq)
147 {
148 return {
149 // NOTE: column is always one char => max 26 columns
150 // row is counted from black side => subtraction
151 x: V.size.x - parseInt(sq.substr(1)),
152 y: sq[0].charCodeAt() - 97
153 };
154 }
155
156 // {x:0,y:4} --> e8
157 static CoordsToSquare(coords)
158 {
159 return V.CoordToColumn(coords.y) + (V.size.x - coords.x);
160 }
161
162 // Aggregates flags into one object
163 aggregateFlags()
164 {
165 return this.castleFlags;
166 }
167
168 // Reverse operation
169 disaggregateFlags(flags)
170 {
171 this.castleFlags = flags;
172 }
173
174 // En-passant square, if any
175 getEpSquare(moveOrSquare)
176 {
177 if (!moveOrSquare)
178 return undefined;
179 if (typeof moveOrSquare === "string")
180 {
181 const square = moveOrSquare;
182 if (square == "-")
183 return undefined;
184 return V.SquareToCoords(square);
185 }
186 // Argument is a move:
187 const move = moveOrSquare;
188 const [sx,sy,ex] = [move.start.x,move.start.y,move.end.x];
189 // TODO: next conditions are first for Atomic, and third for Checkered
190 if (move.appear.length > 0 && move.appear[0].p == V.PAWN && ["w","b"].includes(move.appear[0].c) && Math.abs(sx - ex) == 2)
191 {
192 return {
193 x: (sx + ex)/2,
194 y: sy
195 };
196 }
197 return undefined; //default
198 }
199
200 // Can thing on square1 take thing on square2
201 canTake([x1,y1], [x2,y2])
202 {
203 return this.getColor(x1,y1) !== this.getColor(x2,y2);
204 }
205
206 // Is (x,y) on the chessboard?
207 static OnBoard(x,y)
208 {
209 return (x>=0 && x<V.size.x && y>=0 && y<V.size.y);
210 }
211
212 // Used in interface: 'side' arg == player color
213 canIplay(side, [x,y])
214 {
215 return (this.turn == side && this.getColor(x,y) == side);
216 }
217
218 // On which squares is color under check ? (for interface)
219 getCheckSquares(color)
220 {
221 return this.isAttacked(this.kingPos[color], [this.getOppCol(color)])
222 ? [JSON.parse(JSON.stringify(this.kingPos[color]))] //need to duplicate!
223 : [];
224 }
225
226 /////////////
227 // FEN UTILS
228
229 // Setup the initial random (assymetric) position
230 static GenRandInitFen()
231 {
232 let pieces = { "w": new Array(8), "b": new Array(8) };
233 // Shuffle pieces on first and last rank
234 for (let c of ["w","b"])
235 {
236 let positions = _.range(8);
237
238 // Get random squares for bishops
239 let randIndex = 2 * _.random(3);
240 const bishop1Pos = positions[randIndex];
241 // The second bishop must be on a square of different color
242 let randIndex_tmp = 2 * _.random(3) + 1;
243 const bishop2Pos = positions[randIndex_tmp];
244 // Remove chosen squares
245 positions.splice(Math.max(randIndex,randIndex_tmp), 1);
246 positions.splice(Math.min(randIndex,randIndex_tmp), 1);
247
248 // Get random squares for knights
249 randIndex = _.random(5);
250 const knight1Pos = positions[randIndex];
251 positions.splice(randIndex, 1);
252 randIndex = _.random(4);
253 const knight2Pos = positions[randIndex];
254 positions.splice(randIndex, 1);
255
256 // Get random square for queen
257 randIndex = _.random(3);
258 const queenPos = positions[randIndex];
259 positions.splice(randIndex, 1);
260
261 // Rooks and king positions are now fixed,
262 // because of the ordering rook-king-rook
263 const rook1Pos = positions[0];
264 const kingPos = positions[1];
265 const rook2Pos = positions[2];
266
267 // Finally put the shuffled pieces in the board array
268 pieces[c][rook1Pos] = 'r';
269 pieces[c][knight1Pos] = 'n';
270 pieces[c][bishop1Pos] = 'b';
271 pieces[c][queenPos] = 'q';
272 pieces[c][kingPos] = 'k';
273 pieces[c][bishop2Pos] = 'b';
274 pieces[c][knight2Pos] = 'n';
275 pieces[c][rook2Pos] = 'r';
276 }
277 return pieces["b"].join("") +
278 "/pppppppp/8/8/8/8/PPPPPPPP/" +
279 pieces["w"].join("").toUpperCase() +
280 " w 1111 -"; //add turn + flags + enpassant
281 }
282
283 // "Parse" FEN: just return untransformed string data
284 static ParseFen(fen)
285 {
286 const fenParts = fen.split(" ");
287 let res =
288 {
289 position: fenParts[0],
290 turn: fenParts[1],
291 };
292 let nextIdx = 2;
293 if (V.HasFlags)
294 Object.assign(res, {flags: fenParts[nextIdx++]});
295 if (V.HasEnpassant)
296 Object.assign(res, {enpassant: fenParts[nextIdx]});
297 return res;
298 }
299
300 // Return current fen (game state)
301 getFen()
302 {
303 return this.getBaseFen() + " " + this.getTurnFen() +
304 (V.HasFlags ? (" " + this.getFlagsFen()) : "") +
305 (V.HasEnpassant ? (" " + this.getEnpassantFen()) : "");
306 }
307
308 // Position part of the FEN string
309 getBaseFen()
310 {
311 let position = "";
312 for (let i=0; i<V.size.x; i++)
313 {
314 let emptyCount = 0;
315 for (let j=0; j<V.size.y; j++)
316 {
317 if (this.board[i][j] == V.EMPTY)
318 emptyCount++;
319 else
320 {
321 if (emptyCount > 0)
322 {
323 // Add empty squares in-between
324 position += emptyCount;
325 emptyCount = 0;
326 }
327 position += V.board2fen(this.board[i][j]);
328 }
329 }
330 if (emptyCount > 0)
331 {
332 // "Flush remainder"
333 position += emptyCount;
334 }
335 if (i < V.size.x - 1)
336 position += "/"; //separate rows
337 }
338 return position;
339 }
340
341 getTurnFen()
342 {
343 return this.turn;
344 }
345
346 // Flags part of the FEN string
347 getFlagsFen()
348 {
349 let flags = "";
350 // Add castling flags
351 for (let i of ['w','b'])
352 {
353 for (let j=0; j<2; j++)
354 flags += (this.castleFlags[i][j] ? '1' : '0');
355 }
356 return flags;
357 }
358
359 // Enpassant part of the FEN string
360 getEnpassantFen()
361 {
362 const L = this.epSquares.length;
363 if (!this.epSquares[L-1])
364 return "-"; //no en-passant
365 return V.CoordsToSquare(this.epSquares[L-1]);
366 }
367
368 // Turn position fen into double array ["wb","wp","bk",...]
369 static GetBoard(position)
370 {
371 const rows = position.split("/");
372 let board = doubleArray(V.size.x, V.size.y, "");
373 for (let i=0; i<rows.length; i++)
374 {
375 let j = 0;
376 for (let indexInRow = 0; indexInRow < rows[i].length; indexInRow++)
377 {
378 const character = rows[i][indexInRow];
379 const num = parseInt(character);
380 if (!isNaN(num))
381 j += num; //just shift j
382 else //something at position i,j
383 board[i][j++] = V.fen2board(character);
384 }
385 }
386 return board;
387 }
388
389 // Extract (relevant) flags from fen
390 setFlags(fenflags)
391 {
392 // white a-castle, h-castle, black a-castle, h-castle
393 this.castleFlags = {'w': [true,true], 'b': [true,true]};
394 if (!fenflags)
395 return;
396 for (let i=0; i<4; i++)
397 this.castleFlags[i < 2 ? 'w' : 'b'][i%2] = (fenflags.charAt(i) == '1');
398 }
399
400 //////////////////
401 // INITIALIZATION
402
403 // Fen string fully describes the game state
404 constructor(fen, moves)
405 {
406 this.moves = moves;
407 const fenParsed = V.ParseFen(fen);
408 this.board = V.GetBoard(fenParsed.position);
409 this.turn = fenParsed.turn[0]; //[0] to work with MarseilleRules
410 this.setOtherVariables(fen);
411 }
412
413 // Scan board for kings and rooks positions
414 scanKingsRooks(fen)
415 {
416 this.INIT_COL_KING = {'w':-1, 'b':-1};
417 this.INIT_COL_ROOK = {'w':[-1,-1], 'b':[-1,-1]};
418 this.kingPos = {'w':[-1,-1], 'b':[-1,-1]}; //squares of white and black king
419 const fenRows = V.ParseFen(fen).position.split("/");
420 for (let i=0; i<fenRows.length; i++)
421 {
422 let k = 0; //column index on board
423 for (let j=0; j<fenRows[i].length; j++)
424 {
425 switch (fenRows[i].charAt(j))
426 {
427 case 'k':
428 this.kingPos['b'] = [i,k];
429 this.INIT_COL_KING['b'] = k;
430 break;
431 case 'K':
432 this.kingPos['w'] = [i,k];
433 this.INIT_COL_KING['w'] = k;
434 break;
435 case 'r':
436 if (this.INIT_COL_ROOK['b'][0] < 0)
437 this.INIT_COL_ROOK['b'][0] = k;
438 else
439 this.INIT_COL_ROOK['b'][1] = k;
440 break;
441 case 'R':
442 if (this.INIT_COL_ROOK['w'][0] < 0)
443 this.INIT_COL_ROOK['w'][0] = k;
444 else
445 this.INIT_COL_ROOK['w'][1] = k;
446 break;
447 default:
448 const num = parseInt(fenRows[i].charAt(j));
449 if (!isNaN(num))
450 k += (num-1);
451 }
452 k++;
453 }
454 }
455 }
456
457 // Some additional variables from FEN (variant dependant)
458 setOtherVariables(fen)
459 {
460 // Set flags and enpassant:
461 const parsedFen = V.ParseFen(fen);
462 if (V.HasFlags)
463 this.setFlags(parsedFen.flags);
464 if (V.HasEnpassant)
465 {
466 const epSq = parsedFen.enpassant != "-"
467 ? V.SquareToCoords(parsedFen.enpassant)
468 : undefined;
469 this.epSquares = [ epSq ];
470 }
471 // Search for king and rooks positions:
472 this.scanKingsRooks(fen);
473 }
474
475 /////////////////////
476 // GETTERS & SETTERS
477
478 static get size()
479 {
480 return {x:8, y:8};
481 }
482
483 // Color of thing on suqare (i,j). 'undefined' if square is empty
484 getColor(i,j)
485 {
486 return this.board[i][j].charAt(0);
487 }
488
489 // Piece type on square (i,j). 'undefined' if square is empty
490 getPiece(i,j)
491 {
492 return this.board[i][j].charAt(1);
493 }
494
495 // Get opponent color
496 getOppCol(color)
497 {
498 return (color=="w" ? "b" : "w");
499 }
500
501 get lastMove()
502 {
503 const L = this.moves.length;
504 return (L>0 ? this.moves[L-1] : null);
505 }
506
507 // Pieces codes (for a clearer code)
508 static get PAWN() { return 'p'; }
509 static get ROOK() { return 'r'; }
510 static get KNIGHT() { return 'n'; }
511 static get BISHOP() { return 'b'; }
512 static get QUEEN() { return 'q'; }
513 static get KING() { return 'k'; }
514
515 // For FEN checking:
516 static get PIECES()
517 {
518 return [V.PAWN,V.ROOK,V.KNIGHT,V.BISHOP,V.QUEEN,V.KING];
519 }
520
521 // Empty square
522 static get EMPTY() { return ""; }
523
524 // Some pieces movements
525 static get steps()
526 {
527 return {
528 'r': [ [-1,0],[1,0],[0,-1],[0,1] ],
529 'n': [ [-1,-2],[-1,2],[1,-2],[1,2],[-2,-1],[-2,1],[2,-1],[2,1] ],
530 'b': [ [-1,-1],[-1,1],[1,-1],[1,1] ],
531 };
532 }
533
534 ////////////////////
535 // MOVES GENERATION
536
537 // All possible moves from selected square (assumption: color is OK)
538 getPotentialMovesFrom([x,y])
539 {
540 switch (this.getPiece(x,y))
541 {
542 case V.PAWN:
543 return this.getPotentialPawnMoves([x,y]);
544 case V.ROOK:
545 return this.getPotentialRookMoves([x,y]);
546 case V.KNIGHT:
547 return this.getPotentialKnightMoves([x,y]);
548 case V.BISHOP:
549 return this.getPotentialBishopMoves([x,y]);
550 case V.QUEEN:
551 return this.getPotentialQueenMoves([x,y]);
552 case V.KING:
553 return this.getPotentialKingMoves([x,y]);
554 }
555 }
556
557 // Build a regular move from its initial and destination squares.
558 // tr: transformation
559 getBasicMove([sx,sy], [ex,ey], tr)
560 {
561 let mv = new Move({
562 appear: [
563 new PiPo({
564 x: ex,
565 y: ey,
566 c: !!tr ? tr.c : this.getColor(sx,sy),
567 p: !!tr ? tr.p : this.getPiece(sx,sy)
568 })
569 ],
570 vanish: [
571 new PiPo({
572 x: sx,
573 y: sy,
574 c: this.getColor(sx,sy),
575 p: this.getPiece(sx,sy)
576 })
577 ]
578 });
579
580 // The opponent piece disappears if we take it
581 if (this.board[ex][ey] != V.EMPTY)
582 {
583 mv.vanish.push(
584 new PiPo({
585 x: ex,
586 y: ey,
587 c: this.getColor(ex,ey),
588 p: this.getPiece(ex,ey)
589 })
590 );
591 }
592 return mv;
593 }
594
595 // Generic method to find possible moves of non-pawn pieces:
596 // "sliding or jumping"
597 getSlideNJumpMoves([x,y], steps, oneStep)
598 {
599 const color = this.getColor(x,y);
600 let moves = [];
601 outerLoop:
602 for (let step of steps)
603 {
604 let i = x + step[0];
605 let j = y + step[1];
606 while (V.OnBoard(i,j) && this.board[i][j] == V.EMPTY)
607 {
608 moves.push(this.getBasicMove([x,y], [i,j]));
609 if (oneStep !== undefined)
610 continue outerLoop;
611 i += step[0];
612 j += step[1];
613 }
614 if (V.OnBoard(i,j) && this.canTake([x,y], [i,j]))
615 moves.push(this.getBasicMove([x,y], [i,j]));
616 }
617 return moves;
618 }
619
620 // What are the pawn moves from square x,y ?
621 getPotentialPawnMoves([x,y])
622 {
623 const color = this.turn;
624 let moves = [];
625 const [sizeX,sizeY] = [V.size.x,V.size.y];
626 const shiftX = (color == "w" ? -1 : 1);
627 const firstRank = (color == 'w' ? sizeX-1 : 0);
628 const startRank = (color == "w" ? sizeX-2 : 1);
629 const lastRank = (color == "w" ? 0 : sizeX-1);
630 const pawnColor = this.getColor(x,y); //can be different for checkered
631
632 // NOTE: next condition is generally true (no pawn on last rank)
633 if (x+shiftX >= 0 && x+shiftX < sizeX)
634 {
635 const finalPieces = x + shiftX == lastRank
636 ? [V.ROOK,V.KNIGHT,V.BISHOP,V.QUEEN]
637 : [V.PAWN]
638 // One square forward
639 if (this.board[x+shiftX][y] == V.EMPTY)
640 {
641 for (let piece of finalPieces)
642 {
643 moves.push(this.getBasicMove([x,y], [x+shiftX,y],
644 {c:pawnColor,p:piece}));
645 }
646 // Next condition because pawns on 1st rank can generally jump
647 if ([startRank,firstRank].includes(x)
648 && this.board[x+2*shiftX][y] == V.EMPTY)
649 {
650 // Two squares jump
651 moves.push(this.getBasicMove([x,y], [x+2*shiftX,y]));
652 }
653 }
654 // Captures
655 for (let shiftY of [-1,1])
656 {
657 if (y + shiftY >= 0 && y + shiftY < sizeY
658 && this.board[x+shiftX][y+shiftY] != V.EMPTY
659 && this.canTake([x,y], [x+shiftX,y+shiftY]))
660 {
661 for (let piece of finalPieces)
662 {
663 moves.push(this.getBasicMove([x,y], [x+shiftX,y+shiftY],
664 {c:pawnColor,p:piece}));
665 }
666 }
667 }
668 }
669
670 if (V.HasEnpassant)
671 {
672 // En passant
673 const Lep = this.epSquares.length;
674 const epSquare = this.epSquares[Lep-1]; //always at least one element
675 if (!!epSquare && epSquare.x == x+shiftX && Math.abs(epSquare.y - y) == 1)
676 {
677 let enpassantMove = this.getBasicMove([x,y], [epSquare.x,epSquare.y]);
678 enpassantMove.vanish.push({
679 x: x,
680 y: epSquare.y,
681 p: 'p',
682 c: this.getColor(x,epSquare.y)
683 });
684 moves.push(enpassantMove);
685 }
686 }
687
688 return moves;
689 }
690
691 // What are the rook moves from square x,y ?
692 getPotentialRookMoves(sq)
693 {
694 return this.getSlideNJumpMoves(sq, V.steps[V.ROOK]);
695 }
696
697 // What are the knight moves from square x,y ?
698 getPotentialKnightMoves(sq)
699 {
700 return this.getSlideNJumpMoves(sq, V.steps[V.KNIGHT], "oneStep");
701 }
702
703 // What are the bishop moves from square x,y ?
704 getPotentialBishopMoves(sq)
705 {
706 return this.getSlideNJumpMoves(sq, V.steps[V.BISHOP]);
707 }
708
709 // What are the queen moves from square x,y ?
710 getPotentialQueenMoves(sq)
711 {
712 return this.getSlideNJumpMoves(sq,
713 V.steps[V.ROOK].concat(V.steps[V.BISHOP]));
714 }
715
716 // What are the king moves from square x,y ?
717 getPotentialKingMoves(sq)
718 {
719 // Initialize with normal moves
720 let moves = this.getSlideNJumpMoves(sq,
721 V.steps[V.ROOK].concat(V.steps[V.BISHOP]), "oneStep");
722 return moves.concat(this.getCastleMoves(sq));
723 }
724
725 getCastleMoves([x,y])
726 {
727 const c = this.getColor(x,y);
728 if (x != (c=="w" ? V.size.x-1 : 0) || y != this.INIT_COL_KING[c])
729 return []; //x isn't first rank, or king has moved (shortcut)
730
731 // Castling ?
732 const oppCol = this.getOppCol(c);
733 let moves = [];
734 let i = 0;
735 const finalSquares = [ [2,3], [V.size.y-2,V.size.y-3] ]; //king, then rook
736 castlingCheck:
737 for (let castleSide=0; castleSide < 2; castleSide++) //large, then small
738 {
739 if (!this.castleFlags[c][castleSide])
740 continue;
741 // If this code is reached, rooks and king are on initial position
742
743 // Nothing on the path of the king ?
744 // (And no checks; OK also if y==finalSquare)
745 let step = finalSquares[castleSide][0] < y ? -1 : 1;
746 for (i=y; i!=finalSquares[castleSide][0]; i+=step)
747 {
748 if (this.isAttacked([x,i], [oppCol]) || (this.board[x][i] != V.EMPTY &&
749 // NOTE: next check is enough, because of chessboard constraints
750 (this.getColor(x,i) != c
751 || ![V.KING,V.ROOK].includes(this.getPiece(x,i)))))
752 {
753 continue castlingCheck;
754 }
755 }
756
757 // Nothing on the path to the rook?
758 step = castleSide == 0 ? -1 : 1;
759 for (i = y + step; i != this.INIT_COL_ROOK[c][castleSide]; i += step)
760 {
761 if (this.board[x][i] != V.EMPTY)
762 continue castlingCheck;
763 }
764 const rookPos = this.INIT_COL_ROOK[c][castleSide];
765
766 // Nothing on final squares, except maybe king and castling rook?
767 for (i=0; i<2; i++)
768 {
769 if (this.board[x][finalSquares[castleSide][i]] != V.EMPTY &&
770 this.getPiece(x,finalSquares[castleSide][i]) != V.KING &&
771 finalSquares[castleSide][i] != rookPos)
772 {
773 continue castlingCheck;
774 }
775 }
776
777 // If this code is reached, castle is valid
778 moves.push( new Move({
779 appear: [
780 new PiPo({x:x,y:finalSquares[castleSide][0],p:V.KING,c:c}),
781 new PiPo({x:x,y:finalSquares[castleSide][1],p:V.ROOK,c:c})],
782 vanish: [
783 new PiPo({x:x,y:y,p:V.KING,c:c}),
784 new PiPo({x:x,y:rookPos,p:V.ROOK,c:c})],
785 end: Math.abs(y - rookPos) <= 2
786 ? {x:x, y:rookPos}
787 : {x:x, y:y + 2 * (castleSide==0 ? -1 : 1)}
788 }) );
789 }
790
791 return moves;
792 }
793
794 ////////////////////
795 // MOVES VALIDATION
796
797 // For the interface: possible moves for the current turn from square sq
798 getPossibleMovesFrom(sq)
799 {
800 return this.filterValid( this.getPotentialMovesFrom(sq) );
801 }
802
803 // TODO: promotions (into R,B,N,Q) should be filtered only once
804 filterValid(moves)
805 {
806 if (moves.length == 0)
807 return [];
808 const color = this.turn;
809 return moves.filter(m => {
810 this.play(m);
811 const res = !this.underCheck(color);
812 this.undo(m);
813 return res;
814 });
815 }
816
817 // Search for all valid moves considering current turn
818 // (for engine and game end)
819 getAllValidMoves()
820 {
821 const color = this.turn;
822 const oppCol = this.getOppCol(color);
823 let potentialMoves = [];
824 for (let i=0; i<V.size.x; i++)
825 {
826 for (let j=0; j<V.size.y; j++)
827 {
828 // Next condition "!= oppCol" to work with checkered variant
829 if (this.board[i][j] != V.EMPTY && this.getColor(i,j) != oppCol)
830 {
831 Array.prototype.push.apply(potentialMoves,
832 this.getPotentialMovesFrom([i,j]));
833 }
834 }
835 }
836 return this.filterValid(potentialMoves);
837 }
838
839 // Stop at the first move found
840 atLeastOneMove()
841 {
842 const color = this.turn;
843 const oppCol = this.getOppCol(color);
844 for (let i=0; i<V.size.x; i++)
845 {
846 for (let j=0; j<V.size.y; j++)
847 {
848 if (this.board[i][j] != V.EMPTY && this.getColor(i,j) != oppCol)
849 {
850 const moves = this.getPotentialMovesFrom([i,j]);
851 if (moves.length > 0)
852 {
853 for (let k=0; k<moves.length; k++)
854 {
855 if (this.filterValid([moves[k]]).length > 0)
856 return true;
857 }
858 }
859 }
860 }
861 }
862 return false;
863 }
864
865 // Check if pieces of color in 'colors' are attacking (king) on square x,y
866 isAttacked(sq, colors)
867 {
868 return (this.isAttackedByPawn(sq, colors)
869 || this.isAttackedByRook(sq, colors)
870 || this.isAttackedByKnight(sq, colors)
871 || this.isAttackedByBishop(sq, colors)
872 || this.isAttackedByQueen(sq, colors)
873 || this.isAttackedByKing(sq, colors));
874 }
875
876 // Is square x,y attacked by 'colors' pawns ?
877 isAttackedByPawn([x,y], colors)
878 {
879 for (let c of colors)
880 {
881 let pawnShift = (c=="w" ? 1 : -1);
882 if (x+pawnShift>=0 && x+pawnShift<V.size.x)
883 {
884 for (let i of [-1,1])
885 {
886 if (y+i>=0 && y+i<V.size.y && this.getPiece(x+pawnShift,y+i)==V.PAWN
887 && this.getColor(x+pawnShift,y+i)==c)
888 {
889 return true;
890 }
891 }
892 }
893 }
894 return false;
895 }
896
897 // Is square x,y attacked by 'colors' rooks ?
898 isAttackedByRook(sq, colors)
899 {
900 return this.isAttackedBySlideNJump(sq, colors, V.ROOK, V.steps[V.ROOK]);
901 }
902
903 // Is square x,y attacked by 'colors' knights ?
904 isAttackedByKnight(sq, colors)
905 {
906 return this.isAttackedBySlideNJump(sq, colors,
907 V.KNIGHT, V.steps[V.KNIGHT], "oneStep");
908 }
909
910 // Is square x,y attacked by 'colors' bishops ?
911 isAttackedByBishop(sq, colors)
912 {
913 return this.isAttackedBySlideNJump(sq, colors, V.BISHOP, V.steps[V.BISHOP]);
914 }
915
916 // Is square x,y attacked by 'colors' queens ?
917 isAttackedByQueen(sq, colors)
918 {
919 return this.isAttackedBySlideNJump(sq, colors, V.QUEEN,
920 V.steps[V.ROOK].concat(V.steps[V.BISHOP]));
921 }
922
923 // Is square x,y attacked by 'colors' king(s) ?
924 isAttackedByKing(sq, colors)
925 {
926 return this.isAttackedBySlideNJump(sq, colors, V.KING,
927 V.steps[V.ROOK].concat(V.steps[V.BISHOP]), "oneStep");
928 }
929
930 // Generic method for non-pawn pieces ("sliding or jumping"):
931 // is x,y attacked by a piece of color in array 'colors' ?
932 isAttackedBySlideNJump([x,y], colors, piece, steps, oneStep)
933 {
934 for (let step of steps)
935 {
936 let rx = x+step[0], ry = y+step[1];
937 while (V.OnBoard(rx,ry) && this.board[rx][ry] == V.EMPTY && !oneStep)
938 {
939 rx += step[0];
940 ry += step[1];
941 }
942 if (V.OnBoard(rx,ry) && this.getPiece(rx,ry) === piece
943 && colors.includes(this.getColor(rx,ry)))
944 {
945 return true;
946 }
947 }
948 return false;
949 }
950
951 // Is color under check after his move ?
952 underCheck(color)
953 {
954 return this.isAttacked(this.kingPos[color], [this.getOppCol(color)]);
955 }
956
957 /////////////////
958 // MOVES PLAYING
959
960 // Apply a move on board
961 static PlayOnBoard(board, move)
962 {
963 for (let psq of move.vanish)
964 board[psq.x][psq.y] = V.EMPTY;
965 for (let psq of move.appear)
966 board[psq.x][psq.y] = psq.c + psq.p;
967 }
968 // Un-apply the played move
969 static UndoOnBoard(board, move)
970 {
971 for (let psq of move.appear)
972 board[psq.x][psq.y] = V.EMPTY;
973 for (let psq of move.vanish)
974 board[psq.x][psq.y] = psq.c + psq.p;
975 }
976
977 // After move is played, update variables + flags
978 updateVariables(move)
979 {
980 let piece = undefined;
981 let c = undefined;
982 if (move.vanish.length >= 1)
983 {
984 // Usual case, something is moved
985 piece = move.vanish[0].p;
986 c = move.vanish[0].c;
987 }
988 else
989 {
990 // Crazyhouse-like variants
991 piece = move.appear[0].p;
992 c = move.appear[0].c;
993 }
994 if (c == "c") //if (!["w","b"].includes(c))
995 {
996 // 'c = move.vanish[0].c' doesn't work for Checkered
997 c = this.getOppCol(this.turn);
998 }
999 const firstRank = (c == "w" ? V.size.x-1 : 0);
1000
1001 // Update king position + flags
1002 if (piece == V.KING && move.appear.length > 0)
1003 {
1004 this.kingPos[c][0] = move.appear[0].x;
1005 this.kingPos[c][1] = move.appear[0].y;
1006 if (V.HasFlags)
1007 this.castleFlags[c] = [false,false];
1008 return;
1009 }
1010 if (V.HasFlags)
1011 {
1012 // Update castling flags if rooks are moved
1013 const oppCol = this.getOppCol(c);
1014 const oppFirstRank = (V.size.x-1) - firstRank;
1015 if (move.start.x == firstRank //our rook moves?
1016 && this.INIT_COL_ROOK[c].includes(move.start.y))
1017 {
1018 const flagIdx = (move.start.y == this.INIT_COL_ROOK[c][0] ? 0 : 1);
1019 this.castleFlags[c][flagIdx] = false;
1020 }
1021 else if (move.end.x == oppFirstRank //we took opponent rook?
1022 && this.INIT_COL_ROOK[oppCol].includes(move.end.y))
1023 {
1024 const flagIdx = (move.end.y == this.INIT_COL_ROOK[oppCol][0] ? 0 : 1);
1025 this.castleFlags[oppCol][flagIdx] = false;
1026 }
1027 }
1028 }
1029
1030 // After move is undo-ed *and flags resetted*, un-update other variables
1031 // TODO: more symmetry, by storing flags increment in move (?!)
1032 unupdateVariables(move)
1033 {
1034 // (Potentially) Reset king position
1035 const c = this.getColor(move.start.x,move.start.y);
1036 if (this.getPiece(move.start.x,move.start.y) == V.KING)
1037 this.kingPos[c] = [move.start.x, move.start.y];
1038 }
1039
1040 play(move, ingame)
1041 {
1042 // DEBUG:
1043 // if (!this.states) this.states = [];
1044 // if (!ingame) this.states.push(this.getFen());
1045
1046 if (!!ingame)
1047 move.notation = [this.getNotation(move), this.getLongNotation(move)];
1048
1049 if (V.HasFlags)
1050 move.flags = JSON.stringify(this.aggregateFlags()); //save flags (for undo)
1051 if (V.HasEnpassant)
1052 this.epSquares.push( this.getEpSquare(move) );
1053 V.PlayOnBoard(this.board, move);
1054 this.turn = this.getOppCol(this.turn);
1055 this.moves.push(move);
1056 this.updateVariables(move);
1057
1058 if (!!ingame)
1059 {
1060 // Hash of current game state *after move*, to detect repetitions
1061 move.hash = hex_md5(this.getFen());
1062 }
1063 }
1064
1065 undo(move)
1066 {
1067 if (V.HasEnpassant)
1068 this.epSquares.pop();
1069 if (V.HasFlags)
1070 this.disaggregateFlags(JSON.parse(move.flags));
1071 V.UndoOnBoard(this.board, move);
1072 this.turn = this.getOppCol(this.turn);
1073 this.moves.pop();
1074 this.unupdateVariables(move);
1075
1076 // DEBUG:
1077 // if (this.getFen() != this.states[this.states.length-1])
1078 // debugger;
1079 // this.states.pop();
1080 }
1081
1082 ///////////////
1083 // END OF GAME
1084
1085 // Check for 3 repetitions (position + flags + turn)
1086 checkRepetition()
1087 {
1088 if (!this.hashStates)
1089 this.hashStates = {};
1090 const startIndex =
1091 Object.values(this.hashStates).reduce((a,b) => { return a+b; }, 0)
1092 // Update this.hashStates with last move (or all moves if continuation)
1093 // NOTE: redundant storage, but faster and moderate size
1094 for (let i=startIndex; i<this.moves.length; i++)
1095 {
1096 const move = this.moves[i];
1097 if (!this.hashStates[move.hash])
1098 this.hashStates[move.hash] = 1;
1099 else
1100 this.hashStates[move.hash]++;
1101 }
1102 return Object.values(this.hashStates).some(elt => { return (elt >= 3); });
1103 }
1104
1105 // Is game over ? And if yes, what is the score ?
1106 checkGameOver()
1107 {
1108 if (this.checkRepetition())
1109 return "1/2";
1110
1111 if (this.atLeastOneMove()) // game not over
1112 return "*";
1113
1114 // Game over
1115 return this.checkGameEnd();
1116 }
1117
1118 // No moves are possible: compute score
1119 checkGameEnd()
1120 {
1121 const color = this.turn;
1122 // No valid move: stalemate or checkmate?
1123 if (!this.isAttacked(this.kingPos[color], [this.getOppCol(color)]))
1124 return "1/2";
1125 // OK, checkmate
1126 return (color == "w" ? "0-1" : "1-0");
1127 }
1128
1129 ///////////////
1130 // ENGINE PLAY
1131
1132 // Pieces values
1133 static get VALUES()
1134 {
1135 return {
1136 'p': 1,
1137 'r': 5,
1138 'n': 3,
1139 'b': 3,
1140 'q': 9,
1141 'k': 1000
1142 };
1143 }
1144
1145 // "Checkmate" (unreachable eval)
1146 static get INFINITY() { return 9999; }
1147
1148 // At this value or above, the game is over
1149 static get THRESHOLD_MATE() { return V.INFINITY; }
1150
1151 // Search depth: 2 for high branching factor, 4 for small (Loser chess, eg.)
1152 static get SEARCH_DEPTH() { return 3; }
1153
1154 // Assumption: at least one legal move
1155 // NOTE: works also for extinction chess because depth is 3...
1156 getComputerMove()
1157 {
1158 const maxeval = V.INFINITY;
1159 const color = this.turn;
1160 // Some variants may show a bigger moves list to the human (Switching),
1161 // thus the argument "computer" below (which is generally ignored)
1162 let moves1 = this.getAllValidMoves("computer");
1163
1164 // Can I mate in 1 ? (for Magnetic & Extinction)
1165 for (let i of _.shuffle(_.range(moves1.length)))
1166 {
1167 this.play(moves1[i]);
1168 let finish = (Math.abs(this.evalPosition()) >= V.THRESHOLD_MATE);
1169 if (!finish && !this.atLeastOneMove())
1170 {
1171 // Test mate (for other variants)
1172 const score = this.checkGameEnd();
1173 if (score != "1/2")
1174 finish = true;
1175 }
1176 this.undo(moves1[i]);
1177 if (finish)
1178 return moves1[i];
1179 }
1180
1181 // Rank moves using a min-max at depth 2
1182 for (let i=0; i<moves1.length; i++)
1183 {
1184 // Initial self evaluation is very low: "I'm checkmated"
1185 moves1[i].eval = (color=="w" ? -1 : 1) * maxeval;
1186 this.play(moves1[i]);
1187 let eval2 = undefined;
1188 if (this.atLeastOneMove())
1189 {
1190 // Initial enemy evaluation is very low too, for him
1191 eval2 = (color=="w" ? 1 : -1) * maxeval;
1192 // Second half-move:
1193 let moves2 = this.getAllValidMoves("computer");
1194 for (let j=0; j<moves2.length; j++)
1195 {
1196 this.play(moves2[j]);
1197 let evalPos = undefined;
1198 if (this.atLeastOneMove())
1199 evalPos = this.evalPosition()
1200 else
1201 {
1202 // Working with scores is more accurate (necessary for Loser variant)
1203 const score = this.checkGameEnd();
1204 evalPos = (score=="1/2" ? 0 : (score=="1-0" ? 1 : -1) * maxeval);
1205 }
1206 if ((color == "w" && evalPos < eval2)
1207 || (color=="b" && evalPos > eval2))
1208 {
1209 eval2 = evalPos;
1210 }
1211 this.undo(moves2[j]);
1212 }
1213 }
1214 else
1215 {
1216 const score = this.checkGameEnd();
1217 eval2 = (score=="1/2" ? 0 : (score=="1-0" ? 1 : -1) * maxeval);
1218 }
1219 if ((color=="w" && eval2 > moves1[i].eval)
1220 || (color=="b" && eval2 < moves1[i].eval))
1221 {
1222 moves1[i].eval = eval2;
1223 }
1224 this.undo(moves1[i]);
1225 }
1226 moves1.sort( (a,b) => { return (color=="w" ? 1 : -1) * (b.eval - a.eval); });
1227
1228 let candidates = [0]; //indices of candidates moves
1229 for (let j=1; j<moves1.length && moves1[j].eval == moves1[0].eval; j++)
1230 candidates.push(j);
1231 let currentBest = moves1[_.sample(candidates, 1)];
1232
1233 // From here, depth >= 3: may take a while, so we control time
1234 const timeStart = Date.now();
1235
1236 // Skip depth 3+ if we found a checkmate (or if we are checkmated in 1...)
1237 if (V.SEARCH_DEPTH >= 3 && Math.abs(moves1[0].eval) < V.THRESHOLD_MATE)
1238 {
1239 for (let i=0; i<moves1.length; i++)
1240 {
1241 if (Date.now()-timeStart >= 5000) //more than 5 seconds
1242 return currentBest; //depth 2 at least
1243 this.play(moves1[i]);
1244 // 0.1 * oldEval : heuristic to avoid some bad moves (not all...)
1245 moves1[i].eval = 0.1*moves1[i].eval +
1246 this.alphabeta(V.SEARCH_DEPTH-1, -maxeval, maxeval);
1247 this.undo(moves1[i]);
1248 }
1249 moves1.sort( (a,b) => {
1250 return (color=="w" ? 1 : -1) * (b.eval - a.eval); });
1251 }
1252 else
1253 return currentBest;
1254 // console.log(moves1.map(m => { return [this.getNotation(m), m.eval]; }));
1255
1256 candidates = [0];
1257 for (let j=1; j<moves1.length && moves1[j].eval == moves1[0].eval; j++)
1258 candidates.push(j);
1259 return moves1[_.sample(candidates, 1)];
1260 }
1261
1262 alphabeta(depth, alpha, beta)
1263 {
1264 const maxeval = V.INFINITY;
1265 const color = this.turn;
1266 if (!this.atLeastOneMove())
1267 {
1268 switch (this.checkGameEnd())
1269 {
1270 case "1/2":
1271 return 0;
1272 default:
1273 const score = this.checkGameEnd();
1274 return (score=="1/2" ? 0 : (score=="1-0" ? 1 : -1) * maxeval);
1275 }
1276 }
1277 if (depth == 0)
1278 return this.evalPosition();
1279 const moves = this.getAllValidMoves("computer");
1280 let v = color=="w" ? -maxeval : maxeval;
1281 if (color == "w")
1282 {
1283 for (let i=0; i<moves.length; i++)
1284 {
1285 this.play(moves[i]);
1286 v = Math.max(v, this.alphabeta(depth-1, alpha, beta));
1287 this.undo(moves[i]);
1288 alpha = Math.max(alpha, v);
1289 if (alpha >= beta)
1290 break; //beta cutoff
1291 }
1292 }
1293 else //color=="b"
1294 {
1295 for (let i=0; i<moves.length; i++)
1296 {
1297 this.play(moves[i]);
1298 v = Math.min(v, this.alphabeta(depth-1, alpha, beta));
1299 this.undo(moves[i]);
1300 beta = Math.min(beta, v);
1301 if (alpha >= beta)
1302 break; //alpha cutoff
1303 }
1304 }
1305 return v;
1306 }
1307
1308 evalPosition()
1309 {
1310 let evaluation = 0;
1311 // Just count material for now
1312 for (let i=0; i<V.size.x; i++)
1313 {
1314 for (let j=0; j<V.size.y; j++)
1315 {
1316 if (this.board[i][j] != V.EMPTY)
1317 {
1318 const sign = this.getColor(i,j) == "w" ? 1 : -1;
1319 evaluation += sign * V.VALUES[this.getPiece(i,j)];
1320 }
1321 }
1322 }
1323 return evaluation;
1324 }
1325
1326 /////////////////////////
1327 // MOVES + GAME NOTATION
1328 /////////////////////////
1329
1330 // Context: just before move is played, turn hasn't changed
1331 getNotation(move)
1332 {
1333 if (move.appear.length == 2 && move.appear[0].p == V.KING) //castle
1334 return (move.end.y < move.start.y ? "0-0-0" : "0-0");
1335
1336 // Translate final square
1337 const finalSquare = V.CoordsToSquare(move.end);
1338
1339 const piece = this.getPiece(move.start.x, move.start.y);
1340 if (piece == V.PAWN)
1341 {
1342 // Pawn move
1343 let notation = "";
1344 if (move.vanish.length > move.appear.length)
1345 {
1346 // Capture
1347 const startColumn = V.CoordToColumn(move.start.y);
1348 notation = startColumn + "x" + finalSquare;
1349 }
1350 else //no capture
1351 notation = finalSquare;
1352 if (move.appear.length > 0 && move.appear[0].p != V.PAWN) //promotion
1353 notation += "=" + move.appear[0].p.toUpperCase();
1354 return notation;
1355 }
1356
1357 else
1358 {
1359 // Piece movement
1360 return piece.toUpperCase() +
1361 (move.vanish.length > move.appear.length ? "x" : "") + finalSquare;
1362 }
1363 }
1364
1365 // Complete the usual notation, may be required for de-ambiguification
1366 getLongNotation(move)
1367 {
1368 // Not encoding move. But short+long is enough
1369 return V.CoordsToSquare(move.start) + V.CoordsToSquare(move.end);
1370 }
1371
1372 // The score is already computed when calling this function
1373 getPGN(mycolor, score, fenStart, mode)
1374 {
1375 let pgn = "";
1376 pgn += '[Site "vchess.club"]\n';
1377 const opponent = mode=="human" ? "Anonymous" : "Computer";
1378 pgn += '[Variant "' + variant + '"]\n';
1379 pgn += '[Date "' + getDate(new Date()) + '"]\n';
1380 // TODO: later when users are a bit less anonymous, use better names
1381 const whiteName = ["human","computer"].includes(mode)
1382 ? (mycolor=='w'?'Myself':opponent)
1383 : "analyze";
1384 const blackName = ["human","computer"].includes(mode)
1385 ? (mycolor=='b'?'Myself':opponent)
1386 : "analyze";
1387 pgn += '[White "' + whiteName + '"]\n';
1388 pgn += '[Black "' + blackName + '"]\n';
1389 pgn += '[FenStart "' + fenStart + '"]\n';
1390 pgn += '[Fen "' + this.getFen() + '"]\n';
1391 pgn += '[Result "' + score + '"]\n\n';
1392
1393 // Standard PGN
1394 for (let i=0; i<this.moves.length; i++)
1395 {
1396 if (i % 2 == 0)
1397 pgn += ((i/2)+1) + ".";
1398 pgn += this.moves[i].notation[0] + " ";
1399 }
1400 pgn += "\n\n";
1401
1402 // "Complete moves" PGN (helping in ambiguous cases)
1403 for (let i=0; i<this.moves.length; i++)
1404 {
1405 if (i % 2 == 0)
1406 pgn += ((i/2)+1) + ".";
1407 pgn += this.moves[i].notation[1] + " ";
1408 }
1409
1410 return pgn + "\n";
1411 }
1412 }