<commit_before>#include "error.h"
#include "search.h"
#include "board.h"
#include "step.h"
#include "piece.h"
#include "square.h"
#include "eval.h"
#include <fstream>
#include <time.h>
#include <string.h>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

//////////////////////////////////////////////////////////////////////////////
//Constructor. Basically set last search mode to none and initialize the 
//hash tables to the number of bits
//////////////////////////////////////////////////////////////////////////////
Search :: Search(int scoreHashBits)
{
    //Initialize hash tables
    transTable.setHashKeySize(scoreHashBits);
    gameHistTable.setHashKeySize(10);
    searchHist.init(Int64FromIndex(SEARCH_SEARCH_HIST_HASH_BITS));

    //create hash masks
    searchHistHashMask = 0;
    for (int i = 0; i < SEARCH_SEARCH_HIST_HASH_BITS; i++)
        searchHistHashMask |= Int64FromIndex(i);
}

//////////////////////////////////////////////////////////////////////////////
//Deconstructor, does nothing
//////////////////////////////////////////////////////////////////////////////
Search :: ~Search()
{

}

//////////////////////////////////////////////////////////////////////////////
//Resets all relevant search stats and does an iterative deepening search
//and returns the best move
//////////////////////////////////////////////////////////////////////////////
StepCombo Search :: iterativeDeepen(Board& board, int maxDepth, ostream& log)
{
    //reset search statistics
    numTerminalNodes = 0;
    numTotalNodes = 0;
    score = -30000;
    pv.resize(0);
    hashHits = 0;
    
    eval.reset();
    killerTable.reset();

    log << setw(6) << "Depth" << setw(6) << "Score" << setw(15) 
        << "Nodes" << setw(10) << "Time(ms)" << setw(10)
        << "Nodes/Sec" << " PV\n";
    //start timing now
    time_t reftime = clock();

    for (int currDepth = 1; currDepth <= maxDepth; currDepth++)
    {
        searchRoot(board, currDepth);
        
        Int64 currMillis = (clock() - reftime) * 1000 / CLOCKS_PER_SEC + 1; 
        log << setw(6) << currDepth << setw(6) << score << setw(15) 
            << numTotalNodes << setw(10) << currMillis << setw(10)
            << (unsigned int)((float)numTotalNodes / currMillis * 1000);
        for (int i = 0; i < pv.size(); ++i)
            log << " " << pv[i];
        log << endl;

        log.flush();

        //If the score is so great, then it's probably a win, so don't
        //search any further
        if (score >= 25000)
            break;
    }

    //extract current turn from pv
    int firstOppTurn = 0;
    StepCombo PVToPlay;
    for (int i = 0; i < pv.size(); ++i)
    {
        //stop when the step cost becomes 4, as that has to be the end
        //of the player's turn. Also stop whenever something that is not
        //a move is read.
        if (PVToPlay.stepCost == 4 || pv[i] == string("<HT>"))
            break;

        StepCombo steps;
        steps.fromString(pv[i]);
    
        PVToPlay.addCombo(steps);
    }

    return PVToPlay;
}    

