Игра в угадайку

Со временем люди оказались в бедственном положении. Поразмыслив над тем, что раньше им жилось не так плохо, а теперь они на грани разорения, они пришли к выводу, что среди них есть кто-то, кто навлекает на них несчастья, и решили разделиться на две группы. Так они и сделали, и теперь их было две группы по пятьсот семей в каждой. С тех пор разорение преследовало группу, в которой жили родители будущего Лосаки, в то время как остальные пятьсот семей процветали. Поэтому первые решили продолжать сокращать свое число вдвое и делали это до тех пор, пока одна семья не отделилась от всех остальных. Тогда они поняли, что именно в этой семье кроется источник несчастий, и прогнали их с помощью силы. – The Jataka or Stories of the Buddha’s Former Births.

Формулировка задачи

Игра устроена так.

Играют двое: загадывающий и отгадывающий. Загадывающий загадывает целое число в известном диапазоне — скажем, от 1 до включительно. Отгадывающий пытается это число отгадать, называя варианты. После каждого неверного варианта загадывающий говорит: «больше» или «меньше».

Задача: отгадать число за минимальное количество попыток, используя минимальный объем вычислений.

Подход 1. Максимин Кнута

Итак, первое, что приходит в голову каждому человеку — а мне так и вовсе не приходит ничего другого — это алгоритм оптимального поиска Дональда Кнута, известный как стратегия максимина. Изначально Кнут предложил его для игры Mastermind, но нетрудно видеть, что он применим к любой игре подобного типа, включая нашу.

Алгоритм:

1. Построить множество из всех возможных вариантов ответа (в нашем случае — все числа от 1 до ).

2. Для каждого возможного хода оценить, сколько элементов будет гарантированно удалено из при любом исходе. То есть для каждого возможного ответа загадывающего («больше» / «меньше») посчитать, сколько элементов окажутся противоречащими этому ответу. Очки хода — это минимум из этих чисел.

3. Выбрать ход с максимальным количеством очков. При равенстве — предпочесть тот, что сам входит в .

4. Если число угадано — алгоритм завершается.

5. Иначе — удалить из все элементы, несовместимые с полученным ответом.

6. Повторить с пункта 2.

Вот реализация на Python:

from copy import deepcopy

def knut_maxmin(check, all_hiddens, results, cur_hiddens):
    """Стратегия максимина Кнута для выбора оптимального хода."""
    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 — загаданное число
        if answer is True:
            return guess, step
        cur = [c for c in cur if check(guess, c) == answer]
    return cur[0], step + 1

Замечательно! Можно строго доказать, что максимин Кнута определяет ответ за теоретически оптимальное число попыток. Для нашей задачи это — на каждом шаге пространство вариантов сокращается ровно вдвое.

Для это 10 попыток. Идеально. Врят ли найдется более простой способ столь же великолепно решить эту задачу

Проблема

Есть, однако, нюанс. Максимин находит оптимальный ход за : для каждого из кандидатов на ход нужно проверить его эффективность на всех элементах .

Если — вообще не проблема. Если — это уже операций на первый ход. Вряд ли загадывающий будет ждать столько.

Нам нужно что-то попроще.

Подход 2. Случайный кандидат

Очевидное улучшение: зачем тратить на поиск оптимального хода, если можно просто выбрать случайный элемент из ? Случайность — наш верный друг. Она никогда не подводит. Ну, почти никогда.

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

Вычислительная стоимость: на каждый ход. Фильтрация множества не нужна — у нас интервал, и мы просто сдвигаем его границу. Но возникает вопрос: сколько ходов это займёт?

Математическое отступление

Представим, что текущее пространство — интервал длины . Мы выбираем случайную точку , равномерно. В зависимости от ответа загадывающего, нам остаётся либо левая, либо правая часть интервала.

Если загаданное число лежит правее , нам остаётся интервал длины . Если левее — длины . В среднем по положению загаданного числа и нашей случайной точки, математическое ожидание квадрата относительной длины оставшегося интервала:

Подождите, но это ожидание длины оставшегося интервала при условии, что загаданное число равномерно на интервале, а мы выбираем точку тоже равномерно? Давайте аккуратнее.

Пусть точка выбора — , равномерно на (нормируем). Загаданное число — , тоже равномерно на . При

