Some other fixes
[vchess.git] / client / src / base_rules.js
CommitLineData
92342261
BA
1// (Orthodox) Chess rules are defined in ChessRules class.
2// Variants generally inherit from it, and modify some parts.
3
e2732923 4import { ArrayFun } from "@/utils/array";
0c3fe8a6 5import { randInt, shuffle } from "@/utils/alea";
e2732923 6
910d631b 7// class "PiPo": Piece + Position
6808d7a1 8export const PiPo = class PiPo {
1c9f093d 9 // o: {piece[p], color[c], posX[x], posY[y]}
6808d7a1 10 constructor(o) {
1c9f093d
BA
11 this.p = o.p;
12 this.c = o.c;
13 this.x = o.x;
14 this.y = o.y;
15 }
6808d7a1 16};
1d184b4c 17
6808d7a1 18export const Move = class Move {
1c9f093d
BA
19 // o: {appear, vanish, [start,] [end,]}
20 // appear,vanish = arrays of PiPo
21 // start,end = coordinates to apply to trigger move visually (think castle)
6808d7a1 22 constructor(o) {
1c9f093d
BA
23 this.appear = o.appear;
24 this.vanish = o.vanish;
6808d7a1
BA
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 };
1c9f093d 27 }
6808d7a1 28};
1d184b4c
BA
29
30// NOTE: x coords = top to bottom; y = left to right (from white player perspective)
6808d7a1 31export const ChessRules = class ChessRules {
1c9f093d
BA
32 //////////////
33 // MISC UTILS
34
20620465 35 // Some variants don't have flags:
6808d7a1
BA
36 static get HasFlags() {
37 return true;
20620465 38 }
1c9f093d 39
3a2a7b5f
BA
40 // Or castle
41 static get HasCastle() {
42 return V.HasFlags;
43 }
44
32f6285e
BA
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:
6808d7a1
BA
58 static get HasEnpassant() {
59 return true;
20620465
BA
60 }
61
62 // Some variants cannot have analyse mode
8477e53d 63 static get CanAnalyze() {
20620465
BA
64 return true;
65 }
933fd1f9
BA
66 // Patch: issues with javascript OOP, objects can't access static fields.
67 get canAnalyze() {
68 return V.CanAnalyze;
69 }
20620465
BA
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 }
933fd1f9
BA
76 get showMoves() {
77 return V.ShowMoves;
78 }
1c9f093d 79
71ef1664
BA
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
14edde72
BA
88 static get IMAGE_EXTENSION() {
89 // All pieces should be in the SVG format
90 return ".svg";
91 }
92
1c9f093d 93 // Turn "wb" into "B" (for FEN)
6808d7a1
BA
94 static board2fen(b) {
95 return b[0] == "w" ? b[1].toUpperCase() : b[1];
1c9f093d
BA
96 }
97
98 // Turn "p" into "bp" (for board)
6808d7a1
BA
99 static fen2board(f) {
100 return f.charCodeAt() <= 90 ? "w" + f.toLowerCase() : "b" + f;
1c9f093d
BA
101 }
102
68e19a44 103 // Check if FEN describes a board situation correctly
6808d7a1 104 static IsGoodFen(fen) {
1c9f093d
BA
105 const fenParsed = V.ParseFen(fen);
106 // 1) Check position
6808d7a1 107 if (!V.IsGoodPosition(fenParsed.position)) return false;
1c9f093d 108 // 2) Check turn
6808d7a1 109 if (!fenParsed.turn || !V.IsGoodTurn(fenParsed.turn)) return false;
1c9f093d
BA
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
6808d7a1
BA
117 if (
118 V.HasEnpassant &&
119 (!fenParsed.enpassant || !V.IsGoodEnpassant(fenParsed.enpassant))
120 ) {
1c9f093d
BA
121 return false;
122 }
123 return true;
124 }
125
126 // Is position part of the FEN a priori correct?
6808d7a1
BA
127 static IsGoodPosition(position) {
128 if (position.length == 0) return false;
1c9f093d 129 const rows = position.split("/");
6808d7a1 130 if (rows.length != V.size.x) return false;
6f2f9437 131 let kings = { "k": 0, "K": 0 };
6808d7a1 132 for (let row of rows) {
1c9f093d 133 let sumElts = 0;
6808d7a1 134 for (let i = 0; i < row.length; i++) {
6f2f9437 135 if (['K','k'].includes(row[i])) kings[row[i]]++;
6808d7a1
BA
136 if (V.PIECES.includes(row[i].toLowerCase())) sumElts++;
137 else {
1c9f093d 138 const num = parseInt(row[i]);
6808d7a1 139 if (isNaN(num)) return false;
1c9f093d
BA
140 sumElts += num;
141 }
142 }
6808d7a1 143 if (sumElts != V.size.y) return false;
1c9f093d 144 }
6f2f9437
BA
145 // Both kings should be on board. Exactly one per color.
146 if (Object.values(kings).some(v => v != 1)) return false;
1c9f093d
BA
147 return true;
148 }
149
150 // For FEN checking
6808d7a1
BA
151 static IsGoodTurn(turn) {
152 return ["w", "b"].includes(turn);
1c9f093d
BA
153 }
154
155 // For FEN checking
6808d7a1 156 static IsGoodFlags(flags) {
3a2a7b5f
BA
157 // NOTE: a little too permissive to work with more variants
158 return !!flags.match(/^[a-z]{4,4}$/);
1c9f093d
BA
159 }
160
6808d7a1
BA
161 static IsGoodEnpassant(enpassant) {
162 if (enpassant != "-") {
163 const ep = V.SquareToCoords(enpassant);
164 if (isNaN(ep.x) || !V.OnBoard(ep)) return false;
1c9f093d
BA
165 }
166 return true;
167 }
168
169 // 3 --> d (column number to letter)
6808d7a1 170 static CoordToColumn(colnum) {
1c9f093d
BA
171 return String.fromCharCode(97 + colnum);
172 }
173
174 // d --> 3 (column letter to number)
6808d7a1 175 static ColumnToCoord(column) {
1c9f093d
BA
176 return column.charCodeAt(0) - 97;
177 }
178
179 // a4 --> {x:3,y:0}
6808d7a1 180 static SquareToCoords(sq) {
1c9f093d
BA
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
6808d7a1 190 static CoordsToSquare(coords) {
1c9f093d
BA
191 return V.CoordToColumn(coords.y) + (V.size.x - coords.x);
192 }
193
305ede7e 194 // Path to pieces (standard ones in pieces/ folder)
241bf8f2 195 getPpath(b) {
305ede7e 196 return b;
241bf8f2
BA
197 }
198
3a2a7b5f
BA
199 // Path to promotion pieces (usually the same)
200 getPPpath(b) {
201 return this.getPpath(b);
202 }
203
1c9f093d 204 // Aggregates flags into one object
6808d7a1 205 aggregateFlags() {
1c9f093d
BA
206 return this.castleFlags;
207 }
208
209 // Reverse operation
6808d7a1 210 disaggregateFlags(flags) {
1c9f093d
BA
211 this.castleFlags = flags;
212 }
213
214 // En-passant square, if any
6808d7a1
BA
215 getEpSquare(moveOrSquare) {
216 if (!moveOrSquare) return undefined;
217 if (typeof moveOrSquare === "string") {
1c9f093d 218 const square = moveOrSquare;
6808d7a1 219 if (square == "-") return undefined;
1c9f093d
BA
220 return V.SquareToCoords(square);
221 }
222 // Argument is a move:
223 const move = moveOrSquare;
1c5bfdf2
BA
224 const s = move.start,
225 e = move.end;
6808d7a1 226 if (
1c5bfdf2
BA
227 Math.abs(s.x - e.x) == 2 &&
228 s.y == e.y &&
57d9b2c4 229 (move.appear.length > 0 && move.appear[0].p == V.PAWN)
6808d7a1 230 ) {
1c9f093d 231 return {
1c5bfdf2
BA
232 x: (s.x + e.x) / 2,
233 y: s.y
1c9f093d
BA
234 };
235 }
236 return undefined; //default
237 }
238
239 // Can thing on square1 take thing on square2
6808d7a1
BA
240 canTake([x1, y1], [x2, y2]) {
241 return this.getColor(x1, y1) !== this.getColor(x2, y2);
1c9f093d
BA
242 }
243
244 // Is (x,y) on the chessboard?
6808d7a1
BA
245 static OnBoard(x, y) {
246 return x >= 0 && x < V.size.x && y >= 0 && y < V.size.y;
1c9f093d
BA
247 }
248
249 // Used in interface: 'side' arg == player color
6808d7a1
BA
250 canIplay(side, [x, y]) {
251 return this.turn == side && this.getColor(x, y) == side;
1c9f093d
BA
252 }
253
254 // On which squares is color under check ? (for interface)
6808d7a1 255 getCheckSquares(color) {
b0a0468a
BA
256 return (
257 this.underCheck(color)
258 ? [JSON.parse(JSON.stringify(this.kingPos[color]))] //need to duplicate!
259 : []
260 );
1c9f093d
BA
261 }
262
263 /////////////
264 // FEN UTILS
265
7ba4a5bc
BA
266 // Setup the initial random (asymmetric) position
267 static GenRandInitFen(randomness) {
7ba4a5bc
BA
268 if (randomness == 0)
269 // Deterministic:
3a2a7b5f 270 return "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w 0 ahah -";
7ba4a5bc 271
6808d7a1 272 let pieces = { w: new Array(8), b: new Array(8) };
3a2a7b5f 273 let flags = "";
7ba4a5bc 274 // Shuffle pieces on first (and last rank if randomness == 2)
6808d7a1 275 for (let c of ["w", "b"]) {
7ba4a5bc
BA
276 if (c == 'b' && randomness == 1) {
277 pieces['b'] = pieces['w'];
3a2a7b5f 278 flags += flags;
7ba4a5bc
BA
279 break;
280 }
281
1c9f093d
BA
282 let positions = ArrayFun.range(8);
283
284 // Get random squares for bishops
656b1878 285 let randIndex = 2 * randInt(4);
1c9f093d
BA
286 const bishop1Pos = positions[randIndex];
287 // The second bishop must be on a square of different color
656b1878 288 let randIndex_tmp = 2 * randInt(4) + 1;
1c9f093d
BA
289 const bishop2Pos = positions[randIndex_tmp];
290 // Remove chosen squares
6808d7a1
BA
291 positions.splice(Math.max(randIndex, randIndex_tmp), 1);
292 positions.splice(Math.min(randIndex, randIndex_tmp), 1);
1c9f093d
BA
293
294 // Get random squares for knights
656b1878 295 randIndex = randInt(6);
1c9f093d
BA
296 const knight1Pos = positions[randIndex];
297 positions.splice(randIndex, 1);
656b1878 298 randIndex = randInt(5);
1c9f093d
BA
299 const knight2Pos = positions[randIndex];
300 positions.splice(randIndex, 1);
301
302 // Get random square for queen
656b1878 303 randIndex = randInt(4);
1c9f093d
BA
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
6808d7a1
BA
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";
3a2a7b5f 322 flags += V.CoordToColumn(rook1Pos) + V.CoordToColumn(rook2Pos);
1c9f093d 323 }
e3e2cc44 324 // Add turn + flags + enpassant
6808d7a1
BA
325 return (
326 pieces["b"].join("") +
1c9f093d
BA
327 "/pppppppp/8/8/8/8/PPPPPPPP/" +
328 pieces["w"].join("").toUpperCase() +
3a2a7b5f 329 " w 0 " + flags + " -"
e3e2cc44 330 );
1c9f093d
BA
331 }
332
333 // "Parse" FEN: just return untransformed string data
6808d7a1 334 static ParseFen(fen) {
1c9f093d 335 const fenParts = fen.split(" ");
6808d7a1 336 let res = {
1c9f093d
BA
337 position: fenParts[0],
338 turn: fenParts[1],
6808d7a1 339 movesCount: fenParts[2]
1c9f093d
BA
340 };
341 let nextIdx = 3;
6808d7a1
BA
342 if (V.HasFlags) Object.assign(res, { flags: fenParts[nextIdx++] });
343 if (V.HasEnpassant) Object.assign(res, { enpassant: fenParts[nextIdx] });
1c9f093d
BA
344 return res;
345 }
346
347 // Return current fen (game state)
6808d7a1
BA
348 getFen() {
349 return (
f9c36b2d
BA
350 this.getBaseFen() + " " +
351 this.getTurnFen() + " " +
6808d7a1
BA
352 this.movesCount +
353 (V.HasFlags ? " " + this.getFlagsFen() : "") +
354 (V.HasEnpassant ? " " + this.getEnpassantFen() : "")
355 );
1c9f093d
BA
356 }
357
f9c36b2d
BA
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
1c9f093d 368 // Position part of the FEN string
6808d7a1 369 getBaseFen() {
6f2f9437
BA
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 };
1c9f093d 377 let position = "";
6808d7a1 378 for (let i = 0; i < V.size.x; i++) {
1c9f093d 379 let emptyCount = 0;
6808d7a1
BA
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) {
1c9f093d 384 // Add empty squares in-between
6f2f9437 385 position += format(emptyCount);
1c9f093d
BA
386 emptyCount = 0;
387 }
388 position += V.board2fen(this.board[i][j]);
389 }
390 }
6808d7a1 391 if (emptyCount > 0) {
1c9f093d 392 // "Flush remainder"
6f2f9437 393 position += format(emptyCount);
1c9f093d 394 }
6808d7a1 395 if (i < V.size.x - 1) position += "/"; //separate rows
1c9f093d
BA
396 }
397 return position;
398 }
399
6808d7a1 400 getTurnFen() {
1c9f093d
BA
401 return this.turn;
402 }
403
404 // Flags part of the FEN string
6808d7a1 405 getFlagsFen() {
1c9f093d 406 let flags = "";
3a2a7b5f
BA
407 // Castling flags
408 for (let c of ["w", "b"])
409 flags += this.castleFlags[c].map(V.CoordToColumn).join("");
1c9f093d
BA
410 return flags;
411 }
412
413 // Enpassant part of the FEN string
6808d7a1 414 getEnpassantFen() {
1c9f093d 415 const L = this.epSquares.length;
6808d7a1
BA
416 if (!this.epSquares[L - 1]) return "-"; //no en-passant
417 return V.CoordsToSquare(this.epSquares[L - 1]);
1c9f093d
BA
418 }
419
420 // Turn position fen into double array ["wb","wp","bk",...]
6808d7a1 421 static GetBoard(position) {
1c9f093d
BA
422 const rows = position.split("/");
423 let board = ArrayFun.init(V.size.x, V.size.y, "");
6808d7a1 424 for (let i = 0; i < rows.length; i++) {
1c9f093d 425 let j = 0;
6808d7a1 426 for (let indexInRow = 0; indexInRow < rows[i].length; indexInRow++) {
1c9f093d
BA
427 const character = rows[i][indexInRow];
428 const num = parseInt(character);
a13cbc0f 429 // If num is a number, just shift j:
6808d7a1 430 if (!isNaN(num)) j += num;
a13cbc0f 431 // Else: something at position i,j
6808d7a1 432 else board[i][j++] = V.fen2board(character);
1c9f093d
BA
433 }
434 }
435 return board;
436 }
437
438 // Extract (relevant) flags from fen
6808d7a1 439 setFlags(fenflags) {
1c9f093d 440 // white a-castle, h-castle, black a-castle, h-castle
bb688df5 441 this.castleFlags = { w: [-1, -1], b: [-1, -1] };
3a2a7b5f
BA
442 for (let i = 0; i < 4; i++) {
443 this.castleFlags[i < 2 ? "w" : "b"][i % 2] =
444 V.ColumnToCoord(fenflags.charAt(i));
445 }
1c9f093d
BA
446 }
447
448 //////////////////
449 // INITIALIZATION
450
37cdcbf3 451 // Fen string fully describes the game state
b627d118
BA
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;
1c9f093d
BA
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
3a2a7b5f
BA
464 // Scan board for kings positions
465 scanKings(fen) {
6808d7a1 466 this.INIT_COL_KING = { w: -1, b: -1 };
6808d7a1 467 this.kingPos = { w: [-1, -1], b: [-1, -1] }; //squares of white and black king
1c9f093d 468 const fenRows = V.ParseFen(fen).position.split("/");
90e814b6 469 const startRow = { 'w': V.size.x - 1, 'b': 0 };
6808d7a1 470 for (let i = 0; i < fenRows.length; i++) {
1c9f093d 471 let k = 0; //column index on board
6808d7a1
BA
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;
1c9f093d 477 break;
6808d7a1
BA
478 case "K":
479 this.kingPos["w"] = [i, k];
480 this.INIT_COL_KING["w"] = k;
1c9f093d 481 break;
6808d7a1 482 default: {
1c9f093d 483 const num = parseInt(fenRows[i].charAt(j));
6808d7a1
BA
484 if (!isNaN(num)) k += num - 1;
485 }
1c9f093d
BA
486 }
487 k++;
488 }
489 }
490 }
491
492 // Some additional variables from FEN (variant dependant)
6808d7a1 493 setOtherVariables(fen) {
1c9f093d
BA
494 // Set flags and enpassant:
495 const parsedFen = V.ParseFen(fen);
6808d7a1
BA
496 if (V.HasFlags) this.setFlags(parsedFen.flags);
497 if (V.HasEnpassant) {
498 const epSq =
499 parsedFen.enpassant != "-"
9bd6786b 500 ? this.getEpSquare(parsedFen.enpassant)
6808d7a1
BA
501 : undefined;
502 this.epSquares = [epSq];
1c9f093d 503 }
3a2a7b5f
BA
504 // Search for kings positions:
505 this.scanKings(fen);
1c9f093d
BA
506 }
507
508 /////////////////////
509 // GETTERS & SETTERS
510
6808d7a1
BA
511 static get size() {
512 return { x: 8, y: 8 };
1c9f093d
BA
513 }
514
0ba6420d 515 // Color of thing on square (i,j). 'undefined' if square is empty
6808d7a1 516 getColor(i, j) {
1c9f093d
BA
517 return this.board[i][j].charAt(0);
518 }
519
520 // Piece type on square (i,j). 'undefined' if square is empty
6808d7a1 521 getPiece(i, j) {
1c9f093d
BA
522 return this.board[i][j].charAt(1);
523 }
524
525 // Get opponent color
6808d7a1
BA
526 static GetOppCol(color) {
527 return color == "w" ? "b" : "w";
1c9f093d
BA
528 }
529
1c9f093d 530 // Pieces codes (for a clearer code)
6808d7a1
BA
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 }
1c9f093d
BA
549
550 // For FEN checking:
6808d7a1
BA
551 static get PIECES() {
552 return [V.PAWN, V.ROOK, V.KNIGHT, V.BISHOP, V.QUEEN, V.KING];
1c9f093d
BA
553 }
554
555 // Empty square
6808d7a1
BA
556 static get EMPTY() {
557 return "";
558 }
1c9f093d
BA
559
560 // Some pieces movements
6808d7a1 561 static get steps() {
1c9f093d 562 return {
6808d7a1
BA
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 ]
1c9f093d
BA
585 };
586 }
587
588 ////////////////////
589 // MOVES GENERATION
590
0ba6420d 591 // All possible moves from selected square
6808d7a1
BA
592 getPotentialMovesFrom([x, y]) {
593 switch (this.getPiece(x, y)) {
1c9f093d 594 case V.PAWN:
6808d7a1 595 return this.getPotentialPawnMoves([x, y]);
1c9f093d 596 case V.ROOK:
6808d7a1 597 return this.getPotentialRookMoves([x, y]);
1c9f093d 598 case V.KNIGHT:
6808d7a1 599 return this.getPotentialKnightMoves([x, y]);
1c9f093d 600 case V.BISHOP:
6808d7a1 601 return this.getPotentialBishopMoves([x, y]);
1c9f093d 602 case V.QUEEN:
6808d7a1 603 return this.getPotentialQueenMoves([x, y]);
1c9f093d 604 case V.KING:
6808d7a1 605 return this.getPotentialKingMoves([x, y]);
1c9f093d 606 }
6808d7a1 607 return []; //never reached
1c9f093d
BA
608 }
609
610 // Build a regular move from its initial and destination squares.
611 // tr: transformation
6808d7a1 612 getBasicMove([sx, sy], [ex, ey], tr) {
1c58eb76
BA
613 const initColor = this.getColor(sx, sy);
614 const initPiece = this.getPiece(sx, sy);
1c9f093d
BA
615 let mv = new Move({
616 appear: [
617 new PiPo({
618 x: ex,
619 y: ey,
1c58eb76
BA
620 c: tr ? tr.c : initColor,
621 p: tr ? tr.p : initPiece
1c9f093d
BA
622 })
623 ],
624 vanish: [
625 new PiPo({
626 x: sx,
627 y: sy,
1c58eb76
BA
628 c: initColor,
629 p: initPiece
1c9f093d
BA
630 })
631 ]
632 });
633
634 // The opponent piece disappears if we take it
6808d7a1 635 if (this.board[ex][ey] != V.EMPTY) {
1c9f093d
BA
636 mv.vanish.push(
637 new PiPo({
638 x: ex,
639 y: ey,
6808d7a1
BA
640 c: this.getColor(ex, ey),
641 p: this.getPiece(ex, ey)
1c9f093d
BA
642 })
643 );
644 }
1c5bfdf2 645
1c9f093d
BA
646 return mv;
647 }
648
649 // Generic method to find possible moves of non-pawn pieces:
650 // "sliding or jumping"
6808d7a1 651 getSlideNJumpMoves([x, y], steps, oneStep) {
1c9f093d 652 let moves = [];
6808d7a1 653 outerLoop: for (let step of steps) {
1c9f093d
BA
654 let i = x + step[0];
655 let j = y + step[1];
6808d7a1
BA
656 while (V.OnBoard(i, j) && this.board[i][j] == V.EMPTY) {
657 moves.push(this.getBasicMove([x, y], [i, j]));
d1be8046 658 if (oneStep) continue outerLoop;
1c9f093d
BA
659 i += step[0];
660 j += step[1];
661 }
6808d7a1
BA
662 if (V.OnBoard(i, j) && this.canTake([x, y], [i, j]))
663 moves.push(this.getBasicMove([x, y], [i, j]));
1c9f093d
BA
664 }
665 return moves;
666 }
667
32f6285e
BA
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,
8c1ec210 682 // Captured piece is usually a pawn, but next line seems harmless
6f2f9437 683 p: this.getPiece(x, epSquare.y),
32f6285e
BA
684 c: this.getColor(x, epSquare.y)
685 });
686 }
687 return !!enpassantMove ? [enpassantMove] : [];
688 }
689
1c58eb76
BA
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
1c9f093d 708 // What are the pawn moves from square x,y ?
32f6285e 709 getPotentialPawnMoves([x, y], promotions) {
1c9f093d 710 const color = this.turn;
6808d7a1 711 const [sizeX, sizeY] = [V.size.x, V.size.y];
32f6285e 712 const pawnShiftX = V.PawnSpecs.directions[color];
1c58eb76
BA
713 const firstRank = (color == "w" ? sizeX - 1 : 0);
714 const startRank = (color == "w" ? sizeX - 2 : 1);
32f6285e
BA
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
1c58eb76 723 this.addPawnMoves([x, y], [x + shiftX, y], moves, promotions);
32f6285e
BA
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 ) {
1c58eb76
BA
745 this.addPawnMoves(
746 [x, y], [x + shiftX, y + shiftY],
747 moves, promotions
748 );
32f6285e
BA
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 ) {
1c58eb76
BA
756 this.addPawnMoves(
757 [x, y], [x + shiftX, y + shiftY],
758 moves, promotions
759 );
32f6285e
BA
760 }
761 }
1c9f093d
BA
762 }
763 }
764 }
32f6285e 765 return moves;
1c9f093d
BA
766 }
767
32f6285e
BA
768 let pMoves = getPawnMoves(pawnShiftX);
769 if (V.PawnSpecs.bidirectional)
770 pMoves = pMoves.concat(getPawnMoves(-pawnShiftX));
771
6808d7a1 772 if (V.HasEnpassant) {
32f6285e
BA
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 );
1c9f093d
BA
779 }
780
32f6285e 781 return pMoves;
1c9f093d
BA
782 }
783
784 // What are the rook moves from square x,y ?
6808d7a1 785 getPotentialRookMoves(sq) {
1c9f093d
BA
786 return this.getSlideNJumpMoves(sq, V.steps[V.ROOK]);
787 }
788
789 // What are the knight moves from square x,y ?
6808d7a1 790 getPotentialKnightMoves(sq) {
1c9f093d
BA
791 return this.getSlideNJumpMoves(sq, V.steps[V.KNIGHT], "oneStep");
792 }
793
794 // What are the bishop moves from square x,y ?
6808d7a1 795 getPotentialBishopMoves(sq) {
1c9f093d
BA
796 return this.getSlideNJumpMoves(sq, V.steps[V.BISHOP]);
797 }
798
799 // What are the queen moves from square x,y ?
6808d7a1
BA
800 getPotentialQueenMoves(sq) {
801 return this.getSlideNJumpMoves(
802 sq,
803 V.steps[V.ROOK].concat(V.steps[V.BISHOP])
804 );
1c9f093d
BA
805 }
806
807 // What are the king moves from square x,y ?
6808d7a1 808 getPotentialKingMoves(sq) {
1c9f093d 809 // Initialize with normal moves
c583ef1c 810 let moves = this.getSlideNJumpMoves(
6808d7a1
BA
811 sq,
812 V.steps[V.ROOK].concat(V.steps[V.BISHOP]),
813 "oneStep"
814 );
c583ef1c
BA
815 if (V.HasCastle) moves = moves.concat(this.getCastleMoves(sq));
816 return moves;
1c9f093d
BA
817 }
818
a6836242
BA
819 // "castleInCheck" arg to let some variants castle under check
820 getCastleMoves([x, y], castleInCheck) {
6808d7a1
BA
821 const c = this.getColor(x, y);
822 if (x != (c == "w" ? V.size.x - 1 : 0) || y != this.INIT_COL_KING[c])
1c9f093d
BA
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;
9bd6786b 829 // King, then rook:
6808d7a1
BA
830 const finalSquares = [
831 [2, 3],
832 [V.size.y - 2, V.size.y - 3]
9bd6786b 833 ];
6808d7a1
BA
834 castlingCheck: for (
835 let castleSide = 0;
836 castleSide < 2;
837 castleSide++ //large, then small
838 ) {
3a2a7b5f 839 if (this.castleFlags[c][castleSide] >= V.size.y) continue;
3f22c2c3 840 // If this code is reached, rook and king are on initial position
1c9f093d 841
a6836242 842 // NOTE: in some variants this is not a rook, but let's keep variable name
32f6285e 843 const rookPos = this.castleFlags[c][castleSide];
a6836242 844 const castlingPiece = this.getPiece(x, rookPos);
32f6285e
BA
845 if (this.getColor(x, rookPos) != c)
846 // Rook is here but changed color (see Benedict)
847 continue;
848
2beba6db
BA
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;
6808d7a1
BA
853 do {
854 if (
a6836242 855 (!castleInCheck && this.isAttacked([x, i], oppCol)) ||
6808d7a1
BA
856 (this.board[x][i] != V.EMPTY &&
857 // NOTE: next check is enough, because of chessboard constraints
858 (this.getColor(x, i) != c ||
a6836242 859 ![V.KING, castlingPiece].includes(this.getPiece(x, i))))
6808d7a1 860 ) {
1c9f093d
BA
861 continue castlingCheck;
862 }
2beba6db 863 i += step;
6808d7a1 864 } while (i != finalSquares[castleSide][0]);
1c9f093d
BA
865
866 // Nothing on the path to the rook?
6808d7a1 867 step = castleSide == 0 ? -1 : 1;
3a2a7b5f 868 for (i = y + step; i != rookPos; i += step) {
6808d7a1 869 if (this.board[x][i] != V.EMPTY) continue castlingCheck;
1c9f093d 870 }
1c9f093d
BA
871
872 // Nothing on final squares, except maybe king and castling rook?
6808d7a1
BA
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 ) {
1c9f093d
BA
879 continue castlingCheck;
880 }
881 }
882
883 // If this code is reached, castle is valid
6808d7a1
BA
884 moves.push(
885 new Move({
886 appear: [
887 new PiPo({ x: x, y: finalSquares[castleSide][0], p: V.KING, c: c }),
a6836242 888 new PiPo({ x: x, y: finalSquares[castleSide][1], p: castlingPiece, c: c })
6808d7a1
BA
889 ],
890 vanish: [
891 new PiPo({ x: x, y: y, p: V.KING, c: c }),
a6836242 892 new PiPo({ x: x, y: rookPos, p: castlingPiece, c: c })
6808d7a1
BA
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 );
1c9f093d
BA
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
6808d7a1
BA
909 getPossibleMovesFrom(sq) {
910 return this.filterValid(this.getPotentialMovesFrom(sq));
1c9f093d
BA
911 }
912
913 // TODO: promotions (into R,B,N,Q) should be filtered only once
6808d7a1
BA
914 filterValid(moves) {
915 if (moves.length == 0) return [];
1c9f093d
BA
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)
6808d7a1 927 getAllValidMoves() {
1c9f093d 928 const color = this.turn;
1c9f093d 929 let potentialMoves = [];
6808d7a1
BA
930 for (let i = 0; i < V.size.x; i++) {
931 for (let j = 0; j < V.size.y; j++) {
d1be8046 932 if (this.getColor(i, j) == color) {
6808d7a1
BA
933 Array.prototype.push.apply(
934 potentialMoves,
935 this.getPotentialMovesFrom([i, j])
936 );
1c9f093d
BA
937 }
938 }
939 }
940 return this.filterValid(potentialMoves);
941 }
942
943 // Stop at the first move found
6808d7a1 944 atLeastOneMove() {
1c9f093d 945 const color = this.turn;
6808d7a1
BA
946 for (let i = 0; i < V.size.x; i++) {
947 for (let j = 0; j < V.size.y; j++) {
d1be8046 948 if (this.getColor(i, j) == color) {
6808d7a1
BA
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;
1c9f093d
BA
953 }
954 }
955 }
956 }
957 }
958 return false;
959 }
960
68e19a44
BA
961 // Check if pieces of given color are attacking (king) on square x,y
962 isAttacked(sq, color) {
6808d7a1 963 return (
68e19a44
BA
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)
6808d7a1 970 );
1c9f093d
BA
971 }
972
d1be8046 973 // Generic method for non-pawn pieces ("sliding or jumping"):
68e19a44
BA
974 // is x,y attacked by a piece of given color ?
975 isAttackedBySlideNJump([x, y], color, piece, steps, oneStep) {
d1be8046
BA
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) &&
68e19a44
BA
985 this.getPiece(rx, ry) == piece &&
986 this.getColor(rx, ry) == color
d1be8046
BA
987 ) {
988 return true;
989 }
990 }
991 return false;
992 }
993
68e19a44
BA
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;
1c9f093d
BA
1006 }
1007 }
1008 }
1009 return false;
1010 }
1011
68e19a44
BA
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]);
1c9f093d
BA
1015 }
1016
68e19a44
BA
1017 // Is square x,y attacked by 'color' knights ?
1018 isAttackedByKnight(sq, color) {
6808d7a1
BA
1019 return this.isAttackedBySlideNJump(
1020 sq,
68e19a44 1021 color,
6808d7a1
BA
1022 V.KNIGHT,
1023 V.steps[V.KNIGHT],
1024 "oneStep"
1025 );
1c9f093d
BA
1026 }
1027
68e19a44
BA
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]);
1c9f093d
BA
1031 }
1032
68e19a44
BA
1033 // Is square x,y attacked by 'color' queens ?
1034 isAttackedByQueen(sq, color) {
6808d7a1
BA
1035 return this.isAttackedBySlideNJump(
1036 sq,
68e19a44 1037 color,
6808d7a1
BA
1038 V.QUEEN,
1039 V.steps[V.ROOK].concat(V.steps[V.BISHOP])
1040 );
1c9f093d
BA
1041 }
1042
68e19a44
BA
1043 // Is square x,y attacked by 'color' king(s) ?
1044 isAttackedByKing(sq, color) {
6808d7a1
BA
1045 return this.isAttackedBySlideNJump(
1046 sq,
68e19a44 1047 color,
6808d7a1
BA
1048 V.KING,
1049 V.steps[V.ROOK].concat(V.steps[V.BISHOP]),
1050 "oneStep"
1051 );
1c9f093d
BA
1052 }
1053
1c9f093d 1054 // Is color under check after his move ?
6808d7a1 1055 underCheck(color) {
1c58eb76 1056 return this.isAttacked(this.kingPos[color], V.GetOppCol(color));
1c9f093d
BA
1057 }
1058
1059 /////////////////
1060 // MOVES PLAYING
1061
1062 // Apply a move on board
6808d7a1
BA
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;
1c9f093d
BA
1066 }
1067 // Un-apply the played move
6808d7a1
BA
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;
1c9f093d
BA
1071 }
1072
3a2a7b5f
BA
1073 prePlay() {}
1074
1075 play(move) {
1076 // DEBUG:
1077// if (!this.states) this.states = [];
1c58eb76 1078// const stateFen = this.getFen() + JSON.stringify(this.kingPos);
3a2a7b5f
BA
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
bb688df5 1090 updateCastleFlags(move, piece) {
1c58eb76
BA
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;
bb688df5
BA
1096 if (piece == V.KING && move.appear.length > 0)
1097 this.castleFlags[c] = [V.size.y, V.size.y];
1098 else if (
1c58eb76
BA
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;
305ede7e
BA
1104 }
1105 // NOTE: not "else if" because a rook could take an opposing rook
1106 if (
1c58eb76
BA
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
1c9f093d 1115 // After move is played, update variables + flags
3a2a7b5f
BA
1116 postPlay(move) {
1117 const c = V.GetOppCol(this.turn);
1c9f093d 1118 let piece = undefined;
3a2a7b5f 1119 if (move.vanish.length >= 1)
1c9f093d
BA
1120 // Usual case, something is moved
1121 piece = move.vanish[0].p;
3a2a7b5f 1122 else
1c9f093d
BA
1123 // Crazyhouse-like variants
1124 piece = move.appear[0].p;
1c9f093d
BA
1125
1126 // Update king position + flags
6808d7a1 1127 if (piece == V.KING && move.appear.length > 0) {
1c9f093d
BA
1128 this.kingPos[c][0] = move.appear[0].x;
1129 this.kingPos[c][1] = move.appear[0].y;
1c9f093d
BA
1130 return;
1131 }
bb688df5 1132 if (V.HasCastle) this.updateCastleFlags(move, piece);
1c9f093d
BA
1133 }
1134
3a2a7b5f 1135 preUndo() {}
1c9f093d 1136
6808d7a1 1137 undo(move) {
3a2a7b5f 1138 this.preUndo(move);
6808d7a1
BA
1139 if (V.HasEnpassant) this.epSquares.pop();
1140 if (V.HasFlags) this.disaggregateFlags(JSON.parse(move.flags));
1c9f093d
BA
1141 V.UndoOnBoard(this.board, move);
1142 this.turn = V.GetOppCol(this.turn);
1143 this.movesCount--;
3a2a7b5f 1144 this.postUndo(move);
1c9f093d
BA
1145
1146 // DEBUG:
1c58eb76 1147// const stateFen = this.getFen() + JSON.stringify(this.kingPos);
9bd6786b
BA
1148// if (stateFen != this.states[this.states.length-1]) debugger;
1149// this.states.pop();
1c9f093d
BA
1150 }
1151
3a2a7b5f
BA
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
1c9f093d
BA
1161 ///////////////
1162 // END OF GAME
1163
1164 // What is the score ? (Interesting if game is over)
6808d7a1 1165 getCurrentScore() {
bb688df5 1166 if (this.atLeastOneMove()) return "*";
1c9f093d
BA
1167 // Game over
1168 const color = this.turn;
1169 // No valid move: stalemate or checkmate?
bb688df5 1170 if (!this.underCheck(color)) return "1/2";
1c9f093d 1171 // OK, checkmate
68e19a44 1172 return (color == "w" ? "0-1" : "1-0");
1c9f093d
BA
1173 }
1174
1175 ///////////////
1176 // ENGINE PLAY
1177
1178 // Pieces values
6808d7a1 1179 static get VALUES() {
1c9f093d 1180 return {
6808d7a1
BA
1181 p: 1,
1182 r: 5,
1183 n: 3,
1184 b: 3,
1185 q: 9,
1186 k: 1000
1c9f093d
BA
1187 };
1188 }
1189
1190 // "Checkmate" (unreachable eval)
6808d7a1
BA
1191 static get INFINITY() {
1192 return 9999;
1193 }
1c9f093d
BA
1194
1195 // At this value or above, the game is over
6808d7a1
BA
1196 static get THRESHOLD_MATE() {
1197 return V.INFINITY;
1198 }
1c9f093d 1199
6f2f9437 1200 // Search depth: 1,2 for high branching factor, 4 for small (Loser chess, eg.)
6808d7a1
BA
1201 static get SEARCH_DEPTH() {
1202 return 3;
1203 }
1c9f093d 1204
6808d7a1 1205 getComputerMove() {
1c9f093d
BA
1206 const maxeval = V.INFINITY;
1207 const color = this.turn;
a97bdbda 1208 let moves1 = this.getAllValidMoves();
c322a844 1209
6808d7a1 1210 if (moves1.length == 0)
e71161fb 1211 // TODO: this situation should not happen
41cb9b94 1212 return null;
1c9f093d 1213
b83a675a 1214 // Rank moves using a min-max at depth 2 (if search_depth >= 2!)
6808d7a1 1215 for (let i = 0; i < moves1.length; i++) {
afbf3ca7
BA
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]);
b83a675a
BA
1227 continue;
1228 }
1c9f093d 1229 // Initial self evaluation is very low: "I'm checkmated"
6808d7a1 1230 moves1[i].eval = (color == "w" ? -1 : 1) * maxeval;
afbf3ca7
BA
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;
1c9f093d 1249 }
afbf3ca7
BA
1250 if (
1251 (color == "w" && evalPos < eval2) ||
1252 (color == "b" && evalPos > eval2)
1253 ) {
1254 eval2 = evalPos;
1255 }
1256 this.undo(moves2[j]);
1257 }
6808d7a1
BA
1258 if (
1259 (color == "w" && eval2 > moves1[i].eval) ||
1260 (color == "b" && eval2 < moves1[i].eval)
1261 ) {
1c9f093d
BA
1262 moves1[i].eval = eval2;
1263 }
1264 this.undo(moves1[i]);
1265 }
6808d7a1
BA
1266 moves1.sort((a, b) => {
1267 return (color == "w" ? 1 : -1) * (b.eval - a.eval);
1268 });
a97bdbda 1269// console.log(moves1.map(m => { return [this.getNotation(m), m.eval]; }));
1c9f093d 1270
1c9f093d 1271 // Skip depth 3+ if we found a checkmate (or if we are checkmated in 1...)
6808d7a1 1272 if (V.SEARCH_DEPTH >= 3 && Math.abs(moves1[0].eval) < V.THRESHOLD_MATE) {
6808d7a1 1273 for (let i = 0; i < moves1.length; i++) {
1c9f093d
BA
1274 this.play(moves1[i]);
1275 // 0.1 * oldEval : heuristic to avoid some bad moves (not all...)
6808d7a1
BA
1276 moves1[i].eval =
1277 0.1 * moves1[i].eval +
1278 this.alphabeta(V.SEARCH_DEPTH - 1, -maxeval, maxeval);
1c9f093d
BA
1279 this.undo(moves1[i]);
1280 }
6808d7a1
BA
1281 moves1.sort((a, b) => {
1282 return (color == "w" ? 1 : -1) * (b.eval - a.eval);
1283 });
b83a675a 1284 }
1c9f093d 1285
b83a675a 1286 let candidates = [0];
d54f6261
BA
1287 for (let i = 1; i < moves1.length && moves1[i].eval == moves1[0].eval; i++)
1288 candidates.push(i);
656b1878 1289 return moves1[candidates[randInt(candidates.length)]];
1c9f093d
BA
1290 }
1291
6808d7a1 1292 alphabeta(depth, alpha, beta) {
1c9f093d
BA
1293 const maxeval = V.INFINITY;
1294 const color = this.turn;
1295 const score = this.getCurrentScore();
1296 if (score != "*")
6808d7a1
BA
1297 return score == "1/2" ? 0 : (score == "1-0" ? 1 : -1) * maxeval;
1298 if (depth == 0) return this.evalPosition();
a97bdbda 1299 const moves = this.getAllValidMoves();
6808d7a1
BA
1300 let v = color == "w" ? -maxeval : maxeval;
1301 if (color == "w") {
1302 for (let i = 0; i < moves.length; i++) {
1c9f093d 1303 this.play(moves[i]);
6808d7a1 1304 v = Math.max(v, this.alphabeta(depth - 1, alpha, beta));
1c9f093d
BA
1305 this.undo(moves[i]);
1306 alpha = Math.max(alpha, v);
6808d7a1 1307 if (alpha >= beta) break; //beta cutoff
1c9f093d 1308 }
1c5bfdf2 1309 }
6808d7a1 1310 else {
1c5bfdf2 1311 // color=="b"
6808d7a1 1312 for (let i = 0; i < moves.length; i++) {
1c9f093d 1313 this.play(moves[i]);
6808d7a1 1314 v = Math.min(v, this.alphabeta(depth - 1, alpha, beta));
1c9f093d
BA
1315 this.undo(moves[i]);
1316 beta = Math.min(beta, v);
6808d7a1 1317 if (alpha >= beta) break; //alpha cutoff
1c9f093d
BA
1318 }
1319 }
1320 return v;
1321 }
1322
6808d7a1 1323 evalPosition() {
1c9f093d
BA
1324 let evaluation = 0;
1325 // Just count material for now
6808d7a1
BA
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)];
1c9f093d
BA
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...)
6808d7a1
BA
1343 getNotation(move) {
1344 if (move.appear.length == 2 && move.appear[0].p == V.KING)
1cd3e362 1345 // Castle
6808d7a1 1346 return move.end.y < move.start.y ? "0-0-0" : "0-0";
1c9f093d
BA
1347
1348 // Translate final square
1349 const finalSquare = V.CoordsToSquare(move.end);
1350
1351 const piece = this.getPiece(move.start.x, move.start.y);
6808d7a1 1352 if (piece == V.PAWN) {
1c9f093d
BA
1353 // Pawn move
1354 let notation = "";
6808d7a1 1355 if (move.vanish.length > move.appear.length) {
1c9f093d
BA
1356 // Capture
1357 const startColumn = V.CoordToColumn(move.start.y);
1358 notation = startColumn + "x" + finalSquare;
78d64531 1359 }
6808d7a1
BA
1360 else notation = finalSquare;
1361 if (move.appear.length > 0 && move.appear[0].p != V.PAWN)
78d64531 1362 // Promotion
1c9f093d
BA
1363 notation += "=" + move.appear[0].p.toUpperCase();
1364 return notation;
1365 }
6808d7a1
BA
1366 // Piece movement
1367 return (
1368 piece.toUpperCase() +
1369 (move.vanish.length > move.appear.length ? "x" : "") +
1370 finalSquare
1371 );
1372 }
1373};