Classes | Macros | Typedefs | Functions | Variables
book.c File Reference
#include "book.h"
#include "base.h"
#include "search.h"
#include "const.h"
#include "bit.h"
#include "options.h"
#include "util.h"
#include <assert.h>
#include <time.h>
#include <stdarg.h>
#include <limits.h>

Classes

struct  PositionArray
 An array with positions. More...
 
struct  BookCheckGame
 

Macros

#define BOOK_DEBUG   0
 
#define clear_line()   bprint(" \r")
 
#define foreach_link(l, p)   for ((l) = (p)->link; (l) < (p)->link + (p)->n_link; ++(l))
 
#define foreach_position(p, a, b)
 

Typedefs

typedef struct PositionArray PositionArray
 An array with positions. More...
 
typedef struct BookCheckGame BookCheckGame
 

Functions

static void bprint (const char *format,...)
 print a message on stdout. More...
 
static bool link_read (Link *link, FILE *f)
 read a link. More...
 
static bool link_write (const Link *link, FILE *f)
 write a link. More...
 
static bool link_is_bad (const Link *link)
 check if a link is unvalid. More...
 
static Positionbook_probe (const Book *book, const Board *board)
 Find a position in the book. More...
 
static void book_add (Book *book, const Position *p)
 Add a position to the book. More...
 
static void position_print (const Position *position, const Board *board, FILE *f)
 print a position in a compact but readable format. More...
 
static int get_book_depth (const int depth)
 return the number of plies from where the search is solving. More...
 
static bool position_is_ok (const Position *position)
 Check if position is ok or need fixing. More...
 
static void position_init (Position *position)
 Initialize a position. More...
 
static void position_merge (Position *dest, const Position *src)
 Merge a position with another one. More...
 
static void position_free (Position *position)
 Free resources used by a position. More...
 
static bool position_read (Position *position, FILE *f)
 Read a position. More...
 
static bool position_import (Position *position, FILE *f)
 Read a position. More...
 
static bool position_write (const Position *position, FILE *f)
 Write a position. More...
 
static bool position_export (const Position *p, FILE *f)
 write a position. More...
 
static void position_unique (Position *position)
 Make position unique, regarding symetries. More...
 
static int position_get_moves (const Position *position, const Board *board, MoveList *movelist)
 Get moves from a position. More...
 
static void position_show (const Position *position, const Board *board, FILE *f)
 print a position in a readable format. More...
 
static void position_get_random_move (const Position *position, const Board *board, Move *move, Random *r, const int randomness)
 Chose a move at random from the position. More...
 
static bool position_add_link (Position *position, const Link *link)
 Add a link to this position. More...
 
static void position_sort (Position *position)
 Sort the link moves. More...
 
static void position_search (Position *position, Book *book)
 Evaluate a position. More...
 
static void position_link (Position *position, Book *book)
 Link a position. More...
 
static void position_expand (Position *position, Book *book)
 Expand a position. More...
 
static int position_negamax (Position *position, Book *book)
 Negamax a position. More...
 
static void position_prune (Position *position, Book *book, const int player_deviation, const int opponent_deviation, const int lower, const int upper)
 Prune a position. More...
 
static void position_remove_links (Position *position, Book *book)
 Remove bad links after book pruning. More...
 
static void position_deviate (Position *position, Book *book, const int player_deviation, const int opponent_deviation, const int lower, const int upper)
 Deviate a position. More...
 
static void position_enhance (Position *position, Book *book)
 Enhance a position. More...
 
static void board_feed_hash (Board *board, const Book *book, Search *search, const bool is_pv)
 Feed hash from a position. More...
 
static bool board_fill (Board *board, Book *book, int depth)
 Fill the opening book. More...
 
static void position_fix (Position *position, Book *book)
 Fix a position. More...
 
static void position_array_init (PositionArray *a)
 Initialize the array. More...
 
static bool position_array_add (PositionArray *a, const Position *p)
 Add a position to the array. More...
 
static bool position_array_remove (PositionArray *a, const Position *p)
 Remove a position from an array. More...
 
static void position_array_free (PositionArray *a)
 Free resources used by a position array. More...
 
static Positionposition_array_probe (PositionArray *a, const Board *board)
 Find a position in the array. More...
 
