Author: David Eppstein
Date: 12:49:00 07/13/99
Readers of this group may be interested in my paper "Setting parameters by example", which can be found at http://xxx.lanl.gov/abs/cs.DS/9907001 The paper is mostly about some combinatorial optimization problems like shortest paths and minimum spanning trees, but there's a section towards the end describing possible applications of the same methods to tune chess evaluation function weights. First, a big warning: this has not been tried experimentally, it's all just speculation. Basically, the idea is to apply the ellipsoid method from linear programming to find a set of weights such that a shallow search using those weights plays correctly on each problem from a test suite. Each time the ellipsoid method wants to test a set of weights, you use those weights to run the test suite. If one of the test suite positions is played wrong, you can search that one position more carefully to find two positions A and B such that A should be evaluated better than B but actually is evaluated worse and this misevaluation is causing the position to be misplayed. Then you add a constraint to your linear program saying that the evaluation of A should be greater than the evaluation for B, and go on to the next ellipsoid iteration. Read the paper for (a few more) details. Yes, I know test suites are not very representative of actual play (especially the tactical ones that are the most commonly available). So one of the ways this could go wrong would be that it finds evaluation weights that work for the test suite but are bad for actual play. Another way it could go wrong would be that it finds that there is no assignment of weights that correctly plays all test suite positions; but this might be useful too, either in finding bad positions in the test suite or in helping understand what important terms might be missing in your evaluation. Apparently, for some other games, there is much more sophisticated use of automatic methods for incorporating game knowledge (e.g. the big libraries of edge patterns used in good Othello programs) and I am interested in to what extent this is possible for chess. The advantage of test suites is that they are annotated with correct moves, and (should be) filtered for cooks, but it would be even better if there were some way to learn more than just opening lines from the big collections of thousands of high-quality pgn games. By the way, I'd recommend http://xxx.lanl.gov/ for anyone seeking a good way of making electronic copies of computer science papers. It's very reliable, it's easier to find papers there than on thousands of individual or departmental web sites, it sends out announcements of new papers to a wide mailing list, and it provides convenient format-conversion services (e.g. pdf as well as postscript, which is great for me since the postscript viewers on the mac all suck rocks). Bob Hyatt, you mentioned (on the crafty list) making a recent paper on book learning available on your ftp site -- maybe you could put it on xxx instead, that way people not on the crafty list might notice it too.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.