Author: Vincent Diepeveen
Date: 07:48:06 10/21/04
Go up one level in this thread
On October 21, 2004 at 07:55:33, Uri Blass wrote: >On October 21, 2004 at 07:15:12, Vincent Diepeveen wrote: > >>On October 20, 2004 at 05:14:45, Uri Blass wrote: >> >>>On October 20, 2004 at 04:44:44, martin fierz wrote: >>> >>>>On October 20, 2004 at 03:39:31, Gian-Carlo Pascutto wrote: >>>> >>>>>On October 20, 2004 at 02:27:19, martin fierz wrote: >>>>> >>>>>>so i want to store the move itself in the hashtable instead of the moveindex >>>>>>now, as probably everybody is doing. >>>>> >>>>>Naah. >>>> >>>>naah? i think storing the move itself is much more sensible than the moveindex >>>>and would have supposed everybody is doing the more sensible thing. at least >>>>crafty does it that way. you can avoid generating all moves at all times, which >>>>i have to do now. you can check whether the hashmove is valid or not. i can't do >>>>all that with my stupid moveindex. it saves 2 bytes of course in the hashtable >>>>entry size, but i don't think that is all-important. what are you doing then? >>> >>>Why saving 2 bytes that are 16 bits? >>> >>>In order to store the move in the hash tables you need only 14 bits. >>>6 bits for the from square >>>6 bits for the to square and 2 bits for promotion information. >> >>if you generate moves in the same order always, keeping a sorted piecelist, >>you only need 8 bits to store a move as there is <= 220 moves in any given >>position. >> >>if you don't generate in a fixed order then storing bestmove in hashtable eats >>only 11 bits of course. > >I understand. >Dieter also explained it in previous post. > > >> >>because you're so intelligent to understand why i'll explain, you just need 2 >>small tables: >> >>tostoremove = table[semilegalmove&0x00000fff]+(semilegalmove>>12); >> >>when retrieving: >> >>mymove = translatetable[tostoremove]; // 15 bits move >> >>Another trivial way to get to 11 bits is giving the 'from square' of a piece >>and with a very small translation table for every piece you then translate the >>next 5 bits in the to-square. >> >>In case of a pawn on 7th rank there is so little possibilities that you can >>easily encode capturing left and right and promotion forward to the different >>pieces. >> >>it's useless to use 14 bits as that's an extra expensive 'if then else'. > >In my case I do not need if then else but maybe it is because I do something >that is even more expensive. > >I simply store the from and to square in 12 bits and the promotion information >in 2 bits. > >When I check if a move is in the hash tables I first generate all moves and >later check for every move if the last 14 bits are the same as the hash move(I >have another bit that tell me if there is promotion in the move that I generated >but that bit is not important for checking if the move is in the hash table). > >I may have a faster function to check if the hash move is legal and maybe in >that case you are right that it is faster to have 15 bits in the hash but I have >more important things to improve then this small speed optimization. > > > >>Additionally you show to not know how to reduce bits even further to a trivial >>11 bits, whereas i'm sure 10 bits with some compression effort is possible too. > >> >>Note that in diep i just use 15 bits for a move everywhere. Much faster. > >I did not show not to know how to reduce bits to 11 bits but I admit that I did >not think about the maximal compression before reading Dieter's post. > >I only thought about better compression then the compression that the post that >I replied suggested. > >I showed a simple way to compress to 14 bits. >You need special tables to compress to less than 14 bits. A L2 cache lookup at A64 is 13 cycles. A mispredicted 'if then else' can easily cost 25 cycles. In short you were not so clever, because for the same systemtime loss you go to 14 bits, you can go to 11 bits already very easily. >Uri
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.