25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Fill Algorithms''' FILE:EschersPlaneFillingII.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Fill Algorithms'''
[[FILE:EschersPlaneFillingII.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/recogn-bmp/LW422.jpg|[[Arts#Escher|M. C. Escher]], Plane Filling II, 1957 <ref>[http://www.mcescher.com/Gallery/gallery-recogn.htm Picture gallery "Recognition and Success 1955 - 1972" ] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]
'''Fill algorithms''' perform the [[General Setwise Operations#Union|union]] of a set with their consecutive [[Direction|direction-wise]] [[General Setwise Operations#ShiftingBitboards|shifts]]. The shifted intermediate sets are likely [[General Setwise Operations#Intersection|intersected]] with some mask to avoid board wraps of certain directions, and/or also to consider the [[Occupancy|occupancy]] or any reasonable taboo set (i.e. [[Pawn Attacks (Bitboards)|pawn attacks]]) as flood stopping obstruction.
For the non sliding pieces, [[Pawn|pawn]], [[Knight|knight]] and [[King|king]], one fill cycle covers all potential [[Moves|moves]] in one certain direction, or even all moves in different directions. However, for the sliding pieces, [[Bishop|bishop]], [[Rook|rook]] and [[Queen|queen]], one fill cycle covers a direction-wise move step for a union set of attacked squares reachable in one move. Often, the up to seven direction wise fill cycles may be performed in three [[Parallel Prefix Algorithms|parallel prefix steps]].
Applications of fill algorithms are related to all kinds of [[Pawn Pattern and Properties|pawn properties]], [[Mobility#ProgressiveMobility|progressive mobility]] and [[All Shortest Paths|path finding]] algorithms, f.i. to find so called [[Trajectory|Trajectories]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref> <ref>[[Boris Stilman]] ('''2000'''). ''Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series)''. [http://www.amazon.com/Linguistic-Geometry-Construction-Operations-Interfaces/dp/0792377389/ref=sr_1_1?ie=UTF8&s=books&qid=1257674191&sr=1-1 amazon.com]</ref> .
=Pawn=
Pawn fills are performed by north- or south [[General Setwise Operations#OneStepOnly|steps]], for span determination on the otherwise empty board. If it is about to consider obstructions, the north- or south [[Dumb7Fill#OccludedFill|Dumb7-]] or [[Kogge-Stone Algorithm#OccludedFill|Kogge-Stone occluded fill]] might be applied.
* [[Pawn Fills]]
* [[Pawn Spans]]
* [[Attack Spans]]
* [[Dumb7Fill#OccludedFill|Dumb7Fill]]
* [[Kogge-Stone Algorithm#OccludedFill|Kogge-Stone Algorithm]]
=Knight=
* [[Knight Pattern#KnightFill|Knight Fill]]
* [[Knight-Distance]]
=King=
* [[King Pattern#FloodFillAlgorithms|Flood Fill Algorithm]]
* [[All Shortest Paths|All shortest Paths]]
* [[Corresponding Squares]]
=Sliding Pieces=
Albeit intended as direction-wise attack generators, a surrounding loop may determine target in at least N moves sets of sliding pieces as well. One may pass not only pieces as argument, but their attacks repetitively, likely with alternating disjoint directions, i.e. file- versus ranks-attacks for rooks and diagonal versus anti-diagonal attacks for bishops.
* [[Dumb7Fill]]
: [[AVX2#Dumb7Fill|AVX2 Dumb7Fill]]
* [[Kogge-Stone Algorithm]]
* [[Fill by Subtraction]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?start=0&t=25979&start=10 Re: Hyperbola Quiesscene: hardly any improvement] by [[Karlo Bala Jr.]], [[CCC]], January 14, 2009 » [[Hyperbola Quintessence]]
=External Links=
* [https://en.wikipedia.org/wiki/Flood_fill Flood-fill from Wikipedia]
: [[FILE:Recursive Flood Fill 4 (aka).gif|none|border|text-bottom]]
* [http://www.codecodex.com/wiki/index.php?title=Implementing_the_flood_fill_algorithm Implementing the flood fill algorithm] from [http://www.codecodex.com/wiki/Main_Page CodeCodex]
* [https://en.wikipedia.org/wiki/Pathfinding Pathfinding from Wikipedia]
* [https://en.wikipedia.org/wiki/Heraclitus#Panta_rhei.2C_.22everything_flows.22 Panta rhei, "everything flows" from Wikipedia]
* [[Videos#PantaRhei|Panta Rhei]] - [http://de.wikipedia.org/wiki/Panta_rhei Alles fliesst] (1973), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=f_oaz3vNNN4|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
[[FILE:EschersPlaneFillingII.jpg|border|right|thumb|link=http://www.mcescher.com/Gallery/recogn-bmp/LW422.jpg|[[Arts#Escher|M. C. Escher]], Plane Filling II, 1957 <ref>[http://www.mcescher.com/Gallery/gallery-recogn.htm Picture gallery "Recognition and Success 1955 - 1972" ] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref> ]]
'''Fill algorithms''' perform the [[General Setwise Operations#Union|union]] of a set with their consecutive [[Direction|direction-wise]] [[General Setwise Operations#ShiftingBitboards|shifts]]. The shifted intermediate sets are likely [[General Setwise Operations#Intersection|intersected]] with some mask to avoid board wraps of certain directions, and/or also to consider the [[Occupancy|occupancy]] or any reasonable taboo set (i.e. [[Pawn Attacks (Bitboards)|pawn attacks]]) as flood stopping obstruction.
For the non sliding pieces, [[Pawn|pawn]], [[Knight|knight]] and [[King|king]], one fill cycle covers all potential [[Moves|moves]] in one certain direction, or even all moves in different directions. However, for the sliding pieces, [[Bishop|bishop]], [[Rook|rook]] and [[Queen|queen]], one fill cycle covers a direction-wise move step for a union set of attacked squares reachable in one move. Often, the up to seven direction wise fill cycles may be performed in three [[Parallel Prefix Algorithms|parallel prefix steps]].
Applications of fill algorithms are related to all kinds of [[Pawn Pattern and Properties|pawn properties]], [[Mobility#ProgressiveMobility|progressive mobility]] and [[All Shortest Paths|path finding]] algorithms, f.i. to find so called [[Trajectory|Trajectories]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref> <ref>[[Boris Stilman]] ('''2000'''). ''Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series)''. [http://www.amazon.com/Linguistic-Geometry-Construction-Operations-Interfaces/dp/0792377389/ref=sr_1_1?ie=UTF8&s=books&qid=1257674191&sr=1-1 amazon.com]</ref> .
=Pawn=
Pawn fills are performed by north- or south [[General Setwise Operations#OneStepOnly|steps]], for span determination on the otherwise empty board. If it is about to consider obstructions, the north- or south [[Dumb7Fill#OccludedFill|Dumb7-]] or [[Kogge-Stone Algorithm#OccludedFill|Kogge-Stone occluded fill]] might be applied.
* [[Pawn Fills]]
* [[Pawn Spans]]
* [[Attack Spans]]
* [[Dumb7Fill#OccludedFill|Dumb7Fill]]
* [[Kogge-Stone Algorithm#OccludedFill|Kogge-Stone Algorithm]]
=Knight=
* [[Knight Pattern#KnightFill|Knight Fill]]
* [[Knight-Distance]]
=King=
* [[King Pattern#FloodFillAlgorithms|Flood Fill Algorithm]]
* [[All Shortest Paths|All shortest Paths]]
* [[Corresponding Squares]]
=Sliding Pieces=
Albeit intended as direction-wise attack generators, a surrounding loop may determine target in at least N moves sets of sliding pieces as well. One may pass not only pieces as argument, but their attacks repetitively, likely with alternating disjoint directions, i.e. file- versus ranks-attacks for rooks and diagonal versus anti-diagonal attacks for bishops.
* [[Dumb7Fill]]
: [[AVX2#Dumb7Fill|AVX2 Dumb7Fill]]
* [[Kogge-Stone Algorithm]]
* [[Fill by Subtraction]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?start=0&t=25979&start=10 Re: Hyperbola Quiesscene: hardly any improvement] by [[Karlo Bala Jr.]], [[CCC]], January 14, 2009 » [[Hyperbola Quintessence]]
=External Links=
* [https://en.wikipedia.org/wiki/Flood_fill Flood-fill from Wikipedia]
: [[FILE:Recursive Flood Fill 4 (aka).gif|none|border|text-bottom]]
* [http://www.codecodex.com/wiki/index.php?title=Implementing_the_flood_fill_algorithm Implementing the flood fill algorithm] from [http://www.codecodex.com/wiki/Main_Page CodeCodex]
* [https://en.wikipedia.org/wiki/Pathfinding Pathfinding from Wikipedia]
* [https://en.wikipedia.org/wiki/Heraclitus#Panta_rhei.2C_.22everything_flows.22 Panta rhei, "everything flows" from Wikipedia]
* [[Videos#PantaRhei|Panta Rhei]] - [http://de.wikipedia.org/wiki/Panta_rhei Alles fliesst] (1973), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=f_oaz3vNNN4|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
