Versão computacionalmente limitada do equilíbrio de Nash?

Gostaria de saber se existe uma versão computacionalmente limitada do conceito de equilíbrio de Nash, algo ao longo das seguintes linhas.

Imagine algum tipo de jogo de informações perfeitas para dois jogadores que é jogado em um tabuleiro , e que é complexo no sentido de que o jogo ideal é EXPTIME difícil. Suponha também, por simplicidade, que os desenhos não são possíveis. Imagine um par de máquinas de Turing aleatórias em tempo polinomial jogando esse jogo umas contra as outras. Para cada , seja a probabilidade de que$n\times n$$(A, B)$$n$$p_{A,B}(n)$ derrote B nojogo de ordem n . (Para concretização, digamos que A comece a jogar primeiro com probabilidade 0,5). O que eu acho legal seria se alguém pudesse provar a existência de um par ( A , B $A$$B$$n$$A$$(A,B)$com a propriedade de que nenhuma máquina de Turing aleatória de tempo polinomial domina A (onde " A ′ domina A " significa p A ′ , B ( n ) > p A , B ( n ) para todos suficientemente grandes n ) e da mesma forma não A máquina de Turing de tempo polinomial aleatório B ' domina B (onde " B ′ domina B " significa p A , B $A'$ $A$$A'$$A$$p_{A',B}(n) > p_{A,B}(n)$$n$$B'$$B$$B'$$B$ para todos n suficientemente grandes).$p_{A,B'}(n) < p_{A,B}(n)$$n$

De alguma forma, suspeito que isso seja demais para se esperar, mas há alguma esperança de que algo assim seja verdade, talvez para uma classe restrita de jogos?

Uma motivação para esta pergunta é que estou procurando uma maneira de formalizar a noção de que uma determinada posição no xadrez é "vantajosa para as brancas". Classicamente, uma posição é uma vitória para as brancas ou não. No entanto, os jogadores de xadrez, humanos e computadores, têm uma compreensão intuitiva do que significa que as brancas têm uma vantagem. Parece ter algo a ver com a probabilidade de as brancas vencerem, já que os jogadores são limitados computacionalmente e precisam adivinhar a melhor jogada. Para um par específico de algoritmos aleatórios, é claro que se pode falar sobre a probabilidade de as brancas vencerem, mas o que me pergunto é se pode haver, em certo sentido, um processo canônico. par de jogadores com limites computacionais cujas probabilidades de vitória rendem um valor para a posição que depende apenas do jogo em si e não das idiossincrasias dos jogadores.

Não consigo pensar em nenhuma maneira de haver uma resposta fácil, completamente elegante / satisfatória para essa pergunta, principalmente porque o pagamento final é muito difícil de calcular; no entanto, meus pensamentos são muito longos para serem postados como um comentário.

A melhor ideia que tenho é a seguinte: no caso do xadrez, tente aproximar a probabilidade de as brancas ganharem com base na vantagem material das brancas (ou seja, peões extras, cavaleiros etc.) para uma determinada posição, selecionando aleatoriamente as posições com a quantidade exata configuração de material. Talvez no caso do "xadrez com todas as torres", poderíamos dizer: "Qual a probabilidade de as brancas vencerem com 8 torres em relação às 17 torres das pretas?" Talvez essa probabilidade seja de 4%; para calculá-lo, teríamos que examinar (digamos) 1000 posições de xadrez geradas aleatoriamente diferentes, com 8 torres brancas e 17 pretas, e depois olhar para a frente (digamos) 10 movimentos profundos em todos os casos e ver qual é a nova configuração do material . Em seguida, calcule as probabilidades esperadas com base na configuração do material no final,

Obviamente, seria necessário encontrar a configuração do material para todas as possibilidades relevantes ( M , N ) de M torre branca para N torre preta ... presumivelmente começando no par mais baixo ordenado ( M = 1, N = 1) e trabalhando a partir daí.

Para a posição original, não basta ir com a estatística que você obtém (por exemplo, se a posição original tiver ( M = 6, N = 7) rooks, não apenas assuma que as brancas têm 25% de chance de ganhar, porque as chances esperadas de vitória para (6,7)); em vez disso, como você pode ser mais preciso, observe 10 movimentos profundos, como de costume, com apenas essa posição e encontre todas as posições finais possíveis. Em seguida, encontre o caminho certo (que envolve a reprodução ideal de ambos os lados) para uma configuração de 10 movimentos profundos e selecione as probabilidades esperadas desse caminho como as esperadas da posição original.

Eu acho que esse processo pode ser feito em tempo polinomial. Olhar k se move profundamente para k fixo no xadrez é polinomial no tamanho do tabuleiro, e o número total de torres brancas e pretas é expresso em unário (em certo sentido), porque esse número deve ser menor que o tamanho do tabuleiro.

Se isso parece complicado e difícil de explicar, é porque é. Um resumo mais sucinto do que estou descrevendo é: Use a recursão e as estatísticas básicas para calcular as chances de vitória do branco, com M brancas e N pretas no tabuleiro. Em seguida, use esses valores para olhar k se move profundamente e determinar as chances de as brancas vencerem na posição original.

Comentário final: acho que esse problema também é interessante para jogos que não são EXPTIME completos, como o jogo da velha, que segundo a Wikipedia é completo no PSPACE. Além disso, acredito que um processo como o que descrevi acima também pode ser útil lá também, embora obviamente seja impossível ter uma vantagem "material" no jogo da velha; teria que haver alguma outra base para julgar a superioridade da posição de X ou O.