Bitboard logic: identifying 4 squares in a block

[MOBMAT]

I want to be able to identify a pattern of 4 pieces forming a square anywhere on a board, such as:

Code: Select all

- - - - - - - 
- x x - - - - 
- x x - - - - 
- - - - - - - 
- - - - - - - 

The board could be any size. The pattern can occur anywhere on the board, so, depending on the size of the board, there are a lot of possible occurrences of the pattern.

one way to find the pattern is to create an array of every possible pattern and then loop through them, comparing them against the board. This is very inefficient.

I haven't been able to locate any code that can apply this test across an entire bitboard. Does anyone have a solution they would like to share?

[fabianVDW]

Looping through the pieces is more efficient than trying every possible spot of the pattern. Hard to think of a better solution from the top of my head, too

[syzygy]

The board can be any size? What kind of bitboards are those? Can the code not even assume a particular board size?

So I'm not really sure what you mean, but I'll just focus on chess.

Shouldn't this work (in SF terminology):

Code: Select all

bool has_square(bitboard b)
{
  b &= shift<EAST>(b);
  b &= shift<NORTH>(b);
  return (bool)b;
}

Or if you want to know where they are, just return b as a bitboard.

[Philipp Bach]

I am not sure I understand the question, is this what you want:
(LEFT & DOWN are 1 & 8 in case of a 8x8 board, I assume origin is in the lower left corner)

Code: Select all

leftSides = pieces & (pieces >> LEFT)
lowerLeftCorners = leftSides & (leftSides >> DOWN)

lowerLeftCorners will then contain all lower left corners of the found squares which you can iterate over.
You can easily get back to a full square from a single corner by multiplying the corner by the square located in the lower left corner

[MOBMAT]

Let me elaborate.

Code: Select all

- - - - - - - 
- x x - - - - 
- x x - - - - 
- - - - - - - 
- - - - - - -

The diagram above shows 4 'on' bits adjacent to each other in the shape of a square. There might be additional bits "touching" these four, the test is, is there ANY 4 bits in this pattern.
A square of four can occur anywhere on the board. Only need a boolean (t/f), I don't need to know where it is.

When I said the board can be of any size, I meant that it wasn't limited to being on a chess (8x8) board, it might be on a 7x7 or 6x6, etc.

The proposed idea of scanning the board for pieces should be faster than testing the entire board against all possible pattern locations, depending on how many pieces there are. It appears that this piece-centric approach would require four tests (max) to know if the piece is part of a square. I'll try that out, thanks.

[chrisw]

Let me elaborate.

Code: Select all

- - - - - - - 
- x x - - - - 
- x x - - - - 
- - - - - - - 
- - - - - - -

The diagram above shows 4 'on' bits adjacent to each other in the shape of a square. There might be additional bits "touching" these four, the test is, is there ANY 4 bits in this pattern.

Mobmat wrote earlier post: ”one way to find the pattern is to create an array of every possible pattern and then loop through them, comparing them against the board. This is very inefficient.”

Compares against the board implies those would be the only bits set.
Compares against the board and-ed with the pattern would imply other bits set are possible.

A square of four can occur anywhere on the board. Only need a boolean (t/f), I don't need to know where it is.

SYZYGY already answered this completely one and a half hours before this latest post of yours, and included the code to do it.

When I said the board can be of any size, I meant that it wasn't limited to being on a chess (8x8) board, it might be on a 7x7 or 6x6, etc.

The proposed idea of scanning the board for pieces should be faster than testing the entire board against all possible pattern locations, depending on how many pieces there are. It appears that this piece-centric approach would require four tests (max) to know if the piece is part of a square. I'll try that out, thanks.

[Sven]

I want to be able to identify a pattern of 4 pieces forming a square anywhere on a board, such as:

Code: Select all

- - - - - - - 
- x x - - - - 
- x x - - - - 
- - - - - - - 
- - - - - - - 

The board could be any size. The pattern can occur anywhere on the board, so, depending on the size of the board, there are a lot of possible occurrences of the pattern.

one way to find the pattern is to create an array of every possible pattern and then loop through them, comparing them against the board. This is very inefficient.

I haven't been able to locate any code that can apply this test across an entire bitboard. Does anyone have a solution they would like to share?

The requirement is not yet clear to me. Are you talking about four pieces of possibly different types and colors? That would make sense but then the scope is not to find four set bits in one bitboard (which is a trivial task with two nested loops) but only slightly more complex (and does not even require loops but more preparation). Example: you want to find out whether the current board has any occurrence of
- a white pawn
- blocked by a black pawn ("north")
- with another black pawn to the right of the white pawn ("east")
- and a white knight north-east to the white pawn.

To solve a problem like in this example I would
- define XSize and YSize as board dimensions,
- provide code that returns four bitboards bb, bbNorth, bbEast, bbNorthEast derived from the four piece types and colors given in the pattern,
- prepare those four bitboards such that subsequent shifting will not include "wrong" bits (e.g. mask out file A and/or rank 1 appropriately),
- combine those four prepared bitboards into one by

Code: Select all

bb & (bbNorth >> YSize) & (bbEast >> 1) & (bbNorthEast >> (YSize+1))

- and then test whether the resulting bitboard is non-zero (if it is then you have a match).

[chrisw]

The board can be any size? What kind of bitboards are those? Can the code not even assume a particular board size?

So I'm not really sure what you mean, but I'll just focus on chess.

Shouldn't this work (in SF terminology):

Code: Select all

bool has_square(bitboard b)
{
  b &= shift<EAST>(b);
  b &= shift<NORTH>(b);
  return (bool)b;
}

Or if you want to know where they are, just return b as a bitboard.

The shift EAST requires a wrap-round mask. Probably it’s built in for the SF coding already.

To generate a bitboard of all the squares, using bitboard b from sygzgy code above:

b |= shift_right(b)) # NB edge masking
b |= shift_south(b))

To sequentially generate bitboards for each square:
while b
a = lsbit(b)
sq_bb = gen_bitboard(a) # as above
b ^= a

[hgm]

For a pattern of all 1 bits the shift & AND solution given by Chris should work fine. For arbitrary patterns:

If the board were really small, you could use the entire board as an index in a lookup table that indicates whetre the pattern is there or not. If the board is too large for that, you could split it in a number of areas that are small enough. To see a 2x2 pattern they shouldoverlap by 1 rank or file. E.g. a 7x7 board could be split into four 4x4 areas. Each 4x4 area would give you a 16-bit index to be used in the same lookup table. You can use conventional magic-bitboard techniques to mask out the 4x4 area and collect the relevant bits into an index. You then only have to do 4 lookups instead of 36 (which would be the number of different locations a 2x2 patter can appear on a 7x7 board).