// doChess - a Javascript chess engine (Version 0.5)
// (c) Vlad Bazon, 2008.   <vlad.bazon@gmail.com>
// http://www.docere.ro/
// All rights reserved.

// var qvariant = 1;

function qengine() {
    this.castle = 0;   // 1/2 white O-O/O-O-O; 4/16 black O-O/O-O-O
    this.to_move = 0;  // 0/1 white/black side to move
    this.en_pass = -1; // the square target of the en-passant move (or else -1)
    this.fifty = 0;    // count consecutive uncapturing and non-pawn white/black moves
    this.nr_move = 0;  // count the pairs of white/black moves (incremented after the black response)
    this.sq_king = [0,0]; // the square occupied by the white/black king
    this.heur_hist = {};   // the heuristic history table
    this.ply = 0;
    this.BOARD = new Array(128);
    this.ply_mov = [];
    this.have_pv = false;
    this.nodes = 0; 

    this.game_hist = new Array(500); // keeps track of previous positions for unmake move
    this.gh_top = 0;                 // and for to detect three repetitions

    this.PV = new Array(MAX_PLY);
    this.lenPV = new Array(MAX_PLY);

    this.STATUS = {
        OK        : 0,
        STALEMATE : 1,
        CHECKMATE : 2,
        DRAW_REP  : 3,
        DRAW_50   : 5
    };
};
/** setBOARD(fen)  getFEN()  dumpBOARD() *******************************************************/

qengine.prototype.setBOARD = function(fen) {
    var BOARD = this.BOARD;
    var i = 128; while(i) BOARD[--i] = 0;
    var recs = fen.split(/\s+/);
    var board = recs[0].split(/\x2f/).reverse().join('');
    var ofs = 0;
    var sq_king = this.sq_king;
    board.replace(/[prbnqk]|[1-8]/ig, function(x) {
                      if(x<='8') ofs += x-0;
                      else {
                          var sq = ((ofs >> 3) << 4) | (ofs & 7);
                          BOARD[sq] = pc_cod[x];
                          if(/k/i.test(x)) 
                              if(x=='K') sq_king[0] = sq; else sq_king[1] = sq;
                          ofs++;
                      }
                  });
    this.to_move = (/^w$/i.test(recs[1])) ? 0 : 1; // WHITE = 0
    this.castle = 0; this.en_pass = -1;
    var roq = recs[2].split(''); 
    for(i=0, n = roq.length; i < n; i++) {
        switch(roq[i]) {
        case 'K': this.castle |= 1; break;
        case 'Q': this.castle |= 2; break;
        case 'k': this.castle |= 4; break;
        case 'q': this.castle |= 8;
        }
    }
    var ep = recs[3] || "-"; 
    if(ep != "-") this.en_pass = (ep.charCodeAt(0) - 97) + 16*(ep.charCodeAt(1) - 49);
    this.fifty = recs[4] || 0; this.nr_move = recs[5] || 0;
//    this.gh_top = 0;
    for(i = 2; i <= 13; i++) {
        this.heur_hist[i] = [];
        for(var j = 0; j < 120; j++)  
            this.heur_hist[i][j] = 0;
    }
    for(i = 0; i < MAX_PLY; i++) {
        this.lenPV[i] = 0;
        this.PV[i] = [];
        for(var j = 0; j < MAX_PLY; j++)
            this.PV[i][j] = 0;
    }
};

qengine.prototype.getFEN = function() {
    var a = [], BOARD = this.BOARD;
    for (var row = 7; row >= 0; row--) {
        var str = "", empty = 0;
        for (var col = 0; col < 8; col++) {
            var pc = BOARD[(row << 4) | col];  
            if (pc > 0) {
                if (empty) str += empty;
                empty = 0;
                str += pc_char[pc];
            } else {
                empty++;
            }
        }
        if (empty) str += empty;
        a.push(str);
    }
    var pos = a.join("/");
    a = [ pos ];
    a[1] = this.to_move ? "b" : "w";
    var q = "", castle = this.castle;
    if(castle) {
        if(castle & 1) q += 'K';
        if(castle & 2) q += 'Q';
        if(castle & 4) q += 'k';
        if(castle & 8) q += 'q';
    } else q = "-";
    a[2] = q, en_pass = this.en_pass;
    a[3] = en_pass > 0 ? (String.fromCharCode(97 + (en_pass & 7)) + ((en_pass >> 4) +1)) : "-";
    a[4] = this.fifty;
    a[5] = this.nr_move;
    return a.join(" ");
};
qengine.prototype.dumpBOARD = function() {
    var fen = this.getFEN(); 
    var a = fen.split(/ /);
    fen = a[0].replace(/([1-8])/g, function(s){ var h = ''; for(var i=0; i < s; i++) h+=" "; return h; })
        .replace(/(\w| )/g, function(s){ return "|" + s; })
        .replace(/\x2f/g, '|<br>|-+-+-+-+-+-+-+-|<br>');
    fen += '|';
    return "+-+-+-+-+-+-+-+-+<br>" + fen + "<br>+-+-+-+-+-+-+-+-+";
}

/** isAttacked ( sq, side ) ****************************************************************************/

