ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Plain and fancy magic on modern hardware
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Robert Houdart



Joined: 15 Mar 2010
Posts: 1338

PostPost subject: Re: Plain and fancy magic on modern hardware    Posted: Thu Aug 26, 2010 10:09 am Reply to topic Reply with quote

If memory footprint is an issue, one can always apply a compacting scheme to the rook and bishop tables.

In the "fancy" magic scheme the rook table contains about 100k 64-bit entries (around 800 kB), but in reality there are only 4900 different attacking bitboards possible for a rook, so there is an important redundancy.

One can easily construct the look-up table of 4900 different attacking bitboards (about 40 kB), and then replace the 100 k rook table entries with a 16-bit index in the look-up table. This leads to a memory footprint of 40 kB + 2 * 100 kB or about 240 kB instead of the initial 800 kB.

The next step is to realize that there are maximum 144 rook attacking bitboards for a given square. This means that one can replace the 16-bit index with an 8-bit index combined with a fixed offset per square. This leads to a memory footprint of 40 kB + 100 kB or about 140 kB instead of the initial 800 kB.

In the "plain" magic scheme the savings would be even more important. The 2048 kB rook table becomes 40 kB + 256 kB or about 300 kB.
The plain magic code shown above would simply become:
Code:
byte mBishopAttacks[64] [512]; // 32 K
byte mRookAttacks  [64][4096]; // 256 K

U64 mRookLookup[4900];  // 39 K
U64 mBishopLookup[1428];  // 11 K

struct SMagic {
   U64 mask;  // to mask relevant squares of both lines (no outer squares)
   U64 magic; // magic 64-bit factor
   int offset;   // offset into lookup table
};

SMagic mBishopTbl[64];
SMagic mRookTbl  [64];

U64 bishopAttacks(U64 occ, enumSquare sq) {
   occ &= mBishopTbl[sq].mask;
   occ *= mBishopTbl[sq].magic;
   occ >>= 64-9;
   return mBishopLookup[mBishopTbl[sq].offset + mBishopAttack[sq][occ]];
}


For the bishop table there are 1428 attacking bitboards, so the 40 kB (fancy) bishop table compacts to a 11 kB look-up table and a 5 kB index table = 16 kB. Probably less useful.

I've tested this compacting scheme successfully in Houdini, but I'm still not sure whether it's really beneficial or not.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Plain and fancy magic on modern hardware Robert Purves Sun Aug 22, 2010 5:52 am
      Re: Plain and fancy magic on modern hardware Gerd Isenberg Sun Aug 22, 2010 8:33 am
            Re: Plain and fancy magic on modern hardware Robert Purves Sun Aug 22, 2010 10:55 am
                  Re: Plain and fancy magic on modern hardware Edmund Moshammer Sun Aug 22, 2010 11:05 am
                        Re: Plain and fancy magic on modern hardware Robert Purves Mon Aug 23, 2010 4:35 am
                              Re: Plain and fancy magic on modern hardware Gerd Isenberg Mon Aug 23, 2010 6:03 am
                                    Re: Plain and fancy magic on modern hardware Robert Purves Mon Aug 23, 2010 7:30 am
                                          Re: Plain and fancy magic on modern hardware Gerd Isenberg Mon Aug 23, 2010 10:08 am
                                                Re: Plain and fancy magic on modern hardware Robert Purves Mon Aug 23, 2010 10:01 pm
                                                      Re: Plain and fancy magic on modern hardware Gerd Isenberg Tue Aug 24, 2010 8:30 pm
                  Re: Plain and fancy magic on modern hardware Gerd Isenberg Sun Aug 22, 2010 12:23 pm
      Re: Plain and fancy magic on modern hardware Wylie Garvin Mon Aug 23, 2010 9:39 pm
            Re: Plain and fancy magic on modern hardware Robert Purves Wed Aug 25, 2010 10:02 am
                  Re: Plain and fancy magic on modern hardware Robert Houdart Thu Aug 26, 2010 10:09 am
                        Re: Plain and fancy magic on modern hardware Gerd Isenberg Thu Aug 26, 2010 2:08 pm
                              Re: Plain and fancy magic on modern hardware Robert Houdart Thu Aug 26, 2010 2:27 pm
                                    Re: Plain and fancy magic on modern hardware Gerd Isenberg Thu Aug 26, 2010 2:56 pm
                                          Re: Plain and fancy magic on modern hardware Robert Houdart Thu Aug 26, 2010 3:26 pm
                                                Re: Plain and fancy magic on modern hardware Gerd Isenberg Thu Aug 26, 2010 3:46 pm
                                                Re: Plain and fancy magic on modern hardware Robert Purves Fri Aug 27, 2010 2:11 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads