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]

[mar]

GC has advantages and drawbacks. In Amoeba, the main advantage I found, is I do not have to worry much about memory management, memory leaks, etc. The main drawback is it make the runtime bigger. Amoeba is not really concerned by program pause, slowdown, etc. that a GC may cause.

You can still get memory leaks with GC - if you forget to zero some reference that goes all the way down to one of the GC roots.

Your wrong here. The D language has attributes to make it explicitly safe or not (@safe, @trusted, @system, scope return, ...) https://dlang.org/spec/memory-safe-d.html. Right now it is unsafe by default, but future compiler versions should make code be safe by default. https://github.com/dlang/DIPs/blob/1b70 ... DIP1028.md

Interesting, I didn't know that D had anything like this. I was wrong indeed.
Memory safety is a big selling point so going safe by default makes sense,
depends on how strict the limitations really are.
One of the points in the spec says "No taking the address of a local variable or function parameter.",
yet in the example they take pointer to an element of a static array and pass it to a trusted function,
perhaps that's an exception but I find it a bit confusing.

[Alayan]

The main drawback is it make the runtime bigger. Amoeba is not really concerned by program pause, slowdown, etc. that a GC may cause.

For a chess engine, the bigger runtime is a serious issue.

For two functionally identical chess engines, the faster version's advantage is not only in the elo boost from seeing more nodes, which is useful but gets less important as the TC increases.

The hidden advantage of the faster version is in testing. For equal game quality and depth, you can use a shorter TC which means you can play more games and test more patches faster. For equal TC, you get higher depth, which means you're working to tune your engine to what happens at higher node counts and depth. This means the patches passing testing have a better long TC behavior on average.

For engines that aren't close to the top, shorter TC for more games and faster patch testing is probably the most efficient way to use more speed, as there is so much low-hanging fruit to catch that the short TC is good enough. Hardware time for testing patches remains one of the main limitations on engine improvement.

[bob]

As lone individuals writing chess engines we don't have the resources to do expensive, time consuming test methodologies, beta test procedures before we release.

In writing Amoeba, as a lone individual, I spent 99.9% of my time testing and 0.1% writing code. I have limited financial resources, but I have an invaluable resource: time.

Can you elaborate what the testing is about?

I am mostly testing for enhancements with SPRT; using my own tournament manager.
My development version is also quite different to the release version, as it contains many testing code: perft, epd test, etc.
I also use a language that is probably better at reducing bugs (the D language), as it uses a garbage collector and help to write things in less line of codes.
Is my program bug free? Unfortunately not. Probably half of the Elo of my program came from bugs removal and I guess there are still many of them to suppress.

Year by year your engine will become more and more robust. Tools like MRi may speedup that process.

This is only true IFF (if and only if) you do not add any NEW features. But you are really thinking far too narrowly here. there are lots of possible types of bugs:

(1) syntax - easy to find since compiler points 'em out.

(2) simple things like array bounds violations. There are programs that will catch MOST (but not all) of these (pointers cause issues).

(3) pointer errors. Up to you for the most part. Pretty easy to do silly things like pass a null pointer to a procedure that expects a pointer to something useful. Hard to detect this. And to have a chance you have to compile the entire source in one chunk. Probably not on a piece of code I worked on for Los Alamos back in the 80's, code that was over 7 million lines long.

(4) logic errors. No software is ever going to catch that until you can provide perfect specifications in addition to perfect code. And now you have yet another thing to debug, the specifications. This is about 99% of my bugs. mal-formed test to recognize an open file, or a backward pawn, or whatever.

(5) parallel threading errors. No software will catch these, ever. Gross ones, maybe. Subtle race conditions? Never. Unless you demand an atomic lock for EVERY shared variable and you require one specific order for memory updates for every group of shared values that get updated in parallel. This leads to forgetting about parallel search since the restrictions would make it useless.

(4) and (5) are the ones that give me concern. Programs that cause a crash are usually straightforward to find and fix, excepting parallel race conditions which can be one's worst nightmare to try to find. Programs that just don't produce an optimal answer are much harder to debug since there is no obvious bug showing up in output.

I can only speak for myself, but when I add code, I usually add errors that I have to find and fix. If not, why did I have errors in the original code. I'm still the same person with the same skills.

[bob]

