My idea is not fully formuated and it is likely to be slow compared to existing methods like Magic Numbers.

I know magic numbers seems to be the way to go for fast generation of attack bitboards. It seems very memory intensive.

My idea came after reading a discussion of the amount of memory required by these attack bitboards.

Given that memory is cheap, I don't really see memory as a problem, unless someone tried to create queen magic

rather than using a union of rook and bishop attach bitboards. That's because the queen can move to very many squares.

Still, I was thinking about attack bitboards, their tables and hashing, and this is what I came up with.

Hashing

---------

A bishop or rook can move in 4 directions along two lines.

Queen attack bitboard are usually created as the union of rook and bishop attack bitboards.

Similarly, at the cost of some processor time rook and bishop bitboard can be created as a union of bitboards for two lines.

With good hashing, the indices for lines are likely to be at most 8 bits - not very memory intensive.

So I don't see any need to subdivide and go smaller still, although my first attempt at a chess program did/does

what I call shadow removal (regarding the active piece as a light source), on a direction by direction basis.

It calculated 4 times, N,S,E,W for a rook; this proposes we calculate NS together, and then EW.

If you logically AND a piece occupancy bitboard with a bitboard for the line, you can create a distrubuted 8 bit bit pattern.

This bitpattern then needs to be hashed into a small number of consecutive bits if it is to be easily used to index an array.

This is where magic numbers come in useful, but they are not part of this discussion - they not only permute the order of the bits in

an index, but also muddle values. This is appears to be one reason a lot of memory is required with the magic number approach.

So for hashing, I decided to use modular arithmetic. I don't propose to discuss it in detail, but basically, all I want

is a method to compress a bit pattern like 'a00000000b00000000c00000000d00000000e00000000f00000000g00000000h'

into a bit pattern like 'abcdefgh'.

Now that is precisly what modular arithmetic does. Working modulo 255, 256=1.

So bits could be 1 bit apart (rook moves) or an extra 8 bits (multiple of 256, ie a multiple of 1 modulo 255) forwards or backward (bishop moves)

and they still appear as adjacent when hashed using modulo arithmetic. [The precice choice of modulus chosen may depend on the board layout used etc.]

Anyway, a relatively simple calculation will compress the piece line occupancy bits into an 8 bit value without fundametally changing the bit order or muddling the bit values: it should simply close up the bits.

Recreating a bitboard

-------------------------

Scattering the bits abcdefgh back along the line '1000000001000000001000000001000000001000000001000000001000000001'

is just a simple matter of ANDing a multiple of the bitpattern and the bits for the line, eg :-

- Code: Select all
`1000000001000000001000000001000000001000000001000000001000000001&`

abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh =

a00000000b00000000c00000000d00000000e00000000f00000000g00000000h

Motion and Attack

---------------------

There are 256 ways pieces can be distributed along a line. (Treat short bishop digonals as longer lines with some empty locations.)

There seem to be about 37 motion combinations and about 30 attack possibilities. (These are shown below.)

And there are 8 ways the piece under consideration (doing the moving or attacking)

can be distributed along a line.

So to generate motion and attack bitboards, I initially thought I might need an array of size [256][8]

for the various locations of the moving piece and scattering of the other pieces that may or may not obstruct its path.

The MOTION array contains a string of contiguous 1s indicating the reachable squares for the active piece moving backwards or forwards along the line.

The ATTACK array typically contains a pair of bits indicating the position of the first piece that would be hit by the active piece moving either backwards or forwards from its current location. It may contain less bits, eg a bishop at H8 will never hit another piece by moving in the direction SE/NW.

- Code: Select all
`int motion[37] =`

{ 0, // 0 00000000

1, // 1 00000001

2, // 2 00000010

3, // 3 00000011

4, // 4 00000100

6, // 5 00000110

7, // 6 00000111

8, // 7 00001000

12, // 8 00001100

14, // 9 00001110

15, // 10 00001111

16, // 11 00010000

24, // 12 00011000

28, // 13 00011100

30, // 14 00011110

31, // 15 00011111

32, // 16 00100000

48, // 17 00110000

56, // 18 00111000

60, // 19 00111100

62, // 20 00111110

63, // 21 00111111

64, // 22 01000000

96, // 23 01100000

112, // 24 01110000

120, // 25 01111000

124, // 26 01111100

126, // 27 01111110

127, // 28 01111111

128, // 29 10000000

192, // 30 11000000

224, // 31 11100000

240, // 32 11110000

248, // 33 11111000

252, // 34 11111100

254, // 35 11111110

255 // 36 11111111

};

int attacks[30] =

{ 0, // 0 00000000

1, // 1 00000001

2, // 2 00000010

4, // 3 00000100

5, // 4 00000101

8, // 5 00001000

10, // 6 00001010

9, // 7 00001001

16, // 8 00010000

20, // 9 00010100

18, // 10 00010010

17, // 11 00010001

32, // 12 00100000

40, // 13 00101000

36, // 14 00100100

34, // 15 00100010

33, // 16 00100001

64, // 17 01000000

80, // 18 01010000

72, // 19 01001000

68, // 20 01000100

66, // 21 01000010

65, // 22 01000001

128, // 23 10000000

160, // 24 10100000

144, // 25 10010000

136, // 26 10001000

132, // 27 10000100

130, // 28 10000010

129 // 29 10000001

};

Generating Attack Data from Line Data

----------------------------------------------

It then occured to me that 30 (37 is too) is a small number, less than 64.

This means the possible attack arrays for a piece position along the line (eg A-H) can be bitmapped,

and the possible attack arrays for pieces scattered along a line (0-255) can be bitmapped.

What I mean here, is bit 0 set if motion[0] is possible, and bit 1 set if motion[1] is possible,

bit 2 set if motion[2] is possible, etc.

So rather than require an array [256][8], we just need an array [256] and another [8]

and we AND their contents. The first array with 256 elements tells us which attack are possible for a particular piece occupancy of a line

and the second array tells us the attacks possible for an active piece at a given location in its line.

The result of the AND operation indicates possible attacks

with pieces scattered along the line a certain way and with the active piece at the specified point

along the line.

Summary

-----------

I feel I have found a way to generate attack or motion bitboards using a handful of arrays, none of which contain more than 256 elements.

Speed and applications

---------------------------

I am not thinking that this will be useful for a normal chess playing engine, so please don't tell me that magic is faster, better, etc.

I would like an application on a smartphone that understands chess and yet CANNOT play the game.

I play games over the board and sometimes want to write down the moves. I'd like to have a visual chess board on my phone

and to drag and drop the pieces as I move them, rather as if I were playing chess online, but having to move both white and black pieces.

At the end of the game, it'd be great if the phone could then store the game in a file in portable game notation (PGN) format.

The program can be as slow as it likes - its aim would be simply to register the moves played - an electronic version of

a game book or score sheet. It must NOT be able to play chess, to avoid possible accusations of cheating.

That is the sort of application that might benefit from a low-memory algorithm for generating attack bitboards.

I have glossed over many things here, for these reasons.

1. I haven't actually done it yet I may add sample code for the [256] and [8] arrays later.

2. There are some intricacies to modular arithmetic bit hashing best discussed elsewhere.