File indexing completed on 2024-04-28 15:07:47
0001 /* p4wn, AKA 5k chess - by Douglas Bagnall <douglas@paradise.net.nz> 0002 * 0003 * SPDX-FileCopyrightText: 2002 Douglas Bagnall <douglas@paradise.net.nz> 0004 * 0005 * SPDX-License-Identifier: Unlicense 0006 * 0007 * This code is in the public domain, or as close to it as various 0008 * laws allow. No warranty; no restrictions. 0009 * 0010 * lives at http://p4wn.sf.net/ 0011 */ 0012 0013 /*Compatibility tricks: 0014 * backwards for old MSIEs (to 5.5) 0015 * sideways for seed command-line javascript.*/ 0016 var p4_log; 0017 if (this.imports !== undefined && 0018 this.printerr !== undefined){//seed or gjs 0019 p4_log = function(){ 0020 var args = Array.prototype.slice.call(arguments); 0021 printerr(args.join(', ')); 0022 }; 0023 } 0024 else if (this.console === undefined){//MSIE 0025 p4_log = function(){}; 0026 } 0027 else { 0028 // disable the console 0029 p4_log = function(){}; 0030 //p4_log = function(){console.log.apply(console, arguments);}; 0031 } 0032 0033 /*MSIE Date.now backport */ 0034 if (Date.now === undefined) 0035 Date.now = function(){return (new Date).getTime();}; 0036 0037 /* The pieces are stored as numbers between 2 and 13, inclusive. 0038 * Empty squares are stored as 0, and off-board squares as 16. 0039 * There is some bitwise logic to it: 0040 * piece & 1 -> colour (white: 0, black: 1) 0041 * piece & 2 -> single move piece (including pawn) 0042 * if (piece & 2) == 0: 0043 * piece & 4 -> row and column moves 0044 * piece & 8 -> diagonal moves 0045 */ 0046 var P4_PAWN = 2, P4_ROOK = 4, P4_KNIGHT = 6, P4_BISHOP = 8, P4_QUEEN = 12, P4_KING = 10; 0047 var P4_EDGE = 16; 0048 0049 /* in order, even indices: <nothing>, pawn, rook, knight, bishop, king, queen. Only the 0050 * even indices are used.*/ 0051 var P4_MOVES = [[], [], 0052 [], [], 0053 [1,10,-1,-10], [], 0054 [21,19,12,8,-21,-19,-12,-8], [], 0055 [11,9,-11,-9], [], 0056 [1,10,11,9,-1,-10,-11,-9], [], 0057 [1,10,11,9,-1,-10,-11,-9], [] 0058 ]; 0059 0060 /*P4_VALUES defines the relative value of various pieces. 0061 * 0062 * It follows the 1,3,3,5,9 pattern you learn as a kid, multiplied by 0063 * 20 to give sub-pawn resolution to other factors, with bishops given 0064 * a wee boost over knights. 0065 */ 0066 var P4_VALUES=[0, 0, //Piece values 0067 20, 20, //pawns 0068 100, 100, //rooks 0069 60, 60, //knights 0070 61, 61, //bishops 0071 8000, 8000,//kings 0072 180, 180, //queens 0073 0]; 0074 0075 /* A score greater than P4_WIN indicates a king has been taken. It is 0076 * less than the value of a king, in case someone finds a way to, say, 0077 * sacrifice two queens in order to checkmate. 0078 */ 0079 var P4_KING_VALUE = P4_VALUES[10]; 0080 var P4_WIN = P4_KING_VALUE >> 1; 0081 0082 /* every move, a winning score decreases by this much */ 0083 var P4_WIN_DECAY = 300; 0084 var P4_WIN_NOW = P4_KING_VALUE - 250; 0085 0086 /* P4_{MAX,MIN}_SCORE should be beyond any possible evaluated score */ 0087 0088 var P4_MAX_SCORE = 9999; // extremes of evaluation range 0089 var P4_MIN_SCORE = -P4_MAX_SCORE; 0090 0091 /*initialised in p4_initialise_state */ 0092 var P4_CENTRALISING_WEIGHTS; 0093 var P4_BASE_PAWN_WEIGHTS; 0094 var P4_KNIGHT_WEIGHTS; 0095 0096 /*P4_DEBUG turns on debugging features */ 0097 var P4_DEBUG = 0; 0098 var P4_INITIAL_BOARD = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 1 1"; 0099 0100 /*use javascript typed arrays rather than plain arrays 0101 * (faster in some browsers, unsupported in others, possibly slower elsewhere) */ 0102 var P4_USE_TYPED_ARRAYS = this.Int32Array !== undefined; 0103 0104 var P4_PIECE_LUT = { /*for FEN, PGN interpretation */ 0105 P: 2, 0106 p: 3, 0107 R: 4, 0108 r: 5, 0109 N: 6, 0110 n: 7, 0111 B: 8, 0112 b: 9, 0113 K: 10, 0114 k: 11, 0115 Q: 12, 0116 q: 13 0117 }; 0118 0119 var P4_ENCODE_LUT = ' PPRRNNBBKKQQ'; 0120 0121 0122 function p4_alphabeta_treeclimber(state, count, colour, score, s, e, alpha, beta){ 0123 var move = p4_make_move(state, s, e, P4_QUEEN); 0124 var i; 0125 var ncolour = 1 - colour; 0126 var movelist = p4_parse(state, colour, move.ep, -score); 0127 var movecount = movelist.length; 0128 if(count){ 0129 //branch nodes 0130 var t; 0131 for(i = 0; i < movecount; i++){ 0132 var mv = movelist[i]; 0133 var mscore = mv[0]; 0134 var ms = mv[1]; 0135 var me = mv[2]; 0136 if (mscore > P4_WIN){ //we won! Don't look further. 0137 alpha = P4_KING_VALUE; 0138 break; 0139 } 0140 t = -p4_alphabeta_treeclimber(state, count - 1, ncolour, mscore, ms, me, 0141 -beta, -alpha); 0142 if (t > alpha){ 0143 alpha = t; 0144 } 0145 if (alpha >= beta){ 0146 break; 0147 } 0148 } 0149 if (alpha < -P4_WIN_NOW && ! p4_check_check(state, colour)){ 0150 /* Whatever we do, we lose the king. 0151 * But if it is not check then this is stalemate, and the 0152 * score doesn't apply. 0153 */ 0154 alpha = state.stalemate_scores[colour]; 0155 } 0156 if (alpha < -P4_WIN){ 0157 /*make distant checkmate seem less bad */ 0158 alpha += P4_WIN_DECAY; 0159 } 0160 } 0161 else{ 0162 //leaf nodes 0163 while(beta > alpha && --movecount != -1){ 0164 if(movelist[movecount][0] > alpha){ 0165 alpha = movelist[movecount][0]; 0166 } 0167 } 0168 } 0169 p4_unmake_move(state, move); 0170 return alpha; 0171 } 0172 0173 0174 /* p4_prepare() works out weightings for assessing various moves, 0175 * favouring centralising moves early, for example. 0176 * 0177 * It is called before each tree search, not for each parse(), so it 0178 * is OK for it to be a little bit slow. But that also means it drifts 0179 * out of sync with the real board state, especially on deep searches. 0180 */ 0181 0182 function p4_prepare(state){ 0183 var i, j, x, y, a; 0184 var pieces = state.pieces = [[], []]; 0185 /*convert state.moveno half move count to move cycle count */ 0186 var moveno = state.moveno >> 1; 0187 var board = state.board; 0188 0189 /* high earliness_weight indicates a low move number. The formula 0190 * should work above moveno == 50, but this is javascript. 0191 */ 0192 var earliness_weight = (moveno > 50) ? 0 : parseInt(6 * Math.exp(moveno * -0.07)); 0193 var king_should_hide = moveno < 12; 0194 var early = moveno < 5; 0195 /* find the pieces, kings, and weigh material*/ 0196 var kings = [0, 0]; 0197 var material = [0, 0]; 0198 var best_pieces = [0, 0]; 0199 for(i = 20; i < 100; i++){ 0200 a = board[i]; 0201 var piece = a & 14; 0202 var colour = a & 1; 0203 if(piece){ 0204 pieces[colour].push([a, i]); 0205 if (piece == P4_KING){ 0206 kings[colour] = i; 0207 } 0208 else{ 0209 material[colour] += P4_VALUES[piece]; 0210 best_pieces[colour] = Math.max(best_pieces[colour], P4_VALUES[piece]); 0211 } 0212 } 0213 } 0214 0215 /*does a draw seem likely soon?*/ 0216 var draw_likely = (state.draw_timeout > 90 || state.current_repetitions >= 2); 0217 if (draw_likely) 0218 p4_log("draw likely", state.current_repetitions, state.draw_timeout); 0219 state.values = [[], []]; 0220 var qvalue = P4_VALUES[P4_QUEEN]; /*used as ballast in various ratios*/ 0221 var material_sum = material[0] + material[1] + 2 * qvalue; 0222 var wmul = 2 * (material[1] + qvalue) / material_sum; 0223 var bmul = 2 * (material[0] + qvalue) / material_sum; 0224 var multipliers = [wmul, bmul]; 0225 var emptiness = 4 * P4_QUEEN / material_sum; 0226 state.stalemate_scores = [parseInt(0.5 + (wmul - 1) * 2 * qvalue), 0227 parseInt(0.5 + (bmul - 1) * 2 * qvalue)]; 0228 //p4_log("value multipliers (W, B):", wmul, bmul, 0229 // "stalemate scores", state.stalemate_scores); 0230 for (i = 0; i < P4_VALUES.length; i++){ 0231 var v = P4_VALUES[i]; 0232 if (v < P4_WIN){//i.e., not king 0233 state.values[0][i] = parseInt(v * wmul + 0.5); 0234 state.values[1][i] = parseInt(v * bmul + 0.5); 0235 } 0236 else { 0237 state.values[0][i] = v; 0238 state.values[1][i] = v; 0239 } 0240 } 0241 /*used for pruning quiescence search */ 0242 state.best_pieces = [parseInt(best_pieces[0] * wmul + 0.5), 0243 parseInt(best_pieces[1] * bmul + 0.5)]; 0244 0245 var kx = [kings[0] % 10, kings[1] % 10]; 0246 var ky = [parseInt(kings[0] / 10), parseInt(kings[1] / 10)]; 0247 0248 /* find the frontmost pawns in each file */ 0249 var pawn_cols = [[], []]; 0250 for (y = 3; y < 9; y++){ 0251 for (x = 1; x < 9; x++){ 0252 i = y * 10 + x; 0253 a = board[i]; 0254 if ((a & 14) != P4_PAWN) 0255 continue; 0256 if ((a & 1) == 0){ 0257 pawn_cols[0][x] = y; 0258 } 0259 else if (pawn_cols[1][x] === undefined){ 0260 pawn_cols[1][x] = y; 0261 } 0262 } 0263 } 0264 var target_king = (moveno >= 20 || material_sum < 5 * qvalue); 0265 var weights = state.weights; 0266 0267 for (y = 2; y < 10; y++){ 0268 for (x = 1; x < 9; x++){ 0269 i = y * 10 + x; 0270 var early_centre = P4_CENTRALISING_WEIGHTS[i] * earliness_weight; 0271 var plateau = P4_KNIGHT_WEIGHTS[i]; 0272 for (var c = 0; c < 2; c++){ 0273 var dx = Math.abs(kx[1 - c] - x); 0274 var dy = Math.abs(ky[1 - c] - y); 0275 var our_dx = Math.abs(kx[c] - x); 0276 var our_dy = Math.abs(ky[c] - y); 0277 0278 var d = Math.max(Math.sqrt(dx * dx + dy * dy), 1) + 1; 0279 var mul = multipliers[c]; /*(mul < 1) <==> we're winning*/ 0280 var mul3 = mul * mul * mul; 0281 var at_home = y == 2 + c * 7; 0282 var pawn_home = y == 3 + c * 5; 0283 var row4 = y == 5 + c; 0284 var promotion_row = y == 9 - c * 7; 0285 var get_out = (early && at_home) * -5; 0286 0287 var knight = parseInt(early_centre * 0.3) + 2 * plateau + get_out; 0288 var rook = parseInt(early_centre * 0.3); 0289 var bishop = parseInt(early_centre * 0.6) + plateau + get_out; 0290 if (at_home){ 0291 rook += (x == 4 || x == 5) * (earliness_weight + ! target_king); 0292 rook += (x == 1 || x == 8) * (moveno > 10 && moveno < 20) * -3; 0293 rook += (x == 2 || x == 7) * (moveno > 10 && moveno < 20) * -1; 0294 } 0295 0296 /*Queen wants to stay home early, then jump right in*/ 0297 /*keep kings back on home row for a while*/ 0298 var queen = parseInt(plateau * 0.5 + early_centre * (0.5 - early)); 0299 var king = (king_should_hide && at_home) * 2 * earliness_weight; 0300 0301 /*empty board means pawn advancement is more urgent*/ 0302 var get_on_with_it = Math.max(emptiness * 2, 1); 0303 var pawn = get_on_with_it * P4_BASE_PAWN_WEIGHTS[c ? 119 - i : i]; 0304 if (early){ 0305 /* Early pawn weights are slightly randomised, so each game is different. 0306 */ 0307 if (y >= 4 && y <= 7){ 0308 var boost = 1 + 3 * (y == 5 || y == 6); 0309 pawn += parseInt((boost + p4_random_int(state, 4)) * 0.1 * 0310 early_centre); 0311 } 0312 if (x == 4 || x == 5){ 0313 //discourage middle pawns from waiting at home 0314 pawn -= 3 * pawn_home; 0315 pawn += 3 * row4; 0316 } 0317 } 0318 /*pawn promotion row is weighted as a queen minus a pawn.*/ 0319 if (promotion_row) 0320 pawn += state.values[c][P4_QUEEN] - state.values[c][P4_PAWN]; 0321 0322 /*pawns in front of a castled king should stay there*/ 0323 pawn += 4 * (y == 3 && ky[c] == 2 && Math.abs(our_dx) < 2 && 0324 kx[c] != 5 && x != 4 && x != 5); 0325 /*passed pawns (having no opposing pawn in front) are encouraged. */ 0326 var cols = pawn_cols[1 - c]; 0327 if (cols[x] == undefined || 0328 (c == 0 && cols[x] < y) || 0329 (c == 1 && cols[x] > y)) 0330 pawn += 2; 0331 0332 /* After a while, start going for opposite king. Just 0333 * attract pieces into the area so they can mill about in 0334 * the area, waiting for an opportunity. 0335 * 0336 * As prepare is only called at the beginning of each tree 0337 * search, the king could wander out of the targeted area 0338 * in deep searches. But that's OK. Heuristics are 0339 * heuristics. 0340 */ 0341 if (target_king){ 0342 knight += 2 * parseInt(8 * mul / d); 0343 rook += 2 * ((dx < 2) + (dy < 2)); 0344 bishop += 3 * (Math.abs((dx - dy)) < 2); 0345 queen += 2 * parseInt(8 / d) + (dx * dy == 0) + (dx - dy == 0); 0346 /* The losing king wants to stay in the middle, while 0347 the winning king goes in for the kill.*/ 0348 var king_centre_wt = 8 * emptiness * P4_CENTRALISING_WEIGHTS[i]; 0349 king += parseInt(150 * emptiness / (mul3 * d) + king_centre_wt * mul3); 0350 } 0351 weights[P4_PAWN + c][i] = pawn; 0352 weights[P4_KNIGHT + c][i] = knight; 0353 weights[P4_ROOK + c][i] = rook; 0354 weights[P4_BISHOP + c][i] = bishop; 0355 weights[P4_QUEEN + c][i] = queen; 0356 weights[P4_KING + c][i] = king; 0357 0358 if (draw_likely && mul < 1){ 0359 /*The winning side wants to avoid draw, so adds jitter to its weights.*/ 0360 var range = 3 / mul3; 0361 for (j = 2 + c; j < 14; j += 2){ 0362 weights[j][i] += p4_random_int(state, range); 0363 } 0364 } 0365 } 0366 } 0367 } 0368 state.prepared = true; 0369 } 0370 0371 function p4_maybe_prepare(state){ 0372 if (! state.prepared) 0373 p4_prepare(state); 0374 } 0375 0376 0377 function p4_parse(state, colour, ep, score) { 0378 var board = state.board; 0379 var s, e; //start and end position 0380 var E, a; //E=piece at end place, a= piece moving 0381 var i, j; 0382 var other_colour = 1 - colour; 0383 var dir = (10 - 20 * colour); //dir= 10 for white, -10 for black 0384 var movelist = []; 0385 var captures = []; 0386 var weight; 0387 var pieces = state.pieces[colour]; 0388 var castle_flags = (state.castles >> (colour * 2)) & 3; 0389 var values = state.values[other_colour]; 0390 var all_weights = state.weights; 0391 for (j = pieces.length - 1; j >= 0; j--){ 0392 s = pieces[j][1]; // board position 0393 a = board[s]; //piece number 0394 var weight_lut = all_weights[a]; 0395 weight = score - weight_lut[s]; 0396 a &= 14; 0397 if(a > 2){ //non-pawns 0398 var moves = P4_MOVES[a]; 0399 if(a & 2){ 0400 for(i = 0; i < 8; i++){ 0401 e = s + moves[i]; 0402 E = board[e]; 0403 if(!E){ 0404 movelist.push([weight + values[E] + weight_lut[e], s, e]); 0405 } 0406 else if((E&17)==other_colour){ 0407 captures.push([weight + values[E] + weight_lut[e] + all_weights[E][e], s, e]); 0408 } 0409 } 0410 if(a === P4_KING && castle_flags){ 0411 if((castle_flags & 1) && 0412 (board[s-1] + board[s-2] + board[s-3] == 0) && 0413 p4_check_castling(board, s - 2,other_colour,dir,-1)){//Q side 0414 movelist.push([weight + 12, s, s - 2]); //no analysis, just encouragement 0415 } 0416 if((castle_flags & 2) && (board[s+1]+board[s+2] == 0)&& 0417 p4_check_castling(board, s, other_colour, dir, 1)){//K side 0418 movelist.push([weight + 13, s, s + 2]); 0419 } 0420 } 0421 } 0422 else{//rook, bishop, queen 0423 var mlen = moves.length; 0424 for(i=0;i<mlen;){ //goeth thru list of moves 0425 var m = moves[i++]; 0426 e=s; 0427 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0428 e+=m; 0429 E=board[e]; 0430 if(!E){ 0431 movelist.push([weight + values[E] + weight_lut[e], s, e]); 0432 } 0433 else if((E&17)==other_colour){ 0434 captures.push([weight + values[E] + weight_lut[e] + all_weights[E][e], s, e]); 0435 } 0436 0437 while(!E) { 0438 e+=m; 0439 E=board[e]; 0440 if(!E){ 0441 movelist.push([weight + values[E] + weight_lut[e], s, e]); 0442 } 0443 else if((E&17)==other_colour){ 0444 captures.push([weight + values[E] + weight_lut[e] + all_weights[E][e], s, e]); 0445 } 0446 } 0447 } 0448 } 0449 } 0450 else{ //pawns 0451 e=s+dir; 0452 if(!board[e]){ 0453 movelist.push([weight + weight_lut[e], s, e]); 0454 /* s * (120 - s) < 3200 true for outer two rows on either side.*/ 0455 var e2 = e + dir; 0456 if(s * (120 - s) < 3200 && (!board[e2])){ 0457 movelist.push([weight + weight_lut[e2], s, e2]); 0458 } 0459 } 0460 /* +/-1 for pawn capturing */ 0461 E = board[--e]; 0462 if(E && (E & 17) == other_colour){ 0463 captures.push([weight + values[E] + weight_lut[e] + all_weights[E][e], s, e]); 0464 } 0465 e += 2; 0466 E = board[e]; 0467 if(E && (E & 17) == other_colour){ 0468 captures.push([weight + values[E] + weight_lut[e] + all_weights[E][e], s, e]); 0469 } 0470 } 0471 } 0472 if(ep){ 0473 var pawn = P4_PAWN | colour; 0474 var taken; 0475 /* Some repetitive calculation here could be hoisted out, but that would 0476 probably slow things: the common case is no pawns waiting to capture 0477 enpassant, not 2. 0478 */ 0479 s = ep - dir - 1; 0480 if (board[s] === pawn){ 0481 taken = values[P4_PAWN] + all_weights[P4_PAWN | other_colour][ep - dir]; 0482 captures.push([score - weight_lut[s] + weight_lut[ep] + taken, s, ep]); 0483 } 0484 s += 2; 0485 if (board[s] === pawn){ 0486 taken = values[P4_PAWN] + all_weights[P4_PAWN | other_colour][ep - dir]; 0487 captures.push([score - weight_lut[s] + weight_lut[ep] + taken, s, ep]); 0488 } 0489 } 0490 return captures.concat(movelist); 0491 } 0492 0493 /*Explaining the bit tricks used in check_castling and check_check: 0494 * 0495 * in binary: 16 8 4 2 1 0496 * empty 0497 * pawn 1 c 0498 * rook 1 c 0499 * knight 1 1 c 0500 * bishop 1 c 0501 * king 1 1 c 0502 * queen 1 1 c 0503 * wall 1 0504 * 0505 * so: 0506 * 0507 * piece & (16 | 4 | 2 | 1) is: 0508 * 2 + c for kings and pawns 0509 * 4 + c for rooks and queens 0510 * 6 + c for knights 0511 * 0 + c for bishops 0512 * 16 for walls 0513 * 0514 * thus: 0515 * ((piece & 23) == 4 | colour) separates the rooks and queens out 0516 * from the rest. 0517 * ((piece & 27) == 8 | colour) does the same for queens and bishops. 0518 */ 0519 0520 /* check_castling 0521 * 0522 * s - "start" location (either king home square, or king destination) 0523 * the checks are done left to right. 0524 * * dir - direction of travel (White: 10, Black: -10) 0525 * side: -1 means Q side; 1, K side 0526 */ 0527 0528 function p4_check_castling(board, s, colour, dir, side){ 0529 var e; 0530 var E; 0531 var m, p; 0532 var knight = colour + P4_KNIGHT; 0533 var diag_slider = P4_BISHOP | colour; 0534 var diag_mask = 27; 0535 var grid_slider = P4_ROOK | colour; 0536 var king_pawn = 2 | colour; 0537 var grid_mask = 23; 0538 0539 /* go through 3 positions, checking for check in each 0540 */ 0541 for(p = s; p < s + 3; p++){ 0542 //bishops, rooks, queens 0543 e = p; 0544 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0545 e += dir; 0546 E=board[e]; 0547 while (! E) { 0548 e += dir; 0549 E=board[e]; 0550 } 0551 if((E & grid_mask) == grid_slider) 0552 return 0; 0553 e = p; 0554 var delta = dir - 1; 0555 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0556 e += delta; 0557 E=board[e]; 0558 while (!E) { 0559 e += delta; 0560 E=board[e]; 0561 } 0562 if((E & diag_mask) == diag_slider) 0563 return 0; 0564 e = p; 0565 delta += 2; 0566 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0567 e += delta; 0568 E=board[e]; 0569 while(! E) { 0570 e += delta; 0571 E=board[e]; 0572 } 0573 if((E & diag_mask) == diag_slider) 0574 return 0; 0575 /*knights on row 7. (row 6 is handled below)*/ 0576 if (board[p + dir - 2] === knight || 0577 board[p + dir + 2] === knight) 0578 return 0; 0579 } 0580 0581 /* a pawn or king in any of 5 positions on row 7. 0582 * or a knight on row 6. */ 0583 for(p = s + dir - 1; p < s + dir + 4; p++){ 0584 E = board[p] & grid_mask; 0585 if(E === king_pawn || board[p + dir] === knight) 0586 return 0; 0587 } 0588 /* scan back row for rooks, queens on the other side. 0589 * Same side check is impossible, because the castling rook is there 0590 */ 0591 e = (side < 0) ? s + 2 : s; 0592 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0593 e -= side; 0594 E=board[e]; 0595 while (! E) { 0596 e -= side; 0597 E=board[e]; 0598 } 0599 if((E & grid_mask) == grid_slider) 0600 return 0; 0601 0602 return 1; 0603 } 0604 0605 function p4_check_check(state, colour){ 0606 var board = state.board; 0607 /*find the king. The pieces list updates from the end, 0608 * so the last-most king is correctly placed.*/ 0609 var pieces = state.pieces[colour]; 0610 var i = pieces.length; 0611 var king = P4_KING | colour 0612 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0613 var val = king-1 0614 while (val !== king) { 0615 var p = pieces[--i]; 0616 val = p[0] 0617 }; 0618 var s = p[1]; 0619 var other_colour = 1 - colour; 0620 var dir = 10 - 20 * colour; 0621 if (board[s + dir - 1] === (P4_PAWN | other_colour) || 0622 board[s + dir + 1] === (P4_PAWN | other_colour)) 0623 return true; 0624 var knight_moves = P4_MOVES[P4_KNIGHT]; 0625 var king_moves = P4_MOVES[P4_KING]; 0626 var knight = P4_KNIGHT | other_colour; 0627 var king = P4_KING | other_colour; 0628 for (i = 0; i < 8; i++){ 0629 if (board[s + knight_moves[i]] === knight || 0630 board[s + king_moves[i]] === king) 0631 return true; 0632 } 0633 var diagonal_moves = P4_MOVES[P4_BISHOP]; 0634 var grid_moves = P4_MOVES[P4_ROOK]; 0635 0636 /* diag_mask ignores rook moves of queens, 0637 * grid_mask ignores the bishop moves*/ 0638 var diag_slider = P4_BISHOP | other_colour; 0639 var diag_mask = 27; 0640 var grid_slider = P4_ROOK | other_colour; 0641 var grid_mask = 23; 0642 for (i = 0; i < 4; i++){ 0643 var m = diagonal_moves[i]; 0644 var e = s; 0645 var E; 0646 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0647 e += m; 0648 E = board[e]; 0649 while (!E) { 0650 e += m; 0651 E = board[e]; 0652 } 0653 if((E & diag_mask) == diag_slider) 0654 return true; 0655 0656 m = grid_moves[i]; 0657 e = s; 0658 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 0659 e += m; 0660 E = board[e]; 0661 while (!E) { 0662 e += m; 0663 E = board[e]; 0664 } 0665 0666 if((E & grid_mask) == grid_slider) 0667 return true; 0668 } 0669 return false; 0670 } 0671 0672 function p4_optimise_piece_list(state){ 0673 var i, p, s, e; 0674 var movelists = [ 0675 p4_parse(state, 0, 0, 0), 0676 p4_parse(state, 1, 0, 0) 0677 ]; 0678 var weights = state.weights; 0679 var board = state.board; 0680 for (var colour = 0; colour < 2; colour++){ 0681 var our_values = state.values[colour]; 0682 var pieces = state.pieces[colour]; 0683 var movelist = movelists[colour]; 0684 var threats = movelists[1 - colour]; 0685 /* sparse array to index by score. */ 0686 var scores = []; 0687 for (i = 0; i < pieces.length; i++){ 0688 p = pieces[i]; 0689 scores[p[1]] = { 0690 score: 0, 0691 piece: p[0], 0692 pos: p[1], 0693 threatened: 0 0694 }; 0695 } 0696 /* Find the best score for each piece by pure static weights, 0697 * ignoring captures, which have their own path to the top. */ 0698 for(i = movelist.length - 1; i >= 0; i--){ 0699 var mv = movelist[i]; 0700 var score = mv[0]; 0701 s = mv[1]; 0702 e = mv[2]; 0703 if(! board[e]){ 0704 var x = scores[s]; 0705 x.score = Math.max(x.score, score); 0706 } 0707 } 0708 /* moving out of a threat is worth considering, especially 0709 * if it is a pawn and you are not.*/ 0710 for(i = threats.length - 1; i >= 0; i--){ 0711 var mv = threats[i]; 0712 var x = scores[mv[2]]; 0713 if (x !== undefined){ 0714 var S = board[mv[1]]; 0715 var r = (1 + x.piece > 3 + S < 4) * 0.01; 0716 if (x.threatened < r) 0717 x.threatened = r; 0718 } 0719 } 0720 var pieces2 = []; 0721 for (i = 20; i < 100; i++){ 0722 p = scores[i]; 0723 if (p !== undefined){ 0724 p.score += p.threatened * our_values[p.piece]; 0725 pieces2.push(p); 0726 } 0727 } 0728 pieces2.sort(function(a, b){return a.score - b.score;}); 0729 for (i = 0; i < pieces2.length; i++){ 0730 p = pieces2[i]; 0731 pieces[i] = [p.piece, p.pos]; 0732 } 0733 } 0734 } 0735 0736 function p4_findmove(state, level, colour, ep){ 0737 p4_prepare(state); 0738 p4_optimise_piece_list(state); 0739 var board = state.board; 0740 if (arguments.length == 2){ 0741 colour = state.to_play; 0742 ep = state.enpassant; 0743 } 0744 var movelist = p4_parse(state, colour, ep, 0); 0745 var alpha = P4_MIN_SCORE; 0746 var mv, t, i; 0747 var bs = 0; 0748 var be = 0; 0749 0750 if (level <= 0){ 0751 for (i = 0; i < movelist.length; i++){ 0752 mv = movelist[i]; 0753 if(movelist[i][0] > alpha){ 0754 alpha = mv[0]; 0755 bs = mv[1]; 0756 be = mv[2]; 0757 } 0758 } 0759 return [bs, be, alpha]; 0760 } 0761 0762 for(i = 0; i < movelist.length; i++){ 0763 mv = movelist[i]; 0764 var mscore = mv[0]; 0765 var ms = mv[1]; 0766 var me = mv[2]; 0767 if (mscore > P4_WIN){ 0768 p4_log("XXX taking king! it should never come to this"); 0769 alpha = P4_KING_VALUE; 0770 bs = ms; 0771 be = me; 0772 break; 0773 } 0774 t = -state.treeclimber(state, level - 1, 1 - colour, mscore, ms, me, 0775 P4_MIN_SCORE, -alpha); 0776 if (t > alpha){ 0777 alpha = t; 0778 bs = ms; 0779 be = me; 0780 } 0781 } 0782 if (alpha < -P4_WIN_NOW && ! p4_check_check(state, colour)){ 0783 alpha = state.stalemate_scores[colour]; 0784 } 0785 return [bs, be, alpha]; 0786 } 0787 0788 /*p4_make_move changes the state and returns an object containing 0789 * everything necessary to undo the change. 0790 * 0791 * p4_unmake_move uses the p4_make_move return value to restore the 0792 * previous state. 0793 */ 0794 0795 function p4_make_move(state, s, e, promotion){ 0796 var board = state.board; 0797 var S = board[s]; 0798 var E = board[e]; 0799 board[e] = S; 0800 board[s] = 0; 0801 var piece = S & 14; 0802 var moved_colour = S & 1; 0803 var end_piece = S; /* can differ from S in queening*/ 0804 //now some stuff to handle queening, castling 0805 var rs = 0, re, rook; 0806 var ep_taken = 0, ep_position; 0807 var ep = 0; 0808 if(piece == P4_PAWN){ 0809 if((60 - e) * (60 - e) > 900){ 0810 /*got to end; replace the pawn on board and in pieces cache.*/ 0811 promotion |= moved_colour; 0812 board[e] = promotion; 0813 end_piece = promotion; 0814 } 0815 else if (((s ^ e) & 1) && E === 0){ 0816 /*this is a diagonal move, but the end spot is empty, so we surmise enpassant */ 0817 ep_position = e - 10 + 20 * moved_colour; 0818 ep_taken = board[ep_position]; 0819 board[ep_position] = 0; 0820 } 0821 else if ((s - e) * (s - e) == 400){ 0822 /*delta is 20 --> two row jump at start*/ 0823 ep = (s + e) >> 1; 0824 } 0825 } 0826 else if (piece == P4_KING && ((s - e) * (s - e) == 4)){ //castling - move rook too 0827 rs = s - 4 + (s < e) * 7; 0828 re = (s + e) >> 1; //avg of s,e=rook's spot 0829 rook = moved_colour + P4_ROOK; 0830 board[rs] = 0; 0831 board[re] = rook; 0832 //piece_locations.push([rook, re]); 0833 } 0834 0835 var old_castle_state = state.castles; 0836 if (old_castle_state){ 0837 var mask = 0; 0838 var shift = moved_colour * 2; 0839 var side = moved_colour * 70; 0840 var s2 = s - side; 0841 var e2 = e + side; 0842 //wipe both our sides if king moves 0843 if (s2 == 25) 0844 mask |= 3 << shift; 0845 //wipe one side on any move from rook points 0846 else if (s2 == 21) 0847 mask |= 1 << shift; 0848 else if (s2 == 28) 0849 mask |= 2 << shift; 0850 //or on any move *to* opposition corners 0851 if (e2 == 91) 0852 mask |= 4 >> shift; 0853 else if (e2 == 98) 0854 mask |= 8 >> shift; 0855 state.castles &= ~mask; 0856 } 0857 0858 var old_pieces = state.pieces.concat(); 0859 var our_pieces = old_pieces[moved_colour]; 0860 var dest = state.pieces[moved_colour] = []; 0861 for (var i = 0; i < our_pieces.length; i++){ 0862 var x = our_pieces[i]; 0863 var pp = x[0]; 0864 var ps = x[1]; 0865 if (ps != s && ps != rs){ 0866 dest.push(x); 0867 } 0868 } 0869 dest.push([end_piece, e]); 0870 if (rook) 0871 dest.push([rook, re]); 0872 0873 if (E || ep_taken){ 0874 var their_pieces = old_pieces[1 - moved_colour]; 0875 dest = state.pieces[1 - moved_colour] = []; 0876 var gone = ep_taken ? ep_position : e; 0877 for (i = 0; i < their_pieces.length; i++){ 0878 var x = their_pieces[i]; 0879 if (x[1] != gone){ 0880 dest.push(x); 0881 } 0882 } 0883 } 0884 0885 return { 0886 /*some of these (e.g. rook) could be recalculated during 0887 * unmake, possibly more cheaply. */ 0888 s: s, 0889 e: e, 0890 S: S, 0891 E: E, 0892 ep: ep, 0893 castles: old_castle_state, 0894 rs: rs, 0895 re: re, 0896 rook: rook, 0897 ep_position: ep_position, 0898 ep_taken: ep_taken, 0899 pieces: old_pieces 0900 }; 0901 } 0902 0903 function p4_unmake_move(state, move){ 0904 var board = state.board; 0905 if (move.ep_position){ 0906 board[move.ep_position] = move.ep_taken; 0907 } 0908 board[move.s] = move.S; 0909 board[move.e] = move.E; 0910 //move.piece_locations.length--; 0911 if(move.rs){ 0912 board[move.rs] = move.rook; 0913 board[move.re] = 0; 0914 //move.piece_locations.length--; 0915 } 0916 state.pieces = move.pieces; 0917 state.castles = move.castles; 0918 } 0919 0920 0921 function p4_insufficient_material(state){ 0922 var knights = false; 0923 var bishops = undefined; 0924 var i; 0925 var board = state.board; 0926 for(i = 20; i < 100; i++){ 0927 var piece = board[i] & 14; 0928 if(piece == 0 || piece == P4_KING){ 0929 continue; 0930 } 0931 if (piece == P4_KNIGHT){ 0932 /* only allow one knight of either colour, never with a bishop */ 0933 if (knights || bishops !== undefined){ 0934 return false; 0935 } 0936 knights = true; 0937 } 0938 else if (piece == P4_BISHOP){ 0939 /*any number of bishops, but on only one colour square */ 0940 var x = i & 1; 0941 var y = parseInt(i / 10) & 1; 0942 var parity = x ^ y; 0943 if (knights){ 0944 return false; 0945 } 0946 else if (bishops === undefined){ 0947 bishops = parity; 0948 } 0949 else if (bishops != parity){ 0950 return false; 0951 } 0952 } 0953 else { 0954 return false; 0955 } 0956 } 0957 return true; 0958 } 0959 0960 /* p4_move(state, s, e, promotion) 0961 * s, e are start and end positions 0962 * 0963 * promotion is the desired pawn promotion if the move gets a pawn to the other 0964 * end. 0965 * 0966 * return value contains bitwise flags 0967 */ 0968 0969 var P4_MOVE_FLAG_OK = 1; 0970 var P4_MOVE_FLAG_CHECK = 2; 0971 var P4_MOVE_FLAG_MATE = 4; 0972 var P4_MOVE_FLAG_CAPTURE = 8; 0973 var P4_MOVE_FLAG_CASTLE_KING = 16; 0974 var P4_MOVE_FLAG_CASTLE_QUEEN = 32; 0975 var P4_MOVE_FLAG_DRAW = 64; 0976 0977 var P4_MOVE_ILLEGAL = 0; 0978 var P4_MOVE_MISSED_MATE = P4_MOVE_FLAG_CHECK | P4_MOVE_FLAG_MATE; 0979 var P4_MOVE_CHECKMATE = P4_MOVE_FLAG_OK | P4_MOVE_FLAG_CHECK | P4_MOVE_FLAG_MATE; 0980 var P4_MOVE_STALEMATE = P4_MOVE_FLAG_OK | P4_MOVE_FLAG_MATE; 0981 0982 function p4_move(state, s, e, promotion){ 0983 var board = state.board; 0984 var colour = state.to_play; 0985 var other_colour = 1 - colour; 0986 if (s != parseInt(s)){ 0987 if (e === undefined){ 0988 var mv = p4_interpret_movestring(state, s); 0989 s = mv[0]; 0990 e = mv[1]; 0991 if (s == 0) 0992 return {flags: P4_MOVE_ILLEGAL, ok: false}; 0993 promotion = mv[2]; 0994 } 0995 else {/*assume two point strings: 'e2', 'e4'*/ 0996 s = p4_destringify_point(s); 0997 e = p4_destringify_point(e); 0998 } 0999 } 1000 if (promotion === undefined) 1001 promotion = P4_QUEEN; 1002 var E=board[e]; 1003 var S=board[s]; 1004 1005 /*See if this move is even slightly legal, disregarding check. 1006 */ 1007 var i; 1008 var legal = false; 1009 p4_maybe_prepare(state); 1010 var moves = p4_parse(state, colour, state.enpassant, 0); 1011 for (i = 0; i < moves.length; i++){ 1012 if (e === moves[i][2] && s === moves[i][1]){ 1013 legal = true; 1014 break; 1015 } 1016 } 1017 if (! legal) { 1018 return {flags: P4_MOVE_ILLEGAL, ok: false}; 1019 } 1020 1021 /*Try the move, and see what the response is.*/ 1022 var changes = p4_make_move(state, s, e, promotion); 1023 /*is it check? */ 1024 if (p4_check_check(state, colour)){ 1025 p4_unmake_move(state, changes); 1026 p4_log('in check', changes); 1027 return {flags: P4_MOVE_ILLEGAL, ok: false, string: "in check!"}; 1028 } 1029 /*The move is known to be legal. We won't be undoing it.*/ 1030 1031 var flags = P4_MOVE_FLAG_OK; 1032 1033 state.enpassant = changes.ep; 1034 state.history.push([s, e, promotion]); 1035 /*draw timeout: 50 moves without pawn move or capture is a draw */ 1036 if (changes.E || changes.ep_position){ 1037 state.draw_timeout = 0; 1038 flags |= P4_MOVE_FLAG_CAPTURE; 1039 } 1040 else if ((S & 14) == P4_PAWN){ 1041 state.draw_timeout = 0; 1042 } 1043 else{ 1044 state.draw_timeout++; 1045 } 1046 if (changes.rs){ 1047 flags |= (s > e) ? P4_MOVE_FLAG_CASTLE_QUEEN : P4_MOVE_FLAG_CASTLE_KING; 1048 } 1049 var shortfen = p4_state2fen(state, true); 1050 var repetitions = (state.position_counts[shortfen] || 0) + 1; 1051 state.position_counts[shortfen] = repetitions; 1052 state.current_repetitions = repetitions; 1053 if (state.draw_timeout > 100 || repetitions >= 3 || 1054 p4_insufficient_material(state)){ 1055 flags |= P4_MOVE_FLAG_DRAW; 1056 } 1057 state.moveno++; 1058 state.to_play = other_colour; 1059 1060 if (p4_check_check(state, other_colour)){ 1061 flags |= P4_MOVE_FLAG_CHECK; 1062 } 1063 /* check for (stale|check)mate, by seeing if there is a move for 1064 * the other side that doesn't result in check. (In other words, 1065 * reduce the pseudo-legal-move list down to a legal-move list, 1066 * and check it isn't empty). 1067 * 1068 * We don't need to p4_prepare because other colour pieces can't 1069 * have moved (just disappeared) since previous call. Also, 1070 * setting the promotion piece is unnecessary, because all 1071 * promotions block check equally well. 1072 */ 1073 var is_mate = true; 1074 var replies = p4_parse(state, other_colour, changes.ep, 0); 1075 for (i = 0; i < replies.length; i++){ 1076 var m = replies[i]; 1077 var change2 = p4_make_move(state, m[1], m[2], P4_QUEEN); 1078 var check = p4_check_check(state, other_colour); 1079 p4_unmake_move(state, change2); 1080 if (!check){ 1081 is_mate = false; 1082 break; 1083 } 1084 } 1085 if (is_mate) 1086 flags |= P4_MOVE_FLAG_MATE; 1087 1088 var movestring = p4_move2string(state, s, e, S, promotion, flags, moves); 1089 p4_log("successful move", s, e, movestring, flags); 1090 state.prepared = false; 1091 return { 1092 flags: flags, 1093 string: movestring, 1094 ok: true 1095 }; 1096 } 1097 1098 1099 function p4_move2string(state, s, e, S, promotion, flags, moves){ 1100 var piece = S & 14; 1101 var src, dest; 1102 var mv, i; 1103 var capture = flags & P4_MOVE_FLAG_CAPTURE; 1104 1105 src = p4_stringify_point(s); 1106 dest = p4_stringify_point(e); 1107 if (piece == P4_PAWN){ 1108 if (capture){ 1109 mv = src.charAt(0) + 'x' + dest; 1110 } 1111 else 1112 mv = dest; 1113 if (e > 90 || e < 30){ //end row, queening 1114 if (promotion === undefined) 1115 promotion = P4_QUEEN; 1116 mv += '=' + P4_ENCODE_LUT.charAt(promotion); 1117 } 1118 } 1119 else if (piece == P4_KING && (s-e) * (s-e) == 4) { 1120 if (e < s) 1121 mv = 'O-O-O'; 1122 else 1123 mv = 'O-O'; 1124 } 1125 else { 1126 var row_qualifier = ''; 1127 var col_qualifier = ''; 1128 var pstr = P4_ENCODE_LUT.charAt(S); 1129 var sx = s % 10; 1130 var sy = parseInt(s / 10); 1131 1132 /* find any other pseudo-legal moves that would put the same 1133 * piece in the same place, for which we'd need 1134 * disambiguation. */ 1135 var co_landers = []; 1136 for (i = 0; i < moves.length; i++){ 1137 var m = moves[i]; 1138 if (e == m[2] && s != m[1] && state.board[m[1]] == S){ 1139 co_landers.push(m[1]); 1140 } 1141 } 1142 if (co_landers.length){ 1143 for (i = 0; i < co_landers.length; i++){ 1144 var c = co_landers[i]; 1145 var cx = c % 10; 1146 var cy = parseInt(c / 10); 1147 if (cx == sx)/*same column, so qualify by row*/ 1148 row_qualifier = src.charAt(1); 1149 if (cy == sy) 1150 col_qualifier = src.charAt(0); 1151 } 1152 if (row_qualifier == '' && col_qualifier == ''){ 1153 /*no co-landers on the same rank or file, so one or the other will do. 1154 * By convention, use the column (a-h) */ 1155 col_qualifier = src.charAt(0); 1156 } 1157 } 1158 mv = pstr + col_qualifier + row_qualifier + (capture ? 'x' : '') + dest; 1159 } 1160 if (flags & P4_MOVE_FLAG_CHECK){ 1161 if (flags & P4_MOVE_FLAG_MATE) 1162 mv += '#'; 1163 else 1164 mv += '+'; 1165 } 1166 else if (flags & P4_MOVE_FLAG_MATE) 1167 mv += ' stalemate'; 1168 return mv; 1169 } 1170 1171 1172 function p4_jump_to_moveno(state, moveno){ 1173 p4_log('jumping to move', moveno); 1174 if (moveno === undefined || moveno > state.moveno) 1175 moveno = state.moveno; 1176 else if (moveno < 0){ 1177 moveno = state.moveno + moveno; 1178 } 1179 var state2 = p4_fen2state(state.beginning); 1180 var i = 0; 1181 while (state2.moveno < moveno){ 1182 var m = state.history[i++]; 1183 p4_move(state2, m[0], m[1], m[2]); 1184 } 1185 /* copy the replayed state across, not all that deeply, but 1186 * enough to cover, eg, held references to board. */ 1187 var attr, dest; 1188 for (attr in state2){ 1189 var src = state2[attr]; 1190 if (attr instanceof Array){ 1191 dest = state[attr]; 1192 dest.length = 0; 1193 for (i = 0; i < src.length; i++){ 1194 dest[i] = src[i]; 1195 } 1196 } 1197 else { 1198 state[attr] = src; 1199 } 1200 } 1201 state.prepared = false; 1202 } 1203 1204 1205 /* write a standard FEN notation 1206 * http://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation 1207 * */ 1208 function p4_state2fen(state, reduced){ 1209 var piece_lut = ' PpRrNnBbKkQq'; 1210 var board = state.board; 1211 var fen = ''; 1212 //fen does Y axis backwards, X axis forwards */ 1213 for (var y = 9; y > 1; y--){ 1214 var count = 0; 1215 for (var x = 1; x < 9; x++){ 1216 var piece = board[y * 10 + x]; 1217 if (piece === 0) 1218 count++; 1219 else{ 1220 if (count) 1221 fen += count.toString(); 1222 fen += piece_lut.charAt(piece); 1223 count = 0; 1224 } 1225 } 1226 if (count) 1227 fen += count; 1228 if (y > 2) 1229 fen += '/'; 1230 } 1231 /*white or black */ 1232 fen += ' ' + 'wb'.charAt(state.to_play) + ' '; 1233 /*castling */ 1234 if (state.castles){ 1235 var lut = [2, 'K', 1, 'Q', 8, 'k', 4, 'q']; 1236 for (var i = 0; i < 8; i += 2){ 1237 if (state.castles & lut[i]){ 1238 fen += lut[i + 1]; 1239 } 1240 } 1241 } 1242 else 1243 fen += '-'; 1244 /*enpassant */ 1245 if (state.enpassant !== 0){ 1246 fen += ' ' + p4_stringify_point(state.enpassant); 1247 } 1248 else 1249 fen += ' -'; 1250 if (reduced){ 1251 /*if the 'reduced' flag is set, the move number and draw 1252 *timeout are not added. This form is used to detect draws by 1253 *3-fold repetition.*/ 1254 return fen; 1255 } 1256 fen += ' ' + state.draw_timeout + ' '; 1257 fen += (state.moveno >> 1) + 1; 1258 return fen; 1259 } 1260 1261 function p4_stringify_point(p){ 1262 var letters = " abcdefgh"; 1263 var x = p % 10; 1264 var y = (p - x) / 10 - 1; 1265 return letters.charAt(x) + y; 1266 } 1267 1268 function p4_destringify_point(p){ 1269 var x = parseInt(p.charAt(0), 19) - 9; //a-h <-> 10-18, base 19 1270 var y = parseInt(p.charAt(1)) + 1; 1271 if (y >= 2 && y < 10 && x >= 1 && x < 9) 1272 return y * 10 + x; 1273 return undefined; 1274 } 1275 1276 /* read a standard FEN notation 1277 * http://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation 1278 * */ 1279 function p4_fen2state(fen, state){ 1280 if (state === undefined) 1281 state = p4_initialise_state(); 1282 var board = state.board; 1283 var fenbits = fen.split(' '); 1284 var fen_board = fenbits[0]; 1285 var fen_toplay = fenbits[1]; 1286 var fen_castles = fenbits[2]; 1287 var fen_enpassant = fenbits[3]; 1288 var fen_timeout = fenbits[4]; 1289 var fen_moveno = fenbits[5]; 1290 if (fen_timeout === undefined) 1291 fen_timeout = 0; 1292 //fen does Y axis backwards, X axis forwards */ 1293 var y = 90; 1294 var x = 1; 1295 var i; 1296 for (var j = 0; j < fen_board.length; j++){ 1297 var c = fen_board.charAt(j); 1298 if (c === '/'){ 1299 x = 1; 1300 y -= 10; 1301 if (y < 20) 1302 break; 1303 continue; 1304 } 1305 var piece = P4_PIECE_LUT[c]; 1306 if (piece && x < 9){ 1307 board[y + x] = piece; 1308 x++; 1309 } 1310 else { 1311 var end = Math.min(x + parseInt(c), 9); 1312 for (; x < end; x++){ 1313 board[y + x] = 0; 1314 } 1315 } 1316 } 1317 state.to_play = (fen_toplay.toLowerCase() == 'b') ? 1 : 0; 1318 state.castles = 0; 1319 for (i = 0; i < fen_castles.length; i++){ 1320 var bit = {k: 8, q: 4, K: 2, Q: 1}[fen_castles.charAt(i)]; 1321 state.castles |= (bit || 0); 1322 } 1323 state.enpassant = (fen_enpassant != '-') ? p4_destringify_point(fen_enpassant) : 0; 1324 state.draw_timeout = parseInt(fen_timeout); 1325 if (fen_moveno === undefined){ 1326 /*have a guess based on entropy and pieces remaining*/ 1327 var pieces = 0; 1328 var mix = 0; 1329 var p, q, r; 1330 for (y = 20; y < 100; y+=10){ 1331 for (x = 1; x < 9; x++){ 1332 p = board[y + x] & 15; 1333 pieces += (!!p); 1334 if (x < 8){ 1335 q = board[y + x + 1]; 1336 mix += (!q) != (!p); 1337 } 1338 if (y < 90){ 1339 q = board[y + x + 10]; 1340 mix += (!q) != (!p); 1341 } 1342 } 1343 } 1344 fen_moveno = Math.max(1, parseInt((32 - pieces) * 1.3 + (4 - fen_castles.length) * 1.5 + ((mix - 16) / 5))); 1345 //p4_log("pieces", pieces, "mix", mix, "estimate", fen_moveno); 1346 } 1347 state.moveno = 2 * (parseInt(fen_moveno) - 1) + state.to_play; 1348 state.history = []; 1349 state.beginning = fen; 1350 state.prepared = false; 1351 state.position_counts = {}; 1352 /* Wrap external functions as methods. */ 1353 state.move = function(s, e, promotion){ 1354 return p4_move(this, s, e, promotion); 1355 }; 1356 state.findmove = function(level){ 1357 return p4_findmove(this, level); 1358 }; 1359 state.jump_to_moveno = function(moveno){ 1360 return p4_jump_to_moveno(this, moveno); 1361 }; 1362 return state; 1363 } 1364 1365 /* 1366 Weights would all fit within an Int8Array *except* for the last row 1367 for pawns, which is close to the queen value (180, max is 127). 1368 1369 Int8Array seems slightly quicker in Chromium 18, no different in 1370 Firefox 12. 1371 1372 Int16Array is no faster, perhaps slower than Int32Array. 1373 1374 Int32Array is marginally slower than plain arrays with Firefox 12, but 1375 significantly quicker with Chromium. 1376 */ 1377 1378 var P4_ZEROS = []; 1379 function p4_zero_array(){ 1380 if (P4_USE_TYPED_ARRAYS) 1381 return new Int32Array(120); 1382 if (P4_ZEROS.length == 0){ 1383 for(var i = 0; i < 120; i++){ 1384 P4_ZEROS[i] = 0; 1385 } 1386 } 1387 return P4_ZEROS.slice(); 1388 } 1389 1390 /* p4_initialise_state() creates the board and initialises weight 1391 * arrays etc. Some of this is really only needs to be done once. 1392 */ 1393 1394 function p4_initialise_state(){ 1395 var board = p4_zero_array(); 1396 P4_CENTRALISING_WEIGHTS = p4_zero_array(); 1397 P4_BASE_PAWN_WEIGHTS = p4_zero_array(); 1398 P4_KNIGHT_WEIGHTS = p4_zero_array(); 1399 for(var i = 0; i < 120; i++){ 1400 var y = parseInt(i / 10); 1401 var x = i % 10; 1402 var dx = Math.abs(x - 4.5); 1403 var dy = Math.abs(y - 5.5); 1404 P4_CENTRALISING_WEIGHTS[i] = parseInt(6 - Math.pow((dx * dx + dy * dy) * 1.5, 0.6)); 1405 //knights have a flat topped centre (bishops too, but less so). 1406 P4_KNIGHT_WEIGHTS[i] = parseInt(((dx < 2) + (dy < 2) * 1.5) 1407 + (dx < 3) + (dy < 3)) - 2; 1408 P4_BASE_PAWN_WEIGHTS[i] = parseInt('000012347000'.charAt(y)); 1409 if (y > 9 || y < 2 || x < 1 || x > 8) 1410 board[i] = 16; 1411 } 1412 var weights = []; 1413 for (i = 0; i < 14; i++){ 1414 weights[i] = p4_zero_array(); 1415 } 1416 var state = { 1417 board: board, 1418 weights: weights, 1419 history: [], 1420 treeclimber: p4_alphabeta_treeclimber 1421 }; 1422 p4_random_seed(state, P4_DEBUG ? 1 : Date.now()); 1423 return state; 1424 } 1425 1426 function p4_new_game(){ 1427 return p4_fen2state(P4_INITIAL_BOARD); 1428 } 1429 1430 /*convert an arbitrary movestring into a pair of integers offsets into 1431 * the board. The string might be in any of these forms: 1432 * 1433 * "d2-d4" "d2d4" "d4" -- moving a pawn 1434 * 1435 * "b1-c3" "b1c3" "Nc3" "N1c3" "Nbc3" "Nb1c3" -- moving a knight 1436 * 1437 * "b1xc3" "b1xc3" "Nxc3" -- moving a knight, also happens to capture. 1438 * 1439 * "O-O" "O-O-O" -- special cases for castling ("e1-c1", etc, also work) 1440 * 1441 * Note that for the "Nc3" (pgn) format, some knowledge of the board 1442 * is necessary, so the state parameter is required. If it is 1443 * undefined, the other forms will still work. 1444 */ 1445 1446 function p4_interpret_movestring(state, str){ 1447 /* Ignore any irrelevant characters, then tokenise. 1448 * 1449 */ 1450 var FAIL = [0, 0]; 1451 var algebraic_re = /^\s*([RNBQK]?[a-h]?[1-8]?)[ :x-]*([a-h][1-8]?)(=[RNBQ])?[!?+#e.p]*\s*$/; 1452 var castle_re = /^\s*([O0o]-[O0o](-[O0o])?)\s*$/; 1453 var position_re = /^[a-h][1-8]$/; 1454 1455 var m = algebraic_re.exec(str); 1456 if (m == null){ 1457 /*check for castling notation (O-O, O-O-O) */ 1458 m = castle_re.exec(str); 1459 if (m){ 1460 s = 25 + state.to_play * 70; 1461 if (m[2])/*queenside*/ 1462 e = s - 2; 1463 else 1464 e = s + 2; 1465 } 1466 else 1467 return FAIL; 1468 } 1469 var src = m[1]; 1470 var dest = m[2]; 1471 var queen = m[3]; 1472 var s, e, q; 1473 var moves, i; 1474 if (src == '' || src == undefined){ 1475 /* a single coordinate pawn move */ 1476 e = p4_destringify_point(dest); 1477 s = p4_find_source_point(state, e, 'P' + dest.charAt(0)); 1478 } 1479 else if (/^[RNBQK]/.test(src)){ 1480 /*pgn format*/ 1481 e = p4_destringify_point(dest); 1482 s = p4_find_source_point(state, e, src); 1483 } 1484 else if (position_re.test(src) && position_re.test(dest)){ 1485 s = p4_destringify_point(src); 1486 e = p4_destringify_point(dest); 1487 } 1488 else if (/^[a-h]$/.test(src)){ 1489 e = p4_destringify_point(dest); 1490 s = p4_find_source_point(state, e, 'P' + src); 1491 } 1492 if (s == 0) 1493 return FAIL; 1494 1495 if (queen){ 1496 /* the chosen queen piece */ 1497 q = P4_PIECE_LUT[queen.charAt(1)]; 1498 } 1499 return [s, e, q]; 1500 } 1501 1502 1503 function p4_find_source_point(state, e, str){ 1504 var colour = state.to_play; 1505 var piece = P4_PIECE_LUT[str.charAt(0)]; 1506 piece |= colour; 1507 var s, i; 1508 1509 var row, column; 1510 /* can be specified as Na, Na3, N3, and who knows, N3a? */ 1511 for (i = 1; i < str.length; i++){ 1512 var c = str.charAt(i); 1513 if (/[a-h]/.test(c)){ 1514 column = str.charCodeAt(i) - 96; 1515 } 1516 else if (/[1-8]/.test(c)){ 1517 /*row goes 2 - 9 */ 1518 row = 1 + parseInt(c); 1519 } 1520 } 1521 var possibilities = []; 1522 p4_prepare(state); 1523 var moves = p4_parse(state, colour, 1524 state.enpassant, 0); 1525 for (i = 0; i < moves.length; i++){ 1526 var mv = moves[i]; 1527 if (e === mv[2]){ 1528 s = mv[1]; 1529 if (state.board[s] === piece && 1530 (column === undefined || column === s % 10) && 1531 (row === undefined || row === parseInt(s / 10)) 1532 ){ 1533 var change = p4_make_move(state, s, e, P4_QUEEN); 1534 if (! p4_check_check(state, colour)) 1535 possibilities.push(s); 1536 p4_unmake_move(state, change); 1537 } 1538 } 1539 } 1540 p4_log("finding", str, "that goes to", e, "got", possibilities); 1541 1542 if (possibilities.length == 0){ 1543 return 0; 1544 } 1545 else if (possibilities.length > 1){ 1546 p4_log("p4_find_source_point seems to have failed", 1547 state, e, str, 1548 possibilities); 1549 } 1550 return possibilities[0]; 1551 } 1552 1553 1554 /*random number generator based on 1555 * http://burtleburtle.net/bob/rand/smallprng.html 1556 */ 1557 function p4_random_seed(state, seed){ 1558 seed &= 0xffffffff; 1559 state.rng = (P4_USE_TYPED_ARRAYS) ? new Uint32Array(4) : []; 1560 state.rng[0] = 0xf1ea5eed; 1561 state.rng[1] = seed; 1562 state.rng[2] = seed; 1563 state.rng[3] = seed; 1564 for (var i = 0; i < 20; i++) 1565 p4_random31(state); 1566 } 1567 1568 function p4_random31(state){ 1569 var rng = state.rng; 1570 var b = rng[1]; 1571 var c = rng[2]; 1572 /* These shifts amount to rotates. 1573 * Note the three-fold right shift '>>>', meaning an unsigned shift. 1574 * The 0xffffffff masks are needed to keep javascript to 32bit. (supposing 1575 * untyped arrays). 1576 */ 1577 var e = rng[0] - ((b << 27) | (b >>> 5)); 1578 rng[0] = b ^ ((c << 17) | (c >>> 15)); 1579 rng[1] = (c + rng[3]) & 0xffffffff; 1580 rng[2] = (rng[3] + e) & 0xffffffff; 1581 rng[3] = (e + rng[0]) & 0xffffffff; 1582 return rng[3] & 0x7fffffff; 1583 } 1584 1585 function p4_random_int(state, top){ 1586 /* uniform integer in range [0 < n < top), supposing top < 2 ** 31 1587 * 1588 * This method is slightly (probably pointlessly) more accurate 1589 * than converting to 0-1 float, multiplying and truncating, and 1590 * considerably more accurate than a simple modulus. 1591 * Obviously it is a bit slower. 1592 */ 1593 /* mask becomes one less than the next highest power of 2 */ 1594 var mask = top; 1595 mask--; 1596 mask |= mask >>> 1; 1597 mask |= mask >>> 2; 1598 mask |= mask >>> 4; 1599 mask |= mask >>> 8; 1600 mask |= mask >>> 16; 1601 // can't do-while loop: https://bugreports.qt.io/browse/QTBUG-59012 1602 var r = top + 1; 1603 while(r >= top) 1604 r = p4_random31(state) & mask; 1605 1606 return r; 1607 }