Математическая модель игры Доббль22.01.2019 22:19

Уровни сложности чтения

• Я слишком молод, чтобы думать

  
  
  • Введение и правила игры
  • Как они это делают?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Сделай мне умно

  
  
  • Введение и правила игры
  • Как они это делают?
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Кошмар

  
  
  • Введение и правила игры
  • Как они это делают?
  • Конечная геометрия для грудничков
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Как построить проективную плоскость?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

Введение и правила игры

Несколько лет назад я купил игру Доббль (Dobble, оригинальное название «Spot It!»). Это очень простая, быстрая и весёлая игра, которую я считаю одной из лучших настольных игр вообще.

В комплекте игры 55 карточек с 8 разными символами на каждой. Вот как выглядят эти карточки:

Рис. 1. Пример карточек игры.

На каждых двух карточках совпадает один и только один символ. На приведённом рисунке это символ карандаша:

Рис. 2. Совпадающие символы на карточках.

Игрок, первый увидевший совпадение, делает с одной из карточек действие, зависящее от тура игры. Например, забирает её себе или подкидывает сопернику.
Часто это приводит к тому, что одна из карточек, для которой игроки ищут совпадения, меняется. Из-за этого приходится искать новое совпадение, которое может быть совсем другим символом:

Рис. 3, 4. Первая карточка заменяется на новую. Теперь между ними новое совпадение — символ клоуна.

Как они это делают?

На первый взгляд, кажется невероятным, что на двух карточках ровно одно совпадение, ни больше, ни меньше. Сразу возникают вопросы — сколько всего символов в игре? Их не может быть слишком мало (тогда на карточках будет больше одного совпадения) или слишком много (тогда на карточках может вообще не оказаться совпадений).
Кроме того, очевидно, что символы расположены на карточках в особом порядке, который гарантирует единственное совпадение для любых двух карточек.

Элементарные навыки гугл-фу приводят нас на сайт stackoverflow, где описано, почему так происходит: http://stackoverflow.com/questions/6240113/what-are-the-mathematical-computational-principles-behind-this-game

В игре используются принципы конечной геометрии. Хотя в этом словосочетании есть слово «геометрия», это понятие относится больше к комбинаторике, чем к геометрии. Она оперирует конечным количеством точек, которые могут располагаться, в частности, в виде проективной плоскости.

Карточки и символы в игре являются элементами проективной плоскости 7 порядка. Это значит, что на каждой карточке n+1 символ, а общее количество уникальных символов в игре — n^2+n+1, т.е. 57 символов.

Существуют плоскости как более низких, так и более высоких порядков. Например, существует плоскость 5 порядка. Для неё на карточке изображены 6 символов, а общее количество уникальных символов в игре — 5^2+5+1 = 31. Проективная плоскость такой конфигурации используется в более простом варианте игры Доббль под названием «Доббль 1,2,3».

Связь между точками и линиями для проективной плоскости задаётся при помощи матрицы инцидентности. Её вид представлен в разделе «Матрица инцидентности для игры Доббль».

Конечная геометрия для грудничков

Много позже написания оригинальной статьи я посетил лекцию Алексея Савватеева, где он рассказал о проективной геометрии намного короче и понятнее. Но так как переписывать из-за этого половину статьи у меня нет ни сил, ни желания, то я просто рекомендую его книгу «Математика для гуманитариев», если моя попытка дикаря объяснить устройство автомобиля на пальцах будет непонятной или скучной.

Сначала зайдём на википедию и почитаем несколько статей. Первая статья описывает понятие конечной геометрии:

Конечная геометрия — это любая геометрическая система, имеющая конечное количество точек. [1]

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

Например, евклидова геометрия не является конечной, так как евклидова прямая содержит неограниченное число точек, а точнее говоря, содержит ровно столько точек, сколько существует вещественных чисел. [1]

Для нас это значит, что тот листок бумаги, на котором нарисованы наши точки, не является плоскостью с точки зрения конечной геометрии. Это просто носитель точек.

Существуют два вида геометрии на плоскости: аффинная и проективная. В аффинной геометрии используется обычное понятие параллельности прямых. [1]

Вспомним, какими аксиомами описывается афинная геометрия:

Аффинная геометрия на плоскости — это непустое множество X (элементы которого называются «точками»), с непустым набором L подмножеств X (элементы которого называются «прямая»), таких, что:

1. Для двух различных точек существует только одна прямая, которая содержит обе точки.
2. Для прямой ℓ и точки p, не принадлежащей ℓ, существует одна и только одна прямая ℓ′, содержащая p, такая, что ℓ ∩ ℓ′ = ∅ .
3. Существует множество из четырёх точек, никакие три из которых не лежат на одной прямой. [1]

