question about opening book and learning

[Uri Blass]

Geschrieben von: / Posted by: Uri Blass at 26 April 2002 13:25:56:
I try to implement book and learning in my program.
The target of the learning is simply to change the choice of the first move
in every game(I may change it later to change the choice of the first move only after a loss or a draw).
The program has a textfile of 2 chars when the first char tells it the first move with white and the second char tells it the first move with black.
The program always learn to change the first move with white from e4 to d4 and in the next game again to e4
The program also always change the first move with black from 1...Nf6 to 1...Nc6 and back to 1...Nf6 with the exception that it does not choose
1...Nc6 against 1.d4 and prefers 1...d6(I could choose 1...d5 but I do not like the fact that after 1.d4 d5 2.c4 my program plays dxc4 and tries to defend the pawn).
Here is the relevant part of my program.
I am interested in ideas how to build better opening book(I know that there are a lot of free programs but I know that there are a lot of files in them and the main reason that I almost did not look at other programs except tscp is the fact that I did not know which file to look first).
If there is a simple program that only use book(it does not have to be a chess program and it can be in every thinking game) then I am interested to know about it.

char c;
int fh;
char buffer[] = "ee";
unsigned numwrite;
FILE *in;
for (;;)
{

if (side == computer_side)
{
if (hply

[Sune Fischer]

Geschrieben von: / Posted by: Sune Fischer at 26 April 2002 14:39:50:
Als Antwort auf: / As an answer to: question about opening book and learning geschrieben von: / posted by: Uri Blass at 26 April 2002 13:25:56:

I try to implement book and learning in my program.
The target of the learning is simply to change the choice of the first move
in every game(I may change it later to change the choice of the first move only after a loss or a draw).
The program has a textfile of 2 chars when the first char tells it the first move with white and the second char tells it the first move with black.
The program always learn to change the first move with white from e4 to d4 and in the next game again to e4
The program also always change the first move with black from 1...Nf6 to 1...Nc6 and back to 1...Nf6 with the exception that it does not choose
1...Nc6 against 1.d4 and prefers 1...d6(I could choose 1...d5 but I do not like the fact that after 1.d4 d5 2.c4 my program plays dxc4 and tries to defend the pawn).
Here is the relevant part of my program.
I am interested in ideas how to build better opening book(I know that there are a lot of free programs but I know that there are a lot of files in them and the main reason that I almost did not look at other programs except tscp is the fact that I did not know which file to look first).

If it is just the opening move, it is easier to just put these few moves into a small array and then pick one by random.


My book is not very advanced, no statistics no transpositions of any kind (it can't get back into the book once out).
I use notation such as this:
d2d3e7e5 g2g3d7d5 g1f3b8c6 f1g2g8f6 e1g1f8e7 c2c4d5c4
d2d3e7e6 b1d2d7d5 e2e4g8f6 g1f3c7c5 g2g3b8c6 f1g2f8e7
d2d3g7g6 g2g3f8g7 f1g2d7d5 g1f3e7e5 e1g1g8e7 b1d2e8g8
d2d3g7g6 g2g3f8g7 f1g2d7d5 g1f3g8f6 e1g1c7c5 c2c4e8g8
d2d3g8f6 g1f3d7d5 g2g3c7c5 f1g2b8c6 e1g1e7e6 c2c4f8e7
d2d4b7b5 g1f3c8b7 e2e3a7a6 a2a4b5b4 c2c4g8f6 f1d3g7g6
d2d4b8c6 e2e4e7e5 g1f3e5d4 f3d4d8f6 d4b5f8c5 d1e2c5b6
d2d4b8c6 f2f4d7d5 e2e3g8f6 f1d3c6b4 d3e2c8f5 b1a3e7e6
(the empty space infront is needed)
The code to read it is fairly simple, it builds a streng out of the moves that has been played so far, and then checks if that string matches anyone of the lines in the book. If it finds more than one matching line, it will pick one random of those that were valid. It will then read the next move from the line and check if there is a legal move in that position that matches (there should be or else the book is corrupt, and returns the legal move that matches the move from the book.
Here is the code, you will have to make guesses at what some of the stuff mean, but I think it is not impossible, or else you can ask away.

/*-------------------------------------------------\
| This reads an opening book in the format *.sff, |
| sff is short for "Simple Frenzee Format". |
\-------------------------------------------------*/
MOVE ReadBook(BOARD b)
{
FILE *stream_book;
int linenr[50000];
char linein[2000];
char variation[2000];
int count=0;
int picknumber;
int linecount=0;
unsigned int xb,yb,xe,ye;
int i;
int n;
// init and open book
stream_book=fopen(BookFile,"r");
if (stream_book==NULL)
{
UseBook=false;
sOutput("No book found");
return(BLANKMOVE);
}
memset(linenr,0, 50000*sizeof(int));
memset(linein,'\0', 2000*sizeof(char));
memset(variation,'\0',2000*sizeof(char));
// build variation string:
n=0;
for (i=1;istrlen(variation)+2)
{
count++;
linenr[count]=linecount;
}
memset(linein,'\0',2000*sizeof(char));
}
fprintf(Stream,"active lines in book: %d\n",count);

// check for out of book:
if (count==0)
{
UseBook=false;
fprintf(Stream,"Out of book moves...\n");
fclose(stream_book);
return(BLANKMOVE);
}
// pick a number (variant):
picknumber=(rand()%count)+1;
fprintf(Stream,"picknumber: %d\n",picknumber);
// get the line:
linecount=0;
fseek( stream_book, 0, SEEK_SET );
while (!feof(stream_book)) {
fgets(linein,500,stream_book);
linecount++;
if (linecount==linenr[picknumber])
break;
}
fprintf(Stream,"line %d: %s",linenr[picknumber],linein);

// extract the move from the string:
if (Tree.ply_official%2==0) n=1;
else n=0;
xb = Char2( linein[strlen(variation)+0+n] );
yb = Char2( linein[strlen(variation)+1+n] );
xe = Char2( linein[strlen(variation)+2+n] );
ye = Char2( linein[strlen(variation)+3+n] );
xb = XYcombSQ[xb][yb];
xe = XYcombSQ[xe][ye];
fclose(stream_book);
// return the move:
for (i=0;i

[Sune Fischer]

Geschrieben von: / Posted by: Sune Fischer at 26 April 2002 14:52:22:
Als Antwort auf: / As an answer to: Re: question about opening book and learning geschrieben von: / posted by: Sune Fischer at 26 April 2002 14:39:50:
And that became pretty much unreadable,
I can send you the file and book if you are interested.
-S.

[Omid David]

Geschrieben von: / Posted by: Omid David at 26 April 2002 18:35:54:
Als Antwort auf: / As an answer to: question about opening book and learning geschrieben von: / posted by: Uri Blass at 26 April 2002 13:25:56:
First of all don't bother to check the file, just convert it to string and then work on the string. You can use the function file2string(filename) which I've created and can be downloaded at www.upload co.il
The basic way I've implemented the book is the following:
for example if we see in part of the book file the following:
1. e2e4 e7e5
2. g1f3 b8c6
it checks through the move history to verify that we have played the same moves till a point, then it gets the next move, for example b8c6, checks legality and if legal, it's added to the list of options that can be played.


Omid's Computer Chess Website

[Dieter Bürßner]

Geschrieben von: / Posted by: Dieter Bürßner at 26 April 2002 20:07:34:
Als Antwort auf: / As an answer to: question about opening book and learning geschrieben von: / posted by: Uri Blass at 26 April 2002 13:25:56:

I am interested in ideas how to build better opening book(I know that there are a lot of free programs but I know that there are a lot of files in them and the main reason that I almost did not look at other programs except tscp is the fact that I did not know which file to look first).

There are basically 2 different commonly used approaches. One is to store a game tree, and one is to store positions (together with bookmove(s)). The second approach has in my opinion the big advantage (especially when you want to write a hand tuned book), that it handles transpositions naturally. Because I use the second approach, I can elaborate a bit more on this. For the tree approach, you should find ideas in many computer science books. Often trees are described with pointes, but because the opening book will be on disk, you will use file offsets instead of pointes.
Yace gives every position it finds during book creation a hash key. Even if you don't have hash yet, you can easily create one yourself, by just traversing the board.
hashkey = 0
for all squares
if not empty
hashkey ^= random_array[piece on square][color of piece][square]
and also
hashkey ^= some_other_random_array[castling_rights];
and same with side to move and ep square.
Now a book entry might look like
struct bookentry
{
hashkey_t hk;
MOVE book_move;
unsigned long flags; /* or anything you find worthful. for me flags are for exampe !, !!, ?, etc. */
unsigned long count; /* in how many games was this played, many more statistic fields could be included */
/* And whatever else you find useful */
unsigned long offset_to_next_pos_with_same_hash_index;
}
I reserve space for (say) 100000 such structs. When looking up a board position in the book, use the hashkey%100000, to find the index of the struct. Then see if the entry is used. If yes, compare the whole hashkey. If they are the same, you have one book move. Then follow the offset_to_... which is basically a pointer to the next entry, so the whole thing is a linked list. Traverse this linked list, until no next position is found (which may be indicated by an offset of 0), and collect book moves and statistics while doing this.
Other methods, may instead of the linked list, sort the whole thing, and do a binary search.
I think, how to create such a book should be clear. It is basically, building the (in my example) 100000 linked lists. I think, it is conceptionally not difficult, but it is some programming work.
One easy approach to learning could be, to change the flags (or some other field) of the struct for the last book move in the game, that had no alternative in the book, if the game was lost. If it was won, you could do something similar. If you ask Robert Hyatt, he will probably send you his ICCA article about book learning.

Some (very offtopic) comments to your code. I think, it is a bad idea to use the Unxish open/read/write/... type of functions. They are not defined in Standard C, and there is absolutely no need for them for this task. So, why compromise portability here? Using the Standard C functions would even be easier. You can fopen a file for read and write (you want probably use binary mode as well). You can use fseek to go back to the beginning of the file (or any other point), and overwrite as you like. The following example may show it.
The first time you run the program, it should print 0, and then 1,2,...,10,0,1..., which is in essence very similar, to what you were doing. Not much error checking however ...
#include
int main(void)
{
int c;
FILE *fp = fopen("d.d", "r+b");
if (!fp) /* Probably not existing yet */
fp = fopen("d.d", "w+b");
if (fp)
{
if ((c=fgetc(fp)) == EOF)
c = 0;
printf("c=%d\n", c);
c++;
if (c > 10)
c = 0;
printf("updating to %d\n", c);
fseek(fp, 0, SEEK_SET); /* Go back to the start of the file */
fputc(c,fp);
fclose(fp);
}
return 0;
}
Regards,
Dieter

[Volker Pittlik]

Geschrieben von: / Posted by: Volker Pittlik at 26 April 2002 20:45:28:
Als Antwort auf: / As an answer to: Re: question about opening book and learning geschrieben von: / posted by: Dieter Bürßner at 26 April 2002 20:07:34:
...

#include < stdio.h>

For this reason.
Volker