Handling integer overflow for certain perft() calculations

[sje]

Handling integer overflow for certain perft() calculations

The value of perft(14) is estimated to be greater than 3*2^64, so some kind of extended integer precision treatment is required for handling intermediate sums to form a grand total. In the past, I've used the bc utility or Lisp, but it would be helpful to have a more portable solution which didn't require too many manual steps.

So, I've taken the GPL CLN package from http://www.ginac.de/CLN/ and have gotten it to work under Mac OS/X. My plan is to write a small C++ utility which will read Perft(14) project result file format data and produce correct extended precision calculation results for various averages, sums, and other derived statistics.

When I get it working, I'll post it here so that others may give it a try.

[SMIRF]

Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.

[Rein Halbersma]

Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.

Yes, if you *know* the carry, you can just drop it and keep the remainder modulo 2^64. Or just write a 128- bit int class.

[SMIRF]

Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.

Yes, if you *know* the carry, you can just drop it and keep the remainder modulo 2^64. Or just write a 128- bit int class.

Well, we already know it by dense estimations to be 3.

[Ajedrecista]

Hello:

I proposed a very intuitive method for estimate the carry using MonteCarlo estimates:

Re: KBNk ---> perft(20) result.

Other thing that comes to my mind is add a counter for count the number of times that an overflow happens. A simply pseudocode could be:

Code: Select all

integer :: k  ! It can be a 32-bit integer for today needs.
integer :: perft  ! 64-bit integer. From -[2^(63)] to [2^(63) - 1].
real :: perft_as_real

k = 0  ! Initial value.

! All the stuff of counting positions, if the counter is updated by each move (I mean, one by one).

if (perft == -(2^(63))) then
  k = k + 1
end if

perft_as_real = 1.0*(perft + k*(2^(64)))

It is a clumsy pseudocode that could work. An if statement could be terribly slow. Is there something like a when statement or is it totally equivalent and slow? I am definitively not a programmer.

Regards from Spain.

Ajedrecista.

[AlvaroBegue]

In counting legal positions for the game of go, John Tromp used the technique of computing the result modulo several primes, and then using the Chinese remainder theorem to get back the complete answer. The idea seems to have been originally due to Michal Koucký.

[Henk]

From school I know (Fermat)

(a^p) % p = a % p if p is prime

But that story was about cryptography.

[fogleman]

Python supports arbitrarily large numbers out of the box, why not use that?

>>> 3 * 2 ** 64
55340232221128654848L

[vittyvirus]

Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.

Yes, if you *know* the carry, you can just drop it and keep the remainder modulo 2^64. Or just write a 128- bit int class.

+1