Move generator

[kongsian]

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

[Dann Corbit]

To make it work on Windows, change Clock.h with this:

Code: Select all

//-------------------------------------------------------------------//
//              includes
//-------------------------------------------------------------------//
#ifdef _MSC_VER
#include <windows.h>
extern "C" int gettimeofday&#40;struct timeval *tp, void *tzp&#41;;
#else
#include <sys/time.h>
#endif

And add this file:

Code: Select all

#include <windows.h>
/* FILETIME of Jan 1 1970 00&#58;00&#58;00. */
static const unsigned long long epoch = 116444736000000000ULL;

/*
 * timezone information is stored outside the kernel so tzp isn't used anymore.
 *
 * Note&#58; this function is not for Win32 high precision timing purpose. See
 * elapsed_time&#40;).
 */
int
gettimeofday&#40;struct timeval * tp, struct timezone * tzp&#41;
&#123;
    FILETIME    file_time;
    SYSTEMTIME  system_time;
    ULARGE_INTEGER ularge;

    GetSystemTime&#40;&system_time&#41;;
    SystemTimeToFileTime&#40;&system_time, &file_time&#41;;
    ularge.LowPart = file_time.dwLowDateTime;
    ularge.HighPart = file_time.dwHighDateTime;

    tp->tv_sec = &#40;long&#41; (&#40;ularge.QuadPart - epoch&#41; / 10000000L&#41;;
    tp->tv_usec = &#40;long&#41; &#40;system_time.wMilliseconds * 1000&#41;;

    return 0;
&#125;

[CThinker]

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;
}

[Carey]

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;
}

I happen to know the answer to this one because I've encountered it....

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.

[Dann Corbit]

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;
}

I happen to know the answer to this one because I've encountered it....

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.

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).

[hgm]

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.

[CThinker]

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;
}

I happen to know the answer to this one because I've encountered it....

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.

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).

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]

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;
}

I happen to know the answer to this one because I've encountered it....

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.

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).

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.

That assumes some particular implementation. Here is what the ANSI/ISO C standard says about clock:

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.

[Carey]

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).

My first impression was to say that is very unlikely.

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.

[hgm]

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.