# Levin Tree Search with Context Models **URL:** \ **Category:** Show & Tell\ **Tags:** ai, machine-learning\ **Created:** [June 9, 2023, 1:38pm UTC](https://racket.discourse.group/t/levin-tree-search-with-context-models/1984 "2023-06-09T13:38:18Z")\ **Posts on this page:** 2\ **Page:** 1
**Author:** ![Laurent.O](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/laurent.o/32/18_2.png) [@Laurent.O](https://racket.discourse.group/u/Laurent.O)\ **Post date:** [June 9, 2023, 1:38pm UTC](https://racket.discourse.group/t/levin-tree-search-with-context-models/1984/1 "2023-06-09T13:38:18Z")
The source code for the machine learning research paper "Levin Tree Search with Context Models" (LTS+CM) to be published in IJCAI 2023 ([arXiv](https://arxiv.org/abs/2305.16945)) is now available as a package (requires **racket v8.9.0.4** at least): ```scheme raco pkg install levintreesearch_cm ``` Follow the steps of the [README](https://github.com/deepmind/levintreesearch_cm) 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 ![image](https://global.discourse-cdn.com/free1/uploads/racket/original/2X/2/2b256bd0a99acff302119cd2bd23a55a88dca3eb.png) # 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](https://github.com/deepmind/levintreesearch_cm/tree/main/lts-cm/domains) 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](https://github.com/deepmind/levintreesearch_cm/issues). # Some goodies - The package contains the new collection **jobsched** ([docs](https://docs.racket-lang.org/jobsched/index.html)) 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](https://docs.racket-lang.org/reference/futures.html) 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](https://pkgd.racket-lang.org/pkgn/package/global) (automatic command line flags). While it's not perfect, it has made my life much easier because many of the `main`s share some command-line arguments. - It contains the new collection **timev** ([docs](https://docs.racket-lang.org/timev/index.html)) which is like `time`, but with more features (on-off switch, labels). - It features a neat line search algorithm for convex functions, [delta-secant](https://github.com/deepmind/levintreesearch_cm/blob/main/lts-cm/delta-secant.rkt) — 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. ---
**Author:** ![Laurent.O](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/laurent.o/32/18_2.png) [@Laurent.O](https://racket.discourse.group/u/Laurent.O)\ **Post date:** [August 23, 2023, 2:31pm UTC](https://racket.discourse.group/t/levin-tree-search-with-context-models/1984/2 "2023-08-23T14:31:35Z")
(Almost) sorry to bump this up, but I'm just a little bit proud to say that our paper received a [Distinguished paper award](https://ijcai-23.org/distinguished-paper-awards/) at IJCAI 2023 😊 Additionally, the [convex line search draft](https://arxiv.org/abs/2307.16560) has also been uploaded.