static void book_set_date (Book *book)
 Set book date. More...
 
static double book_get_age (Book *book)
 Get book age, in seconds. More...
 
static void book_remove (Book *book, const Position *p)
 Remove a position from the book. More...
 
static void book_clean (Book *book)
 Set all positions as undone. More...
 
static Positionbook_root (Book *book)
 Find the initial position in the book. More...
 
void book_init (Book *book)
 Initialize the opening book. More...
 
void book_free (Book *book)
 Free resources used by the opening book. More...
 
void book_new (Book *book, int level, int n_empties)
 Create a new opening book. More...
 
void book_load (Book *book, const char *file)
 Load the opening book. More...
 
void book_import (Book *book, const char *file)
 Import an opening book. More...
 
void book_export (Book *book, const char *file)
 Export an opening book. More...
 
void book_save (Book *book, const char *file)
 Save an opening book. More...
 
void book_merge (Book *dest, const Book *src)
 Merge two opening books. More...
 
void book_negamax (Book *book)
 Negamax a book. More...
 
void book_link (Book *book)
 Link a book. More...
 
void book_fix (Book *book)
 Fix a book. More...
 
void book_deepen (Book *book)
 Deepen a book. More...
 
void book_correct_solved (Book *book)
 Correct wrong solved score in the book. More...
 
static void book_expand (Book *book, const char *action, const char *tmp_file)
 Expand a book. More...
 
void book_sort (Book *book)
 Sort a book. More...
 
void book_play (Book *book)
 Play. More...
 
void book_fill (Book *book, const int depth)
 Fill a book. More...
 
void book_deviate (Book *book, Board *board, const int relative_error, const int absolute_error)
 Deviate a book. More...
 
void book_prune (Book *book)
 Prune a book. More...
 
void book_subtree (Book *book, const Board *board)
 Prune a book. More...
 
void book_enhance (Book *book, Board *board, const int midgame_error, const int endcut_error)
 Enhance a book. More...
 
void book_info (Book *book)
 display some book's informations. More...
 
void book_show (Book *book, Board *board)
 Display a position from the book. More...
 
bool book_get_moves (Book *book, const Board *board, MoveList *movelist)
 Get a list of moves from the book. More...
 
void book_get_line (Book *book, const Board *board, const Move *move, Line *line)
 Get a variation from the book. More...
 
bool book_get_random_move (Book *book, const Board *board, Move *move, const int randomness)
 Get a move at random from the opening book. More...
 
void book_get_game_stats (Book *book, const Board *board, GameStats *stat)
 Get game statistics from a position. More...
 
void book_add_board (Book *book, const Board *board)
 Add a position. More...
 
void book_add_game (Book *book, const Game *game)
 Add positions from a game. More...
 
void book_add_base (Book *book, const Base *base)
 Add positions from a game database. More...
 
void book_check_game (Book *book, MoveHash *hash, const Game *game, BookCheckGame *stat)
 Check positions from a game. More...
 
void book_check_base (Book *book, const Base *base)
 Check positions from a game database. More...
 
static void extract_skeleton (Book *book, Board *board, Line *pv, Base *base)
 Extract book lines to a game base. More...
 
void book_extract_skeleton (Book *book, Base *base)
 Extract book draws to a game base. More...
 
void book_extract_positions (Book *book, const int n_empties, const int n_positions)
 print a set of position. More...
 
void book_stats (Book *book)
 print book statistics. More...
 
void book_feed_hash (const Book *book, Board *board, Search *search)
 feed hash table from the opening book. More...
 

Variables

static const int BOOK_INFO_RESOLUTION = 100000
 
bool book_verbose = false
 
const Link BAD_LINK = {-SCORE_INF, NOMOVE}
 

Detailed Description

File for opening book management.

Edax book is a set of positions. Each position is unique concerning all possible symetries. A position is made of an othello board, a set of moves leading to other positions in the book, called here "link", and the best remaining move, as evaluated by a search at fixed depth, called here leaf. It also contains win/draw/loss statistics, which is actually useless, and a score with two bounds from retropropagated error. Several algorithms are present to add positions in the book, in the most usefull way.

Date
1998 - 2017
Author
Richard Delorme
Version
4.4

Macro Definition Documentation

◆ BOOK_DEBUG

#define BOOK_DEBUG   0

