Игра на нескольких графиках

13

Рассмотрим следующую игру на ориентированном взвешенном графе G с чипом в некотором узле.

Все узлы G отмечены буквой A или B.

Есть два игрока Алиса и Боб. Цель Алисы (Боба) - сдвинуть фишку к узлу, обозначенному буквой A (B).

Первоначально Алиса и Боб имеют mA и mB долларов соответственно.

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

Игрок проигрывает, если он или она находится в проигрышной позиции и не имеет денег, чтобы это исправить.

Теперь рассмотрим язык GAME, который состоит из всех ориентированных взвешенных графов G (все веса являются положительными целыми числами), начальной позиции фишки и прописных букв Алисы и Боба, указанных в унарном представлении.

такой, что у Алисы есть выигрышная стратегия в этой игре.

Язык GAME принадлежит P . Действительно, текущая позиция игры определяется позицией фишки и текущими столицами Алисы и Боба, поэтому динамическое программирование работает (здесь важно, чтобы начальные заглавные буквы были указаны в унарном представлении).

Теперь рассмотрим следующее обобщение этой игры. Рассмотрим несколько ориентированных взвешенных графов G1,Gn с чипом на каждом графе. Все узлы всех графиков помечены буквами A и B. Теперь Боб выигрывает, если все фишки помечены буквой B, а Алиса побеждает, если хотя бы одна фишка помечена буквой A.

Рассмотрим язык MULTI-GAME, который состоит из всех графов G1,,Gn , начальных позиций и столиц mA и mB (в унарном представлении), так что Алиса выигрывает в соответствующей игре. Здесь важно, чтобы заглавные буквы были общими для всех графиков, поэтому речь идет не только о нескольких независимых ИГРАХ.

Вопрос В чем сложность языка MULTI-GAMES? (Это также относится к P или есть некоторые причины полагать, что эта проблема сложная?)

UPD1 Нил Янг предложил использовать теорию Конвея. Однако я не знаю, возможно ли использовать эту теорию для нескольких игр с общим капиталом.

UPD2 Я хочу показать пример, который показывает, что MULTI-GAME не очень прост. Пусть Алиса разделит свою столицуmA к некоторомуn точкиmA=a1+a2+an (она собирается использовать я доллары я -му граф). Определим б я как минимальное число такоечто я -м игры Боб выигрываетесли Алиса и Боб имеют я и б я долларов соответственно. Если b 1 + baiibiiaibib1+bn>mB (для некоторого разделенияmA=a1+a2+an ) тогда Алиса побеждает. Однако обратное неверно. Рассмотрим две копии следующего графика (изначально чип находится слева вверху A): введите описание изображения здесь

Для одного графика Боб выигрывает, если mA=0 и mB=2 или если mA=1 и mB=3 . Однако для игры с двумя копиями этого графа Боб проигрывает, если mA=1 и mB=5 . Действительно, Боб придется потратить 4 или 5 долларов , чтобы сдвинуть обе фишки на узел , отмеченный B . Затем Алиса может переместить хотя бы одну фишку в узел, помеченный буквой A. После этого у Боба нет денег, чтобы сохранить свою позицию.

UPD3 Так как вопрос для произвольных графов кажется трудным, рассмотрим конкретные графы. Обозначим узлы некоторого графа Gi , как 1,k . Мое ограничение следующее: для каждой пары i<j существует ребро от i до j и обратного ребра нет. Также существует ограничение на стоимость ребер: для i<j<k ребро от j до k не больше, чем от i до k .

Алексей Милованов
источник
4
в MULTI-GAME, что представляет собой ход? Игрок делает один ход в каждом графике? Или выбирает один график, чтобы сделать один шаг? Вы рассматривали, применима ли здесь теория игр (нагрев и охлаждение) Конвея? (Некоторые ссылки можно найти здесь: en.wikipedia.org/wiki/… )
Нил Янг,
@Neal Young Игрок выбирает один график, чтобы сделать один ход.
Алексей Милованов
FWIW, если я помню, теория игр Конвея действительно рассматривает, как играть в игры, которые составлены из других игр таким образом (в каждом ходу игрок выбирает одну из вспомогательных игр, чтобы двигаться). Я не знаю, какое отношение его теория имеет к вычислительной сложности, хотя.
Нил Янг
1
@NealYoung Спасибо, но, насколько я понимаю, проблема в том, что игроки имеют общие столицы для всех игр. Я не понимаю, как это можно исправить по теории Конвея ...
Алексей Милованов
Алиса (Боб) вынуждена перемещать чип, если он находится на узле A (B)? Каковы условия победы в мультиигре? B выигрывает также, когда все фишки находятся на узлах B, но у A все еще есть деньги? Вы говорите, что A выигрывает, если хотя бы один чип находится на A, поэтому A может просто попытаться удержать два чипа в узле, отмеченном A на «менее дорогих» двух графиках; как только B удалит одну из двух фишек от узла A, Алиса вернет ее (и проигнорирует другие графики)
Марцио Де

