Just made an account to say thank you!

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
bvg
Posts: 1
Joined: Sun Jun 14, 2020 1:15 am
Full name: Bernhard von Gunten

Just made an account to say thank you!

Post by bvg » Tue Jun 23, 2020 7:13 am

Dear forum, it is time to say thank you all!

I've coded my own engine (Java), it was working nicely on a level where you find like tens of thousands of it. But I was happy and continued to work on some more enhancements, transposition tables lately. This is where the problems arised: From time to time the engine did "funny" though bad moves. So you ask the expert: Dr. Google and I landed here, where I was not the only one facing such strange behaviour, and I've read quite a number of threads. This ist what happened to me, well more or less ...

I read in Thread 1: "Checkout your move and zobrist hash generation, this is the most common issue!"
I think: "Nah, come on, this thing is working perfectly! It's something else!"

I read in Thread 2: "Checkout your move and zobrist hash generation, this is the most common issue!"
I say: "No, no ... I've got even Unit tests proving they are working perfectly! It has to be something more exclusive!"

I read in Thread 3: "Checkout your move and zobrist hash generation, this is the most common issue!"
I shout: "Come on! Stop it! I'm a paid developer for 20+ years! I'm able to handle a simple algorithm like this! Tell me where the real problem is!"

Well, needless to say, that I've found the error. I've screwed up and forgot to put the color to move into the zobrist hash key after some refactoring, and yes there is no unit test that does prove it is different between white and black.

Lesson learned: A good test coverage does not show missing code ;)

So, all you people answering questions to newbies! Thank you! You do not only help the people that open threads, but also ignorants like me!

Greetings from Switzerland,
Bernhard

User avatar
hgm
Posts: 24913
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Just made an account to say thank you!

Post by hgm » Tue Jun 23, 2020 8:41 am

Yeah, I recently also had a hash-key problem, which even resulted in very rare engine crashes when a permanent assert detected a move that strayed off board. Turned out I had forgotten to make the Zobrist basis keys different for promotable and unpromotable pieces with the same move. In the rare case that two such pieces were both on the board, and it managed to swap their locations through a transposition, the unpromotable piece could inherit a hash move that was a promotion. This then led to an error cascade: the promotion move applied to the unpromotable piece turned it into a piece with the same piece-list index as an already existing piece elsewhere on the board, one of the two got captured, setting its location in the piece list to an invalid square number encodeing 'captured', and then the other one tried to move using this location when it was encountered on the board...
Get rid of the shit: vote for SHID!

jswaff
Posts: 63
Joined: Sun Jun 08, 2014 10:22 pm
Contact:

Re: Just made an account to say thank you!

Post by jswaff » Tue Jun 23, 2020 1:30 pm

Good test coverage is ... good, but as you say doesn't guarantee the absence of bugs. In this case I would expand my coverage to expose the bug, then write the code to satisfy it.

Another way to look at it is: unit tests (or any kind of tests) only prove the code works as designed, not as it should! :-)

User avatar
lucasart
Posts: 3140
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Just made an account to say thank you!

Post by lucasart » Tue Jun 23, 2020 11:39 pm

bvg wrote:
Tue Jun 23, 2020 7:13 am
Dear forum, it is time to say thank you all!

I've coded my own engine (Java), it was working nicely on a level where you find like tens of thousands of it. But I was happy and continued to work on some more enhancements, transposition tables lately. This is where the problems arised: From time to time the engine did "funny" though bad moves. So you ask the expert: Dr. Google and I landed here, where I was not the only one facing such strange behaviour, and I've read quite a number of threads. This ist what happened to me, well more or less ...

I read in Thread 1: "Checkout your move and zobrist hash generation, this is the most common issue!"
I think: "Nah, come on, this thing is working perfectly! It's something else!"

I read in Thread 2: "Checkout your move and zobrist hash generation, this is the most common issue!"
I say: "No, no ... I've got even Unit tests proving they are working perfectly! It has to be something more exclusive!"

I read in Thread 3: "Checkout your move and zobrist hash generation, this is the most common issue!"
I shout: "Come on! Stop it! I'm a paid developer for 20+ years! I'm able to handle a simple algorithm like this! Tell me where the real problem is!"

Well, needless to say, that I've found the error. I've screwed up and forgot to put the color to move into the zobrist hash key after some refactoring, and yes there is no unit test that does prove it is different between white and black.

Lesson learned: A good test coverage does not show missing code ;)

So, all you people answering questions to newbies! Thank you! You do not only help the people that open threads, but also ignorants like me!

Greetings from Switzerland,
Bernhard
Unit testing for writing casual programs is fine. But chess programming is a bit special and requires *perfect* correctness, not *approximate* correctness. Remember, the engine is going to play millions of moves per seconds (potentially concurrently), so the code that sets up the board, plays (and undoes if you use an undo) moves, generates moves, etc. must be 100% correct. 99.9% is nowhere near good enough. A single bug somewhere in the tree, and the entire search is screwed in unpredictable ways.

And in C or C++, this is not even enough, since undefined behavior is rampant. You also have to systematically run tools like clang sanitizers, or may find one day that updating the compiler "breaks" your code. Or, rather, reveals that your code was always broken, but unexposed by the previous version of the compiler, by pure luck. Another useful thing is to use different compilers, and different optimisation levels, checking that functional signatures are always identical (eg. gcc and clang).

Writing tests is still crucial, but you need to design them differently, with an aim at *proving* correctness (almost in a mathematical sense). Perft is the classic, which allows to find subtle bugs trivially by doing a perft div descent. And for anything that you compute dynamically as moves are played (and possibly undone), you must calculate it two ways: one way incrementally, one way from scratch, and compare. Of course, you only run the slow code in debug compiles using assert() or similar. This is where you would spot a wrong zobrist key, or a wrong PST value, or material key, or whatever you compute incrementally.

You just need to have systematic tests like that, not just unit tests which test a couple of combinations and call this "job done". For example, to prove correctnesss of an undo function, you would run a perft, and at every node of the tree, keep a copy of the board, play (and call perft recursively) then undo the move, and compare to the saved board to ensure that the play + undo is always a no-op. And so on. Think systematic testing => correctness *proof*, rather than "a couple of tests" => unlikely to be incorrect.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Dann Corbit
Posts: 11621
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Just made an account to say thank you!

Post by Dann Corbit » Wed Jun 24, 2020 11:02 am

This is the same brilliant approach as fruit.
If you spend a lot of energy on your program, it will become a world-beater
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

jswaff
Posts: 63
Joined: Sun Jun 08, 2014 10:22 pm
Contact:

Re: Just made an account to say thank you!

Post by jswaff » Wed Jun 24, 2020 4:19 pm

I agree 100%. I do think unit tests are an important tool but as you pointed out they alone aren't enough. I am on my third rewrite of Prophet. In the first version I didn't know much about programming, let alone the value of testing. By the time I started Prophet3 I did have an appreciation of it, but now I've been writing software so long that "how will I test this" is second nature and affects my design. I've been rewriting Prophet4 in fits and starts for nearly a year now. I am using the Google Test stuff for low level Unit tests, in combination with well placed asserts, calculating things in multiple ways... all pieces of the overall strategy that come with experience. And then of course the most difficult (or at least time consuming) test- once I'm satisfied a feature works as designed, was it a good change?

Post Reply