Testing Hash Table with perft

[sje]

For test suites and other goodness, point your Java enabled browser at:

http://idisk.mac.com/chessnotation-Public?view=web

The FEN file for WAC (Win at Chess) can be found in the FEN directory; the EPD version is in the EPD folder.

I'm placing various perft results in "Perft". At the moment, only the initial position is represented, but I'll be adding others later.

[frankp]

Steven

I use Iceweasel (FireFox for Debian) and cannot access your site. Is it just me, something I need to set in my browser, or is the site anti/non-Linux. (I just get a message about recommended browsers.).

Frank

[Teemu Pudas]

Steven

I use Iceweasel (FireFox for Debian) and cannot access your site.

The same with Opera 10 on Windows. It works if I set it to mask as Firefox or IE.

I thought these things belonged on The Daily WTF, not in real life. Really, recommending Internet Explorer 6??

[sje]

Well, it's not anti-Linux as I access it from Ubuntu/Debian using Firefox. It also works with Safari under OS/X and Windows.

I believe that you need to have Java/JavaScript enabled.

[diep]

As a further reference, the file I'm currently using to do some automatic test:
http://cid-b8821720666a55e7.skydrive.li ... tsuite.epd
I'm not the author of this test suite, but I share because was very helpful to me in the first stage of move generator creation...

the original perft was invented by Peter McKenzie in order to test correctness.

But it has grown out of hand.

[sje]

Actually, it was Ken Thompson who first published movepath enumeration results some thirty years ago; the term "perft" is a much later development that (I think) originated with an early Crafty. Ken was also the first to publish the associated unique position counts.

Prior to Thompson's work, the path enumerations for the initial position was known correctly only up to depth three (8,902). For some values of depth greater than six or so, I was the first either to publish or to verify the counts. Others have done perft 12 (and maybe perft 13); someday I'll get around to verify these path counts as well. Considering the length of the calculation and the possibility of machine faults and false positive transposition matches, verification is a good idea.

At the moment I'm re-running perft 11 and will have the results added to the aforementioned file in a day or so.

[Felpo]

As a further reference, the file I'm currently using to do some automatic test:
http://cid-b8821720666a55e7.skydrive.li ... tsuite.epd
I'm not the author of this test suite, but I share because was very helpful to me in the first stage of move generator creation...

the original perft was invented by Peter McKenzie in order to test correctness.

But it has grown out of hand.

Sorry but my english is poor: I was not talking about who invented the perft, but who created the perftestsuite.epg, a precalculated suite of positions very useful to find bugs.

[diep]

Actually, it was Ken Thompson who first published movepath enumeration results some thirty years ago; the term "perft" is a much later development that (I think) originated with an early Crafty. Ken was also the first to publish the associated unique position counts.

Prior to Thompson's work, the path enumerations for the initial position was known correctly only up to depth three (8,902). For some values of depth greater than six or so, I was the first either to publish or to verify the counts. Others have done perft 12 (and maybe perft 13); someday I'll get around to verify these path counts as well. Considering the length of the calculation and the possibility of machine faults and false positive transposition matches, verification is a good idea.

At the moment I'm re-running perft 11 and will have the results added to the aforementioned file in a day or so.

You shouldn't confuse EGTB work with perft.

Perft was 100% setup and promoted by Peter McKenzie.
I remember it like yesterday that he approached me about it.
Later he posted onto rgcc/CCC about it to debug move generators.

Realize also in these days that even commercial engines appeared to have bugs there. Just enumerating positions for indexation isn't the same like systematically counting in iterative manner. You really needed more than a few ply to debug move generator already for en passant, castling and promotion.

Obviously you can do special optimizations for it which are total useless for a well debugged chessprogram.

Some here in this group then started to calculate real deep with it and it grew out of hand as the speed at which some were doing it became an extension of their ...

Vincent

[hgm]

In my experience deep perft are very useful for testing move generators. An advanced move generator can have unexpected bugs that manifest themselves only in very rare situations. (E.g. capturing piece along the pin line when you use special code for pinned pieces, or a typo in a list of moves in a per-square target table.) You would only notice it in the perft of very special positions, that take many moves to set up from any plausible initial positition. (E.g. imagine a bug in the move table for a white King on e8...)

Doing sufficienty deep perfts would be very costly if you did not have an efficient perft program, so speed is a real issue there. Especially as during debugging you need to run the perft several times to zoom in on the error. Perft errors often have the nasty habit of disappearing when you start the perft from a position later along the branch with the error. (At least, they had for me in Joker.)

[sje]

Rough time line:

Early 1970s: Thompson writes a chess program in C that's distributed freely as part of Bell Labs' Unix. This program later evolves into the software side of Belle.

Mid 1970s: Thompson does early DTC tablebases including KQKR and KRKN; these run as the "idle" task on early Unix systems. He also does KBNK but it has a small error giving the max DTM as 32 instead of 33. (He later corrects this.) Around this time his perft numbers (I think one of them also had a very small error) and unique position numbers appear in the typewritten ICCA Newsletter (the predecessor of the ICCAJ).

1987: I start my pre-ANSI C program Spector and perft testing goes in from the start with depths from one to six without a transposition table. Sometime soon thereafter, I ran perft 7 on a Sun 68020 workstation; it takes about 36 hours and a hand edit of the final result is needed because of signed 32 bit overflow. The values appear on mailing list on possibly on rec.game.chess.

Circa 1992: rec.games.chess.computer is voted upon and accepted. Also, the web is started but is slow to grow for a few years. The notation standards are discussed on rgcc and stabilized a few years later.

Circa 1994: I appropriated the word "tablebase" for its current usage. Until this time no one except Thompson had delivered a compehensive set of TBs to the community, and his were available only via CD-ROM. I did not have a CD-ROM drive, so I had no access to Ken's data except for the extrema numbers for some of the classes. (Actually, that was more useful than one might expect.)

Circa 1995: My DTM TBs start to appear, but they are done with an ad hoc generator that is not distributed. My program Symbolic, then competing in New England events, give numerous human opponents their first taste of playing against an omniscient opponent in four man endgames. Soon thereafter, Crafty becomes the second program to use my DTM TBs.

Circa 1996: I write a general TB generator and ship it to anyone with an interest. Many recipients generate five man class data that I couldn't because of my limited hardware resources. A number of commercial programs start to use TB data.

June 1997: The final version of the TB generator source is distributed. It is the last C program that I write other than what I got paid to do. Now while others have done TB work, if one counts only publicly distributed data covering a wide range of classes, then it was first Thomson, then me, and then Nalimov.

Later: I do not recall he exact details, but for perft seven through eleven I posted original or first confirmation numbers on CCC. Soon I will confirm (or refute) perft 12.