TLDR: I'm still working on making my evaluation "king relative".
A quick recap: A few posts back I described how I was tuning separate sets of PSTs and visualized them. The similarity between tiles of the same piece-type inspired me to first implement a minimal approximation based on just 10 (additional) piece-square tables. With these each piece's material value is modified based on the position of the two kings. The placement of the piece however is not considered for that bonus. Despite this rather crude approximation the additional tables helped to gain a few Elo.
But my original idea was a bit more ambitious then just adding a bunch of additional lookup tables. The idea started with a simple realization: While the original meaning of a PSTs is just a lookup table, for "tapered PSTs" that work much better in practice, this is no longer true. Instead each piece-square value is now defined by a very tiny linear function:
value = mg + eg * phase
What I wanted to try is to stick to this linear model but add more terms to it. Terms that are based on the king files and ranks. My expectation was that a higher dimensionality would allow me to increase the accuracy of the linear model but of course it would also have a higher performance cost to compute these increasingly complex formulas each time a piece moves (Leorik uses incremental updates) and most importantly recompute *all* pieces each time one of the kings move. Would it be worth it? That's why I started with the minimal viable thing with the 10 (or even just 5) lookup tables to establish the baseline the high-dimensional linear model would have to beat.
The other problem with my idea was that the best process I could come up with to compute the coefficients for my linear model was quite cumbersome: I planned to train a lot of "normal" PSTs on selected subsets of my training data. (that's where the visualization came from) Then I wanted to extract the relevant features of a position of the subset and use the matching set of PSTs to get the expected value of each piece on that position. That way I'd be able to gather input and expected output data for each piece-square combination.
Then I planned to find the coefficients using QR decomposition as implemented in MathNet library:
Code: Select all
// Solve for the regression coefficients using QR decomposition
QR<double> qr = inputs.QR();
Matrix<double> qTranspose = qr.Q.Transpose();
Vector<double> y = qTranspose * outputs;
Vector<double> coefficients = qr.R.Solve(y);
But did I really want to add a 3rd party dependancy to Leorik? So far everything was "from scratch" so I tried to learn more about how to solve multiple linear regression problems on my own. And only when "gradient descent" was mentioned it hit me that I had already everything I needed! There's really no need to compute all these sets of PSTs on subsets of the training set. I should just modify my tuner to work with an arbitrary amount of dimensions (instead of just midgame and endgame) and then I could start to describe the linear model I had in mind by just generating the "variables" and it'd find me the coefficients automatically that minimize MSE.
In my tuner a chess position is converted into an array of floats and by increasing the dimensionality of my linear model from 2 dimensions (mg + eg) to something like 14 dimensions all that really changed was the size of that float array. (and about a hundred lines of implementation details^^)
The code below adds 14 features for each piece-square combination in a position into an array of about 11,000 floats total.
Code: Select all
private static void AddFeatures(float[] features, int index, int sign, float phase, int kingSqr, int oppKingSqr)
{
float kFile = Bitboard.File(kingSqr) / 3.5f - 1f;
float kRank = Bitboard.Rank(kingSqr) / 3.5f - 1f;
float oppKFile = Bitboard.File(oppKingSqr) / 3.5f - 1f;
float oppKRank = Bitboard.Rank(oppKingSqr) / 3.5f - 1f;
//Base
features[index++] += sign;
features[index++] += sign * kFile * kFile;
features[index++] += sign * kFile;
features[index++] += sign * kRank * kRank;
features[index++] += sign * kRank;
features[index++] += sign * oppKFile * oppKFile;
features[index++] += sign * oppKFile;
features[index++] += sign * oppKRank * oppKRank;
features[index++] += sign * oppKRank;
//Endgame (* phase)
features[index++] += sign * phase;
features[index++] += sign * kFile * phase;
features[index++] += sign * kRank * phase;
features[index++] += sign * oppKFile * phase;
features[index++] += sign * oppKRank * phase;
}
...and the tuner finds the associated coefficients that then look like this:
Code: Select all
405, -3.57f, -13.43f, 29.03f, 32.36f, -8.51f, 10.91f, 11.32f, 28.78f, 143.63f, 24.87f, 76.69f, 45.98f, 61.77f
And that's how material of a piece on a square is now calculated: Look the above coefficients up and use them in a formula that is based on the same features that we used in the tuner:
Code: Select all
private void AddMaterial(int pieceIndex, int squareIndex, int myKingSqr, int oppKingSqr)
{
int entryIndex = Weights.MaterialTerms * ((pieceIndex << 6) | squareIndex);
float kFile = Bitboard.File(myKingSqr) / 3.5f - 1f;
float kRank = Bitboard.Rank(myKingSqr) / 3.5f - 1f;
float oppKFile = Bitboard.File(oppKingSqr) / 3.5f - 1f;
float oppKRank = Bitboard.Rank(oppKingSqr) / 3.5f - 1f;
Material.Base += Weights.MaterialWeights[entryIndex + 0] // Base
+ Weights.MaterialWeights[entryIndex + 1] * kFile * kFile
+ Weights.MaterialWeights[entryIndex + 2] * kFile
+ Weights.MaterialWeights[entryIndex + 3] * kRank * kRank
+ Weights.MaterialWeights[entryIndex + 4] * kRank
+ Weights.MaterialWeights[entryIndex + 5] * oppKFile * oppKFile
+ Weights.MaterialWeights[entryIndex + 6] * oppKFile
+ Weights.MaterialWeights[entryIndex + 7] * oppKRank * oppKRank
+ Weights.MaterialWeights[entryIndex + 8] * oppKRank;
Material.Endgame += Weights.MaterialWeights[entryIndex + 9] // Phase-Bonus
+ Weights.MaterialWeights[entryIndex + 10] * kFile
+ Weights.MaterialWeights[entryIndex + 11] * kRank
+ Weights.MaterialWeights[entryIndex + 12] * oppKFile
+ Weights.MaterialWeights[entryIndex + 13] * oppKRank;
}
For now it seems to work as expected: The MSE (mean squared error between predicted outcome and label on a set of 2.8M positions sourced from selfplay games) goes down significantly which is indicating that the accuracy has improved.
And the other expectation is also met: It's pretty slow and the NPS of my engine tanks from 7M nps to 3M nps.
If that sounds crazy, I'm sorry. Not even I'm convinced that it's a good idea but it wasn't obviously bad either which piqued my curiosity about whether it'd work or not. And now I know that it "worked" in so far that a build with that eval doesn't stand a chance in a time-limited match but in a node-limited match the new version is ~70Elo above base line Leorik 2.4.
The remaining work is all about optimizing the code for performance which to me is the most fun part of chess programming.
For example the above looks like a great opportunity to use SIMD, right? The expensive part of the code above is basically just a Dot product. And I'm flexible to adjust the number of features to exactly fill up a 256bit registers.
In the worst case scenario I still might not make any real progress on Leorik here but at least it's a fun way of not making progress! =)
