|
|
|
| >>Introduction | |
| Background | |
| Algorithm Definition | |
| Experimental Evaluation | |
| Future Work | |
| Screenshots | |
| Conclusions |
Capture the Flag Using Mini-maxGregg Herlacher '04 (CS) / Craig Lowe '04 (CS)
|
|
Introduction:
The program we have created is a game in which artificially intelligent opponents are meant to play a human. The objective of each team is to capture the opposing teams flag and bring it safely back to their side. An interesting additive to the game is that unlike typical games where information is complete, in our version of capture the flag the whole playing field is not visible to the players. This adds a difficulty in the agents because they have to make assumptions as to where their opponents are. This could be related to any type of situation where information about what action to take is based only on a subset of data. Our basic approach is to use a mini-max algorithm with alpha-beta pruning in which its predictions of min and max moves are based on assumptions of what another player would optimally do. The resolution from observing human interaction with the game as well as computer versus computer there arise many surprising as well as disappointing conclusions. A human agent would often encounter some trouble playing the mini-max agents. This was our main goal, to have a challenging opponent for human players. Unfortunately, as creators of the game and very aware how our mini-max agents were likely to operate, we were able to make a hard-coded agent that was able to give our artificially intelligent agents much difficulty. This shows that mini-max can be implemented in a situation of incomplete information but its effectiveness is still open to discussion. |