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