ДОС — игра на бумаге для двух игроков¶
ДОС (от англ. dots and boxes, «точки и квадраты») — настольная бумагографическая игра для двух игроков, в которой участники по очереди проводят линии между соседними точками сетки, а замкнувший квадрат забирает себе и ходит снова. Цель игры — захватить большее число квадратов. ДОС относится к категории математических игр и изучается в теории игр как пример игры с полной информацией и нулевой суммой.
¶История
Игра известна с XIX века под разными названиями: Dots and Boxes, Boxes, Squares, Pigpen, Square-it. В России и странах СНГ она распространена под аббревиатурой ДОС («дотс энд боксес»). Первые печатные упоминания относятся к 1880-м годам. Классификацию и математический анализ игры провёл канадский математик Тони Уоршоффский (Tony Warrington) в 1990-х годах; его работа «Dots-and-Boxes: An Elementary Example of the Sprague-Grundy Theory» стала одним из основных источников по теории этой игры.
¶Правила
Игровое поле — сетка из точек, обычно 4×4, 5×5 или 6×6 (квадрат из n точек образует (n−1)×(n−1) квадратных клеток). Точки расчерчиваются заранее или рисуются по ходу партии.
- Игроки выбирают, кто ходит первым, и договариваются о размере сетки.
- Игроки ходят по очереди, каждый ход — проведение одной горизонтальной или вертикальной линии между двумя соседними точками.
- Если ход замыкает квадрат (все четыре стороны проведены), игрок записывает себе этот квадрат (ставит внутри свою букву или крестик) и ходит ещё раз.
- Если ход одновременно замыкает два квадрата, игрок забирает оба и снова ходит.
- Игра заканчивается, когда проведены все линии. Побеждает игрок, захвативший больше квадратов.
При равном счёте объявляется ничья. Вариант с сеткой 4×4 содержит 24 линии и 9 квадратов, поэтому при нечётном числе клеток ничья невозможна.
¶Стратегия
Несмотря на простоту правил, ДОС обладает нетривиальной стратегической глубиной. Ключевые понятия:
¶Цепи и линейные цепочки
Цепочкой называется ряд из k квадратов, в котором уже проведены все линии, кроме k+1 внешних. Отдавая первую клетку цепи, игрок получает остальные k−1 клеток. Поэтому ход, открывающий цепочку длиной 1 («сдвоенный ход»), крайне невыгоден. Опытные игроки избегают ходов, создающих цепочки, пока это возможно, и стремятся заставить соперника открыть цепь первой.
¶Ход «двойной крючок»
В некоторых позициях существует ход, одновременно создающий две независимые цепи. Соперник может забрать одну цепь, но вынужден отдать другую. Такие ходы считаются сильнейшими в позиции.
¶Теория Шпрага — Грэнди
ДОС — игра с полной информацией, поэтому в ней применима теория Шпрага — Грэнди. Каждая позиция описывается числом Гринди; позиции с числом 0 проигрышны для того, кто ходит. На практике точный расчёт возможен лишь для малых сеток: для 2×2 клеток игра решается тривиально, для 3×3 — перебором, а для сеток 4×4 и выше число позиций слишком велико для полного анализа.
¶Ловушки и «ядовитые» ходы
Иногда полезно провести линию, создающую сопернику привлекательную возможность забрать клетку, но ведущую к цепочке, которую он вынужден открыть. Такие ходы называются ловушками.
¶Математические свойства
Число возможных партий на сетке 4×4 (9 клеток) оценивается в 10^14 и более, что делает полный перебор практически невозможным. Игра демонстрирует, что даже комбинаторные игры с очень простыми правилами могут быть алгоритмически сложными: задача определения победителя в ДОС на произвольной сетке принадлежит классу PSPACE.
¶Варианты
- Двухходовая сетка — в начальной позиции уже проведены линии, образующие «двойные ходы».
- Трёхходовая сетка — часть линий проведена заранее, чтобы гарантировать длинные цепи.
- Размер сетки — сетки 2×2 и 3×3 клеток считаются обучающими, сетки 6×6 и больше — для опытных игроков.
- Квадратные сетки с диагоналями — нестандартный вариант, усложняющий подсчёт.
¶Применение
ДОС используется как обучающая игра в математических кружках и школах: она иллюстрирует понятия теории игр, жадных алгоритмов и комбинаторной оптимизации. Игра входит в программы математических олимпиад и соревнований по программированию как задача на написание стратегии. Существуют компьютерные реализации ДОС с ИИ, использующие перебор с отсечением и оценку позиции.
Источники:
- Warrington T. Dots-and-Boxes: An Elementary Example of the Sprague-Grundy Theory. — 1993.
- Berlekamp E., Conway J., Guy R. Winning Ways for Your Mathematical Plays. — Academic Press.
- Справочник по комбинаторным играм и теории Шпрага — Грэнди.