Perft(14)

[Don]

I did a simple distributed version of perft a few years ago, using WCF (SOAP) and entity framework it just took me a day or so to set up.

There are a few issues to solve...

1) Every user should queue up some "work units" locally to avoid going idle in case of network problems. The server side must remember which WUs have been assigned and re-assign them after a certain timeout period, as the user may have quit the project and they will never complete.

The server is hit once to get a small work assignment that could be run on any machine. The chunk of work should be small, perhaps 5 minute to 1 or 2 hours of work at the most.

No need for complicated tracking. I suggest that the assignments are handed out randomly. The server only cares what it actually has received and it does not care where it came from. There is no harm done if an occasional work assignment is handed out an extra time than intended as that is useful for verification.

2) There should be a stats page to make it more interesting. Who is the lead cruncher, cruncher of the day and all that, like SETI.

Yes, that would make it much more fun.

3) You should have a super fast client for this, something coded just for perft. In fact you should probably have 2 independent clients and randomly validate the result not just between programs but also between users, so that every user is checked for credibility. Some users may have faulty hardware or overclock to the extent that it occationally flips a bit, such clients must be detected and denied access.

The client binary does the work - just get volunteers to run it whenever their computer is idle. It does not have to be fast or run on a fast machine. It will just be a binary that you download and run - and to make it fun the binary will report cool statistics on it's progress.

The secret is to get a lot of volunteers - I don't know how many will be willing to run perft.

How much CPU effort was involved in perft(13)? Was this just Steve's machine? Was it a quad or much more than that?

4) Some kind of security, so that a single user cannot intentionally send you garbage data and sabotage the final result. I image something like a username/password and an computed checksum on each message.

No need. Just obfuscate the assignments so that the user is not aware of what "lines" are specifically being worked on. And to verify the results you hand out the assignments twice. Yes, it's twice as much work but it needs to be checked anyway.

But it kinda seems like a lot of work, just for perft..

[SuneF]

The server is hit once to get a small work assignment that could be run on any machine. The chunk of work should be small, perhaps 5 minute to 1 or 2 hours of work at the most.

No need for complicated tracking. I suggest that the assignments are handed out randomly. The server only cares what it actually has received and it does not care where it came from. There is no harm done if an occasional work assignment is handed out an extra time than intended as that is useful for verification.

The thing with perft is that the deeper you go, the relative more efficient the search becomes due to the hashing of sub-trees.
Very small workunits of 5 mins probably won't be as efficient as larger workunits and you would have to brute force it at lot more. For the same reason I also suspect it is faster to allocate all the memory to a single multithreaded computation rather than e.g. 4 independent parallel work units. It could be more than a factor of 2, we may be talking factors of 10 or 100 in computation needed so it's not completely irrelevant

4) Some kind of security, so that a single user cannot intentionally send you garbage data and sabotage the final result. I image something like a username/password and an computed checksum on each message.

No need. Just obfuscate the assignments so that the user is not aware of what "lines" are specifically being worked on. And to verify the results you hand out the assignments twice. Yes, it's twice as much work but it needs to be checked anyway.

You will want to assert that you get a response to a work unit ID that you know you have delegated to the user, otherwise something is obviously wrong. But this is completely trivial to manage with a database so there is no reason not to do it. You'll also want to know which users have crunched what units in order to produce the stats and in case of cheating remove all the dubious results from a specific user. So the information is already there, it could be just a foreign key from the perft table to the user table or whatever.

I don't see any security in hiding the specific line though, security through obscurity is not the way to go All you need to do really is to create an encrypted checksum token for the result, then serverside use the same encryption to verify that the token matches. Not 100% hacker proof but better than nothing.

[sje]

How much CPU effort was involved in perft(13)? Was this just Steve's machine? Was it a quad or much more than that?

My perft(13) effort was separate and wholly independent from Paul's work; mine started earlier but ended later.

It was done on one machine with some verification done on other machines. That one machine has an Intel main board with a Core i7-2600 CPU (quad core @ 3.4 GHz) plus 16 GB RAM.

[Don]

How much CPU effort was involved in perft(13)? Was this just Steve's machine? Was it a quad or much more than that?

My perft(13) effort was separate and wholly independent from Paul's work; mine started earlier but ended later.

It was done on one machine with some verification done on other machines. That one machine has an Intel main board with a Core i7-2600 CPU (quad core @ 3.4 GHz) plus 16 GB RAM.

So really it should be quite doable if you can get many volunteers to help.

I built a distributed autotester and you could use the same principles. Basically the clients connected only to get what they needed and to report results - and most of the time remains off-line - so it's just a mechanism to manage the work. You could easily build this in half a day because the connection stuff is trivial to do.

