Computer Chess Club Archives




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

Author: Sven Reichard

Date: 07:02:27 09/29/99

Go up one level in this thread

>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?


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.