Teoria dos jogos combinatórios

A teoria dos jogos combinatórios, também conhecida como CGT é um ramo da matemática aplicada e da ciência da computação teórica que estuda jogos combinatórios, e é distinta da teoria dos jogos "tradicionais" ou "econômicos". A CGT surgiu em relação à teoria dos jogos imparciais, o jogo de dois jogadores de Nim em particular, com ênfase na "solução" de certos tipos de jogos combinatórios.

Um jogo deve atender a várias condições para ser um jogo combinatório. Estas são:

O jogo deve ter pelo menos dois jogadores.
O jogo deve ser seqüencial (ou seja, os jogadores alternam os turnos).
O jogo deve ter informações perfeitas (ou seja, nenhuma informação está escondida, como no Poker).
O jogo deve ser determinístico (ou seja, não-corrente). A sorte não faz parte do jogo.
O jogo deve ter uma quantidade definida de movimentos possíveis.
O jogo deve eventualmente terminar.
O jogo deve terminar quando um jogador não pode mais se mover.

A Teoria dos Jogos Combinatórios está em grande parte confinada ao estudo de um subconjunto de jogos combinatórios que são dois jogadores, finitos, e têm um vencedor e um perdedor (ou seja, não terminam em sorteios).

Estes jogos combinatórios podem ser representados por árvores, cada vértice do qual é o jogo resultante de um movimento particular do jogo diretamente abaixo dele sobre a árvore. A estes jogos podem ser atribuídos valores de jogo. Encontrar estes valores de jogo é de grande interesse para os teóricos de CG, assim como o conceito teórico de adição de jogo. A soma de dois jogos é o jogo no qual cada jogador de sua vez deve se mover em apenas um dos dois jogos, deixando o outro como estava.

Elwyn Berlekamp, John Conway e Richard Guy são os fundadores da teoria. Eles trabalharam juntos nos anos 60. Seu trabalho publicado foi chamado Winning Ways for Your Mathematical Plays (Caminhos vencedores para suas peças matemáticas).

Definições

Na teoria, há dois jogadores chamados de esquerda e direita. Um jogo é algo que permite à esquerda e à direita fazer jogadas para outros jogos. Por exemplo, no jogo de xadrez, há uma configuração inicial usual. No entanto, pode-se também pensar em um jogo de xadrez após a primeira jogada como um jogo diferente, com uma configuração diferente. Portanto, cada posição também é chamada de jogo.

Os jogos têm a notação {L|R}. L {L} $L$ são os jogos para os quais o jogador esquerdo pode se mover. R {\an8} $R$ são os jogos para os quais o jogador direito pode se mover. Se você conhece a notação de xadrez, então a configuração usual do xadrez é o jogo

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } estilo de jogo |a3,a4,Na3,b3,b4,c3,c4,Nc3,|dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,|dots $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Os pontos "..." significam que há muitos movimentos, portanto nem todos são mostrados.

O xadrez é muito complexo. É melhor pensar em jogos mais fáceis. Nim, por exemplo, é muito mais simples de se pensar. Nim é jogado desta forma:

Há zero ou mais pilhas de balcões.
Em um turno, um jogador pode tirar quantos balcões de uma pilha quiser.
O jogador que não pode fazer uma jogada perde.

O jogo mais fácil de Nim começa sem nenhum contador! Em tal caso, nenhum dos jogadores pode se mover. Isso é mostrado como {||}. Ambos os lados estão vazios, porque nenhum dos jogadores pode se mover. O primeiro jogador a ir não pode se mover, e por isso perderá. Em CGT, as pessoas costumam escrever {|} como o símbolo 0 (zero).

O jogo mais próximo tem apenas uma pilha, com apenas um contador. Se o jogador esquerdo for primeiro, esse jogador deve pegar o contador, deixando a direita sem movimentos ({|}, ou 0). Se, em vez disso, o jogador da direita for o primeiro, não haverá mais jogadas para a esquerda. Assim, tanto a esquerda quanto a direita podem fazer um movimento a 0. Isso é mostrado como {{|}|{|}}, ou {0|0}. O primeiro jogador a se mover ganhará. Jogos iguais a {0|0} são muito importantes. Eles estão escritos com o símbolo, * (estrela).

Perguntas e Respostas

P: O que é a Teoria Combinatória do Jogo?

R: A Teoria Combinatória dos Jogos (CGT) é um ramo da matemática aplicada e da informática teórica que estuda jogos combinatórios, e é distinta da teoria "tradicional" ou "econômica" dos jogos.

P: Que condições um jogo deve satisfazer para ser considerado um jogo combinatório?

R: Para que um jogo seja considerado um jogo combinatório, ele deve ter pelo menos dois jogadores, deve ser sequencial (ou seja, os jogadores alternam turnos), deve ter informação perfeita (ou seja, nenhuma informação é escondida), deve ser determinista (ou seja, não pode ser uma oportunidade), a sorte não pode fazer parte do jogo, deve haver uma quantidade definida de movimentos possíveis, o jogo deve eventualmente terminar, e o jogo deve terminar quando um jogador não pode mais se mover.

P: Em que tipo de jogos a Teoria Combinatória do Jogo se concentra?

R: A Teoria do Jogo Combinatório se concentra principalmente em jogos finitos de dois jogadores que têm vencedores e perdedores (ou seja, não terminam em empates).

P: Como esses tipos de jogos são representados?

R: Esses tipos de jogos podem ser representados por árvores, com cada vértice representando o jogo resultante de uma determinada jogada, diretamente abaixo dele na árvore.

P: Quais são alguns objetivos para os teóricos de GC?

R: Alguns objetivos para os teóricos de GC incluem encontrar valores para esses tipos de jogos, bem como compreender o conceito de "adição de jogo", que envolve cada jogador fazer apenas uma jogada em dois jogos diferentes, deixando a outra inalterada durante sua vez.

P: Quem fundou a CGT?

R: Elwyn Berlekamp, John Conway e Richard Guy são creditados com a fundação da CGT em seu trabalho publicado chamado Winning Ways for Your Mathematical Plays nos anos sessenta.