Author: Ratko V Tomic
Date: 09:15:44 10/28/99
Go up one level in this thread
Thanks for the thoughtful response. The chess programmers here will find lots of useful advice in it. > >And finally it is the job of the search heuristics to not stop the search >in the positions where the evaluation is not reliable. The truncated tree evaluation is inherently inexact. No quiescence search (short of reaching the table-base depth) can reduce all leaf positions to the same base level where the evaluation terms are equally valid or mean the same thing. Even the material score, normally the most stable and reliable part of the evaluation, is merely a hypothesis about the expected piece usefulness over some average future game. Every concrete game is as different from such hypothetical average game as the every salary in a country is different from the average salary for that country. It is clear for example that not all pawns, in any stage of the game (not just the endgame) are worth 1 point each, i.e. that they will be equally useful over any concrete game. As argued in more detail in another thread (on positional evaluation), assigning plus or minus points to various positional concepts (derived from human chess strategy) and adding these points in a lump sum at the leaf nodes of a truncated tree (the Shannon dogma) is fundamentally wrong headed and highly suboptimal way to use such knowledge. That it is so one just needs to look how many more orders of magnitude more efficiently human player utilizes such knowledge in reducing the amount of search (nodes examined/evaluated) compared to the present chess programs. Namely, there is a great deal more lawfullness or pattern or regularity in chess than what the rules of game contain explicitly (and what is the backbone of the alpha-beta searchers). The chess strategy knowledge captures these laws not as plus or minus evaluation points to be lumped in a sum, but as the reasoning and search guidelines and constraints i.e. the actual full laws (or the pattern) which are the underlying source of the huge economy in search that human player achieves are contained in the _combined_: strategy principles _plus_ the intended manner of their use (forms of reasoning, common sense, specific types of followup checks for specific type of advice, etc). The Shannon's "lump sum" dogma entirely misses the point of such strategy knowledge (I suppose at the time he came up with it, it was a big enough deal, given the technology of that era, to get a program to fit in a few hundreds bytes and to play full and legal game at all, much less to try to make it reason based on strategic principles; today there is no such excuse, though). >Hard to say. From my own experience, I indeed see that you can lose a lot of >information (have a big source of error) with a bad selective algorithm. > >Many times, I noticed that I was desperately trying to improve my evaluation to >solve a given problem, and eventually found that the evaluation knew about the >problem, but the search had simply lost this information. > That and the rest of your comments on the information loss a quite useful observations. I would only note that unlike the inherent (to Shannon dogma) inexactness I was talking about, this one can be remedied by retaining (or even generating) lots more info from the the search than conventionally done (such as killer moves, history and hash tables). I suspect that lots of commercial programs which use proprietary (non-public) algorithms do actually retain and sample much more data which are byproducts of the search & evaluations than what is publicly acknowledged (especially the strong positional programs, such as Rebel and Hiarcs). Type of things which immediately come to mind in this regard would be sampling of the square importance or value (based on the statistics of its role in the search), piece value or potential usefulness or functional overload or underuse (e.g. if a piece can be removed without causing worsening of your position, beyond its nominal material value, such piece is underused etc), detection of cooperating clusters of pieces (as a generalization of the bishop pair extra value), etc. >If I was you, I would not work on this problem. You are going to destroy the >"nerves of steel" behaviour of chess programs, that is so impressive in some >highly tactical situations. :) Yes, that is impressive, and the "nerves of steel" is well put. But that also may cost the program some rating points. For end user it is more fun to play if the program does have the "nerves of steel," however misguided this kind of sure-footedness may turn out on occasion. But for the comp-comp autoplay it would probably be more useful if it is turned off. My private little project, though, isn't a conventional chess program, so the issue of error inherent to Shannon approach to evaluation isn't a problem. I am studying and exploring (in my spare time) something similar to Botvinik's Pioneer scheme. Although I came up with such concept independently, after discovering Botvinik's work I am constantly finding that practically whatever good idea I come up with in this context, Botvinik has thought it through in much greater depth and variety decades ago. When that approach is implemented (be it in my program or someone elses) as a full playing program, I think it will be almost as superior to the human play (and to the play of the current programs) as the computer doing arithmetic is to the paper and pencil arithmetic. The issue of allowing this type of program to play in human events will become as moot and ridiculous one as would be an issue of whether cars should be allowed to compete in a human marathon race. (I said "almost" since the higher level lawfullness of chess (which this approach aims to utilize in full), the known and the unknown laws, isn't quite as great as the lawfullness of the arithmetic.) >But this way of evaluating positions with a score and an error margin on the >score has been studied by Berliner in his program Hitech. I don't remember the >name of the algorithm (wasn't it B*?), but it was indeed doing this kind of >things. An interesting approach, but it was not successful. Which doesn't mean >it has no merits, maybe the implementation was simply not optimal. > It was a Berliner's group algorithm (the B* and its offspring). There is a book (based on a PhD thesis from the Berliner's school) "Searching with Probabilities" by Andrew Palay (1985 Pitman Pub. Inc., ISBN 0-273-08664-2) which covers that approach. Whether that was the best one can get out of the approach, I don't know (it is doubtful, though), but the book is a mind-opener and an excellent base for a critical re-examination and ultimately undermining of the foundations of the Shannon approach (i.e. the basis of the current chess programming). The style may be a be a bit overly dry and scholarly (especially for the modern tastes and the presentday attention spans).
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.