// Iterative Deepening Search
// Calls mtdf at each depth until we hit the depth limit or run out of time
List itSearch(Position pos, int timeLimit){
nodesSearched = 0;
tpLookups = 0;
tpScore.clear(); // clear the transposition table for scores but not for moves
Stopwatch timer = new Stopwatch()..start();
int startTime = timer.elapsedMilliseconds;
Move bestMove;
double f = 0;
int maxDepthSearched = 0;
for(int depth = 1; depth <= MAX_SEARCH_DEPTH; depth++){
int nodesSoFar = nodesSearched;
tpScore.clear();
pos.stage = 0;
maxDepthSearched = depth;
List _l = mtdf(pos, f, depth, timer, timeLimit);
f = _l[0];
if(true) bestMove = tpMove[pos.hash]; // if(_l[1]) -> only uses moves computed by a complete mtdf evaluation
double timeTaken = (timer.elapsedMilliseconds - startTime) / 1000;
int nodesHere = nodesSearched - nodesSoFar;
double nps = nodesHere/timeTaken;
print("Searched depth $depth: $nodesHere nodes in ${timeTaken.toStringAsFixed(2)}s (${nps.toStringAsFixed(2)} NPS)");
print("Best move so far is ${bestMove.name}");
if(timer.elapsedMilliseconds - startTime > timeLimit){
print("Time limit hit");
break;
}
}
// This part is just for formatting lines to print to the console
Map lines = Map();
for(Move m in pos.moves){
String mvName = formatMove(m);
lines[mvName] = [(pos.board[PLAYER_TURN] == WHITE)?"${pos.board[FULLMOVE_COUNTER]} ":"", m.endPosition.eval];
Position p = m.endPosition;
Move nextMove = p.bestMove;
bool first = true;
while(p != null && nextMove != null){
String next = formatMoveForList(p.board, nextMove, first);
first = false;
lines[mvName][0] += next;
//print("Checking ${nextMove.name}");
p = nextMove.endPosition;
//print(p.bestMove);
if(p != null) nextMove = p.bestMove;
if(nextMove == null){
//print("next move after ${p.previousMove.name} is null");
break;
}
}
}
double timeTaken = (timer.elapsedMilliseconds - startTime) / 1000;
double nps = nodesSearched/timeTaken;
print("Iterative search terminated at depth $maxDepthSearched, having searched $nodesSearched nodes in ${timeTaken.toStringAsFixed(2)}s (${nps.toStringAsFixed(2)} NPS)");
print("$tpLookups transposition table lookups");
return [bestMove, f, lines];
}
// Aske Plaat's MTD(f) algorithm
// Calls abm (Alpha-Beta with Memory) a number of times with a gradually converging search window
List mtdf(Position pos, double target, int depth, Stopwatch timer, int timeLimit){
double currentEstimate = target;
var upper = MATE_UPPER;
var lower = -MATE_UPPER;
int pass = 1;
while(lower < upper){
double beta = max(currentEstimate, lower + 0.01);
currentEstimate = -abm(pos, 1-pos.board[PLAYER_TURN], depth, 0, beta - 0.01, beta, true, false);
print("MTDF pass $pass (currentEstimate: $currentEstimate), beta: ${beta.toStringAsFixed(2)} lower: ${lower.toStringAsFixed(2)}, upper: ${upper.toStringAsFixed(2)}");
if(currentEstimate < beta) upper = currentEstimate;
else lower = currentEstimate;
pass++;
if(timer.elapsedMilliseconds > timeLimit){
print("Time limit hit in mtdf");
return [currentEstimate, false];
break;
}
}
return [currentEstimate, true];
}
// Alpha-Beta with Memory (Negamax)
double abm(Position pos, int player, int depth, int stage, double alpha, double beta, bool root, [bool allowNull = true]){
//print("ABM");
nodesSearched++;
// Check transposition tables haven't grown too large
if(tpMove.length > MAX_TRANSPOSITIONS){
print("Clearing transposition table for moves (${tpMove.length})");
tpMove.clear();
}
if(tpScore.length > MAX_TRANSPOSITIONS){
print("Clearing transposition table for scores (${tpScore.length})");
tpScore.clear();
}
// retrieve stored values from transposition table
List _tpScore = tpScore[pos.dhash];
if(_tpScore != null){
tpLookups++;
if(_tpScore[0] >= beta) return _tpScore[0];
if(_tpScore[1] <= alpha) return _tpScore[1];
alpha = max(alpha, _tpScore[0]);
beta = min(beta, _tpScore[1]);
//print("($stage) tp lookup $alpha $beta");
}else{
tpScore[pos.dhash] = [-MATE_UPPER, MATE_UPPER];
}
double g;
if(tpMove[pos.hash] == null) tpMove[pos.hash] = pos.moves[0];
bool qSearch = (depth <= 0); // are we in quiescence search?
// if so, only generate noisy moves (captures)
List<Move> _moves = (!qSearch)?pos.moves:pos.moves.where((_m) => !_m.quiet).toList();
//print("Moves: ${_moves.map((x) => x.name).toList()}");
// Null-Move Heuristic
// CURRENTLY DISABLED FOR SIMPLIITY / DEBUGGING
if(allowNull){
Move _nullMove = Move.nullMove(pos);
double eval = -abm(_nullMove.endPosition, 1-player, depth - 3, stage + 1, -beta, -beta+0.0001, false, false);
if(eval >= beta){
pos.eval = eval;
return eval;
}
}
// ---------
// -10 means 10 moves into quiescence search, increasing doesn't change much except massively slowing everything down
if(_moves.length == 0 || depth <= -10) g = (player != pos.analysisPlayer)?pos.score:-pos.score; // if we've hit the end of the evaluation
else{
if(qSearch){ // STAND PAT
double stand_pat = (player != pos.analysisPlayer)?pos.score:-pos.score;
if(stand_pat >= beta) return beta;
if(alpha < stand_pat) alpha = stand_pat;
}
g = -MATE_UPPER;
double a = alpha;
for(Move m in _moves){
if(m.valid){
m.endPosition.eval = -abm(m.endPosition, 1-player, depth - 1, stage + 1, -beta, -a, false, false);
if(m.endPosition.eval > g){
tpMove[pos.hash] = m;
pos.bestMove = m;
g = m.endPosition.eval;
}
if(g > a){
a = g;
tpMove[pos.hash] = m;
pos.bestMove = m;
}
}
// CUTOFF
//if(a >= beta) break;
}
}
if(g <= alpha) tpScore[pos.dhash][1] = g; // fail low implies an upper bound
if(g > alpha && g < beta){ // found an accurate minimax value
tpScore[pos.dhash] = [g,g];
}
if(g >= beta) tpScore[pos.dhash][0] = g; // fail high implies a lower bound
return g;
}