[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:53376 |
| Date | 22 June 2021 |
| Creators | HANDEL SCHOLZE MARQUES |
| Contributors | SIMON RICHARD GRIFFITHS |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0021 seconds