Complexidade dos jogos de informação parcial em estado finito

12

Dado um jogo determinístico de soma zero com informações parciais determinísticas, com apenas muitos estados finitos,
cujos resultados possíveis são [perder, empatar, vencer] com valores [-1,0, + 1], respectivamente,
qual é a complexidade de se aproximar o valor de tais um jogo de forma aditiva dentro de ?ϵ

Em particular, não consigo criar nenhum algoritmo para fazer isso.
O restante desta postagem é inteiramente dedicado a fornecer uma descrição mais completa
do problema. Portanto, se você já consegue descobrir o que significa a pergunta na parte superior
desta postagem, não há motivo para ler o restante desta postagem.

Dada uma máquina de estados árbitro com , com um estado inicial designado s 0 , um estado s a cujo par de escores é [ - 1 , + 1 ] , um estado s b cujo par de escores é [ + 1 , - 1 ] e estados da forma{1,2,3,...,S}s0sa[1,+1]sb[+1,1]

que:[p1_info,p2_info,num_of_choices,player_to_move,next_state_table]

  • player_to_move{1,2}
  • é uma função de { 1 , 2 , 3 , . . . , Num_of_choices } { 1 , 2 , 3 , . . . , S }next_state_table{1,2,3,...,num_of_choices}{1,2,3,...,S}
  • p1_info,p2_info,num_of_choices1

Quando a máquina estiver em um estado dessa forma:

  • envia para Player_1 e envia p2_info para Player_2,p1_infop2_info
  • num_of_choices{1,2,3,...,num_of_choices}
  • next_state_table

sasb

  • pára com o par de pontuação desse estado como saída

s0=1





Qual é a complexidade do seguinte problema?
Dada uma máquina de arbitragem e um número inteiro positivo N, produza um número racional
que é (aditivo) dentro de 1 / N do valor do jogo natural para o Jogador 1.

Como mencionado anteriormente nesta pergunta, não consigo
criar nenhum algoritmo para fazer isso.

Marzio De Biasi
fonte
Os jogadores conhecem a estrutura interna? Qual é a vantagem de ter informações adicionais, pois oferece mais movimentos possíveis?
domotorp
Sim. Isso lhes dá uma idéia melhor de qual é o estado atual.
Desculpe, mas ainda não entendi. Então eles conhecem a estrutura interna, mas não sabem onde estão no momento? Por favor, faça a descrição clara, tenho certeza de que não sou o único que não consegue entender o problema.
domotorp
3
O seu modelo é o mesmo que um "jogo estocástico baseado em turnos de soma zero com informações parciais"?
Kristoffer Arnsfelt Hansen
1
@Kristoffer: Não é óbvio (pelo menos para mim) que meu modelo permite a codificação probabilidades irracionais, embora meu modelo seja equivalente a esse.

Respostas:

6

NOTA: meu suposto algoritmo estava incorreto; Eu deletei.

pp

Para um limite inferior sobre a complexidade, a questão de aproximar o valor de um jogo estocástica simples é não conhecido por ser em P . Usando o truque de randomização que eu dei acima, é fácil escrever um jogo estocástico simples como um jogo de arbitragem com uma tabela de pesquisa de tamanho polinomial.

Peter Shor
fonte
Essa ideia de randomização (pelo menos, como você a descreveu) só pode fornecer probabilidades racionais. Além disso, as definições usadas nos dois primeiros artigos que você vinculou também implicam que seus jogos tenham uma árvore de jogos finita, enquanto eu estou exigindo apenas um espaço de estado finito (onde "estado" não inclui o histórico do jogo).
Você está certo ... a primeira parte da minha resposta está incorreta. Deixe-me excluí-lo. Estou bastante certo de que não se sabe que aproximar o valor de jogos estocásticos simples seja em P, mesmo quando todas as jogadas de moeda têm probabilidade 1/2.
quer
1


ϵ0<ϵ

Entrada: um jogo como descrito na minha pergunta
deve gerar SIM se: o valor do jogo para o Jogador 1 for maior que 1ϵ
ϵ

permanece RE- difícil, mesmo quando

player_to_move é sempre 1 (ou seja, é necessário apenas 1 jogador)
e
s 0 ≠ s um e s um não está na Range (next_state_table)
(ou seja, é literalmente impossível para o jogador a perder)
e
p1_info e p2_info e number_of_choices são independentes do estado
(ou seja, o único feedback do jogador é se ele ganhou ou não)

.


fonte