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. More...

#include <algorithm>
#include <array>
#include <atomic>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <iterator>
#include <stdexcept>
#include <string>
#include <thread>
#include <utility>
#include <vector>
#include "PBeFS/astar/SlidingTile.h"
#include "PBeFS/astar/Structures.h"
#include "PBeFS/core/SearchUtils.h"
#include "ADS/succinct/PackedArray.h"
#include "ADS/succinct/RankSelect.h"

Classes
struct	PDBOptions
	the options of the construction of an AdditivePDB More...
class	TilePattern< W, H >
	a pattern of the sliding-tile puzzle and the ranking of its placements More...
struct	TilePattern< W, H >::Moves
	the cells adjacent to a cell, in the order up, left, right, down More...
class	ByteEntries
	the entries of a pattern table, one byte each: the distance itself More...
class	NibbleEntries
	the entries of a pattern table, 4 bits each: the excess over Manhattan More...
class	Mod3Entries
	the entries of a pattern table, the distance modulo 3, five in a byte More...
class	ParityBitEntries
	the entries of a pattern table, the second bit of the distance, eight in a byte More...
class	MinNibbleEntries
	the entries of a pattern table, the least excess of each group of ranks More...
class	SparseEntries
	the entries of a pattern table whose excess is nonzero, by rank More...
class	PatternTable< W, H, Enc >
	the distances of a pattern of the sliding-tile puzzle, encoded by Enc More...
class	AdditivePDB< W, H, Enc >
	the additive heuristic of disjoint pattern tables More...
class	SlidingTilePDB< W, H, Enc >
	the sliding-tile puzzle with an additive pattern database heuristic More...

Namespaces
namespace	PBeFS_di_unipi_it
	namespace for the Parallel Best-First Search library

Typedefs
using	Partition = std::vector< std::vector< int > >
	a partition of the tiles into disjoint patterns

Enumerations
enum class	BlankRule : std::uint8_t { ignored , minimized }
	how the abstraction of a pattern treats the blank More...

Functions
Partition	partition_15_7_8 (void)
	the partition 7-8 of the 15-puzzle of Korf and Felner (AIJ 2002)
Partition	partition_15_5_5_5 (void)
	the partition 5-5-5 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)
Partition	partition_15_6_6_3 (void)
	the partition 6-6-3 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)
Partition	partition_24_6_6_6_6 (void)
	the partition 6-6-6-6 of the 24-puzzle of Korf and Felner (AIJ 2002)

Detailed Description

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:

procedure BUILD-IGNORED(π)               ▷ the blank ignored
   for each r ∈ [0, N) do h[r] ← ∞          ▷ N = n! / (n − k)!
   h[rank(goal(π))] ← 0;  d ← 0
   loop
      new ← 0
      for each r with h[r] = d do        ▷ by blocks, in parallel
         p ← unrank(r)
         for each tile i of π, each cell c next to p_i, c ∉ p do
            r' ← rank(p with p_i ← c)
            if h[r'] = ∞ then          ▷ by compare-and-swap
               h[r'] ← d + 1;  new ← new + 1
      if new = 0 then return h
      d ← d + 1
 
procedure BUILD-MINIMIZED(π)             ▷ the blank minimized
   S[r, b] ← unseen for each r and each cell b ∉ unrank(r)
   S[rank(goal(π)), b] ← current for each b ∉ goal(π)
   h[r] ← ∞ for each r;  h[rank(goal(π))] ← 0;  d ← 0
   loop
      for each (r, b) with S[r, b] = current do    ▷ in parallel
         p ← unrank(r);  R ← region(p, b)  ▷ the cells b reaches
         if b ≠ min R then continue      ▷ one cell per region
         for each c ∈ R, each tile i of π with p_i next to c do
            p' ← p with p_i ← c;  r' ← rank(p')
            for each b' ∈ region(p', old p_i) do
               if S[r', b'] = unseen then S[r', b'] ← next
            if h[r'] = ∞ then h[r'] ← d + 1
      if no state is next then return h
      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 \):

function H(s)
   σ₁ ← Σ_j VALUE_j(q restricted to π_j)
   if not reflected then return σ₁
   for each tile t do q'[σ(t)] ← T(q_t)
   σ₂ ← Σ_j VALUE_j(q' restricted to π_j)
   return max(σ₁, σ₂)
function VALUE_j(p)                    ▷ r = rank(p), m = m(p)
   byte: e[r];  nibble, sparse: m + 2 e[r];  min: m + 2 e[r / c]
function CHILD-H(h(s), s, t)        ▷ mod 3, tile x of π_j moved
   δ ← (res_j(t) − res_j(s) + 1) mod 3 − 1
   return h(s) + δ
function EXACT_j(p)       ▷ mod 3: the value from the residues alone
   v ← 0;  r ← rank(p)
   while r ≠ rank(goal(π_j)) do
      r ← a neighbour r' of r with res_j(r') = (res_j(r) − 1) mod 3
      v ← v + 1
   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

Classes

Namespaces

Typedefs

Enumerations

Functions

Detailed Description