◆ clear_line

#define clear_line ( )    bprint(" \r")

◆ foreach_link

#define foreach_link (   l,
 
)    for ((l) = (p)->link; (l) < (p)->link + (p)->n_link; ++(l))

◆ foreach_position

#define foreach_position (   p,
  a,
 
)
Value:
for (a = b->array; a < b->array + b->n; ++a) \
for (p = a->positions; p < a->positions + a->n; ++p)

Typedef Documentation

◆ BookCheckGame

typedef struct BookCheckGame BookCheckGame

◆ PositionArray

typedef struct PositionArray PositionArray

An array with positions.

Function Documentation

◆ board_feed_hash()

static void board_feed_hash ( Board board,
const Book book,
Search search,
const bool  is_pv 
)
static

Feed hash from a position.

Go through the book sub-tree following the current position & feed the hash table from this position.

Parameters
boardPosition to expand.
bookOpening book.
searchHashtables container.
is_pvFlag to tell if the position is from the principal variation.

◆ board_fill()

static bool board_fill ( Board board,
Book book,
int  depth 
)
static

Fill the opening book.

Add positions to link existing positions.

Parameters
boardCandidate position.
bookOpening book.
depthDepth at which to search a link.
Returns
true if the board is in the book, possibly just after having been added to it.

◆ book_add()

static void book_add ( Book book,
const Position p 
)
static

Add a position to the book.

Parameters
bookOpening book.
pPosition to add.

◆ book_add_base()

void book_add_base ( Book book,
const Base base 
)

Add positions from a game database.

Parameters
bookopening book.
basegames to add.

◆ book_add_board()

void book_add_board ( Book book,
const Board board 
)

Add a position.

Parameters
bookopening book.
boardposition to add.

◆ book_add_game()

void book_add_game ( Book book,
const Game game 
)

Add positions from a game.

Parameters
bookopening book.
gamegame to add.

◆ book_check_base()

void book_check_base ( Book book,
const Base base 
)

Check positions from a game database.

Parameters
bookopening book.
basegames to add.

◆ book_check_game()

void book_check_game ( Book book,
MoveHash hash,
const Game game,
BookCheckGame stat 
)

Check positions from a game.

Parameters
bookopening book.
hashBoard + Move hash table.
gamegame to check.
statCount statistics.

◆ book_clean()

static void book_clean ( Book book)
static

Set all positions as undone.

Parameters
bookOpening book.

◆ book_correct_solved()

void book_correct_solved ( Book book)

Correct wrong solved score in the book.

Correct erroneous solved positions. Edax may be unstable and introduce bugs from time to time...

Parameters
bookopening book.

◆ book_deepen()

void book_deepen ( Book book)

Deepen a book.

Research all non link best move.

Parameters
bookopening book.

◆ book_deviate()

void book_deviate ( Book book,
Board board,
const int  relative_error,
const int  absolute_error 
)

Deviate a book.

Parameters
bookopening book.
boardPosition to start from.
relative_errorError relative to the current position's score.
absolute_errorError relative to the root position's score.

◆ book_enhance()

void book_enhance ( Book book,
Board board,
const int  midgame_error,
const int  endcut_error 
)

Enhance a book.

Parameters
bookopening book.
boardPosition to start from.
midgame_errorError in midgame search.
endcut_errorError in endgame search.

◆ book_expand()

static void book_expand ( Book book,
const char *  action,
const char *  tmp_file 
)
static

Expand a book.

Research all non link best move.

Parameters
bookopening book.
actionString with a description of current action.
tmp_fileTemporary file name.

◆ book_export()

void book_export ( Book book,
const char *  file 
)

Export an opening book.

Save the book in a portable text format.

Parameters
bookOpening book.
fileFile name.

◆ book_extract_positions()

void book_extract_positions ( Book book,
const int  n_empties,
const int  n_positions 
)

print a set of position.

Parameters
bookOpening book.
n_emptiesGame stage.
n_positionsNumber of positions to extract.

◆ book_extract_skeleton()

void book_extract_skeleton ( Book book,
Base base 
)

Extract book draws to a game base.

This function supposes that f5d6c4 & f5f6e6f4 are draws and the only draws, excluding the transpositions f5d6c3d3c4 & f5f6e6c6 & c4..., d3..., e6...

