#include "search.h"
#include "bit.h"
#include "options.h"
#include "stats.h"
#include "util.h"
#include "ybwc.h"
#include "settings.h"
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>

Functions
void	search_global_init (void)

void	search_resize_hashtable (Search *search)

void	search_init (Search *search)
	Init the main search. More...

void	search_free (Search *search)
	Free the search allocated ressource. More...

void	search_setup (Search *search)
	Set up various structure once the board has been set. More...

void	search_clone (Search search, Search master)
	Clone a search for parallel search. More...

void	search_cleanup (Search *search)
	Clean-up some search data. More...

void	search_set_board (Search search, const Board board, const int player)
	Set the board to analyze. More...

void	search_set_level (Search *search, const int level, const int n_empties)
	Set the search level. More...

void	search_set_ponder_level (Search *search, const int level, const int n_empties)
	Set the search level while pondering. More...

int	solvable_depth (const long long limit, int n_tasks)
	Compute the deepest level that can be solved given a limited time... More...

void	search_set_game_time (Search *search, const long long t)
	set time to search. More...

void	search_set_move_time (Search *search, const long long t)
	set time to search. More...

void	search_time_init (Search *search)
	Initialize the alloted time. More...

void	search_time_reset (Search search, const Board initial_board)
	Reset the alloted time. More...

void	search_adjust_time (Search *search, const bool once)
	Give more time. More...

bool	search_continue (Search *search)
	Check if it can iterate more... More...

void	search_check_timeout (Search *search)
	Check if it can iterate more... More...

void	search_set_task_number (Search *search, const int n)
	Change the number of task. More...

void	search_swap_parity (Search *search, const int x)
	Change parity. More...

void	search_get_movelist (const Search search, MoveList movelist)
	Get a list of legal moves. More...

void	search_update_endgame (Search search, const Move move)
	Update the search state after a move. More...

void	search_restore_endgame (Search search, const Move move)
	Restore the search state as before a move. More...

void	search_pass_endgame (Search *search)
	Update the search state after a passing move. More...

void	search_update_midgame (Search search, const Move move)
	Update the search state after a move. More...

void	search_restore_midgame (Search search, const Move move)
	Restore the search state as before a move. More...

void	search_update_pass_midgame (Search *search)
	Update the search state after a passing move. More...

void	search_restore_pass_midgame (Search *search)
	Update the search state after a passing move. More...

int	get_pv_extension (const int depth, const int n_empties)
	Compute the pv_extension. More...

bool	is_depth_solving (const int depth, const int n_empties)
	Check if final score use pv_extension or is solved. More...

long long	search_clock (Search *search)
	Return the time spent by the search. More...

long long	search_time (Search *search)
	Return the time spent by the search. More...

unsigned long long	search_count_nodes (Search *search)
	Return the number of nodes searched. More...

void	search_observer (Result *result)
	default observer. More...

void	search_set_observer (Search search, void(observer)(Result *))
	set observer. More...

void	result_print (Result result, FILE f)
	Print the current search result. More...

bool	search_SC_PVS (Search search, volatile int alpha, volatile int beta, int score)
	Stability Cutoff (SC). More...

bool	search_SC_NWS (Search search, const int alpha, int score)
	Stability Cutoff (TC). More...

bool	search_TC_PVS (HashData data, const int depth, const int selectivity, volatile int alpha, volatile int beta, int score)
	Transposition Cutoff (TC). More...

bool	search_TC_NWS (HashData data, const int depth, const int selectivity, const int alpha, int score)
	Transposition Cutoff (TC). More...

bool	search_ETC_NWS (Search search, MoveList movelist, unsigned long long hash_code, const int depth, const int selectivity, const int alpha, int *score)
	Enhanced Transposition Cutoff (ETC). More...

void	search_share (const Search src, Search dest)
	Share search information. More...

int	search_count_tasks (const Search *search)
	Count the number of tasks used in parallel search. More...

void	search_stop_all (Search *search, const Stop stop)
	Stop the search. More...

void	search_set_state (Search *search, const Stop stop)
	Set the search running/waiting state. More...

int	search_guess (Search search, const Board board)
	Guess the bestmove of a given board. More...

Variables
Log	search_log [1]

const int	QUADRANT_ID []

const int	NO_SELECTIVITY = 5

const Selectivity	selectivity_table []

