Evaluation Tuning

[Desperado]

Maybe it is not obvious to see what my algorithm is doing, but if you look at the snippet below, it gets clear,
that the algorithm is derived from simple linear multiple regression

Code: Select all

    double pseudoCode()
    {
        // objective y' = aX1 + bX2 + cX3...
        y = value(0) * coef(0)
        y+= value(1) * coef(1)
        y+= value(n) * coef(n)
        y+=            coef(n+1) // intercept

	
        // Optional: To replace the linear model it was just put into
        y = 1 / (1 + 1 * Exp(-y))
	
    }

Now adapting my code and data layout step by step the result was:

Code: Select all

    double pseudoode()
    {
        // objective y' = aX1 + bX2 + cX3...
        y = getEvaluationScore()

        // y = 1 / (1 + 1 * Exp(-y))
        y = sigmoid(y,400)

        // return error
        return pow(result-y,2)
    }

That my "solver" does not use matrices and compliated math stuff is not important (imo).
The results are the same and it is able to solve more complex stuff without any math skills.

1.
One of my first questions is: Did i transformed the linear model into a logistic model by
putting the linear function into the exponential function as parameter ?

2.
Who has experience with regression analysis in general and with non-material values in this context ?

3.
Does it make sense to tune on 128000 games for example if you get practically the same result for 8000 games ?

a.
Especially if you do not tune all parameters in one run ( which is practise, because you will
introduce new parameters/or change conditions for them all along)

b.
The solver is sensitive to the existing evaluation, so you need to tune the parameters again anyway
because of orthogonality ?

c.
Re-tuning from an already good vector needs much less computation than from a "zero"-vector.
Isn't a runtime to derive a set of 1 to 64 values within seconds/minutes/hours not a quick approach ?

However, just some words for the results i showed in the first post.
Each test is a run for itself. The times showed are individual for each test.
The values are the material values p,n,b,r,q, because i just noted it on the fly somewhere.

Code: Select all

Finished:  16000 games /  686395 positions /  90 210 225 350  705 Time:  62.99s 
Finished:  32000 games / 1415813 positions /  90 220 235 360  730 Time: 196.14s 
Finished:  64000 games / 2845859 positions /  85 205 225 350  705 Time: 222.24s 

What i really like is that i have the option to measure with or without BIAS, the algorithm will be terminated,
and it catches the global optimum, considering RESOLUTION/STEPZIZE are able to jump out of the local optimum,
and the limitation 1 for the resolution.
Further, what was done by hand so far, picking some new values for a subset of the evaluation, can be done on a sound
base, instead of a wild try.

What do you think ?

[jdart]

Not sure I 100% understand what you are doing. But linear regression, as the term implies, is for solving systems where the relationship between x and y is linear. Typically chess evaluation functions are nonlinear in the parameters.

Typically terms interact. This is even true for piece values. If you change the Knight value, you need to change the Rook value too, otherwise your calculation of the exchange values will be off.

Given nonlinearity and interactions, I do not think your stepwise method will have any assurance of convergence on a global minimum, unless you are using coarse enough steps that you can visit the whole search space.

There is a huge literature on optimization methods (especially in the past 20 years or so).

--Jon

[matthewlai]

Given nonlinearity and interactions, I do not think your stepwise method will have any assurance of convergence on a global minimum, unless you are using coarse enough steps that you can visit the whole search space.

That is true for all optimization methods. Nothing guarantees global minimum short of searching the entire parameter space. There can always be an infinitely deep well in a part of the landscape that wasn't explored.

[jdart]

That is true in general but some methods have proof of convergence given some assumptions about the characteristics of the function.

--Jon

[Gerd Isenberg]

Maybe it is not obvious to see what my algorithm is doing, but if you look at the snippet below, it gets clear,
that the algorithm is derived from simple linear multiple regression

Code: Select all

    double pseudoCode()
    {
        // objective y' = aX1 + bX2 + cX3...
        y = value(0) * coef(0)
        y+= value(1) * coef(1)
        y+= value(n) * coef(n)
        y+=            coef(n+1) // intercept

	
        // Optional: To replace the linear model it was just put into
        y = 1 / (1 + 1 * Exp(-y))
	
    }

Now adapting my code and data layout step by step the result was:

Code: Select all

    double pseudoode()
    {
        // objective y' = aX1 + bX2 + cX3...
        y = getEvaluationScore()

        // y = 1 / (1 + 1 * Exp(-y))
        y = sigmoid(y,400)

        // return error
        return pow(result-y,2)
    }

That my "solver" does not use matrices and compliated math stuff is not important (imo).
The results are the same and it is able to solve more complex stuff without any math skills.

1.
One of my first questions is: Did i transformed the linear model into a logistic model by
putting the linear function into the exponential function as parameter ?

... other questions snipped

Hi Michael,

if I understand your code correctly, your cost or loss function is mean squared error of outcome of the game (0, 0.5, 1) and winning prob (0..1) as sigmoid of eval score, and you apply logistic regression, like in Texel's Tuning Method, but unlike Eval Tuning in Deep Thought which _is_ linear regression. See Automated Tuning and specially Álvaro Begué's post.

Cheers,
Gerd

[Desperado]

Hi,

@Jon & Matthew

I need to reformulate that i find the best possible solution with the given restrictions by RESOLUTION and STEPSIZE. The highest resolution i use is one centipawn and there is no limitation for the stepsize.

If i use as shown in my example for the material computation a resolution of 5 centipawns and a stepsize of 5, the algorithm will try the changes -25,-20,...,25 for all parameters until none of these values will produce an improvement. After each improvement it starts again to check each possible change for each of the parameters.

Now if i define a resolution of 1 then the values are -5,-4,-3...5, so i could update the stepsize too, which would lead to -25,-24,-23,-22...25.
There will be a best solution for the given parameters.

Well, the resolution will give a restriction how accurate the result will be and the stepsize is used to leave "loval" optima.

So, as long there is no loacal minima that requires to be left with a jump greater than STEPSIZE * RESOLUTION i get a global optimum on the parameter set with the given RESOLUTION.

Well, it is early in the morning, i'll come back the evening...

@All

I do a minimization on a sigmoid function which uses the input of a linear combination as input parameter. If this is logistic regression, i do logistic regression

[Joerg Oster]

Thanks for sharing your ideas.

Well, i'm working with Jörg tuning idea with epd's. At the moment it's just a "play ground". I need to find more time to work on it.

My code isn't yet ready, but useable.
However, here is a clean fruit manner written code if someone need it.

https://www.dropbox.com/sh/781g8fuonz6i ... aSvaLrLFTa

Regards
Daniel

Well, I'm pretty sure you mean Alexandru's framework, which is based on Texel's and/or Gaviota's tuning method.
I was just offering some ideas ...

[Desperado]

Hello again.

Here is a task i want/need to solve but i guess some help is needed by the forum members.

Although the introduced algorithm works pretty fine for my purposes, "Tapered Evaluation" is a real handicap.
I am not sure if a new thread would be more useful, but i would like to talk about Tapered Evaluation mainly in context to regression analysis.

Here i go:

Until now i computed parameter values independently on game/material phase, which resulted in reasonable values.
For example 95 255 285 415 825 (p,n,b,r,q) for the material.

Already having in mind to improve the algorithm for the given context, and already observed that the basic algorithm
will give insane results like: [-55 125] [-50 205] [-45 240] [-160 365] [-155 855] (or similar).
I was able to observe these kind of numbers for differnet tuning algorithms i tried, so there is a substantial reason for it.


Further, a simple form for the material phase can look like this(ignoring scaling/rounding tricks/..., it does not matter):

Code: Select all

int Evaluation::getMaterialPhase(int tid,Position* pos)
{
    const int PHASE_P  = 0;
    const int PHASE_N  = 1;
    const int PHASE_B  = 1;
    const int PHASE_R  = 1;
    const int PHASE_Q  = 1;
    const int MAXPHASE = 16 * PHASE_P +
                          4 * PHASE_N +
                          4 * PHASE_B +
                          4 * PHASE_R +
                          2 * PHASE_Q ;

    // Count
    int wp = BitUtil::count64(pos->getBitboard(Piece::WP));
    int bp = BitUtil::count64(pos->getBitboard(Piece::BP));
    int wn = BitUtil::count64(pos->getBitboard(Piece::WN));
    int bn = BitUtil::count64(pos->getBitboard(Piece::BN));
    int wb = BitUtil::count64(pos->getBitboard(Piece::WB));
    int bb = BitUtil::count64(pos->getBitboard(Piece::BB));
    int wr = BitUtil::count64(pos->getBitboard(Piece::WR));
    int br = BitUtil::count64(pos->getBitboard(Piece::BR));
    int wq = BitUtil::count64(pos->getBitboard(Piece::WQ));
    int bq = BitUtil::count64(pos->getBitboard(Piece::BQ));

    // Phase
    int phaseW = PHASE_P * wp + PHASE_N * wn + PHASE_B * wb + PHASE_R * wr + PHASE_Q * wq;
    int phaseB = PHASE_P * bp + PHASE_N * bn + PHASE_B * bb + PHASE_R * br + PHASE_Q * bq;
    int phase  = phaseW + phaseB;

    return min(phase,14);
}

