Parallel search. More...

#include "ybwc.h"
#include "move.h"
#include "options.h"
#include "util.h"
#include "search.h"
#include "stats.h"
#include "settings.h"
#include <assert.h>
#include <stdlib.h>

Functions
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.

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

static bool	get_helper (Node master, Node node, Move *move)
	Seek for & use an helper node.

bool	node_split (Node node, Move move)
	Node split.

void	node_wait_slaves (Node *node)
	Wait for slaves termination.

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

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

static Move *	node_next_move_lockless (Node *node)
	Get the next move of the move list.

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

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

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

static Search *	task_search_create (Task *task)
	Create a search structure for a task.

static void	task_search_destroy (Search *search)
	Free a search structure of a task.

void	task_init (Task *task)
	Initialize a task.

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

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

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

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

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

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

Variables
Log	search_log [1]

Detailed Description

Parallel search.

The Young Brother Wait Concept [1, 2] is an efficient technique to search a position with several cpu/core working in parallel. At an inner nodes, this technique always evaluates the first move using a sequential approach, but try to evaluate the siblings in parallel, once the first move has been computed. The YBWC has some nice properties: low search overhead, good scalability, easy implementation, etc.

This file holds the function definition to manipulate structures used in our implementation of parallelism:

Node describes a position shared between different threads.
Task describes a search running in parallel within a thread.
TaskStack is a FIFO providing task available for a new search.

References:

Feldmann R., Monien B., Mysliwietz P. Vornberger O. (1989) Distributed Game-Tree Search. ICCA Journal, Vol. 12, No. 2, pp. 65-73.
Feldmann R. (1993) Game-Tree Search on Massively Parallel System - PhD Thesis, Paderborn (English version).

Date: 1998 - 2017

Author: Richard Delorme

Version: 4.4

Function Documentation

◆ get_helper()

static bool get_helper	(	Node *	master,
		Node *	node,
		Move *	move )

static

Seek for & use an helper node.

When asking for an idle task, this function look if a parent node is waiting and has a task available to help the current search.

Parameters

master	A parent node with an idle task.
node	Searched node.
move	Searched move.

Returns: true if an helper task has been launch, false otherwise.

◆ node_first_move()

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()

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_next_move_lockless()

static Move * node_next_move_lockless ( Node * node )

static

Get the next move of the move list.

This is a thread/safe getter of the next 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.

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

◆ 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_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_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_search_create()

static Search * task_search_create ( Task * task )

static

Create a search structure for a task.

Parameters

task The task.

Returns: a search structure.

◆ task_search_destroy()

static void task_search_destroy ( Search * search )

static

Free a search structure of a task.

Parameters

search The search structure.

◆ 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.

Variable Documentation

◆ search_log

Log search_log[1]

extern

Functions

Variables

Detailed Description

Function Documentation

◆ get_helper()

◆ node_first_move()

◆ node_free()

◆ node_init()

◆ node_next_move()

◆ node_next_move_lockless()

◆ node_split()

◆ node_update()

◆ node_wait_slaves()

◆ task_free()

◆ task_init()

◆ task_loop()

◆ task_search()

◆ task_search_create()

◆ task_search_destroy()

◆ task_stack_free()

◆ task_stack_get_idle_task()

◆ task_stack_init()

◆ task_stack_put_idle_task()

◆ task_stack_resize()

Variable Documentation

◆ search_log