const int	NWS_STABILITY_THRESHOLD []

const int	PVS_STABILITY_THRESHOLD []

const int	SQUARE_TYPE []

struct Level	LEVEL [61][61]

Detailed Description

Search the best move.

Functions that evaluate a board with different methods depending on the position in the tree search and/or that finds the best move of a given board.

At the end of the game, some trivial functions are used to compute the score. For instance, the last move is not made and only the number of flipped discs is evaluated. Special and optimized functions are used when one, two and three empty squares remain on the board, in order to speed up the search.

The search of the best move is driven with the Principal Variation Search algorithm (PVS) [1], an enhanced variation of the alphabeta algorithm. The alphabeta algorithm is known to visit less nodes when the alphabeta window is reduced. PVS takes this property into account. From a set of sibling nodes, the first node is searched using a plain alpha beta window. Then the sibling nodes are only searched with minimal windows (where beta = alpha + 1), just to refute the best (first) score. In rare cases the first move is actually refuted, then the current move is re-searched a second time in order to determinate its score more accurately. On highly ordered tree, very few re-searches will be done. Moreover, thanks to the hash table, a second search is usually faster than a first search. So the seldom and fast re-searches will not impact too much the benefit of using minimal windows. Aspiration windows have been added as another improvement, so that even the first search is done with a reduced window. During the 1990s, several re-re-search algorithms based on null-window alphabeta have been proposed : SSS*ab [2], Dual*ab[2], NegaC*[3], MDT[2], negascout[4]. Some (unpublished) experimental tests I made with them did not show any significant improvement compare to the PVS algorithm with aspiration-windows used here.

To be efficient PVS need highly ordered tree. The following ordering has been made :

fixed square ordering: square usually leading to a good move are visited first, ie from corner squares to X and C squares.
parity: squares on odd set of empty squares should be played first, especially near the end of the game.
most stable ordering: a crude evaluation of stability at the corner (corner, X and C squares) to order the moves.
fast first ordering: the moves leading to the most reduced mobility for the opponent are played first.
best move previously found: If the position has been previously searched, the best move that was found is replayed as the first move.

Campbell MS & Marsland TA (1983) A Comparison of Minimax Trees Search Algorithms. Artificial Intelligence, 20, pp. 347-367.

Plaat A. et al. (1996) Best-First Fixed Depth Minimax Algorithms. Artificial Intelligence, 84, pp. 255-293.
Weill JC. (1992) Experiments With The NegaC* Search. An alternative for Othello Endgame Search. ICCA journal, 15(1), pp. 3-7.
Reinsfeld A. (1983) An Improvement Of the Scout Tree-Search Algorithm. ICCA journal, 6(4), pp. 4-14.

Date: 1998 - 2017

Author: Richard Delorme

Version: 4.4

Function Documentation

◆ get_pv_extension()

int get_pv_extension	(	const int	depth,
		const int	n_empties
	)

Compute the pv_extension.

Parameters

depth	Depth.
n_empties	Game stage (number of empty squares).

◆ is_depth_solving()

bool is_depth_solving	(	const int	depth,
		const int	n_empties
	)

Check if final score use pv_extension or is solved.

Parameters

depth	search depth.
n_empties	position depth.

Returns: true if the score should be a final score.

◆ result_print()

void result_print	(	Result *	result,
		FILE *	f
	)

Print the current search result.

Parameters

result	Last search result.
f	output stream.

◆ search_adjust_time()

void search_adjust_time	(	Search *	search,
		const bool	once
	)

Give more time.

Parameters

search	Search.
once	A flag to prevent further time extension.

◆ search_check_timeout()

void search_check_timeout ( Search * search )

Check if it can iterate more...

Parameters

search Search.

◆ search_cleanup()

void search_cleanup ( Search * search )

Clean-up some search data.

Parameters

search search.

◆ search_clock()

long long search_clock ( Search * search )

Return the time spent by the search.

Parameters

search Search.

Returns: time (in milliseconds).

◆ search_clone()

void search_clone	(	Search *	search,
		Search *	master
	)

Clone a search for parallel search.

Parameters

search	search.
master	search to be cloned.

◆ search_continue()

bool search_continue ( Search * search )

Check if it can iterate more...

Parameters

search Search.

◆ search_count_nodes()

unsigned long long search_count_nodes ( Search * search )

