Magic with fixed shift

[Onno Garms]

Hello,

maybe a bit premature, but as I already anounced, I post now.

I am currently implementing fixed shift values for magic bitboards. That is, instead of looking up the shift in a table, always shift by 52 for rooks and 55 for bishops. This safes the time to look up the shift value.

Obviously this works with the normal magic multipliers, but that would needlessly blow up the attack table so the program would most likely run slower in a real world environment. The trick is to find multipliers for that the magic product always has the appropriate number of highest bits zero. If one found such multipliers for every square, the table size would not increase at all. I believe that for most squares such multipliers do exist.

First I gave up to get good collisions. E.g. I only want the multiplier to yield the same number of relevant bits in the product as there are squares in the mask. Finding multipliers with good collisions is hard, but in the end the best known multipliers according to my knowledge only safe about 10% of table size for rooks, while there are no known reductions for bishops at all.

Then I set out to compute rook multipliers for all squares a1, b1, ... This takes a little more time then expected, but the results look very promissing. I arrived at d2 now and have found the desired multipliers for 9 out of 12 squares. (OK, a1 and h1 are trivial, so 7 out of 10.) In the remaining cases (f1, a2, and c2) I still found multipliers that produce relatively small indices. That's why I believe that a fixed shift is possible without blowing up the table too much.

Multipliers so far:

Code: Select all

  0x0080102040008000, 0x0020000800100020, 0x0040100008004004, 0x0040080004004002,
  0x0040040002004001, 0x0040008200010040, 0x0040004000800100, 0x0080002040800100,
  0x0000400010200040, 0x0000100400080010, 0x0000400440080010, 0x0000200400020020


Table sizes so far:

Code: Select all

  0x1000, 0x0800, 0x0800, 0x0800,
  0x0800, 0x0a00, 0x0800, 0x1000,
  0x0a00, 0x0400, 0x0600, 0x0400


I will continue to compute multipliers and also do bishop multipliers.

Note that above only works with true 64 bit multiplication. I will try to apply Grant's 32 bit trick later, but that looks difficult, esp. for
- bishops that attack e4, f4, or g4 and
- rooks that attack g4 or h4.

[Pradu]

Obviously this works with the normal magic multipliers, but that would needlessly blow up the attack table so the program would most likely run slower in a real world environment. The trick is to find multipliers for that the magic product always has the appropriate number of highest bits zero. If one found such multipliers for every square, the table size would not increase at all. I believe that for most squares such multipliers do exist.

Nice idea. When I get the time this week, I'll try it out with my generator with constraints such that no magic should make a certain number of the top bits 0 and see how good they can get. You can immediately set certain bits to 0 in the magic:

Let Z represent the bits that must be zero in the index bits.
For each bit o in the occupancy, the bits (Z/o) must be zero in the magic.

Perhaps there's a way to extend this idea for combinations of bits in the occupancy.

In conjunction with redundant bits, this leaves us with much fewer bits to guess and perhaps another criteria to get cutoffs.

You can probably also extend this idea to find a magic to producer a smaller "biggest index".

[Onno Garms]

When I get the time this week, I'll try it out with my generator with constraints such that no magic should make a certain number of the top bits 0 and see how good they can get.

That would be nice. Calculating some magics by hand is fun, but 128 of them (plus maybe another 128 for 32 bit) are a hard piece of work.

I have written a little program that translates human readable input into magics. The problem is to find the human readable input. I do so staring at a chessboard, occupancy marked with white pawns and parts of magic product marked with black pawns.

Program:

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>

typedef unsigned long long uint64;

// ########################################################################
// Square
// ########################################################################
// ########################################################################

enum Square {none=-1};

std::istream& operator>> (std::istream& p_stream, Square& r_square)
{
  char file;
  p_stream >> file;

  char rank;
  p_stream >> rank;

  r_square = static_cast<Square>(file-'a' + 8*(rank-'1'));
  return p_stream;
}


