Open njsfield opened 7 years ago
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)....
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
Functions needed =
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.
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)
}
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)...
Issue label added for help wanted
https://en.wikipedia.org/wiki/Minimax