Booijink, B. (2005) Strategy Evolution and Resolution Deduction in Diplomacy. Master's Thesis / Essay, Artificial Intelligence.
|
Text
AI_Ma_2005_BBooijink.CV.pdf - Published Version Download (2MB) | Preview |
Abstract
Diplomacy is a strategic game for seven players. Each player represents a European empire in the early years of the twentieth century with which he tries to conquer Europe. The players have the disposal of armies and fleets (units) to achieve this goal. The game proceeds in rounds. Each round all players simultaneously reveal orders for their units. All orders together determine which are actually carried out and which are not; orders may hinder or support other orders. Usually, Diplomacy players have the opportunity to negotiate with each other. This work focuses on a variant of Diplomacy, no-press, in which negotiation is not allowed. Game theory is a research area in artificial intelligence that investigates the interaction between human beings. Party games provide an excellent domain for such research. Games with large search spaces are particularly interesting. Diplomacy surpasses even Go in this regard, so classic search algorithms do not stand a chance in Diplomacy. More intelligent techniques are required to fathom Diplomacy. This work aims at logic-based Diplomacy order processing and at evolutionary Diplomacy strategy forming. To this length the goal is to develop a logic-based resolution model and an evolutionary player model with the following specifications: the resolution model must determine the correct board state, resulting from any set of orders, within insignificantly small response times, compared to those of human players. The player model must perform better than a random playing model, with response times of less than five minutes. A logic language was designed to describe orders and other aspects of the game. This thesis covers the development of the Diplomacy resolution model 'Atlas', that processes Diplomacy orders by using logical deduction. This model passes through a number of stages in which logic compounds of growing complexity are deduced, until the solution is explicitly kiiown. In this manner, more complex deduction techniques are only applied to more complex cases. Ares allows for the simulation of Diplomacy games and enables player models to foresee the consequences of orders. The resolution model Atlas was tested on a set of 153 game situations that is assumed to include cases of all complexities. Atlas produced the correct resolution in all cases, given the restriction on orders to always be complete and correct. During 128 game simulations Atlas resolved 13323 game situations in an average of 8.8 milliseconds per resolution. Simpler cases were resolved faster than more complex cases. Atlas is accurate and efficient, given the restrictions, and thereby complies with the stated specifications. Logical deduction is a profound basis for Diplomacy resolution and possibly also for logistics and management problems. Decisions would then need to be represented with multiple options, instead of binary Future research should show the attainability of such applications. This thesis also describes the design of an artificially intelligent Diplomacy player model, based on evolutionary computing on strategies. The model represents action alternatives for the situations it is expected to meet. The genetic fitness of action series is determined by the evaluations of the game situations that those series bring forth. The model repeatedly creates new action alternatives by mutating actions in the fittest series. In this manner, the best action series is gradually improved. A simultaneous process searches for actions of the opponents. These counter-actions are mutated to yield game situations with low evaluations; the model assumes that its opponents will continuously counter him. The consistency of Ares' actions was investigated by repeatedly making this model generate opening actions, playing 'Germany'. A relation with the most popular openings for the same empire, as observed during internet games between human players was not found. Ares was set up against a random playing model in 128 Diplomacy games. In each game a unique combination was used to assign the two models to the seven empires. Each game was ended when one of the players reached a victory (109 games) or after 218 rounds (19 games). In the case of a victory, the winner takes one point and in pre-ended games, one point was split equally between the survivors. Ares collected 123.0 points (96.l% of the available points) against 5.0 points (3.9%) for the random playing model. With the used parameter settings in the game simulations (a produced strategy with depth two, of the tenth generation) Ares has response times of approximately one minute. Ares plays better than a random playing model, within five minutes per action and thereby complies with the stated specifications. Evolutionary computing is a hopeful technique in automated strategy forming. Possibly, this technique is better applicable to games in which the imperfectness of information is lower than in Diplomacy, like Stratego or Scotland Yard. The application of strategy evolution to Diplomacy leaves many possibilities for improvement We could try to combine the intentions for similar game situations. Also, we could investigate the influence of trust and negotiations on strategy forming in standard Diplomacy, where players are allowed to negotiate. Finally, it might be interesting to investigate combinations of evolutionary computing with other promising A! Diplomacy playing techniques, like evaluationbased and goal-based approaches. The former tries to move units towards highly evaluated areas and the latter generates attainable goals and chooses the best possible combination of goals to pursue.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Degree programme: | Artificial Intelligence |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 15 Feb 2018 07:30 |
| Last Modified: | 15 Feb 2018 07:30 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/9003 |
Actions (login required)
 |
View Item |