Giving you a better chance against multi-processor engine

[Naum]

It is hard to compete against multi-processor engines, but you may be able to do something about it.
If your engine doesn't support the multiple processors, your MP opponent will have a huge advantage on the MP system.
What I am thinking about is, even though my engine doesn't support MP, it could spawn a dummy thread which would just loop forever in order to take away CPU time from my MP opponent. MP engine will still have an advantage, but much less of it.

This could be taken to an extreme I guess. When your opponent is thinking, you could spawn 20 threads and slow it down to a crawl.
I think the guys who hold tournaments should be running a utility that would give them statistics about the CPU usage, in order to catch such cheaters (if any), since this can be done on non-dual systems too.

I didn't test this Anti-MP technique, but I think I am going to try it.

Regards,
Alex

[Uri Blass]

I believe that it is better if the engine has something to detect cheating.

If the program detected that it does not get enough cpu time it should next time refuse to run and tell the user the following text:


*************************************************************
"last time that I ran I did not get enough cpu time at game 1 move 14 and I got only 50% cpu time when I need at least 90% time.

You need to delete my logfile in order to use me again
If you do not like these messages then please take care that I never get less than 90% cpu time in my games by not playing against cheaters or by not doing other activities in the same time of playing,altrernatively you may change my detect cheating parameter to 0 but in that case I will not detect cheating in the future so your results are meaningless"

*************************************************************


Unfortunately I do not know how to detect cpu time so I do not know how to implement that idea.

Uri

[milix]

Isn't it handled by the gui? I see in task manager that the cpu for the engine not in move is 0% and for engine to move is about 99%. And of course the engine not to move is in an input loop so it does something. But even if not I think this is not important. We are 200-300 engine authors in the world, if someone is cheating this way he will cought and then the disgrace for him will be great, greater than any popularity (if any) he will ever get by cheating in any way including cloning.

[Naum]

Hi,

GUI can't handle CPU allowance. This is done by the operating system. When 1 engine spawns 4 threads, and another only 1, these 5 threads look the same to the OS, and OS will allocate to each of them aprox. same CPU time.
If ponder is off engine should be at 0% CPU, because it's waiting for an input. Engine is not looping.
It would be hard to catch a cheater if he for instance starts multiple threads only when it gets into trouble, or maybe only in the middle of the game. People usually check CPU usage when the game starts. That's why CPU usage monitor would be usefull, but in all honesty, I don't beleive that anyone is cheating like this.

Regards,
Alex

[milix]

Hi Alex

If I remeber correctly (by looking Winboard source) the thread priority of the engine not to move is set to 'IDLE' unless hard(=pondering) is set. But I may be wrong here and not remember correctly. If the OS sets also all child processes (if the engine process had created any) to IDLE then there must be no problem.

What I am thinking about is, even though my engine doesn't support MP, it could spawn a dummy thread which would just loop forever in order to take away CPU time from my MP opponent.

and

If ponder is off engine should be at 0% CPU, because it's waiting for an input. Engine is not looping.

When my engine is not to move and waits for input it loops forever until an input arrives. Of course this does not consume any CPU time (0%).

My best wishes,
Anastasios Milikas

[Anonymous]

Unfortunately I do not know how to detect cpu time so I do not know how to implement that idea.

The following program shows how to do it. It will not work under Windows 95 or Windows 98, because they neither have a clock() that returns CPU time, nor do they have the GetProcessTimes. I know of no method, to check for CPU time under W95 et al.

The Standard C method is clock(). Unfortunately, it does not work under Windows (all versions I know), and it returns "wall clock time" instead of CPU time. It works well under Unix, and probably many more OSs.

I think, I neither agree with you, nor with Naum, regarding methods to cleverly detect/avoid unfairness.

Regards,
Dieter

Code: Select all

#include <time.h>

/* Actually, using integral values would be
   better. Note that after really long runtime,
   this will start to fail, while the alternative
   with integers will still work. It would need
   different structs for the Standard C clock method,
   and the Windows specific method */
typedef struct {double timestamp;} CPU_TIME_INFO;

#ifdef _WIN32
#include <windows.h>
static int use_hp=0;
static int has_proc_times=0;
static HANDLE hprocess;

