Syzygy bases from memory

[Rebel]

False, the readers might conclude that we don't get along, which is true.

[amanjpro]

Please calm down... I don't know the history between both of you. But what I know, you both are very smart and very helpful for the community.
Ed thinks he can do something, not sure if what he says makes sense or not. Let him do it and we judge the work, not the unproven/untested idea.
Once it is implemented we can actually debate if it is better or not. For now we can only say, yeah we have faith or not in the approach, and that would be it.

I am sure H.G. Muller also has his own reasons to believe that the proposed approach is not sound, weather he is correct or not remains to be seen.

Individually in this forum, I see a bunch of helpful and smart guys... but when it comes to some threads (debates), unfortunately I see lots of tension between groups of posters... can we all be nice, please?

[hgm]

[Moderation] Please note that CTF has been closed at the request of a majority of the members, and trying to revive CTF discussions by quoting them here will not be tolerated.

[hgm]

I am sure H.G. Muller also has his own reasons to believe that the proposed approach is not sound, weather he is correct or not remains to be seen.

Please note that I never claimed the method proposed by Ed is unsound. The only point I (and a bunch of others) made is about efficiency, in particular:
1) that storing WDL info as a list of positions with the minority is less space-efficient than a conventional EGT that stores the info on all positions (but doesn't have to store info to identify the position, as that follows from the location in the table), in cases where the minority result is largere than ~3% (which it usually is).
2) That a binary search on such a list is O(log N), and is not competitive to direct EGT probing or hashing (which both are O(1)). On a data set too large to fit in cache it seems relevant whether you need just a single or more than 20 memory accesses to make a probe.
3) Knowing the DTZ/DTM of each position is more helpful to search than knowing a 'best move', and in general takes less space.

[Rebel]

[Moderation] Please note that CTF has been closed at the request of a majority of the members, and trying to revive CTF discussions by quoting them here will not be tolerated.

What about the readers you are so concerned about?

They may not know you have issues?

[hgm]

That sounds very much like an attack on moderation, and brings you on the brink of a ban...

[Rebel]

The post that was deleted was not related to CTF, picked just one of the many examples.

1. http://talkchess.com/forum3/viewtopic.p ... 12#p791212

There are other moderators beside me, you can complain to those, and if I cross a line, I am sure they will notify me. I am not stalking
Ed specifically, I am just allergic to bullshit. Consider me the avenger of evil.

2. http://talkchess.com/forum3/viewtopic.p ... 56#p821056

I am in it because I am allergic to bullshit. Defender of Truth and avenger of Evil. It stands to reason that is not considered very good by the standards of those who like to produce piles of it. Like the two of you.

[hgm]

You seem to take great offense from the fact that I habitually withspeak falsehoods. One can only guess why that is...

I have made my technical points, and summarized those in the posting above. If you think that a personal attack is the best way (or most fun) to 'refute' those, I must warn you as a moderator: if you persist in this behavior you will be sent on a holiday. Stick to discussing the technical issues.

[Rebel]

Meanwhile I completed the bad bishop ending (KBPK), it's also an improvement over the HCE coding that only evaluates the position as a draw when the king is before the pawn. Last will be the KPKP ending.

[Rebel]

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.

Thanks for the code!

Compiler needs "board.h"

Maybe you can post the neccesarry part of it?