qengine.prototype.isAttacked = function( sq, side ) {  // SQ isAttacked by SIDE
    var sq1, dir; var knight = 4, rook = 10, queen = 12, bishop = 8, king = 6; var BOARD = this.BOARD;
    if(!side) {
        sq1 = sq - 15; // white pawn attack: from SQ-15 or from SQ-17
        if(!(sq1 & 0x88) && (BOARD[sq1] == 2)) return 1;
        sq1 -= 2;
        if(!(sq1 & 0x88) && (BOARD[sq1] == 2)) return 1;
    } else {
        sq1 = sq + 15; // black pawn attack: from SQ+15 or from SQ+17
        if(!(sq1 & 0x88) && (BOARD[sq1] == 3)) return 1;
        sq1 += 2;
        if(!(sq1 & 0x88) && (BOARD[sq1] == 3)) return 1;
        knight++; rook++; queen++; bishop++; king++;
    }
    for(dir = 0; dir < 8; dir++ ) {
        sq1 = sq + offs_n[dir];
        if(!(sq1 & 0x88) && (BOARD[sq1] == knight)) return 1;
        sq1 = sq + offs_k[dir];
        if(!(sq1 & 0x88) && (BOARD[sq1] == king)) return 1;
    }
    for(dir = 0; dir < 4; dir++) {
        var step = offs_r[dir];
        sq1 = sq + step;
        while(!(sq1 & 0x88)) {
            var p = BOARD[sq1];
            if(p > 0) {
                if((p == rook) || (p == queen)) return 1;
                break;
            }
            sq1 += step;
        }
        step = offs_b[dir];
        sq1 = sq + step;
        while(!(sq1 & 0x88)) {
            var p = BOARD[sq1];
            if(p > 0) {
                if((p == bishop) || (p == queen)) return 1;
                break;
            }
            sq1 += step;
        }
    }
    return 0;
}

/*
 for MOVE will use 32 bits (24 is sufficient, but is a bad memory allocation)

 FLSP   8 bits 31..24

 bit-31 = 0 (to avoid negative integers)
 bits 30..28  reserved flags (seven disponible values, 1..7)

 bits 27..24  for special moves, by the value of this field:

 = 4, 5, 8 - 13 = promoted piece (= pc_char[value])
 = 1 => castling O-O
 = 2 => castling O-O-O
 = 0x0E => pawn jump-2 move
 = 0x0F => en-passant move

 = 3 => non-capturing and non-pawn move (and non-castling); a reversible move
 = 6 => normal-pawn, including capture
 = 7 => capturing move with a non-pawn piece

 FROM  8 bits 23..16
 TO    8 bits 15..8

 MOVED 4 bits 7..4 values 2..13 = the piece moved FROM - TO
 CAPT  4 bits 3..0 values 0, 2..13 = the captured piece, if any

 */

