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.
