10feb2003 - Release notes ChessPartner book optimizer.

With this utility it is possible to optimize ChessPartner .BK books such that the access time is minimized. The .BK book are already quite fast but this make them even faster.
This can be on intrest in very fast time controls, also it may be beneficial to optimize large books.

To understand how it works first some background on the internal workings of the ChessPartner .BK format.

The format is based on storing positions, togheter with each position the possible moves in that position are stored. The file is further divided in records of a fixed length. Next step, the records are organised in chains. All the positions in a chains share a part of the positions hash signature. The records of a chain may be spread across the file.
The first record of each chain is stored in the hash index table. This is a table of a fixed size which is always resident in memory. The size of this table determines the number chains there are.
To look up a position, first a part of the hash signature is taken to look up the first record of the chain in the hash index table. Then the chain is read record by record to search for the correct position.
Now a few things affect the performance, most important factor is the average length of each chain, the more records in a chain the longer it takes to eighter find the position or to know the position does not exist.
How can we affect the length of each chain, thats easy, the bigger the hash index table is, the more chains there are and thus the shorter each chain is. There is a downsite, having more chains means there are most likely more records which are not fully filled, thus wasting diskspace.

Back to the bookoptimizer, with this utility it is possible to alter the record size and also the size of the hash index table. The bookoptimizer does not alter the original file but makes a copy of it, during the copy process all the record in a chain are nicely ordered adjacent in the file, this may also give some speedup.

To use the utility, open a command prompt, the usage is as follows:

bookoptimize [options] inbook [outbook]

Options:"
	-rn - record size, n=512, 1024, 2048 etc.  default=from input.
	-kn - hash index size n= 128,256,1024,2048 etc.  default=from input.
	-a  - Only analyze the inbook file.

The default books have a record size of 1024, it is generally not neccessary to change this.
The hash index size has a default of 256, depending on the size of the book a value of 2048 may be a better value.
To get a recommendation you can run with the -a option, this will give you information on the book a possible a recommendation to alter the hash index size.

Sample output:

BOOKOPTIMIZE -a rebel.bk

ChessPartner book optimizer 1.0
Copyright (C) 2001, Lokasoft
Input book: rebel.bk
Type:			With statistics
Revision:		30
Comment:		Rebel main book
Hash index size:	256
Record size:		1024
# of records:		6800
Total positions:	276759
Total moves:		317791
Attributes:		1
Avg chain length:	26.6
Longest chain:		29
Shortest chain:		24
The longest chain is too big, it is recommended to increase the hash index size.
Recommended hash index size is: 2048

After optimizing it with this command:

BOOKOPTIMIZE -k2048 rebel.bk test.bk

BOOKOPTIMIZE -a test.bk

gives the following output:

ChessPartner book optimizer 1.0
Copyright (C) 2001, Lokasoft
Input book: test.bk
Type:			With statistics
Revision:		30
Comment:		Rebel main book
Hash index size:	2048
Record size:		1024
# of records:		7817
Total positions:	276759
Total moves:		317791
Attributes:		0
Avg chain length:	3.8
Longest chain:		5
Shortest chain:		3


What thus this tell us, whithout optimizing in the worst case 29 disk reads are needed to determine a position is not in the book. Compare this with the optimized case where the worst case is 5 disk reads.
Another thing to observe is the file size, the size of the unoptimize file is 6800 kb, optimized this is 7817 kb an increase of 15%


DISCLAIMER OF WARRANTY
----------------------
THIS SOFTWARE AND THE ACCOMPANYING FILES ARE PROVIDED "AS IS" AND WITHOUT WARRANTIES OF ANY KIND WHETHER EXPRESSED OR IMPLIED.

In no event shall the author be held liable for any damages whatsoever, including without limitation, damages for loss of business profits, business interruption, loss of business information, or any other loss arising from the use or inability to use the software.

Good data processing procedure dictates that any program be thoroughly tested with non-critical data before relying on it. The user must assume the entire risk of using the program.  ANY LIABILITY OF THE SELLER WILL BE LIMITED EXCLUSIVELY TO PRODUCT REPLACEMENT OR REFUND OF PURCHASE PRICE.


support@lokasoft.nl
http://www.lokasoft.nl

Copyright (C) 2000-2003, Lokasoft