Lock-free transposition table. More...

#include "bit.h"
#include "hash.h"
#include "options.h"
#include "stats.h"
#include "search.h"
#include "util.h"
#include "settings.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

Functions
void	hash_code_init (void)
	Initialize global hash code data. More...

void	hash_move_init (void)
	Initialize global hash move data. More...

void	hash_init (HashTable *hash_table, const unsigned long long size)
	Initialise the hashtable. More...

void	hash_cleanup (HashTable *hash_table)
	Clear the hashtable. More...

void	hash_clear (HashTable *hash_table)
	Clear the hashtable. More...

void	hash_free (HashTable *hash_table)
	Free the hashtable. More...

unsigned int	writeable_level (HashData *data)
	make a level from date, cost, depth & selectivity. More...

static void	data_update (HashData *data, const int cost, const int alpha, const int beta, const int score, const int move)
	update an hash table item. More...

static void	data_upgrade (HashData *data, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
	Upgrade an hash table data item. More...

static void	data_new (HashData *data, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
	Set an hash table data item. More...

static void	hash_new (Hash hash, HashLock lock, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
	Initialize a new hash table item. More...

static void	hash_set (Hash hash, HashLock lock, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int lower, const int upper, const int move)
	Set a new hash table item. More...

static bool	hash_update (Hash hash, HashLock lock, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
	update the hash entry More...

static bool	hash_replace (Hash hash, HashLock lock, const Board *board, const int date, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
	replace the hash entry. More...

static bool	hash_reset (Hash hash, HashLock lock, const Board *board, const int date, const int depth, const int selectivity, const int lower, const int upper, const int move)
	Reset an hash entry from new data values. More...

void	hash_feed (HashTable hash_table, const Board board, const unsigned long long hash_code, const int depth, const int selectivity, const int lower, const int upper, const int move)
	feed hash table (from Cassio). More...

void	hash_store (HashTable hash_table, const Board board, const unsigned long long hash_code, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
	Store an hashtable item. More...

void	hash_force (HashTable hash_table, const Board board, const unsigned long long hash_code, const int depth, const int selectivity, const int cost, const int alpha, const int beta, const int score, const int move)
	Store an hashtable item. More...

bool	hash_get (HashTable hash_table, const Board board, const unsigned long long hash_code, HashData *data)
	Find an hash table entry according to the evaluated board hash codes. More...

Variables
unsigned long long	hash_rank [16][256]

unsigned long long	hash_move [64][60]

const HashData	HASH_DATA_INIT = {0, 0, 0, 0, -SCORE_INF, SCORE_INF, {NOMOVE, NOMOVE}}

Detailed Description

Lock-free transposition table.

Locked transposition table.

The hash table is an efficient memory system to remember the previously analysed positions and re-use the collected data when needed. The hash table contains entries of analysed data where the board is uniquely identified through a 64-bit key and the results of the recorded analysis are two score bounds, the level of the analysis and the best move found. The implementation is now a multi-way hashtable. It both tries to keep the deepest records and to always add the latest one. The following implementation may suffer from hash collision: two different positions may share the same hashcode. Fortunately, this is very unprobable with hascode on 64 bits, and, thanks to alphabeta robustness, it propagates even less often to the root. When doing parallel search with a shared hashtable, a lockless implementation [1] detects & eliminates concurrency collisions without much performance impact.

[1] http://www.cis.uab.edu/hyatt/hashing.html

Date: 1998 - 2012

Author: Richard Delorme

Version: 4.4

The hash table is an efficient memory system to remember the previously analysed positions and re-use the collected data when needed. The hash table contains entries of analysed data where the board is uniquely identified through a 64-bit key and the results of the recorded analysis are two score bounds, the level of the analysis and the best move found. The implementation is now a multi-way hashtable. It both tries to keep the deepest records and to always add the latest one. The following implementation may suffer from hash collision: two different positions may share the same hashcode. Fortunately, this is very improbable with hascode on 64 bits, and, thanks to alphabeta robustness, it propagates even less often to the root. When doing parallel search with a shared hashtable, a locked implementation avoid concurrency collisions.

Date: 1998 - 2012

Author: Richard Delorme

Version: 4.4

The hash table is an efficient memory system to remember the previously analysed positions and re-use the collected data when needed. The hash table contains entries of analysed data where the board is stored and the results of the recorded analysis are two score bounds, the level of the analysis and the best move found. The implementation is now a multi-way (or bucket based) hashtable. It both tries to keep the deepest records and to always add the latest one. The following implementation store the whole board to avoid collision. When doing parallel search with a shared hashtable, a locked implementation avoid concurrency collisions.

Date: 1998 - 2017

Author: Richard Delorme

Version: 4.4

Function Documentation

◆ data_new()

static void data_new	(	HashData *	data,
		const int	date,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

static

Set an hash table data item.

Parameters

data	Hash Data.
date	Search Date.
depth	Search depth.
selectivity	Search selectivity.
cost	Search cost (log2(node count)).
alpha	Alpha bound.
beta	Beta bound.
score	Best score.
move	Best move.

◆ data_update()

static void data_update	(	HashData *	data,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

static

update an hash table item.

This is done when the level is the same as the previous storage. Best moves & bound scores are updated, other data are untouched.

Parameters

data	Hash Data.
cost	Search cost (log2(node count)).
alpha	Alpha bound.
beta	Beta bound.
score	Best score.
move	Best move.

◆ data_upgrade()

static void data_upgrade	(	HashData *	data,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

static

Upgrade an hash table data item.

Upgrade is done when the search level increases. Best moves are updated, others data are reset to new value.

Parameters

data	Hash Data.
depth	Search depth.
selectivity	Search selectivity.
cost	Search cost (log2(node count)).
alpha	Alpha bound.
beta	Beta bound.
score	Best score.
move	Best move.

◆ hash_cleanup()

void hash_cleanup ( HashTable * hash_table )

Clear the hashtable.

Set all hash table entries to zero.

Parameters

hash_table Hash table to clear.

◆ hash_clear()

void hash_clear ( HashTable * hash_table )

Clear the hashtable.

Change the date of the hash table.

Parameters

hash_table Hash table to clear.

◆ hash_code_init()

void hash_code_init ( void )

Initialize global hash code data.

◆ hash_feed()

void hash_feed	(	HashTable *	hash_table,
		const Board *	board,
		const unsigned long long	hash_code,
		const int	depth,
		const int	selectivity,
		const int	lower,
		const int	upper,
		const int	move
	)

feed hash table (from Cassio).

Parameters

hash_table	Hash Table.
hash_code	Hash code.
depth	Search depth.
selectivity	Selectivity level.
lower	Alpha bound.
upper	Beta bound.
move	best move.

◆ hash_force()

void hash_force	(	HashTable *	hash_table,
		const Board *	board,
		const unsigned long long	hash_code,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

Store an hashtable item.

Does the same as hash_store() except it always store the current search state

Parameters

hash_table	Hash table to update.
hash_code	Hash code of an othello board.
alpha	Alpha bound when calling the alphabeta function.
depth	Search depth.
selectivity	Search selectivity.
cost	Search cost (i.e. log2(node count)).
beta	Beta bound when calling the alphabeta function.
score	Best score found.
move	Best move found.

◆ hash_free()

void hash_free ( HashTable * hash_table )

Free the hashtable.

Free the memory allocated by the hash table entries

Parameters

hash_table hash_table to free.

◆ hash_get()

bool hash_get	(	HashTable *	hash_table,
		const Board *	board,
		const unsigned long long	hash_code,
		HashData *	data
	)

Find an hash table entry according to the evaluated board hash codes.

Parameters

hash_table	Hash table.
hash_code	Hash code of an othello board.
data	Output hash data.

Returns: True the board was found, false otherwise.

Erase an hash table entry.

Parameters

hash_table	Hash table.
hash_code	Hash code of an othello board.
move	Move to exclude.

Copy an hastable to another one.

Parameters

src	Source hash table to copy.
dest	Destination hash table.

print HashData content.

Parameters

data	Hash Data
f	Output stream

◆ hash_init()

void hash_init	(	HashTable *	hash_table,
		const unsigned long long	size
	)

Initialise the hashtable.

Allocate the hash table entries and initialise the hash masks.

Parameters

hash_table	Hash table to setup.
size	Requested size for the hash table in number of entries.

◆ hash_move_init()

void hash_move_init ( void )

Initialize global hash move data.

◆ hash_new()

static void hash_new	(	Hash *	hash,
		HashLock *	lock,
		const Board *	board,
		const int	date,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

static

Initialize a new hash table item.

This implementation tries to be robust against concurrency. Data are first set up in a local thread-safe structure, before being copied into the hashtable entry. Then the hashcode of the entry is xored with the thread safe structure ; so that any corrupted entry won't be readable.

Parameters

hash	Hash Entry.
lock	Lock.
hash_code	Hash code.
date	Hash date.
depth	Search depth.
selectivity	Search selectivity.
cost	Search cost.
alpha	Alpha bound.
beta	Beta bound.
score	Best score.
move	Best move.

◆ hash_replace()

static bool hash_replace	(	Hash *	hash,
		HashLock *	lock,
		const Board *	board,
		const int	date,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

static

replace the hash entry.

This implementation tries to be robust against concurrency. Data are first set up in a local thread-safe structure, before being copied into the hashtable entry. Then the hashcode of the entry is xored with the thread safe structure ; so that any corrupted entry won't be readable.

Parameters

hash	Hash Entry.
lock	Lock.
hash_code	Hash code.
date	Hash date.
depth	Search depth.
selectivity	Search selectivity.
cost	Hash Cost (log2(node count)).
alpha	Alpha bound.
beta	Beta bound.
score	Best score.
move	Best move.

Returns: true if an entry has been replaced, false otherwise.

◆ hash_reset()

static bool hash_reset	(	Hash *	hash,
		HashLock *	lock,
		const Board *	board,
		const int	date,
		const int	depth,
		const int	selectivity,
		const int	lower,
		const int	upper,
		const int	move
	)

static

Reset an hash entry from new data values.

Parameters

hash	Hash Entry.
lock	Lock.
hash_code	Hash code.
date	Hash date.
depth	Search depth.
selectivity	Search selectivity.
lower	Lower score bound.
upper	Upper score bound.
move	Best move.

◆ hash_set()

static void hash_set	(	Hash *	hash,
		HashLock *	lock,
		const Board *	board,
		const int	date,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	lower,
		const int	upper,
		const int	move
	)

static

Set a new hash table item.

This implementation tries to be robust against concurrency. Data are first set up in a local thread-safe structure, before being copied into the hashtable entry. Then the hashcode of the entry is xored with the thread safe structure ; so that any corrupted entry won't be readable.

Parameters

hash	Hash Entry.
lock	Lock.
hash_code	Hash code.
date	Hash date.
depth	Search depth.
selectivity	Search selectivity.
cost	Search cost.
lower	Lower score bound.
upper	Upper score bound.
move	Best move.

◆ hash_store()

void hash_store	(	HashTable *	hash_table,
		const Board *	board,
		const unsigned long long	hash_code,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

Store an hashtable item.

Find an hash table entry according to the evaluated board hash codes. Then update the entry if it already exists otherwise create a new one. Collisions are managed in such a way that better existing entries are always preserved and the new evaluated data is always added. Lower and upper score bounds are then updated/set from the alpha, beta and score values according to the following alphabeta property (where alpha < beta): -if (score >= beta) score is a lower bound of the real score -if (score <= alpha) score is an upper bound of the real score -if (alpha < score && score < beta) score equals the real score So: -if (score < beta) update the upper bound of the hash entry -if (score > alpha) update the lower bound of the hash entry The best move is also stored, but only if score >= alpha. In case the entry already exists with better data, nothing is stored.

Parameters

hash_table	Hash table to update.
hash_code	Hash code of an othello board.
alpha	Alpha bound when calling the alphabeta function.
depth	Search depth.
selectivity	Search selectivity.
cost	Search cost (i.e. log2(node count)).
beta	Beta bound when calling the alphabeta function.
score	Best score found.
move	Best move found.

◆ hash_update()

static bool hash_update	(	Hash *	hash,
		HashLock *	lock,
		const Board *	board,
		const int	date,
		const int	depth,
		const int	selectivity,
		const int	cost,
		const int	alpha,
		const int	beta,
		const int	score,
		const int	move
	)

static

update the hash entry

This implementation tries to be robust against concurrency. Data are first set up in a local thread-safe structure, before being copied into the hashtable entry. Then the hashcode of the entry is xored with the thread safe structure ; so that any corrupted entry won't be readable.

Parameters

hash	Hash Entry.
lock	Lock.
hash_code	Hash code.
date	Hash date.
depth	Search depth.
selectivity	Search selectivity.
cost	Hash Cost (log2(node count)).
alpha	Alpha bound.
beta	Beta bound.
score	Best score.
move	Best move.

Returns: true if an entry has been updated, false otherwise.

◆ writeable_level()

unsigned int writeable_level ( HashData * data )

inline

make a level from date, cost, depth & selectivity.

Parameters

data	Hash data.

Returns: A level.

Variable Documentation

◆ HASH_DATA_INIT

const HashData HASH_DATA_INIT = {0, 0, 0, 0, -SCORE_INF, SCORE_INF, {NOMOVE, NOMOVE}}

HashData init value

◆ hash_move

unsigned long long hash_move[64][60]

hashing global data

◆ hash_rank

unsigned long long hash_rank[16][256]

hashing global data

Functions

Variables

Detailed Description

Function Documentation

◆ data_new()

◆ data_update()

◆ data_upgrade()

◆ hash_cleanup()

◆ hash_clear()

◆ hash_code_init()

◆ hash_feed()

◆ hash_force()

◆ hash_free()

◆ hash_get()

◆ hash_init()

◆ hash_move_init()

◆ hash_new()

◆ hash_replace()

◆ hash_reset()

◆ hash_set()

◆ hash_store()

◆ hash_update()

◆ writeable_level()

Variable Documentation

◆ HASH_DATA_INIT

◆ hash_move

◆ hash_rank