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

static unsigned long long	hash_key (const HashData *data)
	Transform hash data into a 64 bits key. More...

void	hash_init (HashTable *hash_table, const int 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 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)

static void	hash_new (Hash *hash, const unsigned long long hash_code, 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...

void	hash_set (Hash *hash, const unsigned long long hash_code, 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, const unsigned long long hash_code, 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, const unsigned long long hash_code, 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...

bool	hash_reset (Hash *hash, const unsigned long long hash_code, 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 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 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 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 unsigned long long hash_code, HashData data)
	Find an hash table entry according to the evaluated board hash codes. More...

void	hash_exclude_move (HashTable *hash_table, const unsigned long long hash_code, const int move)
	Erase an hash table entry. More...

void	hash_copy (const HashTable src, HashTable dest)
	Copy an hastable to another one. More...

void	hash_print (const HashData data, FILE f)
	print HashData content. 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}}

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

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

void hash_copy	(	const HashTable *	src,
		HashTable *	dest
	)

Copy an hastable to another one.

Parameters

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

◆ hash_exclude_move()

void hash_exclude_move	(	HashTable *	hash_table,
		const unsigned long long	hash_code,
		const int	move
	)

Erase an hash table entry.

Parameters

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

◆ hash_feed()

void hash_feed	(	HashTable *	hash_table,
		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 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 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.

◆ hash_init()

void hash_init	(	HashTable *	hash_table,
		const int	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 bits.

◆ hash_key()

static unsigned long long hash_key ( const HashData * data )

inlinestatic

Transform hash data into a 64 bits key.

Parameters

data	Hash data.

Returns: a 64 bits key.

◆ hash_move_init()

void hash_move_init ( void )

Initialize global hash move data.

◆ hash_new()

static void hash_new	(	Hash *	hash,
		const unsigned long long	hash_code,
		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.
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_print()

void hash_print	(	const HashData *	data,
		FILE *	f
	)

print HashData content.

Parameters

data	Hash Data
f	Output stream

◆ hash_replace()

static bool hash_replace	(	Hash *	hash,
		const unsigned long long	hash_code,
		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.
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()

bool hash_reset	(	Hash *	hash,
		const unsigned long long	hash_code,
		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.

Parameters

hash	Hash Entry.
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()

void hash_set	(	Hash *	hash,
		const unsigned long long	hash_code,
		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.

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.
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 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,
		const unsigned long long	hash_code,
		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.
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

Function Documentation

◆ data_new()

◆ data_update()

◆ data_upgrade()

◆ hash_cleanup()

◆ hash_clear()

◆ hash_code_init()

◆ hash_copy()

◆ hash_exclude_move()

◆ hash_feed()

◆ hash_force()

◆ hash_free()

◆ hash_get()

◆ hash_init()

◆ hash_key()

◆ hash_move_init()

◆ hash_new()

◆ hash_print()

◆ hash_replace()

◆ hash_reset()

◆ hash_set()

◆ hash_store()

◆ hash_update()

◆ writeable_level()

Variable Documentation

◆ HASH_DATA_INIT

◆ hash_move

◆ hash_rank