qengine.prototype.gen_moves = function(moves) {
    var ocsq = [], BOARD = this.BOARD, castle = this.castle, to_move = this.to_move;
    for (var i = 0; i < 120; i++) if(!(i & 0x88) && BOARD[i] && ((BOARD[i] & 1) == to_move)) ocsq.push(i);
    if(!to_move) { // is white=0 to move; E1 = 4, G1 = 6, C1 = 2
        if((castle & 3) && !this.isAttacked(4, 1)) { // test legality for O-O, O-O-O
            if((castle & 1) && !(BOARD[5] || BOARD[6] || this.isAttacked(5, 1) || this.isAttacked(6, 1)) )
                moves.push([0x01040660, this.heur_hist[6][6]]);
            if((castle & 2) && !(BOARD[3] || BOARD[2] || BOARD[1] || this.isAttacked(3, 1) || this.isAttacked(2, 1)) )
                moves.push([0x02040260, this.heur_hist[6][2]]);
        }
    }
    else { // is black=1 to move; E8 = 0x74, G8 = 0x76, C8 = 0x71
        if((castle & 0x0C) && !this.isAttacked(0x74, 0)) {
            if((castle & 4) && !(BOARD[0x75] || BOARD[0x76] || this.isAttacked(0x75, 0) || this.isAttacked(0x76, 0)) )
                moves.push([0x01747670, this.heur_hist[7][0x74]]);
            if((castle & 8) && !(BOARD[0x73] || BOARD[0x72] || BOARD[0x71] || this.isAttacked(0x73,0) || this.isAttacked(0x72,0)))
                moves.push([0x02747270, this.heur_hist[7][0x72]]);
        }
    }
    for(var i = 0, np = ocsq.length; i < np; i++) {
        var sq = ocsq[i]; var p = BOARD[sq];
        if(p == (2 | to_move)) {
            if(!to_move) { // white
                if(sq < 0x60) { // not a promote move
                    if(!BOARD[sq + 16]) { // normal pawn move
                        moves.push([0x06000020 | (((sq << 8) | (sq + 16)) << 8), this.heur_hist[2][sq+16]]);
                    }
                    if((sq < 0x18) && !BOARD[sq+16] && !BOARD[sq + 32]) { // pawn-2-square move,
                        moves.push([0x0E000020 | (((sq << 8) | (sq + 32)) << 8), this.heur_hist[2][sq+32]]);
                    }
                }
                else { // four posible promotion moves
                    if(!BOARD[sq + 16]) {
                        var frto = ((sq << 8) | (sq + 16)) << 8;
                        moves.push( [0x0C000020 | frto, 1000],
                                    [0x0A000020 | frto, 600],
                                    [0x08000020 | frto, 350],
                                    [0x04000020 | frto, 350] );
                    }
                }
                for(var j = 15; j <= 17; j += 2) {
                    var sq1 = sq + j;
                    if(!(sq1 & 0x88)) { // pawn move - including promotion - with capture
                        var p1 = BOARD[sq1];
                        if(this.en_pass == sq1) { // mask =
                            moves.push([0x0F000023 | (((sq << 8) | sq1) << 8), 1000100]);
                        }
                        else if(p1 & 1) {
                            var vp = v_piece[p1];
                            if(sq >= 0x60) { // promotion with capture
                                var frto = ((sq << 8) | sq1) << 8;
                                moves.push( [0x0C000020 | frto | p1, 900 + vp],
                                            [0x0A000020 | frto | p1, 500 + vp],
                                            [0x08000020 | frto | p1, 250 + vp],
                                            [0x04000020 | frto | p1, 250 + vp] );
                            }
                            else {
                                moves.push([0x06000020 | (((sq << 8) | sq1) << 8) | p1, 1000000 + 10 * vp - v_piece[p]]);
                            }
                        }
                    }
                }
            }
            else { // black to_move
                if(sq >= 0x20) { // not a promotion move
                    if(!BOARD[sq - 16]) {
                        moves.push([0x06000030 | (((sq << 8) | (sq - 16)) << 8), this.heur_hist[3][sq-16]]);
                    }
                    if((sq >= 0x60) && !BOARD[sq-16] && !BOARD[sq - 32]) {
                        moves.push([0x0E000030 | (((sq << 8) | (sq - 32)) << 8), this.heur_hist[3][sq-32]]);
                    }
                }
                else { // four posible promotion moves
                    if(!BOARD[sq - 16]) {
                        var frto = ((sq << 8) | (sq - 16)) << 8;
                        moves.push( [0x0D000030 | frto, 1000],
                                    [0x0B000030 | frto, 600],
                                    [0x09000030 | frto, 350],
                                    [0x05000030 | frto, 350] );
                    }
                }
                for(var j = 15; j <= 17; j += 2) {
                    var sq1 = sq - j;
                    if(!(sq1 & 0x88)) { // pawn move with capture
                        var p1 = BOARD[sq1];
                        if(this.en_pass == sq1) { // mask = 0x0F
                            moves.push([0x0F000032 | (((sq << 8) | sq1) << 8), 90]);
                        }
                        else if((p1 > 0) && !(p1 & 1)) {
                            var vp = v_piece[p1];
                            if(sq < 0x20) { // promotion with capture
                                var frto = ((sq << 8) | sq1) << 8;
                                moves.push( [0x0D000030 | frto | p1, 900 + vp],
                                            [0x0B000030 | frto | p1, 500 + vp],
                                            [0x09000030 | frto | p1, 250 + vp],
                                            [0x05000030 | frto | p1, 250 + vp] );
                            }
                            else {
                                moves.push([0x06000030 | (((sq << 8) | sq1) << 8) | p1 , 1000000 + 10*vp - v_piece[p]]);
                            }
                        }
                    }
                }
            }
        }
        else {
            var ofdir = offs[p - to_move];
            for(var d = 0, nd = ofdir.length; d < nd; d++) {
                var sq1 = sq;
                for( ; ; ) {
                    sq1 += ofdir[d];
                    if(sq1 & 0x88) break;
                    if((p == (6 | to_move)) && this.isAttacked(sq1, to_move ^ 1)) break;
                    var p1 = BOARD[sq1];
                    if(!p1) {
                        moves.push([0x03000000 | (((sq << 8) | sq1) << 8) | (p << 4), this.heur_hist[p][sq1]]);
                    }
                    else {
                        if( (!to_move && (p1 & 1)) || (to_move && !(p1 & 1))) {
                            moves.push([0x07000000 | (((sq << 8) | sq1) << 8) | ((p << 4) | p1), 1000000 + 10*p1 - p]);
                            break;
                        }
                        else break;
                    }
                    if(!(p & 8)) break; // p is not a sliding piece
                }
            }
        }
    }
}

