A greedy agent to solve the minesweeper game
Loading...
Date
2013-07-04
Authors
Damunugalla, Salinda
Walgampaya, Chamila
Journal Title
Journal ISSN
Volume Title
Publisher
The University of Peradeniya
Abstract
Minesweeper is a one-person game which looks deceptively easy to play, but where average human performance is far from optimal. Playing the game requires logical, arithmetic and probabilistic reasoning based on spatial relationships on the board. At the beginning, the player is presented with a board containing NxM squares which are all blank. Hidden among the tiles are mines distributed uniformly at random on the board. The task of the player is to uncover all the tiles which do not contain a mine. At each turn the player can select one of three actions (moves): to mark a tile as a mine; to unmark a tile; and to uncover a tile. Game play continues until the player has uncovered each and every square that does not hide a mine, while successfully avoiding all of the mines.
In our research, minesweeper game has been redesigned as a key board controlled shooting game. While it can be played by human users we have developed a software player, which we called a greedy agent, to play the minesweeper game. Greedy agent is a rule based agent that uses prior acquired knowledge to achieve specified tasks. The agent stores acquired knowledge in the form of sentences. New sentences are derived from prior sentences during the goal seeking process.
At each move the greedy agent collects the following information: Flagged cell count around the current cell, Mines Count in current cell, and the Uncovered Cell Count around the current cell. According to the collected information the agent can make sentences such as “If mine count of current cell is equal to unvisited or flagged cell count of eight neighbors of current cell then all those unvisited cells contain mines.” During the exploration, if a mine is found and flagged, the agent will look for a safe cell to move. If a safe cell is not found then greedy approach is used to find a safer direction to move. The agent calculates the probability of having a mine in each neighboring cell. Once the cell with the least probability to have a mine is found the agent moves in that direction. In situations where two or more directions have the same probability value, the agent chooses the direction randomly. We have simulated the game with different mines counts and our results show that the agent performs better when the mines count is large.
Description
Keywords
Statistics and computer science , Minesweeper , Greedy agent
Citation
Peradeniya University Research Sessions PURSE - 2012, Book of Abstracts, University of Peradeniya, Sri Lanka, Vol. 17, July. 4. 2012 pp.153