Título
[en] COMBINATORIAL GAMES AND THE NEIGHBORHOOD CONJECTURE
Título
[pt] JOGOS COMBINATÓRIOS E A CONJECTURA DA VIZINHANÇA
Autor
[pt] HANDEL SCHOLZE MARQUES
Vocabulário
[pt] HIPERGRAFOS
Vocabulário
[pt] METODO PROBABILISTICO
Vocabulário
[pt] PROBLEMA DE SAT
Vocabulário
[pt] JOGOS COMBINATORIOS
Vocabulário
[en] HYPERGRAPHS
Vocabulário
[en] PROBABILISTIC METHOD
Vocabulário
[en] SAT
Vocabulário
[en] COMBINATORIAL GAMES
Resumo
[pt] A teoria dos Jogos Combinatórios é o estudo de jogos com informação
completa. Isso é, todos os jogadores conhecem todos os possíveis movimentos,
além disso, temos que não há sorte ou a habilidade de realizar um movimento,
então, em teoria jogar perfeitamente é possível. Exemplos de jogos assim são
jogo da velha, xadrez, damas, Nim... a lista continua. Nessa dissertação focamos
no jogo Maker-Breaker. Ele tem dois jogadores que sequencialmente escolhem
um vértice de um hipergrafo. O objetivo de Maker é escolher todos os vértices
de uma aresta e o objetivo de Breaker é prevenir isso. Para entender em quais
tipos de hipergrafos Maker ou Breaker ganha e quais são as estratégias de
vitória utilizamos SAT, probabilidade, teoria dos grafos em geral e mais.
Resumo
[en] The theory of Combinatorial Games is the study of games with perfect
information. This means that all players have knowledge of all possible moves,
also there isn t luck or skill to perform a move, so, in theory perfect play is
possible. Examples of games like these are tic-tac-toe, chess, checkers, Nim...
the list goes on. In this dissertation we focus on the Maker-Breaker game. It
has two players that pick a vertex from a hypergraph. The goal of Maker is
to claim all vertices of an edge and the goal of Breaker is to prevent it. To
understand in which types of hypergraphs does Maker or Breaker win and
what are the winning strategies, we make use of SAT, Probability, general
Graph Theory and more.
Orientador(es)
SIMON RICHARD GRIFFITHS
Banca
NICOLAU CORCAO SALDANHA
Banca
SIMON RICHARD GRIFFITHS
Banca
MAURICIO DE LEMOS RODRIGUES COLLARES NETO
Banca
TAISA LOPES MARTINS
Catalogação
2021-06-22
Apresentação
2021-04-30
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
INGLÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=53376@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=53376@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.53376
Arquivos do conteúdo
NA ÍNTEGRA PDF