остаётся отрезок длины . При — отрезок длины . Ожидание длины по при фиксированном :

Теперь берём ожидание по :

Итого: в среднем на каждом шаге длина интервала уменьшается до исходной. Для решения задачи нужно:

Сравнение с оптимумом:

В 1,71 раза больше ходов. Для : ~17 вместо 10. Это может показаться значительным падением качества. Но задумайтесь: задача всё ещё решается за ходов. Это несравнимо лучше, чем перебирать варианты по порядку, не правда ли?

К тому же, каждый ход вычисляется за .

Неплохо. Но мы же тут не за «неплохо» собрались. Мы здесь, чтобы решать задачи. По-настоящему.

Досадно признавать, но оба описанных выше подхода обладают общим недостатком: они слишком просты. Любой первокурсник поймёт их за пять минут. Где вызов? Где интеллектуальное удовлетворение? Где параграф «Выбор гиперпараметров»?

Время достать тяжёлую артиллерию.

Подход 3. Марковская цепь Монте-Карло (MCMC)

Идея

Марковская цепь Монте-Карло — один из столпов вычислительной статистики, молекулярной динамики и байесовского вывода. Она позволяет моделировать свёртку белков, оценивать апостериорные распределения в байесовских сетях, и, естественно, угадывать число от 1 до 100.

Идея: вместо того чтобы перебирать все варианты, мы строим случайное блуждание по пространству решений, которое со временем «притягивается» к ответу.

Конструкция

Определим целевое распределение — плотность, которую мы хотим «сэмплировать». Пусть имеется история наблюдений: после каждого хода мы получили ответ

. Число совместимо с наблюдением , если:

Определим целевую функцию:

где — число наблюдений, которым противоречит, а — параметр «температуры» (большое — жёсткий отбор, малое — мягкий).

Алгоритм Метрополиса — Гастингса

1. Инициализировать текущее состояние — случайное число из .

2. На каждой итерации:

   • Предложить кандидата , где (гауссов шум), с округлением и ограничением в .

   • Вычислить коэффициент принятия: .

   • С вероятностью принять: . Иначе .

3. После достаточного числа итераций выбрать как следующий ход.

import random
import math

def mcmc_guess(N, history, n_iter=500, sigma=None, beta=10.0):
    """Алгоритм Метрополиса — Гастингса для угадывания числа."""
    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))

    # Начальное состояние
    x = random.randint(1, N)

    for _ in range(n_iter):
        # Предлагаем кандидата
        x_prime = x + int(random.gauss(0, sigma))
        x_prime = max(1, min(N, x_prime))

        # Принимаем или отвергаем
        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  # не угадали

Экспериментальные результаты

Теория — это, конечно, прекрасно, но мы же учёные. Нам нужны данные. Мы провели серию из 100 экспериментов при (случайное загаданное число) и замерили количество ходов до угадывания.

Результаты: среднее число ходов — 8,3, медиана — 8, максимум — 17. Успешность — 100%. Время работы — 0,33 секунды на 100 игр.

На графике ниже показана трассировка типичной партии (загадано число 73). Видно, как цепь Маркова блуждает по пространству, постепенно стягиваясь к допустимой области. Голубая зона — допустимый интервал, красная линия — ходы алгоритма.

Обратите внимание: на первых ходах цепь прыгает от 1 до 91 — она ещё «не знает», куда идти. К ходу 6–7 интервал уже достаточно сужен, и цепь начинает вести себя осмысленно. На ходе 10 — точное попадание. Всего 500 итераций Метрополиса на каждый ход, и цена за это — лишь 0,33 секунды. Белки складываются дольше.

При : среднее — 13,0 ходов, максимум — 24, провалов — 0. Алгоритм работает, и тратит на это всего лишь ~1,5 раза больше ходов, чем теоретический оптимум.

Обсуждение

Алгоритм Метрополиса — Гастингса обладает рядом замечательных свойств:

• Теоретическая сходимость: при достаточном числе итераций цепь Маркова сходится к целевому распределению.

• Универсальность: не требует знания о структуре пространства. Работает, даже если числа расположены на поверхности 11-мерного многообразия Калаби-Яу, (которым, по мнению теории струн, является наша Вселенная).

• Элегантность: один и тот же алгоритм используется для моделирования свёртки белков и для угадывания числа от 1 до 100. Это ли не прекрасно?

