move ordering

[delphi_coder]

I'm currently using kind of weak implementation for move ordering within alpha-beta framework which cause to calculate the static score for hundred millions of positions in some cases just for searching 6 ply depth. Studying some engine source codes and also some pages from CPW I found killer moves and heuristic history are 2 common methods for this. The question comes to mind why we store these moves (moves that hit alpha and the ones who produce beta cutoff) in different way. One kept with "piece to square" and other stores the move itself. By assuming that starting to search from a certain position most of the moves will remain identical and some minor changes occur so whats the philosophy of storing piece/square? And What's the negative point if we store the move itself in both cases?

As a second part of question
Some people suggest to use transposition table for move ordering, How to do that while we have score type of lower/upper bound and exact value on TT and there is no guaranty that score exist for all positions caused by moves list.

[H.G.Muller]

I am not sure whether your question refers to killer, history or the difference for both. Killer moves are originating from sibbling nodes, and the player using these moves cannot have any of his pieces on a different square. At worst one of his pieces could have been captured, in which case the square is now occupied by an opponent, so that there is no move for him from that square. History is a more global heuristic that tries to prioritize moves that proved useful in myny other nodes of the tree. A table indexed by piece-type and destination square would be smaller than one indexed by two squares. In the latter case a move could be confused by an unrelated one, because in positions far away from each other in the tree the same square can easily be occupied by a different piece. If it is often good to move a Pawn from e4 to e5, it doesn't mean at all that it would also be good do play e4-e5 if a Queen happens to be on e4. By using piece-type & destination to recognize the move, you can confuse moves that had the same piece going to the square from a different location. From a chessic point of view that should not be very harmful; in fact it generalizes better, as the path through which the piece reached the square often is not important. Also, when a Knight move for instance delivers a fork on Q and K, it doesn't matter which of your Knights reaches that square. So also for this case it is more like a useful generalization than a confusion. Different pieces of the same type going to the same destination cannot occur in many situations anyway; only for Knights and Rooks when you still have two of those.

The transposition table records information that is specific for a single position. That is helpful when you reach exactly that same position again (e.g. through a transposition of the moves leading to it, or in the course of iterative deepening, when you want to search it at larger depth). Ideally searching deeper would not make the move any worse, so if the move was good enough before to cause a cutoff, it has a large chance to still cause the cutoff at higher depth. So you try it first. This argument becomes a bit dubious when the value of beta has been raised much compared to what it was on the previous visit of the position; the move might still be equally good, but still no longer sufficient to reach the new beta. But in any case all moves that would otherwise be tried before it were even worse on the previous visit, so it does seem good to skip those. In principle you could try moves from the TT for 'analogous' positions, originating from the same play starting from sibbling nodes. But I don't think anyone has tried that.

[delphi_coder]

thanks for good and detailed explanation. As I'm using bitboard representation, I felt Piece/Square solution is a bit expensive in performance so I implemented square to square indexed by ply solution for Alpha hitters and it worked well with approximately 60% average performance improvement. But the weird part of story I couldn't get my bonus from sorting the moves which produce beta cutoffs and putting them after alpha hitters as well. In my engine Its worsening the performance by approximately -10%.
the current ordering sequence is
1-PV MOVE
2-Captures (ordered by MVV/LVA)
3-Alpha hitters
5-remaining moves sorting by result of evaluation function (disregard of ply or depth number).
Does anybody used attack boards to distinguish between good and bad captures for move ordering? I think we already need attack boards on evaluation (at-least for king safety) anyway

[H.G.Muller]

I am not sure what you mean by 'alpha hitters'. Is that the killer-move heuristic?

The best ordering for captures is generally considered one that postpones captures of a low-value piece by a higher-value one by not using the victim value as the primary sort key, but the outcome of the exchange on the target square (Static Exchange Evaluation = SEE). If the victim is unprotected this is of course the same, but if it is protected it is usually worse, and often negative. E.g. a Bishop protected by a Knight and attacked by two Rooks would give SEE = +1, and be sorted with the P x P captures. Captures with negative SEE are then usually postponed to after the non-captures. Or, in QS, not searched at all.

If you have to search a cut-node at high depth, but have no idea what the cut-move could be, it is usually faster to first do a lower-depth search in that node to find a cut move, and use that as the first move in the full-depth search ('Internal Iterative Deepening'), than to use the static move ordering immediately at full depth. E.g. all captures could be bad, or just not sufficient to gain what you need to get above beta, and there could be a Knight non-capture that forks Q and R. Such a move would get quite late in the static order, so by the time you get the cutoff you will have wasted much effort searching all captures at the full depth. But a 2-ply search (+QS) could be enough to recognize the Knight move as a fork that will gain the exchange. It will be much faster to search and discard all the moves that would be sorted before it (the fork could be made from a square that has not a high evaluation in itself, e.g. from an edge square) in a two-ply search, and then search the force at, say, 10 ply, than having to go through all these moves at 10 ply.

If you use a Transposition Table you might already have a cut move from a lower-depth search (stored in the previous iteration from the root), even in non-PV nodes. But there it can also happen that you have to break new ground, and apply IID to get a move to start with.

[delphi_coder]

I am not sure what you mean by 'alpha hitters'. Is that the killer-move heuristic?

No, I mean any move that caused alpha raise without checking to see if its capture or not.

Code: Select all

      // I failed to get any performance bonus from this part
      if Score>=Beta then
      begin
        Result := Score;
        if Ply<=InitialMaxDepth then // prevent Out of range write in case of check extension(s)
        begin
          FromSquare := MoveList.Items[i] and 63;
          ToSquare := (MoveList.Items[i] shr 6) and 63;
          KillerMoves[ply][FromSquare][ToSquare] := KillerMoves[ply][FromSquare][ToSquare] + 1;
        end;
        break;
      end;

      // but this one worked well
      if Score>Alpha then
      begin
        Alpha := Score;
        FromSquare := MoveList.Items[i] and 63;
        ToSquare := (MoveList.Items[i] shr 6) and 63;
        if Ply<=InitialMaxDepth then // prevent Out of range write in case of check extension(s)
        begin
          History[ply][FromSquare][ToSquare] := History[ply][FromSquare][ToSquare] + 1;
          PVTable[ply][ply] := MoveList.Items[i];
          for j := Ply+1 to PVLength[ply+1] - 1 do
            PVTable[Ply][j] := PVTable[Ply+1][j];
          PVLength[Ply] := PVLength[Ply+1];
        end;
      end;

disregard of arrays naming in the code (it might be wrong name according to common definition for it from CPW) I experienced significant performance improvement by adding second part.

Captures with negative SEE are then usually postponed to after the non-captures.

Yes, this is the exact thing I'm thinking about but a little bit difference is I'm considering to separate them from the good captures and put them on the end of the list because they likely seems to be the worst moves that cause material lost.

If you use a Transposition Table you might already have a cut move from a lower-depth search (stored in the previous iteration from the root), even in non-PV nodes. But there it can also happen that you have to break new ground, and apply IID to get a move to start with.

TT and IID already implemented, but to be honest I'm disappointed from using TT and looking some other optimization to flee from using it. It clearly improves the search performance but sometimes I see bad failures from the engine, for example putting the queen or rook under direct attack of pawn. Its hard to investigate such bugs For me seems there is a same hash for 2 different positions sometimes.

I'm wondering if implementing a bit detailed and accurate evaluation function and constructing attack maps for both side could improve move ordering. Lets say we have an square which attacked by a pawn a knight and 2 rook (or double rook) from opponent and attacked by a queen and a bishop and a rook from our side, so (by having attack maps available) we already know any move to that square is bad move and put the move to end of the move list (Or even as a higher expectation just calculate the score by material and avoid using Quiescence search at terminal nodes. Not sure if its possible to do correctly or not, Just an idea. But in case of positive answer this may help to avoid calling QS which could improve the performance significantly). Thanks for time/reply

[H.G.Muller]

No, I mean any move that caused alpha raise without checking to see if its capture or not.

Well, when you use a heuristic for picking a move after the captures have been searched, whether this is wht the CPW calls killer or history, indicating a capture would completely useless, right? Because these would have already been searched anyway. In the killer heuristic this would just put a useless duplicat in the killer slot, possibly erasing a useful non-capture. In the case of history, suggesting that a move between two given squares might be good in case the destination is empty just because it was good when the destination was occupied by a Queen also seems an invalid deduction, which will likely confuse the engine.

Yes, this is the exact thing I'm thinking about but a little bit difference is I'm considering to separate them from the good captures and put them on the end of the list because they likely seems to be the worst moves that cause material lost.

Well, 'after the non-captures' is at the end of the list, right?

TT and IID already implemented, but to be honest I'm disappointed from using TT and looking some other optimization to flee from using it. It clearly improves the search performance but sometimes I see bad failures from the engine, for example putting the queen or rook under direct attack of pawn. Its hard to investigate such bugs For me seems there is a same hash for 2 different positions sometimes.

It is not possible to measure the effect of new features when you still have bugs. The bugs will limit the performance to a certain level no matter how much you improve all other aspects of the engine. If an engine obviously blunders in a reproducible way, you should always figure out what causes it to play the move it played.

I'm wondering if implementing a bit detailed and accurate evaluation function and constructing attack maps for both side could improve move ordering. Lets say we have an square which attacked by a pawn a knight and 2 rook (or double rook) from opponent and attacked by a queen and a bishop and a rook from our side, so (by having attack maps available) we already know any move to that square is bad move and put the move to end of the move list (Or even as a higher expectation just calculate the score by material and avoid using Quiescence search at terminal nodes. Not sure if its possible to do correctly or not, Just an idea. But in case of positive answer this may help to avoid calling QS which could improve the performance significantly). Thanks for time/reply

Well, if there was a Queen on that square moving to it (i.e. capturing that Queen) would not be so bad.

What you describe is what SEE does, though. And you do need to know which pieces attack the target square, for both players, including X-ray attacks. Whether you would need a complete attack map for that is questionable: such a map would contain the information for every square (possibly even empty squares). And the first move in your static ordering for a certain position might be RxQ, gaining at least Q for R and causing a beta cutoff irrespective of what was protecting that Queen. So at which point would you calculate the attack map? If you encounter RxR amongst the captures, you would still want to search that before captures of any lesser valued piece, irrespective of what protects the Rook. Only when you encounter a move QxR amongst the captures it becomes relevant to know whether the Rook was protected. But if it was not, you gain a full Rook by it, and this would likely cause a beta cutoff. There might be a much cheaper way to figure out whether that one Rook is protected than constructing a complete attack map for the opponent.

Not that there is anything intrinsically wrong with attack maps. In fact the fastest engine design I know is based on an attack map. But even obtaining such a map through incremental update is quite expensive. So it usually only pays off if you exploit it well. E.g. you could set it up such that you could generate captures in MVV/LVA order by extracting them from the attack map, so that you could directly search them without storing in a list or sorting. And you could make a very fast SEE by indexing a table with the attacker and protector sets obtained from the map, which then tells you how much you stand to lose after the capture to it.

[delphi_coder]

The problem was tied with 2 implementation mistake 1- as you said putting killers and history after all captures was bad idea, separating bad captures to after quiet moves both optimizations works fine 2- using evaluation function in-order to sort moves was good when there was no other move-ordering, after sorting with PV, good captures, history and killers there was no need to evaluation sort.
I removed that and experienced another significant improvement in search

Well, 'after the non-captures' is at the end of the list, right?

yes

It is not possible to measure the effect of new features when you still have bugs.

This bug finally fixed. Is there any pseudo code or even clean/readable source code about move ordering using TT?

So at which point would you calculate the attack map?

Since my evaluation function already has some codes very similar to what we do in movegen to calculate the mobility/attack/move count score I was thinking to construct this table for every position within evaluation function and call it on all nodes as helper for ordering both capture and quiet moves, and also use it for calculating king safety score.

After reading your reply I noticed such thing can not replace quiescence. Maybe the complete form of it including x-ray attacks/pins/forks.. could help but again not sure if it will be more performance hungry than quiescence itself or not.

[H.G.Muller]

Indeed, it is very hard to have an accurate static evaluation of tactics. Pieces essential for protection of other pieces can be soft-pinned, or they can be overloaded by protecting several pieces which are independently attacked. In practice such complex situations only occur rarely, though. So simplified methods might still be good enough for move ordering, where the only consequence of an error is that a bit more nodes are searched than would have been needed.

I think more could be achieved than what people usually do, though. The LeelaChess Zero neural net is already a surprisingly strong player (i.e. if you play LC0 at 1 node, the root). But of course this NN is extremely calculationally expensive. I think it would not be an impossible challenge to develop a comparatively cheap algorithm that is reasonably smart tactically. When the sets of attackers and protectors (including X-rays) of each piece is known, these sets can be used to index 2-dimensional arrays that tabulate the result of the exchange (SEE), but also how important each of the involved pieces is for this outcome. And count in how many exchanges each piece is essential, a count larger than two indicating an overload, leading to assignment of the piece to the exchange which would lose most in its absence, recalculating the other exchange(s) in which it was involved without it. (Possibly leading to new essential, and therefore overloaded pieces.) And check whether essential protectors happen to be attacked by enemy sliders, and what those sliders would do to the exchange on the square they would hit when their move was discovered. (Soft pinning.) It doesn't hae to be incredibly expensive, if the SEE can be done through table lookup.

[delphi_coder]

The root of that idea came from the way I was thinking before starting to study what other typical chess engines doing and to be honest still my mind more involved thinking about forward searching algorithm rather than commonly dominated recursive alpha beta that acts like DSF. Its very close to same method I recently had (sorting the moves with evaluation outcome score) and partially proven not acts as good as at-least what IID,history/killers and SEE brought to us within alpha beta frame work plus some optimization techniques.
Anyway I think I'm done with this topic, Many thanks for time and your helpful replies.