#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 Position * | book_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 Position * | position_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 Position * | book_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} |
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.
#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 | |||
) |
typedef struct BookCheckGame BookCheckGame |
typedef struct PositionArray PositionArray |
An array with positions.
|
static |
Feed hash from a position.
Go through the book sub-tree following the current position & feed the hash table from this position.
board | Position to expand. |
book | Opening book. |
search | Hashtables container. |
is_pv | Flag to tell if the position is from the principal variation. |
Fill the opening book.
Add positions to link existing positions.
board | Candidate position. |
book | Opening book. |
depth | Depth at which to search a link. |
Add a position to the book.
book | Opening book. |
p | Position to add. |
Add positions from a game database.
book | opening book. |
base | games to add. |
Add a position.
book | opening book. |
board | position to add. |
Add positions from a game.
book | opening book. |
game | game to add. |
Check positions from a game database.
book | opening book. |
base | games to add. |
void book_check_game | ( | Book * | book, |
MoveHash * | hash, | ||
const Game * | game, | ||
BookCheckGame * | stat | ||
) |
|
static |
Set all positions as undone.
book | Opening book. |
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...
book | opening book. |
void book_deepen | ( | Book * | book | ) |
Deepen a book.
Research all non link best move.
book | opening book. |
void book_deviate | ( | Book * | book, |
Board * | board, | ||
const int | relative_error, | ||
const int | absolute_error | ||
) |
Deviate a book.
book | opening book. |
board | Position to start from. |
relative_error | Error relative to the current position's score. |
absolute_error | Error relative to the root position's score. |
Enhance a book.
book | opening book. |
board | Position to start from. |
midgame_error | Error in midgame search. |
endcut_error | Error in endgame search. |
|
static |
Expand a book.
Research all non link best move.
book | opening book. |
action | String with a description of current action. |
tmp_file | Temporary file name. |
void book_export | ( | Book * | book, |
const char * | file | ||
) |
Export an opening book.
Save the book in a portable text format.
book | Opening book. |
file | File name. |
void book_extract_positions | ( | Book * | book, |
const int | n_empties, | ||
const int | n_positions | ||
) |
print a set of position.
book | Opening book. |
n_empties | Game stage. |
n_positions | Number of positions to extract. |
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...
book | Opening book. |
base | game database. |
feed hash table from the opening book.
book | Opening book. |
board | Position to start from. |
search | HashTables container. |
void book_fill | ( | Book * | book, |
const int | depth | ||
) |
Fill a book.
book | opening book. |
depth | Distance to fill between two positions. |
void book_fix | ( | Book * | book | ) |
Fix a book.
book | opening book. |
void book_free | ( | Book * | book | ) |
Free resources used by the opening book.
book | Opening book. |
|
static |
Get book age, in seconds.
book | Opening book. |
Get a variation from the book.
book | Opening book. |
board | Position. |
move | First move; |
line | Bariation. |
Get a list of moves from the book.
book | Opening book. |
board | Position to display. |
movelist | List of moves. |
Get a move at random from the opening book.
book | Opening book. |
board | Position to find a move from. |
move | Chosen move. |
randomness | Randomness. |
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.
book | Opening book. |
file | File name. |
void book_info | ( | Book * | book | ) |
display some book's informations.
book | opening book. |
void book_init | ( | Book * | book | ) |
Initialize the opening book.
Create an empty opening book.
book | Opening book. |
void book_load | ( | Book * | book, |
const char * | file | ||
) |
Load the opening book.
book | Opening book. |
file | File name. |
Merge two opening books.
It is needed to relink & negamax the destination book after merging.
dest | Destination opening book. |
src | Source opening book. |
void book_negamax | ( | Book * | book | ) |
Negamax a book.
book | opening book. |
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.
book | Opening book. |
level | search level to evaluate positions. |
n_empties | number of empty positions up to which to evaluate positions. |
void book_play | ( | Book * | book | ) |
Play.
Add positions to the opening book by adding links to position with no links.
book | opening book. |
Find a position in the book.
book | Opening book. |
board | Board to find in the array. |
void book_prune | ( | Book * | book | ) |
Prune a book.
Remove positions Edax cannot reach.
book | opening book. |
Remove a position from the book.
book | Opening book. |
p | Position to add. |
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.
book | Opening book. |
void book_save | ( | Book * | book, |
const char * | file | ||
) |
Save an opening book.
Save the book in a fast binary format.
book | Opening book. |
file | File name. |
|
static |
Set book date.
book | Opening book. |
Display a position from the book.
book | opening book. |
board | position to display. |
void book_sort | ( | Book * | book | ) |
Sort a book.
book | opening book. |
void book_stats | ( | Book * | book | ) |
print book statistics.
book | Opening book. |
Prune a book.
Remove positions Edax cannot reach.
book | opening book. |
|
static |
print a message on stdout.
format | Format string. |
... | variable arguments. |
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.
book | Opening book. |
board | Starting position. |
pv | Previous moves leading to the starting position. |
base | game database. |
|
static |
return the number of plies from where the search is solving.
depth | search depth. |
|
inlinestatic |
check if a link is unvalid.
link | checked link. |
|
inlinestatic |
read a link.
link | link to read in. |
f | input stream. |
|
inlinestatic |
write a link.
link | link to write out. |
f | output stream. |
|
static |
Add a position to the array.
a | Positions' array. |
p | Position to add. |
|
static |
Free resources used by a position array.
a | Positions' array. |
|
static |
Initialize the array.
a | Positions' array. |
|
static |
Find a position in the array.
a | Positions' array. |
board | Board to find in the array. |
|
static |
Remove a position from an array.
a | Positions' array. |
p | Position to add. |
|
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:
position | Position to expand. |
book | Opening book. |
player_deviation | Player's error. |
opponent_deviation | Opponent's error. |
lower | Error lower bound. |
upper | Error upper bound. |
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.
position | Position to expand. |
book | Opening book. |
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.
position | Position to expand. |
book | Opening book. |
|
static |
write a position.
p | position to write out. |
f | output stream. |
Fix a position.
Recompute all elements of a buggy position
position | Position to fix. |
book | Opening book. |
|
static |
Free resources used by a position.
position | Position. |
|
static |
Get moves from a position.
position | position to get moves from. |
board | board. |
movelist | movelist. |
|
static |
Read a position.
position | Position to read in. |
f | Input stream. |
|
static |
Initialize a position.
position | Position. |
|
static |
Check if position is ok or need fixing.
Note: All positions should always be OK! A wrong position means a BUG!
position | Position. |
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().
dest | Destination position. |
src | Source position. |
Negamax a position.
Go through the book sub-tree following the current position & negamax the best scores back to this position.
position | Position to expand. |
book | Opening book. |
print a position in a compact but readable format.
position | position to print out. |
board | Symetrical board to use. |
f | output stream. |
|
static |
Prune a position.
position | Position to prune. |
book | Opening book. |
player_deviation | Player's error. |
opponent_deviation | Opponent's error. |
lower | Error lower bound. |
upper | Error upper bound. |
|
static |
Read a position.
position | Position to read in. |
f | Input stream. |
Remove bad links after book pruning.
position | Position to fix. |
book | Opening book. |
Evaluate a position.
If needed, find the best remaining move, after link moves are excluded.
position | Position to search. |
book | Opening book. |
print a position in a readable format.
position | position to print out. |
board | Symetrical board to use. |
f | output stream. |
|
static |
Sort the link moves.
position | Position to sort. |
|
static |
Make position unique, regarding symetries.
position | position. |
|
static |
Write a position.
position | position to write out. |
f | output stream. |
|
static |
bool book_verbose = false |