Perft(14)

[sje]

Some changes I could make to CookieCat:

2) Change the transposition table to use an additional 64 bits of hash code for safety and a slight slowdown.

I'm working on this now. Other than my own programs, I know of no chess software which uses more than 64 bits of hash. Using insufficiently long hash codes is a sure recipe for false positives as we've seen in several perft(11) calculations.

This is finished, but it was the simplest of the needed tasks.

Each perft transposition table entry has:

1) 8 bits of draft (0-255)
2) 120 bits of hash
3) 64 bits of path count

Note that this will break with big counts at or above 2^64 (~18.4 quintillion).

Revised CookieCat source: https://dl.dropbox.com/u/31633927/Cooki ... kieCat.pas

[Don]

Some changes I could make to CookieCat:

2) Change the transposition table to use an additional 64 bits of hash code for safety and a slight slowdown.

I'm working on this now. Other than my own programs, I know of no chess software which uses more than 64 bits of hash. Using insufficiently long hash codes is a sure recipe for false positives as we've seen in several perft(11) calculations.

This is finished, but it was the simplest of the needed tasks.

Each perft transposition table entry has:

1) 8 bits of draft (0-255)
2) 120 bits of hash
3) 64 bits of path count

Note that this will break with big counts at or above 2^64 (~18.4 quintillion).

Revised CookieCat source: https://dl.dropbox.com/u/31633927/Cooki ... kieCat.pas

Does this conform to my protocol or does it need to be wrapped up to do so?

Don

[sje]

Does this conform to my protocol or does it need to be wrapped up to do so?

See the list of needed changes I posted earlier. There is still work to be done.

[Don]

In that positions my perft take 3 hr 44 minutes.

I am not doing bulk counting, but I am avoiding the test for moving into check when I can detect that easily.

Am I missing some hash table trick? I essentially store the draft and do not overwrite deeper entries. I tried set associative hashing to no avail, it seems best to just overwrite without prejudice except for depth.

I did some analysis and perft(8) based on the komodo implementation takes about 90 seconds in the opening, but could take a couple of hours in a complex position.

Out of curiousity I tested with this position:
[d] r1b1kbnr/pppp1ppp/2n1p3/6q1/6Q1/2N1P3/PPPP1PPP/R1B1KBNR w KQkq - 4 4
(It is the 6 ply position with the highest perft(4).) JetChess produces the answer (8709649140824) on my machine (phenom 1090T @ 3.6 GHz) using 1 GB of hash and 1 core in 2508 seconds. My program, using 5 cores on the same machine, took 571 seconds. This may not be the hardest of the 9 million positions, but is probably close. Most should be noticably faster. So it does seem like a reasonable amount of work on any modern machine.

The mechanism the server will use is to assign one of the N positions at random when a client makes a request for help.

While I see the logic behind the random assignments, assigning a single client consecutive positions (assuming some sane ordering) will increase the chances for hash hits between work units...

[EDIT: oops... unless of course the client is called for each position seperately... ]

-paul

[Don]

Some changes I could make to CookieCat:

2) Change the transposition table to use an additional 64 bits of hash code for safety and a slight slowdown.

I'm working on this now. Other than my own programs, I know of no chess software which uses more than 64 bits of hash. Using insufficiently long hash codes is a sure recipe for false positives as we've seen in several perft(11) calculations.

This is finished, but it was the simplest of the needed tasks.

Each perft transposition table entry has:

1) 8 bits of draft (0-255)
2) 120 bits of hash
3) 64 bits of path count

Note that this will break with big counts at or above 2^64 (~18.4 quintillion).

It is ok because the clients don't need anything above 64 bits for counting.

Revised CookieCat source: https://dl.dropbox.com/u/31633927/Cooki ... kieCat.pas

Does this conform to my protocol or does it need to be wrapped up to do so?

Don

[Don]

Does this conform to my protocol or does it need to be wrapped up to do so?

See the list of needed changes I posted earlier. There is still work to be done.

I have a server and client all working they way I want and it should be able to handle a large number of clients.

I did a perft(13) test - estimating how long by doing 315 pieces of it to 7 ply
and if I were running just my slow single core client on a local server it would take about 4.5 years. Of course this doubles with a verification pass.

I am still unsettled on the verification pass. I wanted to make the rule be that I assigned all work twice - and that I take care to never assign the same piece of work to the same client - but if a client is updated it will get a different name although it might have the same bug. Also, if one client (presumably the fastest and most popular) is run significantly more than another, there will be scheduling issues. So I need to work out that issue.

I think I have the solution. First of all, we should go back to 64 bit keys because I don't think it will matter if your program is modified to use "rotating tables", which means the zobrist keys should be randomly created and different for each run. If we do this, we can use the same binaries for the verification pass because it's impossible (for all practical purposes) to get the same collisions on the same work assignment using different tables.

I would be worried less about using the same clients for the verification run if we did this. Any bugs not related to collisions would likely be revealed by one client getting several runs wrong compared to the other clients and this would be picked up.

64 bit keys should be used if we are going to do a verify pass anyway (but only if you use a rotating table) because even if the larger keys slowed down the program by even 1% it would not pay for itself. And I'm sure it will slow down the program more than this just from the slight overhead of generating more key as well as the smaller table size this would require.

[sje]

Some changes I could make to CookieCat:

1) Change the mtperft (multi-threaded perft) command to use transposition assistance for a big speed increase.

There is a basic conflict between Pascal's strong typing and a variable size transposition table. There is a way around this, but it's not very pretty.

Within the context of Free Pascal, command line argument processing may be goofy under Windows, as may be mutex and thread primitives. I have no way of testing this.

I'm going to work on the ply N unique position generator as any distributed approach is likely to need one of these.

[rbarreira]

Maybe you have thought about this more than I have, but I always thought that a good way to ensure the integrity of results is:

1- Give out work units randomly, not in sequence.
2- Always assign each work unit at least twice (and never to the same person).
3- Don't accept results for a given work unit unless the server has assigned this work unit to that person.

[Don]

Maybe you have thought about this more than I have, but I always thought that a good way to ensure the integrity of results is:

1- Give out work units randomly, not in sequence.
2- Always assign each work unit at least twice (and never to the same person).
3- Don't accept results for a given work unit unless the server has assigned this work unit to that person.

That was the basic plan, but I'm not tracking WHO does the work, but I am tracking with clients do the work. But the server doesn't know the difference between some client and one that is based on it, such as a new version of the same client - and if there is a bug in one there might also be a bug in the other.

But I can track which clients have the most disagreements, if any, between the others and look at their results with suspicion.

Don

[ibid]

I'm going to work on the ply N unique position generator as any distributed approach is likely to need one of these.

I have a program that can do just this -- I can modify it quite easily to output in FEN format.

Another test position:
[d] rnb1kbnr/pp1pp1pp/1q3p2/2p5/3P4/N4P2/PPP1P1PP/R1BQKBNR w KQkq - 2 4
This one has a perft(4) as close to average as possible. perft(8) of this should be 500821820755. Jetchess (single core) needs 238 seconds to do this one on my machine. My program on 5 cores took 60 seconds. A slightly modified version could probably do it in 40-45 seconds. If the 60 second figure should prove average, we are looking at 36 years of cpu time for perft(14), computing each piece twice.

-paul