Коэффициент ветвления и количество узлов
Дерево игры моделирует каждую возможную последовательность ходов из начальной позиции. Каждый узел представляет состояние доски. Каждое ребро представляет один законный ход. Структура дерева определяет, остается ли поиск осуществимым.
Ключевые параметры
Коэффициент ветвления b: количество законных ходов, доступных в типичной позиции.
Глубина d: количество полуходов для поиска вперед.
Количество узлов на глубине d: b^d
Всего узлов на всех глубинах: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Для больших b и d сумма ≈ b^d (доминируется уровнем листьев).
4×4×4 Крестики-нолики
Полное дерево игры: b ≈ 64 (законные клетки), d = 64 (всего ходов). Полное количество узлов ≈ 64^64 ≈ 10^115. Наблюдаемая вселенная содержит примерно 10^80 атомов. Полный перебор физически невозможен.
Вычисление размера дерева
Шахматы дают более реалистичные числа. Средний коэффициент ветвления b ≈ 35. Поиск на 6 полуходов (3 хода с каждой стороны) требует примерно 35^6 узлов.
Альфа-бета отсечение: сокращение показателя степени
Альфа-бета отсечение исключает поддеревья, которые не могут влиять на результат минимакса. Ключевое понимание: если вы уже знаете, что одна ветвь дает значение V, вы можете отсечь любую соседнюю ветвь, значение которой заведомо падает ниже V (для максимизирующего игрока) или выше V (для минимизирующего игрока).
Геометрия лучшего случая
При оптимальном порядке ходов (лучшие ходы просматриваются первыми), альфа-бета снижает эффективный коэффициент ветвления с b до √b. Глубина поиска эффективно удваивается для того же количества узлов:
Полный поиск: b^d узлов
Альфа-бета лучший случай: b^(d/2) узлов
Пример: b=35, d=6. Полный: 35^6 ≈ 1,84 × 10^9. Альфа-бета: 35^3 = 42 875. Коэффициент сокращения: ~43 000.
На практике порядок ходов не совершенен. Типичное сокращение: b^(d×0,75) — эквивалентный коэффициент ветвления ≈ b^0,75.
Центрально-угловая двойственность
Хэмминг отмечает геометрическую двойственность в кубе 4×4×4: существует инверсия, отправляющая 8 угловых позиций в 8 центральных позиций (внутренний куб 2×2×2) и наоборот, сохраняя все 76 выигрышных линий.
Подсчет линий через позицию
В кубе 4×4×4 позиции отличаются тем, сколько выигрышных линий проходит через них:
Угловые позиции: по 7 линий каждая (4 диагонали грани, 2 реберные линии, 1 пространственная диагональ)
Реберно-центральные позиции: по 4 линии каждая
Лицевые центральные позиции: по 6 линий каждая
Позиции центра корпуса (внутренние 2×2×2): по 7 линий каждая
Двойственность отображает углы (7 линий) на центры корпуса (7 линий). Обе группы образуют «горячие точки».
Почему геометрически важны горячие точки
Игрок, контролирующий больше позиций с высоким количеством линий, контролирует больше потенциальных выигрышных линий. Это прямой геометрический аргумент: максимизация покрытия линий направляет выбор хода без какого-либо поиска.
Функции оценки
Каждой программе, играющей в игры, нужна функция оценки: функция, отображающая состояния доски в числовые значения (положительное = хорошо для максимизирующего игрока, отрицательное = хорошо для минимизирующего игрока). Функция оценки обеспечивает граничное условие в листьях дерева поиска.
Линейные функции оценки
Линейная функция оценки присваивает вес w_i каждому признаку f_i позиции:
E(позиция) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Для крестиков-ноликов 4×4×4: признаки могут включать контролируемые открытые линии, позиции в клетках с высоким количеством линий, грозящие вилки. Для шахмат: количество материала, контроль центра, безопасность короля, структура пешек.
Это линейная функция в пространстве признаков — гиперплоскость в ℝ^n. Две позиции с одинаковыми значениями признаков получают одинаковую оценку независимо от всех других различий. Геометрия функции оценки определяет, что программа «видит».
Программа шашек Сэмюэля улучшилась путем настройки вектора весов w — градиентный спуск в пространстве линейных функций оценки.
Геометрия и граница формализации
Дерево игры имеет чистую геометрическую структуру: экспоненциальный рост на глубине d, сводимый к b^(d/2) альфа-бета, дополнительно сводимый путем ограничения высокозначных позиций (горячие точки снижают эффективный b). Функция оценки определяет гиперплоскость в пространстве признаков.
Все это чистое, точное, формально завершено. Он описывает центр проблемы игры — область, где математическая структура обеспечивает четкое руководство.
Граница — где переключиться с применения правил на исследование, когда пожертвовать позиционным преимуществом для тактической возможности, как распознавать появляющиеся паттерны за пределами функции оценки — сопротивляется формализации. Неявное знание Хэмминга живет на этой границе.
Геометрия позволяет вычислить, сколько поиска вы можете себе позволить. Она не говорит вам, на что смотреть.