Hi. Please find the source code for my move generator.
http://www.geocities.com/kongsian
Its uses magic bitboards and generates only legal moves.
Here are some perft results compared with QPerft from H.G.Muller. (No hashing, bulk counting at horizon nodes).
For the starting position:
./melee 7
Nodes: 3195901860
Time: 83356
./perft 7
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft(7)=3195901860 (75.530 sec)
For the "KiwiPete" position
./melee 6 "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"
Nodes: 8031647685
Time: 159868
./perft 6 "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft(6)=8031647685 (212.320 sec)
Kong Sian
Move generator
Moderators: hgm, Rebel, chrisw
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move generator
To make it work on Windows, change Clock.h with this:
And add this file:
Code: Select all
//-------------------------------------------------------------------//
// includes
//-------------------------------------------------------------------//
#ifdef _MSC_VER
#include <windows.h>
extern "C" int gettimeofday(struct timeval *tp, void *tzp);
#else
#include <sys/time.h>
#endif
Code: Select all
#include <windows.h>
/* FILETIME of Jan 1 1970 00:00:00. */
static const unsigned long long epoch = 116444736000000000ULL;
/*
* timezone information is stored outside the kernel so tzp isn't used anymore.
*
* Note: this function is not for Win32 high precision timing purpose. See
* elapsed_time().
*/
int
gettimeofday(struct timeval * tp, struct timezone * tzp)
{
FILETIME file_time;
SYSTEMTIME system_time;
ULARGE_INTEGER ularge;
GetSystemTime(&system_time);
SystemTimeToFileTime(&system_time, &file_time);
ularge.LowPart = file_time.dwLowDateTime;
ularge.HighPart = file_time.dwHighDateTime;
tp->tv_sec = (long) ((ularge.QuadPart - epoch) / 10000000L);
tp->tv_usec = (long) (system_time.wMilliseconds * 1000);
return 0;
}
-
- Posts: 388
- Joined: Wed Mar 08, 2006 10:08 pm
Re: Move generator
So, gettimeofday() does not exist in Windows. Instead of implementing it, why not just use one that is available in both Unix and Windows. Something like, clock().
Code: Select all
// note, define start_ as clock_t
inline void Clock::reset() {
start_ = clock();
}
inline Time Clock::elapsed() const {
return (clock() - start_) * 1000 / CLOCKS_PER_SEC;
}
-
- Posts: 313
- Joined: Wed Mar 08, 2006 8:18 pm
Re: Move generator
I happen to know the answer to this one because I've encountered it....CThinker wrote:So, gettimeofday() does not exist in Windows. Instead of implementing it, why not just use one that is available in both Unix and Windows. Something like, clock().
Code: Select all
// note, define start_ as clock_t inline void Clock::reset() { start_ = clock(); } inline Time Clock::elapsed() const { return (clock() - start_) * 1000 / CLOCKS_PER_SEC; }
clock() isn't well defined, or at least is inconsistnatly implemented across platforms and even compilers.
It can be either 'wall clock' or it may be process clock. Meaning your program thinks it's been 60 seconds but in the real world it might be much more than that.
Also, clock() isn't required to have any particular resolution. It may be no better than 1 second resolution even if CLOCKS_PER_SEC says something else. It might just multiply the time value by that to give the impression of it being more.
You never know what you'll get on a new platform or compiler.
Of course, if you limit yourself to a particular compiler & platform, then that isn't a problem.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move generator
Another problem with clock() is that on many implementations it wraps around fairly frequently, producing bizarre results (like thinking you have eons to search when you really have a tiny bit of time).Carey wrote:I happen to know the answer to this one because I've encountered it....CThinker wrote:So, gettimeofday() does not exist in Windows. Instead of implementing it, why not just use one that is available in both Unix and Windows. Something like, clock().
Code: Select all
// note, define start_ as clock_t inline void Clock::reset() { start_ = clock(); } inline Time Clock::elapsed() const { return (clock() - start_) * 1000 / CLOCKS_PER_SEC; }
clock() isn't well defined, or at least is inconsistnatly implemented across platforms and even compilers.
It can be either 'wall clock' or it may be process clock. Meaning your program thinks it's been 60 seconds but in the real world it might be much more than that.
Also, clock() isn't required to have any particular resolution. It may be no better than 1 second resolution even if CLOCKS_PER_SEC says something else. It might just multiply the time value by that to give the impression of it being more.
You never know what you'll get on a new platform or compiler.
Of course, if you limit yourself to a particular compiler & platform, then that isn't a problem.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move generator
If you implement it carefully, like
start = clock();
while(clock()-start < limit) ...
this is never a problem, as long as limit much smaller than the wrap-around interval.
start = clock();
while(clock()-start < limit) ...
this is never a problem, as long as limit much smaller than the wrap-around interval.
-
- Posts: 388
- Joined: Wed Mar 08, 2006 10:08 pm
Re: Move generator
That is why "start" time is set at the start of a game, and game time is computed from there. This is good enough for a single game to last for 49 days.Dann Corbit wrote:Another problem with clock() is that on many implementations it wraps around fairly frequently, producing bizarre results (like thinking you have eons to search when you really have a tiny bit of time).Carey wrote:I happen to know the answer to this one because I've encountered it....CThinker wrote:So, gettimeofday() does not exist in Windows. Instead of implementing it, why not just use one that is available in both Unix and Windows. Something like, clock().
Code: Select all
// note, define start_ as clock_t inline void Clock::reset() { start_ = clock(); } inline Time Clock::elapsed() const { return (clock() - start_) * 1000 / CLOCKS_PER_SEC; }
clock() isn't well defined, or at least is inconsistnatly implemented across platforms and even compilers.
It can be either 'wall clock' or it may be process clock. Meaning your program thinks it's been 60 seconds but in the real world it might be much more than that.
Also, clock() isn't required to have any particular resolution. It may be no better than 1 second resolution even if CLOCKS_PER_SEC says something else. It might just multiply the time value by that to give the impression of it being more.
You never know what you'll get on a new platform or compiler.
Of course, if you limit yourself to a particular compiler & platform, then that isn't a problem.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move generator
That assumes some particular implementation. Here is what the ANSI/ISO C standard says about clock:CThinker wrote:That is why "start" time is set at the start of a game, and game time is computed from there. This is good enough for a single game to last for 49 days.Dann Corbit wrote:Another problem with clock() is that on many implementations it wraps around fairly frequently, producing bizarre results (like thinking you have eons to search when you really have a tiny bit of time).Carey wrote:I happen to know the answer to this one because I've encountered it....CThinker wrote:So, gettimeofday() does not exist in Windows. Instead of implementing it, why not just use one that is available in both Unix and Windows. Something like, clock().
Code: Select all
// note, define start_ as clock_t inline void Clock::reset() { start_ = clock(); } inline Time Clock::elapsed() const { return (clock() - start_) * 1000 / CLOCKS_PER_SEC; }
clock() isn't well defined, or at least is inconsistnatly implemented across platforms and even compilers.
It can be either 'wall clock' or it may be process clock. Meaning your program thinks it's been 60 seconds but in the real world it might be much more than that.
Also, clock() isn't required to have any particular resolution. It may be no better than 1 second resolution even if CLOCKS_PER_SEC says something else. It might just multiply the time value by that to give the impression of it being more.
You never know what you'll get on a new platform or compiler.
Of course, if you limit yourself to a particular compiler & platform, then that isn't a problem.
7.23.2.1 The clock function
Synopsis
1 #include <time.h>
clock_t clock(void);
Description
2 The clock function determines the processor time used.
Returns
3 The clock function returns the implementation's best approximation to the processor time used by the program since the beginning of an implementation-defined era related only to the program invocation. To determine the time in seconds, the value returned by the clock function should be divided by the value of the macro CLOCKS_PER_SEC. If the processor time used is not available or its value cannot be represented, the function returns the value (clock_t)(-1).266)
266) In order to measure the time spent in a program, the clock function should be called at the start of the program and its return value subtracted from the value returned by subsequent calls."
338 Library §7.23.2.2
Note that the data type of clock_t is unspecified as is CLOCKS_PER_SEC. It would be possible, for instance, to have a large value for CLOCKS_PER_SEC and a 4 byte clock_t. At any rate, I have definitely had clock() wrap and in less than 49 days, but it is likely that my implementation was broken.
-
- Posts: 313
- Joined: Wed Mar 08, 2006 8:18 pm
Re: Move generator
My first impression was to say that is very unlikely.Dann Corbit wrote: Another problem with clock() is that on many implementations it wraps around fairly frequently, producing bizarre results (like thinking you have eons to search when you really have a tiny bit of time).
For a 32 bit clock_t, even if you did a million ticks per second, that would still last 71 minutes.
But clock_t doesn't have to be unsigned. It could be signed, which would halve that. Which would also create other issues.
And a 35 minute chess search is not at all unreasonable.
And a clocks_per_sec of a million isn't unreasonable. I don't know of any that do that, but it's not unreasonable with today's processors. You just don't know, since its not specified. (I think some mainframes used to have a microsecond hardware timer. Prof. Hyatt would probably know.)
(I would expect it to be something more useful, such as 1,000 per second at most. Which would limit things to a 24 day search if it's a signed int.)
In fact, it's even possible some clever compiler writer might decide to make that real cpu clocks. Sounds great.... Make clock_t a 64 bit unsigned int and everything is great. Until you have a processor that reduces its fequency to reduce power or heat.
It's just too unspecified to be dependable.
I wouldn't expect the overflow issues to be much of a problem, as long as you know that any timer can overflow and you do elapsed time instead of absolute time. I learned that way back on an 8 bit micro, so I never do absolute time in anything less than a 'double'.
But with the unpredictable nature of how often it might occur, and the other issues (cpu vs. wall-clock, maybe only 1 second accuracy, etc.) clock() is not useful for anything.
It's just another case where the C standard is too vague. They were trying so hard to accomodate existing implementations (their charter required it) and embedded systems and future systems that they left a few holes.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move generator
I think it is resonable to expect that the wrap-around time is longer than any time interval that would plausibly have to be measured by a program. If CLOCKS_PER_SEC was the CPU clock of 2.4GHz, the compiler writer would most certainly not make clock_t a 32-bit type (making the wrap-around occur in less than 2 sec). Trying to guard against that is paranoia at the same level that an int might be only a single bit.