search.h

Go to the documentation of this file.

#ifndef EDAX_SEARCH_H
#define EDAX_SEARCH_H

#include "board.h"
#include "const.h"
#include "empty.h"
#include "eval.h"
#include "hash.h"
#include "move.h"
#include "util.h"

#include <stdio.h>

typedef struct Selectivity {
        double t; 
        int level; 
        int percent; 
} Selectivity;

struct Task;
struct TaskQueue;

typedef struct Bound {
        int lower;
        int upper;
} Bound;

typedef struct Result {
        int depth;                   
        int selectivity;             
        int move;                    
        int score;                   
        Bound bound[BOARD_SIZE + 2]; 
        Line pv[1];                  
        long long time;              
        unsigned long long n_nodes;  
        bool book_move;              
        int n_moves;                 
        int n_moves_left;            
        SpinLock spin;
} Result;

typedef struct Hint {
        int depth;                   
        int selectivity;             
        int move;                    
        int score;                   
        int upper;                   
        int lower;                   
        Line pv[1];                  
        long long time;              
        unsigned long long n_nodes;  
        bool book_move;              
} Hint;

typedef struct HintList {
        Hint hint[MAX_MOVE + 2];   
        int n_hints;
} HintList;


extern struct Level {
        int depth;         
        int selectivity;   
} LEVEL[61][61];


typedef struct Search {
        Board board[1];                               
        SquareList empties[BOARD_SIZE + 2];           
        SquareList *x_to_empties[BOARD_SIZE + 2];     
        int n_empties;                                
        int player;                                   
        int id;                                       
        HashTable hash_table[1];                      
        HashTable pv_table[1];                        
        HashTable shallow_table[1];                   
        Eval eval[1];                                 
        Random random[1];                             
        struct TaskStack *tasks;                      
        struct Task *task;                            
        SpinLock spin;                                
        struct Search *parent;                        
        struct Search *child[MAX_THREADS];            
        struct Search *master;                        
        volatile int n_child;                         
        int depth;                                    
        int selectivity;                              
        int probcut_level;                            
        unsigned int parity;                          
        int depth_pv_extension;                       
        volatile Stop stop;                           
        bool allow_node_splitting;                    
        struct {
                long long  extra;                         
                volatile long long spent;                 
                bool extended;                            
                bool can_update;                          
                long long  mini;                          
                long long  maxi;                          
        } time;                                       
        MoveList movelist[1];                         
        int height;                                   
        NodeType node_type[GAME_SIZE];                
        Bound stability_bound;                        
        struct {
                int depth;                                
                int selectivity;                          
                long long time;                           
                bool time_per_move;                       
                int verbosity;                            
                bool keep_date;                           
                const char *header;                       
                const char *separator;                    
                bool guess_pv;                            
                int multipv_depth;                        
                int hash_size;                            
        } options;                                    
        Result *result;                               
        void (*observer)(Result*);                    
        volatile unsigned long long n_nodes;          
        volatile unsigned long long child_nodes;      
} Search;

struct Node;

extern const int QUADRANT_ID[];
extern const Selectivity selectivity_table[];
extern const int NO_SELECTIVITY;
extern const int NWS_STABILITY_THRESHOLD[];
extern const int PVS_STABILITY_THRESHOLD[];
extern const int SQUARE_TYPE[];

/* function definition */
void search_global_init(void);
void search_init(Search*);
void search_free(Search*);
void search_cleanup(Search*);
void search_setup(Search*);
void search_clone(Search*, Search*);
void search_set_board(Search*, const Board*, const int);
void search_set_level(Search*, const int, const int);
void search_set_ponder_level(Search*, const int, const int);
void search_resize_hashtable(Search*);

void search_set_game_time(Search*, const long long);
void search_set_move_time(Search*, const long long);
void search_time_init(Search*);
void search_time_reset(Search*, const Board*);
void search_adjust_time(Search*, const bool);
bool search_continue(Search *);
void search_check_timeout(Search *search);

void search_set_task_number(Search*, const int);

void search_swap_parity(Search*, const int);
void search_get_movelist(const Search*, MoveList*);
void search_update_endgame(Search*, const Move*);
void search_restore_endgame(Search*, const Move*);
void search_pass_endgame(Search*);
void search_update_midgame(Search*, const Move*);
void search_restore_midgame(Search*, const Move*);
void search_update_pass_midgame(Search*);
void search_restore_pass_midgame(Search*);
long long search_clock(Search*);
long long search_time(Search*);
unsigned long long search_count_nodes(Search*);
void search_print_pv(Search*, const int, const char*, FILE*);
void search_print(Search*, const int, const int, const char, FILE*);
int get_pv_extension(const int, const int);

void result_print(Result*, FILE*);

bool search_SC_PVS(Search*, volatile int*, volatile int*, int*);
bool search_SC_NWS(Search*, const int, int*);
bool search_TC_PVS(HashData*, const int, const int, volatile int*, volatile int*, int*);
bool search_TC_NWS(HashData*, const int, const int, const int, int*);
bool search_ETC_PVS(Search*, MoveList*, unsigned long long, const int, const int, volatile int*, volatile int*, int*);
bool search_ETC_NWS(Search*, MoveList*, unsigned long long, const int, const int, const int, int*);

NodeType next_node_type(const NodeType parent, const bool first_move);

int search_solve(const Search*);
int search_solve_0(const Search*);
extern int board_score_1(const Board*, const int, const int);
int NWS_endgame(Search*, const int);

int search_eval_0(Search*);
int search_eval_1(Search*, const int, int);
int search_eval_2(Search*, int, const int);
int NWS_midgame(Search*, const int, int, struct Node*);
int PVS_midgame(Search*, const int, const int, int, struct Node*);
int NWS_shallow(Search*, const int, int, HashTable*);
int PVS_shallow(Search*, int, int, int);

bool is_pv_ok(Search*, int, int);
void record_best_move(Search*, const Board*, const Move*, const int, const int, const int);
int PVS_root(Search*, const int, const int, const int);
int aspiration_search(Search*, int, int, const int, int);
void iterative_deepening(Search*, int, int);
void* search_run(void*);
int search_guess(Search*, const Board*);
void search_stop_all(Search*, const Stop);
void search_set_state(Search*, const Stop);

void search_observer(Result*);
void search_set_observer(Search*, void (*Observer)(Result*));

void search_share(const Search*, Search*);
int search_count_tasks(const Search *);

bool is_depth_solving(const int, const int);
int solvable_depth(const long long, int);
void pv_debug(Search*, const Move*, FILE*);
int search_get_pv_cost(Search*);
void show_current_move(FILE *f, Search*, const Move*, const int, const int, const bool);
int search_bound(const Search*, int);

#endif