Time assignment to children

[matthewlai]

Well, there is one unexpected problem. Overflow!

I am ready for 128-bit .

Or represent the node budget as log(nodes). Division becomes subtraction. Scale it such that you can use integer arithmetic. And then you find that you have, in fact, the equivalent of fractional depths

I can also have all that work done for me by switching to floating point , which is what I am considering right now.

But then it becomes impossible to prove that the search will terminate, since "--nodeBudget" may no longer have an effect once the exponent becomes large enough. That's why I wanted to stick with an integral type if possible.

[clumma]

Child A is a much simpler position, with only 3 possible moves. Child B is a more complex position, with 9 possible moves.
...
If we assume the probability of A and B being in the theoretical PV to be equal,
...
unless we want to assume that, in general, B has a higher probability of being in the PV because it has more children. I don't see how that can be argued.

It can be argued if we assume each complete variation has an equal probability of being the PV. Which makes as least as much sense as your assumption that each original child has an equal probability of being in the PV.

Can't questions like this be answered with EGTBs? For any node, we know the number of legal moves and we also know the win/draw/loss percentage among the final positions. Is this percentage related to the number of legal moves at the parent node?

-Carl

[matthewlai]

It can be argued if we assume each complete variation has an equal probability of being the PV. Which makes as least as much sense as your assumption that each original child has an equal probability of being in the PV.

That's not really arguing it. That's just restating the claim .

It doesn't make as much sense. Imagine KQPkqp end games, and you have the opportunity to trade the queen vs not trade the queen. Is not trading the queen 10-20x more likely to be better than trading it? Clearly it cannot be.

Or more generally, is not trading (when an opportunity arises) almost always better than trading? Obviously that's not true as well.

It's easy to show that the probability that not trading is better than trading, in general, has to be about 50%. If it's in white's best interest to not trade, it would be in black's best interest to trade, most of the time, so the probability has to be about 50%.

Can't questions like this be answered with EGTBs? For any node, we know the number of legal moves and we also know the win/draw/loss percentage among the final positions. Is this percentage related to the number of legal moves at the parent node?

That would work for end games. I don't really have time to try it however.

Win percentage may be related to the number of legal moves in terms of mobility, but it's mobility imbalance that matters. When we are trading, the reductions in mobility are almost always symmetrical.

[clumma]

I'm afraid you've lost me -- what does trading queens have to do with anything?

In particular, how does it justify your assumption that all immediate children have equal probability of being in the PV even if they lead to a different number of final positions?

You lost me on mobility too. I thought we were talking about scoring nodes based on number of legal moves. Sure, mobility may be involved there, but that's rather more specific than your point about probability of belonging to the PV (which would apply in all game phases).

EGTBs just make it possible to examine questions like this directly, vs. comparing Elo of two engine versions, which is an indirect test.

-Carl

[matthewlai]

I'm afraid you've lost me -- what does trading queens have to do with anything?

In particular, how does it justify your assumption that all immediate children have equal probability of being in the PV even if they lead to a different number of final positions?

You lost me on mobility too. I thought we were talking about scoring nodes based on number of legal moves. Sure, mobility may be involved there, but that's rather more specific than your point about probability of belonging to the PV (which would apply in all game phases).

EGTBs just make it possible to examine questions like this directly, vs. comparing Elo of two engine versions, which is an indirect test.

-Carl

Well, usually when you have 2 branches with different number of legal moves, it's because 1 branch involves trading. That's how trading is related to different-sized subtrees.

The assumption that all children have the same probability is from the fact that trading (the most common cause of different-sized subtrees) cannot possibly be almost always better than not-trading.

By assuming that each complete variation has equal chance, depth-constrained search has an inherent bias for not-trading. I don't see a justification for that.

[clumma]

The assumption that all children have the same probability is from the fact that trading (the most common cause of different-sized subtrees) cannot possibly be almost always better than not-trading.

Ah, OK.

Sometimes though, avoiding a trade is good.
Development is good.
Being in check is often bad.

I reckon we need to consider player-to-move. We should minimize legal moves for our opponent and maximize them for ourselves.

I looked on the wiki to see if this has been proposed for move ordering but I didn't find it.

Wissner-Gross has actually proposed something like this as a universal attribute of intelligence, based on some intuition from maxent.

-Carl

[matthewlai]

Sometimes though, avoiding a trade is good.
Development is good.
Being in check is often bad.

Definitely. That's why an equal-probability approach gives them equal chances .

I reckon we need to consider player-to-move. We should minimize legal moves for our opponent and maximize them for ourselves.

Indeed, and that's the mobility consideration.

I looked on the wiki to see if this has been proposed for move ordering but I didn't find it.

I believe some engines use eval change to do move ordering, and that should include mobility.

[clumma]

Definitely. That's why an equal-probability approach gives them equal chances .

I agree, your proposal is probably an improvement on the status quo.

I reckon we need to consider player-to-move. We should minimize legal moves for our opponent and maximize them for ourselves.

Indeed, and that's the mobility consideration.

I don't think it's quite the same as mobility. Checks reduce legal moves.

-Carl

[matthewlai]

I don't think it's quite the same as mobility. Checks reduce legal moves.

In my engine it is, because I do legal move generation for mobility.

My eval is so slow that the slowdown from that is negligible, and it provides more accurate results.