Older Version
Newer Version
GerdIsenberg
May 27, 2016
[[toc]]
**[[Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Dumb7Fill**
**Dumb7Fill** - the obvious, straight forward [[http://en.wikipedia.org/wiki/Flood_fill|flood-fill]] approach works **set-wise** - **seven** times one fill-cycle by [[General Setwise Operations#OneStepOnly|one step only]] in one of eight [[Direction|directions]]. We rely on the [[http://en.wikipedia.org/wiki/Compass_rose|compass rose]] to identify ray-directions.
[[code]]
noWe nort noEa
+7 +8 +9
\ | /
west -1 <- 0 -> +1 east
/ | \
-9 -8 -7
soWe sout soEa
[[code]]
[[include page="MappingHint"]]
[[#OccludedFill]]
=Occluded Fill=
An [[http://www.thefreedictionary.com/occluded|occluded]] fill includes the flood generating [[Sliding Pieces|sliding pieces]], but excludes the blocker. It is base of attack fills. One additional [[General Setwise Operations#OneStepOnly|direction shift]] excludes the sliders but includes the blocker.
==Seven Fill Cycles==
The sliding pieces generate the flood. They were [[General Setwise Operations#OneStepOnly|shifted one step]] in the desired direction and [[General Setwise Operations#Intersection|intersected]] with the set of empty squares, the propagator. The flood aggregates the intersection and the cycle repeats six further times to cover the maximum [[Distance|distance]] on the [[Chessboard|chessboard]]. A blocker, not member of propagator, stops the flood in that particular ray-direction for one sliding piece. Therefor occluded fill contains the initial generator but excludes any blocker.
[[code format="cpp"]]
U64 soutOccl(U64 gen, U64 pro) {
for (int cycle = 0; cycle < 7; cycle++)
gen |= pro & (gen >> 8);
return gen;
}
[[code]]
==Fill Loop==
Alternatively one may save move-instructions by introducing an explicit flood accumulator, and to probably terminate the loop early if the flood stops:
[[code format="cpp"]]
U64 soutOccl(U64 gen, U64 pro) {
U64 flood = 0;
while (gen) {
flood |= gen;
gen = (gen >> 8) & pro;
}
return flood;
}
[[code]]
==Unrolled Loop==
To [[Avoiding Branches|avoid conditional branches]] and to schedule several directions in parallel, the "real" dumb7fill unrolls the loop:
[[code format="cpp"]]
U64 soutOccl(U64 gen, U64 pro) {
U64 flood = gen;
flood |= gen = (gen >> 8) & pro;
flood |= gen = (gen >> 8) & pro;
flood |= gen = (gen >> 8) & pro;
flood |= gen = (gen >> 8) & pro;
flood |= gen = (gen >> 8) & pro;
flood |= gen = (gen >> 8) & pro;
flood |= (gen >> 8) & pro;
return flood;
}
[[code]]
Some south fill cycles in slow motion:
[[code]]
flood = gen =
brooks|bqueen empty
1 . . . . . . . . 1 1 1 1 1 . 1
. . . 1 . . . . 1 1 . . 1 . 1 .
. . . . . . . . 1 . 1 1 1 1 . 1
. . . . . . . . 1 1 . 1 1 1 1 1
. . . . . 1 . . 1 1 1 . 1 . 1 1
. . . . . . . . 1 1 . 1 1 1 1 .
. . . . . . . . . . . 1 1 . . 1
. . . . . . . . . 1 1 . 1 1 . 1
1.fill
gen = gen >> 8 & empty => flood
. . . . . . . . . . . . . . . . 1 . . . . . . .
1 . . . . . . . 1 . . . . . . . 1 . . 1 . . . .
. . . 1 . . . . . . . 1 . . . . . . . 1 . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . 1 . .
. . . . . 1 . . . . . . . 1 . . . . . . . 1 . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
2.fill
gen = gen >> 8 & empty flood |= ...
. . . . . . . . . . . . . . . . 1 . . . . . . .
. . . . . . . . . . . . . . . . 1 . . 1 . . . .
1 . . . . . . . 1 . . . . . . . 1 . . 1 . . . .
. . . 1 . . . . . . . 1 . . . . . . . 1 . . . .
. . . . . . . . . . . . . . . . . . . . . 1 . .
. . . . . . . . . . . . . . . . . . . . . 1 . .
. . . . . 1 . . . . . . . 0 . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
3.fill
gen = gen >> 8 & empty flood |= ...
. . . . . . . . . . . . . . . . 1 . . . . . . .
. . . . . . . . . . . . . . . . 1 . . 1 . . . .
. . . . . . . . . . . . . . . . 1 . . 1 . . . .
1 . . . . . . . 1 . . . . . . . 1 . . 1 . . . .
. . . 1 . . . . . . . 0 . . . . . . . . . 1 . .
. . . . . . . . . . . . . . . . . . . . . 1 . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
...
6.fill
gen = gen >> 8 & empty flood |= ...
. . . . . . . . . . . . . . . . 1 . . . . . . .
. . . . . . . . . . . . . . . . 1 . . 1 . . . .
. . . . . . . . . . . . . . . . 1 . . 1 . . . .
. . . . . . . . . . . . . . . . 1 . . 1 . . . .
. . . . . . . . . . . . . . . . 1 . . . . 1 . .
. . . . . . . . . . . . . . . . 1 . . . . 1 . .
1 . . . . . . . 0 . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
[[code]]
The flood already stopped, the final 7th fill cycles don't change anything.
=Attack Fill=
To get attacks, one additional [[General Setwise Operations#OneStepOnly|direction shift]] of the occluded fill is necessary to exclude the rooks/queen and include the blocker:
[[code format="cpp"]]
U64 soutAttacks (U64 rooks, U64 empty) {return soutOne(soutOccl(rooks, empty));}
[[code]]
==Comparison with Kogge-Stone==
To combine the dumb7fill as attack getter, we also can take advantage of [[First Rank Attacks#TheOuterSquares|outer square]] occupancy doesn't affect the attack set. We need one fill cycle less, before the final shift. That takes 19 operations. In anticipation to [[Parallel Prefix Algorithms|parallel prefix]], a [[Kogge-Stone Algorithm|Kogge-Stone]] approach takes 14 instructions, 5 less. Kogge-Stone needs more move-instructions and a temporary register to compute generator as well as propagator, while dumb7fill uses a const propagator:
[[code format="cpp"]]
dumb7fill | Kogge-Stone Algorithm
|
U64 soutAttacks(U64 rooks, U64 empty) { | U64 soutAttacks(U64 rooks, U64 empty) {
U64 flood = rooks; | rooks |= empty & (rooks >> 8);
flood |= rooks = (rooks >> 8) & empty; | empty = empty & (empty >> 8);
flood |= rooks = (rooks >> 8) & empty; | rooks |= empty & (rooks >> 16);
flood |= rooks = (rooks >> 8) & empty; | empty = empty & (empty >> 16);
flood |= rooks = (rooks >> 8) & empty; | rooks |= empty & (rooks >> 32);
flood |= rooks = (rooks >> 8) & empty; | return rooks >> 8;
flood |= (rooks >> 8) & empty; | }
return flood >> 8; |
} |
|
in x86/64 assembly | in x86/64 assembly
; dumb7fill | ; koggeStone
; rooks rdx | ; rooks rdx
; empty rcx | ; empty rcx
|
mov rax, rdx | mov rax, rdx
| shr rax, 8
shr rdx, 8 | and rax, rcx
and rdx, rcx | or rdx, rax
or rax, rdx |
| mov rax, rcx
shr rdx, 8 | shr rax, 8
and rdx, rcx | and rcx, rax
or rax, rdx |
| mov rax, rdx
shr rdx, 8 | shr rax, 16
and rdx, rcx | and rax, rcx
or rax, rdx | or rdx, rax
|
shr rdx, 8 | mov rax, rcx
and rdx, rcx | shr rax, 16
or rax, rdx | and rcx, rax
|
shr rdx, 8 | mov rax, rdx
and rdx, rcx | shr rax, 32
or rax, rdx | and rax, rcx
| or rax, rdx
shr rdx, 8 |
and rdx, rcx | shr rax, 8
or rax, rdx |
|
shr rax, 8 |
|
1 move | 5 moves
19 operations | 14 operations
20 instructions | 19 instructions
[[code]]
Thus, dumb7fill is not that bad, specially if processing several directions in parallel, like south and north, all east and all west attacks.
==All Directions==
[[code format="cpp"]]
U64 soutAttacks(U64 rooks, U64 empty) {
U64 flood = rooks;
flood |= rooks = (rooks >> 8) & empty;
flood |= rooks = (rooks >> 8) & empty;
flood |= rooks = (rooks >> 8) & empty;
flood |= rooks = (rooks >> 8) & empty;
flood |= rooks = (rooks >> 8) & empty;
flood |= (rooks >> 8) & empty;
return flood >> 8;
}
U64 nortAttacks(U64 rooks, U64 empty) {
U64 flood = rooks;
flood |= rooks = (rooks << 8) & empty;
flood |= rooks = (rooks << 8) & empty;
flood |= rooks = (rooks << 8) & empty;
flood |= rooks = (rooks << 8) & empty;
flood |= rooks = (rooks << 8) & empty;
flood |= (rooks << 8) & empty;
return flood << 8;
}
[[code]]
Horizontal fills need to consider wraps from H-file to A-file and vice versa. Fortunately this can be combined by intersection of ~A-file or ~H-file with the propagator:
[[code format="cpp"]]
U64 eastAttacks(U64 rooks, U64 empty) {
const U64 notA = C64(0xfefefefefefefefe);
U64 flood = rooks;
empty &= notA;
flood |= rooks = (rooks << 1) & empty;
flood |= rooks = (rooks << 1) & empty;
flood |= rooks = (rooks << 1) & empty;
flood |= rooks = (rooks << 1) & empty;
flood |= rooks = (rooks << 1) & empty;
flood |= (rooks << 1) & empty;
return (flood << 1) & notA ;
}
U64 noEaAttacks(U64 bishops, U64 empty) {
const U64 notA = C64(0xfefefefefefefefe);
U64 flood = bishops;
empty &= notA;
flood |= bishops = (bishops << 9) & empty;
flood |= bishops = (bishops << 9) & empty;
flood |= bishops = (bishops << 9) & empty;
flood |= bishops = (bishops << 9) & empty;
flood |= bishops = (bishops << 9) & empty;
flood |= (bishops << 9) & empty;
return (flood << 9) & notA ;
}
U64 soEaAttacks(U64 bishops, U64 empty) {
const U64 notA = C64(0xfefefefefefefefe);
U64 flood = bishops;
empty &= notA;
flood |= bishops = (bishops >> 7) & empty;
flood |= bishops = (bishops >> 7) & empty;
flood |= bishops = (bishops >> 7) & empty;
flood |= bishops = (bishops >> 7) & empty;
flood |= bishops = (bishops >> 7) & empty;
flood |= (bishops >> 7) & empty;
return (flood >> 7) & notA ;
}
U64 westAttacks(U64 rooks, U64 empty) {
const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
U64 flood = rooks;
empty &= notH;
flood |= rooks = (rooks >> 1) & empty;
flood |= rooks = (rooks >> 1) & empty;
flood |= rooks = (rooks >> 1) & empty;
flood |= rooks = (rooks >> 1) & empty;
flood |= rooks = (rooks >> 1) & empty;
flood |= (rooks >> 1) & empty;
return (flood >> 1) & notH ;
}
U64 soWeAttacks(U64 bishops, U64 empty) {
const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
U64 flood = bishops;
empty &= notH;
flood |= bishops = (bishops >> 9) & empty;
flood |= bishops = (bishops >> 9) & empty;
flood |= bishops = (bishops >> 9) & empty;
flood |= bishops = (bishops >> 9) & empty;
flood |= bishops = (bishops >> 9) & empty;
flood |= (bishops >> 9) & empty;
return (flood >> 9) & notH ;
}
U64 noWeAttacks(U64 bishops, U64 empty) {
const U64 notH = C64(0x7f7f7f7f7f7f7f7f);
U64 flood = bishops;
empty &= notH;
flood |= bishops = (bishops << 7) & empty;
flood |= bishops = (bishops << 7) & empty;
flood |= bishops = (bishops << 7) & empty;
flood |= bishops = (bishops << 7) & empty;
flood |= bishops = (bishops << 7) & empty;
flood |= (bishops << 7) & empty;
return (flood << 7) & notH ;
}
[[code]]
[[#GeneralizedRays]]
=Generalized Rays=
Since [[General Setwise Operations#Rotate|rotate]] works like a [[General Setwise Operations#GeneralizedShift|generalized shift]] with positive or negative shift amount - since it internally applies a modulo 64 and makes -i = 64-i. We need to clear either the lower or upper bits by intersection with a mask, which might be combined with the wrap-ands for [[General Setwise Operations#OneStepOnly|one step]]. It might be applied to get attacks for both sides with a direction parameter and small lookups for shift amount and wrap-ands - instead of multiple code for eight directions. Of course generalized shift will be a bit slower due to lookups and using cl as the shift amount register.
==Loop Version==
This is the loop-version:
[[code format="cpp"]]
U64 occludedFill (U64 gen, U64 pro, int dir8) {
U64 flood = 0;
if (gen) {
int r = shift[dir8]; // {+-1,7,8,9}
pro &= avoidWrap[dir8];
do {
flood |= gen;
gen = rotateLeft(gen, r) & pro;
} while (gen);
}
return flood;
}
U64 shiftOne (U64 b, int dir8) {
int r = shift[dir8]; // {+-1,7,8,9}
return rotateLeft(b, r) & avoidWrap[dir8];
}
U64 slidingAttacks (U64 sliders, U64 empty, int dir8) {
U64 fill = occludedFill(slider, empty, dir8)
return shiftOne(fill, dir8);
}
// positve left, negative right shifts
int shift[8] = {9, 1,-7,-8,-9,-1, 7, 8};
U64 avoidWrap[8] =
{
0xfefefefefefefe00,
0xfefefefefefefefe,
0x00fefefefefefefe,
0x00ffffffffffffff,
0x007f7f7f7f7f7f7f,
0x7f7f7f7f7f7f7f7f,
0x7f7f7f7f7f7f7f00,
0xffffffffffffff00,
};
[[code]]
The avoidWrap masks by some arbitrary dir8 enumeration and shift amount:
[[code]]
6 == noWe -> +7 7 == nort -> +8 0 == noEa -> +9
0x7F7F7F7F7F7F7F00 0xFFFFFFFFFFFFFF00 0xFEFEFEFEFEFEFE00
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
. . . . . . . . . . . . . . . . . . . . . . . .
5 == west -> -1 1 == east -> +1
0x7F7F7F7F7F7F7F7F 0xFEFEFEFEFEFEFEFE
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1
4 == soWe -> -9 3 == sout -> -8 2 == soEa -> -7
0x007F7F7F7F7F7F7F 0x00FFFFFFFFFFFFFF 0x00FEFEFEFEFEFEFE
. . . . . . . . . . . . . . . . . . . . . . . .
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1
[[code]]
==Unrolled Attacks==
The generalized unrolled sliding attack getter:
[[code format="cpp"]]
U64 slidingAttacks (U64 sliders, U64 empty, int dir8) {
U64 flood = sliders;
int r = shift[dir8]; // {+-1,7,8,9}
empty &= avoidWrap[dir8];
flood |= sliders = rotateLeft(sliders , r) & empty;
flood |= sliders = rotateLeft(sliders , r) & empty;
flood |= sliders = rotateLeft(sliders , r) & empty;
flood |= sliders = rotateLeft(sliders , r) & empty;
flood |= sliders = rotateLeft(sliders , r) & empty;
flood |= = rotateLeft(sliders , r) & empty;
return rotateLeft(flood, r) & avoidWrap[dir8];
}
[[code]]
=See also=
* [[AVX2#Dumb7Fill|AVX2 Dumb7Fill]]
* [[Fill Algorithms]]
* [[Kogge-Stone Algorithm]]
* [[Pieces versus Directions]]
=External Links=
* [[http://radagast.se/othello/bitmob.c|bitboard mobility]] Copyright (c) 2003, [[Gunnar Andersson]] » [[Othello]], [[Mobility]]
* [[Videos#WeatherReport|Weather Report]] - [[http://www.weatherreportdiscography.org/weather-report-1971/|Seventh Arrow / Umbrellas, 1971]], [[http://en.wikipedia.org/wiki/YouTube|YouTube]] Video
> [[Videos#JoeZawinul|Joe Zawinul]], [[Videos#WayneShorter|Wayne Shorter]], [[Videos#MiroslavVitous|Miroslav Vitouš]], [[Videos#AlphonseMouzon|Alphonse Mouzon]], [[Videos#DomUmRomao|Dom Um Romão]]
> [[media type="custom" key="26371110"]]
=What links here?=
[[include page="Dumb7Fill" component="backlinks" limit="20" ]]
**[[Sliding Piece Attacks|Up one Level]]**