Author: Dieter Buerssner
Date: 05:46:59 12/07/03
Go up one level in this thread
On December 06, 2003 at 06:05:28, Tim Foden wrote: >On December 05, 2003 at 14:33:26, Dieter Buerssner wrote: > >>I can maximally store one >>score per entry (but want to experiment with two, soon - one upper and one lower >>bound). > >I guess that if you store both an upper and lower bound, you need to also store >separate drafts, eh? Sure. One move might be enough, however (typically, I also store a move in case of an upper bound). Not sure yet, about an additional flag needed, that says "this is lower bound" or so. >In GLC the move takes 23 bits, and the score takes 20 bits and the draft takes >12 bits, and I like to have the full 64 bit hash key in the record, and I don't >want to go over 16 bytes for the whole record. I have 3 bits to spare... :) I use 16 bits for the move (15 would be enough), from (6), to (6), promotion piece (3) (and "overlayed" some special states, like "this score was from TB"). From this, I can regenerate the full move info (including ep/casting/capture flags, etc.) with not too much work. Because I will do a full verify of the move anyway in case of cutoff, it is almost free. Lower 15 bits of my full move are exactly the same as the move I store in the HT, so basically no "compression overhead" at store time. As we both know, one could of course even compress better. I store only 32 bits of the hash key. For score, I need 16 bits at the moment, but I am intending to make this 24 bits. The idea is to use 8 additional bits in case of draw score, for example to prefer a pos with better eval in case of a TB-draw. But perhaps this can also be done for storing the scores with the 16 bits (but that would need another compression/decompression step for storing/retrieving the score). At the moment, I use 12 bytes for one HT-entry (with a bit of space left), and 16 should be enough for 2 bounds. What bothers me, is that I have too many calls to probe (in absearch and I have 3 different qsearch functions). The cutoff logic is not in the probe function itself, but rather in the caller (because things are done slightly different at the various levels). So, there are a lot of places, where I have to change something. I of course should think about a better design for this (without so much redundant code). >I realise that I could store approximate values for the score and the depth, and >I could compress the move, but I can't be bothered (I've actually tried move >compression though). > > >class CHashTableRec >{ >#pragma pack(push, 1) > UINT64 m_hash; // 8 hash key for record > UINT32 m_info1; // 4 age, draw flag, score type, move > INT32 m_info2; // 4 score, depth >#pragma pack(pop) > >// the info words look like this: >// >// ------------- m_info2 ------------- ------------- m_info1 ------------- >// ssssssss ssssssss ssssdddd dddddddd / aaaatt00 0mmmmmmm mmmmmmmm mmmmmmmm >// >// key: >// s = score, in millipawns, signed >// d = depth, in eigths of a ply, unsigned >// a = age indicator, 0 -> record not used >// t = score type, none, exact, upper or lower >// m = move > >Mantis will only use 14 bits for the move, 15 bits for the score, and 10 bits >for the depth. 14+15+10+4+2=45, leaving 19 bits. not quite enough for another >depth and score, but if we have 2 bounds, we don't need a the flag bits, so >14+30+20+4 = 68. 4 bits too many. If I drop a couple of bits from the depth, >so it's only accurate to 0.5 ply, then all this would fit :) Or don't store all 64 bits of the key, of which typically many are redundant anyway (if you calculate the index to the table from the key)? Say you use a power of 2 scheme and have a minumum of 2^12 entries, you can save 12 bits always, without losing any info. Without a power of 2 approach, using modulo for index calculation and divide for the part of the key to store can be done. On x86, compilers can generate code that will only need one div instruction, so overhead is neglible (especially, when considering the slow memory access, that will follow). Regards, Dieter
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.