Alternatives to History Heuristics

[mcostalba]

If I understood what you want to convey you're basically saying that those moves with a presumed bigger subtree should be put in the end of the movelist? But isn't it the kind of moves with the bigger subtree that will have a higher chance of improving the best score or alpha of the current position? Also those moves that are easily refuted means that they are foolish moves, isn't it only logical to search them last?

Suppose you have 30 moves to try fro a ply, of theese you have three moves A, B, C.

Move A is the best. Moves B and C _seems_ good moves either but are not the best.

The remaining moves are easy to prune.

If I think of a 'magic' algorithm for ordering the moves, then this magic algorithm should order in this way:

A, all remaining moves, B, C

So that the best is tried immediately and then the remaining are quickly pruned and then at the end are tried the most troubled ones, i.e. the moves that you need a lot of time to search but don't get you to anywhere.

Of course nobody has this magic alghortim, but we can think of something that approximate this in practical terms.

[zamar]

If I understood what you want to convey you're basically saying that those moves with a presumed bigger subtree should be put in the end of the movelist? But isn't it the kind of moves with the bigger subtree that will have a higher chance of improving the best score or alpha of the current position?

I think that chance is indeed higher, but is it enough higher that it's worth of extra cost?

Also those moves that are easily refuted means that they are foolish moves, isn't it only logical to search them last?

Not necessarily. Let's assume that move A has the cost of 500 nodes and chance to reach beta is only 1%. Then we have move B which has the cost of 50'000 nodes and chance to reach beta is 20%. I'd definetily check the move A first

[Edsel Apostol]

If I understood what you want to convey you're basically saying that those moves with a presumed bigger subtree should be put in the end of the movelist? But isn't it the kind of moves with the bigger subtree that will have a higher chance of improving the best score or alpha of the current position? Also those moves that are easily refuted means that they are foolish moves, isn't it only logical to search them last?

Suppose you have 30 moves to try fro a ply, of theese you have three moves A, B, C.

Move A is the best. Moves B and C _seems_ good moves either but are not the best.

The remaining moves are easy to prune.

If I think of a 'magic' algorithm for ordering the moves, then this magic algorithm should order in this way:

A, all remaining moves, B, C

So that the best is tried immediately and then the remaining are quickly pruned and then at the end are tried the most troubled ones, i.e. the moves that you need a lot of time to search but don't get you to anywhere.

Of course nobody has this magic alghortim, but we can think of something that approximate this in practical terms.

That might work if you really know that A is best but if you only have an estimate that the moves A, B, and C have the potential to produce a cutoff, it will fail 66.67% of the time. It is because B or C may be the best move and you put it at the end of the movelist already.

By the way, I think all the moves will be searched anyway if move A didn't fail high so why defer the moves B and C to the end of the movelist? They would still search the same number of nodes as those remaining moves are foolish moves and they will not give you a cutoff before searching the moves B and C.

I think searching B and C first before remaining moves might give you a better chance of a cut off thus reducing the size of the tree as you will not search the remaining moves anymore.

[mcostalba]

That might work if you really know that A is best but if you only have an estimate that the moves A, B, and C have the potential to produce a cutoff, it will fail 66.67% of the time. It is because B or C may be the best move and you put it at the end of the movelist already.

Yes, this is true. That's why I talked about a 'magic' algorithm

By the way, I think all the moves will be searched anyway if move A didn't fail high so why defer the moves B and C to the end of the movelist?

For the same reason we want to order the moves from the best to the worst: a cut-off could occur and we want to occur sooner then later, or we want the last ones to be LMR reduced.

I think searching B and C first before remaining moves might give you a better chance of a cut off thus reducing the size of the tree as you will not search the remaining moves anymore.

I think I have some idea on how to implement something as I had described, but I would like first to test..... I have just e-mailed it to Joona and Tord to get their private feedback

[Edsel Apostol]

If I understood what you want to convey you're basically saying that those moves with a presumed bigger subtree should be put in the end of the movelist? But isn't it the kind of moves with the bigger subtree that will have a higher chance of improving the best score or alpha of the current position?

I think that chance is indeed higher, but is it enough higher that it's worth of extra cost?

