💾 Archived View for runjimmyrunrunyoufuckerrun.com › src › games › chessengines › crafty › next.c captured on 2021-12-17 at 13:26:06.
-=-=-=-=-=-=-
#include "chess.h"
#include "data.h"
/* last modified 12/29/15 */
/*
*******************************************************************************
* *
* NextMove() is used to select the next move from the current move list. *
* *
* The "excluded move" code below simply collects any moves that were *
* searched without being generated (hash move and up to 4 killers). We *
* save them in the NEXT structure and make sure to exclude them when *
* searching after a move generation to avoid the duplicated effort. *
* *
*******************************************************************************
*/
int NextMove(TREE * RESTRICT tree, int ply, int depth, int side, int in_check) {
unsigned *movep, *bestp;
int hist, bestval, possible;
/*
************************************************************
* *
* The following "big switch" controls the finate state *
* machine that selects moves. The "phase" value in the *
* next_status[ply] structure is always set after a move *
* is selected, and it defines the next state of the FSM *
* so select the next move in a sequenced order. *
* *
************************************************************
*/
switch (tree->next_status[ply].phase) {
/*
************************************************************
* *
* First, try the transposition table move (which will be *
* the principal variation move as we first move down the *
* tree) or the best move found in this position during a *
* prior search. *
* *
************************************************************
*/
case HASH:
tree->next_status[ply].order = 0;
tree->next_status[ply].exclude = &tree->next_status[ply].done[0];
tree->next_status[ply].phase = GENERATE_CAPTURES;
if (tree->hash_move[ply]) {
tree->curmv[ply] = tree->hash_move[ply];
*(tree->next_status[ply].exclude++) = tree->curmv[ply];
if (ValidMove(tree, ply, side, tree->curmv[ply])) {
tree->phase[ply] = HASH;
return ++tree->next_status[ply].order;
}
#if defined(DEBUG)
else
Print(2048, "ERROR: bad move from hash table, ply=%d\n", ply);
#endif
}
/*
************************************************************
* *
* Generate captures and sort them based on the simple *
* MVV/LVA ordering where we try to capture the most *
* valuable victim piece possible, using the least *
* valuable attacking piece possible. Later we will test *
* to see if the capture appears to lose material and we *
* will defer searching it until later. *
* *
* Or, if in check, generate all the legal moves that *
* escape check by using GenerateCheckEvasions(). After *
* we do this, we sort them using MVV/LVA to move captures *
* to the front of the list in the correct order. *
* *
************************************************************
*/
case GENERATE_CAPTURES:
tree->next_status[ply].phase = CAPTURES;
if (!in_check)
tree->last[ply] =
GenerateCaptures(tree, ply, side, tree->last[ply - 1]);
else
tree->last[ply] =
GenerateCheckEvasions(tree, ply, side, tree->last[ply - 1]);
/*
************************************************************
* *
* Now make a pass over the moves to assign the sort value *
* for each. We simply use MVV/LVA move order here. A *
* simple optimization is to use the pre-computed array *
* MVV_LVA[victim][attacker] which returns a simple value *
* that indicates MVV/LVA order. *
* *
************************************************************
*/
tree->next_status[ply].remaining = 0;
for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
if (*movep == tree->hash_move[ply]) {
*movep = 0;
tree->next_status[ply].exclude = &tree->next_status[ply].done[0];
} else {
*movep += MVV_LVA[Captured(*movep)][Piece(*movep)];
tree->next_status[ply].remaining++;
}
NextSort(tree, ply);
tree->next_status[ply].last = tree->last[ply - 1];
if (in_check)
goto remaining_moves;
/*
************************************************************
* *
* Try the captures moves, which are in order based on *
* MVV/LVA ordering. If a larger-valued piece captures a *
* lesser-valued piece, and SEE() says it loses material, *
* this capture will be deferred until later. *
* *
* If we are in check, we jump down to the history moves *
* phase (we don't need to generate any more moves as *
* GenerateCheckEvasions has already generated all legal *
* moves. *
* *
************************************************************
*/
case CAPTURES:
while (tree->next_status[ply].remaining) {
tree->curmv[ply] = Move(*(tree->next_status[ply].last++));
if (!--tree->next_status[ply].remaining)
tree->next_status[ply].phase = KILLER1;
if (pcval[Piece(tree->curmv[ply])] <=
pcval[Captured(tree->curmv[ply])]
|| SEE(tree, side, tree->curmv[ply]) >= 0) {
*(tree->next_status[ply].last - 1) = 0;
tree->phase[ply] = CAPTURES;
return ++tree->next_status[ply].order;
}
}
/*
************************************************************
* *
* Now, try the killer moves. This phase tries the two *
* killers for the current ply without generating moves, *
* which saves time if a cutoff occurs. After those two *
* killers are searched, we try the killers from two plies *
* back since they have greater depth and might produce a *
* cutoff if the current two do not. *
* *
************************************************************
*/
case KILLER1:
possible = tree->killers[ply].move1;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = KILLER2;
tree->phase[ply] = KILLER1;
return ++tree->next_status[ply].order;
}
case KILLER2:
possible = tree->killers[ply].move2;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = (ply < 3) ? COUNTER_MOVE1 : KILLER3;
tree->phase[ply] = KILLER2;
return ++tree->next_status[ply].order;
}
case KILLER3:
possible = tree->killers[ply - 2].move1;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = KILLER4;
tree->phase[ply] = KILLER3;
return ++tree->next_status[ply].order;
}
case KILLER4:
possible = tree->killers[ply - 2].move2;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = COUNTER_MOVE1;
tree->phase[ply] = KILLER4;
return ++tree->next_status[ply].order;
}
/*
************************************************************
* *
* Now, before we give up and generate moves, try the *
* counter-move which was a move that failed high in the *
* past when the move at the previous ply was played. *
* *
************************************************************
*/
case COUNTER_MOVE1:
possible = counter_move[tree->curmv[ply - 1] & 4095].move1;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = COUNTER_MOVE2;
tree->phase[ply] = COUNTER_MOVE1;
return ++tree->next_status[ply].order;
}
case COUNTER_MOVE2:
possible = counter_move[tree->curmv[ply - 1] & 4095].move2;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = MOVE_PAIR1;
tree->phase[ply] = COUNTER_MOVE2;
return ++tree->next_status[ply].order;
}
/*
************************************************************
* *
* Finally we try paired moves, which are simply moves *
* that were good when played after the other move in the *
* pair was played two plies back. *
* *
************************************************************
*/
case MOVE_PAIR1:
possible = move_pair[tree->curmv[ply - 2] & 4095].move1;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = MOVE_PAIR2;
tree->phase[ply] = MOVE_PAIR1;
return ++tree->next_status[ply].order;
}
case MOVE_PAIR2:
possible = move_pair[tree->curmv[ply - 2] & 4095].move2;
if (!Exclude(tree, ply, possible) &&
ValidMove(tree, ply, side, possible)) {
tree->curmv[ply] = possible;
*(tree->next_status[ply].exclude++) = possible;
tree->next_status[ply].phase = GENERATE_QUIET;
tree->phase[ply] = MOVE_PAIR2;
return ++tree->next_status[ply].order;
}
/*
************************************************************
* *
* Now, generate all non-capturing moves, which get added *
* to the move list behind any captures we did not search. *
* *
************************************************************
*/
case GENERATE_QUIET:
if (!in_check)
tree->last[ply] =
GenerateNoncaptures(tree, ply, side, tree->last[ply]);
tree->next_status[ply].last = tree->last[ply - 1];
/*
************************************************************
* *
* Now, try the history moves. This phase takes the *
* complete move list, and passes over them in a classic *
* selection-sort, choosing the move with the highest *
* history score. This phase is only done one time, as it *
* also purges the hash, killer, counter and paired moves *
* from the list. *
* *
************************************************************
*/
tree->next_status[ply].remaining = 0;
tree->next_status[ply].phase = HISTORY;
bestval = -99999999;
bestp = 0;
for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
if (*movep) {
if (Exclude(tree, ply, *movep))
*movep = 0;
else if (depth >= 6) {
tree->next_status[ply].remaining++;
hist = history[HistoryIndex(side, *movep)];
if (hist > bestval) {
bestval = hist;
bestp = movep;
}
}
}
tree->next_status[ply].remaining /= 2;
if (bestp) {
tree->curmv[ply] = Move(*bestp);
*bestp = 0;
tree->phase[ply] = HISTORY;
return ++tree->next_status[ply].order;
}
goto remaining_moves;
/*
************************************************************
* *
* Now, continue with the history moves, but since one *
* pass has been made over the complete move list, there *
* are no hash/killer moves left in the list, so the tests *
* for these can be avoided. *
* *
************************************************************
*/
case HISTORY:
if (depth >= 6) {
bestval = -99999999;
bestp = 0;
for (movep = tree->last[ply - 1]; movep < tree->last[ply]; movep++)
if (*movep) {
hist = history[HistoryIndex(side, *movep)];
if (hist > bestval) {
bestval = hist;
bestp = movep;
}
}
if (bestp) {
tree->curmv[ply] = Move(*bestp);
*bestp = 0;
if (--(tree->next_status[ply].remaining) <= 0) {
tree->next_status[ply].phase = REMAINING;
tree->next_status[ply].last = tree->last[ply - 1];
}
tree->phase[ply] = HISTORY;
return ++tree->next_status[ply].order;
}
}
/*
************************************************************
* *
* Then we try the rest of the set of moves, and we do not *
* use Exclude() function to skip any moves we have *
* already searched (hash or killers) since the history *
* phase above has already done that. *
* *
************************************************************
*/
remaining_moves:
tree->next_status[ply].phase = REMAINING;
tree->next_status[ply].last = tree->last[ply - 1];
case REMAINING:
for (; tree->next_status[ply].last < tree->last[ply];
tree->next_status[ply].last++)
if (*tree->next_status[ply].last) {
tree->curmv[ply] = Move(*tree->next_status[ply].last++);
tree->phase[ply] = REMAINING;
return ++tree->next_status[ply].order;
}
return NONE;
default:
Print(4095, "oops! next_status.phase is bad! [phase=%d]\n",
tree->next_status[ply].phase);
}
return NONE;
}
/* last modified 07/03/14 */
/*
*******************************************************************************
* *
* NextRootMove() is used to select the next move from the root move list. *
* *
* There is one subtle trick here that must not be broken. Crafty does LMR *
* at the root, and the reduction amount is dependent on the order in which *
* a specific move is searched. With the recent changes dealing with this *
* issue in non-root moves, NextRootMove() now simply returns the move's *
* order within the move list. This might be a problem if the last move in *
* the list fails high, because it would be reduced on the re-search, which *
* is something we definitely don't want. The solution is found in the code *
* inside Iterate(). When a move fails high, it is moved to the top of the *
* move list so that (a) it is searched first on the re-search (more on this *
* in a moment) and (b) since its position in the move list is now #1, it *
* will get an order value of 1 which is never reduced. The only warning is *
* that Iterate() MUST re-sort the ply-1 move list after a fail high, even *
* though it seems like a very tiny computational waste. *
* *
* The other reason for doing the re-sort has to do with the parallel search *
* algorithm. When one thread fails high at the root, it stops the others. *
* they have to carefully undo the "this move has been searched" flag since *
* these incomplete searches need to be re-done after the fail-high move is *
* finished. But it is possible some of those interrupted moves appear *
* before the fail high move in the move list. Which would lead Crafty to *
* fail high, then produce a different best move's PV. By re-sorting, now *
* the fail-high move is always searched first since here we just start at *
* the top of the move list and look for the first "not yet searched" move *
* to return. It solves several problems, but if that re-sort is not done, *
* things go south quickly. The voice of experience is all I will say here. *
* *
*******************************************************************************
*/
int NextRootMove(TREE * RESTRICT tree, TREE * RESTRICT mytree, int side) {
uint64_t total_nodes;
int which, i, t;
/*
************************************************************
* *
* First, we check to see if we only have one legal move. *
* If so, and we are not pondering, we stop after a short *
* search, saving time, but making sure we have something *
* to ponder. *
* *
************************************************************
*/
if (!annotate_mode && !pondering && !booking && n_root_moves == 1 &&
iteration > 10) {
abort_search = 1;
return NONE;
}
/*
************************************************************
* *
* For the moves at the root of the tree, the list has *
* already been generated and sorted. *
* *
* We simply have to find the first move that has a zero *
* "already searched" flag and choose that one. We do set *
* the "already searched" flag for this move before we *
* return so that it won't be searched again in another *
* thread. *
* *
************************************************************
*/
for (which = 0; which < n_root_moves; which++) {
if (!(root_moves[which].status & 8)) {
if (search_move) {
if (root_moves[which].move != search_move) {
root_moves[which].status |= 8;
continue;
}
}
tree->curmv[1] = root_moves[which].move;
root_moves[which].status |= 8;
/*
************************************************************
* *
* We have found a move to search. If appropriate, we *
* display this move, along with the time and information *
* such as which move this is in the list and how many *
* are left to search before this iteration is done, and *
* a "status" character that shows the state of the *
* current search ("?" means we are pondering, waiting on *
* a move to be entered, "*" means we are searching and *
* our clock is running). We also display the NPS for *
* the search, simply for information about how fast the *
* machine is running. *
* *
************************************************************
*/
if (ReadClock() - start_time > noise_level && display_options & 16) {
sprintf(mytree->remaining_moves_text, "%d/%d", which + 1,
n_root_moves);
end_time = ReadClock();
Lock(lock_io);
if (pondering)
printf(" %2i %s%7s? ", iteration,
Display2Times(end_time - start_time),
mytree->remaining_moves_text);
else
printf(" %2i %s%7s* ", iteration,
Display2Times(end_time - start_time),
mytree->remaining_moves_text);
printf("%d. ", move_number);
if (Flip(side))
printf("... ");
strcpy(mytree->root_move_text, OutputMove(tree, 1, side,
tree->curmv[1]));
total_nodes = block[0]->nodes_searched;
for (t = 0; t < smp_max_threads; t++)
for (i = 0; i < 64; i++)
if (!(thread[t].blocks & SetMask(i)))
total_nodes += block[t * 64 + 1 + i]->nodes_searched;
nodes_per_second = total_nodes * 100 / Max(end_time - start_time, 1);
i = strlen(mytree->root_move_text);
i = (i < 8) ? i : 8;
strncat(mytree->root_move_text, " ", 8 - i);
printf("%s", mytree->root_move_text);
printf("(%snps) \n", DisplayKMB(nodes_per_second, 0));
fflush(stdout);
Unlock(lock_io);
}
/*
************************************************************
* *
* Bit of a tricky exit. If the move is not flagged as *
* "OK to search in parallel or reduce" then we return *
* "DO_NOT_REDUCE" which will prevent Search() from *
* reducing the move (LMR). Otherwise we return the more *
* common "REMAINING" value which allows LMR to be used on *
* those root moves. *
* *
************************************************************
*/
if (root_moves[which].status & 4)
tree->phase[1] = DO_NOT_REDUCE;
else
tree->phase[1] = REMAINING;
return which + 1;
}
}
return NONE;
}
/* last modified 11/13/14 */
/*
*******************************************************************************
* *
* NextRootMoveParallel() is used to determine if the next root move can be *
* searched in parallel. If it appears to Iterate() that one of the moves *
* following the first move might become the best move, the 'no parallel' *
* flag is set to speed up finding the new best move. This flag is set if *
* this root move has an "age" value > 0 which indicates this move was the *
* "best move" within the previous 3 search iterations. We want to search *
* such moves as quickly as possible, prior to starting a parallel search at *
* the root, in case this move once again becomes the best move and provides *
* a better alpha bound. *
* *
*******************************************************************************
*/
int NextRootMoveParallel(void) {
int which;
/*
************************************************************
* *
* Here we simply check the root_move status flag that is *
* set in Iterate() after each iteration is completed. A *
* value of "1" indicates this move has to be searched by *
* all processors together, splitting at the root must *
* wait until we have searched all moves that have been *
* "best" during the previous three plies. *
* *
* The root move list has a flag, bit 3, used to indicate *
* that this move has been best recently. If this bit is *
* set, we are forced to use all processors to search this *
* move so that it is completed quickly rather than being *
* searched by just one processor, and taking much longer *
* to get a score back. We do this to give the search the *
* best opportunity to fail high on this move before we *
* run out of time. *
* *
************************************************************
*/
for (which = 0; which < n_root_moves; which++)
if (!(root_moves[which].status & 8))
break;
if (which < n_root_moves && !(root_moves[which].status & 4))
return 1;
return 0;
}
/* last modified 09/11/15 */
/*
*******************************************************************************
* *
* Exclude() searches the list of moves searched prior to generating a move *
* list to exclude those that were searched via a hash table best move or *
* through the killer moves for the current ply and two plies back. *
* *
* The variable next_status[].excluded is the total number of non-generated *
* moves we searched. next_status[].remaining is initially set to excluded, *
* but each time an excluded move is found, the counter is decremented. *
* Once all excluded moves have been found, we avoid running through the *
* list of excluded moves on each call and simply return. *
* *
*******************************************************************************
*/
int Exclude(TREE * RESTRICT tree, int ply, int move) {
unsigned *i;
if (tree->next_status[ply].exclude > &tree->next_status[ply].done[0])
for (i = &tree->next_status[ply].done[0];
i < tree->next_status[ply].exclude; i++)
if (move == *i)
return 1;
return 0;
}
/* last modified 05/20/15 */
/*
*******************************************************************************
* *
* NextSort() is used to sort the move list. This is a list of 32 bit *
* values where the rightmost 21 bits is the compressed move, and the left- *
* most 11 bits are the sort key (MVV/LVA values). *
* *
*******************************************************************************
*/
void NextSort(TREE * RESTRICT tree, int ply) {
unsigned temp, *movep, *tmovep;
/*
************************************************************
* *
* This is a simple insertion sort algorithm. *
* *
************************************************************
*/
if (tree->last[ply] > tree->last[ply - 1] + 1) {
for (movep = tree->last[ply - 1] + 1; movep < tree->last[ply]; movep++) {
temp = *movep;
tmovep = movep - 1;
while (tmovep >= tree->last[ply - 1] && SortV(*tmovep) < SortV(temp)) {
*(tmovep + 1) = *tmovep;
tmovep--;
}
*(tmovep + 1) = temp;
}
}
}