Zahlsuchalgorithmen: von Knuth zu MCMC

Optimierung von Zahlraten-Strategien: Knuths Minimax, zufällige Suche und MCMC

Im Zahlraten-Spiel muss ein Spieler eine versteckte ganze Zahl aus dem Bereich [1, N] mithilfe von Abfragen und binärem Feedback – „höher“ oder „niedriger“ – identifizieren. Ziel ist es, die Gesamtanzahl der Versuche zu minimieren und gleichzeitig den Rechenaufwand pro Schritt gering zu halten. Wir untersuchen drei Ansätze: Knuths Minimax-Verfahren, die zufällige Suche sowie die Markov-Chain-Monte-Carlo-Methode (MCMC).

Knuths Minimax garantiert die theoretisch optimale Anzahl von ⌈log₂N⌉ Versuchen – verursacht aber pro Schritt O(N²) Operationen. Die zufällige Suche senkt den Aufwand pro Schritt auf O(1), wobei die erwartete Versuchszahl lediglich um den Faktor 1,71 steigt. MCMC bietet einen pragmatischen Kompromiss: Durch stochastische Exploration konvergiert sie effizient zu konsistenten Kandidaten.

Knuths Minimax-Strategie

Der Minimax-Algorithmus verwaltet eine Menge S möglicher Werte und wählt jede Abfrage so, dass die garantierte Reduktion von |S| maximiert wird – unabhängig davon, ob die Antwort „höher“ oder „niedriger“ lautet.

• Initialisiere S = {1, ..., N}.
• Für jeden möglichen Tipp a ∈ all_hiddens berechne min(|{c ∈ S : check(a,c) = r}|) über alle r ∈ {'>', '<'}.
• Wähle das a mit dem größten dieser Minima.
• Aktualisiere S anhand der tatsächlichen Antwort.

Diese Implementierung erreicht optimale Leistung: Für N = 1024 findet sie die gesuchte Zahl exakt in 10 Versuchen.

from copy import deepcopy

def knut_maxmin(check, all_hiddens, results, cur_hiddens):
    """Knuths Minimax-Strategie zur Auswahl des optimalen nächsten Tips."""
    return max(
        [(a, min(
            [sum(1 for c in cur_hiddens if check(a, c) != r)
             for r in results]
        )) for a in all_hiddens],
        key=lambda p: p[1]
    )[0]

def play_game(N):
    hiddens = list(range(1, N + 1))
    results = ['>', '<']

    def check(guess, hidden):
        if guess == hidden:
            return True
        return '>' if hidden > guess else '<'

    cur = list(hiddens)
    step = 0
    while len(cur) > 1:
        step += 1
        guess = knut_maxmin(check, cur, results, cur)
        answer = check(guess, SECRET)  # SECRET ist die versteckte Zahl
        if answer is True:
            return guess, step
        cur = [c for c in cur if check(guess, c) == answer]
    return cur[0], step + 1

Einschränkung: Der quadratische Aufwand O(N²) pro Schritt macht dieses Verfahren für N > 10⁵ praktisch unbrauchbar.

Intervallbasierte zufällige Suche

Anstatt die gesamte Kandidatenmenge S zu verwalten, behält dieser Ansatz nur das aktuelle Intervall [lo, hi] im Speicher. Jeder Tipp wird gleichverteilt aus diesem Intervall gezogen – die Grenzen werden adaptiv angepasst.

import random

def play_random(N, secret):
    lo, hi = 1, N
    steps = 0
    while lo < hi:
        steps += 1
        guess = random.randint(lo, hi)
        if guess == secret:
            return steps
        elif secret > guess:
            lo = guess + 1
        else:
            hi = guess - 1
    return steps + 1

Analyse: Bei einer Stichprobe x ~ Uniform[0,L] beträgt die erwartete relative Länge des verbleibenden Intervalls ∫₀¹ (x² + (1−x)²) dx = 2/3. Damit ergibt sich die erwartete Versuchszahl k ≈ (ln N) / ln(3/2) ≈ 1,71 log₂N. Für N = 1024 sind das etwa 17 Versuche gegenüber dem Minimax-Optimum von 10 – bei konstantem Zeitaufwand pro Schritt.

Vorteile:

• Konstanter Zeitbedarf pro Schritt.
• Asymptotisch O(log N) Gesamtversuche.
• Kein Speicherbedarf für Kandidatenmengen.

MCMC mit Metropolis–Hastings

Dieses Verfahren konstruiert eine Markov-Kette, die gegen eine Zielverteilung π(x) ∝ exp(−β · violations(x)) konvergiert, wobei violations(x) die Anzahl der Inkonsistenzen zwischen x und vergangenen Abfrage-Antwort-Paaren [(guessᵢ, rᵢ)] zählt.

Abstimmungsparameter: σ (Skala des Gaußschen Vorschlagsrauschens), β (inverse Temperatur) und n_iter (Anzahl der MCMC-Schritte).

import random
import math

def mcmc_guess(N, history, n_iter=500, sigma=None, beta=10.0):
    """Metropolis–Hastings-Algorithmus für das Zahlraten."""
    if sigma is None:
        sigma = N / 4

    def violations(x):
        count = 0
        for guess, response in history:
            if response == '>' and x <= guess:
                count += 1
            elif response == '<' and x >= guess:
                count += 1
        return count

    def target(x):
        return math.exp(-beta * violations(x))

    # Startwert
    x = random.randint(1, N)

    for _ in range(n_iter):
        # Vorschlag generieren
        x_prime = x + int(random.gauss(0, sigma))
        x_prime = max(1, min(N, x_prime))

        # Akzeptieren oder verwerfen
        acceptance = target(x_prime) / max(target(x), 1e-300)
        if random.random() < min(1.0, acceptance):
            x = x_prime

    return x


def play_mcmc(N, secret):
    history = []
    for step in range(1, 10 * N):
        guess = mcmc_guess(N, history)
        if guess == secret:
            return step
        response = '>' if secret > guess else '<'
        history.append((guess, response))
    return None  # konnte nicht erraten

Experimente (N = 100, 100 Durchläufe): Mittelwert = 8,3 Versuche, Median = 8, Maximum = 17. MCMC passt sich intuitiv an die bisherigen Abfragen an – empirisch robust mit σ = N/4 und β = 10.

Kernergebnisse

• Knuths Minimax: Optimal mit ⌈log₂N⌉ Versuchen – doch O(N²) Aufwand pro Schritt. Ideal für kleines N.
• Zufällige Suche: Etwa 1,71× mehr Versuche als optimal, aber O(1) Berechnung pro Schritt. Bestens geeignet für großes N.
• MCMC: Erreicht etwa log N Versuche bei sorgfältiger Parametrierung; konvergiert innerhalb von n_iter Schritten zu realistischen Kandidaten.
• Die Wahl der Strategie hängt von N und den zeitlichen Anforderungen pro Zug ab.
• Alle drei Verfahren bewahren nach den ersten paar Zügen die Intervallstruktur.

— Editorial Team