Bitboard for a non-chess game

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
tysen2k
Posts: 4
Joined: Wed Sep 09, 2015 10:19 pm

Bitboard for a non-chess game

Post by tysen2k » Tue Jun 05, 2018 6:25 pm

I’m using bitboards for a certain game that has some squares occupied and others that are empty. I’m trying to come up with an efficient way of identifying groups of exactly 1 or 2 empty squares that are completely surrounded by occupied squares (or the edge) – orthogonal directions only. So if the bitboard that identifies occupied squares is

00000000
00011110
00100101
00011011
00001010
00001010
00111010
00100110

Then I’d like to be able to get a function that returns

00000000
00000000
00011010
00000000
00000000
00000000
00000000
00011000

It’s easy to create a function that identifies the groups of size 1 (empty & occupied_shift_down & occupied_shift up & occupied_shift_left & occupied_shift_right, where the shift functions also include the border), but I’m struggling to come up with one that will find groups of size 2. Any suggestions?

User avatar
Evert
Posts: 2900
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Bitboard for a non-chess game

Post by Evert » Tue Jun 05, 2018 8:46 pm

You should be able to use the same logic as for pawn duo's and hanging pawns (there's a breakdown of the logic on CPW). Essentially you have to find squares that border exactly one empty square, which can be done by testing for squares that have an empty square to the West (say), but not in any of the other directions. The union of those squares with those that have a free square to the East gives you horizontal pairs, and you can do the same to find the vertical pairs.
This will be four times as expensive as the single test, because you need to test all four directions. I don't think you can avoid that.

Alternatively, you can apply your original test four times, but with one of the directions shifted over two squares. You then need to AND with the bitmask of empty squares to avoid false positives for situations like

Code: Select all

0110
1101
0110
Which would give

Code: Select all

0000
0110
0000

Gerd Isenberg
Posts: 2106
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Bitboard for a non-chess game

Post by Gerd Isenberg » Tue Jun 05, 2018 9:02 pm

The naive disjunctiv normal form approach would be, with some subexpressions to optimize

Code: Select all

oneEmptyNeighbor =
  ( occupied_shift_left & ~occupied_shift_down & ~occupied_shift_right & ~occupied_shift_up)
| (~occupied_shift_left &  occupied_shift_down & ~occupied_shift_right & ~occupied_shift_up)
| (~occupied_shift_left & ~occupied_shift_down &  occupied_shift_right & ~occupied_shift_up)
| (~occupied_shift_left & ~occupied_shift_down & ~occupied_shift_right &  occupied_shift_up)
;
group2 = oneEmptyNeighbor & ~occupied;
see also
https://chessprogramming.wikispaces.com ... igitCounts

AlvaroBegue
Posts: 892
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York

Re: Bitboard for a non-chess game

Post by AlvaroBegue » Wed Jun 06, 2018 2:44 am

I would do something like this:

Code: Select all

#include <iostream>

typedef unsigned long long u64;

void print_bb(u64 x) {
  for (int row = 7; row >= 0; row--) {
    for (int col = 7; col >= 0; col--)
      std::cout << ((x >> (row*8+col)) & 1);
    std::cout << '\n';
  }
    
}

inline u64 N(u64 x) {
  return x << 8;
}

inline u64 W(u64 x) {
  return (x & 0xfefefefefefefefeull) >> 1;
}

inline u64 S(u64 x) {
  return x >> 8;
}

inline u64 E(u64 x) {
  return (x & 0x7f7f7f7f7f7f7f7full) << 1;
}

u64 small_gaps(u64 x) {
  u64 z = ~x;
  u64 isolates   = ~S(z) & ~N(z) & ~E(z) & ~W(z);
  u64 west_only  = ~S(z) & ~N(z) & ~E(z) &  W(z);
  u64 east_only  = ~S(z) & ~N(z) &  E(z) & ~W(z);
  u64 north_only = ~S(z) &  N(z) & ~E(z) & ~W(z);
  u64 south_only =  S(z) & ~N(z) & ~E(z) & ~W(z);

  u64 west_ends = west_only & W(east_only);
  u64 north_ends = north_only & N(south_only);
  
  return z & (west_ends | E(west_ends) | north_ends | S(north_ends) | isolates);
}

int main() {
  print_bb(small_gaps(0b0000000000011110001001010001101100001010000010100011101000100110ull));
}


tysen2k
Posts: 4
Joined: Wed Sep 09, 2015 10:19 pm

Re: Bitboard for a non-chess game

Post by tysen2k » Wed Jun 06, 2018 10:34 pm

Thanks! These are good suggestions.

Post Reply