Есть, правда, и некоторые практические нюансы:

• Выбор (ширина предложения) критичен. Слишком маленькая — цепь застревает. Слишком большая — кандидаты постоянно отвергаются. В пределе алгоритм вырождается в локальный поиск, — в независимое сэмплирование.

• Выбор тоже критичен. Слишком большое — жёсткие стенки, цепь не перемешивается. Слишком маленькое — цепь забывает наблюдения.

• Число итераций MCMC на каждый ход — ещё один гиперпараметр. Он тоже критичен.

• Нужен критерий останова. Нет гарантий на конечное число ходов.

Но всё это — не баги, а пространство для исследований. Каждый гиперпараметр — это потенциальная глава в диссертации.

Подход 4. Градиентный спуск

Идея

Читатель, несомненно, уже задаётся вопросом: а нельзя ли применить к нашей задаче градиентный спуск? Было бы странно, если бы нельзя. В 2026 году всё, что не решается градиентным спуском, попросту не существует.

Определим задачу оптимизации. Имея историю наблюдений , построим функцию потерь, минимум которой соответствует загаданному числу.

Функция потерь

Для каждого наблюдения определим штраф. Если , загаданное число больше , и нам нужно

. Определим:

где

Это мягкие квадратичные штрафы: если находится на правильной стороне от , штраф равен нулю. Если на неправильной — штраф растёт квадратично.

Алгоритм

def gradient_guess(N, history, lr=0.5, n_iter=200):
    """Градиентный спуск для угадывания числа."""
    # Начальная точка — центр интервала
    x = N / 2.0

    for _ in range(n_iter):
        grad = 0.0
        for guess, response in history:
            if response == '>':
                # x должно быть > guess
                margin = guess - x + 1
                if margin > 0:
                    grad += -2 * margin  # производная max(0, margin)^2
            else:
                # x должно быть < guess
                margin = x - guess + 1
                if margin > 0:
                    grad += 2 * margin

        x -= lr * grad
        x = max(1.0, min(float(N), x))

    return int(round(x))


def play_gradient(N, secret):
    history = []
    for step in range(1, 10 * N):
        guess = gradient_guess(N, history)
        if guess == secret:
            return step
        response = '>' if secret > guess else '<'
        history.append((guess, response))
    return None

Экспериментальные результаты

Мы, разумеется, тоже провели 100 экспериментов при .

Результаты: успешность — 54%. Сорок шесть игр из ста закончились провалом (алгоритм не нашёл ответ за 500 ходов). Среднее число ходов среди успешных — 8,5. Время работы — 79,7 секунды на 100 игр.

Посмотрим, почему. Ниже — трассировка для загаданного числа 73:

Алгоритм начинает с (центр интервала — единственное разумное действие при пустой истории). Далее он аккуратно поднимается: 51, 53, 57, 65… Перелетает цель: 81, 80, 78, 74. Вот-вот попадёт! Но на шаге 10 оказывается в точке 66, и тут происходит катастрофа: накопленные штрафы от всех предыдущих ходов перетягивают градиент, и алгоритм улетает в точку 9. После чего остаётся там навсегда. Градиент в точке 9 равен нулю (все штрафы «сверху»), и спуск прекращается.

Да, мы не достигли желаемого. Но зато какую модель экзистенциального кризиса нам удалось построить!

При ситуация ещё более драматична: успешность падает до 14% (7 из 50). Алгоритм тратит 73,7 секунды — и в 86% случаев не находит ответ.

Анализ

Градиентный спуск обладает рядом преимуществ:

• Скорость: на каждый ход — , где — длина истории, — число итераций спуска.

• Дифференцируемость: задача становится непрерывной оптимизацией. Можно применить Adam, RMSProp, или любой другой модный оптимизатор.

• Нейросетевой потенциал: заменив аналитический градиент на автодифференцирование, можно встроить эту задачу в пайплайн глубокого обучения. Нейросеть, угадывающая число от 1 до 100 — звучит как заявка на стартап с оценкой в $50M.

Однако внимательный читатель заметит некоторые особенности:

• На первом ходу, когда история пуста, градиент равен нулю. Алгоритм стоит на месте. Начальную точку приходится выбирать вслепую (мы берём центр интервала, что, стоит признать, подозрительно хорошо работает — но строго по совпадению).

