astar/PatternDatabase.h
Header of the layer astar, in the group Domains; the same header on the site of Doxygen, its source on GitHub.
Classes
Class |
Description |
|---|---|
The options of the construction of an AdditivePDB |
|
A pattern of the sliding-tile puzzle and the ranking of its placements |
|
The entries of a pattern table, one byte each: the distance itself |
|
The entries of a pattern table, 4 bits each: the excess over Manhattan |
|
The entries of a pattern table, the distance modulo 3, five in a byte |
|
The entries of a pattern table, the second bit of the distance, eight in a byte |
|
The entries of a pattern table, the least excess of each group of ranks |
|
The entries of a pattern table whose excess is nonzero, by rank |
|
The distances of a pattern of the sliding-tile puzzle, encoded by Enc |
|
The additive heuristic of disjoint pattern tables |
|
The sliding-tile puzzle with an additive pattern database heuristic |
Functions
-
inline Partition PBeFS_di_unipi_it::partition_15_7_8(void)
the partition 7-8 of the 15-puzzle of Korf and Felner (AIJ 2002)
-
inline Partition PBeFS_di_unipi_it::partition_15_5_5_5(void)
the partition 5-5-5 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)
-
inline Partition PBeFS_di_unipi_it::partition_15_6_6_3(void)
the partition 6-6-3 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)
-
inline Partition PBeFS_di_unipi_it::partition_24_6_6_6_6(void)
the partition 6-6-6-6 of the 24-puzzle of Korf and Felner (AIJ 2002)
Types
-
using PBeFS_di_unipi_it::Partition = std::vector<std::vector<int>>
a partition of the tiles into disjoint patterns
Enumerations
-
enum class PBeFS_di_unipi_it::BlankRule : std::uint8_t
how the abstraction of a pattern treats the blank
Values:
-
enumerator ignored
the blank is not in the abstract state: consistent tables
-
enumerator minimized
the blank is, and the table keeps the least distance
-
enumerator ignored
Description of the header
Header file for the pattern databases of the sliding-tile puzzles, i.e., the heuristics that store the exact distances of an abstraction of the puzzle.
The class templates are TilePattern (a subset of the tiles and the perfect ranking of their placements), PatternTable (the distances of a pattern, built by a backward breadth-first search and stored by one of the encodings), AdditivePDB (the sum of the tables of a partition of the tiles, with the reflection about the main diagonal) and SlidingTilePDB, the domain SlidingTile with the additive heuristic in place of the Manhattan distance. The theory (the abstraction, the admissibility of the additive sum and of the reflection, the consistency, the encodings) is on the page “Pattern databases” of the documentation.
A pattern \( \pi \) is a set of \( k \) tiles of a board of \( n = W H \) cells. A placement of \( \pi \) is the vector \( p = ( p_1 , \ldots , p_k ) \) of the distinct cells of its tiles, and its rank is the lexicographic rank of the \( k \)-permutation \( p \) of \( n \) items, a bijection onto \( [ 0 , n! / ( n - k )! ) \). With the blank ignored, a move of the abstraction takes one tile of \( \pi \) to an adjacent cell that no tile of \( \pi \) holds, at cost 1; with the blank minimized, the blank is part of the abstract state, the moves of the blank into a cell that no tile of \( \pi \) holds cost 0 (they move a tile out of the pattern), and the table keeps the least distance over the cells of the blank. The table is filled by a breadth-first search backward from the goal placement, by layers, each layer scanned in parallel by blocks:
1 procedure BUILD-IGNORED(π) ▷ the blank ignored
2 for each r ∈ [0, N) do h[r] ← ∞ ▷ N = n! / (n − k)!
3 h[rank(goal(π))] ← 0; d ← 0
4 loop
5 new ← 0
6 for each r with h[r] = d do ▷ by blocks, in parallel
7 p ← unrank(r)
8 for each tile i of π, each cell c next to p_i, c ∉ p do
9 r' ← rank(p with p_i ← c)
10 if h[r'] = ∞ then ▷ by compare-and-swap
11 h[r'] ← d + 1; new ← new + 1
12 if new = 0 then return h
13 d ← d + 1
1 procedure BUILD-MINIMIZED(π) ▷ the blank minimized
2 S[r, b] ← unseen for each r and each cell b ∉ unrank(r)
3 S[rank(goal(π)), b] ← current for each b ∉ goal(π)
4 h[r] ← ∞ for each r; h[rank(goal(π))] ← 0; d ← 0
5 loop
6 for each (r, b) with S[r, b] = current do ▷ in parallel
7 p ← unrank(r); R ← region(p, b) ▷ the cells b reaches
8 if b ≠ min R then continue ▷ one cell per region
9 for each c ∈ R, each tile i of π with p_i next to c do
10 p' ← p with p_i ← c; r' ← rank(p')
11 for each b' ∈ region(p', old p_i) do
12 if S[r', b'] = unseen then S[r', b'] ← next
13 if h[r'] = ∞ then h[r'] ← d + 1
14 if no state is next then return h
15 S ← S with current → old and next → current; d ← d + 1
The states \( ( r , b ) \) of BUILD-MINIMIZED take 2 bits each, as in the two-bit breadth-first search of Korf (AAAI 2008); the cell of the blank is coded by its index among the \( n - k \) cells free of the pattern. The table of the distances takes 1 byte per placement during the construction, then it is encoded by one of the following classes, all of which store the excess \( e( p ) = ( h( p ) - m( p ) ) / 2 \) over the Manhattan distance \( m( p ) \) of the tiles of the pattern, which is a nonnegative integer since a move changes \( m \) by one unit at the cost of one unit, save ByteEntries (the distance itself) and Mod3Entries (the distance modulo 3):
ByteEntries, 8 bits per entry;
NibbleEntries, 4 bits per entry (the excess saturated at 15);
Mod3Entries, \( 8 / 5 = 1.6 \) bits per entry, five residues in a byte, after Breyer and Korf (AAAI 2010): the exact value of a successor follows from that of its parent, since the two differ by at most one;
MinNibbleEntries, 4 bits per group of \( c \) consecutive ranks ( \( c \) a power of 2), the least excess of the group, the lossy compression of Felner, Korf, Meshulam and Holte (JAIR 2007);
SparseEntries, a bit per entry that tells whether its excess is nonzero, with rank and select, and the nonzero excesses in 4 bits each.
The lookup of a state \( s \), whose tile \( t \) is in the cell \( q_t \), sums the tables of the partition \( \pi_1 , \ldots , \pi_m \) and, on a square board whose goal has the blank on the main diagonal, takes the maximum with the same sum on the reflection \( \phi( s ) \), which moves the tile \( t \) of the cell \( q_t \) to the transposed cell \( T( q_t ) \) and renames it \( \sigma( t ) \), the tile that the goal holds in the transposed goal cell of \( t \):
1 function H(s)
2 σ₁ ← Σ_j VALUE_j(q restricted to π_j)
3 if not reflected then return σ₁
4 for each tile t do q'[σ(t)] ← T(q_t)
5 σ₂ ← Σ_j VALUE_j(q' restricted to π_j)
6 return max(σ₁, σ₂)
7 function VALUE_j(p) ▷ r = rank(p), m = m(p)
8 byte: e[r]; nibble, sparse: m + 2 e[r]; min: m + 2 e[r / c]
9 function CHILD-H(h(s), s, t) ▷ mod 3, tile x of π_j moved
10 δ ← (res_j(t) − res_j(s) + 1) mod 3 − 1
11 return h(s) + δ
12 function EXACT_j(p) ▷ mod 3: the value from the residues alone
13 v ← 0; r ← rank(p)
14 while r ≠ rank(goal(π_j)) do
15 r ← a neighbour r' of r with res_j(r') = (res_j(r) − 1) mod 3
16 v ← v + 1
17 return v
A table can be saved to a file and loaded back (a versioned header, the pattern, the goal, the encoding and a checksum of the whole file), and a cache directory keeps the tables built, so that the large ones (those of the 24-puzzle take minutes) are built once.
- Author
Donato Meoli
Dipartimento di Informatica
Università di Pisa
- Copyright
© by Donato Meoli