Что это за игра
Обычные крестики-нолики мертвы: игра полностью решена, при точной игре обеих сторон партия всегда заканчивается вничью, а вся стратегия умещается на салфетке. Вложенная версия собрана из тех же клеток, но мёртвой её не назовёшь.
Доска — девять маленьких полей 3×3, составленных в большой квадрат. Клетка, занятая внутри маленького поля, отправляет соперника в маленькое поле на той же позиции: сходили в правую верхнюю клетку — он обязан отвечать в правом верхнем поле. Если оно уже закрыто, он ходит куда захочет. Выигранное маленькое поле закрывается и помечается большим знаком; заполненное без победителя закрывается впустую. Три выигранных поля в ряд выигрывают партию; если все девять закрылись без такого ряда — ничья.
Правило пересылки и делает игру: каждый ход — это ещё и приказ сопернику. Отдать клетку и даже целое поле, лишь бы отправить его в безобидное место, — здесь обычная тактика: важно не только где вы выигрываете, но и куда ваш ход посылает другого игрока.
Как думает машина
На этой странице нет оценочной функции. Машина не знает, что центральное поле сильнее углового и что два знака в ряд — угроза; она вообще ничего не знает об игре, кроме правил. Вместо этого работает поиск по дереву Монте-Карло (MCTS): из текущей позиции доигрываются тысячи полностью случайных партий до самого конца, и записывается, какие первые ходы чаще заканчивались победой.
Дерево растёт неравномерно. Формула в одну строку (UCT) решает, откуда стартует следующая случайная партия: в основном там, где результаты хороши, иногда — там, где партий сыграно слишком мало. Этот баланс между «жать на то, что работает» и «проверять то, что не изучено» — вся математика метода.
Именно этот приём — случайные доигрывания плюс дерево поиска — в связке с нейросетями сломал го: AlphaGo, 2016 год. Об этом рассказывает страница «Как машины играют». Здесь MCTS работает в чистом виде, без нейросети: это единственная игра на сайте, где машина думает именно так.
Про уровни
Уровень — это время на размышление и ничего больше: обычный — около 0,15 с на ход, сложный — около 0,5 с, эксперт — около 1,4 с. Алгоритм на всех трёх одинаковый; разница только в том, сколько случайных партий он успевает доиграть до сигнала.
Строка под доской показывает это число после каждого хода машины. Это не украшение: вся сила хода — ровно в этой цифре.
Решена ли игра
Нет. В отличие от обычных крестиков-ноликов, вложенные не решены: никто не доказал, чем заканчивается партия при точной игре обеих сторон. Компьютерный анализ и турнирная практика указывают на преимущество первого игрока — но это наблюдение, а не теорема.
Первый ход отдан вам.