Эти аксиомы дают нам возможность понять, как выглядит простейшая афинная плоскость в конечной геометрии:

Простейшая аффинная плоскость содержит лишь 4 точки, и называется аффинной плоскостью второго порядка. Каждая пара точек определяет уникальную прямую, поэтому указанная плоскость содержит 6 прямых. [1]

Не очень понятно? Всё верно. Если присмотреться к определению афинной геометрии, то можно заметить, что она оперирует с понятиями теории множеств (элемент, множество, подмножество).
Это значит, что прямые могут выглядеть совсем не как привычные прямые Евклидовой геометрии.

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

Рис. 5. Афинная плоскость второго порядка. (Источник ru.wikipedia.org)

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

Наверняка %username% до сих пор сомневается, что изображение этой плоскости удовлетворяет аксиомам афинной геометрии. Давайте проверим:

1. Берём 2 любых точки, например, левую верхнюю и левую нижнюю.
   Обе эти точки содержит только одна левая красная прямая.
   Правая красная прямая не содержит ни одной из этих точек, а остальные прямые содержат только одну из них.
2. Берём левую красную прямую и правую верхнюю точку. Очевидно, что только одна прямая (правая красная) параллельна левой красной прямой, так как проходит через правую верхнюю точку, но не проходит ни через одну из двух левых точек.
3. На рисунке хорошо видно, что какие бы 3 точки мы ни взяли, одна из них лежит на прямой, отличной от прямой, на которой лежат обе другие точки.
   Две прямых, составляющие диагонали квадрата, не пересекаются, так как не имеют общих точек.

Если вы хорошо поняли содержание предыдущей картинки, то вот картинка посложней:

Рис. 6. Афинная плоскость третьего порядка. (Источник ru.wikipedia.org)

Здесь мы видим 9 точек и 12 прямых. Да-да, %username%, эти эллипсы — на самом деле прямые в терминах конечной геометрии.
Фигуры одинакового цвета — это параллельные прямые. Их трудно заметить, поэтому разделим картинку на несколько:

Плоскость №1	Плоскость №2	Плоскость №3	Плоскость №4

Рис. 7. Параллельные прямые афинной плоскости третьего порядка.

Здесь проверка выполнения аксиом займёт чуть больше времени:

1. Берём 2 любых точки, например, центральную верхнюю и правую нижнюю. Через них проходит только одна из фиолетовых прямых.
2. Берём левую красную прямую и правую нижнюю точку. Аналогично плоскости второго порядка, только одна правая красная прямая проходит через эту точку, но не проходит ни через одну из трёх левых точек.
3. Здесь чуть сложнее, чем в случае с плоскостью 2 порядка. Формулировка аксиомы гласит, что нужно найти хотя бы одно (непустое) множество из четырёх точек, в котором никакие три не лежат не одной прямой.
   Очевидно, что 12 множеств с тремя точками, через которых проходят линии на рисунке, не удовлетворяют этому условию. Но ему удовлетворяет, например, множество из четырёх угловых точек.

В более общем случае, конечная аффинная плоскость порядка n имеет n^2 точек и n^2 + n прямых; каждая прямая содержит n точек, и каждая точка принадлежит n + 1 прямой. [1]

С афинной геометрией закончили, переходим ко второму типу геометрии на плоскости — проективной.

В проективной геометрии наоборот, любые две прямые пересекаются в единственно возможной точке, и потому параллельных прямых не существует. [1]

Предыдущее предложение описывает вторую аксиому проективной геометрии. Первая и третья — такие же, как в афинной.

Поскольку третья аксиома требует существования как минимум четырёх точек, плоскость должна содержать как минимум 7 точек, чтобы удовлетворить условиям первых двух аксиом. В этой простейшей из проективных плоскостей имеется также 7 прямых; каждая точка принадлежит трём прямым, и каждая прямая содержит три точки. Такую проективную плоскость часто называют «плоскостью Фано». [1]

Рис. 8. Плоскость Фано. (Источник en.wikipedia.org)

На этом рисунке сложно сразу разобрать все 7 прямых, так что вот пони-вариант той же плоскости:

Рис. 9. Плоскость Фано с раскрашенными прямыми. (Источник mathpuzzle.com. Используется с разрешения Ed Pegg Jr.)

Итак, плоскость Фано — это проективная плоскость 2 порядка с 7 точками и 7 линиями.

При чём тут карточки?

Что будет, если мы переформулируем 2 аксиомы конечной геометрии, заменив «прямую» на «символ» и «точку» на «карточку»?

Получится вот что:

1. Для двух различных карточек существует только один символ, который изображён на обеих карточках.
2. Для двух различных символов существует только одна карточка, которая содержит оба этих символа.