qengine.prototype.gen_capt_prom = function(moves) { 
    var ocsq = [], BOARD = this.BOARD, to_move = this.to_move;
    for (var i = 0; i < 120; i++) if(!(i & 0x88) && BOARD[i] && ((BOARD[i] & 1) == to_move)) ocsq.push(i);
    for(var i = 0, np = ocsq.length; i < np; i++) {
        var sq = ocsq[i]; var p = BOARD[sq];
        if(p == (2 | to_move)) {
            if(!to_move) { // white
                if(sq >= 0x60) { // a promote non-capturing move
                    if(!BOARD[sq + 16]) {
                        var frto = ((sq << 8) | (sq + 16)) << 8;
                        moves.push( [0x0C000020 | frto, 1000],
                                    [0x0A000020 | frto, 600],
                                    [0x08000020 | frto, 350],
                                    [0x04000020 | frto, 350] );
                    }
                }
                for(var j = 15; j <= 17; j += 2) {
                    var sq1 = sq + j;
                    if(!(sq1 & 0x88)) { // pawn move - including promotion - with capture (including en-passant)
                        var p1 = BOARD[sq1];
                        if(this.en_pass == sq1) {
                            moves.push([0x0F000023 | (((sq << 8) | sq1) << 8), 1000100]);
                        }
                        else if(p1 & 1) {
                            var vp = v_piece[p1];
                            if(sq >= 0x60) { // promotion with capture
                                var frto = ((sq << 8) | sq1) << 8;
                                moves.push( [0x0C000020 | frto | p1, 900 + vp],
                                            [0x0A000020 | frto | p1, 500 + vp],
                                            [0x08000020 | frto | p1, 250 + vp],
                                            [0x04000020 | frto | p1, 250 + vp] );
                            }
                            else {
                                moves.push([0x06000020 | (((sq << 8) | sq1) << 8) | p1, 1000000 + 10 * p1 - p]);
                            }
                        }
                    }
                }
            }
            else { // black to_move
                if(sq <= 0x20) { // a promotion non-capturing move
                    if(!BOARD[sq - 16]) {
                        var frto = ((sq << 8) | (sq - 16)) << 8;
                        moves.push( [0x0D000030 | frto, 1000],
                                    [0x0B000030 | frto, 600],
                                    [0x09000030 | frto, 350],
                                    [0x05000030 | frto, 350] );
                    }
                }
                for(var j = 15; j <= 17; j += 2) {
                    var sq1 = sq - j;
                    if(!(sq1 & 0x88)) { // pawn move with capture
                        var p1 = BOARD[sq1];
                        if(this.en_pass == sq1) { // mask = 0x80 | 0x40
                            moves.push([0x0F000032 | (((sq << 8) | sq1) << 8), 90]);
                        }
                        else if((p1 > 0) && !(p1 & 1)) {
                            var vp = v_piece[p1];
                            if(sq < 0x20) { // promotion with capture
                                var frto = ((sq << 8) | sq1) << 8;
                                moves.push( [0x0D000030 | frto | p1, 900 + vp],
                                            [0x0B000030 | frto | p1, 500 + vp],
                                            [0x09000030 | frto | p1, 250 + vp],
                                            [0x05000030 | frto | p1, 250 + vp] );
                            }
                            else {
                                moves.push([0x06000030 | (((sq << 8) | sq1) << 8) | p1 , 1000000 + 10*p1 - p]);
                            }
                        }
                    }
                }
            }
        }
        else {
            var ofdir = offs[p - to_move];
            for(var d = 0, nd = ofdir.length; d < nd; d++) {
                var sq1 = sq;
                for( ; ; ) {
                    sq1 += ofdir[d];
                    if(sq1 & 0x88) break;
                    var p1 = BOARD[sq1];
                    if(p1) {
                        if((p == (6 | to_move)) && this.isAttacked(sq1, to_move ^ 1)) break;
                        if( (!to_move && (p1 & 1)) || (to_move && !(p1 & 1))) {
                            moves.push([0x07000000 | (((sq << 8) | sq1) << 8) | ((p << 4) | p1), 1000000 + 10*p1 - p]);
                            break;
                        }
                        else break;
                    }
                    if(!(p & 8)) break; // p is not a sliding piece
                }
            }
        }
    }
}

