Magic bitboards, Java

[Pradu]

What I would try as a magic generation algorithm (this is how I constructed the above magic by hand) is to set as few bits as possible in the magic (starting from the LSB) that fill every column at least once in the multiplication table, with as little overlap as possible (i.e. with the least amount of carry bits). Then translate the multiplication table into a matrix and testing whether the determinant is non-zero (mod 2, i.e. odd-valued)

To the contrary, sometimes more overlap is better. For example, my generator did better by first guessing bits for a Rook on A8 by first going from LSB to MSB that modify the 8th rank occupancy bits then doing the other bits from LSB to MSB. I guess the best guessing ordering scheme would be one that maximizes the probability of a collision (which can be done a little with more overlap between the index mappings guessed) but I haven't worked out exactly what this is.

[Rein Halbersma]

And yes, the carry bit propagation is taken care of automatically. Harmless carry bits appear as lower diagonal entries in a suitable transform of the matrix A (the fast algorithms for determinants first transform A = LU with L lower diagonal and U upper diagonal).

After some more experimenting, I think I have to stand corrected: the carry propagation is not taken care of automatically with the determinant test .

With only a single bit collision (as in the example, the 6th bit in the index could be set by 2 bits in the input mask), I think I know how to modify the test so that it keeps working: binary add (with carry!) the two rows that have overlapping bits to form a new row. Remove the column with the overlapping bits from all rows. Now you have a (n-1)x(n-1) matrix. Test whether the determinant of that reduced matrix is nonzero (mod 2).

But a carry bit can propagate as to create more collisions, so that one might have to reduce this matrix recursively. In the previous example, the carry of the 6th bit, propagates to the 7th and 8th bit, so 2 more reductions have to be performed.

With multiple collisions, I haven't yet worked out a method that is simpler than brute force