Author: Charles Roberson
Date: 15:44:48 12/11/04
Go up one level in this thread
Here is something I started a while back. IIRC it is incomplete
but it may answer some of your questions.
How To Infterface with Nalimov Endgame Tablebases
Charles Roberson
This document's intended audience is software engineers that are familar with
fundamental search
algorithms and the specifics or chess programs. Thus, I will not define
fundamental software terms like "glue" code. I intend to make this document
sufficient for an experienced software developer to read and then glue Nalimov
endgame tablebases into his/her program. If you think I could be more clear or
have any questions, email me and I'll be glad to answer and modify this
document.
My motivation is to help people glide through this effort with ease. Some people
have stated this is a confusing process on the various computer chess forums.
Eugene provides a document (probe.txt) but it seems some still have problems. I
in no way intend to step on Eugene's toes or imply that his documentation is
poor. In fact, this document will a bit less detailed.
Thanks to the efforts of Eugene Nalimaov, we have freely available endgame
tablebases (EGTB). The five man (including the two kings) egtbs are complete and
effort is underway for six man tablebases. Also, Eugene supplies code to access
his tablebases. However, one must write some
"glue" code to translate the information from your data structures to the
structures of his code.
This document will attempt to shed enough light on this subject to make the
effort easier. The information in this document comes from my own experience
implementing EGTB's in
NoonainChess.
Internals Information:
Eugene's code uses a straight forward board representation -- a 64 element
array. Position 0 in
the array refers to square A0 while position 63 refers to square H8. Just to
make it clear, position
7 refers to H1 and position 8 refers to A2.
His code requires certain functions to interface with your data structures
and/or some intermediate data structures. For five man EGTB's they are
SqFindOne, SqFindFirst, SqFindSecond, SqFindThird and SqFindKing. I will define
them in the Glue Code Function Definitions section.
What to Do:
Before you start the coding process, I suggest that you email Eugene and ask
permission to
use his code.
So, you only need to do a few things. First, write some code to call your
probing code. Second, initialize some data structures in your probing code.
Third call Eugene's supplied functions from your probing code and use the
result. This is not too difficult because Eugene supplied information on this.
Now, here is the catch. Don't call probe inside your position evaluator (PE) or
quiesce routine. Call it from your main search routines. Fourth, create a
command line option or an initfile option that tells where to find the egtbs.
Fifth, you'll have to define a few macros and types. Last, you'll have to
compile and link in Eugene's code with yours. You'll need the files tbdecode.h
and tbindex.cpp. If you don't use C or C++, you may have to translate his code
into your primary language. This document assumes that you have used C or C++. I
have written the code segments in C. It should be little effort to convert to
other languages.
Why shouldn't you probe the tablebases from the PE or the quiesce routine? If
your code is anything like mine (NoonianChess), you call the PE from your
quiesce routine and you can't trust a mate score returned from the quiesce
routine as it is not an exhaustive search. Also, it is more effective to have it
in the primary search code. When there are only five men on the board, why
perform a negamax search?
Top Down Format:
The rest of this document will define the process in top down fashion. I
will start with the probe code to add to your program and end with information
about Eugene's code. Along the way, types and data structures will be defined.
Initialization of the Tablebases:
You need to add a command line or init file option to define the location and
cache size of the tablebases. Eugene provides the function IInitializeTb (char
*path).
***************************************************************************************************************************************************************************************************************************************
Your Probe Calling Code:
In the search routine add the code to probe egtb's. The code will have to
consider color to move and handle positon not found. The following pseudo code
segment will do the trick for five man tablebases. The modifications for six
should be obvious.
int NegamaxSearch(ply,alpha,beta)
{ int v;
// TotalWhitePieces counts kings, pieces and pawns.
If ((TotalWhitePieces + TotalBlackPieces < 6) && USINGTABLEBASES)
{
v = EGTBProbe(ColorToMove,ply);
if (v!=NOTFOUND)
{
if (v>0) // scores are relative to white.
v = MATESCORE - (INF-v) - ply + 1;
else
if (v<0)
v = -1 * (MATESCORE - (INF+v) - ply +1);
return(v);
}
}
GenerateMoves();
for (each move)
{
Do your normal stuff
}
} // End Negamax
In the above pseudo code, MATESCORE and INF need to be defined. MATESCORE is
your current value for a checkmate. INF is a value used in Eugene's code and it
needs to be exported to your code. Thus, the above equations are needed to
translate egtb mate values to your own. The value returned from probe_egtb is
relative to white to move. The value will be positive if white is winning and
negative if black is winning.
Your Probing Code:
You'll need to define some constants and import functions as described in
Eugene's documentation. The must be as stated below to be compatible. The code
defines below were taken from Eugene's documentation.
#if defined (_MSC_VER)
#define TB_FASTCALL __fastcall
#else
#define TB_FASTCALL
#endif
typedef int color;
#define x_colorWhite 0
#define x_colorBlack 1
#define x_colorNeutral 2
typedef int piece;
#define x_pieceNone 0
#define x_piecePawn 1
#define x_pieceKnight 2
#define x_pieceBishop 3
#define x_pieceRook 4
#define x_pieceQueen 5
#define x_pieceKing 6
#define L_pageL 65536
#define L_tbbe_ssL ((L_pageL - 4) / 2)
#define L_bev_broken (L_tbbe_ssL + 1) /* illegal or busted */
#define L_bev_mi1 L_tbbe_ssL /* mate in 1 move */
#define L_bev_mimin 1 /* mate in 32766 moves */
#define L_bev_draw 0 /* draw */
#define L_bev_limax (-1) /* mated in 32765 moves */
#define L_bev_li0 (-L_tbbe_ssL) /* mated in 0 moves */
#define L_bev_limaxx (-L_tbbe_ssL - 1) /* mated in 32766 moves */
#define L_bev_miminx (-L_tbbe_ssL - 2) /* mate in 32767 moves */
typedef INDEX (TB_FASTCALL * PfnCalcIndex)
(square*, square*, square, int fInverse);
extern int IDescFindFromCounters (int*);
extern int FRegisteredFun (int, color);
#define FRegistered FRegisteredFun
extern PfnCalcIndex PfnIndCalcFun (int, color);
#define PfnIndCalc PfnIndCalcFun
extern int TB_FASTCALL L_TbtProbeTable (int, color, INDEX);
#endif
The fundamental data structures expected by Eugene's code is the array
rgiCounters and two arrays for the white and black piece locations. rgiCounters
is quite simple; it is single dimmensional. It provides the number of pieces of
each type, except kings, to Eugene's code. It has the expected ordering of white
pawns, white knights, white bishops, white rooks, white queens, black pawns,
black knights, black bishops, black rooks and black queens. The piece arrays
have a prescribed usage format in two parts. Each piece array holds both the
piece types and the piece location. The usage format expects all piece types
first and the piece locations second, thus the requirement of 8 elements per
piecelist. In five man tablebases, one side can have at most 4 pieces. The
piecetype is first (lets say 2nd element ==1) and the piece location is offset
from that by 4 (element 5).
The code to setup rgiCounters and peice arrays is based on the data structures
of NoonianChess. NoonianChess has two piecelists -- one for white and one for
black. The values in the piecelists are squares where pieces sit on the board.
The pos[64] array holds the piece type for the piece occupying that square.
NoonianChess defines piece types as constants such as WPT for white pawn type
and BPT for black pawn type.
int EGTBProbe(int ColorToMove, int Ply)
{
int rgiCounters[10],itb, fInvert,j,i;
int WhitePieces[8],BlackPieces[8];
int whitepiececount, blackpiececount;
color side;
square *psqW;
square *psqB;
square sqEnP;
INDEX ind;
// Initialize rgiCounters and piece arrays
for (j=0;j<10;j++)
rgiCounters[j] = 0;
// Putting the King first, makes the function SqFindKing simple.
WhitePieces[0] =6; // Eugene defines the king piece type as 6
BlackPieces[0] = 6;
WhitePieces[4] = whitekingsquare; // the square occupied by the white king
BlackPieces[4] = blackkingsquare; // the square occupied by the black king
whitepiececount = blackpiececount = 1;
for (j=0;j<MAXPIECES;j++)
{
i = WPieceList[j];
switch(pos[i])
{
case WPT:
rgiCounters[0]++;
WhitePieces[whitepiececount] = x_piecePawn;
WhitePieces[whitepiececount] = i;
whitepiececount++;
break;
case WKnT:
rgiCounters[1]++;
WhitePieces[whitepiececount] = x_pieceKnight;
WhitePieces[whitepiececount] = i;
whitepiececount++;
break;
case WBT:
rgiCounters[2]++;
WhitePieces[whitepiececount] = x_pieceBishop;
WhitePieces[whitepiececount] = i;
whitepiececount++;
break;
case WRT:
rgiCounters[3]++;
WhitePieces[whitepiececount] = x_pieceRook;
WhitePieces[whitepiececount] = i;
whitepiececount++;
break;
case WQT:
rgiCounters[4]++;
WhitePieces[whitepiececount] = x_pieceQueen;
WhitePieces[whitepiececount] = i;
whitepiececount++;
break;
default:
break;
}
i = BPieceList[j];
switch(pos[i])
{
case BPT:
rgiCounters[5]++;
BlackPieces[blackpiececount] = x_piecePawn;
BlackPieces[blackpiececount] = i;
blackpiececount++;
break;
case BKnT:
rgiCounters[6]++;
BlackPieces[blackpiececount] = x_pieceKnight;
BlackPieces[blackpiececount] = i;
blackpiececount++;
break;
case BBT:
rgiCounters[7]++;
BlackPieces[blackpiececount] = x_pieceBishop;
BlackPieces[blackpiececount] = i;
blackpiececount++;
break;
case BRT:
rgiCounters[8]++;
BlackPieces[blackpiececount] = x_pieceRook;
BlackPieces[blackpiececount] = i;
blackpiececount++;
break;
case BQT:
rgiCounters[9]++;
BlackPieces[blackpiececount] = x_pieceQueen;
BlackPieces[blackpiececount] = i;
blackpiececount++;
break;
}
}
iTB = IDescFindFromCounters(rgiCounters);
// IDescFindFromCounters supplied by Eugene in tbindex.cpp
if (iTb == 0)
return NOTFOUND
// The tablebases do not have this piece combination
// NOTFOUND is defined identically to use in NegamaxSearch
if (iTb > 0)
{
side = ColorToMove ? x_colorBlack : x_colorWhite;
// NoonianChess defines WHITE as 0 and BLACK as 1
fInvert = false;
// fInvert allows for a single color perspective
// compare settings of psqW and psqB to the else branch
psqW = WhitePieces; //pointer to white piece locations
psqB = BlackPieces; //pointer to the black piece locations
}
else
{
// All needs inversion here
side = ColorToMove ? x_colorWhite : x_colorBlack;
// NoonianChess defines WHITE as 0 and BLACK as 1
fInvert = true;
psqW = BlackPieces; //pointer to black piece locations
psqB = WhitePieces; //pointer to the white piece locations
iTn = -iTb;
}
if (!FRegistered(iTb,side)) // FRegistered is provided by Eugene in
tbindex.cpp
return NOTFOUND
// NOTFOUND is defined identically to use in NegamaxSearch
if (EnPassant Capture is NOT possible)
sqEnP = XX; // You must define XX as any number > 63
else
sqEnP = square of the pawn that can be captured EnPassant;
ind = PfnIndCalc(iTb, side) (psqW, psqB,sqEnp,fInvert);
// PfndIndCalc is provided by Eugene in tbindex.cpp
value = L_TbtProbeTable(iTb,side,ind);
// L_TbtProbeTable is provided by Eugene in tbindex.cpp
if (value == L_bev_broken)
return(NOTFOUND);
if (score>0)
return((score-bev_mi1-1)*2+INF-ply);
else
return((score+bev_mi1)*2-INF+ply);
} // End EGTBProbe
You have to define the types ??square?? and INDEX. I have the following
typedef int square; typedef unsigned long INDEX;
Glue Code Function Definitions:
If you choose to setup as in EGTBProbe, you don't need to change the
following functions. The only reason to change Eugenes definitions of these
functions is you have a more efficient method that will work directly with your
data structures. If that is so, you can drop the setup of WhitePieces and
BlackPieces. But, you still need to setup rgiCounters. You'll have to change
Eugene's code for PfnIndCalc as well.
For all the following funtions the return value should be int and the range
is 0 to 63 as defined above. These functions are supplied in Eugene's code
(tbindex.cpp) however you could rewrite them. My humble suggestion is that you
create the necessary data structures and use his code.
SqFindKing simply returns the square that the king sits on. It is passed a
square pointer to the WhitePieces or BlackPieces arrays.
SqFindOne returns the square of the only nonking piece. This happens when
you are down to the three men tablebases. It receives two parameters. The first
is a pointer to the WhitePieces or BlackPieces arrays. The second is the piece
type.
SqFindFirst returns the location of the first piece of a given type. It
requires two parameters. The first is a pointer to the WhitePieces or
BlackPieces arrays. The second is the piece type.
SqFindSecond returns the location of the second piece of a given type. It
requires two parameters. The first is a pointer to the WhitePieces or
BlackPieces arrays. The second is the piece type.
SqFindThird returns the location of the third piece of a given type. It
requires two parameters. The first is a pointer to the WhitePieces or
BlackPieces arrays. The second is the piece type.
Acknowledgements
I'd like to thank Eugene Nalimov for his efforts and his permission to use
his tablebases and code. I'd thank Gian-Carlo Pascutto for the help he provided
when I started my effort. Also, I thank Dr. Robert Hyatt for supplying download
site for the Nalimov tablebases.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.