//
// search.cpp
// fornax3
//
// Created by Anders on 28/04/2019.
//
#include <thread>
#include <inttypes.h>
#include "search.hpp"
#include "../tt/transpositions.hpp"
#include "../moving/movegen.hpp"
#include "../moving/movepick.hpp"
#include "../moving/makemove.hpp"
#include "../moving/derived_knowledge.h"
#include "../parsing.hpp"
#include "../libs/stopwatch.h"
#include "../libs/iolog.hpp"
#include "../eval_defs.h"
#include "../supplementary/time_management.hpp"
#define CURRMOVE_NODE_THRESHOLD 2500000
#define SEARCH_DEPTH_MAX 128
static std::atomic<bool> async_is_currently_searching (false);
static std::atomic<bool> async_is_stop_command_given (false);
static std::atomic<uint64_t> node_count(0);
#ifdef DEBUGLOG
static uint64_t betacuts = 0;
#define DEBUG_STATS_INCREMENT_BETA_CUTS betacuts++;
static uint64_t quiesceCount = 0;
#define DEBUG_STATS_INCREMENT_QS_COUNT quiesceCount++;
static uint64_t transpositionHits = 0;
#define DEBUG_STATS_INCREMENT_TT_HITS transpositionHits++;
static uint64_t transpositionCuts = 0;
#define DEBUG_STATS_INCREMENT_TT_CUTS transpositionCuts++;
static uint64_t nullcuts = 0;
#define DEBUG_STATS_INCREMENT_NULL_CUTS nullcuts++;
#define RESET_STATS node_count = 1;\
betacuts = 0;\
quiesceCount = 0;\
transpositionHits = 0;\
transpositionCuts = 0;\
nullcuts = 0
#else
#define DEBUG_STATS_INCREMENT_BETA_CUTS
#define DEBUG_STATS_INCREMENT_QS_COUNT
#define DEBUG_STATS_INCREMENT_TT_HITS
#define DEBUG_STATS_INCREMENT_TT_CUTS
#define DEBUG_STATS_INCREMENT_NULL_CUTS
#define RESET_STATS node_count = 1
#endif
typedef struct {
move bestmove;
move ponder;
eval score;
long duration_ms;
} SearchResult;
static inline uint64_t getnps(long duration) {
long time = duration | 1;
return ((node_count | 1) / (uint32_t) time) * 1000;
}
static inline void printline(Board* board, uint8_t depth, eval ev, move mov, long duration) {
uint64_t nodes = node_count;
IO_PRINT("info depth %d score cp %d nodes %" PRIu64 " nps %" PRIu64, depth, ev, nodes, getnps(duration));
#ifdef DEBUGLOG
IO_PRINT(" tthits %" PRIu64, transpositionHits);
IO_PRINT(" ttcuts %" PRIu64, transpositionCuts);
IO_PRINT(" qnodes %" PRIu64, quiesceCount);
IO_PRINT(" betacuts %" PRIu64, betacuts);
IO_PRINT(" nullcuts %" PRIu64, nullcuts);
#endif
IO_PRINT(" ");
parsing_printpv(board, mov, depth);
IO_PRINT("\n");
IO_FLUSH();
}
static inline eval probe_tt(ttkey hash, move* ttmove, int depth, eval lower_bound, eval upper_bound) {
Bucket* b = transpositions_get(hash);
if (b->hash != hash) return EVAL_NONE;
*ttmove = b->ttmove;
DEBUG_STATS_INCREMENT_TT_HITS;
if (b->depth >= depth) {
DEBUG_STATS_INCREMENT_TT_CUTS;
tttype type = b->type;
if(type == TT_TYPE_EXACT) return b->tteval;
if(type == TT_TYPE_LOWER_BOUND && b->tteval <= lower_bound) return lower_bound;
if(type == TT_TYPE_UPPER_BOUND && b->tteval >= upper_bound) return upper_bound;
}
*ttmove = b->ttmove;
return EVAL_NONE;
}
static inline move probe_tt_move(ttkey hash) {
Bucket* b = transpositions_get(hash);
return b->hash == hash ? b->ttmove : MOVE_NONE;
}
template <color active>
static constexpr bool ischeck(const Board* node) {
constexpr color opp = COLOR_OPPOSITE(active);
return node->side[active].pieces[KING] & node->side[opp].attackmask;
}
#define REPETITION_HISTORY_SIZE 16
static inline bool is_repetition(const Board* board) {
if (board_get_currinfo(board)->halfmovecount < 4) return false;
if (board_get_currinfo(board)->halfmovecount >= 100) return true;
ttkey hash = board_get_currinfo(board)->hash;
uint8_t end = board->ply - REPETITION_HISTORY_SIZE;
for (uint8_t i = board->ply - 2; i != end; i -= 2) {
if (hash == board->plyinfo[i].hash) return true;
}
return false;
}
template <color active>
static eval quiesce(Board* node, uint8_t depth, eval lower_bound, eval upper_bound) {
constexpr color opp = COLOR_OPPOSITE(active);
DEBUG_STATS_INCREMENT_QS_COUNT;
node_count++;
bool check = ischeck<active>(node);
if (check) {
depth++;
}
else {
eval pat = eval_evaluate(node);
if (depth == 0) return pat;
if (pat >= upper_bound) return upper_bound;
if (pat > lower_bound) lower_bound = pat;
}
evalmove moves[128];
uint8_t size = movegen_generate<active, false>(node, moves);
if (size == 0) {
eval e = check ? EVAL_I_AM_CHECKMATED : lower_bound;
return e;
}
movepick_annotate_list<active>(node, moves, size, 0);
for (uint8_t n = 0; n < size; ++n) {
evalmove m = movepick_find_best(moves, size, n);
if (!check && MOVE_VALUE(m) < EVAL_QUIESCE_LIMIT_VALUE) break;
makemove_make<active>(node, (move) m);
eval ev = -quiesce<opp>(node, depth - 1, -upper_bound, -lower_bound);
makemove_takeback<opp>(node, (move) m);
if (ev >= upper_bound) {
DEBUG_STATS_INCREMENT_BETA_CUTS;
return upper_bound;
}
if (ev > lower_bound) {
lower_bound = ev;
}
}
return lower_bound;
}
template <color active>
static uint8_t late_move_reduction(uint8_t depth,
piecetype p,
evalmove mov,
bool is_check,
bool is_checkingmove) {
if (depth < 2
|| is_check
|| is_checkingmove
|| (MOVE_VALUE(mov) >= EVAL_LMR_LIMIT_VALUE)) return 0;
assert(p != NONE);
square y = SQUARE_Y(MOVE_GET_ORIGIN(mov));
bool is_advanced_pawn = p == PAWN && (active ? y < 5 : y > 2);
if (is_advanced_pawn) return 0;
return 1;
}
template <color active>
static eval search_node(Board* node, uint8_t depth, eval original_lower_bound, eval upper_bound, bool allow_null);
template <color active>
static inline eval null_search(Board* node, uint8_t depth, eval beta) {
constexpr color opp = COLOR_OPPOSITE(active);
makemove_make_null<active>(node);
uint8_t reduced = depth - 2;
reduced -= depth / 5;
eval ev = -search_node<opp>(node, reduced - 1, -beta, -beta + 1, false);
makemove_takeback_null<opp>(node);
derived_knowledge_compute(node);
return ev;
}
template <color active>
static eval search_node(
Board* node,
uint8_t depth,
const eval original_lower_bound,
const eval upper_bound,
const bool allow_null
) {
constexpr color opp = COLOR_OPPOSITE(active);
if (depth == 0) {
return quiesce<active>(node, 9, original_lower_bound, upper_bound);
}
assert(depth > 0);
node_count++;
if (is_repetition(node)) return eval_calculate_contempt(node);
Plyinfo *info = &node->plyinfo[node->ply];
move ttmove = 0;
eval tteval = probe_tt(info->hash, &ttmove, depth, original_lower_bound, upper_bound);
if (tteval != EVAL_NONE) {
return tteval;
}
bool check = ischeck<active>(node);
evalmove moves[128];
uint8_t size = movegen_generate<active>(node, moves);
if (size == 0) {
eval e = check ? (EVAL_I_AM_CHECKMATED - depth) : eval_calculate_contempt(node);
return e;
}
else if (size == 1) {
makemove_make<active>(node, (move) moves[0]);
eval ev = -search_node<opp>(node, depth, -upper_bound, -original_lower_bound, allow_null);
makemove_takeback<opp>(node, (move) moves[0]);
return ev;
}
if (check) {
if (node->side[opp].eval_material > EVAL_MATERIAL_VALUE_EXTEND_CHECK_THRESHOLD) {
depth++;
}
}
else if (depth <= 2 && upper_bound > EVAL_I_AM_CHECKMATED) {
eval threshold = depth == 1 ? EVAL_PIECE_BISHOPS : EVAL_PIECE_ROOKS;
eval ev = eval_evaluate(node) - threshold;
if (ev > upper_bound) {
DEBUG_STATS_INCREMENT_NULL_CUTS;
return ev;
}
}
else if (allow_null
&& depth > 2
&& node->side[active].eval_material > EVAL_MATERIAL_VALUE_NULL_THRESHOLD) {
eval ev = null_search<active>(node, depth, upper_bound);
if (ev >= upper_bound) {
DEBUG_STATS_INCREMENT_NULL_CUTS;
return upper_bound;
}
}
movepick_annotate_list<active>(node, moves, size, ttmove);
evalmove m = movepick_find_best(moves, size, 0);
/*PVS: search pv move with full bounds*/
makemove_make<active>(node, (move) m);
eval ev = -search_node<opp>(node, depth - 1, -upper_bound, -original_lower_bound, false);
makemove_takeback<opp>(node, (move) m);
eval lower_bound = original_lower_bound;
tttype tt_type = TT_TYPE_LOWER_BOUND;
if (ev >= upper_bound) {
DEBUG_STATS_INCREMENT_BETA_CUTS;
transpositions_put(info->hash, depth, ev, (move) m, TT_TYPE_UPPER_BOUND);
return ev;
}
else if (ev > original_lower_bound) {
lower_bound = ev;
tt_type = TT_TYPE_EXACT;
}
move critical_move = (move) m;
for (uint8_t n = 1; n < size; ++n) {
if (async_is_stop_command_given) return 0;
m = movepick_find_best(moves, size, n);
piecetype piece = node->piecemap[MOVE_GET_ORIGIN(m)];
makemove_make<active>(node, (move) m);
uint8_t reduction = late_move_reduction<active>(depth, piece, m, check, ischeck<opp>(node));
ev = -search_node<opp>(node, depth - reduction - 1, -lower_bound - 1, -lower_bound, true);
/*PVS: if outside bounds search again with full range*/
if (ev > lower_bound && (ev < upper_bound || reduction > 0)) {
derived_knowledge_compute(node);
ev = -search_node<opp>(node, depth - 1, -upper_bound, -lower_bound, false);
}
makemove_takeback<opp>(node, (move) m);
if (ev >= upper_bound) {
DEBUG_STATS_INCREMENT_BETA_CUTS;
transpositions_put(info->hash, depth, ev, (move) m, TT_TYPE_UPPER_BOUND);
movepick_set_killer(node->ply, (move) m);
return ev;
}
else if (ev > lower_bound) {
lower_bound = ev;
critical_move = (move) m;
}
}
transpositions_put(info->hash, depth, lower_bound, critical_move, tt_type);
return lower_bound;
}
template <color active>
static inline move search_find_ponder(Board* node, move mov) {
constexpr color opp = COLOR_OPPOSITE(active);
makemove_make<active>(node, mov);
ttkey hash = node->plyinfo[node->ply].hash;
Bucket* bucket = transpositions_get(hash);
makemove_takeback<opp>(node, mov);
derived_knowledge_compute(node);
if (bucket->hash != hash) return MOVE_NONE;
return bucket->ttmove;
}
template <color active, bool print>
static inline void search_set_results(SearchResult* result, Board* root, uint8_t depth, eval ev, move mov, long starttime) {
long duration = stopwatch_wall_stop(starttime);
if (print) printline(root, depth, ev, mov, duration);
result->bestmove = mov;
result->ponder = search_find_ponder<active>(root, mov);
result->score = ev;
result->duration_ms = duration;
}
template <color active, bool print>
static eval search_root(SearchResult* result,
Board* node,
uint8_t depth,
bool printcurr) {
constexpr color opp = COLOR_OPPOSITE(active);
RESET_STATS;
long starttime = stopwatch_wall_start();
Plyinfo *info = &node->plyinfo[node->ply];
bool check = ischeck<active>(node);
evalmove moves[128];
uint8_t size = movegen_generate<active>(node, moves);
if (size == 0) {
eval e = check ? (EVAL_I_AM_CHECKMATED) : 0;
search_set_results<active, print>(result, node, depth, e, 0, 0);
return 0;
}
node->active_initial = active;
move ttmove = probe_tt_move(info->hash);
movepick_annotate_list<active>(node, moves, size, ttmove);
evalmove m = movepick_find_best(moves, size, 0);
/*PVS: search pv move with full beta range*/
makemove_make<active>(node, (move) m);
eval lower_bound = -search_node<opp>(node, depth - 1, -EVAL_INFINITE, EVAL_INFINITE, false);
makemove_takeback<opp>(node, (move) m);
move best_move = (move) m;
for (uint8_t n = 1; n < size; ++n) {
if (async_is_stop_command_given && depth != 1) return 0;
m = movepick_find_best(moves, size, n);
piecetype piece = node->piecemap[MOVE_GET_ORIGIN(m)];
if (printcurr && print) {
parsing_printcurrmove((move) m, depth, n);
}
makemove_make<active>(node, (move) m);
uint8_t reduction = late_move_reduction<active>(depth, piece, m, check, ischeck<opp>(node));
eval ev = -search_node<opp>(node, depth - reduction - 1, -lower_bound - 1, -lower_bound, true);
/*PVS: if outside bounds search again with full range*/
if (ev > lower_bound) {
derived_knowledge_compute(node);
ev = -search_node<opp>(node, depth - 1, -EVAL_INFINITE, -lower_bound, false);
}
makemove_takeback<opp>(node, (move) m);
if (ev > lower_bound) {
lower_bound = ev;
best_move = (move) m;
}
}
transpositions_put(info->hash, depth, lower_bound, best_move, TT_TYPE_EXACT);
if (!async_is_stop_command_given || depth == 1) {
search_set_results<active, print>(result, node, depth, lower_bound, best_move, starttime);
}
derived_knowledge_compute(node);
return lower_bound;
}
template <color active, bool print>
static move search_iterative_templ(const Board* board, uint8_t maxdepth) {
#ifdef DEBUGLOG
long start = stopwatch_wall_start();
#endif
bool printcurr = false;
SearchResult result = {MOVE_NONE, MOVE_NONE, EVAL_NONE, 0};
Board node = *board; // copy board
uint8_t depth = 1;
while (depth <= maxdepth) {
search_root<active, print>(&result, &node, depth, printcurr);
if (depth == 1 && result.score == -EVAL_I_AM_CHECKMATED) break; // return directly if mate in 1
if (depth == SEARCH_DEPTH_MAX) break;
if (async_is_stop_command_given) break;
if (time_management_check_stop()) break;
depth++;
printcurr = node_count > CURRMOVE_NODE_THRESHOLD;
}
time_management_send_stopped();
#ifdef DEBUGLOG
if (print) IO_PRINT("info string - searched for %.3fs\n", (double) stopwatch_wall_stop(start) / 1000);
#endif
async_is_currently_searching = false;
async_is_stop_command_given = false;
if (print) parsing_printbestmove(result.bestmove, result.ponder);
return result.bestmove;
}
move search_iterative(const Board* board, uint8_t depth, bool print) {
return board->active
? print ? search_iterative_templ<BLACK, true>(board, depth) : search_iterative_templ<BLACK, false>(board, depth)
: print ? search_iterative_templ<WHITE, true>(board, depth) : search_iterative_templ<WHITE, false>(board, depth);
}
std::future<move> search_async_depth(const Board* board, uint8_t depth, bool print) {
#ifdef DEBUGLOG
if (async_is_currently_searching) IO_PRINT("info string - warn: already in a search!\n");
#endif
if (async_is_currently_searching) {
return move_none();
}
async_is_currently_searching = true;
async_is_stop_command_given = false;
return std::async (std::launch::async, search_iterative, board, depth, print);
}
std::future<move> search_async_infinite(const Board* board, bool print) {
return search_async_depth(board, SEARCH_DEPTH_MAX, print);
}
std::future<move> search_async_time(const Board* board, long ms, bool print) {
std::thread(stopwatch_sleep, ms, search_async_stop).detach();
return search_async_depth(board, SEARCH_DEPTH_MAX, print);
}
void search_async_stop(void) {
#ifdef DEBUGLOG
IO_PRINT("info string - stopping ...\n");
#endif
async_is_stop_command_given = true;
}
void search_async_printinfo(void) {
uint64_t nodes = node_count;
IO_PRINT("info nodes %" PRIu64 "\n", nodes);
}
bool search_is_searching(void) {
return async_is_currently_searching;
}