ybwc.c

Go to the documentation of this file.

 
#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>
 
extern Log search_log[1];
 
void node_init(Node* node, Search *search, const int alpha, const int beta, const int depth, const int n_moves, Node* parent)
{
        int i;
        
        assert(node != NULL);
        assert(SCORE_MIN <= alpha && alpha <= SCORE_MAX);
        assert(SCORE_MIN <= beta && beta <= SCORE_MAX);
        assert(alpha < beta);
 
        lock_init(node);
        condition_init(node);
 
        node->alpha = alpha;
        node->beta = beta;
        node->depth = depth;
        node->height = search->height;
        node->move = NULL;
        node->pv_node = false;
        node->bestmove = NOMOVE;
        node->bestscore = -SCORE_INF;
        node->n_moves_todo = n_moves;
        node->n_moves_done = 0;
        node->parent = parent;
        node->search = search;
        for (i = 0; i < SPLIT_MAX_SLAVES; ++i) node->slave[i] = NULL;
        node->n_slave = 0;
        node->is_waiting = false;
        node->is_helping = false;
        node->stop_point = false;
}
 
void node_free(Node *node)
{
        lock_free(node);
        condition_free(node);
}
 
static bool get_helper(Node *master, Node *node, Move *move)
{
        Task *task;
        bool found = false;
 
        if (master) {
                if (master->is_waiting && !master->is_helping) {
                        lock(master);
                        if (master->n_slave && master->is_waiting && !master->is_helping) {
                                master->is_helping = true;
                                task = master->help;
                                task_init(task) ;
                                task->is_helping = true;
                                task->node = node;
                                task->move = move;
                                search_clone(task->search, node->search);
                                lock(node);
                                        node->slave[node->n_slave++] = task->search;
                                unlock(node);                   
                                task->run = true;
                                found = true;
 
                                condition_broadcast(master);
                        }
                        unlock(master);
                } else {
                        found = get_helper(master->parent, node, move);
                }
        }
 
        return found;
}
 
bool node_split(Node *node, Move *move)
{
        Task *task;
        Search *search = node->search;
 
        if (search->allow_node_splitting // split only if parallelism is on
         && node->depth >= SPLIT_MIN_DEPTH // split if we are deep enough
         && node->n_moves_done // do not split first move (ybwc main principle).
         && node->n_slave < SPLIT_MAX_SLAVES // do not split too much at the same point.
         && node->n_moves_todo >=  SPLIT_MIN_MOVES_TODO) {  // do not split the last move(s), to diminish waiting time
                YBWC_STATS(atomic_add(&statistics.n_split_try, 1);)
 
                if (get_helper(node->parent, node, move)) {
                        YBWC_STATS(atomic_add(&statistics.n_master_helper, 1);)
                        return true;
                } else if ((task = task_stack_get_idle_task(search->tasks)) != NULL) {
                        task->node = node;
                        task->move = move;
                        search_clone(task->search, search);
                        lock(node);
                                node->slave[node->n_slave++] = task->search;
                        unlock(node);
                        YBWC_STATS(atomic_add(&statistics.n_split_success, 1);)
 
                        lock(task);
                                task->run = true;
                                condition_signal(task);
                        unlock(task);
 
                        return true;
                }
        }
        return false;
}
 
void node_wait_slaves(Node* node)
{
        int i;
 
        lock(node);
        // stop slaves ?
        if ((node->alpha >= node->beta || node->search->stop) && node->n_slave) {
                for (i = 0; i < node->n_slave; ++i) {
                        search_stop_all(node->slave[i], STOP_PARALLEL_SEARCH);
                        YBWC_STATS(atomic_add(&statistics.n_stopped_slave, 1);)
                }
        }
 
        // wait slaves
        YBWC_STATS(atomic_add(&statistics.n_waited_slave, node->n_slave > 0);)
        while (node->n_slave) {
                node->is_waiting = true;
                assert(node->is_helping == false);
                condition_wait(node);
 
                if (node->is_helping) {
                        assert(node->help->run);
                        task_search(node->help);
                        task_free(node->help);
                        node->is_helping = false;
                } else {
                        node->is_waiting = false;
                }
        }
 
        // wake-up master thread!
        if (node->search->stop == STOP_PARALLEL_SEARCH && node->stop_point) {
                node->search->stop = RUNNING;
                node->stop_point = false;
                YBWC_STATS(atomic_add(&statistics.n_wake_up, 1);)
        }
        unlock(node);
}
 
 
void node_update(Node* node, Move *move)
{
        Search *search = node->search;
        const int score = move->score;
        int i;
 
        lock(node);
        if (!search->stop && score > node->bestscore) {
                node->bestscore = score;
                node->bestmove = move->x;
                if (node->height == 0) {
                        record_best_move(search, search->board, move, node->alpha, node->beta, node->depth);
                        search->result->n_moves_left--;
                }
                if (score > node->alpha) node->alpha = score;
        }
        if (node->alpha >= node->beta  && node->n_slave) { // stop slave ?
                for (i = 0; i < node->n_slave; ++i) {
                        search_stop_all(node->slave[i], STOP_PARALLEL_SEARCH);
                        YBWC_STATS(atomic_add(&statistics.n_stopped_slave, 1);)
                }
        }
        unlock(node);   
}
 
Move* node_first_move(Node *node, MoveList *movelist)
{
        Move *move;
        lock(node);
                node->n_moves_todo = movelist->n_moves;
                node->n_moves_done = 0;
                node->move = movelist_first(movelist);
                if (node->move && !node->search->stop) {
                        assert(node->alpha < node->beta);
                        move = node->move;
                } else {
                        move = NULL;
                }
        unlock(node);
        return move;
}
 
static Move* node_next_move_lockless(Node *node)
{
        Move *move;
        if (node->move && node->alpha < node->beta && !node->search->stop) {
                ++node->n_moves_done; --node->n_moves_todo;
                move = node->move = move_next(node->move);
        } else {
                move = NULL;
        }
 
        return move;
}
 
Move* node_next_move(Node *node)
{
        Move *move;
        lock(node);
                move = node_next_move_lockless(node);
        unlock(node);
 
        return move;
}
 
void task_search(Task *task)
{
 
        Node *node = task->node;
        Search *search = task->search;
        Move *move = task->move;
        int i;
 
        search_set_state(search, node->search->stop);
 
        YBWC_STATS(++task->n_calls;)
 
        while (move && !search->stop) {
                const int alpha = node->alpha;
                if (alpha >= node->beta) break;
 
                search_update_midgame(search, move);
                        move->score = -NWS_midgame(search, -alpha - 1, node->depth - 1, node);
                        if (alpha < move->score && move->score < node->beta) {
                                move->score = -PVS_midgame(search, -node->beta, -alpha, node->depth - 1, node);
                                assert(node->pv_node == true);
                        }
                search_restore_midgame(search, move);
                if (node->height == 0) {
                        move->cost = search_get_pv_cost(search);
                        move->score = search_bound(search, move->score);
                        if (log_is_open(search_log)) show_current_move(search_log->f, search, move, alpha, node->beta, true);
                }
 
                lock(node);
                if (!search->stop && move->score > node->bestscore) {
                        node->bestscore = move->score;
                        node->bestmove = move->x;
                        if (node->height == 0) {
                                record_best_move(search, search->board, move, alpha, node->beta, node->depth);
                                search->result->n_moves_left--;
                                if (search->options.verbosity == 4) pv_debug(search, move, stdout);
                        }
                        if (node->bestscore > node->alpha) {
                                node->alpha = node->bestscore;
                                if (node->alpha >= node->beta && node->search->stop == RUNNING) { // stop the master thread?
                                        node->stop_point = true;
                                        node->search->stop = STOP_PARALLEL_SEARCH;
                                        YBWC_STATS(atomic_add(&statistics.n_stopped_master, 1);)
                                }
                        }
                }
                move = node_next_move_lockless(node);
                unlock(node);
        }
 
        search_set_state(search, STOP_END);
 
        spin_lock(search->parent);
                for (i = 0; i < search->parent->n_child; ++i) {
                        if (search->parent->child[i] == search) {
                                --search->parent->n_child;
                                search->parent->child[i] = search->parent->child[search->parent->n_child];
                                break;
                        }
                }
                search->parent->child_nodes += search_count_nodes(search);
                YBWC_STATS(task->n_nodes += search->n_nodes;)
        spin_unlock(search->parent);
 
        lock(node);
                task->run = false;
                for (i = 0; i < node->n_slave; ++i) {
                        if (node->slave[i] == search) {
                                --node->n_slave;
                                node->slave[i] = node->slave[node->n_slave];
                                break;
                        }
                }
                condition_broadcast(node);
        unlock(node);
}
 
 
void* task_loop(void *param)
{
        Task *task = (Task*) param;
 
        lock(task);
        task->loop = true;
 
        while (task->loop) {
                if (!task->run) {
                        condition_wait(task);
                }
                if (task->run) {
                        task_search(task);
                        task_stack_put_idle_task(task->container, task);
                }
        }
 
        unlock(task);
 
        return NULL;
}
 
static Search* task_search_create(Task *task)
{
        Search *search;
 
        search = (Search*) malloc(sizeof (Search)); // allocate the search attached to this task
        if (search == NULL) {
                fatal_error("task_init: cannot allocate the search position.\n");
        }
        search->n_nodes = 0;
        search->n_child = 0;
        search->parent = NULL;
        eval_init(search->eval);
        spin_init(search);
        search->task = task;
        search->stop = STOP_END;
 
        return search;
}
 
static void task_search_destroy(Search *search)
{
        eval_free(search->eval);
        spin_free(search);
        free(search);
}
 
void task_init(Task *task)
{
        lock_init(task);
        condition_init(task);
 
        task->loop = false;
        task->run = false;
        task->node = NULL;
        task->move = NULL;
        task->n_calls = 0;
        task->n_nodes = 0;
        task->search = task_search_create(task);
}
 
 
void task_free(Task *task)
{
        assert(task->run == false);
        if (task->loop) {
                task->loop = false; // stop the main loop
                condition_signal(task);
                thread_join(task->thread);
        }
        lock_free(task);
        condition_free(task);
        task_search_destroy(task->search); // free other resources
        task->search = NULL;
}
 
void task_stack_init(TaskStack *stack, const int n)
{
        int i;
 
        spin_init(stack);
 
        stack->n = n; // number of additional task
        stack->n_idle = 0;
 
        if (stack->n) {
                // allocate the tasks
                stack->task = (Task*) malloc(stack->n * sizeof (Task));
                stack->stack = (Task**) malloc(stack->n * sizeof (Task*));
                if (stack->task == NULL) {
                        fatal_error("Cannot allocate an array of %d tasks\n", stack->n);
                }
                if (stack->stack == NULL) {
                        fatal_error("Cannot allocate a stack of %d entries\n", stack->n);
                }
 
                // init the tasks.
                for (i = 0; i < stack->n; ++i) {
                        if (i) {
                                task_init(stack->task + i);
                                thread_create2(&stack->task[i].thread, task_loop, stack->task + i); // modified for iOS by lavox. 2018/1/16
                                if (options.cpu_affinity) thread_set_cpu(stack->task[i].thread, i); /* CPU 0 to n - 1 */
                        }
                        stack->task[i].container = stack;
                        stack->stack[i] = NULL;
                }
 
                // put the tasks onto stack;
                for (i = 1; i < stack->n; ++i) {
                        task_stack_put_idle_task(stack, stack->task + i);
                }
 
        } else { // No parallel search
                stack->task = NULL;
                stack->stack = NULL;
        }
}
 
void task_stack_free(TaskStack *stack)
{
        int i;
        for (i = 1; i < stack->n; ++i) {
                task_free(stack->task + i);
        }
        free(stack->task); stack->task = NULL;
        free(stack->stack); stack->stack = NULL;
        stack->n = 0;
        stack->n_idle = 0;
        spin_free(stack);
}
 
void task_stack_resize(TaskStack *stack, const int n)
{
        task_stack_free(stack);
        task_stack_init(stack, n);
}
 
Task* task_stack_get_idle_task(TaskStack *stack)
{
        Task *task;
 
        spin_lock(stack);
 
        if (stack->n_idle) {
                task = stack->stack[--stack->n_idle];
        } else {
                task = NULL;
        }
 
        spin_unlock(stack);
 
        return task;
}
 
void task_stack_put_idle_task(TaskStack *stack, Task *task)
{
        spin_lock(stack);
 
        stack->stack[stack->n_idle++] = task;
 
        spin_unlock(stack);
}