Jogos combinatórios

Consideraremos um jogo combinatório como um jogo de informação perfeita (ou seja, ambos os jogadores vêm todo o estado do jogo a todos os momentos) e que são sequenciais (ou seja, baseados em turnos). Além disso, focamo-nos em jogos com dois jogadores. Para exemplificar este tipo de jogos, podemos pensar no xadrez, que, apesar de ser um jogo mais complexo e que por isso não será abordado, é um tipo de jogo que entra nesta definição.

Com esta definição, podemos pensar em vários tipos de problemas interessantes que nos pedem para resolver ou jogar de alguma forma um destes jogos. Mas o que significa resolver um jogo? Este conceito está relacionado com "jogadas ótimas" ou "jogadas perfeitas" que são as melhores jogadas possíveis que um jogador pode jogar. Um jogador que joga de forma ótima é um jogador que joga sempre uma jogada que lhe garante o melhor resultado possível, independentemente das jogadas do seu adversário.

Assim, vamos ver alguns exemplos clássicos e ainda alguma teoria geral deste tipo de jogos. Muitas vezes o importante é determinar unicamente o estado do jogo e com isso é possível aplicar métodos conhecidos como programação dinâmica.

Jogos combinatórios

Visto que já temos a definição bem estudada, vamos ler um pouco sobre este tipo de jogos.

O artigo anterior fala de muitos conceitos em pouco tempo, por isso pode ser importante consolidá-los com uma visão de outro ponto de vista:

* Grundy numbers

Um tema que foi brevemente abordado em ambos os artigos que já vimos é o de Grundy numbers. Este conceito está relacionado com um teorema que nos permite combinar jogos que sejam independentes. Se quiserem aprender mais sobre o assunto, numa perspetiva relacionada com concursos, aqui têm mais um artigo:

Aplicações

Finalmente, testem o que viram com dois problemas simples que misturam a teoria de jogos combinatórios com outros temas de concursos.