Author: Graham Laight
Date: 04:07:51 07/24/00
Go up one level in this thread
For the benefit of everyone, I'll trim this post a bit. But in order to help
people who want to understand the context of this discussion, I'll put here a
brief summary of what it's all about:
* I have designed a "model" chess program (it hasn't actually been written
yet)which I believe has the benefit of being able to build, manage, and maintain
large amounts of knowledge relatively easily
* Ed believes that the existing knowledge management in his (and other) programs
is already adequate, and that managing knowledge in many chess programs is not,
in any case, the major difficulty in making them play chess well
In my model program, when a position is to be evaluated, here are the steps
which are carried out:
* Some indexes (or "indices") for the position are calculated
* a database of evaluation functions (eval fns), in which each eval fn is
stored, together with values and importance weightings for each of the indices,
exists
* the database is queried with the current indices and weightings, and thus the
eval fns are ordered according to how well they match the current position
* The best (closest matching) eval fns are selected, and their "closeness of
matching" is taken as their evluation weighting
* The evaluation is calculated according to these eval fns and their weighting
By this means, the best knowledge for the position has been selected and used to
calculate an evaluation
>>Here we have a rule, called the "quadrant rule". The things we have to get to now
>>are:
>>
>>* when evaluating a position, how do we select this rule?
>>
>>* where do we store (or code) this rule?
>>
>>I suspect that in many cases, a giant monolithic eval fn runs a lot of code,
>>some of which determines whether the quadrant rule is needed, and if it is, it
>>is run from elsewhere within this monolithic eval fn.
>
>Programmers incrementally maintain some important data during the search
>process. One of them is the variable that says, does white has at least
>a N/B/R/Q. If white has not the quadrant rule is called for each black
>passed pawn and vice versa. So it's just one simple instruction to detect
>the quadrant rule is needed or not.
This is good!
I will even give you the benefit of the doubt and assume that this rule is not
buried in a monolithic eval fn which also contains hundreds of other such rules!
(if it is, then management of this knowledge is going to be difficult)
Certainly, you are left with the decision of what "indices" (in this case, "does
white have at least a N/B/R/Q") to pass down the search.
In my model, simplicity is gained by calculating the indices "just in time". I
think that benefits will be gained by calculating them all together (I'm sure
that the results of calculating some indices will be used in calculating other
indices). Also, it means that you've got all your code for determining the
things that it is necessary to know about a position in one place, rather than
scattered around, which is obviously going to be inefficient (from a knowledge
management point of view). In the fullness of time, I expect that this
calculating of indices for a position could be done with parallel processing to
make it even faster.
I expect to make gains in time usage elsewhere.
* where there are pawns, but no N/B/R/Q, you ALWAYS fire the quadrant rule. But
there may be situations where you fire the rule DESPITE the fact that other
positional aspects make this quadrant rule pale into insignificance
* when ordering the eval fns and picking the most important, there are various
tricks you can do to speed up the process, and avoid having to calculate the
match score for every eval fn. I know that there are third party products that
do this very efficiently. Because I am willing to use APIs, I am saved from the
burden of having to do the job of trying to write this code for myself
>>But are you honestly in a position to say that when you evaluate a position you:
>>
>>* select the units of knowledge that are most appropriate for the position
>>
>>* give these units of knowledge a weighting for their importance in THIS
>>PARTICULAR position
>>
>>* evaluate accordingly
>
>I think that Rebel in 99% (rough estimation) of cases hits the right piece of
>knowledge for every position in the right way it has to search. Note that 99%
>is not much. It means an error rate of 1% and that after evaluating 1,000,000
>positions 10,000 positions are evaluated not accurate. Not accurate can mean
>many things: firstly it depends on playing style and makes "not accurate" quite
>arbitrary. "Not accurate" can also mean a slightly worse evaluation up to dead
>wrong. Search most of the time will filter these evaluation errors but if the
>"not accurate" evaluations are dominating the search (especially from the root)
>you get bad moves. Famous examples are: trapped pieces, hidden king attacks,
>strategic positions.
>
>Take the 99% with a grain of salt as I have no real data to support that
>number it is just a rough estimation but in general this is the way a chess
>program works.
>
>Note that in the above the material (tactics) is not included as this is done
>by search. Most evaluation functions only evaluate the positional aspects of
>a position and leave hanging pieces to Q-Search. There are some exceptions
>such as the quadrant-rule that may count a passed pawn for a queen, claim
>0.00 for KNNK and more of such.
Why do you suppose it is that these positional evaluation errors occur?
Here are some suggestions:
* There's not enough knowledge in the system
* We're picking the wrong knowledge for the position
* We're not giving the knowledge that we do select an appropriate weighting
* The knowledge in the system has become sprawling and difficult to manage
>>And that also you can:
>>
>>* add new knowledge easily and cleanly
>>
>>* "index" this knowledge according to a set of indices that will determine which
>>knowledge is selected in a particular position (and their weightings in this
>>position)
>>
>>* Quickly and easily obtain a ordered list (ordered by weighting) of which
>>pieces of knowledge will be selected for a particular position
>>
>>* Easily adjust the indices if this knowledge selection does not produce the
>>required ordering?
>>
>>If you can do all this, I'll say right now that I'm very impressed!
>
>Thank you. The answer is of course a yes. Easy adding new knowledge is a
>must. Programmers in their first 10 years tend to rewrite crucial parts of
>the chess engine (if not all) from scratch once in a 3-5 year cycle because
>of this reason, to be more flexible. Rebel has been rewritten from scratch
>4-5 times, last time in 1994.
Maybe we need to consider the possibility that the adding of new knowledge
should become the main thing.
You've spoken before about your irritation with the "exceptions" that players
keep finding to the knowledge that you've applied.
These "exceptions" represent additional knowledge requirements.
Computer factories are turning out machines that can run ever more processors (I
think Bob has said that he can get upwards of 5m NPS on an multiprocessor
Alpha).
What are we going to be doing with all this power? Are we going to just drive up
the search depth, with logarithmic benefits? Or are we going to drive up the
knowledge level, with the potential for much higher benefits - if we can manage
that amount of knowledge?
>>Automatic learning is a bit of a holy grail! It would be great!
>>
>>Guess what? I'm going to claim that with my model program, there's a way to
>>attempt to do automatic learning.
>>
>>You could use genetic algorithms (purchased if you don't want to write them) to
>>tinker with the indices (the indexes ("indices" is the plural of "index") used
>>to select the best eval fns for the current position) then use the results of
>>games to "evolve" these indices to a winning formula.
>>
>>It may well be that people have tried to do something similar before. If they
>>have, I suspect they've tried to do it in terms of directly adjusting weightings
>>within their eval fns. This is not good enough - what I'm talking about here is
>>trying to select the BEST knowledge from a big collection for a particular
>>position. I think that will work better.
>
>In case you are interested in this subject there is a commercial program
>that exclusively works (learns) via neural network. The programmer is "Alex
>van Tiggelen" but I forgot about the name of the program. The program got
>very few attention.
Interesting. At the moment, computer NNs are not big enough to match the brain.
However, there could be a possibility of using them to determine whether a
positional aspect exists in a particular position - if it proves to be difficult
to write an algorithm to determine that.
>>A pointer to another table could result in recursion or circular reference. Not
>>easy to manage the knowledge if this could happen.
>
>These kind of things are done to speed-up the code and generally have
>nothing to do with evaluations.
>
>Ed
I can't comment in detail about how your eval is done, but my general comment is
that having so many different types of things all over the place in your
"knowledge tables" is likely to make the knowledge that little bit more
difficult to manage.
Each of these little things on their own are not a serious problem, but when you
have a large number of them, I suspect that together they will make the process
of adding (or modifying) knowledge sufficiently more difficult that you might
decide not to undertake the task in some cases, which may result in positional
holes in your chess game that another player can exploit.
Another benefit I wanted to point out of using a database to store the knowledge
would be the amount of useful information you could store with each eval fn:
* Full text descriptions of what it's supposed to do, and the type of position
in which it's supposed to do it
* References to where the knowledge came from (book title, author, chapter,
page, etc)
* Web site links
* Links to other relevant eval fns
* keyword search terms
+ anything else you can think of. What a wonderful asset to have when working
with your knowledge!
-g
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.