Alternatives to History Heuristics

[Edsel Apostol]

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?

[zamar]

Finding proper alternative for (stupid) history move ordering is really hot question. This could give enormous elo boost.

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?

Stockfish uses psqt delta to order moves with zero history value.

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?

Sounds wise at first sight, but it's not so clear. Very stupid looking moves are also very fast to refute (and sometimes they still work!). So when thinking about cost/benefit ratio, it's not clear whether they should be played first or last. I think we would need some way to identify "boring moves" (which are neither good nor bad, but meaningless) and put them last in the list. Unfortunately this is very position dependant.

[hgm]

In my Xiangqi engine HaQiKi D orderig the non-captures by PST delta reduced the size of the search tree by a significant factor from using history.

[Edsel Apostol]

In my Xiangqi engine HaQiKi D orderig the non-captures by PST delta reduced the size of the search tree by a significant factor from using history.

Do you have two sets of PST and are you scaling them by the game phase?

[Mincho Georgiev]

I am using combination of both. PSQ for every move(not only tactical) and history heuristics as well. The main difference i make between the normal psq tables and the 'move' ones is that the second have higher values (higher positive and lower negative ones.). You could use a formula, but there are some tiny exceptions. However, the values i'm using are only in addition to the score, already been calculated. This technique however is not suitable for endgame phase and especially for pawn endgame (or in 'king alone' for one of sides). Note, that it makes difference only when 2 moves with equal (or very close) scores should be delimited (1st and 2nd...) , therefore i don't believe that this brings a significant improvement but it don't hurts either except if you are trying to limit the used heap.

[hgm]

Do you have two sets of PST and are you scaling them by the game phase?

Not. Just one set, tuned to the middle game. I also tested the performance on middle-game and opening positions.

[Edsel Apostol]

Do you have two sets of PST and are you scaling them by the game phase?

Not. Just one set, tuned to the middle game. I also tested the performance on middle-game and opening positions.

I'm asking this because I have separate PST for middlegame and endgame and if I would only use the one for middlegame some of my pieces in the endgame especially the king would favor the moves to the edge of the board instead of the center.

[mcostalba]

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?

I don't like a lot this idea.

One of the biggest misleadings that I fall in often is to apply human like heuristic to a chess engine.

In this case move ordering IMHO should be something that puts as first moves moves that are good but not just trivially good, and conversly put at the end moves that are bad, but not just trivially bad.

To refute a queen that is going to a square attcked by a pawn is blazing fast and is not a problem: a moves order that avoid that situation does not gain you a lot.

To put at the end a move that _seems_ acceptable but indeed is not is instead an enourmous time saving because engine will avoid to mess with that move searching for a deep and big sub-tree.

So move ordering IMHO should be based on an alghoritm that is far reaching. History or psqt are far reaching because both don't use immediate good/bad information, but they leverage on moves whom "quality" can be seen only many plies ahead. That's IMHO the reason they work.

BTW history works better then psqt in Stockfish, although the actual ordering is a linear comination of the two where history is much more weighted then psqt.

[Edsel Apostol]

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?

I don't like a lot this idea.

One of the biggest misleadings that I fall in often is to apply human like heuristic to a chess engine.

In this case move ordering IMHO should be something that puts as first moves moves that are good but not just trivially good, and conversly put at the end moves that are bad, but not just trivially bad.

To refute a queen that is going to a square attcked by a pawn is blazing fast and is not a problem: a moves order that avoid that situation does not gain you a lot.

To put at the end a move that _seems_ acceptable but indeed is not is instead an enourmous time saving because engine will avoid to mess with that move searching for a deep and big sub-tree.

So move ordering IMHO should be based on an alghoritm that is far reaching. History or psqt are far reaching because both don't use immediate good/bad information, but they leverage on moves whom "quality" can be seen only many plies ahead. That's IMHO the reason they work.

BTW history works better then psqt in Stockfish, although the actual ordering is a linear comination of the two where history is much more weighted then psqt.

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?

By the way, what I don't like with History is that as the time spent on search increases, the randomness of the values contained in the history table also increases, and I don't want to trust that value.

[Edsel Apostol]

Another idea worth trying is to put on top of the move list the moves of the hanging pieces. I'm wondering if anyone has tried this? Does the added cost of calculation for hanging pieces worth the benefit of it?

I'm not sure if I remembered it correctly but it seems that Rebel is doing this based on the info on Ed's website.

And then another idea is to score the non tactical moves according to evaluation criteria. For example a queen move will be scored higher if that move contribute to attacks on the opponent king. Pawns that are passed will be scored higher than ordinary pawn moves. Rook to open files over ordinary rook moves, Knight on outposts, etc... I think this is a good idea but it would be expensive to calculate.