A way to do simple draw detection in a chess program

[adams161]

Often chess programmers working on an app from scratch ask is there any way to do draw detection without implementing transposition tables. It can be costly rating wise for a new program to fall for a lot of draws. I usually see them told no. I know Bob Hyatt has given that answer contending search only returns one reliably tested move.

But all my Pulsar Chess Engine app has ever done since maybe 1999 is check after search completes at root if the move suggested by engine is a duplicate fen and if so zero the moves score. And i've watched it for 25 years get out of hundreds of draws successfully and can barely recall any failings or when it even lost one of these games since it often plays lower rateds.

But there is a point of why the next chosen move is any good and not random. I thought about it, It's probably because i do root move ordering. I need it to make partial depth searches work and that has been in place in pulsar early on. So its probably throwing out the drawing move in cases where it does have a score above zero for another root ordered move from an earlier search. Or if it was losing and sees that 0 it will just make the draw move.

And if anyone wants, try messing around getting pulsar to draw. Its in review now at both Google and Apple for final fix to new flip feature but available at:

Mac/iOS
https://apps.apple.com/us/app/pulsar-ch ... d839640447

Android/Chromebook
https://play.google.com/store/apps/deta ... n_US&gl=US

cheers,
Mike

[Uri Blass]

of course there are ways to detect repetitions without hash tables.

You do not need hash tables to find if there is a circle or not in the last non pawn and non capture moves.

For example
a1-d1 a8-d8 d1-c1 d8-c8 c1-a1 c8-a8 is repetition and you do not need hash tables to see it but only some function to find that you had some type of circle based on the fact that the path of every piece got to the same square that it was earlier.

[hgm]

In my experience almost all undesirable repetitions are 4-ply loops; when you start to repeat positions from longer ago it usually means there is no way to force progress, and the game is a genuine draw.

So a poor-man's solution to draw detection is to test whether a move reverses the move from 2 ply earlier (and none of the three moves is a capture), before you search it. You can do that both in the tree and at game level. When it does, you should either refrain from searching the move, and assign it a draw score (if the previous move also reverses the move 3 ply earlier), or heavily penalize it when the side to move is ahead. (Because even if it isn't a repetition yet, it allows the opponent to also take back his latest move, and reach a repetition that way). E.g.divide the score returned by the search by 2 when it is positive, and conduct that search with doubled alpha and beta when these were positive.

[lithander]

When you can still access relevant information of the previous positions it becomes as easy as this:

Code: Select all

private bool IsRepetition(int ply)
{
	ulong hash = Positions[ply].ZobristHash;
	for (int i = ply - 4; i >= 0; i -= 2)
	{
		if (Positions[i].ZobristHash == hash)
			return true;

		//captures and pawn moves reset the halfmove clock for the purpose of enforcing the 50-move rule and also make repetition impossible
		if (Positions[i].HalfmoveClock <= 1)
			return false;
	}
	return false;
}

Because you can skip 4 positions then skip every 2nd ply and only have to look until the halfmove clock resets what naively sounds like "looping over all past positions" is in practice only a handful of loop iterations and very fast.