[FEATURE] Use PSQTs during move ordering

[dannyhammer]

Description: During move ordering, moves are currently given a "base score" that is modified through move ordering techniques such as MVV-LVA and (once #67 merges) History Heuristic. Instead of assigning the same "base score" to all moves, give each move an initial score based on their PSQT value. After all, PSQTs are (currently) the only way that the eval function can tell whether two positions of equal material are better/worse than each other. The intent here is to make it so that "bad" moves (from a static eval's perspective) get ordered last, and therefore can be pruned easier. This would, of course, require that the PSQT's score does not interfere with any existing move ordering heuristics.

I believe the code would be as simple as adding the following in the Search::score_move method:

score += PSQT[piece][mv.to()] - PSQT[piece][mv.from()];

As an example, using the current PSQTs in the engine, the move Nf3 would receive a score of:

PSQT[WhiteKnight][f3] - PSQT[WhiteKnight][g1] = 337 - 301 = 36

Requirements:

• [ ] Set a move's "base score" to be it's PSQT value
• [ ] Ensure that PSQT scores cannot be greater than scores from History Heuristic or other move ordering heuristics

[dannyhammer]

On further investigation, it appears this will be more difficult than expected.

The problem lies in the fact that PSQTs for individual pieces have both middle-game and end-game tables. So, in order to interpolate between these two tables, we need an endgame weight. Currently, that's only obtainable after constructing an Evaluator instance. It would be expensive to construct an Evaluator just to aid in scoring the moves. It might be worth it- I don't know how much Elo this feature would gain.

I would suggest shelving this issue for now, until we have internal board representation (rather than using chessie).