qengine.prototype.makemove = function(move) {
    var spec = (move >> 24) & 0x0F;
    var from = (move >>> 16) & 0xFF;
    var to = (move >>> 8) & 0xFF;
    var BOARD = this.BOARD, to_move = this.to_move;
    //   var p = (move >> 4) & 0x0F;
    //   var p1 = move & 0x0F;
    var p = BOARD[from], p1 = BOARD[to];
    if((p1 == 6) || (p1 == 7)) return 0;   // is illegal to capture the adverse king
    // ignore the move if it is ilegal
    if((spec != 0x01) && (spec != 0x02)) { // non O-O or O-O-O (which have been tested for legality in gen_moves())
        BOARD[to] = p; // simulate the move (don't push the promoted piece on the board)
        BOARD[from] = 0;
        if(spec == 0x0F)  // simulate en-passant capture; is in check then?
            BOARD[to + (to_move ? 16 : -16)] = 0;
        var sqk = (p == (6 | to_move)) ? to : this.sq_king[to_move];// the actual square of the king
        if(this.isAttacked(sqk, to_move ^ 1)) { // if the to_move side will be in check, ignore the move
            BOARD[from] = p; BOARD[to] = p1;  // if(opp) alert(to_move+": "+from+" "+ to+" "+opp+" "+w);
            if(spec == 0x0F) { if(to_move) BOARD[to + 16] = 2; else BOARD[to - 16] = 3; }
            return 0;
        }
        BOARD[from] = p; BOARD[to] = p1;
    }
    // save from,to,p,p1 and the board-flags in game_hist[], then make the move on this board
    this.game_hist[this.gh_top++] = [ from, to, p, p1, this.castle, this.en_pass, this.fifty, spec ];
    if(this.en_pass > 0) this.en_pass = -1;
    switch(spec) {
    case 0x01: // O-O, // reset the castling rights // actualize sq_king[]
        if(!to_move) { BOARD[5] = 10; BOARD[6] = 6; BOARD[7] = BOARD[4] = 0; }
        else { BOARD[0x75] = 11; BOARD[0x76] = 7; BOARD[0x77] = BOARD[0x74] = 0; }
        this.fifty ++;
        break;
    case 0x02: // O-O-O, // reset the castling rights // actualize sq_king[]
        if(!to_move) { BOARD[3] = 10; BOARD[2] = 6; BOARD[0] = BOARD[4] = 0; }
        else { BOARD[0x73] = 11; BOARD[0x72] = 7; BOARD[0x70] = BOARD[0x74] = 0; }
        this.fifty ++;
        break;
    case 0x03: // a non capturing and non-pawn move (and non-castling)
        BOARD[to] = p; BOARD[from] = 0;
        this.fifty ++;
        break;
    case 0x07: // captures with p != pawn
    case 0x06: // pawn normal (non-enPass, non-2sq, non-promotion) move (including capture);
        BOARD[to] = p; BOARD[from] = 0; this.fifty = 0;
        break;
    case 0x0C:
    case 0x0A:
    case 0x08:
    case 0x04:
    case 0x0D:
    case 0x0B:
    case 0x09:
    case 0x05:
        BOARD[to] = spec; BOARD[from] = 0;
        this.fifty = 0;
        break;
    case 0x0F: // en-passant capture. Reset the en-pass field, erase the opponent's pawn
        if(!to_move) BOARD[to - 16] = 0;
        else BOARD[to + 16] = 0;
        BOARD[to] = p; BOARD[from] = 0;
        this.fifty = 0;
        break;
    case 0x0E: // pawn-two-squares move. Set the en-pass field
        BOARD[to] = p; BOARD[from] = 0;
        this.en_pass = to_move ? to + 16 : to - 16;
        this.fifty = 0;
        break;
    }
    switch(p) {
    case 6:  if(this.castle & 3) this.castle &= 0x0C; // wrong  ^= 3;
        this.sq_king[0] = to;
        break;
    case 7:  if(this.castle & 0x0C) this.castle &= 3; // ^= 0x0C; ??
        this.sq_king[1] = to;
        break;
    case 10: if((this.castle & 1) && (from == 7)) this.castle ^= 1;
        else { if((this.castle & 2) && (from == 0)) this.castle ^= 2; }
        break;
    case 11: if((this.castle & 4) && (from == 0x77)) this.castle ^= 4;
        else { if((this.castle & 8) &&(from == 0x70)) this.castle ^= 8; }
        break;
    }
    switch(p1) {
    case 10:  if((this.castle & 1) && (to == 7)) this.castle ^= 1;
        else { if((this.castle & 2) && (to == 0)) this.castle ^= 2; }
        break;
    case 11:  if((this.castle & 4) && (to == 0x77)) this.castle ^= 4;
        else { if((this.castle & 8) &&(to == 0x70)) this.castle ^= 8; }
        break;
    }
    this.to_move ^= 1;
    if(this.to_move) ++this.nr_move;
    return 1;
}

qengine.prototype.takeback = function() {
    var move = this.game_hist[--this.gh_top]; 
    this.castle = move[4];
    this.en_pass = move[5];
    this.fifty = move[6];
    var p = move[2]; 
    var BOARD = this.BOARD;
    if(p == 6) this.sq_king[0] = move[0];
    else { if(p == 7) this.sq_king[1] = move[0]; }
    BOARD[move[0]] = p;
    BOARD[move[1]] = move[3];
    this.to_move ^= 1;
    switch(move[7]) {
    case 1: if(!this.to_move) { // if castling move, put the rook at initial square
        BOARD[7] = 10; BOARD[5] = 0;
    }
        else {
            BOARD[0x77] = 11; BOARD[0x75] = 0;
        }
        break;
    case 2: if(!this.to_move) { // O-O-O
        BOARD[0] = 10; BOARD[3] = 0;
    }
        else {
            BOARD[0x70] = 11; BOARD[0x73] = 0;
        }
        break;
    case 0x0F: // if en-passant move, put back the captured pawn
        if(!this.to_move) BOARD[move[1] - 16] = 3;
        else BOARD[move[1] + 16] = 2;
        break;
    }
    if(!this.to_move) --this.nr_move; // reset the full number of moves, when black's turn to move
}

/** search() **************************************************************/

