Computer Chess Club Archives




Subject: Re: How do you represent chess boards in your chess programms

Author: KarinsDad

Date: 09:11:41 09/29/99

Go up one level in this thread

On September 29, 1999 at 10:02:27, Sven Reichard wrote:

>>Still sounds very fast.  IE you are generating all the moves, which means you
>>are doing a very good job of handling sliders already...  When I first tried
>>this, I had a loop that went thru the 4 directions one at a time to locate the
>>'blocking piece'.  And required 4 calls to bsf/bsr (depending on the direction)
>>to find this blocking square so that a mask could be used to cut off attacks
>>beyond that point...
>An idea to avoid this loop:
>Let us generate horizontal rook moves for simplicity. We have bitboards for each
>color. Assume we have White. If we remove the black pieces from our rank, the
>white pieces allow a certain set of moves, represented by an 8-bit mask. This
>mask, let's call it m_own, depends only on the mask of white pieces and the
>position of the rook; so these 2^8*2^3=2048 masks can be stored in a table.
>Now we just look at the black pieces; we do a similar thing to get a mask of
>moves m_other; another 2^11 masks are stored for this.
>Now the following claim is easily checked: For the mask of pseudo-legal moves
>m_moves we have
>m_moves = m_own & m_other,
>and no further cut-offs are necessary.
>We can use these masks also for vertical moves; for the bishops, we need to
>distinguish every square on the board. Thus the whole table takes
>rooks:     2(colors)*2^3(squares)*2^8(masks) = 2^12 = 4k
>bishops:   2(colors)*2^6(squares)*2^8(masks) = 2^15 = 32k
>a total of 36 kBytes, which I think is reasonable.
>For cpu time, we need (for each line) two table lookups and one binary operation
>to get the mask; from that we can get the move list.
>I sort of implemented it, but haven't tested it extensively yet.
>Any comments?

I am doing something similar, but I have more operations, so I will have to look
at yours carefully to see if it works better.

Effectively, my equation for white to move is:

xorWB = W XOR B
Table = TABLE(xorWB, position of moving piece)
Answer = Table XOR (Table AND W)

For black to move:

Answer = Table XOR (Table AND B)

I then shift Answer to acquire every move. TABLE is 2040 bytes large (255
possible xorWB times 8 potential starting positions in a row/column/diagonal).

So, I have one table lookup, two XORs and one AND. I did it this way since I was
hoping that the fewer table lookups I use, the faster it would be. Also, the
xorWB variable is stored on the stack and then re-used by the evalutation code
and Table is placed in a register for speed.

KarinsDad :)

This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.