Учитывая детерминированную игру с нулевой суммой частичной информации только с конечным числом состояний,
чьи возможные результаты [проиграть, сыграть, выиграть] со значениями [-1,0, + 1] соответственно,
какова сложность аппроксимации значения такого игра аддитивно в ?
В частности, я не могу придумать какой-либо алгоритм для этого.
Остальная часть этого поста целиком посвящена более подробному описанию
проблемы, поэтому, если вы уже можете понять, что
означает вопрос в верхней
части этого поста, у вас нет оснований читать остальную часть этого поста.
Учитывая судейскую машину состояний , с указанным начальным состоянием s 0 , состоянием s a, чья пара очков равна [ - 1 , + 1 ] , состоянием s b, чья пара очков есть [ + 1 , - 1 ] , и состояниями вида
где:
- является функцией от { 1 , 2 , 3 , . , , , Num_of_choices } → { 1 , 2 , 3 , . , , , S }
Когда машина находится в состоянии этой формы:
- отправляет Player_1 и отправляет p2_info Player_2,
- останавливается с парой очков этого состояния в качестве выходного
Какова сложность следующей проблемы?
Учитывая такую машину рефери и положительное целое число N, выведите рациональное число
, которое (аддитивно) находится в пределах 1 / N от значения натуральной игры для игрока 1.
Как упоминалось ранее в этом вопросе, я не могу придумать
какой-либо алгоритм для этого.
источник
Ответы:
ПРИМЕЧАНИЕ: мой предполагаемый алгоритм был неверным; Я удалил это.
Для более низкой оценки на сложностях, вопрос аппроксимации значения простой стохастической игры является не известен, что в P . Используя трюк рандомизации, который я привел выше, легко написать простую стохастическую игру в качестве рецензируемой игры со справочной таблицей полиномиального размера.
источник
Входные данные: игра, как описано в моем вопросе,ϵ
ϵ
должна вывести ДА, если: значение игры для Игрока 1 больше 1-
остается RE- трудным, даже когда
player_to_move всегда равен 1 (т. е. требуется только 1 игрок),
а
s 0 ≠ s a и s a не находятся в диапазоне (next_state_table)
(т. е. игрок буквально не может проиграть),
а также
p1_info и p2_info и number_of_choices не зависят от состояния
(т. е. единственная обратная связь игрока заключается в том, выиграл он или нет)
,
источник