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.
Handling integer overflow for certain perft() calculations
Moderators: hgm, Rebel, chrisw
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
-
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Handling integer overflow for certain perft() calculatio
Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Handling integer overflow for certain perft() calculatio
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 wrote:Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.
-
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Handling integer overflow for certain perft() calculatio
Well, we already know it by dense estimations to be 3.Rein Halbersma wrote: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 wrote:Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Handling integer overflow for certain perft() calculations.
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:
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.
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)))
Regards from Spain.
Ajedrecista.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Handling integer overflow for certain perft() calculatio
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ý.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Handling integer overflow for certain perft() calculatio
From school I know (Fermat)
(a^p) % p = a % p if p is prime
But that story was about cryptography.
(a^p) % p = a % p if p is prime
But that story was about cryptography.
-
- Posts: 2
- Joined: Mon Oct 27, 2014 7:55 pm
Re: Handling integer overflow for certain perft() calculatio
Python supports arbitrarily large numbers out of the box, why not use that?
>>> 3 * 2 ** 64
55340232221128654848L
>>> 3 * 2 ** 64
55340232221128654848L
-
- Posts: 646
- Joined: Wed Jun 18, 2014 2:30 pm
- Full name: Fahad Syed
Re: Handling integer overflow for certain perft() calculatio
+1Rein Halbersma wrote: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 wrote:Handling by ignoring! Simply add 3 * 2^64 finally after calculating using unsigned long long.