Author: Graham Laight
Date: 03:48:09 07/25/00
Go up one level in this thread
On July 24, 2000 at 22:05:25, Robert Hyatt wrote:
>On July 24, 2000 at 10:17:29, Graham Laight wrote:
>
>>On July 22, 2000 at 22:21:19, Robert Hyatt wrote:
>>
>>>This is not easy to answer. But here is a rough explanation.
>>>
>>>First, there are several knowledge 'modules' that are called when
>>>appropriate. IE before both sides have castled and developed all pieces,
>>>there is an EvaluateDevelopment() modules that is called. Once this has
>>>done its job, it is disabled for the rest of the game. There are similar
>>>modules for mating the opponent, evaluating passed pawns, evaluating
>>>passed pawn races, and so forth. And they are only called when it is
>>>appropriate.
>>>
>>>The rest is more complex. There are many 'major' terms... king safety,
>>>endgame outlook (ie passed pawns, outside passed pawns, pawn majorities,
>>>and so forth). These terms are phased in based on remaining material. IE
>>>king safety is multiplied by using three factors; 1 is the pawn structure
>>>around the king, 2 is the pieces of the opponent and how dangerous they
>>>appear to be (how close and how many are close) and 3 remaining material.
>>>As material is removed, king safety scores are scaled down.
>>>
>>>By the same token, as material is removed, endgame predictors are scaled
>>>up (ie an outside passed pawn becomes more valuable).
>>>
>>>This is all what I call "third order evaluation" since three complex factors
>>>are used to compute a number...
>>
>>I've downloaded the *.c files for version 17.11, and I'd like to comment on what
>>I've seen.
>>
>>Firstly, I have to say that the code is beautifully written, and very well
>>commented. Gold stars for coding and clarity!
>>
>>Secondly, my comments probably apply equally well to other programs as to
>>Crafty. Unfortunately for Crafty lovers, this code is in the public domain. If
>>you are a Crafty lover, please don't feel that my remarks are aimed at Crafty -
>>I just want to use Crafty as a "typical program", so that I can compare and
>>contrast my ideas with the workings of a modern and successful chess program.
>>
>>In order for me to compare my "model" program (which hasn't actually been
>>written, of course) with Crafty, let me briefly explain how I propose to do
>>evaluation: in brief, I want a database of evaluation functions, and, for each
>>position I want to evaluate, I want to pick from this database the evaluation
>>functions that are best suited to that position. Here's the process in a little
>>more detail:
>>
>>* create a database (db) of evaluation functions (eval fns). For each eval fn
>>record in the db, also record some "indices" ("indices" is the plural of
>>"index") which will later be used to determine how well this eval fn matches the
>>position to be evaluated
>>
>>* generate a chess position to evaluate
>>
>>* calculate the indices for this chess position
>>
>>* match these indices with the eval fn indices. For each eval fn, calculate a
>>"match score", and sort the eval fns into an ordered list (where the eval fns
>>with the best match score (ie most useful to the current position) will be at
>>the top of the list)
>>
>>* select the eval fns from this list which best match the current position
>>
>>* evaluate the position using these eval fns, and weighting the result of each
>>eval fn according to its match score
>>
>>
>>In contrast, Crafty's evaluate.c module puts all the knowledge within the code
>>itself.
>>
>>I don't want to claim to be an expert on evaluate.c, because I've only looked
>>over it briefly, but I would offer the following observations:
>>
>>1. The emphasis is always on speed. The author, again and again, is writing code
>>that will "return" and stop more chunks of code running if an initial test makes
>>it unnecessary
>
>This is called "lazy evaluation". Or "procrastinational evaluation". Never
>do today, what you can do tomorrow. The point is that if you delay some eval
>terms, you might get to exit without doing them at all..
>
>It is all about speed... but it doesn't ignore accuracy at all...
Yes - I agree - given the way your evaluation is done, it's a very good thing to
do!
I apologise if I created the impression that this was a criticism. The
impression I have (that I was trying to point out) is that in designing the
evaluation module, the emphasis seems (to me) to put speed of exececution above
all other considerations. Again, taking your approach, this is clearly a good
thing to do.
However, in my model program, I am placing the management of knowledge on the
top of the priority list.
>>
>>2. The knowledge is all in the code. For example, there's a chunk of code in
>>there which is designed to try to avoid the Stonewall Attack. I believe that if
>>somebody wanted to put a huge amount of knowledge in there, it wouldn't be easy.
>>They would probably resort to doing what is already done in there, and putting
>>in another chunk of code for each piece of knowledge they wanted to add. In
>>"Chess Skill In Man And Machine", they say that a human GM has 50,000 pieces of
>>knowledge (if I may paraphrase their talk of pattern recognition), so be
>>prepared to have a mighty, monolithic evaluation.c module!
>
>without a doubt. But the alternative is really difficult too... if you have
>N evaluation modules (your database approach). Then you get zapped because the
>'selector' (database code) becomes the bottleneck... you might actually spend
>more time trying to figure out what you are going to use for the eval, than a
>large monolithic evaluation would spend...
Yes, there is every possibility that my evaluation method is going to burn a lot
of time. It is quite likely that if we follow my approach, we're going to pay a
high price in terms of NPS. Here are some observations in defence of this
approach:
* computers are not getting any slower (unless you want to carry them in your
pocket)
* I suspect that increasing NPS has a logarithmic impact on elo ratings
* human NPS level is very low - looks like knowledge can substitute for NPS,
just as NPS can sometimes substitute for knowledge (though you clearly get
different "playing strengths" and "weaknesses")
Also, there is a real possibility that significant savings can be made in the
eval fn database record sorting/selection process.
Given that this ordering by indices is commonly used in the AI field of
Case-Based Reasoning (CBR), research has been done as to how this process can be
speeded up. One solution, which in tests has speeded up this selection by a
factor of 10, is the use of "knowledge nets", which is something like a giant
cross referencing system between your database records (though I'm not sure this
would work well if you have a huge number of indices). (my understanding of this
comes from an overview of CBR technology done by Kaiserslautern University - if
you wish to find the book on Amazon, try keywords "Case-Based Reasoning" and
"Technology" in the title - or I can find the ISBN for you). Anyway, 3rd party
CBR products claim to be able to do this kind of thing very efficiently, so my
willingness to use these, together with APIs, could save me from writing this
part of the code.
Having said that, because the program isn't written yet, so we don't know what
indices we would be using for sorting/selection, we therefore don't know how
long it would take to calculate the indices for a position on which the
sorting/selection of eval fns is based.
>I might agree with doing that if it makes the code more readable or more
>maintainable of course... that is why most of the code in Crafty is written
>as it is. It could go a lot faster, but then I would go a lot slower when
>I make changes. :)
>
>
>
>
>>
>>3. The general philosophy of the program seems to me to be to go light on
>>knowledge: "travel light, slay 'em with speed" :)
>
>I wouldn't go that far. I don't do things that I consider to be computationally
>prohibitive, but I have added a lot of things to the program over the past year,
>particularly endgame-related... I try to avoid leaving things out because they
>seem to be hard to implement efficiently... I often test an idea with a cheap
>and dirty implementation, then if it does seem reasonable, I will spend more
>time figuring out how to do it in an affordable manner...
>
As I've said above, I aim to be able to get any knowledge which is "important"
in a position, no matter what the cost in time.
>
>>
>>4. For each piece of knowledge in evaluate.c, it seems to me that you're going
>>to have to do at least some sort of check to see whether it's needed or not
>>(though I admit that sometimes a check can dispense with more than one piece of
>>knowledge code in one go)
>>
>>5. The test for the relevancy of a piece of code is binary - either you need it
>>or you don't. In my model, every eval fn is given a "match score" - and only the
>>eval fns with the highest match scores are run. If there is a lot of knowledge,
>>this could conceivably save time!
>
>This is only true in a broad sense. IE King safety isn't "on or off". It
>is phased out as material goes away, or in as the king position gets shakey.
>Ditto for endgame expectation scores...
>
>Other terms interact. IE king safety, remaining material, location of opponent
>pieces...
It seems to me that you are selecting which knowledge to use on the basis of
"inductive reasoning", or a tree of questions.
e.g.
Is there plenty of material left?
|
|
|- Yes
| |
| |- Are the opponent's pieces near my king?
| |
| |- Yes
| | |
| | |- Are the pawns around my king well placed?
| | |
| | |- No
| | | |
| | | |- A king safety problem exists
| | |
| | |
|---|---|
|
|
A king safety problem does not exist
Now, inductive reasoning is usually faster that the sorting/selection process,
but, especially when there are a lot of records to look at, it becomes less
accurate. Generally about 20% less accurate.
A _simple_ example of how it can go wrong would be as follows:
Suppose a car dealer has 2 cars of interest on his website - a Jaguar and a BMW
- and there are only 2 selection criteria - colour and sex-appeal. And finally,
suppose you (the buyer) want to buy a sexy car.
If the website uses inductive reasoning, if the first question is asking you
what colour you want, you may eliminate the Jaguar before you even get to the
sex appeal question.
If, on the other hand, selection was done by indices, you would be asked
(hopefully) to specify your requirements for colour and sex-appeal, and also for
weightings (how important these indices are to you).
In this case, you'd specify that colour was of low importance, high sex appeal
was very important, and even though you'd asked for the wrong colour, the Jaguar
would still appear at the top of your list.
The other benefit is that the BMW would still appear on your list - in 2nd place
with a lower match score - so you could still consider it.
Anyway, hopefully this demonstrates that "Nearest Neighbour" reasoning is
generally better than "inductive" reasoning (except in terms of speed).
>>
>>So - these are my initial thoughts. I believe that my model program has the
>>potential to evaluate positions better than Crafty can. I suspect that many
>>modern programs would, if the code was made available, be subject to the same
>>observations.
>>
>>-g
>
>I wouldn't begin to suggest that my approach is the cleanest. And the
>evaluation is where the most work is needed. The search is doing fine on
>good hardware... I think the main thing I have done, and will continue to
>do, is shore up the knowledge. Fortunately I have some GMs that are willing
>to point out things they see and don't like...
Yes - all good stuff!
-g
This page took 0.01 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.