Impossible perft question

[Sven]

(snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

103 ???

The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?

Unfortunately I can confirm the wrong gaviota result. The output below is the same for the 32 and 64 bit versions of Gaviota 0.86 on Windows:

Code: Select all

Gaviota v0.86
Copyright (c) 2000-2013 Miguel A. Ballicora
There is NO WARRANTY of any kind
# mode = winboard/xboard
# Type 'screen' for a better output in console mode
# Type 'help' for a list of useful commands

setboard 1N6/6k1/8/8/7B/8/8/4K3 w - - 0 1
perft 1
depth 0: leaves:          1 accum:          1
depth 1: leaves:         10 accum:         11
seconds: 0.00
perftdiv 1
   -->   Nb8-c6           1
   -->   Ke1-f2           1
   -->   Ke1-e2           1
   -->   Ke1-f1           1
   -->   Nb8-d7           1
   -->   Ke1-d2           1
   -->   Bh4-d8           1
   -->   Bh4-e7           1
   -->   Bh4-g5           1
   -->   Bh4-f6           1
depth 1: leaves:         10
seconds: 0.02 nps: 500.00

Sven

[Sven]

I am willing to bet that after black's c5, the engine may think bxc6 is a legal move but it is not (R checks!).

That would have resulted in a higher node count but the results of "ccore" are lower than the correct ones, so the logical conclusion would be that the engine erroneously rejects legal moves.

Sven

[lucasart]

(snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

103 ???

The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?

Sorry, my mistake. I can never remember which of the two last numbers in the FEN is the move number and which one is the 50 move counter (this one cannot exceed 100).

[michiguel]

(snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

103 ???

The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?

Unfortunately I can confirm the wrong gaviota result. The output below is the same for the 32 and 64 bit versions of Gaviota 0.86 on Windows:

Code: Select all

Gaviota v0.86
Copyright (c) 2000-2013 Miguel A. Ballicora
There is NO WARRANTY of any kind
# mode = winboard/xboard
# Type 'screen' for a better output in console mode
# Type 'help' for a list of useful commands

setboard 1N6/6k1/8/8/7B/8/8/4K3 w - - 0 1
perft 1
depth 0: leaves:          1 accum:          1
depth 1: leaves:         10 accum:         11
seconds: 0.00
perftdiv 1
   -->   Nb8-c6           1
   -->   Ke1-f2           1
   -->   Ke1-e2           1
   -->   Ke1-f1           1
   -->   Nb8-d7           1
   -->   Ke1-d2           1
   -->   Bh4-d8           1
   -->   Bh4-e7           1
   -->   Bh4-g5           1
   -->   Bh4-f6           1
depth 1: leaves:         10
seconds: 0.02 nps: 500.00

Sven

Ha!!!! it is unbelievable that I am going to say... this is not a bug, it is a feature , but I should remove it from perft.

Gaviota rejects moves after being generated in the KBNvK endgame. In this case, moves where the king increments the distance with the other king (Kd1,Kd2), and moves where the B does not attack the opponent kings surroundings. The reason is because neither of those moves are good and it can be demonstrated that you will never need them. It is some sort of super hard pruning. With this feature and some others, Gaviota became extremely good at mating in this endgame, better than any other Adam and I tested (without TBs, of course).

This does not increase any elo, but it was fun to explore this endgame to its full capacity.

I really need to fix this, otherwise it screws perft completely and that is not good. Thanks for reporting it!

Miguel
PS: This is the code. During pre ordering of the moves, if the position is KBNK and the moves is !KBNK_nicemove(), the move is directly eliminated from the list.

Code: Select all

static int kingdist (SQUARE fr, SQUARE to);
static int taxidist (SQUARE fr, SQUARE to);
static int combidist(SQUARE a, SQUARE b) {return taxidist(a,b) + kingdist(a,b);}

#include "gtb-att.h"

#define FOURCORNERS U64(0x8100000000000081)

static bool_t 
KBNK_nicemove (POSITION *po, move_t mv)
{
	unsigned to = MV_TO(mv);
	unsigned fr = MV_FROM(mv);
	unsigned pc = MV_PC(mv);
	unsigned own = po->bi.occ[WH].n_all > 1? WH: BL;
	unsigned opp = Opp(own);
	BITBOARD occ = po->bi.occ[own].all;
	SQUARE 	 oppk = po->bi.occ[opp].king;
	BITBOARD kz = Reach[KING][oppk] | (U64(1) << oppk); /* king zone*/
	unsigned c = MV_COLOR(mv);
	unsigned mvc = Cidx(c);
	int 	 cd0 = combidist(fr,oppk);
	int 	 cd1 = combidist(to,oppk);

	return
		(mvc == opp) 							/* opponent king move */
	||	(0 != ((FOURCORNERS>>oppk) & U64(1))) 	/* opponent king in the corner */
	||	(KNIGHT == pc && (0 != (Reach[KNIGHT][to]&kz) || cd1 < cd0 )) /*N not attacking king zone, moving away*/
	||	(BISHOP == pc && 0 != (B_attacks(to,occ)&kz)) /*B not attacking king zone */
	||	(KING == pc && (cd1 == 4 || cd1 == 5 || cd1 <= cd0 )) /*king moving away*/
	;
}

[lucasart]

(snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

103 ???

The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?

Unfortunately I can confirm the wrong gaviota result. The output below is the same for the 32 and 64 bit versions of Gaviota 0.86 on Windows:

Code: Select all

Gaviota v0.86
Copyright (c) 2000-2013 Miguel A. Ballicora
There is NO WARRANTY of any kind
# mode = winboard/xboard
# Type 'screen' for a better output in console mode
# Type 'help' for a list of useful commands

setboard 1N6/6k1/8/8/7B/8/8/4K3 w - - 0 1
perft 1
depth 0: leaves:          1 accum:          1
depth 1: leaves:         10 accum:         11
seconds: 0.00
perftdiv 1
   -->   Nb8-c6           1
   -->   Ke1-f2           1
   -->   Ke1-e2           1
   -->   Ke1-f1           1
   -->   Nb8-d7           1
   -->   Ke1-d2           1
   -->   Bh4-d8           1
   -->   Bh4-e7           1
   -->   Bh4-g5           1
   -->   Bh4-f6           1
depth 1: leaves:         10
seconds: 0.02 nps: 500.00

Sven

Ha!!!! it is unbelievable that I am going to say... this is not a bug, it is a feature , but I should remove it from perft.

Gaviota rejects moves after being generated in the KBNvK endgame. In this case, moves where the king increments the distance with the other king (Kd1,Kd2), and moves where the B does not attack the opponent kings surroundings. The reason is because neither of those moves are good and it can be demonstrated that you will never need them. It is some sort of super hard pruning. With this feature and some others, Gaviota became extremely good at mating in this endgame, better than any other Adam and I tested (without TBs, of course).

This does not increase any elo, but it was fun to explore this endgame to its full capacity.

I really need to fix this, otherwise it screws perft completely and that is not good. Thanks for reporting it!

Miguel
PS: This is the code. During pre ordering of the moves, if the position is KBNK and the moves is !KBNK_nicemove(), the move is directly eliminated from the list.

Code: Select all

static int kingdist (SQUARE fr, SQUARE to);
static int taxidist (SQUARE fr, SQUARE to);
static int combidist(SQUARE a, SQUARE b) {return taxidist(a,b) + kingdist(a,b);}

#include "gtb-att.h"

#define FOURCORNERS U64(0x8100000000000081)

static bool_t 
KBNK_nicemove (POSITION *po, move_t mv)
{
	unsigned to = MV_TO(mv);
	unsigned fr = MV_FROM(mv);
	unsigned pc = MV_PC(mv);
	unsigned own = po->bi.occ[WH].n_all > 1? WH: BL;
	unsigned opp = Opp(own);
	BITBOARD occ = po->bi.occ[own].all;
	SQUARE 	 oppk = po->bi.occ[opp].king;
	BITBOARD kz = Reach[KING][oppk] | (U64(1) << oppk); /* king zone*/
	unsigned c = MV_COLOR(mv);
	unsigned mvc = Cidx(c);
	int 	 cd0 = combidist(fr,oppk);
	int 	 cd1 = combidist(to,oppk);

	return
		(mvc == opp) 							/* opponent king move */
	||	(0 != ((FOURCORNERS>>oppk) & U64(1))) 	/* opponent king in the corner */
	||	(KNIGHT == pc && (0 != (Reach[KNIGHT][to]&kz) || cd1 < cd0 )) /*N not attacking king zone, moving away*/
	||	(BISHOP == pc && 0 != (B_attacks(to,occ)&kz)) /*B not attacking king zone */
	||	(KING == pc && (cd1 == 4 || cd1 == 5 || cd1 <= cd0 )) /*king moving away*/
	;
}

That is a very creative idea. Thanks for sharing.

Can Gaviota find the mate in any KBNK endgame without any TB and without an yheuristic with this feature ? (by heuristic I mean a different PST to move the defending K in a corner of the colour of the B, for example).

If so it's really elegant. You solve the KBNK by means of better search rather than using eval heuristic.

DiscoCheck has no knowledge of KBNK and it stupidly searches all the moves and doesn't know in which corner to push the king. It uses general PST knowledge to push the king in a corner or an edge, but if the defendor chooses to go in a colour opposite colour to the B, it will take a lot of depth to find the mating line... And only when the mating line is found DC will start to play accurately... Quite pathetic to watch really

[Uri Blass]

(snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

103 ???

The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?

Sorry, my mistake. I can never remember which of the two last numbers in the FEN is the move number and which one is the 50 move counter (this one cannot exceed 100).

The 50 move counter can clearly exceed 100 because there is no rule that the players have to claim a draw when they can do it.

The players have the right to claim a draw when the last 50 moves are with no capture and no pawn move but they also have the right not to claim a draw.

[lucasart]

(snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

103 ???

The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?

Sorry, my mistake. I can never remember which of the two last numbers in the FEN is the move number and which one is the 50 move counter (this one cannot exceed 100).

The 50 move counter can clearly exceed 100 because there is no rule that the players have to claim a draw when they can do it.

The players have the right to claim a draw when the last 50 moves are with no capture and no pawn move but they also have the right not to claim a draw.

What you describe is probably valid in the brain damaged logic that gave birth to the Xboard protocol... Engines forgetting to claim a draw: what kind of idiocy is that ?

UCI GUI is assumed to never send an illegal or game over position to the engine. Draw adjudication is at the hand of the user, who defines in the GUI how he wants adjudication to work (based on score move number, count etc.).

[trojanfoe]

(snipped)
Obviously ccore is correct here. But Gaviota is correct in the original position, as confirmed by Critter here:
(snipped)

Thanks for the tip; switched to using critter as my reference implementation.

Good luck finding the bug.

Cheers! The python script is chundering through positions as I write; I hope it won't take too long...

[Sven]

Draw adjudication is at the hand of the user, who defines in the GUI how he wants adjudication to work

So what if the user defines "no adjudication"? Is an FEN with a fifty-moves count > 100 illegal, then? Should we even depend on that when deciding whether an FEN is illegal?

The PGN standard says:

16.1.3.5: Halfmove clock

The fifth field is a nonnegative integer representing the halfmove clock. This
number is the count of halfmoves (or ply) since the last pawn advance or
capturing move. This value is used for the fifty move draw rule.

and does not include any restriction other than that the number must be nonnegative. So engines should be able to process such an FEN, and should not crash on it. A position where both sides have not claimed a 50 moves draw is not a "game over" position. Even in engine-engine games with adjudication off, it is possible in theory that both sides think they can win so they do not claim the draw.

Sven

[Uri Blass]

(snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

103 ???

The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?

Sorry, my mistake. I can never remember which of the two last numbers in the FEN is the move number and which one is the 50 move counter (this one cannot exceed 100).

The 50 move counter can clearly exceed 100 because there is no rule that the players have to claim a draw when they can do it.

The players have the right to claim a draw when the last 50 moves are with no capture and no pawn move but they also have the right not to claim a draw.

What you describe is probably valid in the brain damaged logic that gave birth to the Xboard protocol... Engines forgetting to claim a draw: what kind of idiocy is that ?

UCI GUI is assumed to never send an illegal or game over position to the engine. Draw adjudication is at the hand of the user, who defines in the GUI how he wants adjudication to work (based on score move number, count etc.).

This is not idiocy and it is not always about forgetting.
The position is not draw if both sides do not want a draw and want to continue to play and they may want to continue to play not because they do not understand that they can claim a draw but because they simply want to win the game and hope the opponent is going to do a mistake
in the evaluation.



Suppose player A play against a player B and after 50 moves of both sides with no pawn move and no capture both see some interesting line when white is sacrificing a piece.

Suppose that every player believe that the line is better for them so both of them do not claim a draw because they hope their opponent is wrong in his evaluation of the sacrifice.

White does not claim a draw because he hopes that black is going to accept the sacrifice in order to win instead of claiming a draw and that it is going to cause him to lose the game.

black does not claim a draw because he hopes that white is going to fall into the trap of sacrificing a piece in order to win the game.