Author: Vincent Diepeveen
Date: 03:13:44 10/22/04
Go up one level in this thread
On October 21, 2004 at 14:20:05, Dieter Buerssner wrote: >On October 21, 2004 at 07:55:33, Uri Blass wrote: > >>On October 21, 2004 at 07:15:12, Vincent Diepeveen wrote: >> >>>it's useless to use 14 bits as that's an extra expensive 'if then else'. > >Not necessary. Assume you have (for example) N=2, B=3, R=4, Q=5. > > >move = from*64 + to + (promoted_piece-2)*64*64. >No branches. You need everywhere extra branches. move ordering, see, you name it. If you just use it to store in hashtable like that you will need to write extra 'if then else' to convert to 15 bits: 'in case there is a pawn on 7th rank for this and that side, THEN modify upperbits of move. Losing cycles for nothing. You can read in parallel from L2 cache. So for same effort you can already do a lookup to L2 cache when doing other lookups and convert from 11 bits to 15 without any effort. Assuming it's in L2 and not in L1, which in a number of cases will happen too. >>I showed a simple way to compress to 14 bits. >>You need special tables to compress to less than 14 bits. > >I can suggest a method to compress to 9 bits. Enumerate the pieces, for example >from a1-h8. 16 pieces max, so with 4 bits you can "adress" each piece. Maximum >numbers of moves per piece is 27 -> 5 bits. It would need a few tables, but no >move generator. The piece adress gives the from square. The to square could be >something like: to = to_table[board[from]][move>>4]. This is similar to what nicbase did. Note that in move generator you must then keep your pieces sorted each time you make a move. In DIEP i do this in interface code of engine. As they are sorted anyway, i can simply generate the legal move list and just use a variable number of bits to store each move. On average 5 bits a move. >For all "normal" positions 8 bit is also possible. For example when we assume, >that there are less than 3 queens and less than 5 rooks + queens, ... of one >color. Now enumerate the pieces first by vale (K, Q, R, B, N, P) and then by >square (Qa1 comes before Qa2). The move will be a byte. value 0-7 means the K >move. From 8 to (8+26) the 2nd piece (for example a Q), etc. > >8 + 3*27 + 2*15 + 2*14 + 8*12 = 243. > >I used 12 possible moves for pawns and knights here (a pawn can have 12 moves, a >knight of course not). A bit more tweaking, and it will be enough for 4 or 5 >queens, and will probably be able to store all mvoes in all seriously played >games. For a database (where one also wants to store some constructed games with >many promotions), for example move number 255 could mean an "escape", (in case >of 9 queens, etc.) and the next 2 bytes store the move in a more conventional >way. > >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.