Without precise tweaking of the scoring, we can easily wind up pursuing only one branch of the possible solution space until the heap is too large to continue. Some ideas to pursue:
Change the progress score scale factor after a while.
We can block for a time and rescore all the heap states, which is not ideal but can simultaneously clean out the heap of too-old states.
Lowering the weight of the progress factor in this way prioritizes states with lower elapsed times (more breadth).
Reraising the weight of the progress factor would then prioritize states closer to finishing (more depth).
Occasionally make a greedy run on a state to see if we can get a better solution from it.
Occasionally grab a block of states from the heap, choose one based on different metrics, and return the rest.
Run a separate thread for greedy runs only, basically looking for faster solutions.
It could return all the states found from each step as usual, but this could result in extreme heap growth.
It could be limited to only returning anything if it finds a better solution.
Without precise tweaking of the scoring, we can easily wind up pursuing only one branch of the possible solution space until the heap is too large to continue. Some ideas to pursue: