Programming advice (how to interrupt/cancel a search?)

[Roman Hartmann]

Hi all,
finally I found some time to add a working search to my 'engine'. So far my alpha-beta search is only looping till a certain depth is reached and there are no extensions at all yet. Still roce draws against cassandre most of the games (cassandre doesn't know about the 3-fold either) and even wins from time to time. So it seems I'm making some progress
But I'm lacking the proper programming knowledge to cancel/leave the for loop during the search (i.e. move now/stopp/cancel, searching a certain time rather than searching to a certain depth). I want to implement time management and add the analyze feature.
What's a simple but yet clean solution for this? signal() ? What's the easiest/cleanest solution that works on a win32 system?
I'm programming in C and use the MS Visual C Express Edition to compile.

best regards
Roman

[Pallav Nawani]

First you need to check for timeout/user input at regular intervals. Some people have a counter for this and check every few number of nodes. I have given my approach below. There is a slight subtlety if you use my method: TIMENODES must be a power of 2, and if you want to check for timeout every x nodes, the value of TIMENODES should be x/2.

Code: Select all

/* Pseudocode for main search, note that we are not checking for timeout
    in the quiescence search. */

int search(int alpha, int beta)
{
    nodes++;         /* Increment node count */
    if(TIMENODES&nodes) {
        if(check_time() == TIME_OVER) {
           abort = 1;   /* Abort is a global variable, if its value is 1, it signifies that the search was aborted, and so the score from this search is not reliable */
           return 0;
        }
       
        /* This piece of code is useful when you are doing analysis/pondering */
       if(check_for_input()) {
          handle_input_if_possible();
          if_user_ask_for_abort() {
              abort = 1;
              return 0;
          }
      }
      .
      .
       More search stuff


}


You can also take a look at the source code of some open source engines if you want. Will be useful if you want to see how to write the code for check_for_input() function.

Hope that helps
Pallav

[Roman Hartmann]

Hi Pallav,
thanks for your answer. Your suggestion looks like a good solution to my problem.
I rather try to keep away from looking at other sources that's the main reason I asked here.

thx again
Roman

[Zach Wegner]

Hello Pallav,

I think your method works, but with a slight modification. The condition (TIMENODES&nodes) will be true for half of all the nodes. I think what will work for this purpose is !((TIMENODES-1)&nodes). This is true only when all the bits below TIMENODES are not set, so only once per TIMENODES nodes.

Regards,
Zach

[Sven Schüle]

Hi, Zach,

just a small note on your note ... I agree to everything you wrote in principle. But if TIMENODES is a compile-time constant and a power of 2 then

Code: Select all

if (!(nodes % TIMENODES)) { ...

should be fast enough, probably even faster than:

Code: Select all

if (!(nodes & (TIMENODES-1)) {...

But even if the value of TIMENODES is not known for the compiler (so that he can't transform the modulo into a shift) then this looks preferrable to me because it is the most simple and straightforward way of writing "every X nodes".

Sven

[Anonymous]

Hi, Zach,

just a small note on your note ... I agree to everything you wrote in principle. But if TIMENODES is a compile-time constant and a power of 2 then

Code: Select all

if (!(nodes % TIMENODES)) { ...

should be fast enough, probably even faster than:

Code: Select all

if (!(nodes & (TIMENODES-1)) {...

But even if the value of TIMENODES is not known for the compiler (so that he can't transform the modulo into a shift) then this looks preferrable to me because it is the most simple and straightforward way of writing "every X nodes".

Sven

Sven, I am not saying, that it will make a lot of difference, but modulo is typically the slowest operation on computers (together with devide - often, for example on x86, both devide and modulo are done together by one opcode. On some computers, modulo is done by some subroutine calls). Be very careful, when the node counter is 64 bit - the the modulo will probably be very ineffecient on every 32-bit computer.

I use:

Code: Select all


/* at some suitable place before calling absearch() initialize checknodes */

absearch(...)
{
   ...
   ++node_counter;
   if (--checknodes <= 0)
  {
    /* Do time over and input available checks here */
    /* And reset checknodes to some suitable value.
        The actual value may be calculated dynamically */
  }
  ...



This should not be slower than the and method, should be less prone to coding errors (not the first time, I saw code in fora, that got the and method wrong), and even is a bit more general, because you don't need to have a constant number of nodes, when you want to check. (Or at least you save the hazzle, to calculate the closest power of two, to the actual number).

The overhead of the above method is one branch, and one decrement in every call to absearch (no real need to do it in qsearch). Certainly faster than modulo, probably not slower than the and method.


Cheers,
Dieter

[Pallav Nawani]

Hello Pallav,

I think your method works, but with a slight modification. The condition (TIMENODES&nodes) will be true for half of all the nodes. I think what will work for this purpose is !((TIMENODES-1)&nodes). This is true only when all the bits below TIMENODES are not set, so only once per TIMENODES nodes.

Regards,
Zach

Hi,

You are right of course, and I can't image why I did not realise this

Pallav

[Sven Schüle]

Hi Dieter,

you are absolutely right if the compiler cannot optimize the modulo operation and creates code which calls a modulo subroutine. My point was just that in many cases TIMENODES may be something defined like

Code: Select all

#define TIMENODES (4096)

and in this case the compiler would always transform the modulo into something very efficient. Indeed, this would be the same AND with (TIMENODES-1) as proposed above (not a "shift" as I erroneously wrote - I had a division in mind, not modulo).

So we are very close together now. The only major difference I see is that I prefer better readable code over optimized code if the better readable code does no real harm.

Just my 0,02?!

Sven

[Sven Schüle]

... and of course this code:

Code: Select all

nodes & (TIMENODES-1)

would break immediately if the programmer changes 4096 into 4000 while the modulo would still work

Sven

[Roman Hartmann]

Thanks to all for the input. In the meantime I implemented a counter like Dieter suggested to keep track of the time and it seems to work just fine. Now I have to fix my search, of course, as it's returning trash when I leave it before the the search is finnished.

Roman