hash collisions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 24656
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: hash collisions

Post by hgm » Sat Feb 15, 2020 2:28 pm

Terje wrote:
Fri Feb 14, 2020 4:28 pm
Good summary, except the outstanding issue (to me anyway) is which approach - pseudo legal test or handle making/unmaking illegal moves stably - is best. Not in the sense that it's "correct coding practice" or whatever, but best for speed / strength of the engine. Maybe I'll try the latter approach some day to compare, but if someone does in the meantime I'd love to hear the results :)
This cannot be answered with universal generality, because it depends on the engine in many ways. E.g. which fraction of the hash moves will be moves from other positions due to key collisions or SMP corruption. This obviously depends on how many key bits you store in the entry, and whether you already take more general measures against corruption (such as Bob's lockless hashing, or accessing entries atomically). Since in any good design of your hash table the frequency of faulty hash moves will be very small, things you must do in every node to identify them very easily can become counter-productive (in time of speed / Elo). In general it is bad practice to apply cures that are worse than the disease. Crashing is a pretty bad disease, though, so you would probably do anything to prevent occasional crashing, even when this would cost Elo (under the assumption that a crash would be counted as any other loss). But I could even imagine there are people who prefer the Elo over the label 'crash-free', no matter how much worked up others woould get about this.

Which problems with the hash move could cause crashing, and how expensive it would be to test for those will very much depend on what info is included in the hash move, (like: does it contain moved piece or capture victim?), and how your MakeMove / UnMake uses that information. Bob apparently encodes the moved piece, and since I suppose he would not do that if it wasn't used somewhere, e.g. in UnMake to put the piece back, a mismatch here would cause permanent damage to the game. But on the upside is that it can be helpful in weeding out faulty hash moves.

So you would have to do an analysis of what defects in a hash move could cause UnMake to not precisely undo MakeMove, and how MakeMove could produce invalid game states that could cause crashing deeper in the tree. And for each such condition you can then investigate whether the problem can be solved in MakeMove / UnMake by doing things differently, or whether it would be cheaper to add an extra test to intercept hash moves that cause the problem. E.g. if your move encoding contains the capture victim, and UnMake would put back the piece from the move, this would fail if the hash move did not specify the victim that was actually there. But you could disarm that by having MakeMove remember the piece that was captured, and have UnMake put back that. Reading the piece from the board might be just as efficient as extracting it from your move encoding.

chrisw
Posts: 3366
Joined: Tue Apr 03, 2012 2:28 pm

Re: hash collisions

Post by chrisw » Sat Feb 15, 2020 3:23 pm

abulmo2 wrote:
Sat Feb 15, 2020 2:03 pm
chrisw wrote:
Sat Feb 15, 2020 12:08 pm
That’s what all programmers say, and it is not true. A chess engine should be 100% bug free, no excuses for anything else.
What do you call a bug on a chess engine?
  1. Is an engine not returning the best move on a given position buggy?
  2. Is an engine with hash collisions buggy?
  3. Is an engine crashing on illegal input buggy?
  4. Or an engine crashing while playing a normal game with legal input?
(1) is an unreachable goal but it is on what most programmers are working on and each new engine version is expected to play better.
(2) at a small rate seems to not affect the playing strength of a program.
On illegal input it cannot handle (3) , a program should give an error message and eventually quit. But for many users such a behaviour is a bug. A program should not quit but guess the right input from the wrong one. So to crash or to stop working after displaying an error message is considered identical by many, and thus some programmers does not care about illegal input. Moreover, on normal legal inputs such crashes never happen.
(2) may be annoying, but a crash can just be considered a loss in game playing and so is not that much different from (1). If crashes are rare enough they will not even affect the overal strength of an engine.
From a project management and company perspective, anything that is negative to your brand.

Concretely, hangs, crashes, damage to other systems, not returning properly whatever the inputs the user has chosen to give it, however dumb (for example, a position with 32 queens would need to be accounted for, or certainly 18 queens). Software to be completely robust and trapping all and any dumb inputs. I take the view that SF should trap all possible EPD input, even random junk. Is not difficult nor impossible to add the final touches.
With regards to allowing junk tree lines to be generated, on a don’t care basis when could be fixed, that’s a bug. More in the programmer than the program, but a bug. A programmer who argued on that is unemployable.
Basically, if left to programmers to decide, nothing would work properly, and interfacing different systems would be a nightmare. Programmers are at the bottom, QC and managers above them - that’s the point the ensemble begins to produce quality material.

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

Re: hash collisions

Post by hgm » Sat Feb 15, 2020 3:59 pm

So you have your own private definition of 'bug'. In the real world a bug is an unintended program error that would cause a program to function in deviation of its specification. If you dislike the specification, it is just a poor product. (Or, more likely, use of the product for an unitended purpose.)

If the specifications say the result of invalid input (such as an unreachable position of FIDE Chess) to be 'undefined', crashing is within the specification, and is not a bug of the program. If the program is intended for use in an environment where there is an absolute guarantee that it will never result in such input, it cannot even be considered a flaw.

As for internal behavior that is absolutely undetecable by the user... How silly can it get?

chrisw
Posts: 3366
Joined: Tue Apr 03, 2012 2:28 pm

Re: hash collisions

Post by chrisw » Sat Feb 15, 2020 5:31 pm

hgm wrote:
Sat Feb 15, 2020 3:59 pm
So you have your own private definition of 'bug'. In the real world
Hahahahaha! That is really funny, being told by you what is the "real world". In the real world there are buggy programmers. The ones that argue a lot why XYZ can't be done, whey they are not doing XYZ, and how bugs is inevitable and somebody else's fault anyway and it isn't a bug and and and. P45. Door.
a bug is an unintended program error that would cause a program to function in deviation of its specification. If you dislike the specification, it is just a poor product. (Or, more likely, use of the product for an unitended purpose.)

If the specifications say the result of invalid input (such as an unreachable position of FIDE Chess) to be 'undefined', crashing is within the specification, and is not a bug of the program. If the program is intended for use in an environment where there is an absolute guarantee that it will never result in such input, it cannot even be considered a flaw.
I heard these excuses a thousand times and many more just like them. Sloppy programming, failure to integrity check input and output are incompatible with a connected world. Stuff should just work. Period. Plug n Play was a thing back in 1990s to solve just this problem. Integrated design, everything worked with everything else, immediately. Is this the case in comp chess 2020? Nope. Why not? Well, I would call it narcissistic programming, a refusal to add the final touches and to make sure one's stuff conforms with and works with everything else. Result? Wasted time on the part of users.

As for internal behavior that is absolutely undetecable by the user... How silly can it get?
You admitted to it. Now everybody knows. Your engine(s) visit and evaluate impossible parts of the tree, degrading performance in unknown ways, you know it, you could very easily fix it, but you don't care.

Enough. You know my opinion.

bob
Posts: 20916
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: hash collisions

Post by bob » Sat Feb 15, 2020 6:24 pm

Chess programs are pretty large. Not nearly as large as some applications I have worked on (one over 7 million lines of code). Crafty has 42,000 lines of code. ANYBODY that believes/claims such a piece of code can be written bug-free is delusional. We can't even use software verification methodologies on such programs. We can't use traditional testing strategies (branch coverage, path coverage, statement coverage, etc) due to SMP timing variance that can't be predicted or tested thoroughly.

Claiming otherwise is pretty much anti software engineering. You could create one billion unique test cases and still come nowhere near complete testing on a chess program. And you would wait years for such a test to run and still not prove a thing.

chrisw
Posts: 3366
Joined: Tue Apr 03, 2012 2:28 pm

Re: hash collisions

Post by chrisw » Sat Feb 15, 2020 6:46 pm

bob wrote:
Sat Feb 15, 2020 6:24 pm
Chess programs are pretty large. Not nearly as large as some applications I have worked on (one over 7 million lines of code). Crafty has 42,000 lines of code. ANYBODY that believes/claims such a piece of code can be written bug-free is delusional. We can't even use software verification methodologies on such programs. We can't use traditional testing strategies (branch coverage, path coverage, statement coverage, etc) due to SMP timing variance that can't be predicted or tested thoroughly.

Claiming otherwise is pretty much anti software engineering. You could create one billion unique test cases and still come nowhere near complete testing on a chess program. And you would wait years for such a test to run and still not prove a thing.
Nonsense. Chess programs are simple things. 8x8 board, six piece types, you are seriously trying to convince yourself the simple routines for moving stuff around according to known simple chess rules, via a recursive search doing the same things over and over again has to have bugs? It’s a simple mechanical process, entirely verifiable. “Inevitable bugs” are only for sloppy programmers to create excuses for being lazy.
Stockfish has no bugs, btw. Rigorous testing, strict quality control, written in consistent manner. It can be done. Question of attitude.

mar
Posts: 2122
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: hash collisions

Post by mar » Sat Feb 15, 2020 7:04 pm

bob wrote:
Sat Feb 15, 2020 6:24 pm
Chess programs are pretty large.
Chess programs are trivial. Their beauty lies is in the algorithms they use.

I've just looked and Crafty is 24.7k sloc (including 3rd party tablebase code of course), StockFish is 6.2k, Demolito is only 2.2k...
Cheng is 14.6k because I did a bad job, I admit. Still very small programs.
Martin Sedlak

User avatar
xr_a_y
Posts: 1187
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: hash collisions

Post by xr_a_y » Sat Feb 15, 2020 7:11 pm

mar wrote:
Sat Feb 15, 2020 7:04 pm
bob wrote:
Sat Feb 15, 2020 6:24 pm
Chess programs are pretty large.
Chess programs are trivial. Their beauty lies is in the algorithms they use.

I've just looked and Crafty is 24.7k sloc (including 3rd party tablebase code of course), StockFish is 6.2k, Demolito is only 2.2k...
Cheng is 14.6k because I did a bad job, I admit. Still very small programs.
A little more for "cloc" but indeed, very small and strong Demolito

Code: Select all

vivien@serv2:/ssd/engines$ cloc Demolito/src/
      34 text files.
      34 unique files.                              
       1 file ignored.

github.com/AlDanial/cloc v 1.82  T=0.03 s (1164.9 files/s, 135555.2 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C                               16            600            428           2367
C/C++ Header                    16             83             14            324
make                             1              8              6             10
-------------------------------------------------------------------------------
SUM:                            33            691            448           2701
-------------------------------------------------------------------------------

mar
Posts: 2122
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: hash collisions

Post by mar » Sat Feb 15, 2020 7:16 pm

xr_a_y wrote:
Sat Feb 15, 2020 7:11 pm

Code: Select all

vivien@serv2:/ssd/engines$ cloc Demolito/src/
      34 text files.
      34 unique files.                              
       1 file ignored.

github.com/AlDanial/cloc v 1.82  T=0.03 s (1164.9 files/s, 135555.2 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C                               16            600            428           2367
C/C++ Header                    16             83             14            324
make                             1              8              6             10
-------------------------------------------------------------------------------
SUM:                            33            691            448           2701
-------------------------------------------------------------------------------
I used my own line counting tool which doesn't count separate punctuation as code. so

Code: Select all

if (a)
    b=1;

if (a)
{
    b=1;
}

if (a) {
    b=1;
}
will all be counted as 2 lines of code (cloc will count 2, 4 and 3). It doesn't matter much. Yes, Demolito has an extremely clean code base, as I've already stated several times.

From my experience, bugs are strongly correlated to code complexity.

Which program is better, assuming they do the same thing?
A or B, where B has order of magnitude more code?
Which one is likely to contain more bugs?
Which one is easier to maintain?
Martin Sedlak

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

Re: hash collisions

Post by hgm » Sat Feb 15, 2020 7:39 pm

chrisw wrote:
Sat Feb 15, 2020 5:31 pm
Stuff should just work. Period.
Try flying in your car by driving it off a cliff. Should just work. Period.

Don't forget to come back here to tell us how it went! :lol:
chrisw wrote:
Sat Feb 15, 2020 5:31 pm
You admitted to it. Now everybody knows. Your engine(s) visit and evaluate impossible parts of the tree, ...
once in a billion nodes...
degrading performance in unknown ways, ...
correction: speeding up the search in a calculated way
you know it, you could very easily fix it, ...
correction: spoil it
but you don't care.
correction: but I care a great deal to keep it optimal.
Enough. You know my opinion.
All you made clear is that you live in a fantasy world, where everything is the reverse from reality. You did not manage to get a single point right.

Post Reply