Игра на чипсете

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

Каждая вершина имеет количество «фишек», указанное в ее переменной состояния. При каждом срабатывании выбирается вершина и одна из ее фишек передается каждому соседу (вершине, с которой она имеет общее ребро). Количество фишек на каждой вершине не может быть отрицательным. Игра заканчивается, когда стрельба становится невозможной.

Определение

Пусть конечный граф G связен с и не имеет петель вершинами V = {1, 2, . . . , н }. Пусть deg( v ) — степень вершины, а e( v,w ) — количество ребер между вершинами v и w . Конфигурация или состояние игры определяется путем присвоения каждой вершине неотрицательного целого числа s ( v ), представляющего количество фишек в этой вершине. Ход начинается с выбора вершины w , у которой количество фишек не меньше ее степени : s ( w ) ≥ deg( w ). Вершина w запускается , перемещая один чип из w вдоль каждого инцидентного ребра в соседнюю вершину, создавая новую конфигурацию. $s'$ определяется:

$s'(w)=s(w)-\deg(w)$

и для v ≠ w ,

$s'(v)=s(v)+e(v,w).$

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

Если количество фишек меньше количества ребер, игра всегда конечна и достигает устойчивого состояния.
Если в каждой вершине меньше фишек, чем ее степень, игра конечна.

Если количество фишек не меньше количества ребер, игра может быть бесконечной и никогда не достигать стабильного состояния при правильно выбранной начальной конфигурации.
Если количество фишек более чем в два раза превышает количество ребер минус количество вершин, игра всегда бесконечна.

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

Долларовые игры

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

Вариант Бейкера и Норин

В этой долларовой игре некоторым вершинам конечного графа G присваиваются отрицательные целые значения (представляющие долг) . Игра называется выигрышной , если существует состояние, в котором все вершины можно сделать положительными. ^[2] Теоретико-графовый аналог теоремы Римана – Роха можно использовать для определения того, можно ли выиграть в игре или нет. ^[2]^[3]

Вариант Биггса

В вариантной форме запуска фишек, тесно связанной с моделью песочницы , также известной как игра в доллары, одна специальная вершина q обозначается как банк и ей разрешается влезать в долги, принимая отрицательное целое значение s ( q ). < 0. Если любая другая вершина может стрелять, банк не может стрелять, а только собирает фишки. В конце концов, q накопит столько фишек, что ни одна другая вершина не сможет запустить: только в таком состоянии вершина q может запускать фишки в соседние вершины, чтобы «запустить экономику».

Набору состояний, которые являются стабильными (т. е. для которых может сработать только q ) и рекуррентными для этой игры, можно придать структуру абелевой группы , которая изоморфна прямому произведению $\mathbb {Z}$ и группа песочниц (также называемая группой Якобиана или критической группой). Порядок последнего является номером дерева графа. ^[4]^[5]

См. также

Ссылки

^ Бьёрнер, Андерс ; Ловас, Ласло ; Шор, Питер В. (1991). «Игры с чип-файтингом на графах» . Европейский журнал комбинаторики . 12 (4): 283–291. дои : 10.1016/S0195-6698(13)80111-4 . МР 1120415 . Кнауэр, Коля (2009). «Чип-выстрел, антиматроиды и многогранники». Европейская конференция по комбинаторике, теории графов и приложениям (EuroComb 2009) . Электронные заметки по дискретной математике. Том. 34. С. 9–13. дои : 10.1016/j.endm.2009.07.002 . МР 2591410 .
^ Jump up to: Перейти обратно: ^а ^б Бейкер, Мэтью; Норина, Сергей (2007). «Теория Римана–Роха и Абеля–Якоби на конечном графе» . Достижения в математике . 215 (2): 766–788. дои : 10.1016/j.aim.2007.04.012 .
^ Ламболья, Сара; Улирш, Мартин. «От долларовой игры к теореме Римана-Роха» . Снимки современной математики из Обервольфаха . doi : 10.14760/SNAP-2021-001-EN .
^ Биггс, Норман Л. (25 июня 1997 г.). «Сброс чипов и критическая группа графа» (PDF) . Журнал алгебраической комбинаторики : 25–45 . Проверено 10 мая 2014 г.
^ викидот. «Ссылки на чип-старение» . Проверено 19 мая 2014 г.

А. Бьорнер, Л. Ловас: Игры со стрельбой чипами на ориентированных графах. Журнал алгебраической комбинаторики, декабрь 1992 г., том 1, выпуск 4, стр. 305–328. два : 10.1023/A:1022467132614

Внешние ссылки

Курс MIT 18.312: Алгебраическая комбинаторика
Агостон Вайс: Игра в броски по шайбе. Диссертация, ELTE TTK Bsc, 2014 г. ^{[ постоянная мертвая ссылка ]}
Исследование обжига чипов в исследовательской группе Egerváry
Игры, построенные на чипах (2010 г.). Архивировано 11 июля 2017 г. на Wayback Machine.
Долларовая игра - видео для любителей цифр о долларовом варианте игры Бейкера и Норин.
https://thedollargame.io/ — игра, основанная на варианте долларовой игры Бейкера и Норин.

[1] Бьёрнер, Андерс ; Ловас, Ласло ; Шор, Питер В. (1991). «Игры с чип-файтингом на графах» . Европейский журнал комбинаторики . 12 (4): 283–291. дои : 10.1016/S0195-6698(13)80111-4 . МР 1120415 . Кнауэр, Коля (2009). «Чип-выстрел, антиматроиды и многогранники». Европейская конференция по комбинаторике, теории графов и приложениям (EuroComb 2009) . Электронные заметки по дискретной математике. Том. 34. С. 9–13. дои : 10.1016/j.endm.2009.07.002 . МР 2591410 .

[:0-2] Jump up to: Перейти обратно: ^а ^б Бейкер, Мэтью; Норина, Сергей (2007). «Теория Римана–Роха и Абеля–Якоби на конечном графе» . Достижения в математике . 215 (2): 766–788. дои : 10.1016/j.aim.2007.04.012 .

[3] Ламболья, Сара; Улирш, Мартин. «От долларовой игры к теореме Римана-Роха» . Снимки современной математики из Обервольфаха . doi : 10.14760/SNAP-2021-001-EN .

[4] Биггс, Норман Л. (25 июня 1997 г.). «Сброс чипов и критическая группа графа» (PDF) . Журнал алгебраической комбинаторики : 25–45 . Проверено 10 мая 2014 г.

[5] викидот. «Ссылки на чип-старение» . Проверено 19 мая 2014 г.

[1]

[2]

[3]

[4]

[5]