Parallel search header. More...

#include "util.h"
#include "const.h"
#include "settings.h"
#include <stdbool.h>

Classes
struct	Task

struct	Node

struct	TaskStack

Typedefs
typedef struct Task	Task

typedef struct Node	Node

typedef struct TaskStack	TaskStack

Functions
void	node_init (Node , struct Search , const int, const int, const int, const int, Node *)
	Initialize a node.

void	node_free (Node *)
	Free Resources allocated by a node.

bool	node_split (Node , struct Move )
	Node split.

void	node_stop_slaves (Node *)

void	node_wait_slaves (Node *)
	Wait for slaves termination.

void	node_update (Node , struct Move )
	Update a node.

struct Move *	node_first_move (Node , struct MoveList )
	Get the first move of the move list.

struct Move *	node_next_move (Node *)
	Get the next move of the move list.

void *	task_loop (void *)
	The main loop runned by a task.

void *	task_help (void *)

void	task_init (Task *)
	Initialize a task.

void	task_free (Task *)
	Free resources used by a task.

void	task_update (Task *)

void	task_search (Task *task)
	A parallel search within a Task structure.

void	task_stack_init (TaskStack *, const int)
	Initialize the stack of tasks.

void	task_stack_free (TaskStack *)
	Free resources used by the stack of tasks.

void	task_stack_resize (TaskStack *, const int)
	Resize the stack of tasks.

void	task_stack_stop (TaskStack *, const Stop)

Task *	task_stack_get_idle_task (TaskStack *)
	Return, if available, an idle task.

void	task_stack_put_idle_task (TaskStack , Task )
	Put back an idle task after using it.

void	task_stack_clear (TaskStack *)

unsigned long long	task_stack_count_nodes (TaskStack *)

Detailed Description

Parallel search header.

Date: 1998 - 2017

Author: Richard Delorme

Version: 4.4

Typedef Documentation

◆ Node

typedef struct Node Node

A Node is a position in the search tree, containing information shared with parallel threads.

◆ Task

typedef struct Task Task

A Task is a parallel search thread.

◆ TaskStack

typedef struct TaskStack TaskStack

Function Documentation

◆ node_first_move()

struct Move * node_first_move	(	Node *	node,
		MoveList *	movelist )

Get the first move of the move list.

This is thread/safe getter of the first move. If the search is stopped, or an alphabeta cut has been found or no move is available the function returns NULL.

Parameters

node	Node data.
movelist	List of moves.

Returns: the first move of the list or NULL if none is available.

◆ node_free()

void node_free ( Node * node )

Free Resources allocated by a node.

Parameters

node Node.

◆ node_init()

void node_init	(	Node *	node,
		Search *	search,
		const int	alpha,
		const int	beta,
		const int	depth,
		const int	n_moves,
		Node *	parent )

Initialize a node.

Initialize the various members of the node structure. The important part of the initialization establishes a master-slave relashionship between this node (the slave) and its parent (the master).

Parameters

node	A potentially shared position.
search	The position searched
alpha	lower score bound.
beta	upper score bound.
depth	depth.
n_moves	Move count.
parent	The parent node.

◆ node_next_move()

struct Move * node_next_move ( Node * node )

Get the next move of the move list.

This is a thread/safe getter of the next move.

Parameters

node	Node data.

Returns: the next move of the list.

◆ node_split()

bool node_split	(	Node *	node,
		Move *	move )

Node split.

Here is the heart of the YBWC algorithm. It splits a node into two tasks. Splitting occurs if the following conditions are met:

the first move has been already searched. The main principle of the YBWC algorithm. It avoids to split a cut-type node, for which searching a single move is enough, and thus diminish search-overhead.
search to do is deep enough. In order to diminish the overhead of the parallelism. Can be tuned through SPLIT_MIN_DEPTH.
the node has not been splitted yet. For a single position, only two tasks can run in parallel. The idea is to favor splitting elsewhere in the tree.
This is not the last move. The idea is to lose less time in waiting for the parallel task to terminate. Can be tuned through SPLIT_MIN_MOVES_TODO. If these conditions are met, an idle task is requested, first from an idle task of a parent node; then, if none is available, from the idle task stack storage. If no idle task is found, the node splitting fails.

