Alessandro Scotti wrote:Hi Dieter,
I don't use a special indexing scheme because there's so much going on at the moment that I can't possibly manage another level of complexity. Code is designed so that it can be put in at a later time though.
At some time Kiwi sources will be released under the GPL and I can't use EGTB probing code, so I must score positions (a la Heinz) and also embed my own bitbases in the engine, or at least make them as small a download as possible. That's why I'm interested in compression.
The method I'm using now is performing reasonably well in practice, but requires some work to be done for each bitbase. It takes three steps to compress a bitbase:
- a "predictor" function that predicts the outcome of each position;
- preliminary RLE compression (optional);
- ZIP compression.
Let me present an example with KBPK, strong side on move. In its raw form the bitbase would take 64*64*48*64 / 2 bits or 768K. Since KBP almost always win, actually 97.22% of those bits will have the same value (assuming invalid positions are properly set). This compress very well of course and actually zips to about 18K. I've found that in such cases adding a preliminary layer of RLE compression helps a lot, and here it will take the final size to 15K, that's more than 15% smaller.
So far so good. Now the problem is: can we improve the 97.22% figure? Yes, and here enters the predictor. This function encodes the bitbase by guessing the value of each position, then replacing the bitbase entry with a 0 if the guess was correct, or 1 if it was wrong. In the KBPK predictor I've put this simple line:
- Code: Select all
if( FileOfSquare(wp) == 0 && ! is_light_square(wb) ) {
if( distance( bk, A8 ) < (distance( wk, A8 )-1) && distance(bk,A8) < distance( wp,A8) ) {
predicted_value = 0;
}
}
This says that when the weak king is closer to the promotion square of a rook pawn and the bishop cannot control that square, the position is draw. It doesn't have to be 100% accurate, all that's matter is that it's right more than it's wrong!
With this one liner we now have 97.63% zero's in the bitbase, and it compresses to 14K.
That's the idea... very similar to what you said about KBNK: your code knews most positions but not all. So it wasn't a perfect recognizer, but it will probably make for an extremely good predictor, allowing for great compression of the corresponding bitbase.
In my code I take advantage of existing bitbases too, so I use KPK in the KPPK predictor, here's the full code:
- Code: Select all
int bbAdjustKPPK( PackedArray * pa, int wtm, int op )
{
printf( "Adjusting KPPK/%d...", wtm );
// Predictions are based on the KPK bitbases, get them
PackedArray * kpk_wtm = getBitBase( bb_KPK, bb_WtM );
PackedArray * kpk_btm = getBitBase( bb_KPK, bb_BtM );
if( kpk_wtm == 0 || kpk_btm == 0 ) {
printf( "*** Warning: KPPK adjuster can't find KPK bitbase\n" );
return -1;
}
// Use also the KPPK table with black to move
PackedArray * kppk_btm = 0;
if( wtm ) {
kppk_btm = getBitBase( bb_KPPK, bb_BtM );
}
PositionEnumerator posEnum;
posEnum.addPiece( WhitePawn );
posEnum.addPiece( WhitePawn );
unsigned good_predictions = 0;
while( posEnum.hasMorePositions() ) {
if( FileOfSquare( posEnum.getWhiteKingPos() ) >= 4 ) {
// Skip this position (simmetry)
posEnum.gotoNextPosition();
continue;
}
if( ! posEnum.isValidPosition( wtm ? true : false ) ) {
good_predictions++;
posEnum.gotoNextPosition();
continue;
}
int index = getBitBaseIndex( bb_KPPK, posEnum );
// Predict and fix the bitbase
int wk = posEnum.getWhiteKingPos();
int bk = posEnum.getBlackKingPos();
int p1 = posEnum.getPiecePos( 2 );
int p2 = posEnum.getPiecePos( 3 );
if( p1 > p2 ) {
int x = p1;
p1 = p2;
p2 = x;
}
unsigned predicted_value =
kpk_wtm->get( getBitBaseIndex(bb_KPK,wk,bk,p1) ) |
kpk_wtm->get( getBitBaseIndex(bb_KPK,wk,bk,p2) ) |
kpk_btm->get( getBitBaseIndex(bb_KPK,wk,bk,p1) ) |
kpk_btm->get( getBitBaseIndex(bb_KPK,wk,bk,p2) );
if( RankOfSquare(p1) == 1 || RankOfSquare(p2) == 1 ) {
predicted_value = 1;
}
if( FileOfSquare(p1) < 7 && p2 == (p1+1) ) predicted_value = 1;
if( FileOfSquare(p1) < 6 && p2 == (p1+2) ) predicted_value = 1;
if( FileOfSquare(p1) < 5 && p2 == (p1+3) ) predicted_value = 1;
if( kppk_btm != 0 ) {
predicted_value |= kppk_btm->get(index);
}
if( predicted_value == pa->get(index) ) {
good_predictions++;
}
pa->set( index, pa->get(index) ^ predicted_value );
posEnum.gotoNextPosition();
}
printf( " done, accuracy = %05.2f\n", (good_predictions * 100.0) / getBitBaseIndexRange(bb_KPPK) );
return 0;
}
This was easy and fun to write, and made KPPK compress to 9K.
The bitbases for the weaker side do not compress so well, so I'm a bit concerned about those, but if it is actually possible to use bitbases for only one side then probably the few hundreds K target is feasible.
- at least I was not able to educe it enough with Acobat Distiller 7.0.