trick question

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Daniel Shawul
Posts: 3920
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

trick question

Post by Daniel Shawul » Tue Mar 20, 2018 10:49 pm

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
Posts: 313
Joined: Thu Mar 16, 2006 6:39 pm
Location: Portugal
Full name: Alvaro Cardoso
Contact:

Re: trick question

Post by Cardoso » Tue Mar 20, 2018 11:16 pm

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
Posts: 3920
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: trick question

Post by Daniel Shawul » Wed Mar 21, 2018 1:08 am

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
Posts: 830
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: trick question

Post by elcabesa » Wed Mar 21, 2018 6:10 am

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
Posts: 882
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: trick question

Post by Aleks Peshkov » Wed Mar 21, 2018 8:42 am

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
Posts: 2122
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: trick question

Post by mar » Wed Mar 21, 2018 10:03 am

Aleks Peshkov wrote: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
Posts: 20914
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: trick question

Post by bob » Thu Mar 22, 2018 12:21 am

Daniel Shawul wrote: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
Posts: 4582
Joined: Tue Feb 28, 2012 10:56 pm

Re: trick question

Post by syzygy » Thu Mar 22, 2018 12:51 am

Daniel Shawul wrote: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
Posts: 4582
Joined: Tue Feb 28, 2012 10:56 pm

Re: trick question

Post by syzygy » Thu Mar 22, 2018 1:00 am

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
Posts: 925
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: trick question

Post by AlvaroBegue » Thu Mar 22, 2018 1:09 am

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&#41; &#123;
    next_time_check = nodes_searched + 30000l;
    check_if_time_is_up&#40;);
  &#125;
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.

Post Reply