Author: Russell Reagan
Date: 01:00:22 01/20/03
Go up one level in this thread
On January 20, 2003 at 03:25:07, Scott Gasch wrote:
>Ok maybe I'm thinking about thiw wrong but if you have 10 bits for both white
>and black you have 1024 possibilities each side (2^10). Now assume a lookup
>table that is 1024x1024 entries (white square attacks on the horizonal, black on
>the vertical). That is 1M (1048576) entries, say, at one byte a piece.
Well, Ed's lookup table had another dimension for the piece type, so if you were
going to stick with Ed's idea, only upgrade to 10-bit keys, then you would be
using 12 times the space, or 12 MB. But, as you point out below, there are
algorithmic things you can do besides simple table lookup.
>You can
>also do a simple comparison of the two attack bitvectors before you hit the
>memory because if one is zero and the other is non-zero the non-zero side
>controls the square by default without the need to hit RAM.
>
>I've also been trying to come up with a quick way to do this without a table
>lookup and have not arrived at anything wonderful yet. One partial idea is
>using some sort of small struct instead of bitboards:
>
>typedef struct
>{
> char uPawnAttacks;
> char uMinorAttacks;
> char uRookAttacks;
> char uQueenAttacks;
> char uKingAttacks;
>}
>ATTACK_NODE;
>
>ATTACK_NODE g_AttackTable[64][2];
>
>Now instead of a bitvector you have counts (which is more memory hungry). But
>you get these benefits:
>
>1. It works no matter how many pieces / types are attacking a square. Even if
>you promote and have three queens attacking the same square it works. In Ed's
>way and even my 10-bit way you run out of bits after promotions.
>
>2. You ditch the lookup table in favor of just computing the score. You can
>compute the score pretty quickly by translating the struct above into an N bit
>unsigned number where pawns are the most significant bit. When you have both
>numbers, compare them. Whichever is higher controls the square.
That is an interesting approach. I have been playing with 0x88 lately, so I
might give this a try. BTW, you could turn that struct into a 32-bit value quite
easily. You will never have more than one king attacking a square, and never
more than two pawns (at least of the same color). So you can make those bit
fields:
typedef struct
{
unsigned uPawnAttacks : 2;
char uMinorAttacks;
char uRookAttacks;
char uQueenAttacks;
unsigned uKingAttacks : 1;
}
ATTACK_NODE;
Union that with an unsigned int and you're in business. Computing square control
would be fast, and doing SSE should be pretty easy as well after you have this
information (I think). I like this idea quite a bit.
>I'm in serious brainstorming mode and appreciate the dialogue / ideas / advice.
>
>Scott
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.