hgm wrote: ↑Wed Apr 08, 2020 1:35 pm
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:
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.