Edsel Apostol wrote:I don't have History Pruning and History Based Reductions in my engine and I'm planning to remove the History Heuristic altogether.
The question is what are the possible alternatives to it? I'm thinking of using values from piece square tables to order my non tactical moves instead of the data in the history table. Has anyone tried it? Is it better than using history?
Has anyone also tried ordering those non tactical moves by type of piece? For example prioritize pawn moves first, knight and bishop next and so on.
Another idea would be to put those moves at the end of the movelist when the "to" square is being attacked by a lower value piece. For example a queen move to a square attacked by the opponent pawn. Is it a sound idea?
First, a bit of logic. Ordering is needed so that you get a "good" move ordered first. A good program can do this 90% of the time. So any other ordering you do is an attempt to improve on that. Most of the time a capture is best, as it captures a piece that was hung at the previous ply. The exception to this is the "hash move" which has more evidence to support it being best since it was best the last time a search was done from this position. After good captures, and the hash move, you have to be careful, because effort expended ordering the remaining moves can become expensive since it is done so often. You don't want to make the tree 5% smaller but expend 25% more effort, the net effect is a significant performance loss.
I use the hash move, then good (SEE) captures, then two killer moves, and then just take the moves in the order they are generated. I do generate moves so that more advanced pieces are moved first, and moves toward the opponent's side of the board are generated first for each piece.
Edsel Apostol wrote: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?
If a node is really an ALL node, ordering is completely irrelevant. You still have to search each move, with the same alpha/beta bounds (since alpha is never improved at an ALL node) so how can ordering make _any_ difference at all???
Edsel Apostol wrote:
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
I'll ask again... How can you get _any_ improvement from searching in a different order at an ALL node? It just can not happen. You have to search each move, regardless of the order. Since it is an ALL node, alpha is never changed, so all the moves are searched with the same bound. You can search in completely random order and not search any less efficiently, except perhaps for completely random effects introduced by hash hits. And with a large enough table, even this effect is zero.
bob wrote:If a node is really an ALL node, ordering is completely irrelevant. You still have to search each move, with the same alpha/beta bounds (since alpha is never improved at an ALL node) so how can ordering make _any_ difference at all???
Maybe it could narrow the alpha beta window earlier, which then should imply a speedup.
bob wrote:If a node is really an ALL node, ordering is completely irrelevant. You still have to search each move, with the same alpha/beta bounds (since alpha is never improved at an ALL node) so how can ordering make _any_ difference at all???
Maybe it could narrow the alpha beta window earlier, which then should imply a speedup.
How? We reach node X, which is an ALL node. We must search _every_ move at X, and we know alpha/beta bounds will not change since this is an ALL node, so how can the order affect the alpha/beta window at this node at all? 99.999% of positions are already searched with alpha, alpha+1 as the "window" so that can't be narrowed any further at all.
The old Knuth/Moore "An analysis of alpha/beta pruning" paper makes this pretty clear, IMHO. Ordering at an ALL node is completely irrelevant. The problem is, it is impossible to say with 100% certainty which nodes are "ALL" nodes.
Another point is, that if (as in my SMIRF) there is done a prefiltering of moves by a slightly wider alpha beta window, there might be a narrowing effect by move ordering.
bob wrote:
I'll ask again... How can you get _any_ improvement from searching in a different order at an ALL node? It just can not happen. You have to search each move, regardless of the order. Since it is an ALL node, alpha is never changed, so all the moves are searched with the same bound. You can search in completely random order and not search any less efficiently, except perhaps for completely random effects introduced by hash hits. And with a large enough table, even this effect is zero.
I really don't understand of what you are talking about. Whole point of examining an _expected_ ALL node is to find out if it really is an ALL node. And it's of course advantageous to test moves which are likely to turn tables as early as possible.
bob wrote:
I'll ask again... How can you get _any_ improvement from searching in a different order at an ALL node? It just can not happen. You have to search each move, regardless of the order. Since it is an ALL node, alpha is never changed, so all the moves are searched with the same bound. You can search in completely random order and not search any less efficiently, except perhaps for completely random effects introduced by hash hits. And with a large enough table, even this effect is zero.
I really don't understand of what you are talking about. Whole point of examining an _expected_ ALL node is to find out if it really is an ALL node. And it's of course advantageous to test moves which are likely to turn tables as early as possible.
Nope. The idea is to search the tree by examining the fewest nodes and expending the least effort possible. Ordering at an ALL node is irrelevant. As I clearly stated. Ordering at a CUT or PV node is critical. But since a good program already gets the best move ordered first in over 90% of the CUT/PV nodes, the only ordering improvement available is that last 10% (actually, in the case of Crafty, this number is 92% overall so make that 8%) of the CUT/PV nodes. No ordering improvement is possible in an ALL node. My point, therefore, was that you have to be _very_ careful in the effort you expend to reduce that remaining 8-10% of the CUT/PV nodes, so that the cost of improving the ordering is not outweighed by the cost of the ordering itself.