qengine.prototype.findBestMove = function() { 
    this.ply_mov = new Array(); var i, j, hh;
    for(i = 2; i <= 13; i++) {  // the History Heuristic: increase the score for a move that causes a cutoff;
        hh = this.heur_hist[i] = [];     // moves will be dynamically ordered according to their prior history score (if any)
        //for(var j = 0; j < 120; j++) // (a move is "good" if it produces a cutoff-node in alphabeta algorithm (>= beta),
        //this.heur_hist[p][j] = 0;      // or it returns the best minimax value)
        j = 120; do { hh[--j] = 0; } while(j);
    }
    for(i = 0; i < MAX_PLY; i++) { // init Principal Variation; PV collect moves with returned score in (alpha, beta),
        this.lenPV[i] = 0;                   // assuming (or proving) for the rest of the moves that they are all bad.
        j = MAX_PLY;
        hh = this.PV[i] = new Array(j);     // (and if one of these was better than the first PV move - it has to search again,
        //for(var j = 0; j < MAX_PLY; j++) // in the normal alpha-beta manner)
        do { hh[--j] = 0; } while(j);
    }
    this.ply = 0; // generate the game tree of the derived positions
    this.nodes = 0;
    var depth, best;
    for(depth = 1; depth <= max_DEPTH; ++depth) { // Iterative Deepening in the tree
        this.have_pv = true;                            // (at the next iteration will have a better ordering; the best move for
        best = this.searchMove(-10000, 10000, depth);   // depth d will often turn out to be the best move for depth d + 1 too)
        // the number of nodes visited by all successive iterations taken together is generally much smaller
        // than that of a single non-iterative search to the full depth (because of the possibility to re-order moves
        // dynamically after every iteration has been completed)

        if(best > 9000 || best < -9000) break;
    }
//    alert(this.gh_top + '\n' + this.game_hist[this.gh_top]);
    return this.PV[0][0];
}

qengine.prototype.searchMove = function(alpha, beta, depth) {  // negamax style, with PV
    var i, j, n, best, in_check, found;
    if(!depth) return this.quiesce(alpha, beta); // evaluate() is a static-evaluation here, so try to find a stable position
    // (at least, without captures) before pass the position to evaluate())
    this.lenPV[this.ply] = this.ply;
    if(this.ply && this.repetitions()) return 0;
    in_check = this.isAttacked(this.sq_king[this.to_move], this.to_move ^ 1);
    this.ply_mov[this.ply] = new Array(); var childs = this.ply_mov[this.ply];
    if(in_check) depth++; // TODO gen_escape_check(childs);
    this.gen_moves(childs); // generate the pseudolegal moves in the current position (the ply's move list)
    n = childs.length;
    if(this.have_pv == true) { // if exists a PV node in the ply's move list, high-score it and swap it in childs[],
        this.have_pv = false;  // so that it (the PV move) will be played first
        for(i = 0; i < n; i++) {
            if(childs[i][0] == this.PV[0][this.ply]) {
                this.have_pv = true;
                childs[i][1] += 10000000;
                break;
            }
        }
    }
    found = false; // find a legal move
    for(i = 0; i < n; i++) {
        // swap the i-move with the j-move (j > i) which has the highest score
        var bs = -1, bi = i, g = childs[i];
        for(j = i; j < n; j++)
            if(childs[j][1] > bs) {
                bs = childs[j][1];
                bi = j;
            }
        childs[i] = childs[bi];
        childs[bi] = g;   // end swap(i)
        var thm = childs[i][0];
        if(thm && this.makemove(thm)) {
            found = true; // will find a legal move and play it
            this.ply++;        // investigate the possible replies, using (and updating) the alpha-beta window
            best = - this.searchMove(-beta, -alpha, depth - 1);
            this.ply--;
            this.takeback();
            if(best > alpha) { // thm-move caused a cutoff, so gets ordered high in the future search
                this.heur_hist[(thm >> 4) & 0x0F][(thm >> 16) & 0xFF] += (1 << depth);
                if(best >= beta) return best;  // beta (11.08.09) // thm-move is a beta-node; the rest of the children are pruned
                alpha = best;  // PV-node
                this.PV[this.ply][this.ply] = thm; var p1 = this.lenPV[this.ply + 1]; // update the PV list at ply's level
                for(j = this.ply + 1; j < p1; j++)                // (keeping for the next iteration, the best moves
                    this.PV[this.ply][j] = this.PV[this.ply + 1][j];             // found at (ply +1)'s level of the search tree)
                this.lenPV[this.ply] = p1;
            }
        }
    }
    if(!found) { // no legal moves
        if(in_check) return -10000 + this.ply;  // is checkmate
        else return 0; // is stalemate
    }
    if(this.fifty >= 100) return 0; // fifty move draw rule
    return alpha;
};

// qengine.prototype.pos_eval = function() { return qvariant == 1 ? this.evaluate() : this.std_eval(); };

qengine.prototype.quiesce = function(alpha, beta) { // expand the search when at last iteration the resulting position
    var i, n, j, best;           // is not-quiet (while capture or promotion moves exists)
    this.nodes++; // count the evaluated nodes
    best = this.std_eval(); //this.pos_eval(); //this.evaluate();
    if(best >= beta) return beta;
    if(best > alpha) alpha = best;
    this.lenPV[this.ply] = this.ply;
    this.ply_mov[this.ply] = new Array(); var childs = this.ply_mov[this.ply];
    this.gen_capt_prom(childs);
    n = childs.length; 
    //     var all = ""; for(var h = 0; h < n; h++) all += childs[h][0].toString(16) + "\n"; alert(to_move+"\n"+all);
    if((n > 0) && this.have_pv) { // first - a PV node, if exists
        this.have_pv = false;
        for(i = 0; i < n; i++) {
            if(childs[i][0] == this.PV[0][this.ply]) {
                this.have_pv = true;
                childs[i][1] += 1000000;
                break;
            }
        }
    }
    for(i = 0; i < n; i++) {
        // swap the i-move with the j-move (j > i) which has the highest score
        var bs = -1, bi = i, g = childs[i];
        for(j = i; j < n; j++)
            if(childs[j][1] > bs) {
                bs = childs[j][1];
                bi = j;
            }
        childs[i] = childs[bi];
        childs[bi] = g;   // end swap(i)
        var thm = childs[i][0];
        if(thm && this.makemove(thm)) {
            this.ply++;
            best = - this.quiesce(-beta, -alpha);
            this.ply--;
            this.takeback();
            if(best > alpha) {
                if(best >= beta) return beta; //  best; ??  // the rest of the children are pruned
                alpha = best;
                this.PV[this.ply][this.ply] = thm; // update the PV
                var p1 = this.lenPV[this.ply + 1];
                for(j = this.ply + 1; j < p1; j++)
                    this.PV[this.ply][j] = this.PV[this.ply + 1][j];
                this.lenPV[this.ply] = p1;
            }
        }
    }
    return alpha;
}