• Функция потерь кусочно-квадратична. Это значит, что при хорошем (совместимом со всей историей) градиент равен нулю, и алгоритм перестаёт двигаться. Кажется, нужен momentum.

• Дискретность: округление до целого вносит… нюансы.

Впрочем, все эти проблемы — лишь приглашение к более глубокому исследованию. Learning rate scheduling, warm restarts, стохастический градиентный спуск по мини-батчам наблюдений, cosine annealing… Возможности безграничны. Было бы число от 1 до 100, а оптимизатор найдётся.

Подход 5. Эволюционный алгоритм

Мотивация

Предыдущие методы имеют общий недостаток: в каждый момент времени они поддерживают одну гипотезу. Одно число, один кандидат, одну точку в пространстве. Это узко. Это негибко. Это не по-эволюционному.

Что если вместо одной гипотезы мы будем поддерживать целую популяцию кандидатов? И позволим естественному отбору самому определить, кто из них прав?

3,5 миллиарда лет эволюции привели к появлению человеческого мозга. Дадим алгоритму 30 поколений — посмотрим, хватит ли ему, чтобы угадать число 73.

Представление

Поддерживаем популяцию из кандидатов:

Каждый кандидат — число из .

Функция приспособленности (fitness)

Пусть имеется история наблюдений . Для кандидата определим штраф:

Тогда fitness:

Кандидаты, полностью согласованные с историей, получают . Кандидаты с противоречиями — экспоненциально подавляются. Элегантно и беспощадно.

Основной цикл

import random
import math

def evolutionary_guess(N, history, pop_size=50, generations=30, alpha=5.0):
    """Эволюционный алгоритм для угадывания числа."""

    def fitness(x):
        penalty = 0
        for guess, response in history:
            if response == '>' and x <= guess:
                penalty += 1
            elif response == '<' and x >= guess:
                penalty += 1
        return math.exp(-alpha * penalty)

    # Инициализация популяции
    population = [random.randint(1, N) for _ in range(pop_size)]

    for gen in range(generations):
        # Оценка приспособленности
        scores = [fitness(x) for x in population]
        total = sum(scores)
        if total == 0:
            population = [random.randint(1, N) for _ in range(pop_size)]
            continue

        # Отбор (рулетка)
        probs = [s / total for s in scores]
        selected = random.choices(population, weights=probs, k=pop_size)

        # Мутация
        new_population = []
        for x in selected:
            if random.random() < 0.1:
                # Глобальный прыжок
                x = random.randint(1, N)
            else:
                # Локальная мутация
                delta = int(random.gauss(0, max(1, N / 20)))
                x = max(1, min(N, x + delta))
            new_population.append(x)

        population = new_population

    # Выбор лучшего
    scores = [fitness(x) for x in population]
    best_idx = scores.index(max(scores))
    return population[best_idx]


def play_evolutionary(N, secret):
    history = []
    for step in range(1, 10 * N):
        guess = evolutionary_guess(N, history)
        if guess == secret:
            return step
        response = '>' if secret > guess else '<'
        history.append((guess, response))
    return None

Алгоритм работает итеративно:

1. Оценка популяции. Каждому кандидату начисляется fitness.

2. Отбор. Формируется новая популяция преимущественно из «сильных» кандидатов. Используется пропорциональный отбор (рулетка): вероятность быть выбранным пропорциональна fitness. Можно также использовать турнирный отбор или просто отбирать k лучших, но рулетка звучит внушительнее, отсылая нас к классическим методам Монте-Карло, и связывая эволюционный подход с другими вышеупомянутыми методам.

3. Мутация. К каждому потомку применяется случайное изменение: , где . С небольшой вероятностью — глобальный прыжок в случайную точку (чтобы популяция не «вырождалась»).

4. Обновление. Новая популяция заменяет старую. Круг жизни замкнулся.

Выбор хода

После нескольких поколений эволюции популяция концентрируется в области, совместимой с историей. В качестве хода выбираем наиболее приспособленную особь.

Экспериментальные результаты

Естественно, мы подвергли и эволюционный алгоритм суровому испытанию: 100 игр, . Результаты: среднее число ходов — 7,4, медиана — 7, максимум — 15. Успешность — 100%. Время — 0,76 секунды.