Here is how I might do it. Assume that you split work into 200,000 units (I don't really know what is reasonable here.) I would require each chunk to be done twice. When an assignment is requested from a client, I would look to see what has not been received yet (ignore what has already been assigned but not yet received) and assign one work unit randomly from that.

If it bothers you that the initial moves are not completed in orderly fashion you can of course subdivided this into 20 separate sub-projects.

I'll build this for you if you supply the binary (one for linux and one for windows) to do perft that follows a simple command line interface protocol and you or someone else provides the server and runs it.

Don

[sje]

I'll build this for you if you supply the binary (one for linux and one for windows) to do perft that follows a simple command line interface protocol and you or someone else provides the server and runs it.

Well, I don't use any Microsoft software, so I can neither produce nor test a Windows executable. At present I use only Linux and Mac OS/X, and I'm starting to get pissed at the latter.

I think that my CookieCat program might be a good candidate for the client side of distributed perft. It is written in Free Pascal and so it should work under Windows, perhaps with a few modifications. What it does not do at present is to chew on command line arguments; it employs a console interface instead. It does have a multithreaded perft which does utilize all available cores.

For some reason I can't recall, the multithreaded perft does not use transposition tables, but there's a single threaded perft which does.

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

The above file is 15,904 lines long. Its internal introductory comments give instructions on building and running. The program will need to have its hash code length increased for seriously large perft calculations.

I have given it a BSD License for the good of us all.

[Don]

I'll build this for you if you supply the binary (one for linux and one for windows) to do perft that follows a simple command line interface protocol and you or someone else provides the server and runs it.

Well, I don't use any Microsoft software, so I can neither produce nor test a Windows executable. At present I use only Linux and Mac OS/X, and I'm starting to get pissed at the latter.

I think that my CookieCat program might be a good candidate for the client side of distributed perft. It is written in Free Pascal and so it should work under Windows, perhaps with a few modifications. What it does not do at present is to chew on command line arguments; it employs a console interface instead. It does have a multithreaded perft which does utilize all available cores.

For some reason I can't recall, the multithreaded perft does not use transposition tables, but there's a single threaded perft which does.

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

The above file is 15,904 lines long. Its internal introductory comments give instructions on building and running. The program will need to have its hash code length increased for seriously large perft calculations.

I have given it a BSD License for the good of us all.

Hi Steven,

It's very easy to produce windows binaries with the linux cross compiler. I you have source code I will do this for you. I will take a look at the pascal source code too and if it gives me no trouble I can probably utilize it. It has been a very long time since I programmed in Pascal, and that was the old turbo pascal of the late 80's. Rexchess user interface was written in Pascal and the engine portion was written in assembler.

So I will build the tool - it will be graphical and have some sort of progress display. I can test it on smaller perft numbers.

The interface I had in mind was simply a perft binary that takes as a command argument a depth and a list of moves in long algebraic.

./perft 10 a2a3 b7b6 e2e4 g7g6

it will do perft 10 FROM this position and return the answer. The server will store the results in a simple sqlite3 database. The server will sum the results using infinite precision math and report progress to the clients for the entire calculation - estimating the progress. So the clients only need to understand 64 bit math.

The client will be a graphical application (which I will build in tcl/tk) which will connect to the perft binary and do communication with the server.

We can do 2 separate runs, the second being a verification run and all results will be tracked to seek out and destroy discrepancies by doing a third run.

Don

[sje]

The interface I had in mind was simply a perft binary that takes as a command argument a depth and a list of moves in long algebraic.

./perft 10 a2a3 b7b6 e2e4 g7g6

it will do perft 10 FROM this position and return the answer.

Better is to send two arguments: a quoted FEN string and an integer ply depth. Also, CookieCat knows only SAN and not long algebraic.

[sje]

Better is to send two arguments: a quoted FEN string and an integer ply depth. Also, CookieCat knows only SAN and not long algebraic.

Better than that is to send three arguments: a command verb, the FEN string, and the depth. The idea is to use different verbs for different perft modes. See CookieCat's command list for further details.

[Don]

The interface I had in mind was simply a perft binary that takes as a command argument a depth and a list of moves in long algebraic.

./perft 10 a2a3 b7b6 e2e4 g7g6

it will do perft 10 FROM this position and return the answer.

Better is to send two arguments: a quoted FEN string and an integer ply depth. Also, CookieCat knows only SAN and not long algebraic.

Yes, that is better.

Don

[Don]

Better is to send two arguments: a quoted FEN string and an integer ply depth. Also, CookieCat knows only SAN and not long algebraic.

Better than that is to send three arguments: a command verb, the FEN string, and the depth. The idea is to use different verbs for different perft modes. See CookieCat's command list for further details.

Just sending the Fen solves the problem, then cookie does not need to understand long algebraic.

By the way, just out of curiosity, how does cookie work with user interfaces if it cannot even understand long algebraic? I think both xboard and UCI expect moves in that format, no?