Perft(15) - it will cost you only US$500,000

[sje]

Perft(15) - it will cost you only about US$500,000, or maybe a fifth of that using GPU processing instead of CPU processing.

The estimate comes from a rough calculation based on in part upon prices for Amazon's EC2 (Elastic Compute Cloud) cloud computing rental service.

https://aws.amazon.com/ec2/

Too pricey for me. Also, not a good buy in some cases; renting a 3 GHz, 16 hyperthread CPU with 64 GiB RAM for some four months at about US$1/hour costs about as much as buying the same machine and keeping it.

[hgm]

That makes a lot of assumptions. Smarter perft programs, e.g. incrementally calculating the number of moves in the last ply rather than generating them all, could easily speed up the calculation by a factor 30 compared to existing perft programs. The forelast move does not have that much effect on what the opponent can move. Many moves have no effect at all (if they do not happen to block or unblock enemy sliders, attack squares next to the king, or pin pieces), and their contribution would be equal to perft(1) after null move, which you could calculate once and then use for all such moves.

[Dann Corbit]

Next year: $250,000.00
In 2 years: $125,000.00
In 3 years: $62,500.00
In 4 years: $31,250.00
In 5 years: $15,625.00
In 6 years: $7,812.50
In 7 years: $3,906.25
In 8 years: $1,953.13
In 9 years: $976.56
In 10 years: $244.14
In 11 years: $122.07
In 12 years: $61.04
In 13 years: $30.52
In 14 years: $15.26
In 15 years: $7.63
In 16 years: $3.81
Pretty reasonable by 2031. This assumes that either software or hardware doubles in speed each year. If both double in speed, it will be cheap a lot faster.

What would the cost of Perft(10) been in 1976? IBM Mainframe time and a large disk pack holding 45 MB.

How about in 1906, when we would have had to use pen and paper?

Of course, it is hard to be patient.

[Dann Corbit]

That makes a lot of assumptions. Smarter perft programs, e.g. incrementally calculating the number of moves in the last ply rather than generating them all, could easily speed up the calculation by a factor 30 compared to existing perft programs. The forelast move does not have that much effect on what the opponent can move. Many moves have no effect at all (if they do not happen to block or unblock enemy sliders, attack squares next to the king, or pin pieces), and their contribution would be equal to perft(1) after null move, which you could calculate once and then use for all such moves.

This thing can do perft(11) in one hour:
https://github.com/ankan-ban/perft_gpu

So, if we could get a mere 1296 people with that level GPU running on it, we could get perft(12) in one hour, perft(13) in 36 hours, perft(14) in 1296 hours, and perft(15) in 46656 hours = 1944 days = 5.3 years.
36*36*46656 GPUs =60,466,176 GPUs could solve it in one hour (ignoring coordination time). Sounds like a lot of GPUs, but for sure there are that many out there.

[Ajedrecista]

Hello Dann:

[...]
In 9 years: $976.56
In 10 years: $244.14
[...]

It would be cheaper if we will have major breakthrougs like this one, without needing $488.28.

On a more serious note, I agree with you and I also thought on your example: Perft(3) was a triumph in the '70, '80 or whatever it was computed for the very first time by a machine, and it was costly for sure. Let us wait the HW + SW improvements. We can toy with very accurate estimates in the meantime.

Regards from Spain.

Ajedrecista.

[Dann Corbit]

Hello Dann:

[...]
In 9 years: $976.56
In 10 years: $244.14
[...]

It would be cheaper if we will have major breakthrougs like this one, without needing $488.28.

On a more serious note, I agree with you and I also thought on your example: Perft(3) was a triumph in the '70, '80 or whatever it was computed for the very first time by a machine, and it was costly for sure. Let us wait the HW + SW improvements. We can toy with very accurate estimates in the meantime.

Regards from Spain.

Ajedrecista.

I think that history has shown us that we will compute whatever is possible to compute, as soon as it becomes possible to do it.

Sometimes, we get an early reprise (e.g. Lomonosov tables computed with supercomputer -- would still be way out of range for home PC).

[Henk]

Buying computers is just a waste of money. For after three or five years it's worthless. So I never understood people that bought expensive computers. Biggest problem is these software updates that force us to buy better hardware for otherwise it won't run. They are all thieves.

I saw on TV that if there is no oil anymore then no satellites won't be launched. That means end of internet and perhaps end of these annoying software updates.

Better invest in Lithium or algae.

[matthewlai]

Perft(15) - it will cost you only about US$500,000, or maybe a fifth of that using GPU processing instead of CPU processing.

The estimate comes from a rough calculation based on in part upon prices for Amazon's EC2 (Elastic Compute Cloud) cloud computing rental service.

https://aws.amazon.com/ec2/

Too pricey for me. Also, not a good buy in some cases; renting a 3 GHz, 16 hyperthread CPU with 64 GiB RAM for some four months at about US$1/hour costs about as much as buying the same machine and keeping it.

For something like computing perft, I would look into spot instances.

Basically you buy Amazon's spare compute capacity at about 20% the price, but they can kill your instance any time.

Should be no problem if your program does proper checkpointing/resuming.

c4.4xlarge is cheaper if you don't need so much RAM. $0.88/hr on-demand, $0.55/hr if you pay for 1 year upfront, about $0.15/hr if you use spot instances. Now that's much cheaper than buying your own, taking depreciation into account.

[elpapa]

Next year: $250,000.00
In 16 years: $3.81

I find that hard to believe. You forgot to adjust for inflation.

[sje]

Symbolic already uses bulk counting at penultimate nodes. The observed speedup is a factor of at least about fourteen and with higher values for more complex positions as expected.

Oscar also has bulk counting although it's not a bitboard program.

----

At present I'm looking at writing a perft(6) server. This would run on a dedicated machine on the LAN and would store and serve perft(6) results to the worker machines. The idea is for the server to use a big fat drive holding a vector of binary trees of perft(6) results. Each of the N=2^Q trees would hold values for positions with signatures where the bottom Q bits mapped to the tree's index. With 2^16 trees, the first 16 key comparisons are done with a simple mask; disk access for location/insertion is thus greatly reduced.

Each tree entry is 32 bytes long: signature/key 16 bytes, count 8 bytes, left and right record indices 4 bytes each. For perft(14), I estimate the distinct perft(6) count to be about one billion which would need about 32 GiB storage. Which is not that much, but will increase a lot with projects doing perft(15), perft(16), etc; also, a big increase if the server handles perft(5) results as well.

Using trees instead of transposition tables means that no entries are ever lost. Also, the nice feature of having persistent data retained across server machine power cycles.

One attraction here is that the effect of network latency is nearly zero because each worker machine can have its copy of Symbolic run extra threads so that waiting threads do not make any cores go idle. Symbolic's semaphore/queue mechanism has shown to have less than 1% time overhead even when running active threads at a ratio of eight threads per core.