Better move ordering to reduce search time

[jamesqo]

https://www.chessprogramming.org/Move_Ordering

[jamesqo]

One possible method is to calculate the heuristic values for each successor before sorting them (descending or ascending, depending on the active player) then searching them in that order.

It could be challenging to implement this without introducing memory allocations or significant slowdowns due to re-applying moves; we would essentially want to do something like this:

// Before
var pq; // priority queue
using var moves = state.GetPseudoLegalMoves(); // this returns a PooledList now since we're no longer iterating it lazily
foreach (var move in moves) {
    if (!state.TryApply(move, out _)) continue;
    pq.Add(state.Snapshot(), priority: Evaluation.Heuristic(state));
}
// dispose of moves here
while (!pq.IsEmpty) { state.Restore(in pq.Pop()); ... }

[jamesqo]

Alternatively (following the move ordering guide):

• Captures/promotions first
  • Use MVV/LVA (apparently it's much simpler to write than SEE, despite not covering all cases)
• Then non-captures
  • Use history heuristic, which is a generalized version of the killer heuristic

[jamesqo]

Move ordering for captures was implemented in https://github.com/jamesqo/chess-bot/pull/26