Syzygy bases from memory

[syzygy]

Another syzygy question, is there a tool that can create all epd positions from a syzygy file?

For instance, It would be nice to have all winning positions from KRKN or KRKB endings, or the draws of KRKP endings, they are not too many.

You have to loop through all positions and probe them. Shouldn't be difficult... three for loops, check for two pieces on same square, check for enemy king in check.

[syzygy]

another interesting thing might be to compare scorpio bitbases (WDL I assume) with syzygy WDL, I believe scorpio bitbases actually occupy less disk space

I estimate that Syzygy WDL can be reduced by about 65% by storing only the "smaller" half of each table (either white-to-move only or black-to-move only). This comes at the cost of slowing down the WDL probes by a lot (in case you're probing the missing half -> you need to do a 1-ply probing search). I think this is what Scorpio does (besides having an altogether different compression scheme).

A more subtle cost in case of Syzygy (which knows about the 50-move rule) is that you would have to probe positions with 50-move counter = 1 instead of 0, and the WDL table assumes 50-move counter = 0. So this would introduce some inaccuracy.

Syzygy DTZ only stores the smaller half of each table (and "subtracts" the WDL info from it plus various other tricks).

I have created DTM tables but got stuck on the decision whether to release them as 1-sided or 2-sided tables (they have to be probed in the search, at least when beta > KNOWN_MATE, say).

[Rebel]

Another syzygy question, is there a tool that can create all epd positions from a syzygy file?

For instance, It would be nice to have all winning positions from KRKN or KRKB endings, or the draws of KRKP endings, they are not too many.

You have to loop through all positions and probe them. Shouldn't be difficult... three for loops, check for two pieces on same square, check for enemy king in check.

That's indeed how I do it.

Got stuck trying the KRPKR, probably the most present late endgame, got about 700 million positions for white. Assuming you can safely flipping the board to get the positions with the black pawn I still found probing the Syzygy bases 700 million times a bridge too far for the moment

[petero2]

I have created DTM tables but got stuck on the decision whether to release them as 1-sided or 2-sided tables (they have to be probed in the search, at least when beta > KNOWN_MATE, say).

In texel I probe the DTZ tables during search if the WDL tables don't give enough information given the alpha/beta bounds. I think this works pretty well even though the DTZ tables are 1-sided. Therefore I think 1-sided DTM tables would be fine too.

Another option could be to let the engine know for which side DTM/DTZ information is available, so the engine could search one extra ply itself before probing the TB. I have not tested that though so I don't know if it would actually be better than letting the TB code do the 1-ply search.

[jonkr]

I looked into your code, saw it came under the UBC license (Use But Credit) and wondered if I could use it, did some test positions and it did very well, is it 100% accurate? But my compiler could not compile it and I gave up. Regarding KPKQ, I prune too, white can only draw if the pawn is at least at the 6th row and the white king is close to the pawn, and if the black queen is not on the promotion square.

Feel free to use it if you are able to, this is the latest code :

Code: Select all

//
// Slow Chess has its own table to tell if an endgame with only 1 pawn (+kings) is won or drawn
// It also now has King+Pawn v King+Pawn, King+Pawn v King+Rook, King+Pawn v King+Queen, King+Pawn+Pawn v. King
// and King+Pawn+Pawn v King+Pawn where a white and black pawn block each other.
//
// You can use this code and bitbase freely in your own program.

#include <stdio.h>
#include <malloc.h>

#include "board.h"

int inline SqX(int sq) { return (sq & 7); }
int inline SqY(int sq) { return (sq >> 3); }
int inline FlipH64 ( int nSq ) { return (nSq&56) + 7-(nSq&7); }
// pawn squares
int inline PSQ	( int nSq ) { return ((nSq&56)>>1)-4 + (nSq&7); }
int inline FlipPSQ ( int nSq ) { return ((nSq&56)>>1)-4 + 7 - (nSq&7); }

static constexpr int BITBASE_WIN = 900;
static constexpr int PIECE_BITBASE_WIN = 500;

// -----------

struct SBitbase 
{
	int32_t m_nSize = 0;
	int32_t m_nElz = 0; //Size of each table
	int32_t m_nTables = 0;
	uint16_t *m_pTable = nullptr;
	uint8_t *m_pData = nullptr;

	~SBitbase()
	{
		free( m_pData );
		free( m_pTable );
	}

	size_t Load( std::string filenamePath );
	bool IsLoaded() { return m_pData != 0; }

	size_t Read(FILE* fp);
	size_t Write(FILE* fp);

	int inline ProbeBit( int index)
	{
		int nDataEntry = m_pTable[ (index >> 3) / m_nElz ] * m_nElz + ( (index >>3)&(m_nElz-1) );
		return m_pData[ nDataEntry ] & (1<<(index &7));
	}

	void inline Probe( const int index, int &eval, const int nWin, const int nDraw, const int bFlip)
	{
		if (index < 0 || index >= m_nSize*8) return;

		if ( ProbeBit(index) )	{
			if (bFlip) eval += nWin; else eval = nDraw;
		} else {
			if (bFlip) eval = nDraw; else eval += nWin;
		}
	}
};

size_t SBitbase::Load( std::string filenamePath )
{
	size_t bytes = 0;
	FILE *pFile = fopen(filenamePath.c_str(), "rb" );
	if (pFile != nullptr) 
	{
		bytes += Read(pFile);
		fclose (pFile);
	}

	return bytes;
}

size_t SBitbase::Read(FILE* pFile)
{
	size_t bytes = 0;
	bytes += fread(&m_nSize, sizeof(int32_t), 1, pFile);
	bytes += fread(&m_nTables, sizeof(int32_t), 1, pFile);
	bytes += fread(&m_nElz, sizeof(int32_t), 1, pFile);
	m_pTable = (uint16_t*)malloc(sizeof(uint16_t) * m_nSize / m_nElz);
	m_pData = (uint8_t*)malloc(m_nTables * m_nElz);
	assert(m_pTable && m_pData);
	if (m_pTable && m_pData) {
		bytes += fread(m_pTable, 2, (m_nSize / m_nElz), pFile);
		bytes += fread(m_pData, m_nElz, m_nTables, pFile);
	}
	return bytes;
}

size_t SBitbase::Write(FILE* pFile)
{
	size_t bytes = 0;
	bytes += fwrite(&m_nSize, sizeof(int32_t), 1, pFile);
	bytes += fwrite(&m_nTables, sizeof(int32_t), 1, pFile);
	bytes += fwrite(&m_nElz, sizeof(int32_t), 1, pFile);
	bytes += fwrite(m_pTable, 2, (m_nSize / m_nElz), pFile);
	bytes += fwrite(m_pData, m_nElz, m_nTables, pFile);
	return bytes;
}

SBitbase KPPK, KPK, KPKR, KPPKP, KPNK, KPKQ, KPKP, KPBK, PawnRace;
SBitbase* AllBitbases[] = { &PawnRace, &KPK, &KPKP, &KPPK, &KPPKP, &KPKQ, &KPKR, &KPNK, &KPBK };

int LoadEndgameBitbases( std::string path )
{
	int count = 0;
	std::string fullPath = path + "/EndgameBitbases.sbb";
	FILE* fp = fopen(fullPath.c_str(), "rb");
	if (fp)
	{
		for (auto bitBase : AllBitbases)
		{
			count += bitBase->Read(fp) > 0;
		}
		fclose(fp);
	}
	/*
	count += PawnRace.Load( path + std::string("/bitbases/pawnrace.sbb") ) > 0;
	count += KPK.Load(path + "/bitbases/KPK.sbb") > 0;
	count += KPKP.Load(path + "/bitbases/KPKP.sbb") > 0;
	count += KPPK.Load(path + "/bitbases/KPPK.sbb") > 0;
	count += KPPKP.Load(path + "/bitbases/KPPKP.sbb") > 0;
	count += KPKQ.Load(path + "/bitbases/KPKQ.sbb") > 0;
	count += KPKR.Load(path + "/bitbases/KPKR.sbb") > 0;
	count += KPNK.Load(path + "/bitbases/KPNK.sbb") > 0;
	count += KPBK.Load(path + "/bitbases/KPBK.sbb") > 0;
	*/
	return count;
}

void WriteAllBitbases()
{
	FILE* fp = fopen("EndgameBitbases.sbb", "wb");
	if (fp)
	{
		for (auto bb : AllBitbases)
		{
			bb->Write(fp);
		}
		fclose(fp);
	}
}


//
// Black calls the same routine but flips vertically the sqs and swaps the king sqs before calling it
//
void inline KingPawnProbe (int wKingSq, int bKingSq, int pawnSq, eColor stm, int &eval, const int nWin)
{
	// Get Entry Key... May have to flip horizontally because table only stores positions for 
	// the pawn on one side.
	int nEntry; 
	int nTM = (stm == WHITE) ? 1 : 0;
	if ( SqX(pawnSq) > 3)
		nEntry = (FlipH64(wKingSq)) + (FlipH64(bKingSq)<<6) + (nTM<<12) + (FlipPSQ(pawnSq) <<13);
	else 
		nEntry = (wKingSq) + (bKingSq<<6) + (nTM<<12) + (PSQ(pawnSq) <<13);

	KPK.Probe( nEntry, eval, nWin, 0, 0 );
}

//
// 2 Pawns
//
void inline KingPawnsProbe(SBitbase &BitBase, int wKingSq, int bKingSq, int wPawnSq, int bPawnSq, eColor stm, int &eval, const int nWin, int bFlip)
{
	int nEntry; 
	int nTM = (stm == WHITE) ? 1 : 0;
	if ( SqX(wPawnSq) > 3) nEntry = (nTM) + (FlipH64(wKingSq)<<1) + (FlipH64(bKingSq)<<7) + (FlipPSQ(wPawnSq) <<13) + (FlipH64(bPawnSq)-8) * (0x30000);
		else nEntry = (nTM) + (wKingSq<<1) + (bKingSq<<7) + (PSQ(wPawnSq) <<13) + (bPawnSq -8) * (0x30000);
	BitBase.Probe( nEntry, eval, nWin, 0,  bFlip);
}

//
// Knight + Pawn probe
//
void inline KingPiecePawnProbe(SBitbase &BitBase, int wKingSq, int bKingSq, int wPawnSq, int nWPieceSq, eColor stm, int &eval, const int nWin)
{
	int nEntry; 
	int nTM = (stm == WHITE) ? 1 : 0;
	if ( SqX(wPawnSq) > 3) nEntry = (nTM) + (FlipH64(bKingSq)<<1) + (FlipH64(wKingSq)<<7) + (FlipH64(nWPieceSq)<<13) + (FlipPSQ(wPawnSq) <<19);
		else nEntry = (nTM) + (bKingSq<<1) + (wKingSq<<7) + (nWPieceSq<<13) + (PSQ(wPawnSq) <<19);
	BitBase.Probe( nEntry, eval, nWin, 0,  0);
}

//
// Pawn v Queen
// Only includes positions with the weak side's King and Pawn on squares with drawing possibilities
//
void inline KingPawnQueenProbe (int wKingSq, int bKingSq, int bQueenSq, int wPawnSq, eColor stm, int &eval )
{
	int nEntry = -1, nPSq;
	if ( wKingSq >= 24) return;
	if (wPawnSq == 8) nPSq = 0; else if (wPawnSq == 10) nPSq = 1; else if (wPawnSq == 16) nPSq = 2; else if (wPawnSq == 18) nPSq=3;
	else if (wPawnSq ==15) nPSq = 4; else if (wPawnSq == 13) nPSq = 5; else if (wPawnSq == 23) nPSq = 6; else if (wPawnSq == 21) nPSq=7;
	else return;

	int nTM = (stm == WHITE) ? 1 : 0;
	if (nPSq > 3) nEntry = (FlipH64(bQueenSq)) + (FlipH64(bKingSq)<<6) + (nTM<<12) + ((nPSq-4)<<13) + (FlipH64(wKingSq)<<15);
	else nEntry = (bQueenSq) + (bKingSq<<6) + (nTM<<12) + (nPSq<<13) + (wKingSq << 15);

	KPKQ.Probe( nEntry, eval, 0, (eval>>5) + (eval>>6), 0);
}

//
// Pawn Versus Rook
// 
void inline KingPawnRookProbe( int wKingSq, int bKingSq, int bRookSq, int wPawnSq, eColor stm, int &eval, const int nWin )
{
	int nTM = (stm == WHITE) ? 1 : 0;
	if (SqY(wPawnSq) > 4) // Table doesn't include pawn on first ranks, do the pawn move first then check the table
	{
		int advanceSq = wPawnSq - 8;
		if (nTM == 1 && advanceSq !=wKingSq && advanceSq !=bKingSq && advanceSq != bRookSq)
		{
			wPawnSq = advanceSq;
			if (SqY(wPawnSq) > 4)
			{
				advanceSq = wPawnSq - 8;
				if ( advanceSq != wKingSq && advanceSq != bKingSq && advanceSq != bRookSq) wPawnSq = advanceSq; else { eval += nWin; return; }
			}
		}
		else {eval+=nWin; return;}
		nTM^=1;
	}
	int index; 
	if ( SqX(wPawnSq) > 3)
		index = (FlipH64(bRookSq)) + (FlipH64(bKingSq)<<6) + (FlipH64(wKingSq)<<17) + (nTM<<16) + (FlipPSQ(wPawnSq) <<12);
	else
		index = (bRookSq) + (bKingSq<<6) + (wKingSq<<17) + (nTM<<16) + (PSQ(wPawnSq) <<12);

	KPKR.Probe(index, eval, nWin, 0, 0);
}

//
// Check if a bitbase is applicable, and if it is convert to the appropriate piece list and probe it.
// Because of quite different board formats, this code is longer than I'd like it to be.
//
bool ProbeBitbases(const Board &board, int &eval)
{
	for ( const eColor c : {WHITE, BLACK})
	{
		const eColor o = Opp(c);
		const int KingSqC = board.kingSq[c];
		const int KingSqO = board.kingSq[o];

		if (board.material[c].Value() == PAWN_VALUE && board.material[o].Value() == QUEEN_VALUE && board.NumPawns(o) == 0)
		{
			if (KPKQ.IsLoaded())
			{
				int PawnSqC = board.GetPieceSq(PAWN, c);
				int QueenSqO = board.GetPieceSq(QUEEN, o);
				if (c == BLACK) KingPawnQueenProbe(63 - KingSqC, 63 - KingSqO, 63 - QueenSqO, 63 - PawnSqC, Opp(board.stm), eval);
				else KingPawnQueenProbe(KingSqC, KingSqO, QueenSqO, PawnSqC, board.stm, eval);
				return 1;
			}
		}
		if (board.material[c].Value() == PAWN_VALUE && board.material[o].Value() == ROOK_VALUE && board.NumPawns(o) == 0)
		{
			if (KPKR.IsLoaded())
			{
				int RookSqO = board.GetPieceSq(ROOK, o);
				int PawnSqC = board.GetPieceSq(PAWN, c);
				if (c == BLACK) KingPawnRookProbe(63 - KingSqC, 63 - KingSqO, 63 - RookSqO, 63 - PawnSqC, Opp(board.stm), eval, PIECE_BITBASE_WIN);
				else KingPawnRookProbe(KingSqC, KingSqO, RookSqO, PawnSqC, board.stm, eval, -PIECE_BITBASE_WIN);
				return 1;
			}
		}
		if (board.material[c].Value() == PAWN_VALUE + KNIGHT_VALUE && board.material[o].Value() == 0)
		{
			if (KPNK.IsLoaded())
			{
				int KnightSqC = board.GetPieceSq( KNIGHT, c);
				int PawnSqC = board.GetPieceSq(PAWN, c);
				if ( c == BLACK ) KingPiecePawnProbe(KPNK, 63 - KingSqC, 63 - KingSqO, 63 - PawnSqC, 63 - KnightSqC, Opp(board.stm), eval, -PIECE_BITBASE_WIN);
				else KingPiecePawnProbe(KPNK, KingSqC, KingSqO, PawnSqC, KnightSqC, board.stm, eval, PIECE_BITBASE_WIN);
				return 1;
			}
		}
		if (board.material[c].Value() == PAWN_VALUE + BISHOP_VALUE && board.material[o].Value() == 0)
		{
			if (KPBK.IsLoaded())
			{
				int BishopSqC = board.GetPieceSq(BISHOP, c);
				int PawnSqC = board.GetPieceSq(PAWN, c);
				if (c == BLACK) KingPiecePawnProbe(KPBK, 63 - KingSqC, 63 - KingSqO, 63 - PawnSqC, 63 - BishopSqC, Opp(board.stm), eval, -PIECE_BITBASE_WIN);
				else KingPiecePawnProbe(KPBK, KingSqC, KingSqO, PawnSqC, BishopSqC, board.stm, eval, PIECE_BITBASE_WIN);
				return 1;
			}
		}
	}

	return 0;
}

#define MakePawnKey( pawnsC, pawnsO ) pawnsC + (pawnsO << 3)

//
// Probe bitbases for positions with only pawns and kings
//
bool ProbePawnBitbases( const Board &board, int &eval )
{
	for (const eColor c : {WHITE, BLACK})
	{
		const eColor o = Opp(c);
		int pawnKey = MakePawnKey( board.NumPawns(c), board.NumPawns(o) );
		const int KingSqC = board.kingSq[c];
		const int KingSqO = board.kingSq[o];

		switch (pawnKey)
		{
		case MakePawnKey(1, 0):
			if (KPK.IsLoaded())
			{
				int PawnSqC = board.GetPieceSq(PAWN, c);
				if (c == BLACK) KingPawnProbe(63 - KingSqC, 63 - KingSqO, 63 - PawnSqC, Opp(board.stm), eval, -BITBASE_WIN);
				else KingPawnProbe(KingSqC, KingSqO, PawnSqC, board.stm, eval, BITBASE_WIN);
				return true;
			}
			break;

		case MakePawnKey(2, 0):		
			if (KPPK.IsLoaded())
			{
				BitBoard pbb = board.Pieces(PAWN, c);
				int pawnSq1 = pbb.PopLowSq();
				int pawnSq2 = pbb.PopLowSq();
				if (c == BLACK) KingPawnsProbe(KPPK, 63 - KingSqC, 63 - KingSqO, 63 - pawnSq1, 63 - pawnSq2, Opp(board.stm), eval, -BITBASE_WIN, 0);
				else KingPawnsProbe(KPPK, KingSqC, KingSqO, pawnSq1, pawnSq2, board.stm, eval, BITBASE_WIN, 0);
				return true;
			}
			break;
				
		case MakePawnKey(1, 1):
			// Since this table is symetric, it's probed for a win by both sides during WHITE check only
			if (KPKP.IsLoaded() && c == WHITE)
			{
				int PawnSqC = board.GetPieceSq(PAWN, c);
				int PawnSqO = board.GetPieceSq(PAWN, o);
				int oldEval = eval;
				KingPawnsProbe(KPKP, KingSqC, KingSqO, PawnSqC, PawnSqO, board.stm, eval, BITBASE_WIN, 1);
				if (eval == 0)
				{
					eval = oldEval;
					KingPawnsProbe(KPKP, 63 - KingSqO, 63 - KingSqC, 63 - PawnSqO, 63 - PawnSqC, Opp(board.stm), eval, -BITBASE_WIN, 1);
				}
				return true;
			}
			break;

		case MakePawnKey(2, 1):
			// this bitbase not full, it only stores position where there is a blocked pawn.. those are often trickiest
			// Theres no loss for side with more pawns, it gets draw instead. I suppose that's more accurate as long as previous eval favored side with more pawns.
			// 8/8/3Kp1p1/6P1/8/3k4/8/8 b - 
			if (KPPKP.IsLoaded())
			{
				int PawnSqO = board.GetPieceSq(PAWN, o);
				if ((board.sqs[PawnSqO + PawnPush[o]] & 7) == PAWN)
				{
					// Get non-blocked pawn sq
					BitBoard pbb = board.Pieces(PAWN, c);
					int PawnSqC = pbb.PopLowSq();
					if (PawnSqC == PawnSqO + PawnPush[o])  PawnSqC = pbb.PopLowSq();
					if (c == BLACK) KingPawnsProbe(KPPKP, 63 - KingSqC, 63 - KingSqO, 63 - PawnSqC, 63 - PawnSqO, Opp(board.stm), eval, -BITBASE_WIN, 0);
					else KingPawnsProbe(KPPKP, KingSqC, KingSqO, PawnSqC, PawnSqO, board.stm, eval, BITBASE_WIN, 0);
					return true;
				}
			}
			break;
		}
	}
	return false;
}

When coming back to the very old SlowChess code it took me a while to unravel it in general, definitely wasn't the cleanest or best code.
I haven't looked in any detail at bitbases again, syzygy are a good standard (though do require a few thousand lines of someone else's code to probe.) I'd probably only look into endgame tables again if I wanted to do some specific experiments.

My bitbases should be accurate in terms of being bug free (I hope so anyway), but it doesn't necessarily give a score for every position, and I think some piece configurations if there's a weak-side that can win, it would still give draw value. I did at one time locally have a more complete set, but only included ones that seemed important to play.

[hgm]

I am perfectly fine with the chosen format as it contains the best move for free to guide the search something bit-bases don't have.

So you store a move as well? That of course bloats the amount of data even more. Even more than when you would store the DTZ.

And it doesn't seem useful. When a position probed in search is a draw, searching on is just a waste of time, and you can return a draw score immediately. In the root you would need a move to play, but a 1-ply search will give you a drawing move. So the only case where you have to search on is when the position is win/loss. A self-inflicted problem, because you store moves rather than DTZ or DTM. With the latter you could also just return the DTx score without search, (or in the root, search one ply).

Doesn't sound like a smart design to me...

And I somehow doubt that it would be very difficult for a search in the root to find the shortest win in KRKB / KRKN and the like when guided by the WDL info.

[Rebel]

You judge without asking how things are organized.

Takes away the fun of answering.

[hgm]

Oh, is that is? I thought you didn't want to make clear what you are doing as a matter of principle...

[Rebel]

Wrong, if you ask instead of jumping into false conclusions I will explain.

Just be civilized like everybody else.

Or pretend.

[hgm]

I have no reason to believe that any of my conclusions could be falsified in the eyes of the readers by new information from you that would not contradict what you wrote earlier. I do understand of course why you would like to pretend they do.