Linear vs. Nonlinear Evalulation
Moderators: bob, hgm, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 Posts: 2127
 Joined: Wed Mar 08, 2006 7:47 pm
 Location: Hattingen, Germany
Linear vs. Nonlinear Evalulation
I have a question about the definition of linear versus nonlinear evaluation.
Linear eval is the dotproduct of features and weights. Assuming a passed pawn piecesquare table contains for instance the square (x*x) of baserank distance (x), is this still linear evaluation?
Is nonlinear eval necessarily connected with piece interactions? Or what is its exact definition?
Thanks,
Gerd
Linear eval is the dotproduct of features and weights. Assuming a passed pawn piecesquare table contains for instance the square (x*x) of baserank distance (x), is this still linear evaluation?
Is nonlinear eval necessarily connected with piece interactions? Or what is its exact definition?
Thanks,
Gerd
 hgm
 Posts: 23718
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: Linear vs. Nonlinear Evalulation
This is a bit arbitrary. But I guess he dependence on individual piece positions is not taken into account in this classification. Piecesquare tables are in general filled with irregular functions that are far from linear, but no one would consider that nonlinear eval. A Bishop pair term could be called nonlinear, but I don't believe anyone would do that either.

 Posts: 2127
 Joined: Wed Mar 08, 2006 7:47 pm
 Location: Hattingen, Germany
Re: Linear vs. Nonlinear Evalulation
Yes, one can interpret piece square table as weight vector, which are multiplied with a vector of boolean (absence or existence) features. Thus a "linear" combination or dotproduct, even if the features are only zero or one.hgm wrote:This is a bit arbitrary. But I guess he dependence on individual piece positions is not taken into account in this classification. Piecesquare tables are in general filled with irregular functions that are far from linear, but no one would consider that nonlinear eval. A Bishop pair term could be called nonlinear, but I don't believe anyone would do that either.
Code: Select all
for all i sum += Feature[i] * weight[i];
Re: Linear vs. Nonlinear Evalulation
I believe the general idea is that if you sum weights, the function is linear. As in y = aX + b; If you product things, say king position * pieces attacking squares close to king * pawn shelter around king, then it is considered beyond linear or as it is sometimes called, beyond firstorder.Gerd Isenberg wrote:Yes, one can interpret piece square table as weight vector, which are multiplied with a vector of boolean (absence or existence) features. Thus a "linear" combination or dotproduct, even if the features are only zero or one.hgm wrote:This is a bit arbitrary. But I guess he dependence on individual piece positions is not taken into account in this classification. Piecesquare tables are in general filled with irregular functions that are far from linear, but no one would consider that nonlinear eval. A Bishop pair term could be called nonlinear, but I don't believe anyone would do that either.The terms linear versus nonlinear evalulation were mentioned in several papers, but I wonder what their definition is. May be its arbitrary or outdated.Code: Select all
for all i sum += Feature[i] * weight[i];
Re: Linear vs. Nonlinear Evalulation
I guess the usual definition of a linear function is one where the output of a sum of the inputs is equal to the the output of each individual input. A function f is linear iff:Gerd Isenberg wrote:I have a question about the definition of linear versus nonlinear evaluation.
Linear eval is the dotproduct of features and weights. Assuming a passed pawn piecesquare table contains for instance the square (x*x) of baserank distance (x), is this still linear evaluation?
Is nonlinear eval necessarily connected with piece interactions? Or what is its exact definition?
Thanks,
Gerd
f(a+b) = f(a) + f(b).
f(c*a) = c*f(a)
So I'd guess an evaluation function is linear if
f(feature1_a + feature1_b,feature2_a + feature2_b,feature3_a + feature3_a...) = f(feature1_a,feature2_a,feature3_a) + f(feature1_b,feature2_b,feature3_b) = f(feature1_a)+ f(feature2_a) + f(feature3_a)+f(feature1_b)+f(feature2_b)+f(feature3_b) ...
PSTs would be nonlinear because PST[sq1+sq2] != PST[sq1] + PST[sq2]
Simple material eval and mobility eval could be linear:
materialEval(onepawn + onepawn) = materialEval(onepawn) + materialEval(onepawn)
Re: Linear vs. Nonlinear Evalulation
I guess PSTs are linear if you define your function differently (with 64 discrete inputs instead of one). For example take a knight position PST:Pradu wrote:PSTs would be nonlinear because PST[sq1+sq2] != PST[sq1] + PST[sq2]
PSTeval(ispieceonsq1 , ispieceonsq2, ispieceonsq3... ispieceonsq64)
where ispieceonsq has values of
0  no piece
1  my piece
1  opponent piece
and you can define the function as
PSTeval(x0,x1,x2...) = PST[0]*x0 + PST[1]*x1 + PST[2]*x2
ignoring everything except square 1:
PSTeval(0+1) = PSTeval(0)+PSTeval(1) OK
PSTeval(0+0) = PSTeval(0) + PSTeval(0) OK
PSTeval(1+0) = PSTeval(1) + PSTeval(0) OK
PSTeval(1+1) = PSTeval(1) + PSTeval(1) OK (but will never occur on a real chessboard)
For non symmetric pawn PSTs you could take in 128 values (64 for each side) instead of 64 and still define the PST function the same way and be good to go.
Re: Linear vs. Nonlinear Evalulation
Is there any advantage to having a linear vs nonlinear evaluation function? Would it make analyzing an evaluation function significantly easier if it was linear?Gerd Isenberg wrote:I have a question about the definition of linear versus nonlinear evaluation.

 Posts: 1808
 Joined: Wed Mar 08, 2006 8:19 pm
 Location: Oslo, Norway
Re: Linear vs. Nonlinear Evalulation
Not quite. The above is the definition of an additive function. However, you proceed to give the correct definition:I guess the usual definition of a linear function is one where the output of a sum of the inputs is equal to the the output of each individual input.
The first of these equations says that the function is additive, and the second that it is homogeneous of degree 1. Together, they say that the function is linear.A function f is linear iff:
f(a+b) = f(a) + f(b).
f(c*a) = c*f(a)
At least to me, it is fairly obvious that every additive real number function is linear. Nevertheless, it is wrong, if you accept the axiom of choice. The proof is simple and beautiful:
Regard R (the set of real numbers) as a vector space over Q (the rational numbers). Pick two nonzero real numbers, one rational and one irrational. The numbers 1 and pi will do, and I'll use those for the rest of the discussion. Because 1 and pi are linearly independent over Q, we can construct a basis B for R over Q with 1 and pi as two of the basis elements (this is where we need the axiom of choice; the axiom of choice is equivalent to the existence of a basis for all vectorspaces).
Now construct a Qlinear map f: R > R by f(1) = 0, and f(b) = 1 for all other basis vectors b. Because f is Qlinear, it is additive. However, it is not Rlinear: We see that get f(pi) = 1, but pi * f(1) = 0.
Like all proofs using the axiom of choice, this proof is nonconstructive: It doesn't help us find a particular real number function which is additive but nonlinear. Indeed, I am fairly sure that noone will ever find such a function. This is a good example of why the axiom of choice is somewhat controversial: While the AC by itself looks intuitive and obvious, it can be used to give nonconstructive proofs for a lot of very counterintuitive results.
Of course, in computer chess, most functions are not real number functions, but integer functions (modulo 2^32 or 2^64), and for such functions additivity and linearity are of course the same thing.
You can't define what it means that en evaluation function is linear without first defining what a "feature" means. For a program using a material + piece square table eval, it would be most natural to let the features be the set of all (piece, square) pairs on the board. Write this set as {(p_1, s_1), ..., (p_n, s_n)}. Then the evaluation function would look like this:So I'd guess an evaluation function is linear if
f(feature1_a + feature1_b,feature2_a + feature2_b,feature3_a + feature3_a...) = f(feature1_a,feature2_a,feature3_a) + f(feature1_b,feature2_b,feature3_b) = f(feature1_a)+ f(feature2_a) + f(feature3_a)+f(feature1_b)+f(feature2_b)+f(feature3_b) ...
PSTs would be nonlinear because PST[sq1+sq2] != PST[sq1] + PST[sq2]
Simple material eval and mobility eval could be linear:
materialEval(onepawn + onepawn) = materialEval(onepawn) + materialEval(onepawn)
Code: Select all
eval = MaterialValue[p_1] + ... + MaterialValue[p_n] + PST[p_1][s_1] + ... + PST[p_n][s_n]
In other words, all evaluation functions can be regarded as linear, or as nonlinear. It always depends on how you define the features. For the complex evaluation functions found in strong chess programs, I don't think it makes much sense to talk about linearity of the evaluation function as a whole, but discussing the linearity of some of the components of the evaluation function could still be interesting.
 hgm
 Posts: 23718
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: Linear vs. Nonlinear Evalulation
The point is that you can make anything linear that way. Just put al nonlinearity in the Feature, and set al the weights to 100% (and make them userconfigurable as UCI option. )Gerd Isenberg wrote: Yes, one can interpret piece square table as weight vector, which are multiplied with a vector of boolean (absence or existence) features. Thus a "linear" combination or dotproduct, even if the features are only zero or one.The terms linear versus nonlinear evalulation were mentioned in several papers, but I wonder what their definition is. May be its arbitrary or outdated.Code: Select all
for all i sum += Feature[i] * weight[i];
Suppose I have a term that is proportional to the square of the number of Grasshoppers in my evaluation function. I can define a Feature that is 1 if there are exactly i Grasshopers on the board, and 0 otherwise. And then I set weight to i*i. And, magical trick, a purely quadratic function has suddenly become linear...
So the statement that something is linear always has to be accompanied by the information "as a function of what?" to acquire meaning. That something is a linear function of the weights is not all that significant. (In fact it is merely the definition of "weights".) Nonlinear as a function of piece position (e.g. passer advance) through a PST is something quite different from nonlinear in piece values (e.g. through material tables).
In itself the claim a program uses "nonlinear evaluation" is at par with detergent manufacturers claiming their product "launders whiter".

 Posts: 2127
 Joined: Wed Mar 08, 2006 7:47 pm
 Location: Hattingen, Germany
Re: Linear vs. Nonlinear Evalulation
I am only interested in the definition, related for instance to Levy's statement about:Pradu wrote:Is there any advantage to having a linear vs nonlinear evaluation function? Would it make analyzing an evaluation function significantly easier if it was linear?Gerd Isenberg wrote:I have a question about the definition of linear versus nonlinear evaluation.
Good, I.J. (1968). A FiveYear Plan for Automatic Chess Machine Intelligence II pp. 110115
David Levy (1988). Computer Chess Compendium, 3 Position Evaluation pp. 112:
I wonder whether the "future" already began more than 20 years afterPerhaps nonlinear evaluation functions will become popular at some future date, in which case some of Good's ideas will come into their own.