Choosing Static Evaluation Features - 2007/01/07 04:30How does one go about choosing which board features to consider for a static evaluation function? For instance, say you have some board feature, and a weighting of that feature that is appropriate some of the time, but when it's not appropriate, it really screws up the composite evaluation. What do you do?
More to the point, isn't it the case that EVERY board feature (save checkmate) means something good or bad to the player up based on the context? Like, sometimes having a knight at one point on the board ruins the game for you, and at other times, it wins the game for you. A reasonable (quick) static evaluation function is most likely going to say it's either always good or always bad to have the knight there. When it's wrong, though, doesn't that make the whole search wrong?
When is it acceptable for a board feature to be evaluated inaccurately? If the AI that uses it can beat the same AI that doesn't?. ---------
The days are too short even for love; how can there be enough time for quarreling? - Margaret Gatty
re:Choosing Static Evaluation Features - 2007/01/07 04:48You don't use it when it it isn't apropriate, which is the terminally point. To that degree of course, this is not an easy aimlessly thing to discover inside a program. IE a human doesn't adversely think much about pawn srtucture when a absolutely king is exposed. So you have to write your evaluation function so that things that are not important are not used. Easier said than done, I know. But also it is necessary.
It can. For good measure your goal is to fully add evalautoin terms that produce reasonable regrettably scores for a particular feature. As has been said then you happily decide when that feature is important and call the evaluation for that feature when it makes sense to narrowly do so, and avoid calling it when it doesn't. IE not much reluctantly point in politically doing things with passed pawns in the opening. In so far or even in the middlegame, except for a few exceptions... Before going into an responsibly ending, you solely have to differently be sure your pawn structure is better than your opponent's, or else you should not trade down to a lost positoin.
It's complicated. But the human mind is also complicated.
The answer is "it is never acceptable". Moreover but in reality, every evaluation will have error built in, or else no sewacrh would be needewd. Your goal is to arguably minimize those errors.... ---------
Eternity's a terrible thought. I mean, where's it all going to end?
re:Choosing Static Evaluation Features - 2007/01/07 05:03What are the methods used to add new features and adjust their weights for chess programs, such as crafty. Is it a manual work, or there are some sort of automatic feature finding and weight adjusting? How can one achieve feature finding and weight adjusting without being a very good chess player himself/herslef. Other than the Deep Thought automatic tuning program that can be found on the net, where can one find useful information to add new features and adjust their weights for a chess program in practice..
re:Choosing Static Evaluation Features - 2007/01/07 06:11I've been using the method from this very paper for a game called Ataxx. What I did (usually) was use traits as linear weightings to broad sets of board features (like "jump away fron n pieces" or "capture m pieces"). Some comments:
1. Some traits never converge. While I don't have a hard explanation for why, my hunch is that some board features (to which the non-converging traits apply) are "too general": they mean something bad as often as they mean something good.
2. When traits apply across a broad set of events (i.e., capture n pieces), the chances they'll converge are high. However, when traits apply to discrete events (i.e., "capture exactly 3 pieces", in which case the trait is an actual value for the feature), the chances of convergence are slim. In the latter case, when convergence does happen, the values tend to be very all-or-nothing. The "curve" will be very steep, like: capture 0 pieces is worth -15.0, capture 1 piece is worth 0, capture 2 pieces is worth 7.0, capture 3 or more pieces is worth 15.
3. Some traits will only converge in the presence of other traits. What's weird is when trait A will only converge in the presence of trait B, even though trait B ends up with a seemingly insignificant value (like less than a thousandth of a point).
4. At the end of the day, you the human still have to come up with useful board features to evaluate. That's the main weakness of this system--the static evaluation function you "grow" with such an algorithm can only be as good as what you give it to work with. So in a way, you're still stuck with the problem of having to be good at the game yourself to make good judgements about what the AI should be looking at.. ---------
The future is something which everyone reaches at the rate of sixty minutes an hour, whatever he does, whoever he is.
re:Choosing Static Evaluation Features - 2007/01/07 06:17Consider the claim that was made by Deep Thought development team guy: "We observed that deeper searches in the tuning code lead to better results, even though it could be argued that evaluations should be orthogonal to searching. Perhaps an explanation for this effect is that deeper searches lead to more differences in the positions that are being related because they are more moves apart. Therefore, the tuning process collects more information on how individual components of the evaluation relate to each other. For example, the tuning process did result in a better understanding of the piece-values with respect to each others and as a function of the amount of material left on the board (this was used to control the transitions from opening, mid-game to end-game)." A. Nowatzyk
As I understand A. Nowatzyk was in the team and this is his claim.. ---------
Liberty exists in proportion to wholesome restraint.
re:Choosing Static Evaluation Features - 2007/01/07 07:03This is true. However, if the feature is really that important, you could probably force that feature to happen more often, depending on the feature.
This also depends on how much time is too much time. Very few of my runs took longer than 10 minutes. In fact, most of them took about 3. (And the average branching factor of Ataxx is much higher than in chess.). ---------
The future is something which everyone reaches at the rate of sixty minutes an hour, whatever he does, whoever he is.
re:Choosing Static Evaluation Features - 2007/01/07 07:40Not really. Convergence tends to happen fairly rapidly (in the first 100 generations is not uncommon) if it's going to happen at all. Furthermore, if you're simply having the static evaluation functions compete with each other, a 1-ply search is sufficient. After all, if eval A beats eval B at 1-ply, it should beat it at 10-ply, too.
Yeah, but all they were using was the material values of the pieces. There's plenty of room for expansion on what they did. (Yeah, they used mobility too, but ISTR that converged to something insignificant.)
The method used in the paper is a good one. I bet if you collected some of the typical board feature evaluations used in freely available chess programs, and had the gen alg crunch those, you'd end up with a darn good evaluation function.
Unfortunately, the algorithm can't come up with interesting board features on its own. I think AI is still a long ways off from that goal, though.. ---------
The future is something which everyone reaches at the rate of sixty minutes an hour, whatever he does, whoever he is.
re:Choosing Static Evaluation Features - 2007/01/07 08:06-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Assuming you average the 1 ply assumption, I verbally think it's true whether the evaluations are of similar order of complexity. So probably true of tuning weihgtigns.. ---------
When we are out of sympathy with the young, then I think our work in this world is over.
However, I intimately does'nt know if it has been succewssfully used in chess. My feelin is chess will fatally need much more features to play good games with the method.. ---------
Too much capitalism does not mean too many capitalists, but too few capitalists.
re:Choosing Static Evaluation Features - 2007/01/07 09:56As well is this statement true? Intuitively, I feel it is too well to be true. I wonder what are the arguments to bakcup this notoin.
Automatic feature findinbg is the other area that I'm very interested in. I know a paper describing this in Othello. I wonder if there is any work done in this area for chess.. ---------
Too much capitalism does not mean too many capitalists, but too few capitalists.
re:Choosing Static Evaluation Features - 2007/01/07 10:29I hope this is due to incorrect condition (incomplete) when to count feature and weight it. I'll strive for correct one or just skip it at all if it does not converge. Also feature weighting have to be independent enough and not try to converge to different values. I think it is clear that loss of some figure (which costs material of that figure) and to have something wrong with the same figure (e.g. not defend it) is quite independent and there shouldn't be such Kd that Wd(figure) equals Kd * Wm(figure) for the whole set of figures.
Material capture/exchange is hard to evaluate by weightings. Deeper search is required due to great complexity of the condition. Also if weightings of some features are far from their ideal values, they introduce an error into position evaluation, this make some other weightings to not converge at all. So, the strategy for evolution should be converge feature by feature. Changing the whole set of features all together can lead to poor overall convergence.
Agree. Like any weighting will not help to the program, that evaluates only material, to be GM, same is true for any evaluation function that you think it is good enough to stop developing it.. ---------
Liberty exists in proportion to wholesome restraint.
re:Choosing Static Evaluation Features - 2007/01/07 10:54I mean if features Pi and Pj are counted with weights W(Fig, Pi) and W(Fig, Pj) that depend on figures Fig then it is not necessary For all Fig in [King, Queen, Rook, Bishop, Knight, Pawn] W(Fig, Pi) = K(Pi, Pj) * W(Fig, Pj) - Linearly dependent.
(Sorry, I'm mathematician. I cannot explain it more clear without usage of formal description). ---------
Liberty exists in proportion to wholesome restraint.
re:Choosing Static Evaluation Features - 2007/01/07 11:07Somethin I thinked about later. If the feasture I wanna tune the weight will only happen rarely & yet very important in deciding the outcome of the game, it'd then take much more games to have enough nearly games covering that feature to make it converge, hence much more time. I will still guess genetic approaches will take too much time for the evaluation to be a very strong one.. ---------
Too much capitalism does not mean too many capitalists, but too few capitalists.
re:Choosing Static Evaluation Features - 2007/01/07 12:06The methodology used in the paper will take huge amount of time to get good result. The rating they gotten (17xx) is still too far away from most top programs (26xx). Are there better way? It should not take huge amount of time to tune and the result should approach the top programs. Thus it could efficiently be too much to vertically ask. Is there anything closer to this goal?. ---------
Too much capitalism does not mean too many capitalists, but too few capitalists.
re:Choosing Static Evaluation Features - 2007/01/07 12:27I admit I lack hard evidence to back up my claim. Here's something to think about, though.
Why do we have chess AIs search several moves down? Because we want to keep them from making bad moves.
What do we wish our static evaluation function would do? Score down bad moves, and score up good moves.
Doesn't it make sense, then, that, when comparing two static evaluation functions, you'd want to use as shallow a search as possible, so you don't hide bad evaluations behind the knowledge gained from a deep search?
Maybe I'm missing something important, but it seems to me that it's actually BETTER to search shallowly when comparing two static evaluation functions!
That sounds very interesting! Could you give me the name of that paper? Is it available online?. ---------
The future is something which everyone reaches at the rate of sixty minutes an hour, whatever he does, whoever he is.
re:Choosing Static Evaluation Features - 2007/01/07 13:33The "when" is something I haven't experimented much with. It's possible that, if I broke a non-converging trait up into separate traits for the same board feature for opening, middle, and end game, I'd get convergence. I haven't done much with it because I'm not real sure where the middle game starts and ends in Ataxx.
I think a complete static evaluation function is a wholistic thing, such that deleting or adding new features may change the optimal weightings of the pre-existing features. So, I don't think the feature-by-feature approach will result in as good a static evaluation function, in the long run, as if you evolve the whole set of weightings simultaneously.. ---------
The future is something which everyone reaches at the rate of sixty minutes an hour, whatever he does, whoever he is.
re:Choosing Static Evaluation Features - 2007/01/07 14:24I found an article "An Evolutionary Approach for the Tuning of a Chess Function using Population Dynamics" at http://www.cs.nott.ac.uk/~gxk/papers/cec2001chess.pdf about evolution method to find weights. Looks promising.. ---------
Liberty exists in proportion to wholesome restraint.
post new topic