Parameters
bookOpening book.
basegame database.

◆ book_feed_hash()

void book_feed_hash ( const Book book,
Board board,
Search search 
)

feed hash table from the opening book.

Parameters
bookOpening book.
boardPosition to start from.
searchHashTables container.

◆ book_fill()

void book_fill ( Book book,
const int  depth 
)

Fill a book.

Parameters
bookopening book.
depthDistance to fill between two positions.

◆ book_fix()

void book_fix ( Book book)

Fix a book.

Parameters
bookopening book.

◆ book_free()

void book_free ( Book book)

Free resources used by the opening book.

Parameters
bookOpening book.

◆ book_get_age()

static double book_get_age ( Book book)
static

Get book age, in seconds.

Parameters
bookOpening book.
Returns
book age.

◆ book_get_game_stats()

void book_get_game_stats ( Book book,
const Board board,
GameStats stat 
)

Get game statistics from a position.

Parameters
bookOpening book.
boardPosition to find a move from.
statGame statistics output.

◆ book_get_line()

void book_get_line ( Book book,
const Board board,
const Move move,
Line line 
)

Get a variation from the book.

Parameters
bookOpening book.
boardPosition.
moveFirst move;
lineBariation.

◆ book_get_moves()

bool book_get_moves ( Book book,
const Board board,
MoveList movelist 
)

Get a list of moves from the book.

Parameters
bookOpening book.
boardPosition to display.
movelistList of moves.

◆ book_get_random_move()

bool book_get_random_move ( Book book,
const Board board,
Move move,
const int  randomness 
)

Get a move at random from the opening book.

Parameters
bookOpening book.
boardPosition to find a move from.
moveChosen move.
randomnessRandomness.

◆ book_import()

void book_import ( Book book,
const char *  file 
)

Import an opening book.

Read the opening book from a portable text format. After the book is imported, it is needed to relink & negamax it.

Parameters
bookOpening book.
fileFile name.

◆ book_info()

void book_info ( Book book)

display some book's informations.

Parameters
bookopening book.

◆ book_init()

void book_init ( Book book)

Initialize the opening book.

Create an empty opening book.

Parameters
bookOpening book.

◆ book_link()

void book_link ( Book book)

Link a book.

Parameters
bookopening book.

◆ book_load()

void book_load ( Book book,
const char *  file 
)

Load the opening book.

Parameters
bookOpening book.
fileFile name.

◆ book_merge()

void book_merge ( Book dest,
const Book src 
)

Merge two opening books.

It is needed to relink & negamax the destination book after merging.

Parameters
destDestination opening book.
srcSource opening book.

◆ book_negamax()

void book_negamax ( Book book)

Negamax a book.

Parameters
bookopening book.

◆ book_new()

void book_new ( Book book,
int  level,
int  n_empties 
)

Create a new opening book.

Create an opening book with the initial position & a single non link move.

Parameters
bookOpening book.
levelsearch level to evaluate positions.
n_emptiesnumber of empty positions up to which to evaluate positions.

◆ book_play()

void book_play ( Book book)

Play.

Add positions to the opening book by adding links to position with no links.

Parameters
bookopening book.

◆ book_probe()

static Position * book_probe ( const Book book,
const Board board 
)
static

Find a position in the book.

Parameters
bookOpening book.
boardBoard to find in the array.
Returns
a position containg the board (or a symetry) or NULL is no position is found.

◆ book_prune()

void book_prune ( Book book)

Prune a book.

Remove positions Edax cannot reach.

Parameters
bookopening book.

◆ book_remove()

static void book_remove ( Book book,
const Position p 
)
static

Remove a position from the book.

Parameters
bookOpening book.
pPosition to add.

◆ book_root()

static Position* book_root ( Book book)
static

Find the initial position in the book.

Attention: when a position is added to the book, the pointer returned by this position may be wrong. If the root position is updated the contents of the pointed structure may be wrong. So it is needed to recall this function each time as necessary.

Parameters
bookOpening book.
Returns
the inital position.

◆ book_save()

void book_save ( Book book,
const char *  file 
)

Save an opening book.

Save the book in a fast binary format.

Parameters
bookOpening book.
fileFile name.

◆ book_set_date()

static void book_set_date ( Book book)
static

