hash collisions

[Rebel]

[d]1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - -

It's a fun position, I tried other engines, in alphabetic order.

Booot6 - ok
Chest - ok
Crafty 24.1 - hangs
Critter 1.4 - hangs
Doch 1.2 - hangs
Fruit 2.1 - hangs
Gideon Pro (1993) - ok
Komodo - ok
Lc0 - ok
Rofchade - ok
Stockfish - ok

Ed, where did this position come from originally? Was it part of some “review” done on your program back whenever?

Back in 1986 nobody cared about such unrealistic positions, so no, but I was aware and so was the manufacturer. Moving in 1989 to the Archimedes (lots of RAM suddenly) and later the PC (see Gideon Pro) I simply increased the move generation buffer size, problem solved.

On max move width and max depth, I keep a counter in the source code (debug version) and will print out a debug if my engine exceeds the prior maximum ever found. If it does, I put that as the new maximum ever found back into the source. That plus a margin gives me an actual maximum to use as an array size and defensive bounds check. Saying that, I am not at all confident mine won’t bitch at the movewidth of the above test position.

Since I moved away from the 6502 I have in use:

Code: Select all

#define MAX_DEPTH 60
#define MAX_LENGTH 192
int moves[MAX_DEPTH+2 * MAX_LENGTH]

Wrong there. Crafty does not hang. Give it some time.

After 10 minutes still nothing.

Tried on Arena and Chesspartner.

[bob]