Return the number of nodes searched.

Parameters

search Search.

Returns: node count.

◆ search_count_tasks()

int search_count_tasks ( const Search * search )

Count the number of tasks used in parallel search.

Parameters

search Search.

Returns: number of tasks.

◆ search_ETC_NWS()

bool search_ETC_NWS	(	Search *	search,
		MoveList *	movelist,
		unsigned long long	hash_code,
		const int	depth,
		const int	selectivity,
		const int	alpha,
		int *	score
	)

Enhanced Transposition Cutoff (ETC).

Before looping over each moves to search at next ply, ETC looks if a cutoff is available from the hashtable. This version also looks for a cutoff based on stability.

Parameters

search	Current position.
movelist	List of moves for the current position.
hash_code	Hashing code.
depth	Search depth.
selectivity	Search selectivity.
alpha	Alpha bound.
score	Score to return in case a cutoff is found.

Returns: 'true' if a cutoff is found, 'false' otherwise.

◆ search_free()

void search_free ( Search * search )

Free the search allocated ressource.

Free a previously initialized search structure.

Parameters

search search.

◆ search_get_movelist()

void search_get_movelist	(	const Search *	search,
		MoveList *	movelist
	)

Get a list of legal moves.

Compute the complete list of legal moves and store it into a simple linked list, to fasten ulterior move sorting. Note: at this point the list is sorted from A1 to H8 (i.e. unsorted).

Parameters

search	Search.
movelist	List of moves.

◆ search_global_init()

void search_global_init ( void )

Global initialisations.

Todo:: Add more global initialization from here?

◆ search_guess()

int search_guess	(	Search *	search,
		const Board *	board
	)

Guess the bestmove of a given board.

Look for a move from the hash tables.

Parameters

search	Search.
board	Board.

Returns: the best move.

◆ search_init()

void search_init ( Search * search )

Init the main search.

Initialize a new search structure.

Parameters

search search.

◆ search_observer()

void search_observer ( Result * result )

default observer.

Parameters

result search results to print.

◆ search_pass_endgame()

void search_pass_endgame ( Search * search )

Update the search state after a passing move.

Parameters

search search.

◆ search_resize_hashtable()

void search_resize_hashtable ( Search * search )

◆ search_restore_endgame()

void search_restore_endgame	(	Search *	search,
		const Move *	move
	)

Restore the search state as before a move.

Parameters

search	search.
move	played move.

◆ search_restore_midgame()

void search_restore_midgame	(	Search *	search,
		const Move *	move
	)

Restore the search state as before a move.

Parameters

search	search.
move	played move.

◆ search_restore_pass_midgame()

void search_restore_pass_midgame ( Search * search )

Update the search state after a passing move.

Parameters

search search.

◆ search_SC_NWS()

bool search_SC_NWS	(	Search *	search,
		const int	alpha,
		int *	score
	)

Stability Cutoff (TC).

Parameters

search	Current position.
alpha	Alpha bound.
score	Score to return in case of a cutoff is found.

Returns: 'true' if a cutoff is found, false otherwise.

◆ search_SC_PVS()

bool search_SC_PVS	(	Search *	search,
		volatile int *	alpha,
		volatile int *	beta,
		int *	score
	)

Stability Cutoff (SC).

Parameters

search	Current position.
alpha	Alpha bound.
beta	Beta bound, to adjust if necessary.
score	Score to return in case of a cutoff is found.

Returns: 'true' if a cutoff is found, false otherwise.

◆ search_set_board()

void search_set_board	(	Search *	search,
		const Board *	board,
		const int	player
	)

Set the board to analyze.

Parameters

search	search.
board	board.
player	player's turn.

◆ search_set_game_time()

void search_set_game_time	(	Search *	search,
		const long long	t
	)

set time to search.

This function should be called before each new search, with the accurate remaining time to do the whole search for the game.

Parameters

search	Search.
t	time in ms.

◆ search_set_level()

void search_set_level	(	Search *	search,
		const int	level,
		const int	n_empties
	)

Set the search level.

Compute the couple (depth, selectivity) as a function of (level, n_empties)

Parameters

search	search.
level	search level.
n_empties	Search stage.

◆ search_set_move_time()

void search_set_move_time	(	Search *	search,
		const long long	t
	)

set time to search.