Set book date.

Parameters
bookOpening book.

◆ book_show()

void book_show ( Book book,
Board board 
)

Display a position from the book.

Parameters
bookopening book.
boardposition to display.

◆ book_sort()

void book_sort ( Book book)

Sort a book.

Parameters
bookopening book.

◆ book_stats()

void book_stats ( Book book)

print book statistics.

Parameters
bookOpening book.

◆ book_subtree()

void book_subtree ( Book book,
const Board board 
)

Prune a book.

Remove positions Edax cannot reach.

Parameters
bookopening book.

◆ bprint()

static void bprint ( const char *  format,
  ... 
)
static

print a message on stdout.

Parameters
formatFormat string.
...variable arguments.

◆ extract_skeleton()

static void extract_skeleton ( Book book,
Board board,
Line pv,
Base base 
)
static

Extract book lines to a game base.

Recursively add move to a PV until no move are available, where we dump the PV to a game data base.

Parameters
bookOpening book.
boardStarting position.
pvPrevious moves leading to the starting position.
basegame database.

◆ get_book_depth()

static int get_book_depth ( const int  depth)
static

return the number of plies from where the search is solving.

Parameters
depthsearch depth.
Returns
book depth.

◆ link_is_bad()

static bool link_is_bad ( const Link link)
inlinestatic

check if a link is unvalid.

Parameters
linkchecked link.
Returns
true if link is unvalid, false otherwise.

◆ link_read()

static bool link_read ( Link link,
FILE *  f 
)
inlinestatic

read a link.

Parameters
linklink to read in.
finput stream.

◆ link_write()

static bool link_write ( const Link link,
FILE *  f 
)
inlinestatic

write a link.

Parameters
linklink to write out.
foutput stream.

◆ position_add_link()

static bool position_add_link ( Position position,
const Link link 
)
static

Add a link to this position.

Parameters
positionPosition to chose a move from.
linkLink to add.
Returns
true if the link has been added, false if it was already present.

◆ position_array_add()

static bool position_array_add ( PositionArray a,
const Position p 
)
static

Add a position to the array.

Parameters
aPositions' array.
pPosition to add.
Returns
true in case of success.

◆ position_array_free()

static void position_array_free ( PositionArray a)
static

Free resources used by a position array.

Parameters
aPositions' array.

◆ position_array_init()

static void position_array_init ( PositionArray a)
static

Initialize the array.

Parameters
aPositions' array.

◆ position_array_probe()

static Position* position_array_probe ( PositionArray a,
const Board board 
)
static

Find a position in the array.

Parameters
aPositions' array.
boardBoard to find in the array.
Returns
a position containg the board (or a symetry) or NULL is no position is found.

◆ position_array_remove()

static bool position_array_remove ( PositionArray a,
const Position p 
)
static

Remove a position from an array.

Parameters
aPositions' array.
pPosition to add.
Returns
true in case of success.

◆ position_deviate()

static void position_deviate ( Position position,
Book book,
const int  player_deviation,
const int  opponent_deviation,
const int  lower,
const int  upper 
)
static

Deviate a position.

This is the important part of the opening book code, where it finds the best moves to add to the book. Considering the current position, it will deviate a child position or expand a move if:

  • move_score < best_score - player_deviation
  • lower <= move_score <= upper. So a good candidate move for expansion need to have a score close to the best move, and not too far from the root score from where we deviates, in order to not derive to very bad positions.
Parameters
positionPosition to expand.
bookOpening book.
player_deviationPlayer's error.
opponent_deviationOpponent's error.
lowerError lower bound.
upperError upper bound.

◆ position_enhance()

static void position_enhance ( Position position,
Book book 
)
static

Enhance a position.

This is the other important part of the opening book code, where it finds the best moves to add to the book by another methods. Here we use score negamaxed bounds to decide if a move is a good candidate for further enhancement or for expansion. The purpose of this algorithm is to find more moves.

Parameters
positionPosition to expand.
bookOpening book.

◆ position_expand()

static void position_expand ( Position position,
Book book 
)
static

Expand a position.

Expand the best yet unlink move. This will add a new position to the book. Two new moves will also be analyzed, one for the new position, the other for the actual position as a new best unlink move.

Parameters
positionPosition to expand.
bookOpening book.

