b83a409b8c37a98d6e366b959a1e64a3a56733cd
[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 = {};
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]] = true;
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:
146 if (Object.keys(kings).length != 2) 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 let position = "";
371 for (let i = 0; i < V.size.x; i++) {
372 let emptyCount = 0;
373 for (let j = 0; j < V.size.y; j++) {
374 if (this.board[i][j] == V.EMPTY) emptyCount++;
375 else {
376 if (emptyCount > 0) {
377 // Add empty squares in-between
378 position += emptyCount;
379 emptyCount = 0;
380 }
381 position += V.board2fen(this.board[i][j]);
382 }
383 }
384 if (emptyCount > 0) {
385 // "Flush remainder"
386 position += emptyCount;
387 }
388 if (i < V.size.x - 1) position += "/"; //separate rows
389 }
390 return position;
391 }
392
393 getTurnFen() {
394 return this.turn;
395 }
396
397 // Flags part of the FEN string
398 getFlagsFen() {
399 let flags = "";
400 // Castling flags
401 for (let c of ["w", "b"])
402 flags += this.castleFlags[c].map(V.CoordToColumn).join("");
403 return flags;
404 }
405
406 // Enpassant part of the FEN string
407 getEnpassantFen() {
408 const L = this.epSquares.length;
409 if (!this.epSquares[L - 1]) return "-"; //no en-passant
410 return V.CoordsToSquare(this.epSquares[L - 1]);
411 }
412
413 // Turn position fen into double array ["wb","wp","bk",...]
414 static GetBoard(position) {
415 const rows = position.split("/");
416 let board = ArrayFun.init(V.size.x, V.size.y, "");
417 for (let i = 0; i < rows.length; i++) {
418 let j = 0;
419 for (let indexInRow = 0; indexInRow < rows[i].length; indexInRow++) {
420 const character = rows[i][indexInRow];
421 const num = parseInt(character);
422 // If num is a number, just shift j:
423 if (!isNaN(num)) j += num;
424 // Else: something at position i,j
425 else board[i][j++] = V.fen2board(character);
426 }
427 }
428 return board;
429 }
430
431 // Extract (relevant) flags from fen
432 setFlags(fenflags) {
433 // white a-castle, h-castle, black a-castle, h-castle
434 this.castleFlags = { w: [-1, -1], b: [-1, -1] };
435 for (let i = 0; i < 4; i++) {
436 this.castleFlags[i < 2 ? "w" : "b"][i % 2] =
437 V.ColumnToCoord(fenflags.charAt(i));
438 }
439 }
440
441 //////////////////
442 // INITIALIZATION
443
444 // Fen string fully describes the game state
445 constructor(fen) {
446 if (!fen)
447 // In printDiagram() fen isn't supply because only getPpath() is used
448 // TODO: find a better solution!
449 return;
450 const fenParsed = V.ParseFen(fen);
451 this.board = V.GetBoard(fenParsed.position);
452 this.turn = fenParsed.turn[0]; //[0] to work with MarseilleRules
453 this.movesCount = parseInt(fenParsed.movesCount);
454 this.setOtherVariables(fen);
455 }
456
457 // Scan board for kings positions
458 scanKings(fen) {
459 this.INIT_COL_KING = { w: -1, b: -1 };
460 this.kingPos = { w: [-1, -1], b: [-1, -1] }; //squares of white and black king
461 const fenRows = V.ParseFen(fen).position.split("/");
462 const startRow = { 'w': V.size.x - 1, 'b': 0 };
463 for (let i = 0; i < fenRows.length; i++) {
464 let k = 0; //column index on board
465 for (let j = 0; j < fenRows[i].length; j++) {
466 switch (fenRows[i].charAt(j)) {
467 case "k":
468 this.kingPos["b"] = [i, k];
469 this.INIT_COL_KING["b"] = k;
470 break;
471 case "K":
472 this.kingPos["w"] = [i, k];
473 this.INIT_COL_KING["w"] = k;
474 break;
475 default: {
476 const num = parseInt(fenRows[i].charAt(j));
477 if (!isNaN(num)) k += num - 1;
478 }
479 }
480 k++;
481 }
482 }
483 }
484
485 // Some additional variables from FEN (variant dependant)
486 setOtherVariables(fen) {
487 // Set flags and enpassant:
488 const parsedFen = V.ParseFen(fen);
489 if (V.HasFlags) this.setFlags(parsedFen.flags);
490 if (V.HasEnpassant) {
491 const epSq =
492 parsedFen.enpassant != "-"
493 ? this.getEpSquare(parsedFen.enpassant)
494 : undefined;
495 this.epSquares = [epSq];
496 }
497 // Search for kings positions:
498 this.scanKings(fen);
499 }
500
501 /////////////////////
502 // GETTERS & SETTERS
503
504 static get size() {
505 return { x: 8, y: 8 };
506 }
507
508 // Color of thing on square (i,j). 'undefined' if square is empty
509 getColor(i, j) {
510 return this.board[i][j].charAt(0);
511 }
512
513 // Piece type on square (i,j). 'undefined' if square is empty
514 getPiece(i, j) {
515 return this.board[i][j].charAt(1);
516 }
517
518 // Get opponent color
519 static GetOppCol(color) {
520 return color == "w" ? "b" : "w";
521 }
522
523 // Pieces codes (for a clearer code)
524 static get PAWN() {
525 return "p";
526 }
527 static get ROOK() {
528 return "r";
529 }
530 static get KNIGHT() {
531 return "n";
532 }
533 static get BISHOP() {
534 return "b";
535 }
536 static get QUEEN() {
537 return "q";
538 }
539 static get KING() {
540 return "k";
541 }
542
543 // For FEN checking:
544 static get PIECES() {
545 return [V.PAWN, V.ROOK, V.KNIGHT, V.BISHOP, V.QUEEN, V.KING];
546 }
547
548 // Empty square
549 static get EMPTY() {
550 return "";
551 }
552
553 // Some pieces movements
554 static get steps() {
555 return {
556 r: [
557 [-1, 0],
558 [1, 0],
559 [0, -1],
560 [0, 1]
561 ],
562 n: [
563 [-1, -2],
564 [-1, 2],
565 [1, -2],
566 [1, 2],
567 [-2, -1],
568 [-2, 1],
569 [2, -1],
570 [2, 1]
571 ],
572 b: [
573 [-1, -1],
574 [-1, 1],
575 [1, -1],
576 [1, 1]
577 ]
578 };
579 }
580
581 ////////////////////
582 // MOVES GENERATION
583
584 // All possible moves from selected square
585 getPotentialMovesFrom([x, y]) {
586 switch (this.getPiece(x, y)) {
587 case V.PAWN:
588 return this.getPotentialPawnMoves([x, y]);
589 case V.ROOK:
590 return this.getPotentialRookMoves([x, y]);
591 case V.KNIGHT:
592 return this.getPotentialKnightMoves([x, y]);
593 case V.BISHOP:
594 return this.getPotentialBishopMoves([x, y]);
595 case V.QUEEN:
596 return this.getPotentialQueenMoves([x, y]);
597 case V.KING:
598 return this.getPotentialKingMoves([x, y]);
599 }
600 return []; //never reached
601 }
602
603 // Build a regular move from its initial and destination squares.
604 // tr: transformation
605 getBasicMove([sx, sy], [ex, ey], tr) {
606 const initColor = this.getColor(sx, sy);
607 const initPiece = this.getPiece(sx, sy);
608 let mv = new Move({
609 appear: [
610 new PiPo({
611 x: ex,
612 y: ey,
613 c: tr ? tr.c : initColor,
614 p: tr ? tr.p : initPiece
615 })
616 ],
617 vanish: [
618 new PiPo({
619 x: sx,
620 y: sy,
621 c: initColor,
622 p: initPiece
623 })
624 ]
625 });
626
627 // The opponent piece disappears if we take it
628 if (this.board[ex][ey] != V.EMPTY) {
629 mv.vanish.push(
630 new PiPo({
631 x: ex,
632 y: ey,
633 c: this.getColor(ex, ey),
634 p: this.getPiece(ex, ey)
635 })
636 );
637 }
638
639 return mv;
640 }
641
642 // Generic method to find possible moves of non-pawn pieces:
643 // "sliding or jumping"
644 getSlideNJumpMoves([x, y], steps, oneStep) {
645 let moves = [];
646 outerLoop: for (let step of steps) {
647 let i = x + step[0];
648 let j = y + step[1];
649 while (V.OnBoard(i, j) && this.board[i][j] == V.EMPTY) {
650 moves.push(this.getBasicMove([x, y], [i, j]));
651 if (oneStep) continue outerLoop;
652 i += step[0];
653 j += step[1];
654 }
655 if (V.OnBoard(i, j) && this.canTake([x, y], [i, j]))
656 moves.push(this.getBasicMove([x, y], [i, j]));
657 }
658 return moves;
659 }
660
661 // Special case of en-passant captures: treated separately
662 getEnpassantCaptures([x, y], shiftX) {
663 const Lep = this.epSquares.length;
664 const epSquare = this.epSquares[Lep - 1]; //always at least one element
665 let enpassantMove = null;
666 if (
667 !!epSquare &&
668 epSquare.x == x + shiftX &&
669 Math.abs(epSquare.y - y) == 1
670 ) {
671 enpassantMove = this.getBasicMove([x, y], [epSquare.x, epSquare.y]);
672 enpassantMove.vanish.push({
673 x: x,
674 y: epSquare.y,
675 p: "p",
676 c: this.getColor(x, epSquare.y)
677 });
678 }
679 return !!enpassantMove ? [enpassantMove] : [];
680 }
681
682 // Consider all potential promotions:
683 addPawnMoves([x1, y1], [x2, y2], moves, promotions) {
684 let finalPieces = [V.PAWN];
685 const color = this.turn;
686 const lastRank = (color == "w" ? 0 : V.size.x - 1);
687 if (x2 == lastRank) {
688 // promotions arg: special override for Hiddenqueen variant
689 if (!!promotions) finalPieces = promotions;
690 else if (!!V.PawnSpecs.promotions)
691 finalPieces = V.PawnSpecs.promotions;
692 }
693 let tr = null;
694 for (let piece of finalPieces) {
695 tr = (piece != V.PAWN ? { c: color, p: piece } : null);
696 moves.push(this.getBasicMove([x1, y1], [x2, y2], tr));
697 }
698 }
699
700 // What are the pawn moves from square x,y ?
701 getPotentialPawnMoves([x, y], promotions) {
702 const color = this.turn;
703 const [sizeX, sizeY] = [V.size.x, V.size.y];
704 const pawnShiftX = V.PawnSpecs.directions[color];
705 const firstRank = (color == "w" ? sizeX - 1 : 0);
706 const startRank = (color == "w" ? sizeX - 2 : 1);
707
708 // Pawn movements in shiftX direction:
709 const getPawnMoves = (shiftX) => {
710 let moves = [];
711 // NOTE: next condition is generally true (no pawn on last rank)
712 if (x + shiftX >= 0 && x + shiftX < sizeX) {
713 if (this.board[x + shiftX][y] == V.EMPTY) {
714 // One square forward
715 this.addPawnMoves([x, y], [x + shiftX, y], moves, promotions);
716 // Next condition because pawns on 1st rank can generally jump
717 if (
718 V.PawnSpecs.twoSquares &&
719 [startRank, firstRank].includes(x) &&
720 this.board[x + 2 * shiftX][y] == V.EMPTY
721 ) {
722 // Two squares jump
723 moves.push(this.getBasicMove([x, y], [x + 2 * shiftX, y]));
724 }
725 }
726 // Captures
727 if (V.PawnSpecs.canCapture) {
728 for (let shiftY of [-1, 1]) {
729 if (
730 y + shiftY >= 0 &&
731 y + shiftY < sizeY
732 ) {
733 if (
734 this.board[x + shiftX][y + shiftY] != V.EMPTY &&
735 this.canTake([x, y], [x + shiftX, y + shiftY])
736 ) {
737 this.addPawnMoves(
738 [x, y], [x + shiftX, y + shiftY],
739 moves, promotions
740 );
741 }
742 if (
743 V.PawnSpecs.captureBackward &&
744 x - shiftX >= 0 && x - shiftX < V.size.x &&
745 this.board[x - shiftX][y + shiftY] != V.EMPTY &&
746 this.canTake([x, y], [x - shiftX, y + shiftY])
747 ) {
748 this.addPawnMoves(
749 [x, y], [x + shiftX, y + shiftY],
750 moves, promotions
751 );
752 }
753 }
754 }
755 }
756 }
757 return moves;
758 }
759
760 let pMoves = getPawnMoves(pawnShiftX);
761 if (V.PawnSpecs.bidirectional)
762 pMoves = pMoves.concat(getPawnMoves(-pawnShiftX));
763
764 if (V.HasEnpassant) {
765 // NOTE: backward en-passant captures are not considered
766 // because no rules define them (for now).
767 Array.prototype.push.apply(
768 pMoves,
769 this.getEnpassantCaptures([x, y], pawnShiftX)
770 );
771 }
772
773 return pMoves;
774 }
775
776 // What are the rook moves from square x,y ?
777 getPotentialRookMoves(sq) {
778 return this.getSlideNJumpMoves(sq, V.steps[V.ROOK]);
779 }
780
781 // What are the knight moves from square x,y ?
782 getPotentialKnightMoves(sq) {
783 return this.getSlideNJumpMoves(sq, V.steps[V.KNIGHT], "oneStep");
784 }
785
786 // What are the bishop moves from square x,y ?
787 getPotentialBishopMoves(sq) {
788 return this.getSlideNJumpMoves(sq, V.steps[V.BISHOP]);
789 }
790
791 // What are the queen moves from square x,y ?
792 getPotentialQueenMoves(sq) {
793 return this.getSlideNJumpMoves(
794 sq,
795 V.steps[V.ROOK].concat(V.steps[V.BISHOP])
796 );
797 }
798
799 // What are the king moves from square x,y ?
800 getPotentialKingMoves(sq) {
801 // Initialize with normal moves
802 let moves = this.getSlideNJumpMoves(
803 sq,
804 V.steps[V.ROOK].concat(V.steps[V.BISHOP]),
805 "oneStep"
806 );
807 if (V.HasCastle) moves = moves.concat(this.getCastleMoves(sq));
808 return moves;
809 }
810
811 // "castleInCheck" arg to let some variants castle under check
812 getCastleMoves([x, y], castleInCheck) {
813 const c = this.getColor(x, y);
814 if (x != (c == "w" ? V.size.x - 1 : 0) || y != this.INIT_COL_KING[c])
815 return []; //x isn't first rank, or king has moved (shortcut)
816
817 // Castling ?
818 const oppCol = V.GetOppCol(c);
819 let moves = [];
820 let i = 0;
821 // King, then rook:
822 const finalSquares = [
823 [2, 3],
824 [V.size.y - 2, V.size.y - 3]
825 ];
826 castlingCheck: for (
827 let castleSide = 0;
828 castleSide < 2;
829 castleSide++ //large, then small
830 ) {
831 if (this.castleFlags[c][castleSide] >= V.size.y) continue;
832 // If this code is reached, rook and king are on initial position
833
834 // NOTE: in some variants this is not a rook, but let's keep variable name
835 const rookPos = this.castleFlags[c][castleSide];
836 const castlingPiece = this.getPiece(x, rookPos);
837 if (this.getColor(x, rookPos) != c)
838 // Rook is here but changed color (see Benedict)
839 continue;
840
841 // Nothing on the path of the king ? (and no checks)
842 const finDist = finalSquares[castleSide][0] - y;
843 let step = finDist / Math.max(1, Math.abs(finDist));
844 i = y;
845 do {
846 if (
847 (!castleInCheck && this.isAttacked([x, i], oppCol)) ||
848 (this.board[x][i] != V.EMPTY &&
849 // NOTE: next check is enough, because of chessboard constraints
850 (this.getColor(x, i) != c ||
851 ![V.KING, castlingPiece].includes(this.getPiece(x, i))))
852 ) {
853 continue castlingCheck;
854 }
855 i += step;
856 } while (i != finalSquares[castleSide][0]);
857
858 // Nothing on the path to the rook?
859 step = castleSide == 0 ? -1 : 1;
860 for (i = y + step; i != rookPos; i += step) {
861 if (this.board[x][i] != V.EMPTY) continue castlingCheck;
862 }
863
864 // Nothing on final squares, except maybe king and castling rook?
865 for (i = 0; i < 2; i++) {
866 if (
867 this.board[x][finalSquares[castleSide][i]] != V.EMPTY &&
868 this.getPiece(x, finalSquares[castleSide][i]) != V.KING &&
869 finalSquares[castleSide][i] != rookPos
870 ) {
871 continue castlingCheck;
872 }
873 }
874
875 // If this code is reached, castle is valid
876 moves.push(
877 new Move({
878 appear: [
879 new PiPo({ x: x, y: finalSquares[castleSide][0], p: V.KING, c: c }),
880 new PiPo({ x: x, y: finalSquares[castleSide][1], p: castlingPiece, c: c })
881 ],
882 vanish: [
883 new PiPo({ x: x, y: y, p: V.KING, c: c }),
884 new PiPo({ x: x, y: rookPos, p: castlingPiece, c: c })
885 ],
886 end:
887 Math.abs(y - rookPos) <= 2
888 ? { x: x, y: rookPos }
889 : { x: x, y: y + 2 * (castleSide == 0 ? -1 : 1) }
890 })
891 );
892 }
893
894 return moves;
895 }
896
897 ////////////////////
898 // MOVES VALIDATION
899
900 // For the interface: possible moves for the current turn from square sq
901 getPossibleMovesFrom(sq) {
902 return this.filterValid(this.getPotentialMovesFrom(sq));
903 }
904
905 // TODO: promotions (into R,B,N,Q) should be filtered only once
906 filterValid(moves) {
907 if (moves.length == 0) return [];
908 const color = this.turn;
909 return moves.filter(m => {
910 this.play(m);
911 const res = !this.underCheck(color);
912 this.undo(m);
913 return res;
914 });
915 }
916
917 // Search for all valid moves considering current turn
918 // (for engine and game end)
919 getAllValidMoves() {
920 const color = this.turn;
921 let potentialMoves = [];
922 for (let i = 0; i < V.size.x; i++) {
923 for (let j = 0; j < V.size.y; j++) {
924 if (this.getColor(i, j) == color) {
925 Array.prototype.push.apply(
926 potentialMoves,
927 this.getPotentialMovesFrom([i, j])
928 );
929 }
930 }
931 }
932 return this.filterValid(potentialMoves);
933 }
934
935 // Stop at the first move found
936 atLeastOneMove() {
937 const color = this.turn;
938 for (let i = 0; i < V.size.x; i++) {
939 for (let j = 0; j < V.size.y; j++) {
940 if (this.getColor(i, j) == color) {
941 const moves = this.getPotentialMovesFrom([i, j]);
942 if (moves.length > 0) {
943 for (let k = 0; k < moves.length; k++) {
944 if (this.filterValid([moves[k]]).length > 0) return true;
945 }
946 }
947 }
948 }
949 }
950 return false;
951 }
952
953 // Check if pieces of given color are attacking (king) on square x,y
954 isAttacked(sq, color) {
955 return (
956 this.isAttackedByPawn(sq, color) ||
957 this.isAttackedByRook(sq, color) ||
958 this.isAttackedByKnight(sq, color) ||
959 this.isAttackedByBishop(sq, color) ||
960 this.isAttackedByQueen(sq, color) ||
961 this.isAttackedByKing(sq, color)
962 );
963 }
964
965 // Generic method for non-pawn pieces ("sliding or jumping"):
966 // is x,y attacked by a piece of given color ?
967 isAttackedBySlideNJump([x, y], color, piece, steps, oneStep) {
968 for (let step of steps) {
969 let rx = x + step[0],
970 ry = y + step[1];
971 while (V.OnBoard(rx, ry) && this.board[rx][ry] == V.EMPTY && !oneStep) {
972 rx += step[0];
973 ry += step[1];
974 }
975 if (
976 V.OnBoard(rx, ry) &&
977 this.getPiece(rx, ry) == piece &&
978 this.getColor(rx, ry) == color
979 ) {
980 return true;
981 }
982 }
983 return false;
984 }
985
986 // Is square x,y attacked by 'color' pawns ?
987 isAttackedByPawn([x, y], color) {
988 const pawnShift = (color == "w" ? 1 : -1);
989 if (x + pawnShift >= 0 && x + pawnShift < V.size.x) {
990 for (let i of [-1, 1]) {
991 if (
992 y + i >= 0 &&
993 y + i < V.size.y &&
994 this.getPiece(x + pawnShift, y + i) == V.PAWN &&
995 this.getColor(x + pawnShift, y + i) == color
996 ) {
997 return true;
998 }
999 }
1000 }
1001 return false;
1002 }
1003
1004 // Is square x,y attacked by 'color' rooks ?
1005 isAttackedByRook(sq, color) {
1006 return this.isAttackedBySlideNJump(sq, color, V.ROOK, V.steps[V.ROOK]);
1007 }
1008
1009 // Is square x,y attacked by 'color' knights ?
1010 isAttackedByKnight(sq, color) {
1011 return this.isAttackedBySlideNJump(
1012 sq,
1013 color,
1014 V.KNIGHT,
1015 V.steps[V.KNIGHT],
1016 "oneStep"
1017 );
1018 }
1019
1020 // Is square x,y attacked by 'color' bishops ?
1021 isAttackedByBishop(sq, color) {
1022 return this.isAttackedBySlideNJump(sq, color, V.BISHOP, V.steps[V.BISHOP]);
1023 }
1024
1025 // Is square x,y attacked by 'color' queens ?
1026 isAttackedByQueen(sq, color) {
1027 return this.isAttackedBySlideNJump(
1028 sq,
1029 color,
1030 V.QUEEN,
1031 V.steps[V.ROOK].concat(V.steps[V.BISHOP])
1032 );
1033 }
1034
1035 // Is square x,y attacked by 'color' king(s) ?
1036 isAttackedByKing(sq, color) {
1037 return this.isAttackedBySlideNJump(
1038 sq,
1039 color,
1040 V.KING,
1041 V.steps[V.ROOK].concat(V.steps[V.BISHOP]),
1042 "oneStep"
1043 );
1044 }
1045
1046 // Is color under check after his move ?
1047 underCheck(color) {
1048 return this.isAttacked(this.kingPos[color], V.GetOppCol(color));
1049 }
1050
1051 /////////////////
1052 // MOVES PLAYING
1053
1054 // Apply a move on board
1055 static PlayOnBoard(board, move) {
1056 for (let psq of move.vanish) board[psq.x][psq.y] = V.EMPTY;
1057 for (let psq of move.appear) board[psq.x][psq.y] = psq.c + psq.p;
1058 }
1059 // Un-apply the played move
1060 static UndoOnBoard(board, move) {
1061 for (let psq of move.appear) board[psq.x][psq.y] = V.EMPTY;
1062 for (let psq of move.vanish) board[psq.x][psq.y] = psq.c + psq.p;
1063 }
1064
1065 prePlay() {}
1066
1067 play(move) {
1068 // DEBUG:
1069 // if (!this.states) this.states = [];
1070 // const stateFen = this.getFen() + JSON.stringify(this.kingPos);
1071 // this.states.push(stateFen);
1072
1073 this.prePlay(move);
1074 if (V.HasFlags) move.flags = JSON.stringify(this.aggregateFlags()); //save flags (for undo)
1075 if (V.HasEnpassant) this.epSquares.push(this.getEpSquare(move));
1076 V.PlayOnBoard(this.board, move);
1077 this.turn = V.GetOppCol(this.turn);
1078 this.movesCount++;
1079 this.postPlay(move);
1080 }
1081
1082 updateCastleFlags(move, piece) {
1083 const c = V.GetOppCol(this.turn);
1084 const firstRank = (c == "w" ? V.size.x - 1 : 0);
1085 // Update castling flags if rooks are moved
1086 const oppCol = V.GetOppCol(c);
1087 const oppFirstRank = V.size.x - 1 - firstRank;
1088 if (piece == V.KING && move.appear.length > 0)
1089 this.castleFlags[c] = [V.size.y, V.size.y];
1090 else if (
1091 move.start.x == firstRank && //our rook moves?
1092 this.castleFlags[c].includes(move.start.y)
1093 ) {
1094 const flagIdx = (move.start.y == this.castleFlags[c][0] ? 0 : 1);
1095 this.castleFlags[c][flagIdx] = V.size.y;
1096 } else if (
1097 move.end.x == oppFirstRank && //we took opponent rook?
1098 this.castleFlags[oppCol].includes(move.end.y)
1099 ) {
1100 const flagIdx = (move.end.y == this.castleFlags[oppCol][0] ? 0 : 1);
1101 this.castleFlags[oppCol][flagIdx] = V.size.y;
1102 }
1103 }
1104
1105 // After move is played, update variables + flags
1106 postPlay(move) {
1107 const c = V.GetOppCol(this.turn);
1108 let piece = undefined;
1109 if (move.vanish.length >= 1)
1110 // Usual case, something is moved
1111 piece = move.vanish[0].p;
1112 else
1113 // Crazyhouse-like variants
1114 piece = move.appear[0].p;
1115
1116 // Update king position + flags
1117 if (piece == V.KING && move.appear.length > 0) {
1118 this.kingPos[c][0] = move.appear[0].x;
1119 this.kingPos[c][1] = move.appear[0].y;
1120 return;
1121 }
1122 if (V.HasCastle) this.updateCastleFlags(move, piece);
1123 }
1124
1125 preUndo() {}
1126
1127 undo(move) {
1128 this.preUndo(move);
1129 if (V.HasEnpassant) this.epSquares.pop();
1130 if (V.HasFlags) this.disaggregateFlags(JSON.parse(move.flags));
1131 V.UndoOnBoard(this.board, move);
1132 this.turn = V.GetOppCol(this.turn);
1133 this.movesCount--;
1134 this.postUndo(move);
1135
1136 // DEBUG:
1137 // const stateFen = this.getFen() + JSON.stringify(this.kingPos);
1138 // if (stateFen != this.states[this.states.length-1]) debugger;
1139 // this.states.pop();
1140 }
1141
1142 // After move is undo-ed *and flags resetted*, un-update other variables
1143 // TODO: more symmetry, by storing flags increment in move (?!)
1144 postUndo(move) {
1145 // (Potentially) Reset king position
1146 const c = this.getColor(move.start.x, move.start.y);
1147 if (this.getPiece(move.start.x, move.start.y) == V.KING)
1148 this.kingPos[c] = [move.start.x, move.start.y];
1149 }
1150
1151 ///////////////
1152 // END OF GAME
1153
1154 // What is the score ? (Interesting if game is over)
1155 getCurrentScore() {
1156 if (this.atLeastOneMove()) return "*";
1157 // Game over
1158 const color = this.turn;
1159 // No valid move: stalemate or checkmate?
1160 if (!this.underCheck(color)) return "1/2";
1161 // OK, checkmate
1162 return (color == "w" ? "0-1" : "1-0");
1163 }
1164
1165 ///////////////
1166 // ENGINE PLAY
1167
1168 // Pieces values
1169 static get VALUES() {
1170 return {
1171 p: 1,
1172 r: 5,
1173 n: 3,
1174 b: 3,
1175 q: 9,
1176 k: 1000
1177 };
1178 }
1179
1180 // "Checkmate" (unreachable eval)
1181 static get INFINITY() {
1182 return 9999;
1183 }
1184
1185 // At this value or above, the game is over
1186 static get THRESHOLD_MATE() {
1187 return V.INFINITY;
1188 }
1189
1190 // Search depth: 2 for high branching factor, 4 for small (Loser chess, eg.)
1191 static get SEARCH_DEPTH() {
1192 return 3;
1193 }
1194
1195 getComputerMove() {
1196 const maxeval = V.INFINITY;
1197 const color = this.turn;
1198 let moves1 = this.getAllValidMoves();
1199
1200 if (moves1.length == 0)
1201 // TODO: this situation should not happen
1202 return null;
1203
1204 // Rank moves using a min-max at depth 2 (if search_depth >= 2!)
1205 for (let i = 0; i < moves1.length; i++) {
1206 this.play(moves1[i]);
1207 const score1 = this.getCurrentScore();
1208 if (score1 != "*") {
1209 moves1[i].eval =
1210 score1 == "1/2"
1211 ? 0
1212 : (score1 == "1-0" ? 1 : -1) * maxeval;
1213 }
1214 if (V.SEARCH_DEPTH == 1 || score1 != "*") {
1215 if (!moves1[i].eval) moves1[i].eval = this.evalPosition();
1216 this.undo(moves1[i]);
1217 continue;
1218 }
1219 // Initial self evaluation is very low: "I'm checkmated"
1220 moves1[i].eval = (color == "w" ? -1 : 1) * maxeval;
1221 // Initial enemy evaluation is very low too, for him
1222 let eval2 = (color == "w" ? 1 : -1) * maxeval;
1223 // Second half-move:
1224 let moves2 = this.getAllValidMoves();
1225 for (let j = 0; j < moves2.length; j++) {
1226 this.play(moves2[j]);
1227 const score2 = this.getCurrentScore();
1228 let evalPos = 0; //1/2 value
1229 switch (score2) {
1230 case "*":
1231 evalPos = this.evalPosition();
1232 break;
1233 case "1-0":
1234 evalPos = maxeval;
1235 break;
1236 case "0-1":
1237 evalPos = -maxeval;
1238 break;
1239 }
1240 if (
1241 (color == "w" && evalPos < eval2) ||
1242 (color == "b" && evalPos > eval2)
1243 ) {
1244 eval2 = evalPos;
1245 }
1246 this.undo(moves2[j]);
1247 }
1248 if (
1249 (color == "w" && eval2 > moves1[i].eval) ||
1250 (color == "b" && eval2 < moves1[i].eval)
1251 ) {
1252 moves1[i].eval = eval2;
1253 }
1254 this.undo(moves1[i]);
1255 }
1256 moves1.sort((a, b) => {
1257 return (color == "w" ? 1 : -1) * (b.eval - a.eval);
1258 });
1259 // console.log(moves1.map(m => { return [this.getNotation(m), m.eval]; }));
1260
1261 // Skip depth 3+ if we found a checkmate (or if we are checkmated in 1...)
1262 if (V.SEARCH_DEPTH >= 3 && Math.abs(moves1[0].eval) < V.THRESHOLD_MATE) {
1263 for (let i = 0; i < moves1.length; i++) {
1264 this.play(moves1[i]);
1265 // 0.1 * oldEval : heuristic to avoid some bad moves (not all...)
1266 moves1[i].eval =
1267 0.1 * moves1[i].eval +
1268 this.alphabeta(V.SEARCH_DEPTH - 1, -maxeval, maxeval);
1269 this.undo(moves1[i]);
1270 }
1271 moves1.sort((a, b) => {
1272 return (color == "w" ? 1 : -1) * (b.eval - a.eval);
1273 });
1274 }
1275
1276 let candidates = [0];
1277 for (let j = 1; j < moves1.length && moves1[j].eval == moves1[0].eval; j++)
1278 candidates.push(j);
1279 return moves1[candidates[randInt(candidates.length)]];
1280 }
1281
1282 alphabeta(depth, alpha, beta) {
1283 const maxeval = V.INFINITY;
1284 const color = this.turn;
1285 const score = this.getCurrentScore();
1286 if (score != "*")
1287 return score == "1/2" ? 0 : (score == "1-0" ? 1 : -1) * maxeval;
1288 if (depth == 0) return this.evalPosition();
1289 const moves = this.getAllValidMoves();
1290 let v = color == "w" ? -maxeval : maxeval;
1291 if (color == "w") {
1292 for (let i = 0; i < moves.length; i++) {
1293 this.play(moves[i]);
1294 v = Math.max(v, this.alphabeta(depth - 1, alpha, beta));
1295 this.undo(moves[i]);
1296 alpha = Math.max(alpha, v);
1297 if (alpha >= beta) break; //beta cutoff
1298 }
1299 }
1300 else {
1301 // color=="b"
1302 for (let i = 0; i < moves.length; i++) {
1303 this.play(moves[i]);
1304 v = Math.min(v, this.alphabeta(depth - 1, alpha, beta));
1305 this.undo(moves[i]);
1306 beta = Math.min(beta, v);
1307 if (alpha >= beta) break; //alpha cutoff
1308 }
1309 }
1310 return v;
1311 }
1312
1313 evalPosition() {
1314 let evaluation = 0;
1315 // Just count material for now
1316 for (let i = 0; i < V.size.x; i++) {
1317 for (let j = 0; j < V.size.y; j++) {
1318 if (this.board[i][j] != V.EMPTY) {
1319 const sign = this.getColor(i, j) == "w" ? 1 : -1;
1320 evaluation += sign * V.VALUES[this.getPiece(i, j)];
1321 }
1322 }
1323 }
1324 return evaluation;
1325 }
1326
1327 /////////////////////////
1328 // MOVES + GAME NOTATION
1329 /////////////////////////
1330
1331 // Context: just before move is played, turn hasn't changed
1332 // TODO: un-ambiguous notation (switch on piece type, check directions...)
1333 getNotation(move) {
1334 if (move.appear.length == 2 && move.appear[0].p == V.KING)
1335 // Castle
1336 return move.end.y < move.start.y ? "0-0-0" : "0-0";
1337
1338 // Translate final square
1339 const finalSquare = V.CoordsToSquare(move.end);
1340
1341 const piece = this.getPiece(move.start.x, move.start.y);
1342 if (piece == V.PAWN) {
1343 // Pawn move
1344 let notation = "";
1345 if (move.vanish.length > move.appear.length) {
1346 // Capture
1347 const startColumn = V.CoordToColumn(move.start.y);
1348 notation = startColumn + "x" + finalSquare;
1349 }
1350 else notation = finalSquare;
1351 if (move.appear.length > 0 && move.appear[0].p != V.PAWN)
1352 // Promotion
1353 notation += "=" + move.appear[0].p.toUpperCase();
1354 return notation;
1355 }
1356 // Piece movement
1357 return (
1358 piece.toUpperCase() +
1359 (move.vanish.length > move.appear.length ? "x" : "") +
1360 finalSquare
1361 );
1362 }
1363 };