std::ostream& operator<< (std::ostream& p_stream, Square p_square)
{
  p_stream << static_cast<char>('a' + p_square%8)
           << static_cast<char>('1' + p_square/8);
  return p_stream;
}


// ########################################################################
// ########################################################################
// ########################################################################

void write_hex (std::ostream& p_stream, uint64 p_val)
{
  char fill = p_stream.fill('0');
  p_stream << std::hex;
  p_stream << "0x" << std::setw(16) << p_val;
  p_stream << std::dec;
  p_stream.fill(fill);
}


void process (const std::string& p_line)
{
  std::istringstream str(p_line);

  // read index
  Square index = none;
  str >> index;

  // read bits
  Square source, target;
  uint64 magic = 0;
  while (str >> source >> target)
  {
    magic |= 1ull << (target - source);
  }

  // write output
  if (index<0)
  {
    std::cout << std::endl;
  }
  else
  {
    std::cout << index << " ";
    write_hex (std::cout, magic);
    std::cout << std::endl;
  }
}


int main ()
{
  std::string line;
  while (getline (std::cin, line))
    process (line);
}


Input:

Code: Select all

a1 b1a8 a2e7 a3f7 a4g7 a6h7
b1 c1h7 b3e7 b5f7 b7g7
c1 b1h7 c7e7 c6a8 c4f7 c2g7
d1 b1h7 d7e7 d6b8 d4f7 d2g7
e1 b1h7 e7e7 e6c8 e4f7 e2g7
f1 b1h7 f7d8 f5f7 f3g7 f2e7 
g1 b1h7 g2e7 g4f7 g6g7
h1 b1a8 h2e7 h3f7 h4g7 h6h7

a2 b2h7 a7g7 a5f7 a4e7
b2 c2g7 b7f7 b5e7 b4d8
c2 b2h7 c7g7 c5f7 c4a8 c3e7 
d2 b2g7 d7a8 d5e7 d3f7


Output:

Code: Select all

a1 0x0080102040008000
b1 0x0020000800100020
c1 0x0040100008004004
d1 0x0040080004004002
e1 0x0040040002004001
f1 0x0040008200010040
g1 0x0040004000800100
h1 0x0080002040800100

a2 0x0000400010200040
b2 0x0000100400080010
c2 0x0000400440080010
d2 0x0000200400020020


[Onno Garms]

Here are my bishop multipliers so far:

Code: Select all

  OG_UI64(0x0000404040404040), OG_UI64(0x0000202020202000), OG_UI64(0x0000401020200000), OG_UI64(0x0000808002000000),
  OG_UI64(0x0000440200000000), OG_UI64(0x0000220100800000), OG_UI64(0x0000808080808000), OG_UI64(0x0000808080808080),
  OG_UI64(0x0000004040404040), OG_UI64(0x0000002020202020), OG_UI64(0x0000004010202000), OG_UI64(0x0000008080020000),
  OG_UI64(0x0000004402000000), OG_UI64(0x0000002201008000), OG_UI64(0x0000008080808080), OG_UI64(0x0000004040404040),
  OG_UI64(0x0000400080808080), OG_UI64(0x0000200040404040), OG_UI64(0x0000400080808080), OG_UI64(0x0000200200801000),
  OG_UI64(0x0001040080808000), OG_UI64(0x0000080080840080),


And the table sizes:

Code: Select all

  0x040, 0x020, 0x020, 0x038, 0x03f, 0x040, 0x040, 0x080,
  0x020, 0x020, 0x020, 0x038, 0x03f, 0x040, 0x040, 0x040,
  0x020, 0x020, 0x080, 0x080, 0x0c0, 0x080


I won't have time to continue computing in the next days.

[Jeroen de Bruin]

Hi Onno

Did you manage to compute all the multipliers?

Jeroen

[Brian Richardson]

Here is one implementation (early stages) I think, albeit with longer shifts:
http://github.com/kongsian/melee64