Ответы:

2

Поскольку ответ Стивена Стадницкого, по-видимому, не был принят запрашивающим, я подумал, что все же может быть полезно предоставить обновление: у меня есть сокращение от 3SAT до MULTI-GAME. Я не внимательно изучил ответ Стивена и не проследовал по предоставленной им ссылке, но, основываясь на следующем сокращении, я не удивлюсь, если MULTI-GAME действительно PSPACE-завершена. Однако, возможно, я не стану расширять этот результат за пределы NP-твердости.

Экземпляр 3SAT состоит из пунктов C1,,Cm , причем каждое предложение имеет вид Ci=Li1Li2Li3 где каждый Lik является одной из переменных x1,,xn или отрицание одной из переменных.

Для такого экземпляра 3SAT сокращение создает экземпляр MULTI-GAME, состоящий из n+1 игр - по одной на каждую переменную, а другая игра используется в качестве поглотителя избыточного капитала. Сначала мы определим структуру графиков для каждой игры, затем рассмотрим пример и обсудим основную идею, а затем выясним, какие именно затраты следует назначить ребрам, чтобы сделать сокращение устойчивым.

Сначала переменный игровой граф Gj для каждой переменной xj :

  1. Создайте вершину с меткой xj помеченную буквой A (т. Е. Выигрышную вершину для Алисы). Фишка для Gj начинается в вершине xj .
  2. Создайте вершину, помеченную буквой T и вершину, помеченную буквой F , каждая из которых помечена буквой B (то есть обе являются выигрышными позициями для Боба). Создайте направленные ребра от xj до T и F , оба с ценой 1 .
  3. Для каждого литерала Lik предложения Ci , если Lik=xj или Lik=¬xj , создайте вершины с меткой CiTA и CiFA помеченные A, и вершины, помеченные CiTB и CiFB помеченный буквой B. Добавьте ребра (T,CiTA) и(F,CiFA) с затратами, установленными вlik . (Мы определимlik позже.)

    Добавьте ребра (CiTA,CiTB) и (CiTA,CiTB) . Если Lik=xj , то установите стоимость ( C i T A , C i T B ) равной l i k - 1 и ( C i T A , C i T B ) , то стоимость l i k . В противном случае установите ( C i T A , C i T B )(CiTA,CiTB)lik1(CiTA,CiTB)lik(CiTA,CiTB) равной lik а стоимость (CiTA,CiTB) равной lik1 .

Столичная раковина игры:

  1. Создайте вершину, помеченную буквой C , помеченную буквой B.
  2. Для каждого предложения Ci создайте вершину с меткой CiA помеченную буквой A, и вершину с меткой CiB помеченную буквой B. Создайте ребро (C,CiA) со стоимостью ребраci (снова будет определено ниже) и ребро(CiA,CiB) также со стоимостью ребраci .

Это много, чтобы принять, так что, надеюсь, пример делает это немного более усваиваемым. Наш экземпляр 3SAT выглядит следующим образом:

C1=x1x2¬x3

C2=x2x3¬x4

C3=¬x1¬x3x4

Сокращение превращает этот экземпляр в 4 переменных игровых графа и 1 граф поглощения капитала. На диаграммах ниже красные вершины отмечены буквой A (т. Е. Являются выигрышными позициями для Алисы), а голубые вершины отмечены буквой B (это выигрышные позиции для Боба).

График для x1 :

введите описание изображения здесь

График для x2 :

введите описание изображения здесь

x3

введите описание изображения здесь

x4

введите описание изображения здесь

График для капитального стока:

введите описание изображения здесь

Идея заключается в следующем:

nn

cilikCi

Стратегия Алисы в предложении Ci : пусть Ci=Li1Li2Li3 . Для каждого k{1,2,3} , если Lik=xj или ¬xjCi?AxjCiA