[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. It orders root moves by making each one and then doing a zero-ply search by calling Quiesce(). With -inf,+inf bounds so that I get a real score to order moves by. In this position there are a "few" captures and checks, which Crafty follows deeply into the q-search. And on my MacBook it takes MINUTES to start the search. But it doesn't hang.

Older versions of Crafty won't even do that if you pick a version prior to the switch to using Quiesce() for the ordering...

[bob]

[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]

Why not at least use the known upper bound which I think is 208 so far. Nobody has produced a position with more legal moves than that, so far, although who knows if that can be exceeded. Also the "int moves[]" is not cache friendly since there are large gaps between the moves for each ply. I use a pointer to the start of the move list for each ply, which is in one shared array, IE pointer[1]=moves[0], pointer[2]=moves[20] if we are on the first move. Now everything is stuck together in consecutive addresses.

[bob]

Was I wrong when I pointed out that a released version of your program had a bug that let it hang or make an illegal move.

Yes, you were wrong, you must have missed my post that addresses the issue.

What does wrong test methodology mean? That it failed to find a bug? So you had a bug that was not caught by testing, so it really wasn't a bug?

Switching from Arena to cutechess testing without the option restart=on gave me unreliable results.

I would agree with that. In fact, Crafty does not accept the "new" command. I decided it was too tricky and could introduce additional bugs. It produces an error if you send it "new". All of my testing (which uses my own referee program) explicitly restarts both engines after each game concludes.

[bob]

If you keep parameter lists small, you can exhaustively test s function for every input bit pattern possible. There are computer systems used for verification. You can also exhaustively test a domain and the check the input range so that the function or method does not violate the domain.

Program proving is not impossible. It's just expensive.

Exactly.

When I write new code or make changes especially when it's complex it may happen I only type a few lines and then test it before continuing Same for a new relative simple but large (say 50 lines of code) routine, I still hack it into small pieces, check and double check. Time consuming and often unnecessary, but it works for me.

Again, this is meaningless. I have changed just one line of code in parallel search. And later discovered VERY subtle side-effects that testing did not catch. Problem is you add a few lines in the middle of thousands of lines. Testing all side-effects is not a small task.

[abulmo2]

The main drawback is it make the runtime bigger. Amoeba is not really concerned by program pause, slowdown, etc. that a GC may cause.

For a chess engine, the bigger runtime is a serious issue.

For two functionally identical chess engines, the faster version's advantage is not only in the elo boost from seeing more nodes, which is useful but gets less important as the TC increases.

I am afraid there is a misunderstanding. I was speaking about the size of the D runtime, not about the time to run my program. Amoeba is very fast and can play at very fast bullet time. The D runtime is a piece of software associated with the D standard library that manages program startup and shutdown, the garbage collector, etc.

[Rebel]

As lone individuals writing chess engines we don't have the resources to do expensive, time consuming test methodologies, beta test procedures before we release.

In writing Amoeba, as a lone individual, I spent 99.9% of my time testing and 0.1% writing code. I have limited financial resources, but I have an invaluable resource: time.

Can you elaborate what the testing is about?

I am mostly testing for enhancements with SPRT; using my own tournament manager.
My development version is also quite different to the release version, as it contains many testing code: perft, epd test, etc.
I also use a language that is probably better at reducing bugs (the D language), as it uses a garbage collector and help to write things in less line of codes.
Is my program bug free? Unfortunately not. Probably half of the Elo of my program came from bugs removal and I guess there are still many of them to suppress.

Year by year your engine will become more and more robust. Tools like MRi may speedup that process.

This is only true IFF (if and only if) you do not add any NEW features. But you are really thinking far too narrowly here. there are lots of possible types of bugs:

Most of us (if not anyone) here are not your inexperienced students

(1) syntax - easy to find since compiler points 'em out.

(2) simple things like array bounds violations. There are programs that will catch MOST (but not all) of these (pointers cause issues).

(3) pointer errors. Up to you for the most part. Pretty easy to do silly things like pass a null pointer to a procedure that expects a pointer to something useful. Hard to detect this. And to have a chance you have to compile the entire source in one chunk. Probably not on a piece of code I worked on for Los Alamos back in the 80's, code that was over 7 million lines long.

(4) logic errors. No software is ever going to catch that until you can provide perfect specifications in addition to perfect code. And now you have yet another thing to debug, the specifications. This is about 99% of my bugs. mal-formed test to recognize an open file, or a backward pawn, or whatever.

(5) parallel threading errors. No software will catch these, ever. Gross ones, maybe. Subtle race conditions? Never. Unless you demand an atomic lock for EVERY shared variable and you require one specific order for memory updates for every group of shared values that get updated in parallel. This leads to forgetting about parallel search since the restrictions would make it useless.

(4) and (5) are the ones that give me concern. Programs that cause a crash are usually straightforward to find and fix, excepting parallel race conditions which can be one's worst nightmare to try to find. Programs that just don't produce an optimal answer are much harder to debug since there is no obvious bug showing up in output.

I can only speak for myself, but when I add code, I usually add errors that I have to find and fix. If not, why did I have errors in the original code. I'm still the same person with the same skills.