Also those moves that are easily refuted means that they are foolish moves, isn't it only logical to search them last?

Not necessarily. Let's assume that move A has the cost of 500 nodes and chance to reach beta is only 1%. Then we have move B which has the cost of 50'000 nodes and chance to reach beta is 20%. I'd definetily check the move A first

I would still try the one with 20%. Even if you have 100 moves like this (100 moves x 500 nodes = same number of nodes as the one with 20% chance) with only 1% chance of producing a cutoff, the total chance will not be 100% but still 1% as the moves are independent of each other. So no matter how many moves you've tried with 1% chance of producing a cutoff, that still would not beat the one with a 20% chance.

I may be wrong. Would the math guys here give some clarification on which is the better of the two?

[hgm]

I may be wrong. Would the math guys here give some clarification on which is the better of the two?

Indeed, you are wrong. 100 moves with independent 1% probability of a cutoff would give 1-(0.99)^100 = 63% probability for a cutoff.

But even if you had only one such move:

If you try A first, you certainly spend 500 nodes, and with a probability of 99% you have to search B as well and spend 50,000 nodes. So on average you save 1% of 50,000 is 500 nodes compared to searching both.

But if you search B first you certainly spend 50,000 nodes on it, and with 20% probabiity you can save the effort of searching the 500 nodes for A So on average you save 100 nodes of effort. So A fist saved you 5 times as much effort. (But none of the savings is very impressive.)

[Edsel Apostol]

I may be wrong. Would the math guys here give some clarification on which is the better of the two?

Indeed, you are wrong. 100 moves with independent 1% probability of a cutoff would give 1-(0.99)^100 = 63% probability for a cutoff.

But even if you had only one such move:

If you try A first, you certainly spend 500 nodes, and with a probability of 99% you have to search B as well and spend 50,000 nodes. So on average you save 1% of 50,000 is 500 nodes compared to searching both.

But if you search B first you certainly spend 50,000 nodes on it, and with 20% probabiity you can save the effort of searching the 500 nodes for A So on average you save 100 nodes of effort. So A fist saved you 5 times as much effort. (But none of the savings is very impressive.)

I am not sure but in a real situation I don't think that an effort for one move will be 100 times the effort for another just like in the above example so I will still stick with the 20%.

By the way, here is a hypothetical question for the above example:
Since foolish moves are refuted easily they would qualify as move A in the above example and promising moves as move B. So for example in an All node, since most probably all moves will be searched anyway, would it be better to reverse the ordering of moves and put the best ones at the end of the movelist to maximize the savings in effort?

[zamar]

By the way, here is a hypothetical question for the above example:
Since foolish moves are refuted easily they would qualify as move A in the above example and promising moves as move B. So for example in an All node, since most probably all moves will be searched anyway, would it be better to reverse the ordering of moves and put the best ones at the end of the movelist to maximize the savings in effort?

Of course not!

If move A has cutoff probability of 30% and cost 1000, move B has cutoff probability 1% and cost 500, we of course search the move A first

The point is that you need to consider both cost and cutoff probability

[Edsel Apostol]

By the way, here is a hypothetical question for the above example:
Since foolish moves are refuted easily they would qualify as move A in the above example and promising moves as move B. So for example in an All node, since most probably all moves will be searched anyway, would it be better to reverse the ordering of moves and put the best ones at the end of the movelist to maximize the savings in effort?

Of course not!

If move A has cutoff probability of 30% and cost 1000, move B has cutoff probability 1% and cost 500, we of course search the move A first

The point is that you need to consider both cost and cutoff probability

Indeed. If only moves have those values already then we will have a perfect move ordering.

By the way, I will try to implement the PST for move ordering and report here what's my findings.

For Stockfish, maybe you guys could try putting higher in the movelist those pieces attacked by the null threat move. I'm curious if that idea is good.

[mcostalba]

For Stockfish, maybe you guys could try putting higher in the movelist those pieces attacked by the null threat move. I'm curious if that idea is good.

This sounds interesting. Thanks.

I will put in my testing queue (that is unfortunatly not so short...but that of Joona and Tord is big either).

We _really_ have more ideas then computers available