SlidingTile
Declared in astar/SlidingTile.h; the same class on the site of Doxygen.
-
template<int W, int H>
class SlidingTile the sliding-tile puzzle on a board of at most 25 cells
The board has \( W \times H \) cells, with \( W H \leq 25 \). A state is packed into one integer, the field of \( b \) bits of the cell \( i = r W + k \) holding the tile in row \( r \) and column \( k \) (0 being the blank): a word of 64 bits with \( b = 4 \) up to 16 cells, as for the 15-puzzle, and a Word128 with \( b = 5 \) above, as for the 24-puzzle. The integer is at the same time the state, its equality test and the key of its hash, as advocated by Burns et al. (SoCS 2012). The blank is found as the zero field of the integer with a few bitwise operations, and the Manhattan distance is updated incrementally from a table of the change caused by each move of each tile.
The feature i of Zobrist hashing is “tile t is in cell c”, with \( i = t W H + c \), for the tiles \( t = 1 , \ldots , W H - 1 \). The abstract feature of Abstract Zobrist hashing keeps of the cell only whether it lies in the upper or in the lower half of the board, which is the hand-crafted projection of Jinnai and Fukunaga (JAIR 2017, fig. 8b) for the 15-puzzle. The state abstraction of AHDA* looks at the cells of tiles 1, 2 and 3, and the nblocks of PBNF at those of the blank and of tiles 1 and 2 [see Burns et al., JAIR 2010]. The perfect hash, the rank of the permutation, is given only up to 20 cells, since 21! exceeds \( 2^{64} \).
Subclassed by SlidingTilePDB< W, H, Enc >
Public Types
-
using cost_type = int
the cost type
Public Functions
-
inline explicit SlidingTile(const board_type &start, const board_type &goal = korf_goal())
constructor, taking the start and the goal boards
Constructs the puzzle of going from
starttogoal; throws std::invalid_argument if either is not a permutation of 0 , … , W H - 1, or if the goal cannot be reached from the start.
-
inline state_type initial_state(void) const noexcept
the start board
-
inline bool is_goal(state_type s) const noexcept
true if s is the goal board
-
inline std::uint64_t hash(state_type s) const noexcept
the hash of a board: its packed integer, mixed
-
inline cost_type heuristic(state_type s) const noexcept
the Manhattan distance of s from the goal
-
template<class F>
inline void for_each_successor(state_type s, cost_type h, F &&f) const calls f( t , 1 , h( t ) ) for each successor t of s
Calls
f( t , 1 , h( t ) )for each successor t ofs, h( t ) being computed fromh= h( s ) by the change of the moved tile.
-
template<class F>
inline void for_each_successor(state_type s, cost_type h, std::uint8_t op, F &&f) const as above, but without the successor that op, the cell where the blank was, leads back to; the operator of a successor is the cell of the blank in s
-
template<class F>
inline void for_each_feature(state_type s, F &&f) const calls f( t W H + c ) for each tile t != 0 in each cell c of s
-
template<class F>
inline void for_each_feature_change(state_type s, state_type t, F &&f) const calls f( k W H + c ) and f( k W H + b ) for the tile k that the move from s to its successor t slides from the cell c to the cell b of the blank of s
The fields of \( s \oplus t \) hold k in the cells b and c and 0 elsewhere, so that the two cells are found without the blanks.
-
inline std::uint64_t abstract_state(state_type s) const noexcept
the abstract state of AHDA*: the cells of tiles 1, 2 and 3
-
inline std::size_t nblock(state_type s) const noexcept
the nblock of PBNF: the cells of the blank and of tiles 1 and 2
-
template<class F>
inline void for_each_nblock_successor(std::size_t b, F &&f) const calls f( b’ ) for each abstract successor b’ of the nblock b
-
inline cost_type pairwise_heuristic(state_type s, state_type t) const noexcept
the heuristic of PA*SE: the sum of the displacements of the tiles
-
inline std::uint64_t perfect_hash(state_type s) const noexcept
the lexicographic rank of the permutation of the cells of the tiles
It is the perfect hash of Korf and Schultze (2005), by which Burns et al. (JAIR 2010) distributed the states of HDA*: as Jinnai and Fukunaga (JAIR 2017) show, modulo the number of processors it depends on very few tiles, and it is kept as a poor work distribution to compare to.
Public Static Functions
-
static inline board_type korf_goal(void)
the goal of Korf (1985): the blank in the first cell, then 1 , 2 , …
-
static inline constexpr std::size_t num_features(void) noexcept
the number of features: one per pair ( tile , cell )
-
static inline constexpr std::size_t num_abstract_features(void) noexcept
the number of abstract features: one per pair ( tile , half board )
-
static inline constexpr std::size_t abstract_feature(std::size_t i) noexcept
the abstract feature of a feature: the tile and the half of its cell
-
static inline constexpr std::size_t num_nblocks(void) noexcept
the number of nblocks: one per triple of cells, not all of them used
-
static inline int tile(state_type s, int c) noexcept
the tile in the cell c of s
-
static inline int blank(state_type s) noexcept
the cell of the blank in s, i.e., of the zero field of the integer
The bits of each field are or-ed into its lowest one, which is then 0 only in the field of the blank.
-
static inline state_type pack(const board_type &b) noexcept
packs a board into a word
-
static inline board_type unpack(state_type s) noexcept
unpacks a word into a board
-
static inline board_type parse(const std::string &text)
reads a board: W H numbers, the tiles cell by cell, 0 for the blank
-
static inline void print(std::ostream &os, state_type s)
prints a board, one row per line
-
using cost_type = int