A non-programmer idea for Stockfish, probably worthless

[Isaac]

Hello guys!
I'm trying to get a vague grasp on material.cpp through the wiki of Stockfish (http://stockfish.wikispaces.com/material.cpp).
What I understood is that there are 2 "reference" phases in Stockfish's code: phase_midgame and phase_endgame. And "almost" an infinity (around 11 kilo) of possible game phases according to non-pawn material.
The material imbalance depends on the game phase which is calculated via a quadratic polynomial (where the variable is the number of non-pawns material and there are other parameters that depends on bishop pair but that's less clear to me) that it used to interpolate between 2 "points" which are in fact

Code: Select all

const Value MidgameLimit = Value(15581);

and

Code: Select all

const Value EndgameLimit = Value(3998);

My idea was to try a 3rd degree or 4th degree polynomial instead of a quadratic.
Since it would require more calculations of SF, I realize that it would make it slower. On the other hand I expect (when well tuned of course, which might require several hundreds of thousands of games?) it to get a slightly more accurate evaluation.

Another possible idea but maybe worse because of more slow down and introducing much more complexity in the code would be to introduce a new game phase and use a 2nd degree spline in order to interpolate through the game phases.

We could add even more parameters (such as the bishop pair) to try to get a more accurate eval in the future.

Thoughts?
Please don't retain yourself If this is madness or pure nonsense, say it.

[Joost Buijs]

My idea was to try a 3rd degree or 4th degree polynomial instead of a quadratic.
Since it would require more calculations of SF, I realize that it would make it slower. On the other hand I expect (when well tuned of course, which might require several hundreds of thousands of games?) it to get a slightly more accurate evaluation.

Another possible idea but maybe worse because of more slow down and introducing much more complexity in the code would be to introduce a new game phase and use a 2nd degree spline in order to interpolate through the game phases.

We could add even more parameters (such as the bishop pair) to try to get a more accurate eval in the future.

Thoughts?
Please don't retain yourself If this is madness or pure nonsense, say it.

I don't think this is nonsense, I've been thinking about this as well.

At the moment my engine uses linear interpolation to determine material value versus game phase. Using a parabola (probably what Stockfish does) would be better, but this is still not accurate enough.

The difference in speed between calculating a 2nd or a 3th degree polynomial is almost negligible when you compare this to the time taken by the positional evaluation. The only drawback is that you have to tune an extra parameter.

[mcostalba]

Thoughts?

I don't think you have clear ideas about what is quadratic and what is linear: game phase is linearly interpolated between the 2 limits.

Probably the 'quadratic' word popped up in your mind when reading the comments in the following code:

Code: Select all

    // Second-degree polynomial material imbalance by Tord Romstad
    for (pt1 = NO_PIECE_TYPE; pt1 <= QUEEN; ++pt1)
    {
        pc = pieceCount[Us][pt1];
        if (!pc)
            continue;

        v = LinearCoefficients[pt1];

        for (pt2 = NO_PIECE_TYPE; pt2 <= pt1; ++pt2)
            v +=  QuadraticCoefficientsSameColor[pt1][pt2] * pieceCount[Us][pt2]
                + QuadraticCoefficientsOppositeColor[pt1][pt2] * pieceCount[Them][pt2];

        value += pc * v;
    }

But this has nothing to do with game phase. In case you are interested in this piece of code I'd suggest to look up what each variable /array mean, this will require a bit of time perhaps, but not much more than writing a quick post

[Isaac]

Thank you guys.
I realize my confusion now.

Actually a linear interpolation between the game phases makes more sense to me than a quadratic one to me, now. Because for instance I can hardly imagine that being down one bishop (or pawn, if we were to include them in order to calculate the game phase, but this isn't how Stockfish works as of now) compared to the previous move would translate as being further away from the end game phase.

However yes, in order to calculate the material imbalance, I'd try to investigate if a higher order polynomial (with more parameters) would do a noticeably better job.

[mcostalba]

or pawn, if we were to include them in order to calculate the game phase, but this isn't how Stockfish works as of now

I did some quick test in a far past to include pawns in game phase calculation and not just no-pawn material, but was not good..anyhow could be right time to retest it

[Isaac]

Yet another quick post of mine, sorry.
It is possible to have a strictly decreasing quadratic function to interpolate through 2 points. So the idea of interpolating through 2 phases with a quadratic might still be "ok", but one would have to use a criteria to choose between the infinity of possible quadratic functions that passes through those 2 points.
Maybe one could even use a decaying exponential function to interpolate through the game phases.
Though I don't really know how much "elo" one can find there.

Intuitively I think that getting a more accurate material imbalance calculation could lead to a greater gain in strength compared to a better calculation of game phase but I might be wrong.

@Marco, I have seen such tests but it was only a few months ago (2 at most if I remember well). I don't remember who did them though, and yes I remember they failed.
Maybe we could try the non linear interpolation between the 2 game phases introducing the counting of pawns. A decaying function of the type y(x)=a*exp(-b*x) has only 2 parameters (like the current linear interpolation). Not sure it would work better than the linear one. Maybe worth a try.

[mcostalba]

Maybe we could try the non linear interpolation between the 2 game phases introducing the counting of pawns. A decaying function of the type y(x)=a*exp(-b*x) has only 2 parameters (like the current linear interpolation). Not sure it would work better than the linear one. Maybe worth a try.

This post made came to my mind old memories

Actually the tweak of interpolation was the first patch I tried just after I forked Glaurung (!)

https://github.com/mcostalba/Stockfish/ ... 6471f28e1b

I had also committed it (see the date, 5 years ago!!!) but then reverted, at the time my standard test was of few hundreds games on my old and slow PC.

I was using a kind of transition where instead of climbing linearly the line started almost flat or with lower steep than linear and about at half way it climbed in super linear way to end the run at the other point in the same symmetrical flat way.

[Isaac]

This post made came to my mind old memories

Hehe, I would never have guessed so.

Actually the tweak of interpolation was the first patch I tried just after I forked Glaurung (!)

https://github.com/mcostalba/Stockfish/ ... 6471f28e1b

I had also committed it (see the date, 5 years ago!!!) but then reverted, at the time my standard test was of few hundreds games on my old and slow PC.

I was using a kind of transition where instead of climbing linearly the line started almost flat or with lower steep than linear and about at half way it climbed in super linear way to end the run at the other point in the same symmetrical flat way.

The description of the function you used makes me think of the "error function".

With second thoughts, I don't think that a decaying exponential would be appropriate. Given 2 points (x0,y0) and (x1,y1) such that y1>y0, I don't think that it's always possible to find a function f such that f(x)=a*exp(-b*x) where a and b are constants be to be found and such that f satisifies the boundary conditions f(x0)=y0 and f(x1)=y1. There are arbitrary cases where it is not possible. But what matters is the case of Stockfish with x0=3998, y0=0 (or 1 because 0 would either give a=0 or b worth infinity), x1=15581 and y1=128 and I don't think it's possible: I reach a non linear system of 2 equations with 2 unknows but it doesn't seem to have solution (it doesn't even make sense). I may be wrong and could have done some error though.
So I tried to use a quadratic to interpolate the game phase. Since I am interpolating only 2 points with a 2nd degree polynomial, I will be left with a free parameter. I have in mind using the SPSA tuner to tune it.
The polynomial is approximately worth p(x)=5.64x10^(-7) * x^2 -9+b (-3182-x^2 *5.11x10^(-5)+x) where b could be in principle any value. In other words, for any value of b, this polynomial will interpolate through the game phase and will be worth 128 for when x=15581 and worth 0 for when x=3998. Here x stands for the "npm" value in Stockfish's code, namely the non pawn material value.
b could be either positive or negative. When b is approximately worth 0.01 you get the original Stockfish linear interpolation. So I already know what is the value to start with, for the SPSA tuner.

I've plotted the polynomial for a range of values for b, and I think that a reasonable range for these values could be around [-0.011, 0.030]. Else the parabola gets really too pronounced. This gives you the order of magnitude for b.

If I understand more or less correctly Stockfish's code (without knowing how to write a hello world program in c++), I'd have to change the line 264 of material.cpp, which currently reads

Code: Select all

 : Phase(((npm - EndgameLimit) * 128) / (MidgameLimit - EndgameLimit));

to

Code: Select all

: Phase( 5.64*pow(10,-7)*pow(npm,2) -9 + b *(-3182-pow(npm,2)*5.11*pow(10,-5) +npm) );

where b would be the well tuned value I find with the SPSA.

I am still skeptical on how much elo there's to gain using a 2nd order polynomial instead of a 1st order in order to calculate the game phase. But if I succeed using the SPSA tuner to tune b, I will probably give 1 shot in the fishtest. Unless you tell me not to, or point out errors I am/could be making.

[mcostalba]

The description of the function you used makes me think of the "error function".

Yes you are right, is similar to this one:

http://en.wikipedia.org/wiki/Error_function

But a bit linearized to be faster to calculate.

I am still skeptical on how much elo there's to gain using a 2nd order polynomial instead of a 1st order in order to calculate the game phase. But if I succeed using the SPSA tuner to tune b, I will probably give 1 shot in the fishtest. Unless you tell me not to, or point out errors I am/could be making.

Of course you can, I even suggest to just pick a value of your choice for b (like 0.01) and run in fishtest against master, so to verify everything is more or less ok and also wet your hands with test submitting.

[Joerg Oster]

or pawn, if we were to include them in order to calculate the game phase, but this isn't how Stockfish works as of now

I did some quick test in a far past to include pawns in game phase calculation and not just no-pawn material, but was not good..anyhow could be right time to retest it

I did test it not too long ago, and it failed.