KPK bitbase

[lucasart]

Exploiting the symmetry of the problem, we assume without restriction that white has the pawn, and the pawn is within [A2..D7] rectangle. So there are N = 64*64*24*2 elements in the bitbase (2 for side to move).

Out of these, how many draws are there ?

I need a unit test to validate my code -- like assert(nb_draws == ...). Nb of draws seems like a good unit test, just like perft values are a good unit test for board/movegen code. If everyone agrees on that number, it's likely to be correct. If it's not a good unit test as such, perhaps the number of draws for each of the 6 values of rank(white pawn) or something like that.

Also regarding rules used to initialize the generation, are these rules 100% correct at detecting a draw ? (even if the white pawn is on the 2nd rank and/or on a rook file)

• Black king directly in front of the pawn, white king directly behind it, black to move.
• Black king directly in front of the pawn, white king diagonally behind the pawn, white to move.

[Evert]

Also regarding rules used to initialize the generation, are these rules 100% correct at detecting a draw ? (even if the white pawn is on the 2nd rank and/or on a rook file)

• Black king directly in front of the pawn, white king directly behind it, black to move.
• Black king directly in front of the pawn, white king diagonally behind the pawn, white to move.

Can't you use key squares to test that more generally?

[lucasart]

Also regarding rules used to initialize the generation, are these rules 100% correct at detecting a draw ? (even if the white pawn is on the 2nd rank and/or on a rook file)

• Black king directly in front of the pawn, white king directly behind it, black to move.
• Black king directly in front of the pawn, white king diagonally behind the pawn, white to move.

Can't you use key squares to test that more generally?

I am not looking to generalize or complicate the rules so that I can predict all with static rules. This would lead to an immense and incomprehensible code base (that would almost certainly be buggy too). I want to have a few basic and simple rules that are 100% accurate for the first iteration. Then I will generate the bitbase iteratively. Here are the fules I've coded so far:

Code: Select all

int rules(unsigned idx)
{
	assert(idx < IndexMax);
	int wk, bk, stm, wp;
	decode(idx, &wk, &bk, &stm, &wp);
	
	// pieces overlapping or kings checking each other
	if (kdist(wk, bk) <= 1 || wp == wk || wp == bk)
		return ILLEGAL;
	// cannot be white's turn if black is in check
	if (stm == WHITE && test_bit(PAttacks[WHITE][wp], bk))
		return ILLEGAL;
	
	// black king can capture the pawn immediately
	if (stm == BLACK && test_bit(KAttacks[bk], wp) && !test_bit(KAttacks[wk], wp))
		return DRAW;
	
	// rule of the square (unstoppable passer)
	const int psq = square(RANK_8, file(wp));
	if (kdist(bk, psq) - (stm == BLACK) > RANK_8 - rank(wp))
		return WIN;
	
	// black king in front of the pawn
	if (wp+8 == bk) {
		// white king behind the pawn, black to move
		if (stm == BLACK && wk+8 == wp)
			return DRAW;
		// white king diagonally behind the pawn, white to move
		if (stm == WHITE && test_bit(PAttacks[BLACK][wp], wk))
			return DRAW;
	}
	
	return UNKNOWN;
}

Results of applying these rules to the N = 64*64*24*2 positions:

Code: Select all

30932 ILLEGAL
74355 UNKNOWN
9164 DRAW
82157 WIN

Now I need to code the iteration part.

I should have some total results soon

**edit** Just realized that my "rule of the square" implementation is wrong. White king should be outside of the promotion path... obviously...

[kongsian]

I have the following:

Unknown: 0
Invalid: 30932
Win: 62642
Loss: 49052
Draw: 53982

Kong Sian

[lucasart]

I have the following:

Unknown: 0
Invalid: 30932
Win: 62642
Loss: 49052
Draw: 53982

Kong Sian

Thank you. Fingers crossed I get the same results

[lucasart]

I have the following:

Unknown: 0
Invalid: 30932
Win: 62642
Loss: 49052
Draw: 53982

Kong Sian

Are you sure of these numbers ? Just by applying the rule of the square

Code: Select all

	// rule of the square (unstoppable passer)
	const int psq = square(RANK_8, file(wp));
	if (kdist(bk, psq) - (stm == BLACK) > RANK_8 - rank(wp)
		&& !test_bit(SquaresInFront[WHITE][wp], wk))
		return WIN;

I can already find 78419 wins.

Does anyone have different numbers ? I don't see what I'm doing wrong in with rule of the square

[Ajedrecista]

Hello Lucas:

I have the following:

Unknown: 0
Invalid: 30932
Win: 62642
Loss: 49052
Draw: 53982

Kong Sian

Are you sure of these numbers ? Just by applying the rule of the square

Code: Select all

	// rule of the square (unstoppable passer)
	const int psq = square(RANK_8, file(wp));
	if (kdist(bk, psq) - (stm == BLACK) > RANK_8 - rank(wp)
		&& !test_bit(SquaresInFront[WHITE][wp], wk))
		return WIN;

I can already find 78419 wins.

Does anyone have different numbers ? I don't see what I'm doing wrong in with rule of the square

There is a recent thread in TalkChess with this exact name:

KPK bitbase

There are other numbers in that thread. I hope it will be helpful for you. Good luck!

Regards from Spain.

Ajedrecista.

[lucasart]

Thank you Jesus. According to this thread, the correct numbers are

Code: Select all

WIN: 111282 
DRAW: 54394 
INVALID: 30932 

This seems much more reasonable, as I could already find 78585 wins by applying some trivial static rules.

[kongsian]

I have the following:

Unknown: 0
Invalid: 30932
Win: 62642
Loss: 49052
Draw: 53982

Kong Sian

Are you sure of these numbers ? Just by applying the rule of the square

Code: Select all

	// rule of the square (unstoppable passer)
	const int psq = square(RANK_8, file(wp));
	if (kdist(bk, psq) - (stm == BLACK) > RANK_8 - rank(wp)
		&& !test_bit(SquaresInFront[WHITE][wp], wk))
		return WIN;

I can already find 78419 wins.

Does anyone have different numbers ? I don't see what I'm doing wrong in with rule of the square

I can't guarantee the numbers. The win/loss is for wtm/btm. You can add them up and compare to your number.

Kong Sian

[hgm]

Why not just generate the bitbase by retrograde analysis? This is really a trivial case, as white cannot even be checked, and black cannot be checkmated before promotion.

After marking all illegal positions (Kings next to each other or coinciding, King checked by Pawn and white to move, white King and Pawn coinciding) setting all positions where the Pawn is on the 8th rank and white to move as WON. (As was discussed in the previous thread, there are some positions where these would be stalemate even after promotion to R, but as these positions will not be part of your bitbase, and their aren't positions that are have trivial alternative wins, you can ignore that.)

Don't outlaw positions where Black King and Pawn coincide; these represent the positions were the Pawn was captured. Don't use them to generate moves from.

Then alternate btm and wtm passes through the entire bitbase, probing all reachable positions, and setting them to LOST in a btm pass when all moves from them lead to WON or ILLEGAL positions, and to WON in a wtm pass on the first move you find to a LOST position, until you could not assign anymore WON or LOST positions.