Главная » Хабрахабр » Математическая модель игры Доббль

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

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

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

    • Введение и правила игры
    • Как они это делают?
    • Матрица инцидентности для игры Доббль
    • Каких двух карточек не хватает в комплекте игры?
    • Почему в игре на 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Order 2 affine plane

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

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

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

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

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

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

Order 3 affine plane

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

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

Плоскость №1

Плоскость №2

Плоскость №3

Плоскость №4

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

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

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

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

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

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

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

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

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

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

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

Итак, плоскость Фано — это проективная плоскость 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
Там представлена матрица из чисел. Числа в строках — это порядковые номера символов (линий), начиная с нуля, которые нарисованы на каждой карточке (проходят через данную точку).

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

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

Столбцы матрицы соответствуют ребрам, строки — вершинам. Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). [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. Матрица инцидентности игры Доббль. Рис.

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

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

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

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

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

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

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

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

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

вдруг между какими-то карточками нет совпадений)? Осталось ответить на последний вопрос — не влияет ли отсутствие этих карточек на свойство совпадения единственного символа между двумя карточками (т.е.

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

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Ложные срабатывания в PVS-Studio: как глубока кроличья нора

Наша команда оказывает быструю и эффективную поддержку клиентов. В поддержке принимают участие только программисты, так как вопросы нам тоже задают программисты и над многими из них приходится подумать. Хочется описать одно из недавних обращений в поддержку на тему ложного срабатывания, ...

Онлайн контест по решению задачи из теории игр

Привет, Хабр! На факультативе по теории игр мы решаем различные интересные задачи, и я хотел бы поделиться с вами одной из таких. Меня зовут Миша, и я студент. Описание игры «Я люблю вархаммер, поэтому решил адаптировать условие» Играют двое. 1. ...