 |
|
MAP Links Contact Us Books Glossary ECO Search Tools FAQ News
HOME CLUBS BANNERS 
BLOG VIRTUAL MUSEUM ARTICLES CAISSA FORUM
 | |||
 |
|
|
|
|
3o) The Evaluation Function
In chess, the evaluation function is approximate, it only translates heuristic principles - there is no canonical method to compute the evaluation. A single numerical value is used to summarize many rules. It is a way of explaining strategy principles to the machine. In searching to optimize the value of the position the computer acts as if he could understand the rules of strategy. Of course those principles do not enable combination recognition: it is the minimax algorithm that enables machines to find combinations. Basically, the evaluation function counts the material (on each side) by summing the pieces weighted by the values for each kind of piece: for example, the Queen equals 9 pawns. Sometimes the function gives the King a very high value signifying that checkmate is the most important factor. We can refine this evaluation by adding to the assessment other values that translate certain positional considerations. It is important to distinguish positions with equal material, and sometimes positional aspects can prevail over material aspects. Refining the evaluation function is one of the fundamental ways to improve the performance of chess computers. One aspect easy to compute is mobility: it suffices to count the number of legal moves generated by the move generator. This is not exactly what we call mobility in chess because it counts all possible moves, even those that are useless or even bad! - but it gives a rough approximation. We can quantify other positional aspects such as the protection of the King, domination of the centre and pawn structure etc. We can refine the evaluation by adding or subtracting points depending on whether certain rules are satisfied or not by using conditional propositions such as: "if the King is in check then subtract x points". It is advisable to have 3 different evaluation functions - for the opening, the middle game and the endgame - because strategic rules are different in each phase. For example, in the opening the function subtracts points if the Queen has moved, or if the pawn f2/f7 has moved before kingside castling. In the middle game the function subtracts points if the King hasn't castled, or if Knights or Bishops haven't yet moved. In the endgame the function subtracts points for backward, isolated and doubled pawns.
4o) The Horizon Effect
To remedy the horizon effect we must make depth vary as a function of the type of position. We have only a certain amount of analysis time available and we have to share it out in the most useful manner between all positions to be analysed. We can noticeably improve the research with a given depth ‘d’ if we make an algorithm with a variable depth that is only an average ‘d’. If a move seems bad (for example in the case of loss of material) then it is probable that this move is in fact bad and it is useless to privilege it in the analysis, whereas, if the move seems interesting it is useful to continue to decide if it actually is so, so as not to unwisely play it. To recognise a bad move we can use the ‘nil move’ heuristic: if immediately after having moved we move a second time as if it was again our turn to play, and if this second move is not advantageous then the first move can be considered as bad. For defining an average depth equal to ‘d’, the algorithm Search Extension associates to each branch the value 10 times ‘d’ and decreases it at each dropping of a level in the tree by a small quantity if the move is interesting. So interesting moves benefit from a greater depth of analysis. The research in depth stops in each branch when this value is nil (or negative). As well as looking at bad or ‘good’ or interesting moves, the horizon effect concerns unstable positions, i.e. those where there is capture, check or promotion. For example, let us consider the case where we run the algorithm min-max with a depth = 1. The program will choose a move that captures an opposite piece, for example the Queen takes a protected Knight, because the response of the adversary is beyond his horizon. If we run it with a greater depth this problem will still occur at the frontier of the horizon: it will see in this place a capture whereas it can be balanced or even largely balanced. It will see an illusory threat in what is a commonplace exchange because it will see only one half of this exchange and this will impact on the calculation even if it occurs in the depths of the calculations of the variations. For example, if at the end of a variation it sees that it can take the opposite Queen with its own Queen but doesn't see that its Queen will be recaptured on the following move it will believe to have found a combination and this variant will be overestimated erroneously. This problem is specific to captures: if the depth is odd the algorithm doesn't take into account the riposte of the adversary and overvalues some moves, whereas if the depth is even it doesn't see its own riposte to moves of the adversary and therefore overvalues some moves by the opponent. The problem is that we *must* stop at a determined depth (even or odd). A rather more subtle obstacle occurs when the computer is in the midst of a forced threat (such as the loss of his Queen). The horizon effect will give him the illusion of an answer: all sacrificial moves that enable delaying the danger will give him the illusion of avoiding it because it will push it back and locate it beyond his horizon, although those sacrifices are not valid replies and only serve to worsen uselessly the material balance. Although if at such a situation the alpha-beta algorithm is extended, the program computes the global balance and doesn't play those delay-action moves. Hence the solution is to recognise this kind of position in order to invest more analysis time on it. The solution then is to continue the basic search by a search for stability. For this we create a second evaluation function like the one which evaluates the position, but this one evaluates the kind of position. This second evaluation provides the degree of confidence the program may have in the evaluation of the position. So the computer continues the analysis in the cases where the position hasn’t a reliable evaluation to reach positions where the evaluation is reliable, and which enable modification of the evaluation of the position concerned. Stable positions have a reliable evaluation, and we don't need to continue the analysis on them further, whereas unstable positions must be analysed in depth until reaching stable positions that enable changing the evaluation of our position in a reliable manner.
************
|
|||||
|
[This page was conceived by Antoine Bruneau - John E Hawkes has contributed to the English presentation of this article - All data is copyrighted by: © Antoine Bruneau & Chess-Theory] ************ If you like music, you may choose now a fine background Music:
*** FOR PLEASANT SURFING AROUND THIS SITE:
*** FOR DISCOVERING WHO WE ARE:
******** ©-«Chess-Theory.com»-2004-2008 ******** |
 |
Choose now a fine background Music!...
«CRYSTAL PHOENIX GALLERY- 
