MoveOrdering++

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Henk
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

MoveOrdering++

Post by Henk » Fri Aug 16, 2013 5:00 pm

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
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: MoveOrdering++

Post by bob » Fri Aug 16, 2013 5:17 pm

Henk wrote: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
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

Re: MoveOrdering++

Post by Henk » Fri Aug 16, 2013 5:41 pm

bob wrote:
Henk wrote: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
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: MoveOrdering++

Post by elcabesa » Fri Aug 16, 2013 6:38 pm

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
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

Re: MoveOrdering++

Post by Henk » Fri Aug 16, 2013 7:31 pm

elcabesa wrote: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
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: MoveOrdering++

Post by elcabesa » Fri Aug 16, 2013 7:47 pm

how do you think to implement this?

Henk
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

Re: MoveOrdering++

Post by Henk » Fri Aug 16, 2013 8:10 pm

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
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: MoveOrdering++

Post by elcabesa » Fri Aug 16, 2013 8:25 pm

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
Posts: 5816
Joined: Mon May 27, 2013 8:31 am

Re: MoveOrdering++

Post by Henk » Fri Aug 16, 2013 8:37 pm

elcabesa wrote: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
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: MoveOrdering++

Post by jdart » Sat Aug 17, 2013 2:05 pm

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

Post Reply