(Ci?ACiTACiFA

CiCili1+li2+li3+ciCi1cilik значения и стартовые капиталы Алисы и Боба должны гарантировать, что указанная скидка является решающим фактором при победе Алисы или Боба.

b=m+1

lik=2b10+ib2kk{1,2,3}

ci=3b10+b8k=13ib2k

9b10+b8

9b10+b8+n1.

m

Cili1+li2+li3+ci=9b10+b81n

CiCi

Если открытие Боба удовлетворяет всем условиям, мы можем поспорить об ограничениях параметров Алисы, которые исключают любую другую возможность победы Алисы. Обратите внимание, что порядок, в котором Алиса делает свои ходы, не имеет значения, поскольку ответы Боба являются вынужденными, и общий капитал, который Бобу потребуется для ответа на ходы Алисы, не изменяется в соответствии с порядком ходов Алисы.

  • 5b10
  • 9b10+3b83b7>9b10+2b88b10+2b8+b7
  • 8b10+4b7

b10b89b10+b8CiAb10b8k=13ib2k1

  • lj3Cj3b5
  • lj3li3lj3j>i(i+1)b6lj3j<il(ij)3b6 термин порядка в оставшемся бюджете Боба. Но тогда либоb2b2

li2li1Cilik1


Замечание к моему предыдущему ответу: задним числом очевидно, что для варианта MULTI-GAME, описанного в TABLE-GAME, который я определил в комментариях к этому ответу, DP в виде рюкзака достаточно, чтобы определить, какой игрок имеет выигрышную стратегию. Вы можете утверждать, что лучшая стратегия Боба - всегда реагировать на проигрышное состояние в данном игровом столе с минимально возможными инвестициями (это не может отрезать последующий ход для Боба, который он имел бы в противном случае), и оттуда, что заказ ходов Алисы не имеет значения. Затем возникает вопрос выбора доли капитала Алисы между играми таким образом, чтобы сумма минимальных выигрышных ответов Боба над этими играми превышала его бюджет, что можно переосмыслить как проблему типа рюкзака, которая имеет DP за полиномиальное время из-за до одинарного представления затрат. (Мой рецидив на самом деле будет

n

Я не особо задумывался о вашем особом случае с UPD3 . Я подозреваю, что это также NP-hard, потому что мои переменные гаджеты с первого взгляда кажутся такими, что они могут быть адаптированы к этим ограничениям, но я, вероятно, не буду вдаваться в подробности.

gdmclellan
источник
0

Обновление: скорее всего, неверное, оставив на данный момент запись о том, что исследовали проспект. Смотрите комментарии.

Обновление 2: определенно неверно.

G=(V,E)V={1,2,3}E={(1,2),(2,3)} , вершины 1, 2, 3 помечены как B, A, B соответственно, а ребрам назначены затраты, равные 1.

mA=mB=2G1=G2=G3=G трех игр, , причем все три игры начинаются с вершины 1. Очевидно, что Алиса не может выиграть эту игру.

M[3,2,2]2u,uv,2vM[2,2u,2v]=BW[3,u,v]=B . Еслиu=1u=2M[2,2u,2]=Au=0W[3,u,2]=A .

uv приводит к сбою повторения в экземпляре в обновлении 2 вопроса.


mA,mB,G1,,Gn,

предвычисления

W[k,x,y]={Aif Alice wins GAME on Gk with initial funds x for Alice and y for Bob,Botherwise

xmAymB .

M[k,x,y]kxmAymBM[k,x,y]=BA

M[1,x,y]=W[1,x,y]

а также

M[k+1,x,y]=Bif and only ifvu,W[k+1,u,v]=BandM[k,xu,yv]=B.

M[n,mA,mB]=A

gdmclellan
источник
Ваш алгоритм неверен. Посмотрите на график на картинке в моем посте. Рассмотрим МУЛЬТИ-ИГРУ с двумя такими графиками. Здесь W [1,0,2] = W [2,0,2] = B и W [1,1,3] = W [2,1,3] = B. Однако для МУЛЬТИ-ИГРЫ с m_A = 1 и m_B = 5 победа Алисы
Алексей Милованов
u
@AlexeyMilovanov с изменениями в квантификаторах повторение должно пройти для примера. Но вы поставили под сомнение этот подход. Кажется, что это может потребовать, чтобы Боб выложил единственное распределение средств, которое превосходит все распределения, которые Алиса могла придумать. Тем не менее, я не уверен, что меня убедили в главной идее: эта проблема на самом деле не в игре. Известно ли что-нибудь о связанной проблеме, когда каждый экземпляр GAME заменяется простой таблицей, описанной выше?
gdmclellan
Таблица W не определяет победителя. Я не знаю, правда ли это для какой-то другой таблицы ...
Алексей Милованов
@AlexeyMilovanov Таблица W по определению определяет победителя экземпляров GAME, изолированных для какого-либо конкретного входного графика. Я не уверен, почему ты сказал бы иначе. Я обновил свой ответ контрпримером, хотя, в случае, если были какие-то длительные сомнения, что это было неправильно.
gdmclellan
0

[n]n+1n0i+1i0i<n00n[n]n00

Gαβα[i]ββ[j][k]j<kαββ[j][k][k][i]{i{jk}}

Стивен Стадницки
источник
1
Доказательства в тезисе, кажется, используют большие значения i, j и k в играх. Обратите внимание, что здесь все веса могут быть приняты в большинстве столиц игроков, которые были представлены в одинарных.
Антти Ройско
@ AnttiRöyskö Тогда мне придется более внимательно взглянуть на доказательства; Я полагаю, что результат о полноте PSPACE эндшпилей Go использует результат тезиса и также предполагает унарный подсчет (поскольку там i / j / k определяется размерами областей доски).
Стивен Стадницки
αβ0
αβα[i]>[j]j+1[i][j]
αβn