Measuring position complexity

[grandmastermac]

I am interested in creating an engine that is humanistic. Aside from the style of play, one of the ways I identified to be more "human" is to temper how quickly the engine plays it's move. My idea was if a position is more complex, a human will typically take more time to think than in a relatively simple position such as a basic recapture.

So my question is, what methods are best used to measure a positions complexity? I am interested in something calculable. Any thoughts are greatly appreciated.

[Dann Corbit]

Extreme mobility is one measure of complexity.
There is a position which has 218 possible move choices. Some programs crash just trying to quiesce.

Another measure of complexity is threats. Imagine if there are 9 of your chessmen simultaneously under attack.
There can be complicating factors. You may have overworked defenders (e.g. one pawn is defending two pieces, and so if the pawn is taken, both pieces are left undefended).

Another measure of complexity is the number of operations until quiescence. It is similar to the above measure, but the position changes after each capture.

King danger is another measure of complexity. If I have a giant pile of wood in the vicinity of your king, you *have* to care about what those chessmen might do.

I guess that there are a lot of other measures as well.

I would say "time of analysis to depth" for a strong engine is quite a good measure. If an engine can get to 36 plies in a fraction of a second, the position is probably not very complex. But if it takes 2 hours to get to 36 plies then it is probably quite a complex position.

[Karlo Bala]

The effective branching factor?!

[Ovyron]

The effective branching factor?!

Yes, the easiest way to measure complexity is to let the engine run for a while, and see how fast you reach higher depth. If you do it faster than usual, the complexity is low. If you do it slower than usual, the complexity is high.

So you can make the engine play faster if depth is reached fast, and play slower if depth is reached slowly.

Another thing is score difference, simple positions have a score that is mostly the same all the search, complex positions have some fail lows and fail highs that make the score do sudden jumps, so you can make the engine play faster when scores don't seem to change with more depth, while it plays slower if there's more sudden changes.

[grandmastermac]

Thank you - this discussion and insight has been really helpful!

[Dann Corbit]

I don't think that EBF is enough, though.
Quite often, I have seen SF roar to 100+ plies with a draw score, and then finally, at long last, goes into a massive fail high and finds the mate.
So the EBF is very close to 1 for 100 plies. Then the EBF goes through the roof. I guess you could say "SF finally found the complexity."

[Ferdy]

I am interested in creating an engine that is humanistic. Aside from the style of play, one of the ways I identified to be more "human" is to temper how quickly the engine plays it's move. My idea was if a position is more complex, a human will typically take more time to think than in a relatively simple position such as a basic recapture.

So my question is, what methods are best used to measure a positions complexity? I am interested in something calculable. Any thoughts are greatly appreciated.

One idea is to train a model by giving it some positions with features like, material, mobility, pins, number of queens, etc. then add a target value of 3 classifications or so like most complex, complex, and less complex. Basically we need a data like.

Code: Select all

pos, mat, mob, pins, nq ... target
1, .., .., .., .., ... 3
2, .., .., .., .., ... 1
3, .., .., .., .., ... 2
...

where:
target 3 is most complex.

Once we have the model, we can just input a position and see the model prediction of that position.

But we need to collect the data and this is not easy but not impossible. We collect positions and let some people vote for either 3, 2 or 1.
One further observation is that position complexity depends on the strength of the player. A position might be complex to a 1500 player but not for a 2000 player. So people who classify the position should also show their rating.

Perhaps there is a high correlation between position complexity and difficulty of finding the best move or even finding the top 3 moves in the position. Given some 100 engines, give them 1 position, if 75% or more of the engines find the best move, that position can be classified as less complex and assign a target value is 1. Do for other positions and we can build the data to train the model.