Да, вы прочитали правильно. Эволюционный алгоритм с 50 особями, 30 поколениями и 4 гиперпараметрами угадывает число быстрее, чем MCMC (7,4 vs 8,3). И лишь чуть медленнее, чем случайный кандидат (7,4 vs 7,3). Дарвин, видимо, действительно что-то знал.

На графике ниже показано, как популяция концентрируется в допустимой области по поколениям. История наблюдений:

, , , — допустимый интервал .

В поколении 0 особи распределены равномерно. К поколению 3 популяция уже заметно сместилась вправо. К поколению 10 — сконцентрирована в допустимой области. К поколению 29 — практически все особи находятся в , с небольшим числом «разведчиков» за пределами (10% глобальных мутаций не дают популяции выродиться).

При : среднее — 12,7 ходов, максимум — 28, провалов — 0. Эволюция справляется.

Обсуждение

Эволюционный подход привлекателен своей философской глубиной:

• Он не требует явного перебора пространства.

• Легко адаптируется к шумным или противоречивым данным (загадывающий ошибся? Не проблема — эволюция учтёт).

• Допускает параллельную реализацию (каждая особь может эволюционировать на отдельном ядре процессора).

• Естественно обобщается на многомерные пространства.

Конечно, есть и нюансы: размер популяции, сила мутаций, баланс эксплорации и эксплуатации, выбор … Но всё это детали реализации. Главное — мы решили задачу угадывания числа от 1 до 100 методом, вдохновлённым самой природой. Дарвин бы одобрил.

Сравнение подходов

Давайте честно сравним все три серьёзных подхода. Мы провели по 100 экспериментов при и по 50 при , с лимитом в 500 ходов.

Результаты при (100 игр)

* — среднее только по успешным попыткам.

Результаты при (50 игр)

Распределение числа ходов

На гистограмме хорошо видна ключевая разница: MCMC и эволюционный алгоритм демонстрируют компактное, почти нормальное распределение числа ходов. Градиентный спуск — показывает распределение только выживших. Остальные 77 из 200 игр ушли в вечность и на графике не представлены.

Наблюдения

1. MCMC — работает надёжно, сходится всегда. 0,33 секунды ценой 500 итераций цепи Маркова на каждый ход — приемлемая плата за принадлежность к байесовской аристократии.

2. Градиентный спуск — экспериментально подтвердил свой экзистенциальный кризис. При проваливается в 46% случаев. При — в 86%. При этом тратит 79,7 секунды — в 240 раз больше, чем MCMC, для худшего результата. Диагноз: функция потерь кусочно-квадратична, в допустимой области градиент равен нулю, алгоритм застревает и повторяет один и тот же ответ до скончания времён.

3. Эволюционный — неожиданный фаворит. Лучшее среднее (7,4), 100% успех, умеренное время. 50 особей × 30 поколений — и задача решена. Единственное, что омрачает триумф: количество гиперпараметров по-прежнему сопоставимо с количеством ходов.

Возможно, внимательный читатель к этому моменту задумается: а нет ли чего-нибудь попроще? Чего-нибудь, что не требует 500 итераций MCMC, 30 поколений эволюции и двух гиперпараметров (один из которых ведёт к 86% провалов), чтобы угадать число от 1 до 100?

Нет. Ничего проще не существует.

Ну, разве что трансформеры.

Литература

1. Knuth D. E. The Computer as Master Mind. Journal of Recreational Mathematics, 9(1), 1976/77, pp. 1–6.

2. Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1953, pp. 1087–1092.

3. Hastings W. K. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika, 57(1), 1970, pp. 97–109.

4. Boyd S., Vandenberghe L. Convex Optimization. Cambridge University Press, 2004.

5. Hansen N. The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772, 2016.

6. Robert C. A Short History of Markov Chain Monte Carlo: Subjective Recollections from Incomplete Data. Statistical Science, 26(1), 2011, pp. 102–115.

7. Charles Darwin. On the Origin of Species by Means of Natural Selection. London: John Murray, 1859.

8. The Jataka. The Jataka or Stories of the Buddha’s Former Births, Vol. I, trans. Robert Chalmers. Cambridge University Press, 1895.

9. Автор. Экспериментальное исследование поведения стохастических методов в задаче интерактивной идентификации целого параметра. Не опубликовано, 2026.