Estimating q-search size using move list length

[matthewlai]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

[bob]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

I don't see where the factorial comes from here. Nor do I understand the "after a null-move". How does null-move apply in a q-search?

[matthewlai]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

I don't see where the factorial comes from here. Nor do I understand the "after a null-move". How does null-move apply in a q-search?

If you have a position where the moving side has 5 possible captures, and the other side has 3, on the first ply, we have 5 possible moves, then on the second ply, we have 3 possible moves, and on the third ply, we have 4 possible moves (since 1 of the 5 possible captures have already been done).

[bob]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

I don't see where the factorial comes from here. Nor do I understand the "after a null-move". How does null-move apply in a q-search?

If you have a position where the moving side has 5 possible captures, and the other side has 3, on the first ply, we have 5 possible moves, then on the second ply, we have 3 possible moves, and on the third ply, we have 4 possible moves (since 1 of the 5 possible captures have already been done).

That's all guesswork. First, there are stand-pat cases where no captures are examined at all. Second, 5-3 is just one of N possible cases. And what about the possible captures at ply=3 and ply=4. The captures don't necessarily decrease, due to x-rays and such...

[matthewlai]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

I don't see where the factorial comes from here. Nor do I understand the "after a null-move". How does null-move apply in a q-search?

If you have a position where the moving side has 5 possible captures, and the other side has 3, on the first ply, we have 5 possible moves, then on the second ply, we have 3 possible moves, and on the third ply, we have 4 possible moves (since 1 of the 5 possible captures have already been done).

That's all guesswork. First, there are stand-pat cases where no captures are examined at all. Second, 5-3 is just one of N possible cases. And what about the possible captures at ply=3 and ply=4. The captures don't necessarily decrease, due to x-rays and such...

Yes, it's all guesswork. That's what heuristics are. It just has to be right often enough to have a net positive speedup.

In extreme cases, if we have positions where both sides have 10 possible captures, it's quite likely that the q-search tree will be relatively large, and using the TT will most likely be beneficial.

Simply use TT above depth = 0 and not use TT in q-search is all guesswork as well. It's assuming all depth > 0 trees will be bigger than all q-search trees, which is obviously not true either.

[hgm]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

I don't think that will work at all. Usually captures create new captures, because pieces are seldomly hanging. If a piece is twice protacted, capturing it creates two new captures for the opponent, which he did not have before, because it is not legal to capture your own pieces. But it is much worse: when he replies not with one of these new recaptures, but with one of his pre-existing captures, the piece I just captured with will survive, and also have new captures.

Usually these are very many, because in typical Chess positions pieces are not randomly distributed over the board, but tend to cluster with friends. So capturing something usually makes you penetrate into the 'enemy camp', where you will have many new victims. You can easily get a QS with millions of nodes in a position where each side just has one capture (with a Queen into the opponent camp, starting a plunder raid). If you don't take account of move sorting and beta cutoffs, this is actually quite typical, when the Queens are still on the board. And it is not clear your calculation takes these into account at all.

[Sven]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

In addition to all the other comments so far, to which I fully agree, the tree size is also subject to alpha-beta.

The typical, or average, QS tree size can also be determined from the percentage of QS nodes vs. all nodes. Many people report numbers between 80% and 90%. Assuming that the horizon nodes themselves, which are also QS root nodes, do not count as QS nodes, and assuming further that most full-width nodes are actually horizon nodes, a QS ratio of 80% would indicate an average QS tree size of 4 nodes (9 for 90%). If only 50% of all full-width nodes are horizon nodes then these numbers change into 8 (for 80%) resp. 18 (for 90%).

[matthewlai]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

I don't think that will work at all. Usually captures create new captures, because pieces are seldomly hanging. If a piece is twice protacted, capturing it creates two new captures for the opponent, which he did not have before, because it is not legal to capture your own pieces. But it is much worse: when he replies not with one of these new recaptures, but with one of his pre-existing captures, the piece I just captured with will survive, and also have new captures.

Usually these are very many, because in typical Chess positions pieces are not randomly distributed over the board, but tend to cluster with friends. So capturing something usually makes you penetrate into the 'enemy camp', where you will have many new victims. You can easily get a QS with millions of nodes in a position where each side just has one capture (with a Queen into the opponent camp, starting a plunder raid). If you don't take account of move sorting and beta cutoffs, this is actually quite typical, when the Queens are still on the board. And it is not clear your calculation takes these into account at all.

That is true, so I suppose it would be more accurate to count the number of useful re-captures as well (which can be done almost for free if already doing SEE).

That way it will only underestimate cases where the queen captures an undefended piece in enemy camp.

[bob]

In q-search, if we have n moves, and opponent has m moves (after we do a null-move), the tree size is approximately (not taking into account checks, etc) n!m!.

For example, if the moving side has 5 possible captures (filtered using whatever criteria you want) and the opponent has 3 possible captures, the tree size would be -

5 * 3 * 4 * 2 * 3 * 1 * 2 * 1. If we re-arrange that, we get 5!3!.

I imagine this is a pretty accurate estimate in the vast majority of cases.

Has anyone experimented with using that estimate to determine, for example, whether to use ttable or not?

I don't see where the factorial comes from here. Nor do I understand the "after a null-move". How does null-move apply in a q-search?

If you have a position where the moving side has 5 possible captures, and the other side has 3, on the first ply, we have 5 possible moves, then on the second ply, we have 3 possible moves, and on the third ply, we have 4 possible moves (since 1 of the 5 possible captures have already been done).

That's all guesswork. First, there are stand-pat cases where no captures are examined at all. Second, 5-3 is just one of N possible cases. And what about the possible captures at ply=3 and ply=4. The captures don't necessarily decrease, due to x-rays and such...

Yes, it's all guesswork. That's what heuristics are. It just has to be right often enough to have a net positive speedup.

In extreme cases, if we have positions where both sides have 10 possible captures, it's quite likely that the q-search tree will be relatively large, and using the TT will most likely be beneficial.

Simply use TT above depth = 0 and not use TT in q-search is all guesswork as well. It's assuming all depth > 0 trees will be bigger than all q-search trees, which is obviously not true either.

I predict you will discover that whether you probe in q-search or not, you are going to get the same result in about the same amount of time. From about a zillion experiments over the years. And I can only assume that if you probe you also store, otherwise I really don't see the point at all. Storing in the q-search certainly has an effect, namely greatly increasing the demands on the ttable. YMMV, but every time I have tested it was a complete wash.

[hgm]

Another issue, already mentioned by Sven, is that you are not really interested in he size of the minimax tree, but the alpha-beta tree. A position can have 10 captures for you, and 20 for the opponent, and still lead to a 'tree' of only 1 node, because all your 10 captures are futile, since you are at alpha-4, and none of the potential victims is R or Q.