The source code for the machine learning research paper "Levin Tree Search with Context Models" (LTS+CM) to be published in IJCAI 2023 (arXiv) is now available as a package (requires racket v8.9.0.4 at least):
raco pkg install levintreesearch_cm
Follow the steps of the README for a Quick Start and further instructions.
What is it?
Levin Tree Search (LTS) is a tree/graph search algorithm (like A* or Best-First Search) that has been developed through a few research papers over the past 6 years. While A* uses a distance-to-the-goal heuristic to guide the search, LTS uses a policy, that is, at each step it is given probabilities for the actions --- the probabilities are used to make a cost function, there is no randomness.
The policy usually has parameters that can be optimized (learned) to make the search more efficient, by using information gathered on previously solved problems. While neural networks have been used in the past with LTS, in this new paper we explore more information-theory-based parameterized models — the so-called context models — which have better theoretical properties.
For the paper, we learn a policy for the following domains:
———— Sokoban ————————— Sliding Tile Puzzle ———— The Witness ——————— Rubik's cube
What it's not
This is not a library (unfortunately). It's a research prototype.
Currently it does not contain documentation about how to use it for your own domains. However, if you look at the examples in the domains folder it should be relatively easy to figure out what to do. Don't hesitate to reach out via issues/email/discourse/slack if you need help — I would be more than happy to help.
Note that backward compatibility is not guaranteed for anything that's not documented.
That said, if you see ways to improve it, do let me know.
Some goodies
-
The package contains the new collection jobsched (docs) which is a server-worker library for running multiple instances of Racket in parallel to send jobs and receive results. It does not have the limitations of racket/place on the number of cores.
-
It features an extensive use of futures which are used during optimization. It took some work to use them properly, but now they can run efficiently on 64 cores.
-
It features an extensive use of global (automatic command line flags). While it's not perfect, it has made my life much easier because many of the
mains share some command-line arguments. -
It contains the new collection timev (docs) which is like
time, but with more features (on-off switch, labels). -
It features a neat line search algorithm for convex functions, delta-secant — arxiv paper coming soon.
-
The levels of the domains are playable by humans, but the feature is a little hidden.
Feedback welcome!
Finally, a huge thank you to the wonderful Racket community for its reactivity and its help.