/* Initialize at startup */
/* See, if we have GetProcessTimes working */
void sys_init(void)
{
  OSVERSIONINFO osvi;
  osvi.dwOSVersionInfoSize = sizeof(osvi);
  if (GetVersionEx(&osvi) != 0)
  {
#if 0
    printf("siz %u, major %u, minor %u, build %u, platid %u, ver %s\n",
    osvi.dwOSVersionInfoSize,
    osvi.dwMajorVersion,
    osvi.dwMinorVersion,
    osvi.dwBuildNumber,
    osvi.dwPlatformId,
    osvi.szCSDVersion);
#endif   
    if (osvi.dwPlatformId==VER_PLATFORM_WIN32_NT)
      has_proc_times = 1;
  }
  hprocess = GetCurrentProcess();
}
#endif

#ifdef _WIN32
double cpu_time_stamp(void)
{
  FILETIME ct, kt, et, ut;
  if (has_proc_times && GetProcessTimes(hprocess,&ct,&et,&kt,&ut))
  {
    unsigned __int64 ns100 = *(unsigned __int64 *)&ut;
#if 0 
    /* For some reason, this does not work, while all the nasty casting
       stuff does ... */
    double r =    ((signed __int64)((unsigned __int64)ut.dwLowDateTime
                + ((unsigned __int64)ut.dwHighDateTime)<<32))*1e-7;
    my_printf(INFORMATION, "cpu %u %u, %f %I64u\n", ut.dwHighDateTime, ut.dwLowDateTime, r, ns100);
#endif   
    /* This cast to signed is needed, because (some verions of)
       MSVC cannot cast unsigned _int64 to double. */
    return (signed __int64)ns100*1e-7;
  }
  /* Won't really give CPU time */
  return (double)clock()/CLOCKS_PER_SEC;
}
#else
/* Standard C method */
double cpu_time_stamp(void)
{
  return (double)clock()/CLOCKS_PER_SEC;
}
#endif

void start_cpu_time(CPU_TIME_INFO *p)
{
  p->timestamp = cpu_time_stamp();
}

double elapsed_cpu_time(CPU_TIME_INFO *p)
{
  double r = cpu_time_stamp()-p->timestamp;
  if (r < 0.0) /* Should never happen, of course */
    r = 0;
  return r;
}

/* Windows specific main (the call to Sleep) */
#include <stdio.h>
#include <math.h>
int main(void)
{
  CPU_TIME_INFO cpu_t;
  double ct, r;
  unsigned long n;
  sys_init();
  start_cpu_time(&cpu_t);
  printf("GetProcessTimes should %s work on this computer\n",
         has_proc_times ? "" : "not");
  printf("I will sleep for 10 seconds now\n");
  Sleep(10000);
  ct = elapsed_cpu_time(&cpu_t);
  printf("I used %.g s cpu time until now\n", ct);
  printf("I will do some calculation now\n", ct);
  r = 0;
  for (n=0; n<10000000UL; n++)
    r += sin(n*1e-7);
  printf("result %g\n", r);
  printf("I used %g s cpu time until now\n", elapsed_cpu_time(&cpu_t));
  return 0;
}


[Robert Allgeuer]

When I am organising tournaments I would not want to have an engine doing all sorts of clever and complex tricks to hog, steal or whatever CPU-time, because exactly this behaviour may do the opposite and result in unfair conditions. And in the end this also risks to be not controllable by the tourney director.
I am actually very regularly controlling in the task manager CPU usage and times as well as memory consumptions in order to assure fair conditions, and I would not want a program to interfere there or rendering what I see there useless information.

Robert

[Dann Corbit]

Under the heading of "How to make friends and influence people" I think that dummy CPU grabbers will put you on the "dookie" list for every tester I can imagine. I predict that within one hour of release, it will be discovered what you are doing.

Why not just write an SMP program?
1. Remove all globals that are written to (read only is fine).
2. Remove all non-reentrant junk like strtok()
3. Remove all statics that are written to
4. For anything else, gate it.

You can use pthreads like Amy does, and it will run everywhere.
You could also use ACE or some similar toolkit.

// Here is something for process times under WIN32:
#define WIN32_LEAN_AND_MEAN

#include <windows.h>
#include <winperf.h>
#include <Psapi.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <errno.h>

#ifndef ENODATA
#define ENODATA 61
#endif

#ifndef RUSAGE_SELF
#define RUSAGE_SELF 0
#endif

#ifndef RUSAGE_CHILDREN
#define RUSAGE_CHILDREN -1
#endif

#ifdef _MSC_VER
typedef __int64 longlong;
#else
typedef long long longlong;
#endif

typedef struct timeval {
long tv_sec;
long tv_usec;
} timeval;

typedef struct rusage {
struct timeval ru_utime; /* user time used */
struct timeval ru_stime; /* system time used */
long ru_maxrss; /* integral max resident set size */
long ru_ixrss; /* integral shared text memory size */
long ru_idrss; /* integral unshared data size */
long ru_isrss; /* integral unshared stack size */
long ru_minflt; /* page reclaims */
long ru_majflt; /* page faults */
long ru_nswap; /* swaps */
long ru_inblock; /* block input operations */
long ru_oublock; /* block output operations */
long ru_msgsnd; /* messages sent */
long ru_msgrcv; /* messages received */
long ru_nsignals;/* signals received */
long ru_nvcsw; /* voluntary context switches */
long ru_nivcsw; /* involuntary context switches */
} rusage;

/* The function GetPerformanceInfo() may or may not exist (e.g. Windows 2003 has it) in Psapi.dll */
typedef BOOL(*pfnGetPerformanceInfo) (PPERFORMANCE_INFORMATION pPerformanceInformation, DWORD cb);

int getrusage(int who, struct rusage * usage)
{

HANDLE process_handle;
PROCESS_MEMORY_COUNTERS pmc;
FILETIME create_time,
exit_time,
kernel_time,
user_time;
size_t page_size = 8192;
PPERFORMANCE_INFORMATION PerformanceInformation = {0};
DWORD cb = 0;
HMODULE hm;
pfnGetPerformanceInfo fnGetPerformanceInfo = 0;

hm = GetModuleHandle("Psapi.DLL");
if (hm)
fnGetPerformanceInfo = (pfnGetPerformanceInfo) GetProcAddress(hm, "GetPerformanceInfo");

if (who != RUSAGE_SELF && who != RUSAGE_CHILDREN) {
errno = EINVAL;
return -1;
}
/* Win32 systems do not have a convenient call to enumerate child
* processes that I am aware of. */
if (who == RUSAGE_CHILDREN) {
errno = ENODATA;
return -1;
}
process_handle = OpenProcess(PROCESS_QUERY_INFORMATION | PROCESS_VM_READ, FALSE, GetCurrentProcessId());

/*
* http://msdn.microsoft.com/library/defau ... us/dllproc
* /base/getprocesstimes.asp */
if (GetProcessTimes(process_handle, &create_time, &exit_time, &kernel_time, &user_time)) {
longlong u_time = (*(longlong *) & user_time);
longlong k_time = (*(longlong *) & kernel_time);
/* The units returned by GetProcessTimes are 100 nanoseconds */
usage->ru_utime.tv_sec = (long) (u_time / 10000000);
usage->ru_stime.tv_sec = (long) (k_time / 10000000);
usage->ru_utime.tv_usec = (long) (u_time % 10000000);
usage->ru_stime.tv_usec = (long) (k_time % 10000000);
} else {
/* * Probably a permissions problem */
if (hm)
FreeLibrary(hm);
CloseHandle(process_handle);
errno = EACCES;
return -1;
}

if (fnGetPerformanceInfo && fnGetPerformanceInfo(PerformanceInformation, cb)) {
/* If the call fails, we will use an estimate of 8K per page. Else: */
page_size = PerformanceInformation->PageSize;
}
if (GetProcessMemoryInfo(process_handle, &pmc, sizeof(pmc))) {
usage->ru_maxrss = (DWORD) (pmc.WorkingSetSize / page_size);
usage->ru_majflt = pmc.PageFaultCount;
} else {
/* * Probably a permissions problem */
if (hm)
FreeLibrary(hm);
CloseHandle(process_handle);
errno = EACCES;
return -1;
}

if (hm)
FreeLibrary(hm);

CloseHandle(process_handle);

return 0;
}

typedef struct tms {
FILETIME tms_utime;
FILETIME tms_stime;
FILETIME tms_cutime;
FILETIME tms_cstime;
} tms;

longlong
times(struct tms * timebuf)
{
longlong user;
longlong kernel;
longlong dummy;
if (GetProcessTimes(GetCurrentProcess(), &dummy, &dummy,
&kernel, &user)) {
timebuf->tms_utime = (*(longlong *) &user);
timebuf->tms_stime = (*(longlong *) &kernel);
timebuf->tms_cutime = 0;
timebuf->tms_cstime = 0;

} else {
/* That failed - e.g. Win95 fallback to clock() */
clock_t t = clock();
timebuf->tms_utime = t;
timebuf->tms_stime = 0;
timebuf->tms_cutime = 0;
timebuf->tms_cstime = 0;
}
return timebuf->tms_utime ;
}

#ifdef UNIT_TEST
#include <time.h>
int main(void)
{
size_t i;
rusage ruse;
int r;
double cps_inv = 1.0 / CLOCKS_PER_SEC;
clock_t start,
end;
start = clock();
while ((clock() - start) * cps_inv < 1.0 && i++ < 1000000000 /* clock() can wrap */ )
r = rand();
Sleep(1000); /* We want wall time to be greater than
* process time to ensure it is working OK. */
getrusage(RUSAGE_SELF, &ruse);
printf("rusage user: %ld.%ld system: %ld.%ld\n",
ruse.ru_utime.tv_sec,
ruse.ru_utime.tv_usec,
ruse.ru_stime.tv_sec,
ruse.ru_stime.tv_usec);
return 0;
}
#endif

[José Carlos]

Should look better this way:

Code: Select all

// Here is something for process times under WIN32:
#define WIN32_LEAN_AND_MEAN

#include <windows.h>
#include <winperf.h>
#include <Psapi.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <errno.h>

#ifndef ENODATA
#define ENODATA 61
#endif

#ifndef RUSAGE_SELF
#define   RUSAGE_SELF   0
#endif

#ifndef   RUSAGE_CHILDREN
#define   RUSAGE_CHILDREN   -1
#endif

#ifdef _MSC_VER
typedef __int64 longlong;
#else
typedef long long longlong;
#endif

typedef struct timeval {
    long            tv_sec;
    long            tv_usec;
}               timeval;

typedef struct rusage {
    struct timeval  ru_utime;   /* user time used */
    struct timeval  ru_stime;   /* system time used */
    long            ru_maxrss;  /* integral max resident set size */
    long            ru_ixrss;   /* integral shared text memory size */
    long            ru_idrss;   /* integral unshared data size */
    long            ru_isrss;   /* integral unshared stack size */
    long            ru_minflt;  /* page reclaims */
    long            ru_majflt;  /* page faults */
    long            ru_nswap;   /* swaps */
    long            ru_inblock; /* block input operations */
    long            ru_oublock; /* block output operations */
    long            ru_msgsnd;  /* messages sent */
    long            ru_msgrcv;  /* messages received */
    long            ru_nsignals;/* signals received */
    long            ru_nvcsw;   /* voluntary context switches */
    long            ru_nivcsw;  /* involuntary context switches */
}               rusage;

/* The function GetPerformanceInfo() may or may not exist (e.g. Windows 2003 has it) in Psapi.dll */
typedef         BOOL(*pfnGetPerformanceInfo) (PPERFORMANCE_INFORMATION pPerformanceInformation, DWORD cb);

int             getrusage(int who, struct rusage * usage)
{

    HANDLE          process_handle;
    PROCESS_MEMORY_COUNTERS pmc;
    FILETIME        create_time,
                    exit_time,
                    kernel_time,
                    user_time;
    size_t          page_size = 8192;
    PPERFORMANCE_INFORMATION PerformanceInformation = {0};
    DWORD           cb = 0;
    HMODULE         hm;
    pfnGetPerformanceInfo fnGetPerformanceInfo = 0;

    hm = GetModuleHandle("Psapi.DLL");
    if (hm)
        fnGetPerformanceInfo = (pfnGetPerformanceInfo) GetProcAddress(hm, "GetPerformanceInfo");

    if (who != RUSAGE_SELF && who != RUSAGE_CHILDREN) {
        errno = EINVAL;
        return -1;
    }
    /* Win32 systems do not have a convenient call to enumerate child
     * processes that I am aware of. */
    if (who == RUSAGE_CHILDREN) {
        errno = ENODATA;
        return -1;
    }
    process_handle = OpenProcess(PROCESS_QUERY_INFORMATION | PROCESS_VM_READ, FALSE, GetCurrentProcessId());

    /*
     * http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc
     * /base/getprocesstimes.asp */
    if (GetProcessTimes(process_handle, &create_time, &exit_time, &kernel_time, &user_time)) {
        longlong        u_time = (*(longlong *) & user_time);
        longlong        k_time = (*(longlong *) & kernel_time);
        /* The units returned by GetProcessTimes are 100 nanoseconds */
        usage->ru_utime.tv_sec = (long) (u_time / 10000000);
        usage->ru_stime.tv_sec = (long) (k_time / 10000000);
        usage->ru_utime.tv_usec = (long) (u_time % 10000000);
        usage->ru_stime.tv_usec = (long) (k_time % 10000000);
    } else {
        /* * Probably a permissions problem */
        if (hm)
            FreeLibrary(hm);
        CloseHandle(process_handle);
        errno = EACCES;
        return -1;
    }

    if (fnGetPerformanceInfo && fnGetPerformanceInfo(PerformanceInformation, cb)) {
        /* If the call fails, we will use an estimate of 8K per page.  Else: */
        page_size = PerformanceInformation->PageSize;
    }
    if (GetProcessMemoryInfo(process_handle, &pmc, sizeof(pmc))) {
        usage->ru_maxrss = (DWORD) (pmc.WorkingSetSize / page_size);
        usage->ru_majflt = pmc.PageFaultCount;
    } else {
        /* * Probably a permissions problem */
        if (hm)
            FreeLibrary(hm);
        CloseHandle(process_handle);
        errno = EACCES;
        return -1;
    }

    if (hm)
        FreeLibrary(hm);

    CloseHandle(process_handle);

    return 0;
}

typedef struct tms {
    FILETIME         tms_utime;
    FILETIME         tms_stime;
    FILETIME         tms_cutime;
    FILETIME         tms_cstime;
}               tms;

longlong
times(struct tms * timebuf)
{
    longlong        user;
    longlong        kernel;
    longlong        dummy;
    if (GetProcessTimes(GetCurrentProcess(), &dummy, &dummy,
                        &kernel, &user)) {
        timebuf->tms_utime = (*(longlong *) &user);
        timebuf->tms_stime = (*(longlong *) &kernel);
        timebuf->tms_cutime = 0;
        timebuf->tms_cstime = 0;

    } else {
        /* That failed - e.g. Win95 fallback to clock() */
        clock_t         t = clock();
        timebuf->tms_utime = t;
        timebuf->tms_stime = 0;
        timebuf->tms_cutime = 0;
        timebuf->tms_cstime = 0;
    }
    return timebuf->tms_utime ;
}

#ifdef UNIT_TEST
#include <time.h>
int             main(void)
{
    size_t          i;
    rusage          ruse;
    int             r;
    double          cps_inv = 1.0 / CLOCKS_PER_SEC;
    clock_t         start,
                    end;
    start = clock();
    while ((clock() - start) * cps_inv < 1.0 && i++ < 1000000000 /* clock() can wrap */ )
        r = rand();
    Sleep(1000);                /* We want wall time to be greater than
                                 * process time to ensure it is working OK. */
    getrusage(RUSAGE_SELF, &ruse);
    printf("rusage user: %ld.%ld system: %ld.%ld\n",
           ruse.ru_utime.tv_sec,
           ruse.ru_utime.tv_usec,
           ruse.ru_stime.tv_sec,
           ruse.ru_stime.tv_usec);
    return 0;
}
#endif


[Peter Fendrich]

Why not just write an SMP program?
1. Remove all globals that are written to (read only is fine).
2. Remove all non-reentrant junk like strtok()
3. Remove all statics that are written to
4. For anything else, gate it.

You can use pthreads like Amy does, and it will run everywhere.
You could also use ACE or some similar toolkit.

Ooh, that easy!

Why didn't we all write one at once!
/Peter

[Dann Corbit]

If you design them that way from the start. I have written dozens of threading programs. (Maybe hundreds? Not really sure how many) I write servers all the time.

But if you start off with TSCP or something that does everything with globals, then it is a big, big problem.

[Peter Fendrich]

Dann,
My programs (both Terra and the new Alaric) are threaded...
That isn't the same as utilising a threaded search. The "bug threat" is much more heavy and with limited time you have the choice of a simpler approach that needs less time for every step you take.
I choosed that!
/Peter

[Sune Fischer]

Hi Dann,

I think it's a little more tricky than that. I've written a few other SMP programs but nothing has been even remotely as complex as doing it in chess.

One must have a tree splitter and a tree merger function(s).
One must solve the problem with the lockless hash.
One must figure out how to create and stop threads quickly (usually this is not a performance issue but it might be in chess).
Doing this recursively for N threads doesn't make it simpler.

Then there is also the question of splitting strategy, although for starters something simple would be fine I guess.

If just one of these things have a tiny bug the whole thing will come crashing down.

Considering how complex engines are already and given the many other ways they can be improved I'm not surprised that so few have decided to support SMP.

When AMD releases their dual core and the chip becomes mainstream, we should expect more to be motivated for the SMP challenge.

-S.

[Dann Corbit]

I suspect that this is an area where someone can gain a very significant advantage.

I think that no published splitting strategy is optimal.

[José Carlos]

I once read about starting two threads and give them search independently, with the hash table as only contact point.
I haven't had the time to go multithreaded yet, but I'd like to try this idea first. Looks like a good starting point, avoiding the complexity of splitting strategy and thread creation and destruction inside the tree. I guess the shared hash table might give a nice speedup/effort ratio.

[Anonymous]

Why not just write an SMP program?
1. Remove all globals that are written to (read only is fine).
2. Remove all non-reentrant junk like strtok()
3. Remove all statics that are written to
4. For anything else, gate it.

Short instructions, lot's of work (when changing an engine, that was not written with SMP in mind, and lots of globals).

What does "gate it" mean?

[...]
> // Here is something for process times under WIN32:
[...]

Seems not much difference, to what I have shown, arguably a bit less efficient (in case, it is called often). Suffers from exactly the same things, I had mentioned in my post (nasty, in principle incorrect cast; not working correctly under W95/W98).

Does anybody know a solution for W95/W98? There must be something. You can download the trial version of Larsen Taskinfo, and it wil show CPU time for all processes under W98. Is it done on really low level (by something like a driver)?

Can anybody with W98 try the code Dann showed, and the code I have shown? In the code I have shown, please also change

if (has_proc_times && GetProcessTimes(hprocess,&ct,&et,&kt,&ut))

to

if (GetProcessTimes(hprocess,&ct,&et,&kt,&ut))

What does happen? No difference or perhaps even an exception?


Regards,
Dieter

[Dann Corbit]

When I say gate it, I mean:

Critical Section or Semaphore

[Dann Corbit]

Seems not much difference, to what I have shown, arguably a bit less efficient (in case, it is called often). Suffers from exactly the same things, I had mentioned in my post (nasty, in principle incorrect cast; not working correctly under W95/W98).

It is not better than what you did. The only reason I supplied it is that Unix people will already be using that interface for process verses wall time, so that they can use what I gave as a drop-in replacement.

I imagine that there are better ways to do it.

[Dan Honeycutt]

One must solve the problem with the lockless hash.

Hi Sune:
Having never done it I speak from ignorance. But I read Dr. Hyatts paper on lockless hash and that seemed pretty straightforeward. Am I missing something?

(Everything else you list I agree 100%)

Dan H.

[Peter Fendrich]

Hi Sune:
Having never done it I speak from ignorance. But I read Dr. Hyatts paper on lockless hash and that seemed pretty straightforeward. Am I missing something?

(Everything else you list I agree 100%)

Dan H.

No but it's just one tiny little detail out of all the others to think about. I'm sure Sune mentioned it just as an example.
/Peter