Author: Ratko V Tomic
Date: 11:17:04 10/27/99
Go up one level in this thread
>>The problem with minimaxing (via alpha-beta, or in any other way) of inexact >>values is that due to the error propagation up the tree, the evaluation error >>increases with depth. Of course, in chess (checkers and similar strategy >>games),there are other beneficial effects of minimaxing unrelated to >>the positional evaluation (such as detection of material loss, traps >>which cause early termination), which for most root moves offset the >>drawbacks of the largerpositional error. > >Are you not relying on the independence of leaf node evaluations to show that >the evaluation error increases? This assumption is false in practice. > The simple game models used to obtain _analytically_ in closed form the error increase with depth do indeed use independence of node values (one of such results is that for the case of small errors in evaluation function, the increase of errors is exponential with depth). Similarly, other simple models were used to show analytically no increase of error with depth, but these too had highly artificial kind of dependencies which again didn't apply to the more complicated realistic games. For chess and other more complicated (for analytical treatment) games one has to use empirical measurements. One possible indicator of error propagation effects is flattening of strength vs depth curve. In simpler games where large depth (20+ plies of full width) is routinely achieved such flattening has been observed unambiguously. In chess, where the (full width) depths are still relatively small there is still some controversy whether various indicators mean this flattening or not. Of course, this also depends on the positions looked at. In positions which have a clear cut material gain or checkmate within horizon, there is no error increase with depth. The problematic positions are those where no such clear cut gain exists (within horizon), and several candidate moves fall within the noise band of the evaluation functions. The standard starting position for chess is a good example of such position, and indeed programs don't perform well if left without the book (or even with a book, but not the "right" kind of a book). Since that position is the most analyzed single position in chess theory, it is much easier to notice the basic flaws of program's play when purposefully left without a book, be it from start or mid-way through some openings. To most human players (who know given opening) observing such experiment it is clear that program has no clue why certain opening moves are played (e.g. what kind of followup plan they assume). I have seen Fritz or Hiarcs trade off their fianchetto bishop for a centralized opponent's bishop, when taken out of a book with some early a2-a3 type move. Another clear indicator of empirical nature that there is an error increase (of positional evaluation) with depth are experiments of playing the same program at N and N+1 ply depths. If the deeper application of the "lump sum" positional evaluation function is always either better or at worst equal to the shallower application, then (since the N+1 ply program will never be tactically surprised by the N-ply program), the N-ply program should never win. But it does win, around 20% of time. (And it probably gets positional advantage even in greater prportion, but loses later on a tactical shot.) That is a good indicator that at least in some quite non-negligable proportion of positions the increased depth has worsened positional evaluation. >>> All of that multi-level stuff can be done in one function. One. >> >>In principle, yes. In the similar way, you don't need even that single >> function -- a single lookup in the appropriate table base will give >> you the best move. >>Again, in principle. In practice (with limited computing resources) it isn't >>so in either case. > >A single lookup in an approriate table is an implementation of an evaluation >function, but I digress. > Well, yes, in a trivial and entirely fruitless sense. But that's not the kind of evaluation "function" we were talking about, i.e. the function which is a "lump sum" of positional bonus/penalty points (derived from human chess theory) applied at the leaf nodes. The type of positional "values" such individual terms represent are not used well in such manner. They do help the program, even when used in such crude way, but that is the kind of "help" that, to use an analogy, a short kid who is trying to learn programming in C++ would get from taking the pile of C++ books and putting them on the chair to sit on, so he can reach the keyboard easer. The kid is right, too, when he claims that the books do help. But that doesn't mean there isn't a more suitable way to use those books, the way they were intended to be used. The same goes for the multitude of positional terms adapted from human chess theory to chess programs -- those rules and advice are meant to be used in conjunction with reasoning and common sense, not to be converted to plus or minus points to be amorphously added all together. Yes, they're useful this way, too, but so are the books to sit on top of, to the short boy. >I suggest there are many more positions where the human would do worse than >simply to let the machine grind. The difference is that a human operator has a >good understanding of certain positions, and will know when they can step in to >make a difference. > >If I selected 100 positions from GM play, and gave a 1800 player Crafty for a >day for each position, and had Crafty analyze each position for the same length >of time on its own, I do not believe that the 1800 would come up with superior >analysis most of the time. I believe that after this 3-month experiment we >would find that Crafty alone would consistently chose more reliable PVs, >even if they were not so understandable to 1800s. Of course, I am >discounting the possibility that the 1800 will elect to leave their >Crafty alone to ponder. ;-) > I have no doubt that there exist at least 100 chess positions where a program alone would do better than a program + an 1800 player. Any highly non-intuitive long combination which takes a full day for a program to find will do. But if there are well known indicators for existence of a combination, human player will be able to guide the program through it much quicker. And if there is no such long anti-intuitive combination, the combined player will be superior. If there may be someone here who has done and quantified such experiments, it would be nice to hear about it. >The method you propose is reducible to alpha-beta with a single function, so >what is left to address? There is no theoretical advantage to doing it a la >Botwinnik. Currently, there is a severe practical disadvantage, which doesn't >help the cause. > The main disadvantage (at present) is the complexity of trying to program the "reasoning" and "common sense" which underlies the use of positional evaluations from the human chess theory. Going back to the short kid and C++ books analogy, your argument against using the C++ books the way they were meant to be used is that boy doesn't have good enough reading skills, it's better to use them as booster chair. It works. >> >>The same goes for direct full chess-tree table-base lookup. In principle yes, >>but without practical relevance. The actual positional evaluation terms >>as used in the chess programs are based on human chess theory. So >> these concepts (and the corresponding derived formulas/algorithms used >>in the programs) are optimized for use in particular manner -- for >> human-like search guidance/constraints, reasoning and followups. > >What is without practical relevance is a method espoused by a fraud for thirty >years. There are lots of people doing AI, and I have no doubt that many would >like your proposal. However, straightforward search actually works. > That is an irrelevant attack on Botvinik's approach. So what if they (with or without Botvinik's knowledge/participation) had perhaps hand simulated some results they later claimed their program calculated by itself? That doesn't make the theory faulty. It only means that someone in the team was impatient and took a shortcut in providing the empirical evidence in its support. Given the miserable level of technology they had available in USSR for their work, one can understand that kind of temptation. Returning once more to the short boy & C++ analogy, suppose a more experienced (and a taller) student is using the C++ books they way they were meant, by reading them first. The short boy and his supporters then argue that their method of sitting on the books is better since it does actually work, and the taller boy's way of using the literature is no good since he had used his dad's library card to get the books in a dishonest way, "therefore" since the taller boy is an obvious fraud, reading those books can't be the right way to use them. That's about the level and relevance of Hans Berliner's attack on Botvinik's approach.
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.