UCT (Upper Confidence Bound for Trees) ist ein Verfahren der Monte-Carlo-Baumsuche, das bei jedem Schritt entscheidet, welchem Ast eines Suchbaums die Suche als Nächstes folgt. UCT überträgt dafür das Prinzip „Upper Confidence Bound“ (UCB) auf Suchbäume und gleicht zwei Ziele aus: Erkundung (Exploration) und Ausnutzung (Exploitation).
Einordnung: Monte-Carlo-Baumsuche
Die Monte-Carlo-Baumsuche (MCTS) ist ein Suchalgorithmus. Sie nähert sich einer Lösung über viele zufällige Verzweigungen. Man setzt sie ein, wenn eine genaue Berechnung unmöglich oder sehr aufwendig ist, zum Beispiel beim verstärkenden Lernen.
So wählt UCT einen Ast
An jedem Knoten wählt UCT zuerst Aktionen, die dort noch nie gewählt wurden. Unter diesen entscheidet der Zufall. Sind alle Aktionen erprobt, berechnet UCT für jede Aktion einen Wert aus zwei Teilen und wählt die Aktion mit dem höchsten Wert.
Der erste Teil ist der bisher gemessene Durchschnittsertrag der Aktion. Er bevorzugt Äste, die sich bewährt haben. Der zweite Teil ist ein Erkundungsbonus. Dieser Bonus wächst, je öfter der übergeordnete Knoten besucht wurde, ohne dass der betreffende Ast an die Reihe kam. Dadurch bekommt ein selten besuchter Ast gelegentlich eine Chance. Ein Explorationsparameter gewichtet den Erkundungsbonus und steuert so, wie stark die Suche neue Äste ausprobiert.
Warum der Ausgleich zählt
Ohne diesen Ausgleich drohen zwei Fehler. Ein Verfahren, das stark ausnutzt, wählt oft dieselbe Aktion. Es legt sich dann zu früh auf einen scheinbar guten, aber tatsächlich schwächeren Ast fest und bleibt in einem lokalen Optimum hängen. Ein Verfahren ohne Bindung an bewährte Äste probiert dagegen endlos neue Äste aus, ohne je in die Tiefe zu gehen.
UCT in KI-Agenten
Language Agent Tree Search (LATS) überträgt die Baumsuche auf Sprachmodell-Agenten. In der Selection-Phase nutzt LATS die UCT-Formel. Sie wägt den bisher gemessenen Wert eines Astes gegen das Verhältnis der bisherigen Besuche ab und bestimmt so den Knoten, an dem weitergesucht wird.
Bezug zu SAP Business One
Die Verfügbarkeitsprüfung in SAP Business One zeigt mehrere Lösungsoptionen gleichzeitig, wenn die Bestellmenge den verfügbaren Bestand übersteigt. Das System bewertet diese Optionen aber nicht und wählt keine automatisch aus. Gemessene Werte je Option, auf die eine Auswahlregel wie UCT zugreifen könnte, gibt es dort nicht. Die Auswahl bleibt vollständig beim Anwender.
Abgrenzung
UCT ist nicht die Baumsuche selbst, sondern eine Auswahlregel innerhalb der Baumsuche. Die Monte-Carlo-Baumsuche umfasst weitere Schritte, etwa das Anhängen neuer Knoten und die Backpropagation, bei der das Ergebnis eines Durchlaufs im Baum nach oben zurückgereicht wird. UCT entscheidet nur, welcher Ast als Nächstes an der Reihe ist.
Sprint und Swirl: Wie ein KI-Agent Arbeit aufteilt und aus Probeläufen lernt
LATS: Mehrere Wege gleichzeitig durchdenkt mit KI — und die Verfügbarkeitsprüfung in SAP B1
ReAct und RLEF: Wie Künstliche Intelligenz aus echten Fehlern lernt — und was der automatische Bankabgleich in SAP Business One damit zu tun hat
SAP B1 10.0 FP2608: Service Layer KI als transaktionalen Schicht
Process Reward Models: Warum ein richtiges Ergebnis noch keinen richtigen Weg beweist