Parameters

node	Master node to split.
move	move to search.

Returns: true if the split was a success, false otherwise.

◆ node_stop_slaves()

void node_stop_slaves ( Node * )

◆ node_update()

void node_update	(	Node *	node,
		Move *	move )

Update a node.

Update bestmove, bestscore and alpha value of the node, in case the move is the bestmove found so far. The function is thread-safe although it updates a shared resource. Double check lock is used as an optimization.

Parameters

node	current node.
move	last evaluated move.

◆ node_wait_slaves()

void node_wait_slaves ( Node * node )

Wait for slaves termination.

Actually, three steps are performed here:

Stop slaves node in case their scores are unneeded.
Wait for slaves' termination.
Wake-up the master thread that may have been stopped.

Parameters

node Node.

◆ task_free()

void task_free ( Task * task )

Free resources used by a task.

Parameters

task The task.

◆ task_help()

void * task_help ( void * )

◆ task_init()

void task_init ( Task * task )

Initialize a task.

Initialize task data members and start the task main loop task_loop() within a thread.

Parameters

task The task.

◆ task_loop()

void * task_loop ( void * param )

The main loop runned by a task.

When task->run is set to true, the task starts a parallel search. In order to diminish the parallelism overhead, we do not launch a new thread at each new splitted node. Instead the threads are created at the beginning of the program and run a waiting loop who enters/quits a parallel search when requested.

Parameters

param The task.

Returns: NULL.

◆ task_search()

void task_search ( Task * task )

A parallel search within a Task structure.

Here we share the search with a main parent task.

Parameters

task	The task to search with.

◆ task_stack_clear()

void task_stack_clear ( TaskStack * )

◆ task_stack_count_nodes()

unsigned long long task_stack_count_nodes ( TaskStack * )

◆ task_stack_free()

void task_stack_free ( TaskStack * stack )

Free resources used by the stack of tasks.

Parameters

stack The stack of tasks.

◆ task_stack_get_idle_task()

Task * task_stack_get_idle_task ( TaskStack * stack )

Return, if available, an idle task.

Parameters

stack The stack of tasks.

Returns: An idle task.

◆ task_stack_init()

void task_stack_init	(	TaskStack *	stack,
		const int	n )

Initialize the stack of tasks.

Parameters

stack	The stack of tasks.
n	Stack size (number of tasks).

◆ task_stack_put_idle_task()

void task_stack_put_idle_task	(	TaskStack *	stack,
		Task *	task )

Put back an idle task after using it.

Parameters

stack	The stack of tasks.
task	An idle task.

◆ task_stack_resize()

void task_stack_resize	(	TaskStack *	stack,
		const int	n )

Resize the stack of tasks.

Parameters

stack	Stack to resize.
n	New stack size.

◆ task_stack_stop()

void task_stack_stop	(	TaskStack *	,
		const Stop	)

◆ task_update()

void task_update ( Task * )

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ Node

◆ Task

◆ TaskStack

Function Documentation

◆ node_first_move()

◆ node_free()

◆ node_init()

◆ node_next_move()

◆ node_split()

◆ node_stop_slaves()

◆ node_update()

◆ node_wait_slaves()

◆ task_free()

◆ task_help()

◆ task_init()

◆ task_loop()

◆ task_search()

◆ task_stack_clear()

◆ task_stack_count_nodes()

◆ task_stack_free()

◆ task_stack_get_idle_task()

◆ task_stack_init()

◆ task_stack_put_idle_task()

◆ task_stack_resize()

◆ task_stack_stop()

◆ task_update()