[Design] Move ordering refactor

[KYLChiu]

Survey of existing move ordering techniques:

Heuristic name	Required information to evaluate	Brief description
MVV-LVA	(board, move)	For captures, evaluate victim - aggressor score, higher implies ordered first.
Killer	(killer_table, move, depth)	Strong non-capturing 1-3 moves causing beta-cutoff per ply (depth), ordering these first.
History	(history_table, move, depth)	Order based off the number of cutoffs of this move, irrespective of position. This is stored in 2 64 64 (side_2_move from_sq to_sq) table. These moves are given an extra score based off the depth of the move.
Principal Variation (PV)	(pv_sequence, move)	Place the best move from previous iterative deepening iteration first.
Hash/TT	(transposition_table, move)	Order moves found from tranposition table first (either PV or beta-cutoff), sort of encompasses PV move.
Countermove	(countermove_table, move)	Store non-capturing move causing beta-cutoff in a (2 64 64, side_2_move from_sq to_sq) table, irrespective of depth. If the move is found in the table, its given extra points.
Internal Iterative Deepening (IID)	(IID_move, move)	Uses a shallow depth search to generate an approximation to PV move, if no hash/PV move found.

[ccjeremylo]

Interesting - look forward to this 👀

[KYLChiu]

From the above it looks like PV, Hash/TT, and IID require information from the searcher in some way (the transposition table or PV approximation move). Moreover for history, killer and countermove heuristic, not only do we need this information from the searcher, we need to update their respective tables there too (i.e. we only update the table when there is a cutoff, which we can't possibly know in the move ordering class).

In the current evaluate function we only pass (board, move): def evaluate(self, board: Board, move: chess.Move) -> float:

It looks like this won't be enough to encompass all cases. Any ideas on how to incorporate generically?

[KYLChiu]

@ccjeremylo @yibeili

As discussed the issue is due to circular responsibilities of searcher and move ordering. Searcher depends on move ordering for AB-pruning but move ordering depends on searcher to update it's depedent attributes. To break this circular juggling I propose:

• We keep the existing MoveOrder (maybe renamed to MoveOrderingHeuristic or MoveOrderingStrategy) parent class with evaluate signature:

  def evaluate(self, move: chess.Move) -> float:
  pass

  FYI: TIL this is known as a strategy pattern.

• All child classes of MoveOrder, e.g. MvvLvaHeuristic or KillerMoveHeurstic now are built every time when we need to call order moves. We inject the dependencies on construction. All information now comes from the searcher, which means the searcher owns any dependencies. The runtime difference for doing this should be negligble because of python's pass by assignment principle.

For example for KillerMoveHeuristic:

class KillerMoveHeuristic(MoveOrder):
    def __init__(self, killer_table):
        self._killer_table = killer_table

where killer_table is now a MinimaxVariant level object.

• _ordered_moves in MinimaxVariant will take in the MoveOrder child class as an argument as well, allowing it to decide which evaluate function to call.

  @staticmethod
  def _ordered_moves(move_ordering_strategy: MoveOrder, legal_moves: Any) -> Any:
      return sorted(
          legal_moves,
          key=lambda move: (move_ordering_strategy.evaluate(move),),
          reverse=True,
      )

• We will move the _build_moveorder factory onto MinimaxVariant - and possibly change it to be a dispatching function, so that we can determine which move ordering we need once, and just call that create function over and over again. Whether this will need some sort of Dependency Injection is not quite clear to me yet, hopefully not.

[ccjeremylo]

Will discuss further details with you offline - the design looks quite nice to me, biggest question I have is that I am not sure how we can combine mover order strategies using this design. The static method:

@staticmethod
def _ordered_moves(move_ordering_strategy: MoveOrder, legal_moves: Any) -> Any:
        return sorted(
            legal_moves,
            key=lambda move: (move_ordering_strategy.evaluate(move),),
            reverse=True,
        )

only takes in a single unique move_ordering_strategy, so how do we mix and match them?

[yibeili]

where killer_table is now a MinimaxVariant level object.

What does level mean here?

[yibeili]

i am not too sure :( my first question is that what problem will circular calling cause? and secondly, what if we have a separate class storing the info searcher wants from moveorder and the info moveorder from searcher?

[KYLChiu]

Will discuss further details with you offline - the design looks quite nice to me, biggest question I have is that I am not sure how we can combine mover order strategies using this design. The static method:

@staticmethod
def _ordered_moves(move_ordering_strategy: MoveOrder, legal_moves: Any) -> Any:
        return sorted(
            legal_moves,
            key=lambda move: (move_ordering_strategy.evaluate(move),),
            reverse=True,
        )

only takes in a single unique move_ordering_strategy, so how do we mix and match them?

@ccjeremylo Mixing and matching will be done through multiple inheritance or composition. Lets call it the CompositeMoveOrdering - this will have

class CompositeMoveOrdering(MoveOrder, MvvLva, Killer, ...)

or

class CompositeMoveOrdering(MoveOrder):

  def __init__(MvvLva, Killer, ...):

[KYLChiu]

where killer_table is now a MinimaxVariant level object.

What does level mean here?

@yibeili As in the killer_table will move into the MinimaxVariant class, which will own the object (i.e. be responsible for it's creation and deletion).

[KYLChiu]

i am not too sure :( my first question is that what problem will circular calling cause? and secondly, what if we have a separate class storing the info searcher wants from moveorder and the info moveorder from searcher?

@yibeili Circular design is usually avoided because it introduces tight coupling. Tight coupling causes rigidity; as you saw, each time we introduce a new type of move ordering, we need to extend the evaluate function. See Open/Closed principle. I'm sure chatGPT can give you more.

Re the second question, introducing a segway container class to hold your dependencies and inserting them when needed is called Dependency Injection. However this isn't much different to what I'm proposing here - instead of injecting them at run time and having mutable classes, we inject them on construction.