MoveOrdering++

[Henk]

For move ordering I use MVV/LVA for captures in normal search and History Heuristic for non captures. Are there more options ?


1) Using SEE for detecting bad captures. I think it does not help for a bad capture can be a good sacrifice.

2) Piece Square table for ordering remaining moves.

3) Using value of Transposition table. What if there is none. What should be the order of moves which don't have one ?

One cannot combine ordering values. For instance value from Transposition table with move rating from History Heuristic (Table) ?

[bob]

For move ordering I use MVV/LVA for captures in normal search and History Heuristic for non captures. Are there more options ?


1) Using SEE for detecting bad captures. I think it does not help for a bad capture can be a good sacrifice.

2) Piece Square table for ordering remaining moves.

3) Using value of Transposition table. What if there is none. What should be the order of moves which don't have one ?

One cannot combine ordering values. For instance value from Transposition table with move rating from History Heuristic (Table) ?

Best move from an earlier search, which comes from a hash table hit.

killer moves.

I don't quite follow what you mean in (3).

[Henk]

For move ordering I use MVV/LVA for captures in normal search and History Heuristic for non captures. Are there more options ?


1) Using SEE for detecting bad captures. I think it does not help for a bad capture can be a good sacrifice.

2) Piece Square table for ordering remaining moves.

3) Using value of Transposition table. What if there is none. What should be the order of moves which don't have one ?

One cannot combine ordering values. For instance value from Transposition table with move rating from History Heuristic (Table) ?

Best move from an earlier search, which comes from a hash table hit.

killer moves.

I don't quite follow what you mean in (3).

With 3) I mean that some moves when applied give a position which had already been stored in the Hash table. So these moves can be assigned a value from hash table although these values might be computed at different search depths and different types of nodes. Maybe it might be possible to use these values for ordering moves.

Combining ordering values from different ordering methods may not be possible. For instance (value from hash table, move rating from History Heuristic Table).

[elcabesa]

usually the result of a previous search (hash value) and the move ordering value have nothing in common.
if you know the value or the bound from the hash table you know the result of a search, how do think to use it to order the move?

[Henk]

usually the result of a previous search (hash value) and the move ordering value have nothing in common.
if you know the value or the bound from the hash table you know the result of a search, how do think to use it to order the move?

For instance if move_1 has lower bound from hash that is greater than lower bound from hash of move_2, one can decide that move_1 is tried before move_2 for it may have better chances.

[elcabesa]

how do you think to implement this?

[Henk]

For ordering remaining moves:

Collect moves with values from hash(>= some depth) that are not upper bounds. Sort them on value.

Or
(Collect moves with values from hash(>= some depth) that are exact. Sort them in descending order)
+
(Collect moves with values from hash(>= some depth) that are lower bounds. Sort them in descending order)
+
(Collect moves with values from hash(>= some depth) that are upper bounds. Sort them in descending order)
+
(moves that have no value from hash)

Don't know the position of moves that have no value from hash.

Maybe this ordering is a bit better than random.

[elcabesa]

I don't think that history euristic is totally random.
Have you tried collecting some statistics about percentage of hash hit you could achieve with this?

[Henk]

I don't think that history euristic is totally random.
Have you tried collecting some statistics about percentage of hash hit you could achieve with this?

It is just an idea. By the way it's about ordering remaining moves that have no rating from history heuristic table. But I think that all these extra look-ups in hash table may cost more than the gain you get from better ordering of these unrated moves. But who knows.

[jdart]

With PVS most moves do not have reliable scores in the hash table. Typically all moves except the PV to fail low and all you know about their scores is that the upper bound is alpha. Since it is the same upper bound for all moves that does not help with ordering.

--Jon