//////////////////////////////////////////////////////////////////////////////
//Starts a search on the given board as the root node to the given depth and 
//returns the best combo for the player to move.
//////////////////////////////////////////////////////////////////////////////
void Search :: searchRoot(Board& board, int depth)
{
    //set back history scores to avoid overflows if possible
    for (int f1 = 0; f1 < NUM_SQUARES + 1; f1++)
    {
        for (int t1 = 0; t1 < NUM_SQUARES + 1; t1++)
        {
            for (int f2 = 0;  f2 < NUM_SQUARES + 1; f2++)
            {
                for (int c = 0; c < MAX_COLORS; c++)
                {
                    eval.historyScore[f1][t1][f2][c] >>=7;
                }
            }
        }
    }

    //Add this board to the search history
    addSearchHistory(board);

    //combo that was the best one to try last time
    StepCombo lastBest;
    bool lastBestFound = false;

    //check if there is a hash position of at least this depth, but only
    //to get the best move from the hash.  
    if (transTable.hasValidEntry(board.hash))
    {
        hashHits++;

        TranspositionEntry entry = transTable.getEntry(board.hash); 
        if (entry.getNumSteps() == 1)
        {
            if (board.gen1Step(lastBest, entry.getFrom1(),
                              entry.getTo1()))
                lastBestFound = true;
        }
        else
        {
            if (board.gen2Step(lastBest, entry.getFrom1(),
                              entry.getTo1(), entry.getFrom2()))
                lastBestFound = true;
        }
    }
    
    //try out the best successor first
    StepCombo bestCombo;
    if (lastBestFound)
    {
        bestCombo = lastBest;
        score = doMoveAndSearch(board, depth, 0, -30000, 
                                          30000, pv, 
                                          lastBest);  
    }

    //Check to make sure the combo arrays has entries up to this ply
    if ((int)combos.size() < 1)
    {
        combos.resize(1);
        combos[0].resize(SEARCH_MAX_COMBOS_PER_PLY);
    }

    unsigned int numCombos = board.genMoves(combos[0]);
        
    if (numCombos == 0 ) //no moves available? 
    {
        return;
    }

    if (!lastBestFound)
        bestCombo = combos[0][0];

    //give the combos some score for move ordering
    eval.scoreCombos(combos[0], numCombos, board.sideToMove);

    //go through all remaining successors
    for (int i = 0; i < numCombos; ++i)
    {
        //get the next best combo to look at
        StepCombo next = getNextBestComboAndRemove(combos[0], numCombos);

        //check that this wasn't the last best successor, which was already
        //searched
        if (next == lastBest)
            continue;

        short nodeScore = doMoveAndSearch(board, depth, 0,  score, 
                                          30000, pv, 
                                          next); 

        if (nodeScore > score)
        {
            bestCombo = next;
            score = nodeScore;
        }
    }

    //Remove this board to the search history
    removeSearchHistory(board);

    //add a entry into the hash table for this node
    transTable.setEntry(board.hash, TRANSPOSITION_SCORETYPE_EXACT, score, 
                            depth, bestCombo.getRawMove());
}<commit_msg>Made sure the behavior at search root and the ply are correct when given a board without all 4 steps left<commit_after>#include "error.h"
#include "search.h"
#include "board.h"
#include "step.h"
#include "piece.h"
#include "square.h"
#include "eval.h"
#include <fstream>
#include <time.h>
#include <string.h>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

//////////////////////////////////////////////////////////////////////////////
//Constructor. Basically set last search mode to none and initialize the 
//hash tables to the number of bits
//////////////////////////////////////////////////////////////////////////////
Search :: Search(int scoreHashBits)
{
    //Initialize hash tables
    transTable.setHashKeySize(scoreHashBits);
    gameHistTable.setHashKeySize(10);
    searchHist.init(Int64FromIndex(SEARCH_SEARCH_HIST_HASH_BITS));

    //create hash masks
    searchHistHashMask = 0;
    for (int i = 0; i < SEARCH_SEARCH_HIST_HASH_BITS; i++)
        searchHistHashMask |= Int64FromIndex(i);
}

//////////////////////////////////////////////////////////////////////////////
//Deconstructor, does nothing
//////////////////////////////////////////////////////////////////////////////
Search :: ~Search()
{

}

//////////////////////////////////////////////////////////////////////////////
//Resets all relevant search stats and does an iterative deepening search
//and returns the best move
//////////////////////////////////////////////////////////////////////////////
StepCombo Search :: iterativeDeepen(Board& board, int maxDepth, ostream& log)
{
    //reset search statistics
    numTerminalNodes = 0;
    numTotalNodes = 0;
    score = -30000;
    pv.resize(0);
    hashHits = 0;
    
    eval.reset();
    killerTable.reset();

    log << setw(6) << "Depth" << setw(6) << "Score" << setw(15) 
        << "Nodes" << setw(10) << "Time(ms)" << setw(10)
        << "Nodes/Sec" << " PV\n";
    //start timing now
    time_t reftime = clock();

    for (int currDepth = 1; currDepth <= maxDepth; currDepth++)
    {
        searchRoot(board, currDepth);
        
        Int64 currMillis = (clock() - reftime) * 1000 / CLOCKS_PER_SEC + 1; 
        log << setw(6) << currDepth << setw(6) << score << setw(15) 
            << numTotalNodes << setw(10) << currMillis << setw(10)
            << (unsigned int)((float)numTotalNodes / currMillis * 1000);
        for (int i = 0; i < pv.size(); ++i)
            log << " " << pv[i];
        log << endl;

        log.flush();

        //If the score is so great, then it's probably a win, so don't
        //search any further
        if (score >= 25000)
            break;
    }

    //extract current turn from pv
    int firstOppTurn = 0;
    StepCombo PVToPlay;
    for (int i = 0; i < pv.size(); ++i)
    {
        //stop when the step cost becomes 4, as that has to be the end
        //of the player's turn. Also stop whenever something that is not
        //a move is read.
        if (PVToPlay.stepCost == 4 || pv[i] == string("<HT>"))
            break;

        StepCombo steps;
        steps.fromString(pv[i]);
    
        PVToPlay.addCombo(steps);
    }

    return PVToPlay;
}    

