f9574004f5973f2e6cef6911a392b04754c9085d
[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
195 getPpath(b) {
196 return b; //usual pieces in pieces/ folder
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[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 p: this.getPiece(x, epSquare.y),
683 c: this.getColor(x, epSquare.y)
684 });
685 }
686 return !!enpassantMove ? [enpassantMove] : [];
687 }
688
689 // Consider all potential promotions:
690 addPawnMoves([x1, y1], [x2, y2], moves, promotions) {
691 let finalPieces = [V.PAWN];
692 const color = this.turn;
693 const lastRank = (color == "w" ? 0 : V.size.x - 1);
694 if (x2 == lastRank) {
695 // promotions arg: special override for Hiddenqueen variant
696 if (!!promotions) finalPieces = promotions;
697 else if (!!V.PawnSpecs.promotions)
698 finalPieces = V.PawnSpecs.promotions;
699 }
700 let tr = null;
701 for (let piece of finalPieces) {
702 tr = (piece != V.PAWN ? { c: color, p: piece } : null);
703 moves.push(this.getBasicMove([x1, y1], [x2, y2], tr));
704 }
705 }
706
707 // What are the pawn moves from square x,y ?
708 getPotentialPawnMoves([x, y], promotions) {
709 const color = this.turn;
710 const [sizeX, sizeY] = [V.size.x, V.size.y];
711 const pawnShiftX = V.PawnSpecs.directions[color];
712 const firstRank = (color == "w" ? sizeX - 1 : 0);
713 const startRank = (color == "w" ? sizeX - 2 : 1);
714
715 // Pawn movements in shiftX direction:
716 const getPawnMoves = (shiftX) => {
717 let moves = [];
718 // NOTE: next condition is generally true (no pawn on last rank)
719 if (x + shiftX >= 0 && x + shiftX < sizeX) {
720 if (this.board[x + shiftX][y] == V.EMPTY) {
721 // One square forward
722 this.addPawnMoves([x, y], [x + shiftX, y], moves, promotions);
723 // Next condition because pawns on 1st rank can generally jump
724 if (
725 V.PawnSpecs.twoSquares &&
726 [startRank, firstRank].includes(x) &&
727 this.board[x + 2 * shiftX][y] == V.EMPTY
728 ) {
729 // Two squares jump
730 moves.push(this.getBasicMove([x, y], [x + 2 * shiftX, y]));
731 }
732 }
733 // Captures
734 if (V.PawnSpecs.canCapture) {
735 for (let shiftY of [-1, 1]) {
736 if (
737 y + shiftY >= 0 &&
738 y + shiftY < sizeY
739 ) {
740 if (
741 this.board[x + shiftX][y + shiftY] != V.EMPTY &&
742 this.canTake([x, y], [x + shiftX, y + shiftY])
743 ) {
744 this.addPawnMoves(
745 [x, y], [x + shiftX, y + shiftY],
746 moves, promotions
747 );
748 }
749 if (
750 V.PawnSpecs.captureBackward &&
751 x - shiftX >= 0 && x - shiftX < V.size.x &&
752 this.board[x - shiftX][y + shiftY] != V.EMPTY &&
753 this.canTake([x, y], [x - shiftX, y + shiftY])
754 ) {
755 this.addPawnMoves(
756 [x, y], [x + shiftX, y + shiftY],
757 moves, promotions
758 );
759 }
760 }
761 }
762 }
763 }
764 return moves;
765 }
766
767 let pMoves = getPawnMoves(pawnShiftX);
768 if (V.PawnSpecs.bidirectional)
769 pMoves = pMoves.concat(getPawnMoves(-pawnShiftX));
770
771 if (V.HasEnpassant) {
772 // NOTE: backward en-passant captures are not considered
773 // because no rules define them (for now).
774 Array.prototype.push.apply(
775 pMoves,
776 this.getEnpassantCaptures([x, y], pawnShiftX)
777 );
778 }
779
780 return pMoves;
781 }
782
783 // What are the rook moves from square x,y ?
784 getPotentialRookMoves(sq) {
785 return this.getSlideNJumpMoves(sq, V.steps[V.ROOK]);
786 }
787
788 // What are the knight moves from square x,y ?
789 getPotentialKnightMoves(sq) {
790 return this.getSlideNJumpMoves(sq, V.steps[V.KNIGHT], "oneStep");
791 }
792
793 // What are the bishop moves from square x,y ?
794 getPotentialBishopMoves(sq) {
795 return this.getSlideNJumpMoves(sq, V.steps[V.BISHOP]);
796 }
797
798 // What are the queen moves from square x,y ?
799 getPotentialQueenMoves(sq) {
800 return this.getSlideNJumpMoves(
801 sq,
802 V.steps[V.ROOK].concat(V.steps[V.BISHOP])
803 );
804 }
805
806 // What are the king moves from square x,y ?
807 getPotentialKingMoves(sq) {
808 // Initialize with normal moves
809 let moves = this.getSlideNJumpMoves(
810 sq,
811 V.steps[V.ROOK].concat(V.steps[V.BISHOP]),
812 "oneStep"
813 );
814 if (V.HasCastle) moves = moves.concat(this.getCastleMoves(sq));
815 return moves;
816 }
817
818 // "castleInCheck" arg to let some variants castle under check
819 getCastleMoves([x, y], castleInCheck) {
820 const c = this.getColor(x, y);
821 if (x != (c == "w" ? V.size.x - 1 : 0) || y != this.INIT_COL_KING[c])
822 return []; //x isn't first rank, or king has moved (shortcut)
823
824 // Castling ?
825 const oppCol = V.GetOppCol(c);
826 let moves = [];
827 let i = 0;
828 // King, then rook:
829 const finalSquares = [
830 [2, 3],
831 [V.size.y - 2, V.size.y - 3]
832 ];
833 castlingCheck: for (
834 let castleSide = 0;
835 castleSide < 2;
836 castleSide++ //large, then small
837 ) {
838 if (this.castleFlags[c][castleSide] >= V.size.y) continue;
839 // If this code is reached, rook and king are on initial position
840
841 // NOTE: in some variants this is not a rook, but let's keep variable name
842 const rookPos = this.castleFlags[c][castleSide];
843 const castlingPiece = this.getPiece(x, rookPos);
844 if (this.getColor(x, rookPos) != c)
845 // Rook is here but changed color (see Benedict)
846 continue;
847
848 // Nothing on the path of the king ? (and no checks)
849 const finDist = finalSquares[castleSide][0] - y;
850 let step = finDist / Math.max(1, Math.abs(finDist));
851 i = y;
852 do {
853 if (
854 (!castleInCheck && this.isAttacked([x, i], oppCol)) ||
855 (this.board[x][i] != V.EMPTY &&
856 // NOTE: next check is enough, because of chessboard constraints
857 (this.getColor(x, i) != c ||
858 ![V.KING, castlingPiece].includes(this.getPiece(x, i))))
859 ) {
860 continue castlingCheck;
861 }
862 i += step;
863 } while (i != finalSquares[castleSide][0]);
864
865 // Nothing on the path to the rook?
866 step = castleSide == 0 ? -1 : 1;
867 for (i = y + step; i != rookPos; i += step) {
868 if (this.board[x][i] != V.EMPTY) continue castlingCheck;
869 }
870
871 // Nothing on final squares, except maybe king and castling rook?
872 for (i = 0; i < 2; i++) {
873 if (
874 this.board[x][finalSquares[castleSide][i]] != V.EMPTY &&
875 this.getPiece(x, finalSquares[castleSide][i]) != V.KING &&
876 finalSquares[castleSide][i] != rookPos
877 ) {
878 continue castlingCheck;
879 }
880 }
881
882 // If this code is reached, castle is valid
883 moves.push(
884 new Move({
885 appear: [
886 new PiPo({ x: x, y: finalSquares[castleSide][0], p: V.KING, c: c }),
887 new PiPo({ x: x, y: finalSquares[castleSide][1], p: castlingPiece, c: c })
888 ],
889 vanish: [
890 new PiPo({ x: x, y: y, p: V.KING, c: c }),
891 new PiPo({ x: x, y: rookPos, p: castlingPiece, c: c })
892 ],
893 end:
894 Math.abs(y - rookPos) <= 2
895 ? { x: x, y: rookPos }
896 : { x: x, y: y + 2 * (castleSide == 0 ? -1 : 1) }
897 })
898 );
899 }
900
901 return moves;
902 }
903
904 ////////////////////
905 // MOVES VALIDATION
906
907 // For the interface: possible moves for the current turn from square sq
908 getPossibleMovesFrom(sq) {
909 return this.filterValid(this.getPotentialMovesFrom(sq));
910 }
911
912 // TODO: promotions (into R,B,N,Q) should be filtered only once
913 filterValid(moves) {
914 if (moves.length == 0) return [];
915 const color = this.turn;
916 return moves.filter(m => {
917 this.play(m);
918 const res = !this.underCheck(color);
919 this.undo(m);
920 return res;
921 });
922 }
923
924 // Search for all valid moves considering current turn
925 // (for engine and game end)
926 getAllValidMoves() {
927 const color = this.turn;
928 let potentialMoves = [];
929 for (let i = 0; i < V.size.x; i++) {
930 for (let j = 0; j < V.size.y; j++) {
931 if (this.getColor(i, j) == color) {
932 Array.prototype.push.apply(
933 potentialMoves,
934 this.getPotentialMovesFrom([i, j])
935 );
936 }
937 }
938 }
939 return this.filterValid(potentialMoves);
940 }
941
942 // Stop at the first move found
943 atLeastOneMove() {
944 const color = this.turn;
945 for (let i = 0; i < V.size.x; i++) {
946 for (let j = 0; j < V.size.y; j++) {
947 if (this.getColor(i, j) == color) {
948 const moves = this.getPotentialMovesFrom([i, j]);
949 if (moves.length > 0) {
950 for (let k = 0; k < moves.length; k++) {
951 if (this.filterValid([moves[k]]).length > 0) return true;
952 }
953 }
954 }
955 }
956 }
957 return false;
958 }
959
960 // Check if pieces of given color are attacking (king) on square x,y
961 isAttacked(sq, color) {
962 return (
963 this.isAttackedByPawn(sq, color) ||
964 this.isAttackedByRook(sq, color) ||
965 this.isAttackedByKnight(sq, color) ||
966 this.isAttackedByBishop(sq, color) ||
967 this.isAttackedByQueen(sq, color) ||
968 this.isAttackedByKing(sq, color)
969 );
970 }
971
972 // Generic method for non-pawn pieces ("sliding or jumping"):
973 // is x,y attacked by a piece of given color ?
974 isAttackedBySlideNJump([x, y], color, piece, steps, oneStep) {
975 for (let step of steps) {
976 let rx = x + step[0],
977 ry = y + step[1];
978 while (V.OnBoard(rx, ry) && this.board[rx][ry] == V.EMPTY && !oneStep) {
979 rx += step[0];
980 ry += step[1];
981 }
982 if (
983 V.OnBoard(rx, ry) &&
984 this.getPiece(rx, ry) == piece &&
985 this.getColor(rx, ry) == color
986 ) {
987 return true;
988 }
989 }
990 return false;
991 }
992
993 // Is square x,y attacked by 'color' pawns ?
994 isAttackedByPawn([x, y], color) {
995 const pawnShift = (color == "w" ? 1 : -1);
996 if (x + pawnShift >= 0 && x + pawnShift < V.size.x) {
997 for (let i of [-1, 1]) {
998 if (
999 y + i >= 0 &&
1000 y + i < V.size.y &&
1001 this.getPiece(x + pawnShift, y + i) == V.PAWN &&
1002 this.getColor(x + pawnShift, y + i) == color
1003 ) {
1004 return true;
1005 }
1006 }
1007 }
1008 return false;
1009 }
1010
1011 // Is square x,y attacked by 'color' rooks ?
1012 isAttackedByRook(sq, color) {
1013 return this.isAttackedBySlideNJump(sq, color, V.ROOK, V.steps[V.ROOK]);
1014 }
1015
1016 // Is square x,y attacked by 'color' knights ?
1017 isAttackedByKnight(sq, color) {
1018 return this.isAttackedBySlideNJump(
1019 sq,
1020 color,
1021 V.KNIGHT,
1022 V.steps[V.KNIGHT],
1023 "oneStep"
1024 );
1025 }
1026
1027 // Is square x,y attacked by 'color' bishops ?
1028 isAttackedByBishop(sq, color) {
1029 return this.isAttackedBySlideNJump(sq, color, V.BISHOP, V.steps[V.BISHOP]);
1030 }
1031
1032 // Is square x,y attacked by 'color' queens ?
1033 isAttackedByQueen(sq, color) {
1034 return this.isAttackedBySlideNJump(
1035 sq,
1036 color,
1037 V.QUEEN,
1038 V.steps[V.ROOK].concat(V.steps[V.BISHOP])
1039 );
1040 }
1041
1042 // Is square x,y attacked by 'color' king(s) ?
1043 isAttackedByKing(sq, color) {
1044 return this.isAttackedBySlideNJump(
1045 sq,
1046 color,
1047 V.KING,
1048 V.steps[V.ROOK].concat(V.steps[V.BISHOP]),
1049 "oneStep"
1050 );
1051 }
1052
1053 // Is color under check after his move ?
1054 underCheck(color) {
1055 return this.isAttacked(this.kingPos[color], V.GetOppCol(color));
1056 }
1057
1058 /////////////////
1059 // MOVES PLAYING
1060
1061 // Apply a move on board
1062 static PlayOnBoard(board, move) {
1063 for (let psq of move.vanish) board[psq.x][psq.y] = V.EMPTY;
1064 for (let psq of move.appear) board[psq.x][psq.y] = psq.c + psq.p;
1065 }
1066 // Un-apply the played move
1067 static UndoOnBoard(board, move) {
1068 for (let psq of move.appear) board[psq.x][psq.y] = V.EMPTY;
1069 for (let psq of move.vanish) board[psq.x][psq.y] = psq.c + psq.p;
1070 }
1071
1072 prePlay() {}
1073
1074 play(move) {
1075 // DEBUG:
1076 // if (!this.states) this.states = [];
1077 // const stateFen = this.getFen() + JSON.stringify(this.kingPos);
1078 // this.states.push(stateFen);
1079
1080 this.prePlay(move);
1081 if (V.HasFlags) move.flags = JSON.stringify(this.aggregateFlags()); //save flags (for undo)
1082 if (V.HasEnpassant) this.epSquares.push(this.getEpSquare(move));
1083 V.PlayOnBoard(this.board, move);
1084 this.turn = V.GetOppCol(this.turn);
1085 this.movesCount++;
1086 this.postPlay(move);
1087 }
1088
1089 updateCastleFlags(move, piece) {
1090 const c = V.GetOppCol(this.turn);
1091 const firstRank = (c == "w" ? V.size.x - 1 : 0);
1092 // Update castling flags if rooks are moved
1093 const oppCol = V.GetOppCol(c);
1094 const oppFirstRank = V.size.x - 1 - firstRank;
1095 if (piece == V.KING && move.appear.length > 0)
1096 this.castleFlags[c] = [V.size.y, V.size.y];
1097 else if (
1098 move.start.x == firstRank && //our rook moves?
1099 this.castleFlags[c].includes(move.start.y)
1100 ) {
1101 const flagIdx = (move.start.y == this.castleFlags[c][0] ? 0 : 1);
1102 this.castleFlags[c][flagIdx] = V.size.y;
1103 } else if (
1104 move.end.x == oppFirstRank && //we took opponent rook?
1105 this.castleFlags[oppCol].includes(move.end.y)
1106 ) {
1107 const flagIdx = (move.end.y == this.castleFlags[oppCol][0] ? 0 : 1);
1108 this.castleFlags[oppCol][flagIdx] = V.size.y;
1109 }
1110 }
1111
1112 // After move is played, update variables + flags
1113 postPlay(move) {
1114 const c = V.GetOppCol(this.turn);
1115 let piece = undefined;
1116 if (move.vanish.length >= 1)
1117 // Usual case, something is moved
1118 piece = move.vanish[0].p;
1119 else
1120 // Crazyhouse-like variants
1121 piece = move.appear[0].p;
1122
1123 // Update king position + flags
1124 if (piece == V.KING && move.appear.length > 0) {
1125 this.kingPos[c][0] = move.appear[0].x;
1126 this.kingPos[c][1] = move.appear[0].y;
1127 return;
1128 }
1129 if (V.HasCastle) this.updateCastleFlags(move, piece);
1130 }
1131
1132 preUndo() {}
1133
1134 undo(move) {
1135 this.preUndo(move);
1136 if (V.HasEnpassant) this.epSquares.pop();
1137 if (V.HasFlags) this.disaggregateFlags(JSON.parse(move.flags));
1138 V.UndoOnBoard(this.board, move);
1139 this.turn = V.GetOppCol(this.turn);
1140 this.movesCount--;
1141 this.postUndo(move);
1142
1143 // DEBUG:
1144 // const stateFen = this.getFen() + JSON.stringify(this.kingPos);
1145 // if (stateFen != this.states[this.states.length-1]) debugger;
1146 // this.states.pop();
1147 }
1148
1149 // After move is undo-ed *and flags resetted*, un-update other variables
1150 // TODO: more symmetry, by storing flags increment in move (?!)
1151 postUndo(move) {
1152 // (Potentially) Reset king position
1153 const c = this.getColor(move.start.x, move.start.y);
1154 if (this.getPiece(move.start.x, move.start.y) == V.KING)
1155 this.kingPos[c] = [move.start.x, move.start.y];
1156 }
1157
1158 ///////////////
1159 // END OF GAME
1160
1161 // What is the score ? (Interesting if game is over)
1162 getCurrentScore() {
1163 if (this.atLeastOneMove()) return "*";
1164 // Game over
1165 const color = this.turn;
1166 // No valid move: stalemate or checkmate?
1167 if (!this.underCheck(color)) return "1/2";
1168 // OK, checkmate
1169 return (color == "w" ? "0-1" : "1-0");
1170 }
1171
1172 ///////////////
1173 // ENGINE PLAY
1174
1175 // Pieces values
1176 static get VALUES() {
1177 return {
1178 p: 1,
1179 r: 5,
1180 n: 3,
1181 b: 3,
1182 q: 9,
1183 k: 1000
1184 };
1185 }
1186
1187 // "Checkmate" (unreachable eval)
1188 static get INFINITY() {
1189 return 9999;
1190 }
1191
1192 // At this value or above, the game is over
1193 static get THRESHOLD_MATE() {
1194 return V.INFINITY;
1195 }
1196
1197 // Search depth: 1,2 for high branching factor, 4 for small (Loser chess, eg.)
1198 static get SEARCH_DEPTH() {
1199 return 3;
1200 }
1201
1202 getComputerMove() {
1203 const maxeval = V.INFINITY;
1204 const color = this.turn;
1205 let moves1 = this.getAllValidMoves();
1206
1207 if (moves1.length == 0)
1208 // TODO: this situation should not happen
1209 return null;
1210
1211 // Rank moves using a min-max at depth 2 (if search_depth >= 2!)
1212 for (let i = 0; i < moves1.length; i++) {
1213 this.play(moves1[i]);
1214 const score1 = this.getCurrentScore();
1215 if (score1 != "*") {
1216 moves1[i].eval =
1217 score1 == "1/2"
1218 ? 0
1219 : (score1 == "1-0" ? 1 : -1) * maxeval;
1220 }
1221 if (V.SEARCH_DEPTH == 1 || score1 != "*") {
1222 if (!moves1[i].eval) moves1[i].eval = this.evalPosition();
1223 this.undo(moves1[i]);
1224 continue;
1225 }
1226 // Initial self evaluation is very low: "I'm checkmated"
1227 moves1[i].eval = (color == "w" ? -1 : 1) * maxeval;
1228 // Initial enemy evaluation is very low too, for him
1229 let eval2 = (color == "w" ? 1 : -1) * maxeval;
1230 // Second half-move:
1231 let moves2 = this.getAllValidMoves();
1232 for (let j = 0; j < moves2.length; j++) {
1233 this.play(moves2[j]);
1234 const score2 = this.getCurrentScore();
1235 let evalPos = 0; //1/2 value
1236 switch (score2) {
1237 case "*":
1238 evalPos = this.evalPosition();
1239 break;
1240 case "1-0":
1241 evalPos = maxeval;
1242 break;
1243 case "0-1":
1244 evalPos = -maxeval;
1245 break;
1246 }
1247 if (
1248 (color == "w" && evalPos < eval2) ||
1249 (color == "b" && evalPos > eval2)
1250 ) {
1251 eval2 = evalPos;
1252 }
1253 this.undo(moves2[j]);
1254 }
1255 if (
1256 (color == "w" && eval2 > moves1[i].eval) ||
1257 (color == "b" && eval2 < moves1[i].eval)
1258 ) {
1259 moves1[i].eval = eval2;
1260 }
1261 this.undo(moves1[i]);
1262 }
1263 moves1.sort((a, b) => {
1264 return (color == "w" ? 1 : -1) * (b.eval - a.eval);
1265 });
1266 // console.log(moves1.map(m => { return [this.getNotation(m), m.eval]; }));
1267
1268 // Skip depth 3+ if we found a checkmate (or if we are checkmated in 1...)
1269 if (V.SEARCH_DEPTH >= 3 && Math.abs(moves1[0].eval) < V.THRESHOLD_MATE) {
1270 for (let i = 0; i < moves1.length; i++) {
1271 this.play(moves1[i]);
1272 // 0.1 * oldEval : heuristic to avoid some bad moves (not all...)
1273 moves1[i].eval =
1274 0.1 * moves1[i].eval +
1275 this.alphabeta(V.SEARCH_DEPTH - 1, -maxeval, maxeval);
1276 this.undo(moves1[i]);
1277 }
1278 moves1.sort((a, b) => {
1279 return (color == "w" ? 1 : -1) * (b.eval - a.eval);
1280 });
1281 }
1282
1283 let candidates = [0];
1284 for (let j = 1; j < moves1.length && moves1[j].eval == moves1[0].eval; j++)
1285 candidates.push(j);
1286 return moves1[candidates[randInt(candidates.length)]];
1287 }
1288
1289 alphabeta(depth, alpha, beta) {
1290 const maxeval = V.INFINITY;
1291 const color = this.turn;
1292 const score = this.getCurrentScore();
1293 if (score != "*")
1294 return score == "1/2" ? 0 : (score == "1-0" ? 1 : -1) * maxeval;
1295 if (depth == 0) return this.evalPosition();
1296 const moves = this.getAllValidMoves();
1297 let v = color == "w" ? -maxeval : maxeval;
1298 if (color == "w") {
1299 for (let i = 0; i < moves.length; i++) {
1300 this.play(moves[i]);
1301 v = Math.max(v, this.alphabeta(depth - 1, alpha, beta));
1302 this.undo(moves[i]);
1303 alpha = Math.max(alpha, v);
1304 if (alpha >= beta) break; //beta cutoff
1305 }
1306 }
1307 else {
1308 // color=="b"
1309 for (let i = 0; i < moves.length; i++) {
1310 this.play(moves[i]);
1311 v = Math.min(v, this.alphabeta(depth - 1, alpha, beta));
1312 this.undo(moves[i]);
1313 beta = Math.min(beta, v);
1314 if (alpha >= beta) break; //alpha cutoff
1315 }
1316 }
1317 return v;
1318 }
1319
1320 evalPosition() {
1321 let evaluation = 0;
1322 // Just count material for now
1323 for (let i = 0; i < V.size.x; i++) {
1324 for (let j = 0; j < V.size.y; j++) {
1325 if (this.board[i][j] != V.EMPTY) {
1326 const sign = this.getColor(i, j) == "w" ? 1 : -1;
1327 evaluation += sign * V.VALUES[this.getPiece(i, j)];
1328 }
1329 }
1330 }
1331 return evaluation;
1332 }
1333
1334 /////////////////////////
1335 // MOVES + GAME NOTATION
1336 /////////////////////////
1337
1338 // Context: just before move is played, turn hasn't changed
1339 // TODO: un-ambiguous notation (switch on piece type, check directions...)
1340 getNotation(move) {
1341 if (move.appear.length == 2 && move.appear[0].p == V.KING)
1342 // Castle
1343 return move.end.y < move.start.y ? "0-0-0" : "0-0";
1344
1345 // Translate final square
1346 const finalSquare = V.CoordsToSquare(move.end);
1347
1348 const piece = this.getPiece(move.start.x, move.start.y);
1349 if (piece == V.PAWN) {
1350 // Pawn move
1351 let notation = "";
1352 if (move.vanish.length > move.appear.length) {
1353 // Capture
1354 const startColumn = V.CoordToColumn(move.start.y);
1355 notation = startColumn + "x" + finalSquare;
1356 }
1357 else notation = finalSquare;
1358 if (move.appear.length > 0 && move.appear[0].p != V.PAWN)
1359 // Promotion
1360 notation += "=" + move.appear[0].p.toUpperCase();
1361 return notation;
1362 }
1363 // Piece movement
1364 return (
1365 piece.toUpperCase() +
1366 (move.vanish.length > move.appear.length ? "x" : "") +
1367 finalSquare
1368 );
1369 }
1370 };