Bitboard logic: identifying 4 squares in a block

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
MOBMAT
Posts: 73
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Bitboard logic: identifying 4 squares in a block

Post by MOBMAT » Sun Aug 11, 2019 9:56 pm

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?
Vince S
Author of MOBMAT

"Reductions, extensions, and pruning, oh my!"

fabianVDW
Posts: 45
Joined: Fri Mar 15, 2019 7:46 pm
Location: Germany
Full name: Fabian von der Warth

Re: Bitboard logic: identifying 4 squares in a block

Post by fabianVDW » Sun Aug 11, 2019 10:14 pm

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
Author of FabChess: https://github.com/fabianvdW/FabChess
A UCI compliant chess engine written in Rust.
fabianvonderwarth@gmail.com

syzygy
Posts: 4442
Joined: Tue Feb 28, 2012 10:56 pm

Re: Bitboard logic: identifying 4 squares in a block

Post by syzygy » Sun Aug 11, 2019 11:12 pm

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
Posts: 4
Joined: Thu Jan 01, 2015 11:21 am

Re: Bitboard logic: identifying 4 squares in a block

Post by Philipp Bach » Sun Aug 11, 2019 11:20 pm

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
Posts: 73
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: Bitboard logic: identifying 4 squares in a block

Post by MOBMAT » Mon Aug 12, 2019 12:58 am

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.
Vince S
Author of MOBMAT

"Reductions, extensions, and pruning, oh my!"

chrisw
Posts: 1743
Joined: Tue Apr 03, 2012 2:28 pm

Re: Bitboard logic: identifying 4 squares in a block

Post by chrisw » Mon Aug 12, 2019 8:29 am

MOBMAT wrote:
Mon Aug 12, 2019 12:58 am
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
Posts: 3811
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Bitboard logic: identifying 4 squares in a block

Post by Sven » Mon Aug 12, 2019 9:23 am

MOBMAT wrote:
Sun Aug 11, 2019 9:56 pm
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).
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

chrisw
Posts: 1743
Joined: Tue Apr 03, 2012 2:28 pm

Re: Bitboard logic: identifying 4 squares in a block

Post by chrisw » Mon Aug 12, 2019 9:25 am

syzygy wrote:
Sun Aug 11, 2019 11:12 pm
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

User avatar
hgm
Posts: 23385
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Bitboard logic: identifying 4 squares in a block

Post by hgm » Tue Aug 13, 2019 3:50 am

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).

Post Reply