qengine.prototype.repetitions = function() {
    if(this.fifty < 7) return 0;
    var b = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
    var c = 0;  // count of squares that are different from the current position
    var r = 0;  // number of repetitions
//    alert(this.gh_top + '\n' + this.fifty + '\n' + this.game_hist);
    for(var i = this.gh_top - 1; i >= this.gh_top - this.fifty; --i) {
       if (++b[this.game_hist[i][0]] == 0)
           --c;
       else
           ++c;
       if (--b[this.game_hist[i][1]] == 0)
           --c;
       else
           ++c;
       if (c == 0)
           ++r;
    }
    return (r==3);
}

qengine.prototype.evaluate = function() { 
//    this.nodes++; // count the evaluated nodes
    var BOARD = this.BOARD;
    var ocsq = []; var sq, row, col, pp, i;
    var pbits0 = [0,0,0,0,0,0,0,0], pbits1 = [0,0,0,0,0,0,0,0];
    var st_eval0 = 0, st_eval1 = 0;
    var piece_mat0 = 0, piece_mat1 = 0;
    var pawn_mat0 = 0, pawn_mat1 = 0;
    for (sq = 120; --sq >= 0;)
        if(!(sq & 0x88) && BOARD[sq])
            ocsq.push(sq);
    var nr = ocsq.length;
    for(i = nr; --i >= 0;) {
        sq = ocsq[i]; col = sq & 7; row = sq >> 4;
        pp = BOARD[sq];
        switch(pp) {
        case 2: pawn_mat0 += 100;
            pbits0[col] |= (1 << (row - 1));
            break;
        case 3: pawn_mat1 += 100;
            pbits1[col] |= (1 << (row - 1));
            break;
        case 4:
        case 8:
        case 10:
        case 12: piece_mat0 += v_piece[pp];
            break;
        case 5:
        case 9:
        case 11:
        case 13: piece_mat1 += v_piece[pp];
            break;
        }
    }
    st_eval0 = piece_mat0 + pawn_mat0;
    st_eval1 = piece_mat1 + pawn_mat1; 
    for(i = nr; --i >= 0;) {
        sq = ocsq[i]; col = sq & 7; row = sq >> 4;
        pp = BOARD[sq];
        switch(pp) {
        case  2:  st_eval0 += sPAWN[0][sq];
            var bits = pbits0[col];
            var msb = last1(bits), lsb = first1(bits);
            var left = col > 0 ? last1(pbits0[col - 1]) : 0;
            var right = col < 7 ? last1(pbits0[col + 1]) : 0;
            if(lsb != msb)
                st_eval0 -= 10; // DOUBLED PAWN penalty
            if(!(left || right))
                st_eval0 -= 20; // ISOLATED PAWN penalty
            else {
                if((left > msb) && (right > msb))
                    st_eval0 -= 8; // BACKWARDS PAWN penalty
            }
            left = col > 0 ? first1(pbits1[col - 1]) : 0;
            right = col < 7 ? first1(pbits1[col + 1]) : 0;
            if((msb >= left) && (msb >= right))
                st_eval0 += 20; // PASSED PAWN bonus
            break;
        case  3:  st_eval1 += sPAWN[1][sq];
            var bits = pbits1[col]; var msb = last1(bits), lsb = first1(bits);
            var left = col > 0 ? last1(pbits1[col - 1]) : 0;
            var right = col < 7 ? last1(pbits1[col + 1]) : 0;
            if(lsb != msb)
                st_eval1 -= 10; // DOUBLED PAWN penalty
            if(!(left || right))
                st_eval1 -= 20; // ISOLATED PAWN penalty
            else {
                if((left < msb) && (right < msb))
                    st_eval1 -= 8; // BACKWARDS PAWN penalty
            }
            left = col > 0 ? first1(pbits0[col - 1]) : 0;
            right = col < 7 ? first1(pbits0[col + 1]) : 0;
            if((msb <= left) && (msb <= right))
                st_eval1 += 20; // PASSED PAWN bonus
            break;
        case  4:  st_eval0 += sKnight[0][sq];
            break;
        case  5:  st_eval1 += sKnight[1][sq];
            break;
        case  6:  if((st_eval1 - pawn_mat1) > 1400) { // opening or midlegame - 2200 ??
            st_eval0 += sKing[0][sq];
            // penalties for the pawn cover being far or not having any
            if((col > 4) || (col < 3)) {
                var p0 = first1(pbits0[col]) + 1;
                var p1 = col > 0 ? first1(pbits0[col-1]) + 1 : 0;
                var p2 = col < 7 ? first1(pbits0[col+1]) + 1 : 0;
                if(p0 && (p0 - 1 > row)) st_eval0 -= 8 * (p0 - row - 1);
                else if(!p0) st_eval0 -= 12;
                if(p1 && (p1 - 1 > row)) st_eval0 -= 8 * (p1 - row - 1);
                else if(!p1) st_eval0 -= 12;
                if(p2 && (p2 - 1 > row)) st_eval0 -= 8 * (p2 - row - 1);
                else if(!p2) st_eval0 -= 12;
            }
        }
            else { // endgame
                st_eval0 += sKing_end[sq];
            }
            break;
        case  7:  if((st_eval0 - pawn_mat0) > 1400) {
            st_eval1 += sKing[1][sq];
            // penalties for the pawn cover being far or not having any
            if((col > 4) || (col < 3)) {
                var p0 = last1(pbits1[col]);
                var p1 = col > 0 ? last1(pbits1[col-1]) : 0;
                var p2 = col < 7 ? last1(pbits1[col+1]) : 0;
                if(p0 && (p0 + 1 < row)) st_eval1 -= 8 * (row - p0 - 1);
                else if(!p0) st_eval1 -= 12;
                if(p1 && (p1 + 1 < row)) st_eval1 -= 8 * (row - p1 - 1);
                else if(!p1) st_eval1 -= 12;
                if(p2 && (p2 + 1 < row)) st_eval0 -= 8 * (row - p2 - 1);
                else if(!p2) st_eval1 -= 12;
            }
        }
            else {
                st_eval1 += sKing_end[sq];
            }
            break;
        case  8:  st_eval0 += sBishop[0][sq];
            //if((sq == 0x24) || (sq == 0x23))
            //if(BOARD[sq-0x10] == 2) st_eval -= 10; // do not to block e2/d2 pawn!
            break;
        case  9:  st_eval1 += sBishop[1][sq];
            //if((sq == 0x54) || (sq == 0x53))
            //if(BOARD[sq+0x10] == 3) st_eval -= 10; // not to block e7/d7 pawn!
            break;
        case 10:  if(!pbits0[col]) {
            if(!pbits1[col])
                st_eval0 += 15; // ROOK OPEN FILE bonus
            else st_eval0 += 10; // ROOK SEMIOPEN FILE bonus
        }
            if(row == 6) st_eval0 += 20; // ROOK ON SEVENTH bonus
            break;
        case 11:  if(!pbits1[col]) {
            if(!pbits0[col])
                st_eval1 += 15; // ROOK OPEN FILE bonus
            else st_eval1 += 10; // ROOK SEMIOPEN FILE bonus
        }
            if(row == 1) st_eval0 += 20; // ROOK ON SEVENTH bonus
            break;
        case 12:  st_eval0 += sQueen[0][sq];
            break;
        case 13:  st_eval1 += sQueen[1][sq];
            break;
        }
    }
    return this.to_move ? st_eval1 - st_eval0 : st_eval0 - st_eval1;
}


