Artificiel intelligence, ai07
The minesweep agent project

files

• batch file 2007
• Update to MInesweeper that allows you to change density without recompiling

Introduction

Background

Your team is trying to get a very lucrative deal to develop a system for clearing mine fields. However, before you are given access to the real hardware you have to prove yourself in simulation. The strategy you come up with will be tested in the classical minesweep game for which a typical environment is shown below.

In this game all squares are initially unknown and you have to open them one by one. The game is over if you open a square with a mine under. You will be evaluated on how many squares you managed to open without being blown up. When you open a square you will be told how many mines are in the 8-neighbors of that square but not where they are. Your task is to use the knowledge you have gained in the AI course to come up with a strategy to clear the minefield in a good way, i.e. without getting blown up.

Rules overview

Since when opening the first square there is no information available and an explosion at this point can not be blamed on your AI system, the game will be considered started after the first non-mine square has been opened. Your team will get one point per cleared square. If you trigger a mine it will cost you $c_{dead}$. You also have the option to use a new piece of hardware the allows you to peek at the content of a square before deciding what to do. This will cost you $c_{peek}$ and you can do this only once, but it will give you the same information as if you had opened the square but you do not risk getting killed. You can decide to stop and collect the points that you have earned so far at any time.

Comparison/Competition

As a final step in the course we will let the agents play each other, one agent against another. This is done by letting one agent at a time make a move. The one that gets the most points wins. The players will get the information about a square that is opened by himself and another agent but only the agent that pays for a peek will get this info. Once an agent decides to stop it cannot continue again, since it would otherwise be possible to let the other agent play in solo in risky areas.

Evaluation and testing

To evaluate the performance of your agent you can define minefield in files and play one at a time or in batch mode. The mine files have the following format

00000000000000000000000
00000000000010000000000
00000000010000000000000
00000000000000000000000

Here the ``0'' denote squares that are free from mines and ``1'' means that there is a mine in that place. There is no requirement that the area is square (number of rows and columns the same) but each row/column has the same length.

Software

The system you develop should be able to communicate with the Minesweep server (Minesweep.java) provided in source.

Help classes

An interface for a MineAgent is provided in JAVA and C++ to move the focus away from programming and towards the AI part of the task. There is also a program called MineClient.java/MineClient.cc that can connect to and communicate with the server. What you have to do is to inherit from the MineAgent interface/baseclass and implement the functions

• startNewGame(...)
  Called once in the beginning of the game
• getNextMove()
  Called every time you should make a move
• handleInfo(...)
  Called every time there is new information for you, such as when a square was opened

These functions are automatically called for you when you run the MineClient program.

You are free to implement your agent in any language as long as it can communicate with the Minesweep server.

Downloads

Her eyou can download the code provded for this project

• The java code contains the server (needed by all) and the JAVA interface and client code to connect to the server.
  • Version from 2007-09-17 (adding missing square icons in their own directory)
• The c++ code contains a base class for an agent and client code that can connect to the server.
  • Version from 2007-09-12
• To evaluate your agent and during debugging it is often useful to run on specific board configurations. You can run in so called batch mode.
  • The batch file used for the single player game last year: batch-qual-2006.zip
  • An agent from last year agent2006.jar . You wun it with

    java -jar agent2006.jar
    

    It is based on the MineClient.java class so you can give it the same arguments.

Running the code

To test the code that was provides simply build the java code and start the server. Have a look at the menu in the server and you will find that there are a number of different modes and settings. You can for example run with random boards, you can load a board at a time and you can load whole batch files (see above). As a first test do this

1. Go into the java source directory
2. Do "javac *.java"
3. In one window do "java Minesweep"
4. In another window do "java MineClient"
5. Press "New game"

To test using a batch file unzip the batch file above in the server directory and select to run from batch file in the menu and select the file ending with .msb

Task

• Design and implement a strategy for minesweeping.
• Investigate how effective the strategy is for different amounts of mines, sizes of the environment, etc. What about the complexity?
• How does the cost for detonating a mine and peeking affect the strategy?
• How does the strategy change if you have another agent on the field?
• Gather statistics to support your claims about the effectiveness.
• What if you know before hand how many mines there are in the field? Would that change the strategy?
• What if the minesweep cannot fly around, i.e.~you are only allowed to move to squares near to where you are standing\footnote{The first square you can still choose freely}? How does this change the problem?

Rules for the competition

Before going through the rules let us stress the fact that the competition is supposed to be for fun and is only there so that we can compare different implementations. Just because your agent wins the competition does not mean that you will get the highest grade in the class. It is not a competition in programming, so do not spend all your time on optimizing code. Brains is to prefer over brute force.

• You are allowed to bring your own computer to the competition that will be help in one of the computer rooms Oscars Backe 2.
• Your code cannot run on more than one computer (one motherboard) and not on more than 2 cores if you happen to have a multicore platform. The idea is to compare the algorithms and not the computer power of the groups.
• The boards will be at most 50x50
• The density will not exceed 0.3. If you play at other density levels, the upper and lower limits cannot be made known to the agent.
• The board size, density and the cost to die and peek are randomly generated for every board game in the tournament. The density is not known by the players.