trick question

[Daniel Shawul]

We usually implement polling for input by something like

Code: Select all

nodes++

if(nodes % 200 == 0) {
    check_keyboard()
}

which will execute 1 in 200 times. I had a scheme that executes the following instead

Code: Select all

nodes += number_of_children ( could be any number between 1 to 40 )

if(nodes % 200 == 0) {
    check_keyboard()
}

and thought this is not going to execute every 200 nodes (which is what i had in mind when i wrote the code), because nodes is not being increased by 1.

Which code checks for input more frequently ?

Daniel

[Cardoso]

Well, as my first reaction I would go for the first case wich is guaranted to poll every 200 nodes,
The second case is a bit random and requires luck to get a number exactly divisible by 200. But then again it might take less nodes to get a poll check.
Ok I give up what is the answer?

[Daniel Shawul]

Hmm, i think they are equally likely

My line of thought is :
a) Each number from 160 - 199 has a probability of 1/40 of hitting exactly 200 on the next polling test. At this point i thought, hey this (1/40) is more likely than 1/200 but nooo...
b) We are in this range, i.e.160-199 only 40/200 of the time so, 1/40 * 40/200 = 1/200, which is exactly same as the case of incrementing by 1.

So no matter the increment, both codes execute polling once every 200 nodes.

However, there is a problem though with the later because you are not guaranteed to do polling every 200 nodes. Infact, my engine was failing on time multiple times using the second approach which led me to this question.

The second approach has a large gap between hits on average. A maximum of 200x larger gap between hits could occur for the second approach, which is probably why it was failing on time.

Daniel

[elcabesa]

just my 2 cent.

here check_keyboard execute on average every 200 moves. it add aother variable and some math but should be faster than the original code

Code: Select all

nodes += number_of_children ( could be any number between 1 to 40 )

if(nodes - backup_nodes > 200) {
    check_keyboard()
    backup_nodes = nodes
}

[Aleks Peshkov]

The trick is to use second counter.

Code: Select all

    unsigned long nodes;
    unsigned long nodesLimit; //search limit

    enum : unsigned { TickLimit = 5000 }; // ~1 msec
    unsigned nodesQuota; //number of remaining nodes before slow checking for terminate

    // the current exact number of nodes
    node_count_t getNodes() const {
        assert (nodes >= nodesQuota);
        return nodes - nodesQuota;
    }

    bool countNode() {
        if (nodesQuota > 0) {
            --nodesQuota;
            return false;
        }
        return refreshQuota();
    }

bool refreshQuota() {
    static_assert (TickLimit > 0, "TickLimit should be a positive number");

    assert (nodes >= nodesQuota);
    nodes -= nodesQuota;

    assert (nodesLimit >= nodes);
    auto nodesRemaining = nodesLimit - nodes;

    if (nodesRemaining >= TickLimit) {
        nodesQuota = TickLimit;
    }
    else {
        nodesQuota = static_cast<decltype&#40;nodesQuota&#41;>&#40;nodesRemaining&#41;;
        if &#40;nodesQuota == 0&#41; &#123;
            return true;
        &#125;
    &#125;

// do something slow ...

    assert &#40;nodesQuota > 0&#41;;
    nodes += nodesQuota;

    --nodesQuota; //count current node
    return false;
&#125;

[mar]

The trick is to use second counter.

for IO, I'd use a separate thread (main thread IO, search in a separate thread
for the timeout, however, I'd still use polling

[bob]

Hmm, i think they are equally likely

My line of thought is :
a) Each number from 160 - 199 has a probability of 1/40 of hitting exactly 200 on the next polling test. At this point i thought, hey this (1/40) is more likely than 1/200 but nooo...
b) We are in this range, i.e.160-199 only 40/200 of the time so, 1/40 * 40/200 = 1/200, which is exactly same as the case of incrementing by 1.

So no matter the increment, both codes execute polling once every 200 nodes.

However, there is a problem though with the later because you are not guaranteed to do polling every 200 nodes. Infact, my engine was failing on time multiple times using the second approach which led me to this question.

The second approach has a large gap between hits on average. A maximum of 200x larger gap between hits could occur for the second approach, which is probably why it was failing on time.

Daniel

Is nodes shared or local to each thread? If shared, you are sure adding a LOT of cache traffic invalidating shared copies across all CPU caches... If local, the obvious result would be that everybody polls once every 200 nodes. Neither sounds like what you really want...

[syzygy]

Hmm, i think they are equally likely

My line of thought is :
a) Each number from 160 - 199 has a probability of 1/40 of hitting exactly 200 on the next polling test. At this point i thought, hey this (1/40) is more likely than 1/200 but nooo...
b) We are in this range, i.e.160-199 only 40/200 of the time so, 1/40 * 40/200 = 1/200, which is exactly same as the case of incrementing by 1.

So no matter the increment, both codes execute polling once every 200 nodes.

This is probably easy to prove by considering for each t the vector p(t) = (p_i(t)) of probabilities that nodes % 200 = i at time t. We have p(t+1) = A x p(t) for some 200x200 matrix A. So we have a Markov chain.

It is easy to see that p = (p_i) with p_i = 1/200 for all i satisfies p = A x p, so p is the unique stationary distribution, provided that the Markov chain is irreducible and aperiodic (Wikipedia).

The chain is irreducible if every state can be reached from any other state. I think that is the case here if and only if the possible values of "number_of_children" have a greatest common divisor equal to 1. So the number shouldn't always be even, for example. (If the number is always even, then the probability will be 1/100 (or still higher), or 0 if you start with an odd number of nodes).

Aperiodic means, here, that the possible numbers of steps between consecutive occurrences of nodes % 200 = 0 (or any other number) have greatest common divisor equal to 1. This will also be the case for any sensible distribution of "number_of_children".

[syzygy]

I guess if the chain is irreducible but aperiodic, the average number of times that nodes % 200 = 0 is still exactly 1/200, but the probability of this at time t will not converge to 1/200 as t->inf.

For example, if you always add 1, the probability that nodes % 200 = 0 is exactly 1 at steps 0, 200, 400, ... and exactly 0 at all other steps. The average is 1/200, which is exactly what you want.

So if you only care about the average, it is sufficient to make sure that you're not always adding a number that is a multiple of some integer k > 1.

[AlvaroBegue]

My solution is to schedule the next check when the node counter reaches some number.

Code: Select all

  // Check the time every so often
  if (++nodes_searched >= next_time_check) {
    next_time_check = nodes_searched + 30000l;
    check_if_time_is_up();
  }

Now that I am looking at the code, that function both checks if time is up and processes input, so I should find a better name for it.