Теперь на основе этих знаний посмотрим, как выглядел бы Доббль в простейшем случае. В нём было бы 7 карточек и 7 символов, на каждой карточке было бы по 3 символа (т.к. в одной точке пересекаются 3 прямые):

Рис. 10. Пример минимально возможного набора карточек для Доббля.

Тут используются следующие 7 символов:

, , , , , ,
Какие бы 2 карточки мы ни взяли, они будут иметь общий символ, изображённый рядом с прямой, на которой лежат обе карточки.
Например, у карточки в левом нижнем углу и карточки в середине правой грани общий символ . Он изображён рядом с прямой .

Проективные плоскости малых порядков

На сайте Wolfram можно найти визуальную демонстрацию проективных плоскостей малых порядков: http://demonstrations.wolfram.com/ProjectivePlanesOfLowOrder/
Она оформлена в виде документа в формате CDF (Computable Document Format), для которого нужно установить CDF Player.

Вот пример проективной плоскости 3 порядка:

Рис. 11. Изображение проективной плоскости 3 порядка.

Трудно понять, что происходит, поэтому возьмём 2 произвольные прямые:

Рис. 12. Пересечение двух линий проективной плоскости 3 порядка.

Как мы видим, они пересекаются ровно в одной точке. Сами линии содержат по 4 точки.
Чтобы убедиться, что через каждую точку проходит 4 прямые, придётся переключать отображаемые пары прямых в интерактивном документе и сосредоточить внимание на какой-то точке.

Проективные плоскости более высоких порядков изображены на рисунках ниже.

Рис. 13. Проективная плоскость порядка 4

Рис. 14. Проективная плоскость порядка 5

Рис. 15. Проективная плоскость порядка 7

В приведённой последовательности отсутствует изображение для проективной плоскости 6 порядка. Это не ошибка.
Хотя Wolfram генерирует графическое представление такой структуры, она не удовлетворяет аксиомам проективной геометрии, и не является проективной плоскостью.

Предполагается, но до сих пор не доказано, что порядок конечной плоскости всегда является степенью простого числа. [1]

Как построить проективную плоскость?

Графическое представление проективной плоскости выглядит интересно и наглядно, но как найти такую комбинацию точек, чтобы она обладала вышеописанными свойствами?
Проще всего — посетив сайты, где размещены предрасчитанные данные для проективных плоскостей разных порядков.

Например, для проективной плоскости 7 порядка можно посетить такую страницу: https://web.archive.org/web/20170619110638/https://www.uwyo.edu/moorhouse/pub/planes/pg27.txt
Там представлена матрица из чисел. Строки — это карточки (точки) в понятиях Доббля. Числа в строках — это порядковые номера символов (линий), начиная с нуля, которые нарисованы на каждой карточке (проходят через данную точку).

Также можно воспользоваться услугами математических пакетов, таких, как Matlab, чтобы построить матрицу инцидентности проективной плоскости. [2] [3]

Матрицы инцидентности

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро (дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность). [2]

Одним из простейших примеров матрицы инцидентности может служить матрица размером 2×1 для неориентированного графа из двух вершин, соединённых одним ребром:

Рис. 16. Неориентированный граф из двух вершин, соединённых одним ребром, и его матрица инцидентности.

Более сложный пример графа и его матрицы инцидентности:

Рис. 17. Неориентированный граф с 4-мя вершинами и его матрица инцидентности.

Как видно из последнего примера, в матрице инцидентности графа в каждом столбце ровно две единицы, т.к. одно ребро соединяет две вершины.
Проективная плоскость является гиперграфом, так как одна прямая (ребро) соединяет несколько точек (вершин). Поэтому в матрице инцидентности проективной плоскости единицы в каждом столбце встречаются n+1 раз, где n — порядок проективной плоскости.

Для плоскости Фано, изображённой на рис. 9, матрица инцидентности будет иметь следующий вид:

Рис. 18. Матрица инцидентности плоскости Фано.

Для упрощения восприятия нули не показаны, а единицы заменены на символ Х.
В таком представлении проективной плоскости хорошо заметен принцип двойственности точек и прямых — прямая проходит ровно через 3 точки, и, в то же время, точка принадлежит ровно трём прямым.

Построение проективной плоскости перебором

Текущих знаний о свойствах матрицы инцидентности достаточно, чтобы построить её для проективной плоскости любого порядка n. Для этого можно использовать следующий псевдокод:

Для всех столбцов
    Для всех строк
        Если в столбце стоит n+1 единиц, то перейти к следующему столбцу
        Если в строке стоит n+1 единиц, то перейти к следующей строке
        Для каждого предыдущего столбца Х
            Если в столбце Х на текущей строке стоит единица
            и
            Если уже есть совпадения в строках для столбца Х и текущего столбца,
                то перейти к следующей строке
        Поставить единицу
    Перейти на следующую строку
Перейти на следующий столбец

Следуя этому алгоритму, мы получим симметричную матрицу для плоскости Фано:

Рис. 19. Матрица инцидентности плоскости Фано, построенная по алгоритму псевдокода.

Эта матрица не совпадает с предыдущей. На самом деле, это неважно.
Перестановка любых двух строк матрицы инцидентности равносильна перенумерации вершин графа.
Перестановка любых двух столбцов матрицы инцидентности равносильна перенумерации рёбер графа (если их заранее пронумеровать).

Матрица инцидентности для игры Доббль

Для игры Доббль в матрице инцидентности строки отвечают за карточки, а столбцы — за символы на них.
Таким образом, перестановка любых двух столбцов матрицы инцидентности равносильна изменению очерёдности следования символов на карточке. Однако, символы на карточке неупорядочены, поэтому данная операция не влияет на внешний вид карточек.
Перестановка двух строк означает, что на всех карточках два соответствующих символа заменяют друг друга.

Последняя операция меняет внешний вид карточек, а значит, что тот набор символов, который мы видим в игре — лишь одна из возможных комбинаций.
Количество наборов символов для отдельно взятой карточки есть сочетание без повторений из 57 элементов по 8 элементам. Оно вычисляется по формуле

Матрица инцидентности для игры Доббль показана в таблице ниже. Она транспонирована, т.е. строки — это символы, а столбцы — это карточки (картинка кликабельна). Хабр не даёт вставить картинку нужного размера и качества, поэтому фулсайз вариант отдельной ссылкой: https://github.com/Skybladev2/DobbleMathModel/blob/master/images/Dobble%20incidence%20matrix.png

Рис. 20. Матрица инцидентности игры Доббль.

Каких двух карточек не хватает в комплекте игры?

Всего в таблице с матрицей инцидентности игры 57 строк и 55 столбцов. Это значит, что в игре могло быть ещё 2 карточки.
Значит, символы, которые должны быть на этих карточках, встречаются в игре реже, чем остальные. Количество символов в игре показано в последнем столбце таблицы.

Количество символов с недостающих карточек таково:

• , , , , , , , , , , , , и 
  (всего 14 символов) встречаются по 7 раз.
• встречается 6 раз.

Как выглядят недостающие карточки? Для ответа на этот вопрос возьмём любой из представленных выше символов в матрице инцидентности (кроме снеговика), и поместим его на недостающую карточку (например, предпоследний столбец).
Затем найдём все карточки (столбцы), на которых изображён этот символ. Это значит, на всех этих карточках символы совпадают, и других совпадений быть не может.
Так как на этих карточках уже есть совпадение с выбранным символом, вычеркнем из предпоследнего столбца все символы, которые встречаются на остальных карточках.
Недостающие символы, которые не были вычеркнуты, и составляют символы одной из оставшихся карточек. Так как их получилось ровно 8, то вид второй недостающей карточки определяется однозначно.

Вот эти 2 карточки:

Рис. 21. Возможный вид недостающих карточек №56 и №57.

Осталось ответить на последний вопрос — не влияет ли отсутствие этих карточек на свойство совпадения единственного символа между двумя карточками (т.е. вдруг между какими-то карточками нет совпадений)?
Ответ на него очевиден, если ещё взглянуть на матрицу инцидентности игры — нет, не влияет. Между любыми двумя карточками (столбцами) по-прежнему единственное совпадение.

Почему в игре на 2 карточки меньше максимально возможного количества?

Изначально правила для пяти мини игр были не в буклете, а на пяти отдельных карточках. При этом максимум можно было напечатать лишь 60 карточек. Поэтому авторы игры решили убрать 2 карточки, чтобы в итоге получилось 55 карточек с символами + 5 карточек с правилами. (Отдельное спасибо Guillaume Gille-Naves за разъяснение).

Благодарности

Выражаю огромную благодарность сети магазинов настольных игр «Игровед» за помощь в написании статьи.
Благодарю Ed Pegg Jr за предоставленное изображение плоскости Фано.
Отдельно хочу отметить одного анонимуса и Master-а за помощь в проверке статьи.
Благодарю магазин «Настольный град» за помощь в подготовке к публикации статьи.
От всего сердца благодарю авторов игры Igor Polouchine, Denis Blanchot, Guillaume Gille-Naves, а также компанию Asmodee за предоставленное право на использование изображений из игры.

© Habrahabr.ru