Fill Algorithms

From Chessprogramming wiki
Jump to: navigation, search

Home * Board Representation * Bitboards * Fill Algorithms

M. C. Escher, Plane Filling II, 1957 [1]

Fill algorithms perform the union of a set with their consecutive direction-wise shifts. The shifted intermediate sets are likely intersected with some mask to avoid board wraps of certain directions, and/or also to consider the occupancy or any reasonable taboo set (i.e. pawn attacks) as flood stopping obstruction.

For the non sliding pieces, pawn, knight and king, one fill cycle covers all potential moves in one certain direction, or even all moves in different directions. However, for the sliding pieces, bishop, rook and 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 steps.

Applications of fill algorithms are related to all kinds of pawn properties, progressive mobility and path finding algorithms, f.i. to find so called Trajectories [2] [3] .

Pawn

Pawn fills are performed by north- or south steps, for span determination on the otherwise empty board. If it is about to consider obstructions, the north- or south Dumb7- or Kogge-Stone occluded fill might be applied.

Knight

King

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.

AVX2 Dumb7Fill

Forum Posts

External Links

Recursive Flood Fill 4 (aka).gif

References

  1. Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website
  2. Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
  3. Boris Stilman (2000). Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series). amazon.com

Up one Level