//////////////////////////////////////////////////////////////////////////////
//Starts a search on the given board as the root node to the given depth and 
//returns the best combo for the player to move.
//////////////////////////////////////////////////////////////////////////////
void Search :: searchRoot(Board& board, int depth)
{
    //set back history scores to avoid overflows if possible
    for (int f1 = 0; f1 < NUM_SQUARES + 1; f1++)
    {
        for (int t1 = 0; t1 < NUM_SQUARES + 1; t1++)
        {
            for (int f2 = 0;  f2 < NUM_SQUARES + 1; f2++)
            {
                for (int c = 0; c < MAX_COLORS; c++)
                {
                    eval.historyScore[f1][t1][f2][c] >>=7;
                }
            }
        }
    }

    //make sure to just pass if there are no steps left
    if (board.stepsLeft == 0)
    {
        board.changeTurn();
        searchRoot(board, depth);
        board.unchangeTurn(0);
        score = -score;
        return;
    }

    //Add this board to the search history
    addSearchHistory(board);

    //combo that was the best one to try last time
    StepCombo lastBest;
    bool lastBestFound = false;

    //check if there is a hash position of at least this depth, but only
    //to get the best move from the hash.  
    if (transTable.hasValidEntry(board.hash))
    {
        hashHits++;

        TranspositionEntry entry = transTable.getEntry(board.hash); 
        if (entry.getNumSteps() == 1)
        {
            if (board.gen1Step(lastBest, entry.getFrom1(),
                              entry.getTo1()))
                lastBestFound = true;
        }
        else
        {
            if (board.gen2Step(lastBest, entry.getFrom1(),
                              entry.getTo1(), entry.getFrom2()))
                lastBestFound = true;
        }
    }
    
    //try out the best successor first
    StepCombo bestCombo;
    if (lastBestFound)
    {
        bestCombo = lastBest;
        score = doMoveAndSearch(board, depth, 4 - board.stepsLeft, -30000, 
                                          30000, pv, 
                                          lastBest);  
    }

    //Check to make sure the combo arrays has entries up to this ply
    if ((int)combos.size() < 1)
    {
        combos.resize(1);
        combos[0].resize(SEARCH_MAX_COMBOS_PER_PLY);
    }

    unsigned int numCombos = board.genMoves(combos[0]);
        
    if (numCombos == 0) //no moves available? 
    {
        return;
    }

    if (!lastBestFound)
        bestCombo = combos[0][0];

    //give the combos some score for move ordering
    eval.scoreCombos(combos[0], numCombos, board.sideToMove);

    //go through all remaining successors
    for (int i = 0; i < numCombos; ++i)
    {
        //get the next best combo to look at
        StepCombo next = getNextBestComboAndRemove(combos[0], numCombos);

        //check that this wasn't the last best successor, which was already
        //searched
        if (next == lastBest)
            continue;

        short nodeScore = doMoveAndSearch(board, depth, 
                                          4 - board.stepsLeft,  
                                          score, 
                                          30000, pv, 
                                          next); 

        if (nodeScore > score)
        {
            bestCombo = next;
            score = nodeScore;
        }
    }

    //Remove this board to the search history
    removeSearchHistory(board);

    //add a entry into the hash table for this node
    transTable.setEntry(board.hash, TRANSPOSITION_SCORETYPE_EXACT, score, 
                            depth, bestCombo.getRawMove());
}
{'fraction_non_alphanumeric': 0.19490063742032246, 'fraction_numerical': 0.016722909636295462, 'mean_word_length': 1.4398097328942554, 'pattern_counts': {'":': 0, '<': 135, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3774971', 'n_tokens_mistral': 3913, 'n_tokens_neox': 3707, 'n_words': 1117}