◆ position_export()

static bool position_export ( const Position p,
FILE *  f 
)
static

write a position.

Parameters
pposition to write out.
foutput stream.

◆ position_fix()

static void position_fix ( Position position,
Book book 
)
static

Fix a position.

Recompute all elements of a buggy position

Parameters
positionPosition to fix.
bookOpening book.

◆ position_free()

static void position_free ( Position position)
static

Free resources used by a position.

Parameters
positionPosition.

◆ position_get_moves()

static int position_get_moves ( const Position position,
const Board board,
MoveList movelist 
)
static

Get moves from a position.

Parameters
positionposition to get moves from.
boardboard.
movelistmovelist.

◆ position_get_random_move()

static void position_get_random_move ( const Position position,
const Board board,
Move move,
Random r,
const int  randomness 
)
static

Chose a move at random from the position.

Parameters
positionPosition to chose a move from.
boardCorrectly rotated/mirrored board.
moveChosen move.
rRandom data.
randomnessRandomness intensity (randomness = 0 means no randomness).

◆ position_import()

static bool position_import ( Position position,
FILE *  f 
)
static

Read a position.

Parameters
positionPosition to read in.
fInput stream.

◆ position_init()

static void position_init ( Position position)
static

Initialize a position.

Parameters
positionPosition.

◆ position_is_ok()

static bool position_is_ok ( const Position position)
static

Check if position is ok or need fixing.

Note: All positions should always be OK! A wrong position means a BUG!

Parameters
positionPosition.
Returns
true if ok, false if it needs fixing.

◆ position_link()

static void position_link ( Position position,
Book book 
)
static

Link a position.

Find moves that lead to other positions in the book.

Parameters
positionPosition to link.
bookOpening book.

◆ position_merge()

static void position_merge ( Position dest,
const Position src 
)
static

Merge a position with another one.

A position is merged if its level is > to the destination position; or == and its leaf move is not contains into the destination link moves.

Note: link moves are not copied. This can be done later with position_link().

Parameters
destDestination position.
srcSource position.

◆ position_negamax()

static int position_negamax ( Position position,
Book book 
)
static

Negamax a position.

Go through the book sub-tree following the current position & negamax the best scores back to this position.

Parameters
positionPosition to expand.
bookOpening book.

◆ position_print()

static void position_print ( const Position position,
const Board board,
FILE *  f 
)
static

print a position in a compact but readable format.

Parameters
positionposition to print out.
boardSymetrical board to use.
foutput stream.

◆ position_prune()

static void position_prune ( Position position,
Book book,
const int  player_deviation,
const int  opponent_deviation,
const int  lower,
const int  upper 
)
static

Prune a position.

Parameters
positionPosition to prune.
bookOpening book.
player_deviationPlayer's error.
opponent_deviationOpponent's error.
lowerError lower bound.
upperError upper bound.

◆ position_read()

static bool position_read ( Position position,
FILE *  f 
)
static

Read a position.

Parameters
positionPosition to read in.
fInput stream.

◆ position_remove_links()

static void position_remove_links ( Position position,
Book book 
)
static

Remove bad links after book pruning.

Parameters
positionPosition to fix.
bookOpening book.

◆ position_search()

static void position_search ( Position position,
Book book 
)
static

Evaluate a position.

If needed, find the best remaining move, after link moves are excluded.

Parameters
positionPosition to search.
bookOpening book.

◆ position_show()

static void position_show ( const Position position,
const Board board,
FILE *  f 
)
static

print a position in a readable format.

Parameters
positionposition to print out.
boardSymetrical board to use.
foutput stream.

◆ position_sort()

static void position_sort ( Position position)
static

Sort the link moves.

Parameters
positionPosition to sort.

◆ position_unique()

static void position_unique ( Position position)
static

Make position unique, regarding symetries.

Parameters
positionposition.

◆ position_write()

static bool position_write ( const Position position,
FILE *  f 
)
static

Write a position.

Parameters
positionposition to write out.
foutput stream.

Variable Documentation

◆ BAD_LINK

const Link BAD_LINK = {-SCORE_INF, NOMOVE}

◆ BOOK_INFO_RESOLUTION

const int BOOK_INFO_RESOLUTION = 100000
static

◆ book_verbose

bool book_verbose = false