Author: Robert Hyatt
Date: 19:58:10 11/20/00
Go up one level in this thread
On November 20, 2000 at 21:39:17, Bob Durrett wrote: >Before launching into the "new idea," I must admit that I have never seen the >source code for Fritz, Rebel, and any of the other commercial chess programs. >Maybe this "new" idea is already being implemented, at least in part. > >NEW IDEA: > >If a program evaluates each new position from scratch, it will take a certain >amount of processor time, and the software will take up a certain amount of >space in memory, and the situation will be much the same for each position of a >chess game. > >But what if the same [or equal] evaluation could be done in a fraction of this >time? How? It is wasteful to throw useful information away, so find a way to >use it. > >The answer may be to use an "evaluation" method which converges on the correct >evaluation by means of an iterative process. This process need not be >restricted to evaluation of the current position. > >For some, this may require casting off self-imposed boundaries [doing it the way >"it's done"] and moving into a new paradigm. > >If it is noted that consecutive positions are necessarily very similar, then a >way should be sought to use the information gleaned in one position and to use >as a starting point for the evaluation of the next position. This may require >finding a radically new way to do "evaluation." > >Similarly, two positions separated by two half-moves in a game are also very >similar, although typically not as similar as two positions separated by a >"distance" of one half-move. This suggests that information obtained during the >"evaluation" of a position might also be useful for positions separated by more >than one half-move. This has been done forever. It is called "incremental evaluation". Chess 4.x even used an incremental move generator since most of the moves that are legal in position X are also legal in position X' (X'=MakeMove(X,move)); > >One could extend this idea to positions separated by "distances" of many >half-moves. In fact, some of the information known in advance before the game >begins [assuming starting from the usual starting position] should have some >bearing on all of the positions which follow in a game. The greater the >"distance," the less the usefulness of the information.. This is also not new. Some programs do a _lot_ of evaluation at the root, then use piece-square tables to score positions at the tips. Some programs go 1/2 way down the tree, then do the expensive evaluation, then only update small changes as the tree progresses beyond that point > >This idea could be used "backwards" as well. Since positions in a chess game >are reasonably similar if separated by some reasonably small distance, then the >evaluations of positions could also be used to refine prior evaluations of prior >moves. This suggests some sort of iteration, maybe. > >As I understand it, hash tables contain precious little information about each >position. That would have to change to use this method. In fact, the structure >of hash tables and the way they are used would have to change. > >Information obtained from a position would have to be retained by the program in >some manner. The use of hash tables is the "current paradigm" way of doing it. >But the information might also be stored in settings the values of integers used >in loops, for example. Innovation by programmers not bound by the boundaries of >current paradigms might be needed here. > >It is not suggested that any ordinary beginning programmer could figure out the >optimal way of doing this. But wouldn't it be worth the pain and agony required >of an innovative programmer if he/she could work out a practical way of doing >this? The problem is that it is already being done by some. There are problems. IE in an incremental eval, for a search with 6 moves in the analysis, the incremental eval is pretty cheap. But suppose you search 30 plies in an endgame. You do more work doing the incremental stuff than you would if you just scored at the tips. > >Underlying message: To produce big improvements in performance of chess-playing >software, or any other kind of software, for that matter, it may be necessary to >cast off the shackles of the assumption that "doing it the way it's done" is the >only way. One should look for new paradigms. This "evaluation" idea is my >attempt to do just that. The problem with your statement is that it is made "in the dark." What you cast as a new paradigm is exactly what most programs were doing 25 years ago. :) > >Incidentally, the name "Shannon" could be mentioned. Any scheme which throws >away, repeatedly, large amounts of information is inferior in the sense that it >is theoretically better to use most or all of the information available, >assuming that a practical way to do that is found. > > >Bob D. Unfortunately alpha/beta throws away 99.999% of the information passed over in a normal tree search.
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.