evaluation idea

[Uri Blass]

I wonder if somebody tried the following idea to build a slow searcher with expensive evaluation function when the idea is to use also the fast evaluation function to calculate the slow function:

The idea is the following

1)use your chess program to search 1,000,000 different positions so you have a database of position and evaluation based on searching to relatively big depth.

You may have something like
s(p(i))=result of search of position p(i) to depth 20 when 1<=i<=1000,000.


2)For every position that you search in the tree calculate distance to everyone of the 1,000,000 positions with the same material configuration that is the number of pieces that have different squares(hopefully in most cases clearly less than 1,000,000 positions but more than 1 position).

3)take the positions with the smallest distance to the position in the tree(denote this distance by d) and calculate the average of the evaluation of positions with distance d to the relevant position.
denote the average by a
use all the results to calculate a new evaluation

for example you may have something like

slow_eval=fast_eval*(d/d+1)+a/(d+1)

It means if the distance is 0 you use a that is the evaluation after search to depth 20 and if the distance is bigger than 0 you use some average between a and the fast eval with bigger weight for a in case that the position is closer to the position in the database.

I do not think that it is the best formula and it may be better to use the following factors in the formula:

1)differece between slow_eval and fast_eval for similiar positions because it is logical to assume that the difference of a new position is going to be in the same direction
2)number of different positions with the minimal distance(with big number of positions with small distance the evaluation should be closer to the new evaluation.

based on 1 I can think of formula like
slow_eval=fast_eval+avg_diff/(d+1) but it does not consider the fact that more positions with distance d is better.

something like
slow_eval=fast_eval+avg_diff/(d+(1/n)) when n is the number of different positions with the minimal distance d sounds better
when d+(1/n)=1 only in one case when d=0 and as a result n=1 because there is only one position with distance 0

[ZirconiumX]

I wonder if somebody tried the following idea to build a slow searcher with expensive evaluation function when the idea is to use also the fast evaluation function to calculate the slow function:

Lazy eval is not uncommon in engines - Rebel and the CPW-Engine use it, to name a few.

Matthew:out

[AlvaroBegue]

I think this idea would only be interesting if we could figure out a good distance between positions. What exactly do you propose to use as distance?

[Uri Blass]

I think this idea would only be interesting if we could figure out a good distance between positions. What exactly do you propose to use as distance?

The simplest option is simply the number of pieces or pawns that are on different squares but I understand that it is not optimal and there are probably better distance functions.

It may be possible to consider the distance in number of moves or the distance in static evaluation after having the same material configuration(and bishop on light square can be considered as a different piece relative to bishop on dark square for material configuration).

I also think that having a passed pawn or not having a passed pawn can be considered as a big difference even if you change only the square of a single pawn(and same for isolated pawn or difference between pawn in a2 and pawn in a7).

Generally the distance should be some integer that is 0 when we have the same position and bigger in other cases.

[crybotmark]

I think this idea would only be interesting if we could figure out a good distance between positions. What exactly do you propose to use as distance?

Assuming an human could compute a distance between two positions, this could be achieved using machine learning. I think this would be better than introducing some very aproximate chess knowledge into a function.

[AlvaroBegue]

Actually, you can probably use unsupervised learning to define a distance between two positions. I followed an online course by Geoffrey Hinton where he described some mechanisms to do this.

One such mechanism would be a deep belief network. You start with a description of the position on the board (perhaps as a long list of booleans indicating "square <X> has piece <Y>"), then use a restricted Boltzmann machine to identify features in the input, then use those features as inputs to another restricted Boltzmann machine, an so on for several levels. On the top level you have just a handful of features (say, 50). Now you define the distance between two boards as the square of the distance between the activation levels of those top-level features. A similar technique was used for document classification and it seemed to be very powerful.

Actually, you could also do the same thing and use a linear combination of the top-level features as an evaluation function, and perhaps use back-propagation to fine tune all the weights in the machine as a last step of learning. Professor Hinton described several successful projects that used that kind of technique.

I would be really curious to see what that would produce. Maybe when my kids get older...

[Before people jump at my neck for this: Of course, using a complicated neural network like this would be slow and impractical for an engine, but producing a decent evaluation function without explicitly feeding in any knowledge of the game is still an interesting intellectual challenge.]