Looking for Magics, with ternary field types.

[fabianVDW]

As the title already says, I am looking for magics, with ternary field types. The relevance mask has exactly 6 bits set, but each field can have exactly one of the three types: Free, Blocked by Piece, Blocked. The resulting lookup depends on all information.

There can be at maximum 3 fields with the type Blocked yielding in total 656 valid patterns. I am currently trying to brute force 32-Bit magics, and packing the info like this:
Pretend the relevance mask is operating on a 3x3 grid, and looks like this:

Code: Select all

110
100
111

1 is a set bit, and 0 is unset. Then I do :

Code: Select all

info = blocked_by_piece & relevance_mask | (blocked & relevance_mask) << 3 // Appending another mask right behind it
index = (info * magic) >> 32 - BITS

You can safely assume there is enough space to pack the other information behind it by shifting 3 to the right, as the board has a width of 11.
For now the best I could find was with 12 Bits and an absolute lookuptablesize of 3000. I am currently bruteforcing 11 Bits with 2048 lookuptablesize, and am around 75% through with no hit. As we are close to L3 size (11.7KB), I am eager to improve on this.

Now my question: Is there maybe a better way to pack the information? I know I could switch to 64-Bit information, and really do ternary packing, but this will be inefficient at runtime, as I need to convert from gamestate data into ternary data.

[fabianVDW]

I failed to realize something very important! The output only has 64 possibilites, and until now, I didn't allow two different keys mapping to the same value, which is perfectly fine however I instantly found 8Kb tables, and I think I can get this value even lower...

[hgm]

I don't get what you are trying to do. What else can you be blocked by than by a piece? Are you considering boards with holes in them? And would the holes be any different in blocking probabilities than having an own piece there?

[fabianVDW]

I don't get what you are trying to do. What else can you be blocked by than by a piece? Are you considering boards with holes in them? And would the holes be any different in blocking probabilities than having an own piece there?

Thats right, you can be blocked by something else than a piece, there exist obstacles. I don't consider obstacles pieces, atleast not in the occupied bitboard, maybe this is where the confusion arises. For all I know, you can also consider obstacles the same as holes in the board. There are at maximum 3 obstacles.

So to conclude: There exist the occupied bitboard, which is just the union of all the piece bitboards except for obstacles, and the obstacle bitboard.

The grid is hexagonal, so there exist 6 neighbors. What I am trying to search magics for is an operation, that takes the neighboring fields of one field, and outputs a bitboard of possible destinations. The possible destinations depend on whether some neighbors are pieces, and some are obstacles, but does not depend on the type of piece or color of piece, if there is a piece and not an obstacle.
So given a field and a game_state, this is how you get all the information there is:

Code: Select all

let NEIGHBOR_MASK = get_neighbors(field)
let blocked_by_pieces = NEIGHBOR_MASK & game_state.occupied;
let blocked_by_obstacles = NEIGHBOR_MASK & game_state.obstacles
assert(game_state.occupied | game_state.obstacles == game_state.occupied ^game_state.obstacles);

In total, there are 656 valid patterns the neighbors can occur in, and 64 valid outputs. The best magics I could find require a lookup table of size 2048, which results in 8KB. I would like to improve on the absolute table size.

[hgm]

If you have to shift the masked obstacle bitboard to combine it with the occupied bitboard, you might as well multiply it. Perhaps you could do better when you used different magics for the masked obstacle and occupancy bitboards, and combine these afterwards (through + or ^ rather than |), rather than combining them first and using a single magic on the combination. That would give you far more freedom.

Since your boards seem to need only 32 bits, you could make the occupied and obstacle board sub-fields of a uint64, and use a uint64 multiplier to effectively create the sum of the products of the lower 32-bits of the multiplier with one, and the upper 32-bit with the other, in the upper half of the product. On an x64 architecture that would even require fewer instructions than merging the two bitboards and using a single magic on them.

[fabianVDW]

Since your boards seem to need only 32 bits, you could make the occupied and obstacle board sub-fields of a uint64, and use a uint64 multiplier to effectively create the sum of the products of the lower 32-bits of the multiplier with one, and the upper 32-bit with the other, in the upper half of the product. On an x64 architecture that would even require fewer instructions than merging the two bitboards and using a single magic on them.

I just tried this with 64-Bit magics, and the best I could find again was around 8KB. All in all it seems pretty weird, that 64 possibilities need that big of a lookup table. Anyway, I don't know how to sensibly reduce the search space, and random search probably isn't the fastest. For 32 Bit Magics I could just brute force them, but 64-Bit is too much.
For the moment, I am doing this

Code: Select all

        let random_u32 = rand.next_u32() & rand.next_u32();
        let random_u322 = rand.next_u32() & rand.next_u32();
        let random_u64 = (random_u32 as u64) << 32 | random_u322 as u64;
        let appended = NEIGHBOR_MASK | (NEIGHBOR_MASK<< 32);
        if (appended.wrapping_mul(random_u64) & 0xFFC0_0000).count_ones() < 8 {
            continue;
        }

[hgm]

Well, it is hard to say anything sensible about this without knowing more details. E.g. how are the relevant bits distributed over their masks, and how are the 656 neighborhood compositions grouped into 64.

Randomly trying is just taking a sample of an exhaustive search; neither method is goal directed. If you have time for exhausingly searching 2^32 magics, you probably would have time for a number of random tries in a space of 2^64 that is a multiple of that, and I don't see why the success rate per try should be different. With the 32-bit space you will run out of things to try in not too long a time, in a 64-bit space you can go on trying.

It is also not clear whether the the 8KB result applies to all board cells, or is just the worst case for a particular set of relevant bits, while most cases can do better.

And why should there at least be 8 bits set of the upper 10? You are just calculating the index that would result from a position where all neighbors are both pieces and obstacles. Apart from the fact that this should never happen, why would you care if it is (say) 0? The only important thing is that other neighborhood constellations that must result in different move patterns do not map to 0 too.

[fabianVDW]

Well, it is hard to say anything sensible about this without knowing more details. E.g. how are the relevant bits distributed over their masks, and how are the 656 neighborhood compositions grouped into 64.

Okay, I will go into more detail. The game is called Hive, if you maybe know it.

The grid is hexagonal, but we can still do a square enumeration which allows for making shifts for neighbors:

Code: Select all

Populated valid fields:
[   ,    ,    ,    ,    ,  X ,  X ,  X ,  X ,  X ,  X ]
[   ,    ,    ,    ,  X ,  X ,  X ,  X ,  X ,  X ,  X ]
[   ,    ,    ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ]
[   ,    ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ]
[   ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ]
[ X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ]
[ X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,    ]
[ X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,    ,    ]
[ X ,  X ,  X ,  X ,  X ,  X ,  X ,  X ,    ,    ,    ]
[ X ,  X ,  X ,  X ,  X ,  X ,  X ,    ,    ,    ,    ]
[ X ,  X ,  X ,  X ,  X ,  X ,    ,    ,    ,    ,    ]
  noWe                      noEa
          +11         +12
              \     /
  west    -1 <-  0  -> +1    east
              /     \
          -12         -11
  soWe                      soEa

From a top down view, the board looks like this:
---------------------------------------------
|         | X | X | X | X | X | X |         |
|       | X | X | X | X | X | X | X |       |
|     | X | X | X | X | X | X | X | X |     |
|   | X | X | X | X | X | X | X | X | X |   |
| | X | X | X | X | X | X | X | X | X | X | |
| X | X | X | X | X | X | X | X | X | X | X |
| | X | X | X | X | X | X | X | X | X | X | |
|   | X | X | X | X | X | X | X | X | X |   |
|     | X | X | X | X | X | X | X | X |     |
|       | X | X | X | X | X | X | X |       |
|         | X | X | X | X | X | X |         |
---------------------------------------------

So, given a board field(marked with X) in isolation, I will be talking about the 3x3 grid surrounding the board field in isolation, as the NEIGHBOR_MASK for this field will be in this grid. For simplicity, I assume all neighbors exist, so the NEIGHBOR_MASK will look like this:

Code: Select all

011
1X1
110

To be calculated are the "accessible neighbors", e.g. the output is fully contained in NEIGHBOR_MASK, so that the following assert would always pass

Code: Select all

let output = accessible_neighbors(field)
assert!(output & NEIGHBOR_MASK(field) == output)

This explains the 64 maximum possibilities, as the NEIGHBOR_MASK contains 6 bits. Now what are accessible neighbors? It is quite simple actually, two rules need to pass: 1. Moving the piece of the field to an accessible neighbor must not result in having to physically move other pieces or obstacles, e.g.

Code: Select all

For this neighboring constellation with neighboring beeing occupied | obstacle:
010
0X1
000

accessible neighbors are:
000
100
110

Until now, it does not matter if the neighbors contains obstacles or pieces.
2. The piece must move along the edge of the piece swarm.
Okay, so all pieces are always in a swarm. The piece must move along the edge of the swarm. This can be checked as follows: For each possible neighborfield, there are two neighborfields neighboring the neighborfield which also neighbor yourself. Atleast one of those needs to contain a piece(not an obstacle!). If two of those contain a piece, rule 1 does not pass!.

Valid patterns:
I just brute forced the valid patterns like this:

Code: Select all

pub fn generate_patterns(){
    for i in 0..729{
        let (occ, obs) = put_along_mask(i as u32, NEIGHBOR_MASK as u32);
        if obs.count_ones() > 3 {
            continue;
        }
        add_to_patterns(occ,obs);
}
pub fn put_along_mask(mut value: u32, mut mask: u32) -> (u32, u32) {
    let (mut occ, mut obs) = (0u32, 0u32);
    while value > 0 && mask > 0 {
        let type_of_value = value % 3;
        let mask_bit = mask.trailing_zeros();
        if type_of_value == 1 {
            occ |= 1u32 << mask_bit;
        } else if type_of_value == 2 {
            obs |= 1u32 << mask_bit;
        }
        mask ^= 1u32 << mask_bit;
        value /= 3;
    }
    (occ, obs)
}

I hope it is not too bad for you to read this Rust code

It is also not clear whether the the 8KB result applies to all board cells, or is just the worst case for a particular set of relevant bits, while most cases can do better.

I think I am only interested in magic values for one square, which represents the worst case, and all other cases can be calculated from this worst case with a few shifts and ands. I could try generating magic values for other squares, but I am not sure it would even be faster. My idea was that if magic table is small enough to fit into L3 all the time, this will be much more worth than saving those few shifts for other cases. There are other fields with 6 neighbors, and fields with less neighbors. If a neighbor is missing, it can be assumed that the field is blocked by an obstacle ( which would raise the maximum obstacle value).

And why should there at least be 8 bits set of the upper 10? You are just calculating the index that would result from a position where all neighbors are both pieces and obstacles. Apart from the fact that this should never happen, why would you care if it is (say) 0? The only important thing is that other neighborhood constellations that must result in different move patterns do not map to 0 too.

You may be right, I just saw this somewhere on chessprogrammingwiki or atleast in my engine, and just stupidly copied it in here, I don't actually know if it helps.

[fabianVDW]

I just found out, that when I say L3, I actually mean L1 cache, and that the table is already small enough to fit into L1, although I am obviously still interested in making it as small as possible.

[fabianVDW]

Using 64-Bit Magics,I still couldn't get better than 8KB. I think either a) I am search through the search space very inefficiently or b) the problem is just a very hard one, with the way the information is packed. It's definitely a mixture of both, and it's very hard to find a good way to pack the information without runtime loss, as the current packing requires one shift..