Author: Ricardo Gibert
Date: 20:01:19 08/19/99
Go up one level in this thread
On August 19, 1999 at 14:03:01, David Eppstein wrote: >On August 18, 1999 at 20:25:06, KarinsDad wrote: >>Doesn't 2 * 2^162 + 16 * 2^161 > 2^165? >>>So even ignoring the cases you can't handle, you still have 166 bits required. >>>Why do you say the maximum required is 162? >> >>The cases are not part of the same position, but rather templates of given >>position types. For example, you could split positions into 17 cases: ones with >>16 pawns, one with 15 pawns, ..., ones with zero pawns. > >Perhaps you misunderstood my question. Any count of the number of bits required >to store a position has to include the number of bits used to tell which case >you are in. Otherwise I could just divide into 2^180 cases and say that I store >the position in 0 bits. It seems that when you are saying you require at most >162 bits (except for the cases you can't handle) that you are not counting this >part of the representation. I know what you are getting at, but there is 2nd way of encoding information in memory. Information can be stored "by value", which is what you are thinking of, and another way is "by location". In essence, you have a value to store and many places to put it. By not being arbitrary about where you put it, you can encode more information and so save space. An EGTB is an example of using 1 bit to encode a position. Another example is a dictionary, where there is no reason why you can't clip off the 1st letter of each word, since you know what it is by which section (A-Z) it is in. Such a dictionary would be a hybrid of the 2 ways: by value & location. Presumably, with 17 cases, you would in effect be dividing up one database into 17 databases. Which one you look in is determined by the search key. Example: The position I am looking for has 4 pawns so I look in database 4 + 1 = 5th database. Karinsdad is gradually getting more aggressive with this technique to achieve a more compact form, but he is not really encoding positions in fewer bits, whether it 160 bits or or 128 bits or whatever, since you must not forget the bits encoded "by location". At first it seems you are getting something for nothing, but you are really making a trade off at the expense of simplicity, time and flexibility. You must manage more cases. 2^180 cases is an example of over doing it. Inefficiencies can develope when you divide up the "cases" in a way such that only a few are being used most of the time and the other cases use up time and space for little return. The trick is how to divide things up. The dividing up into cases is a kind of sort, which is preserved by the database itself to save spacein its storing of values.
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.