This function should be called before each new search, with the accurate remaining time to do the whole search for this move.

Parameters

search	Search.
t	time in ms.

◆ search_set_observer()

void search_set_observer	(	Search *	search,
		void()(Result )	observer
	)

set observer.

Parameters

search	Searched position.
observer	call back function to print the current search.

◆ search_set_ponder_level()

void search_set_ponder_level	(	Search *	search,
		const int	level,
		const int	n_empties
	)

Set the search level while pondering.

Compute the couple (depth, selectivity) as a function of (level, n_empties)

Parameters

search	Search.
level	Search level.
n_empties	Search stage.

◆ search_set_state()

void search_set_state	(	Search *	search,
		const Stop	stop
	)

Set the search running/waiting state.

Parameters

search	Search.
stop	State.

◆ search_set_task_number()

void search_set_task_number	(	Search *	search,
		const int	n
	)

Change the number of task.

Parameters

search	Search.
n	New task number.

◆ search_setup()

void search_setup ( Search * search )

Set up various structure once the board has been set.

Initialize the list of empty squares, the parity and the evaluation function.

Parameters

search search.

◆ search_share()

void search_share	(	const Search *	src,
		Search *	dest
	)

Share search information.

Parameters

src	source search.
dest	destination search.

◆ search_stop_all()

void search_stop_all	(	Search *	search,
		const Stop	stop
	)

Stop the search.

Parameters

search	Search.
stop	Source of stopping.

◆ search_swap_parity()

void search_swap_parity	(	Search *	search,
		const int	x
	)

Change parity.

Parameters

search	Search.
x	Played square.

◆ search_TC_NWS()

bool search_TC_NWS	(	HashData *	data,
		const int	depth,
		const int	selectivity,
		const int	alpha,
		int *	score
	)

Transposition Cutoff (TC).

Parameters

data	Transposition data.
depth	Search depth.
selectivity	Search selecticity level.
alpha	Alpha bound.
score	Score to return in case of a cutoff is found.

Returns: 'true' if a cutoff is found, false otherwise.

◆ search_TC_PVS()

bool search_TC_PVS	(	HashData *	data,
		const int	depth,
		const int	selectivity,
		volatile int *	alpha,
		volatile int *	beta,
		int *	score
	)

Transposition Cutoff (TC).

Parameters

data	Transposition data.
depth	Search depth.
selectivity	Search selecticity level.
alpha	Alpha bound, to adjust of necessary.
beta	Beta bound, to adjust of necessary.
score	Score to return in case of a cutoff is found.

Returns: 'true' if a cutoff is found, false otherwise.

◆ search_time()

long long search_time ( Search * search )

Return the time spent by the search.

Parameters

search Search.

Returns: time (in milliseconds).

◆ search_time_init()

void search_time_init ( Search * search )

Initialize the alloted time.

Parameters

search Search.

◆ search_time_reset()

void search_time_reset	(	Search *	search,
		const Board *	initial_board
	)

Reset the alloted time.

Adjust the time when continuing the search from pondering.

Parameters

search	Search.
initial_board	Initial board.

◆ search_update_endgame()

void search_update_endgame	(	Search *	search,
		const Move *	move
	)

Update the search state after a move.

Parameters

search	search.
move	played move.

◆ search_update_midgame()

void search_update_midgame	(	Search *	search,
		const Move *	move
	)

Update the search state after a move.

Parameters

search	search.
move	played move.

◆ search_update_pass_midgame()

void search_update_pass_midgame ( Search * search )

Update the search state after a passing move.

Parameters

search search.

◆ solvable_depth()

int solvable_depth	(	const long long	limit,
		int	n_tasks
	)

Compute the deepest level that can be solved given a limited time...

This is a very approximate computation... SMP_W & SMP_C depends on the depth and the position. The branching factor depends also of the position.

Parameters

limit	Time limit in ms.
n_tasks	Number of parallel tasks.

Returns: Reachable depth.

Variable Documentation

◆ LEVEL

struct Level LEVEL[61][61]

◆ NO_SELECTIVITY

const int NO_SELECTIVITY = 5

level with no selectivity

◆ NWS_STABILITY_THRESHOLD

const int NWS_STABILITY_THRESHOLD[]

Initial value:

= { 
         99, 99, 99, 99,  6,  8, 10, 12,
         14, 16, 20, 22, 24, 26, 28, 30,
         32, 34, 36, 38, 40, 42, 44, 46,
         48, 48, 50, 50, 52, 52, 54, 54,
         56, 56, 58, 58, 60, 60, 62, 62,
         64, 64, 64, 64, 64, 64, 64, 64,
         99, 99, 99, 99, 99, 99, 99, 99, 
}

threshold values to try stability cutoff during NWS search

◆ PVS_STABILITY_THRESHOLD

const int PVS_STABILITY_THRESHOLD[]

Initial value:

= { 
         99, 99, 99, 99, -2,  0,  2,  4,
          6,  8, 12, 14, 16, 18, 20, 22,
         24, 26, 28, 30, 32, 34, 36, 38,
         40, 40, 42, 42, 44, 44, 46, 46,
         48, 48, 50, 50, 52, 52, 54, 54,
         56, 56, 58, 58, 60, 60, 62, 62,
         99, 99, 99, 99, 99, 99, 99, 99, 
}

threshold values to try stability cutoff during PVS search

◆ QUADRANT_ID

const int QUADRANT_ID[]

Initial value:

= {
                1, 1, 1, 1, 2, 2, 2, 2,
                1, 1, 1, 1, 2, 2, 2, 2,
                1, 1, 1, 1, 2, 2, 2, 2,
                1, 1, 1, 1, 2, 2, 2, 2,
                4, 4, 4, 4, 8, 8, 8, 8,
                4, 4, 4, 4, 8, 8, 8, 8,
                4, 4, 4, 4, 8, 8, 8, 8,
                4, 4, 4, 4, 8, 8, 8, 8,
                0, 0
        }

a quadrant id for each square

◆ search_log

Log search_log[1]

◆ selectivity_table

const Selectivity selectivity_table[]

Initial value:

= {
        {1.1, 0, 73}, 
        {1.5, 1, 87}, 
        {2.0, 2, 95}, 
        {2.6, 3, 98}, 
        {3.3, 4, 99}, 
        {999, 5,100}, 
}

predefined selectivity

◆ SQUARE_TYPE

const int SQUARE_TYPE[]

Initial value:

= {
        0, 1, 2, 3, 3, 2, 1, 0,
        1, 4, 5, 6, 6, 5, 4, 1,
        2, 5, 7, 8, 8, 7, 5, 2,
        3, 6, 8, 9, 9, 8, 6, 3,
        3, 6, 8, 9, 9, 8, 6, 3,
        2, 5, 7, 8, 8, 7, 5, 2,
        1, 4, 5, 6, 6, 5, 4, 1,
        0, 1, 2, 3, 3, 2, 1, 0,
        9, 9,
}

square type

Functions

Variables

Detailed Description

Function Documentation

◆ get_pv_extension()

◆ is_depth_solving()

◆ result_print()

◆ search_adjust_time()

◆ search_check_timeout()

◆ search_cleanup()

◆ search_clock()

◆ search_clone()

◆ search_continue()

◆ search_count_nodes()

◆ search_count_tasks()

◆ search_ETC_NWS()

◆ search_free()

◆ search_get_movelist()

◆ search_global_init()

◆ search_guess()

◆ search_init()

◆ search_observer()

◆ search_pass_endgame()

◆ search_resize_hashtable()

◆ search_restore_endgame()

◆ search_restore_midgame()

◆ search_restore_pass_midgame()

◆ search_SC_NWS()

◆ search_SC_PVS()

◆ search_set_board()

◆ search_set_game_time()

◆ search_set_level()

◆ search_set_move_time()

◆ search_set_observer()

◆ search_set_ponder_level()

◆ search_set_state()

◆ search_set_task_number()

◆ search_setup()

◆ search_share()

◆ search_stop_all()

◆ search_swap_parity()

◆ search_TC_NWS()

◆ search_TC_PVS()

◆ search_time()

◆ search_time_init()

◆ search_time_reset()

◆ search_update_endgame()

◆ search_update_midgame()

◆ search_update_pass_midgame()

◆ solvable_depth()

Variable Documentation

◆ LEVEL

◆ NO_SELECTIVITY

◆ NWS_STABILITY_THRESHOLD

◆ PVS_STABILITY_THRESHOLD

◆ QUADRANT_ID

◆ search_log

◆ selectivity_table

◆ SQUARE_TYPE