function last1(bits) { // the rang of the Most Significant 1 Bit (the row of the pawn in a column)
    if(bits >= 32) return 6;
    if(bits >= 16) return 5;
    if(bits >= 8) return 4;
    if(bits >= 4) return 3;
    if(bits >= 2) return 2;
    if(bits) return 1;
    return 0;
}
function first1(bits) {
    if(!bits) return 0;
    if(bits < 2) return 1;
    if(bits < 4) return 2;
    if(bits < 8) return 3;
    if(bits < 16) return 4;
    if(bits < 32) return 5;
    return 6;
}

qengine.prototype.status = function() {
    var GLOBMOVES = []; this.gen_moves(GLOBMOVES);
    var found = false;
    for (var i = GLOBMOVES.length; --i >= 0;) {
        if (this.makemove(GLOBMOVES[i][0])) {
            found = true;
            this.takeback();
            break;
        }
    }
    if (!found)
        return this.isAttacked(this.sq_king[this.to_move], this.to_move ^ 1) ? this.STATUS.CHECKMATE : this.STATUS.STALEMATE;
    if (this.repetitions())
        return this.STATUS.DRAW_REP;
    if (this.fifty >= 100)
        return this.STATUS.DRAW_50;
    return found;
}

qengine.prototype.validate = function(move) { 
    var globmoves = [];
    this.gen_moves(globmoves); 
    for (var i = 0, n = globmoves.length; i < n; i++) {
        var m = globmoves[i][0];
        if (((m >> 8) & 0xFFFF) == move) {
            if(this.makemove(m)) {
                this.takeback();
                return m;
            }
        }
    }
    return 0;
}

/*
 function Perft(depth) {
 var move_list = [];
 move_list[depth] = [];
 var n_moves, i, nodes = 0;
 if(depth == 0) return 1;
 gen_moves(move_list[depth]);
 n_moves = move_list[depth].length;
 for(i = 0; i < n_moves; i++) {
 var mv = move_list[depth][i][0];
 if(makemove(mv)) {
 nodes += Perft(depth-1);
 takeback();
 }
 }
 return nodes;
 }
 */