Diplomacy: base de dados de movimentos para controlar províncias

• Author(s): Deyllot, Rui Jorge Gregório
• Date: 2010
• Persistent ID: http://hdl.handle.net/10773/3561
• Origin: RIA - Repositório Institucional da Universidade de Aveiro
• Subject(s): Engenharia de computadores; Jogos de computador; Inteligência artificial; Bases de dados; Desenvolvimento de software; Teoria de jogos; Teoria de decisão
• Document Type: Master Thesis
• Language: Portuguese
• Advisor(s): Mariano, Pedro Lopes da Silva; Neto, João Pedro

Description

A literatura sobre modelos e ferramentas para a construção de agentes para jogarem jogos a 2 jogadores é relativamente extensa. Algoritmos de pesquisa, bases de dados de aberturas ou com jogadas finais, ou heurísticas especialmente desenvolvidas são algumas das técnicas mais utilizadas. O Diplomacy é um jogo para 2 ou mais jogadores, que decorre num mapa que retrata o estado da Europa no início do século 20. O mapa encontra-se dividido em províncias. Certas províncias são denominadas centros de produção e o objectivo do jogo consiste no controlo de mais de metade dos centros de produção. Cada jogador controla um certo número de unidades. O factor de ramificação do jogo é elevado. Há cerca de 4 mil biliões de aberturas possíveis. No entanto há implementações que calculam a jogada que cada uma das suas unidades deve fazer. Para cada unidade é efectuada uma pesquisa local de modo a encontrar qual a acção que deve efectuar. Este trabalho apresenta uma possível abordagem a este problema que passa pela construção de uma base de dados de movimentos tendo em conta o controlo de uma província dentro de um determinado horizonte de turnos. A construção da base de dados é feita à custa de mecanismos de pesquisa de soluções e enumeração de mapas possíveis. The literacy about models and tools for the construction of agents capable of playing 2 player games is relatively extense. Search algorithms, data bases of opening or final moves, or specially developed heuristics are some of the most used techniques. Diplomacy is a game for 2 or more players in a map depicting the state of Europe in the beginning of the 20th century. The map is divided in provinces. Certain provinces are named supply centers and the goal of the game is to control more than half of the supply centers. Each player controls a certain number of units. The game’s branching factor is very high. There are about 4 thousand billion possible openings. However, there are programs that calculate the move that each one of the units should make. This work presents one possible approach to this problem by the construction of a movements database considering the control of a province within a certain number of turns. The construction of the database is made through the use of solution search and map enumeration mechanisms. Mestrado em Engenharia de Computadores e Telemática