Since alpha beta pruning depends on move ordering, we will now consider moves as also to be nodes.
Therefore, we add 1 more data type to gen_t which is our move list called score.
The idea is that moves would be generated and ordered based on this score.
The idea for score is this:
If it is a capture, then score is stored using MVV-LVA principle.
Most valuable victim - Least valuable attacker.
If its not a capture, then we will introduce another array - of 64 x 64 elements called history.
This is different from hist_dat which is a 1 dimensional array used for takeback.
In this history array, the from square and the to square of a move is picked and represented as indexes of the array.
The score is stored as the int.
If a non-capture is causing a cut-off, then it will be scored high.
Insertion sort is used only for that particular place in move list i.e. if I am at the third move in the list, then I'll only make sure that the move at 3rd position is the third most scored move.
We will not sort the complete list in descending order. This is because if a cut-off is achieved, then all the other moves of the position become irrelevant.
We will also use Iterative Deepening. i.e. First search for a depth of 1.
Find the best move and let it be stored in the PV table.
Then we search for depth = 2.
But, this time, we know what the best move was at depth = 1.
We order it as the leftmost move so that it gets searched first.
Thus, we would use the information from search at previous depth in search of the current depth and call search iteratively by increasing depth.
With these 3 tools, we will do move ordering.
1. First we will assign another variable called score to moves.
2. Then for captures we will use MVV-LVA.
3. For non-captures, we will use history.
4. For PV nodes found in previous shallower depth search, we will assume that it should be the best move when searched at higher depth, and we will order it as assumed.
Note that the function sort_pv actually sorts nothing.
It is just used to increase the score of the pv move so that the actual sort function picks that move first.