Empty board moves table

[monk64]

I've been toying around with a chess engine as a hobby. One thing that occurred to me is that it's rather easy to pre-compute an "empty board moves" table.

Such a table would look like this (if written out in ASCII):

piece type:square:ray (if applicable):list of squares that piece can move to]

So, for example:

(type:square_from:ray:squares_to)
B:G4:NW:F5,E6,D7,C8
N:C3::A2,E2,B1,D1,E4,A4,D5,B5

Obviously, in most engines these squares would be represented as numbers or bits, etc.

For knights and kings, ray is not needed - you just list the squares. For pawns, you need one for captures and one for moves, and it varies by color since they move in opposite directions.

I wrote a quick perl script to generate the data and it came out to 1160 lines - there are a lot of rays that don't get printed (a rook on A1 can't move West, for example). At any rate, even in ASCII form as shown above it's only ~20K, and will obviously be smaller in memory when converted to internal representations.

I'm thinking that at move generation time, this could be used to eliminate all the "am I off the board" math and checks.

Let's say you load this info into a tree in memory. When you're computing non-sliders, it's very easy to combine the possible moves with "friendly occupied" bitmap and wah-lah, there are all the moves in one stroke.

For the sliders, it's more complicated and still would involve some ray tracing. But no bounds checking - you'd start on each ray with the moves and go until you hit an enemy (stop there) or friend (stop one before).

I'm wondering if there is a way of speeding that up, again through pre-computation. Perhaps an "obstructed squares" tree like this:

square_def:square_atk:type_atk:friend/enemy:obstructed_squares

So if you were generating moves for a bishop on C3, you'd combine it with a bitboard of friendly pieces and then another "obstructed squares" board that would say "If the attacking square is C3 and it's a bishop, and I'm a friendly piece on D4, then E5, F6, G7, and H8 are obstructed". I haven't thought this part all the way through

Anyway, the precomputation is not large for empty board moves, nor for obstructed squares.

Is there any merit to this approach? Am I reinventing the wheel? Probably...

[hgm]

I think GNU Chess uses this method. It actually maintains two such lists: one for the next square the piece could go to if the current square was empty, (so this would be the list you propose), and the other one the next square to try if the current square was occupied.

In my Xiangqi engine HaQiKi D I only use lists of board steps for each pieceType / square combination, leaving it to a program loop to implement distant slider moves. This saves time for pieces on edge and corner squares, and is a very efficient way to implement the board zones (Palace and River): a King on f2 would only have moves to f1 or e2 listed, so it will never try to step out of the Palace. It also takes care of 'promotion' of Pawns when they cross the River: the squares on the other side simply list 3 moves for the Pawns, in stead of one.

[Michel]

I think GNU Chess uses this method. It actually maintains two such lists: one for the next square the piece could go to if the current square was empty, (so this would be the list you propose), and the other one the next square to try if the current square was occupied.

That must be GNU Chess 4. GNU Chess 5 uses rotated bitboards.

It is on my TODO list to change that into magic bitboards (because they are conceptually much easier to understand).