I checked various ideas and the most promising has been to balance the number of measured positions for any gamephase.
That means, if a parameter runs through a set of positions (eg: 500000), i made sure that every gamephase was included to the same amount.
phase[0]==75000,phase[1]==75000,...,phase[14]=75000.

I thought that the imbalance of the phases in a set of positions is the main reason for the strange results and the tuner will
weight/prefer phases with high frequency because the total error is minimized stronger then.

Well, that was a wrong interpretation ! Even with a balanced dataset the numbers keep to be like mentioned.
Another observation is, that the result values have the property that (mgValue+egValue)/2 are close to a realistic value.
Tough the mentioned values above look different, they are based on the balanced dataset which included only 15000 positions/phase.

Any ideas how to progress are welcome.


Thanks in advance

ps: i am not sure, but my impression is that this subject needs to be solved for different tuning algorithms. what do you think ?

[Ferdy]

Hello again.

Here is a task i want/need to solve but i guess some help is needed by the forum members.

Although the introduced algorithm works pretty fine for my purposes, "Tapered Evaluation" is a real handicap.
I am not sure if a new thread would be more useful, but i would like to talk about Tapered Evaluation mainly in context to regression analysis.

Here i go:

Until now i computed parameter values independently on game/material phase, which resulted in reasonable values.
For example 95 255 285 415 825 (p,n,b,r,q) for the material.

Already having in mind to improve the algorithm for the given context, and already observed that the basic algorithm
will give insane results like: [-55 125] [-50 205] [-45 240] [-160 365] [-155 855] (or similar).

Can you describe what is this basic algorithm that gives insane results?

[Ferdy]

Further, a simple form for the material phase can look like this(ignoring scaling/rounding tricks/..., it does not matter):

Code: Select all

int Evaluation::getMaterialPhase(int tid,Position* pos)
{
    const int PHASE_P  = 0;
    const int PHASE_N  = 1;
    const int PHASE_B  = 1;
    const int PHASE_R  = 1;
    const int PHASE_Q  = 1;
    const int MAXPHASE = 16 * PHASE_P +
                          4 * PHASE_N +
                          4 * PHASE_B +
                          4 * PHASE_R +
                          2 * PHASE_Q ;

    // Count
    int wp = BitUtil::count64(pos->getBitboard(Piece::WP));
    int bp = BitUtil::count64(pos->getBitboard(Piece::BP));
    int wn = BitUtil::count64(pos->getBitboard(Piece::WN));
    int bn = BitUtil::count64(pos->getBitboard(Piece::BN));
    int wb = BitUtil::count64(pos->getBitboard(Piece::WB));
    int bb = BitUtil::count64(pos->getBitboard(Piece::BB));
    int wr = BitUtil::count64(pos->getBitboard(Piece::WR));
    int br = BitUtil::count64(pos->getBitboard(Piece::BR));
    int wq = BitUtil::count64(pos->getBitboard(Piece::WQ));
    int bq = BitUtil::count64(pos->getBitboard(Piece::BQ));

    // Phase
    int phaseW = PHASE_P * wp + PHASE_N * wn + PHASE_B * wb + PHASE_R * wr + PHASE_Q * wq;
    int phaseB = PHASE_P * bp + PHASE_N * bn + PHASE_B * bb + PHASE_R * br + PHASE_Q * bq;
    int phase  = phaseW + phaseB;

    return min(phase,14);
}

I use something like the ff.
const int PHASE_N = 3;
const int PHASE_B = 3;
const int PHASE_R = 5;
const int PHASE_Q = 10;