MENU
MIP - Material Imbalance Pruning
As far as I know Material Imbalance Pruning is a new technique that offers quite some new features to improve the search, or even the evaluation. Possibilities -
1. Reductions
2. Pruning
3. Lazy eval
4. Score corrections.
Data structure
Meaning the number of board piece types are stored in its unique cell, in total there are 236.196 cells representing all the possible board combination in chess except the rare cases when there 3 bishops or 5 queens on the board, these kind of positions are automatically ignored.
With an utility (see left above) we filled the 236.196 cells using 13.7 billion Leela epds and stored the WDL outcome in each 32 bit representing the number of positions plus the WDL percentage, see Phase III, Cell overview.
Arrived here we can explore many interesting possibilities, let's take 1 . reductions as our first example, consider the 3 tables below. In case if a call to the table and it returns a value of 0% or 100% it means that the current board position is totally lost or won from the white point of view and is good candidate for a reduction, and the more positions the cell contains the reliable the WDL percentage.
2. Pruning
In case of WDL result of 0% or 100% you can consider it as a TT or TB hit, add a large bonus to the score and prune, risky but I never tried.
3. Lazy Eval
It's possible to replace the expensive evaluation in case DEPTH<=0 with Lazy Eval when the cell information is good enough, just add a bonus based on the percentage and sufficient number of positions to the material score. Lazy Eval is dangerous except when you do it right, Lazy Eval as described on the CPW is not the way to do it. Or just follow the large discussion on Lazy Eval at Talkches.
4. Score corrections
Based on the percentage and sufficient number of positions apply a bonus malus table to update the evaluation score, example :
Enough to explore. I only developed the system and made sure the code is bug free . I haven't tested it since I am on a break.
_____________________________________________________________________________________________
The Code
At program start read the mip.bin into memory.
_____________________________________________________________________________________________
​
Calling the MIP table
count is the number of positions of the cell.
perc is the WDL result.
From here invent your own ideas.
Regarding the speed-up instruction, it's skipping cells where the material balance is equal or one pawn up or down and thus it's highly unlikely a reliable WDL might occur as after all the algorithm is about material imbalance... And so we are avoiding the expensive 10 dimensional table look up code.
​
Remarks and observations
1. An observation is made the system gets the most hits in the end game.
2. The percentages in the cells are from the white-point-of-view.
mip.bin