Sobre a Complexidade de Jogos Combinatórios
Autores
|
4242 |
257,1888
|
|
|
4243 |
257,1888
|
Informações:
Publicações do PESC
Jogo combinatório é um jogo de dois jogadores, I e II, onde cada jogador faz um lance por vez e I é o primeiro a jogar. As regras de movimentação, bem como as de término do jogo, são bem definidas. A todo momento ambos os jogadores possuem total informação sobre quais os possíveis próximos lances do oponente (não há elementos secretos ou aleatórios). São exemplos populares de jogos combinatórios: Xadrez, Dama e GO. Neste trabalho estudamos a complexidade de jogos combinatórios com particular interesse na classe PSPACE, classe que concentra um grande número de jogos combinatórios. Para estudar esta classe exibimos resultados clássicos sobre complexidade de espaço. Consideramos os jogos GEOGRAPHY, HEX, GO e G1 como nossos exemplos de jogos combinatórios difíceis e desenvolvemos a teoria tendo esses jogos como base. Para tal, consideramos como modelos de computaçãoo: Máquina de Turing determinística, não determinística e alternada, onde a última é uma generalização das duas primeiras.
A combinatorial game is a game with two players, I and II, where each player makes a move at a time, and I is the first to play. The rules of the game as well as the rule to finish the game are well defined. At each time, both players have all knowledge about the subsequent movements of the other player (there are no secret nor random elements). Chess, Checkers and GO are popular examples of combinatorial games. In this work, we study the complexity of combinatorial games. The PSPACE class is studied as a space complexity class containing most of the combinatorial games. We consider the games: GEOGRAPHY, HEX, GO and G1 as examples of hard combinatorial games. We consider as models of computation the following variations of Turing machines: deterministic, nondeterministic and alternating, in which the latter is a generalization of the two former ones.