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