Give it time. I can't say exactly how much, but on my MacBook it took a while. I'll start it again and see what it reports for the first move at ply 1, which will also include the ordering time. Edit: it is running now. will give time needed in a bit (on a 2.2ghz intel dual-core i7 using just one thread. No idea how your hardware compares speed wise. I usually see >10M nodes per second using threads on this box.

OK, here's the result:

time surplus 0.00 time limit 30.00 (2:30)
depth time score variation (1)
1 7:33/36.00 Mate 1. Qfxa3#
1-> 7:33/36.00 Mate 1. Qfxa3#

So 7 minutes 33 seconds on my MacBook. If this happened in a real game, I would worry about it and revert to the old way of ordering, which just used Evaluate() + Swap to check piece safety for the moving piece.

[mar]

Well, Cheng needs 6 milliseconds to finish depth 1 (and finds Qcxb1#), there's no excuse for 7+ minutes to finish depth 1.
Like I wrote in another thread (people don't listen): this is qs explosion and all you have to do is to limit minimum qs depth based on root depth. Simple, costs no elo and allows to at least output a move in such impossible positions.

EDIT: Even without this trick it only takes 14 seconds to finish depth 1, so I've no idea what Crafty crunches on for minutes.

[chrisw]

Well, Cheng needs 6 milliseconds to finish depth 1 (and finds Qcxb1#), there's no excuse for 7+ minutes to finish depth 1.
Like I wrote in another thread (people don't listen):

some do, mine is already patched with your suggestion. When I finish the ultimate EPD checker and get back to France, will test on the 30 or 18 queens position. And on Ed’s problematic EPD and make sure there no Elo issue.

this is qs explosion and all you have to do is to limit minimum qs depth based on root depth.

basing off root depth was a very creative idea. If there’s going to be an explosion, it’s going to manifest immediately, your technique factored that in. Smart.

Simple, costs no elo and allows to at least output a move in such impossible positions.

EDIT: Even without this trick it only takes 14 seconds to finish depth 1, so I've no idea what Crafty crunches on for minutes.

[hgm]

One should be careful with hashing, though: if a depth-restricted QS gets hashed, it could later be used to satisfy the request for a QS with a much less severe depth-restriction. And nodes with larger depth could be contaminated by backed-up non-reliable QS scores as well. To do this fundamentally correct one should keep track in the search of which nodes were contaminated by any depth restriction, and refrain from hashing those.

[bob]

Well, Cheng needs 6 milliseconds to finish depth 1 (and finds Qcxb1#), there's no excuse for 7+ minutes to finish depth 1.
Like I wrote in another thread (people don't listen): this is qs explosion and all you have to do is to limit minimum qs depth based on root depth. Simple, costs no elo and allows to at least output a move in such impossible positions.

EDIT: Even without this trick it only takes 14 seconds to finish depth 1, so I've no idea what Crafty crunches on for minutes.

It is not to finish depth 1. It is to sort the ply-1 move list. For a long time I kept a counter in root.c to measure the time used. It was always 0.0 at the end of every game (out of tens of millions.) So in normal games this can't be measured since my timer resolution in Crafty is .01 seconds by design. This q-search explosion comes BEFORE the first move is searched. And every single root move is searched with infinite search bounds so I get an exact score back for ordering...

To see the issue, take your program and just search to depth=1, but after EVERY move reset alpha/beta to +/- infinity. THAT is what lets this explode. Because each and every q-search has to stomp through all those checks and captures, for each root move...

My evaluation here is this is what is known as an "edge condition" that will never be seen in a game. I like the q-search ordering because it actually works reasonably well for those cases where the best move fails low and you have to search through the others. This often gets "the others" at least nearer the front.

[Dann Corbit]

Origin of: 1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - - is:
https://www.yacpdb.org/#search/MVFxUXFR ... LzEvMA==/1

[mar]

It is not to finish depth 1. It is to sort the ply-1 move list. For a long time I kept a counter in root.c to measure the time used. It was always 0.0 at the end of every game (out of tens of millions.) So in normal games this can't be measured since my timer resolution in Crafty is .01 seconds by design. This q-search explosion comes BEFORE the first move is searched. And every single root move is searched with infinite search bounds so I get an exact score back for ordering...

To see the issue, take your program and just search to depth=1, but after EVERY move reset alpha/beta to +/- infinity. THAT is what lets this explode. Because each and every q-search has to stomp through all those checks and captures, for each root move...

My evaluation here is this is what is known as an "edge condition" that will never be seen in a game. I like the q-search ordering because it actually works reasonably well for those cases where the best move fails low and you have to search through the others. This often gets "the others" at least nearer the front.

Don't node counts already give you any resolution you want?
Why would I ever want do a full-width qsearch for each move? You do this at low depths or at any depth? I don't see what good is qsearch ordering at high depths.
My priority is to finish D1 as soon as possible.

[hgm]

There are many variants in which a conventional QS (depth-first all- (or non-bad-)capture search) typically suffers from severe search explosion. In Crazyhouse I have even encountered positions (in real games!) where a QS that extended check evasions exploded to the extent that the QS-depth alone exceeded the maximum number of plies of the total search. A variant with a material composition similar to that of the discussed position would be very prone to such QS explosion.

One really has to implement measures to prevent QS explosion in such variants, to get a working engine. Sometimes it helps to conduct QS in a breadth-first fashion, by subjecting it to a depth limit, which then is iterated over until the result has converged. That is more stable, but sometimes it is still not enough. And at some point it becomes counter-productive to precisely calculate the result of every very complex QS, as this goes at the expense of searching for good alternatives in the full-width search that might avoid the problem altogether.

[Rebel]

Well, Cheng needs 6 milliseconds to finish depth 1 (and finds Qcxb1#), there's no excuse for 7+ minutes to finish depth 1.
Like I wrote in another thread (people don't listen): this is qs explosion and all you have to do is to limit minimum qs depth based on root depth. Simple, costs no elo and allows to at least output a move in such impossible positions.

EDIT: Even without this trick it only takes 14 seconds to finish depth 1, so I've no idea what Crafty crunches on for minutes.

It is not to finish depth 1. It is to sort the ply-1 move list. For a long time I kept a counter in root.c to measure the time used. It was always 0.0 at the end of every game (out of tens of millions.) So in normal games this can't be measured since my timer resolution in Crafty is .01 seconds by design. This q-search explosion comes BEFORE the first move is searched. And every single root move is searched with infinite search bounds so I get an exact score back for ordering...

To see the issue, take your program and just search to depth=1, but after EVERY move reset alpha/beta to +/- infinity. THAT is what lets this explode. Because each and every q-search has to stomp through all those checks and captures, for each root move...

My evaluation here is this is what is known as an "edge condition" that will never be seen in a game. I like the q-search ordering because it actually works reasonably well for those cases where the best move fails low and you have to search through the others. This often gets "the others" at least nearer the front.

Here is what I do since 6502 times, I set the max_depth of QS to 8 and increase it with 2 after each iteration. Maybe something like that can help Crafty to keep your "reset alpha/beta to +/- infinity" system. Or start with a QS_max_depth of 6 when the move count is crazy (say >100) as the position in question has 157 legal moves, not even counting the pseudo illegal ones.