libpolicyts

A C++23 library for policy tree search algorithms and auxiliary utilities.
The design goal is to make it easy to use different environments and models (single functors or complex neural networks) for each implemented algorithm.

Usage implementations of training and testing neural policies/heuristics for these algorithms are in the companion project policyts, which uses this library as a dependency for the algorithm implementation and neural networks.

Why implement all this in C++?

Speed matters, especially when running search over complex environment domains.
Even with neural policies/heuristics being used to query for each generated node, you can often see ~2-4x speedups by keeping the search in the C++ runtime rather than writing your search algorithms in Python.

Implemented Algorithms

The following algorithms are implemented in include/libpolicyts/algorithm/,
which support both user-defined policy/heuristics and neural network defined versions.

Best First Search: A general search algorithm with controlled weights on the g-cost and h-cost
LubyTS: Orseau, Laurent, et al. "Single-agent policy tree search with guarantees." Advances in Neural Information Processing Systems 31 (2018).
MultiTS: Orseau, Laurent, et al. "Single-agent policy tree search with guarantees." Advances in Neural Information Processing Systems 31 (2018).
LevinTS: Orseau, Laurent, et al. "Single-agent policy tree search with guarantees." Advances in Neural Information Processing Systems 31 (2018).
PHS*: Orseau, Laurent, and Levi HS Lelis. "Policy-guided heuristic search with guarantees." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 14. 2021.
$\sqrt{\mathrm{LTS}}$: Orseau, Laurent, Marcus Hutter, and Levi HS Lelis. "Exponential Speedups by Rerooting Levin Tree Search." (2024).
Bootstrap Training: Jabbari Arfaee, S.; Zilles, S.; and Holte, R. C. 2011. Learning heuristic functions for large state spaces. Artificial Intelligence 175(16): 2075–2098

Documentation

For some documentation on how to instantiate each algorithm, see the list below.
For full code examples, see examples/.

Implemented Environments

The following environment wrappers are implemented in include/libpolicyts/env/,
which support all of the concepts required for all implemented algorithms.
This can be enabled by setting the LIBPOLICYTS_BUILD_ENVIRONMENTS CMake flag.

Implemented Neural Models

The following environment wrappers are implemented in include/libpolicyts/model/,
which support all of the concepts required for all implemented algorithms.
This can be enabled by setting the LIBPOLICYTS_BUILD_TORCH CMake flag, with libtorch in your path through the environment variable LIBTORCH_ROOT
(see the section below about building)

BinaryClassifierConvNetWrapper: A ResNet style binary classifier net
HeuristicConvNetWrapper: A ResNet style heuristic net
PolicyConvNetWrapper: A ResNet style policy net
TwoHeadedConvNetWrapper: A ResNet style two headed policy + heuristic net

Auxiliary Utilities

Neural Network policy and heuristic functions through libtorch which are compatible with all implemented algorithms, which can be found in include/libpolicyts/model/
Training and Testing bootstrap functions which include threaded runners with neural network support
A tree viewer GUI using ImGui, which supports the included algorithms letting you step through to incrementally build the tree, view details for each node including the
image of the underlying state if supported, and can create GIFs of the state images along paths of the tree.

CMake Flags

The following CMake flags are supported:

LIBPOLICYTS_BUILD_ENVIRONMENTS: Set to ON to build the environment wrappers
LIBPOLICYTS_BUILD_EXAMPLES: Set to ON to build the examples (implicitly enables LIBPOLICYTS_BUILD_ENVIRONMENTS)
LIBPOLICYTS_BUILD_TORCH: Set to ON to build neural models backed my libtorch

Examples

Simple examples using both custom and libtorch neural moddesl are given in examples/.
policyts: Training and testing usage of algorithms and models in this library.

Include to Your Project: CMake

VCPKG

libpolicyts is not part of the official registry for vcpkg,
but is supported in my personal registry here.
This is by far the easier way to use this library as it will pull in dependencies, and is really the only documented way.
To add tuero/vcpkg-registry as a git registry to your vcpkg project:

"registries": [
...
{
    "kind": "git",
    "repository": "https://github.com/tuero/vcpkg-registry",
    "reference": "master",
    "baseline": "<COMMIT_SHA>",
    "packages": ["libpolicyts", "boulderdash", "craftworld", "sokoban", "tsp"]
}
]
...

where <COMMIT_SHA> is the 40-character git commit sha in the registry's repository (you can find
this by clicking on the latest commit here and looking
at the URL.

To enable the Libtorch utilities, you can use the torch feature option when adding the library to vcpkg.
To enable the provided environment wrappers, you can use the environment feature option when adding the library to vcpkg.

vcpkg add port libpolicyts
vcpkg add port libpolicyts[torch,environment]

Note that torch will look for the libtorch project in the environment variable LIBTORCH_ROOT, which is not part of the included dependencies.
The easiest way to get libtorch is through the python package.
First, create a virtual environment and install pytorch:

conda create -n <MY_ENV> python=3.12
conda activate <MY_ENV>
pip3 install torch torchvision

Then set the LIBTORCH_ROOT environment variable:

export LIBTORCH_ROOT=`python3 -c 'import torch;print(torch.utils.cmake_prefix_path)'`

Then in your project cmake:

cmake_minimum_required(VERSION 3.25)
project(my_project LANGUAGES CXX)

find_package(libpolicyts CONFIG REQUIRED)
add_executable(main main.cpp)
target_link_libraries(main PRIVATE libpolicyts::libpolicyts)

Important

If you have pytorch installed in multiple virtual environments, you may get a configure error under the following scenario:
You configured this dependency through vcpkg with LIBTORCH_ROOT pointing to one virtual environment,
and then you trying to configure this dependency through vcpkg with LIBTORCH_ROOT pointing to another virtual environment.

You can use the triplet in the vcpkg-registry (or in cmake/triplets) which will include LIBTORCH_ROOT in the dependency ABI.

If you still somehow see a CMake warning about an RPATH cycle involving libtorch/libc10
(often caused by vcpkg reusing an older cached build of a dependency and you aren't using the vcpkg registry triplet),
delete the build folder, and request to not reuse cached artifacts when configuring:
VCPKG_BINARY_SOURCES=clear cmake --preset=debug-linux

Building Examples

The CMakePrests.json defines build options for the examples and libtorch neural models.
You will first need to set the following environment variables for your CC, CC, and FC compiler.
You will also need to set LIBTORCH_ROOT for the libtorch path.
The easiest way for this is to install as a python package, then locate.

For example:

export CC=gcc-15.2
export CXX=g++-15.2
export FC=gfortrain-15.2
export LIBTORCH_ROOT=`python3 -c 'import torch;print(torch.utils.cmake_prefix_path)'`

Using the supplied CMakePresets.json:

cmake --preset=release-linux
cmake --build --preset=release-linux -- -j8
# OSX may not have good support
# cmake --preset=release-osx
# cmake --build --preset=release-osx -- -j8

tuero/libpolicyts