Teoria combinatória dos jogos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Teoria de jogos combinatórios é um ramo da matemática aplicada e teoria ciência da computação que estuda jogos sequenciais com informação perfeita, ou seja, jogos de dois jogadores que têm uma posição em que os jogadores se revezam mudando de formas definidas ou se move para alcançar um condição onde ele é o vencedor. A teoria dos jogos combinatórios não estuda jogos com informação imperfeita ou incompleta (às vezes chamada de jogos de azar, como o poker). Ela limita-se a jogos cujas informações são públicas para ambos os jogadores, e no qual o conjunto de movimentos disponíveis também é público (informação perfeita)..[1] Os jogos combinatórios incluem jogos conhecidos, como xadrez, damas ,GO, Arimaa, hex, e 6 em Linha. Eles também incluem jogos de quebra-cabeças, e até mesmo jogos sem jogador, como o Jogo da Vida de Conway.[2] Na teoria dos jogos combinatórios os movimentos são representados por uma árvore de jogo.

A teoria dos jogos, de forma geral, inclui jogos de azar, jogos de conhecimento imperfeito, e os jogos em que os jogadores podem se mover ao mesmo tempo, e eles tendem a fazer representar situações de decisão da vida real. A TJC tem uma ênfase diferente do "tradicional" ou "teoria econômica" do jogo, que foi inicialmente desenvolvida para o estudo de jogos com a estrutura combinatória simples, mas com elementos do acaso (embora também considere movimentos sequenciais). Essencialmente, a TJC contribuiu com novos métodos de análise de árvores de jogo, por exemplo, usando números surreais, que são uma subclasse de todos os jogos para dois jogadores com informação perfeita. [2] O tipo de jogos estudados pela TJC também é de interesse da inteligência artificial, particularmente para o planejamento e programação automática. Na TJC, tem havido menos ênfase no refino de algoritmos de busca práticos (como a heurística da poda alfa-beta, incluída nos livros didáticos de inteligência artificial recentes), mas com mais ênfase em resultados teóricos descritivos (como medidas de complexidade de jogo ou provas da existência solução ideal, sem necessariamente especificar um algoritmo - ver estratégia de roubo de argumento , por exemplo).

Uma noção importante na TJC é a de jogo resolvido (que tem vários flavors), o que significa , por exemplo, que se pode provar que o jogo da velha resulta em empate se ambos os jogadores jogam de forma otimizada. Embora isto seja um resultado trivial, obtendo resultados semelhantes para jogos com estruturas ricas combinatórias é difícil. Por exemplo, em 2007, foi anunciado que o jogo de damas foi (fracamente , mas não fortemente) resolvido - jogadas ótimas dos dois lados também leva a um empate - mas o resultado foi uma prova assistida por computador. [3] Outros jogos do mundo real são muito complicados para permitir uma análise completa hoje em dia (embora a teoria tem tido alguns sucessos recentes na análise dos endgames do GO). Aplicar a TJC para uma posição tenta determinar a melhor seqüência de movimentos para ambos os jogadores até que o jogo termine, e ao fazê-lo descobrir o movimento ideal em qualquer posição. Na prática, este processo é tortuosamente difícil, a menos que o jogo seja muito simples .

Referências

  1. Lessons in Play, p. 3
  2. a b http://erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf
  3. doi:10.1126/science.1144079
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente