Employ minimax solution to generate opponent move

[njsfield]

https://en.wikipedia.org/wiki/Minimax

[njsfield]

Variant of minimax is Negamax

Pseudo Code =

int negaMax( int depth ) {
    if ( depth == 0 ) return evaluate();
    int max = -oo;
    for ( all moves)  {
        score = -negaMax( depth - 1 );
        if( score > max )
            max = score;
    }
    return max;
}

In the body of the loop of this root negaMax, in the loop which generates all the root moves – there one holds a variable as you call negaMax on the movement of each piece – and that is where you find the particular move attached to the score – in the line where you find score > max, right after you keep track of it by adding max = score – in the root negamax, that is where you pick out your move – which is what the root negaMax will return (instead of a score)....

[njsfield]

So instead of just returning the highest score from moves...

string negaMax( int depth = 1, fen ) {
    if ( depth == 0 ) return evaluate();
    int max = -oo;
    let moves = getMoves(fen)
    let bestMove;
    for ( all moves)  {
        let newFen = newFenFromMove(fen, move)
        score = -negaMax( depth - 1, newMove);
        if( score > max )
            max = score;
            bestMove = move;
    }
    return bestMove;
}

Depth should be a minimum of 1

[njsfield]

Functions needed =

1. negaMax
2. evaluate()
3. getMoves(returns array of moves in the object form) - [ ...
   { from : a5
   to : d7
   }
   ]
4. newFenFromMove (takes above object, then returns new fen)
5. piecesTotal (takes string representing piece, returns number of pieces or 0 if none)
6. chess.turn (takes fen, finds who's turn it is)

[njsfield]

Evaluate function-

f(p) = 200(K-K')
       + 9(Q-Q')
       + 5(R-R')
       + 3(B-B' + N-N')
       + 1(P-P')
       - 0.5(D-D' + S-S' + I-I')
       + 0.1(M-M') + ...
 
KQRBNP = number of kings, queens, rooks, bishops, knights and pawns
D,S,I = doubled, blocked and isolated pawns
M = Mobility (the number of legal moves)

In negaMax practice (simplified)-

materialScore = kingWt  * (wK-bK)
              + queenWt * (wQ-bQ)
              + rookWt  * (wR-bR)
              + knightWt* (wN-bN)
              + bishopWt* (wB-bB)
              + pawnWt  * (wP-bP)
 
mobilityScore = mobilityWt * (wMobility-bMobility)

score = (materialScore + mobilityScore) * who2Move

This method allows both calculations to be hardcoded, and who2Move is dependent on the fen passed in.

In Practice

string evaluate ( fen ) {
  string who2Move = whosTurn(fen); // chess.turn(fen)
  
  int materialScore = 
    (200 * (pieceTotal('K') - pieceTotal('k')) + 
    (9     * (pieceTotal('Q') - pieceTotal('q')) + 
    (5     * (pieceTotal('R') - pieceTotal('r')) +
    (3     * (pieceTotal('N') - pieceTotal('n')) + 
    (3     * (pieceTotal('B') - pieceTotal('b')) + 
    (1     * (pieceTotal('P') - pieceTotal('p'))

   int mobilityScore = 0.1 * (getMoves(fen).length)

   return (materialScore + mobilityScore) * (who2Move == 'w' ? 1 : -1)
}

[njsfield]

Progress-

import { player, canMove, pieceMoves, prepFen } from './fenmap';
var Chess = require('chess.js').Chess;


// Make negaMax
export const negaMax = (depth, fen) => {
    if ( depth === 0 ) return evaluate(fen);
    let max = -Infinity;
    let moves = getMoves(fen);
    let bestMove;
    for (let move of moves)  {
        let newFen = newFenFromMove(fen, move);
        let score = -(negaMax(depth - 1, newFen));
        if( score > max )
            max = score;
            bestMove = move;
    }
    return bestMove;
};

// Simplified Evaluate Function
export const evaluate = (fen) => {
  let whosGo = new Chess(fen).turn(); // Returns 'w' or 'b'

  let materialScore =
    (200   * (pieceTotal(fen,'K') - pieceTotal(fen,'k'))) +
    (9     * (pieceTotal(fen,'Q') - pieceTotal(fen,'q'))) +
    (5     * (pieceTotal(fen,'R') - pieceTotal(fen,'r'))) +
    (3     * (pieceTotal(fen,'N') - pieceTotal(fen,'n'))) +
    (3     * (pieceTotal(fen,'B') - pieceTotal(fen,'b'))) +
    (1     * (pieceTotal(fen,'P') - pieceTotal(fen,'p')));

   let mobilityScore = 0.1 * (getMoves(fen).length);

   return (materialScore + mobilityScore) * (whosGo === 'w' ? 1 : -1);
};

// Returns array of objects with (from & to)
export const getMoves = (fen) => {

  let flatten = (arr) => [].concat(...arr);

  let twoDimArr =
        canMove(fen, player(fen))
          .map(moveable => pieceMoves(fen, moveable)
            .map(newPos => { return {from: moveable, to: newPos};}));
  return flatten(twoDimArr);

};


// Returns array or empty array
export const pieceTotal = (fen, piece) => {
  let arr = prepFen(fen).join("").match(new RegExp(piece, 'g')) || [];
  return arr.length;
};


// newFenFromMove
export const newFenFromMove = (fen, move) => {
  let newPos = new Chess(fen);
  newPos.move(move);
  return newPos.fen();
};


// Default Export
export const bestMove = (fen) => negaMax(3, fen);

Is a working solution with a depth of 3 (computer analyses 3 moves ahead)...

. . .

. . .

. . .

TOOK 4 MINUTES TO CALCULATE !

Issue label added for help wanted