Learning Minesweeper with Multirelational Learning

1 Introduction

Minesweeper is a popular one-player computer game written by Robert Donner aAd Curt Johnson which was included in Microsoft Windows<9 in 1991. At the beginning of the game, the player is presented with a p x q board containing pq tiles or squares which are all blank. Hidden among the tiles are M 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. In the last action, if the tile contains a mine, the player loses; otherwise, the number of mines around the tile is displayed. In the 4 x 4 board depicted in Fig. 1 left, the number 1 located on the second row from top indicates that there is one and only one mine hidden among the eight blank neighbouring tiles.

Although the simplicity of its rules makes Minesweeper look deceptively easy, playing the game well is indeed chal­ lenging: A player requires logic and arithmetic reasoning to perform certain moves given the board state, and probabilis­ tic reasoning to minimize the risk of uncovering a mine when

Stefan Wrobel

Fraunhofer AIS, Sankt Augustin and University Bonn, Germany

a safe move cannot be done. Given the difficulty of hand­ crafting playing strategies for this and other games, AI re­ searchers have always been interested in the possibility of au­ tomatically learning such strategies from experience. How­ ever, with the exception of reinforcement learning [Tesauro, 1995], most of the playing strategies and heuristics used in game playing programs are coded and tuned per hand in­ stead of automatically learned. In this work, we use a gen­ eral purpose ILP system, Mio, to learn a playing strategy for Minesweeper. Multirelational learning or ILP consists in learning from examples usually within the framework pro­ vided by clausal logic.

The task of learning rules to deduce Minesweeper moves proved itself to be an arduous test for current multirelational learning systems. In this paper, we describe how recent opti­ mizations make possible for Mio to discover a Minesweeper playing strategy. Experimental results obtained by playing Minesweeper using this strategy show a better performance than that obtained on average by non-expert human players.

The remainder of this paper is organized as follows. The next section discusses the complexity of the game and de­ scribes the learning task. Section 3 describes the background knowledge, the learning system and the new techniques used. Section 4 shows our empirical results on the effectiveness of the learning techniques, the strategy obtained and its perfor­ mance at game playing. Related work is surveyed in Section 5 and Section 6 concludes.

2 Minesweeper

2.1 Why Is Minesweeper Interesting?

Minesweeper has been shown to be NP-complete by simulat­ ing boolean circuits as Minesweeper positions [Kaye, 2000]. Kaye describes the Minesweeper consistency problem as the problem of determining if there is some pattern of mines in the blank squares that give rise to the numbers seen in a given board partially filled with numbers and marked mines, and thus determining that the data given is consistent.

One realizes the complexity of the game by calculating an estimate for the size of its search space. Consider an 8 x 8 board with M = 10 mines; in this case at the beginning of the game the player has pq = 64 tiles from which to choose a move (i.e. , a tile to uncover) and in the last move, assuming the player does not uncover a mine, there are 11 tiles from which to choose one. This leads to 54! ::::::: 10 71 possible move sequences to win a game. Alternatively, one can calculate the probability of a random player winning a game. In the first move the probability that the random player chooses a tile which does not contain a mine is 54/64, and in the last move it has 1/ 11 chance to choose the only tile without a mine. Then, the probability of a random player winning a game is 1/ (~!) ::::::: 10- 12 and that is only for the easiest playing level! Another measure of the complexity of Minesweeper is the number of games won on average by non-expert human play­ ers. To estimate the average human performance playing Minesweeper, we carried out an informal study. In the study, eleven persons who have played Minesweeper before were asked to play at least ten times in an 8 x 8 board with 10 mines. Every participant was told to aim for accuracy rather than for speed. In this study, a person won on average 35% of the games with a standard deviation of 8%.

2.2 The Learning Task

In Minesweeper there are situations that can be "solved" with nontrivial reasoning. For example, consider Fig. 1 left where the only available information about the board state are the numbers. After careful analysis one finds that the squares with an s (see Fig. 1 right) do not contain a mine, the square with an m is a mine, and the state of the blank tiles cannot be determined if we do not know how many mines are hidden in the board. There are other Minesweeper situations where the available information is not enough to identify a safe square or a mine, as in Fig. 2, and the best option available to the player is to make an informed guess, i.e., a guess that mini­ mizes the risk of blowing up by uncovering a mine.

In this work, we consider the learning task in Minesweeper to be the induction of rules to identify all the safe squares 1 and squares with a mine which can be deduced given a board state. For instance, we want the system to learn rules to clas­ sify all the blank tiles in Fig. 1 either as safe or mine.

3 The Learning Tools

In machine learning it is possible to choose between a propo­ sitional representation (in the form of attribute-value tuples) and a multirelational representation (in the form oflogic pred­ icates). A multirelational representation has the expressive­ ness required to describe the concepts involved when rea­ soning about Minesweeper, and is thus more intuitive than the propositional one. For this reason we use multirelational learning for the learning task described above. Usually a mul­ tirelationallearning system takes as input background knowl­ edge B , positive (E+) and negative (E-) examples of a target concept such that E = E+ u E- and E+ n E- = 0, and has to find a clausal theory T which minimizes the classification error on future instances. Next we describe the background knowledge and the system used.

1 A safe square is a blank tile which given the current board state cannot contain a mine.

3.1 Background Knowledge

The background knowledge provides the system with infor­ mation about the domain and is given in the form of logic predicates (facts and rules, or clauses). A predicate is de­ scribed as name(arg1 , . .. , argn) and, in our case, argi in­ dicates the argument's type. The background knowledge pro­ vided to the learning system about Minesweeper is shown in Table 1. The predicates in the background knowledge were defined by trying to abstract the concepts used by hu­ mans when explaining their own Minesweeper playing strate­ gies. These concepts were obtained from the first author's Minesweeper playing experience and from Minesweeper pages on the web.

In the predicates listed in Table 1, a TD is a determined or uncovered tile, i.e., a number 0 .. . 8 is shown on the tile; a TU is an undetermined or blank tile; Board is the board state given as a list of p x q characters 0 . . . 8, m, u; Zone is a list of determined tiles, and Set is a set of undetermined tiles to­ gether with the number of mines hidden among those tiles. In addition, each symbol preceding an argument denotes how that argument should be instantiated when calling the predi­ cate. A +argi is an input argument and should be instanti­ ated to a non-variable term; a -argi is an output argument and should be uninstantiated, and a #arg indicates that the constant value of an output argument can appear in a rule.

too much in effectiveness. We implement a greedy search with macros which consists of a Iookahead step where all the macros are combined with each other and the best evalu­ ated clauses are selected. Then if the selected clauses can be extended (refined) the system tries to combine these clauses with all the macros available and selects the best candidates. This last step is repeated until there is no clause which can be extended and the best candidates are returned.

Active Inductive Learning

In the covering algorithm a clause is learned which covers (explains) some positive examples and none (or few) negative ones; however, in domains such as games and puzzles, thou­ sands of examples are required to contain most of the possible game situations; on the other hand, considering thousands of examples when evaluating a rule slows down the learning pro­ cess. Thus, to improve the efficiency of the exploration of the instance space, active learning [Cohn eta!., 1994] is included inMio.

Active inductive learning consists of the following steps. At the beginning, Mio learns from few randomly drawn ex­ amples and when it has learned some clauses gives these clauses to an active learning server. The active learning server returns to Mio counterexamples 4 . These counterexamples are selected from examples given by a random example generator (or random sampler). While Mio iterates on the new exam­ ples received, the server tests the rules obtained against ran­ domly drawn examples, discards all the rules below a user­ defined accuracy value and collects new counterexamples. This validation step on the server side avoids overfitting 5 . These steps are repeated until a user-defined maximum num­ ber of iterations is reached or no counterexample is found.

Active inductive learning is similar in spirit to integrative windowing [Fi.irnkranz, 1998] with two main differences: in our approach random sampling is done dynamically and a client-server architecture is used which allows to treat test­ ing and learning as separated processes.

4 A counterexample is a positive example not covered by a set of clauses T or a negative example covered by at least one clause in T .

5 0verfitting refers to obtaining results with high classification error over new data despite null or almost null training error.

3.2 The System

Mio is an example-driven covering system (see Fig. 3) in­ troduced by Pefia Castillo and Wrobel [2002b] which uses a Progol-Iike declaration language and, the same as Pro­ go! [Muggleton, 1995], lower bounds the search space with a most specific clause ..l (also called bottom clause). This ..lis a maximally specific clause which entails (covers) a positive example e. Mio performs a general-to-specific (top-down) IDA* [Korf, 1985] search to find a clause to add to the the­ ory. In addition, Mio selects stochastically the examples from which it learns, performs parallel search to increase the stabil­ ity of the example-driven approach, and enforces type strict­ ness. Three other techniques are implemented in Mio to al­ low the learning of Minesweeper rules: macro-operators (or macros, for short) to reduce the search space, greedy search with macros to speed up the learning process, and active learning to guide the exploration of the instance space.

Macros

Macros in multirelational learning [Pefia Castillo and Wro­ bel, 2002a] are a formal technique to reduce the hypothesis space explored by a covering system. A macro is a sequence of literals, chosen from the bottom clause, which is created based on provider-consumer relationships between the liter­ als. A literal is a provider if it has output arguments, and it is a consumer if it receives as an input argument a variable provided by another literal in the bottom clause. Pefia and Wrobel show that by adding macros instead of literals to a clause, the number of clauses evaluated by the system is sig­ nificantly reduced.

Greedy Search with Macros

In [Pefia Castillo and Wrobel, 2002a] macros are used with IDA*. It is well known that greedy search explores on av­ erage less nodes than IDA*; however, greedy search could miss a solution because it underestimates the importance of provider literals without discriminative power which are nonetheless necessary to introduce new variables (this is known as the myopia problem). Since macros add several literals at once to a clause, they might reduce the myopia of greedy search allowing us to gain in efficiency without losing

3 Fringe refers to all the blank tiles with a determined neighbour.

4 Empirical Results

4.1 Improvements Obtained with each Technique

Experiments were carried out to determine the effects on the rules obtained and on the system efficiency, of macros, greedy search with macros, and active inductive learning. To produce the training examples, we randomly generate board configu­ rations and take all blank tiles with at least one determined neighbour as examples. If the blank tile does not contain a mine is labeled as safe, otherwise it is labeled as mine. Af­ terwards, contradictory examples are removed. In the exper­ iments, the learning task was to learn rules to identify safe tiles. The rule to discover mines was learned using the best setting (i.e., using active learning, macros and greedy search).

For the completeness of this work, we ran Progol [Muggle­ ton and Firth, 2001] and Foil [Quinlan and Cameron-Jones, 1995] on the same learning task as Mio; however, we failed to make the systems learn correct rules about safe tiles. Pro­ go! search was interrupted due to search limits implemented in the system (although the maximum stack depth and res­ olutions steps were set to 50000 and 10000, respectively), and Foil pruned determined literals which are needed. This might imply that the optimizations included in Mio are in­ deed necessary to learn a Minesweeper playing strategy. Ta­ ble 2 shows the empirical results with four Mio settings.

All the experiments with active learning were performed with the same seeds which means that the same training ex­ amples are generated by the random sampler and that Mio selects the same examples to guide the search. For the exper­ iments without active learning, we took five random samples from the set of examples used in the active learning exper­ iments. The size of the sample is equal to the number of examples received by Mio when performing active learning ( 40 positive and 34 negative examples). We carried out an extra experiment where Mio was given the complete set of examples (2890 positive and 1306 negative) used by the ac­ tive learning server to test Mio's rules and select counterex­ amples; however, this experiment was stopped after Mio ran for 10 days. To reduce the running time of the experiments, we set the maximum number of clauses explored per search to 4000 clauses.

Table 2 shows that each optimization added to Mio reduces the average number of rules (nodes) explored per search and the number of times the search is interrupted because of the search limit. Without active learning, overfitting occurs and erroneous rules are obtained. The performance of the rules obtained with IDA *+M is worse than that of the IDA* rules because Mio with macros explores a larger part of the hy­ pothesis space and thus the IDA* + M setting overfits more the training data. However, if no limit in the maximum num­ ber of clauses explored per search is set, both settings (IDA* and IDA *+M) obtain the same rules. The running time of the fastest setting (AL+GS+M) is 56hrs.

4.2 Rules Learned

Table 3 shows the rules with the highest winning rate which were obtained by using both AL+GS+M and AL+IDA *+M. An extra rule was obtained with the latter setting; however, this extra rule does not improve the playing performance. One important feature of the rules learned by Mio is that they can be applied independently of the size of the board and the number of mines. The rules vary in complexity. Rule S-1 and Rule M-1 correspond to the trivial situations where a deter­ mined tile needs k mines and k mines are already marked, and where a determined tile needs k mines and it has k blank neighbours, respectively.

On the other hand, Rule S-3 can be seen as one of the most complex rules because it involves three determined tiles to deduce a safe tile. Fig. 4 left shows a board state where Rule S-3 is the only one which allows to identify a safe tile. The rule obtains the zoneOflnterest corresponding to the unde­ termined tile considered (Fig. 4 center). Then by applying difference operations on the sets determined by three uncov­ ered tiles from the zoneOflnterest (see Fig. 4 right), the set ([40], 0) is obtained and thus it is deduced that tile 40 is safe.

4.3 Game Playing

To evaluate the performance at game playing of each set of rules obtained, we used each set of rules as the playing strategy of an automatic Minesweeper player and calculated the percentage of games won by the player in 1000 random games (see Table 2). The playing conditions were th~ same as the ones presented to the human players; i.e., at the begin­ ning the player is presented with an empty 8 x 8 board with M = 10 mines and can uncover a mine in the first move. Note that in most Minesweeper implementations, one never hits a mine in the first move.

Let us analyze the performance of the best rule set (see Table 3). In 1000 games, the player made 15481 moves from which 2762 where random guesses, 169 used Rule S-1, 10285 used Rule S-2, 54 used Rule S-3, and 2211 used Rule M-1.

In addition, we examined the effect of adding probabilistic reasoning. In the experiment, we instructed the player us­ ing the rules shown in Table 3 to select a tile which mini­ mizes the probability P(Tu) that an undetermined tile Tu is a mine when none of the rules can be applied. P(Tu) is equal to maxrd ( j::rJ:?) where Td is a determined neighbour of Tu, fm(Td) returns the number of mines needed by Td and fn(Td) returns the number of blank neighbours ofTd. Every time the player has to guess, it selects the tile which mini­ mizes P(Tu)· This player wins 579 of 1000 random games.

5 Related Work

5.1 Minesweeper Playing Programs

There are several Minesweeper programs available on the web. These programs are not learning programs but playing programs where the authors have embedded their own game playing strategy. Among these programs, John D. Ramsdell's PGMS is quite successful winning 60% of 10000 random games in a 8 x 8 board with 10 mines.

PGMS plays using the Equation Strategy based on find­ ing approximate solutions to derived integer linear equations, and probabilities. As mentioned by Ramsdell [2002], PGMS represents the information available on the board as a set of integer linear equations. Associated with an undetermined tile is a variable x that has the value 1 if the tile hides a mine, or 0 otherwise. An equation is generated for each uncovered tile with an adjacent undetermined tile. Each equation has the form c = L:iES Xi, where S is a set of undetermined tiles, and cis the number of mines hidden among S. To sim­ plify notation, this equation is written as c ~ S. Since the total number of hidden mines is known, an additional equa­ tion simply equates this number with the sum of all of the undetermined tiles.

Every time a tile t is determined safe or a mine, the board changes are propagated to all the equations containing t and a new equation for the undetermined neighbours oft is added. In addition, if Co ~ So and C! ~ sl are two equations such that So is a proper subset of sl, the equation C! -Co ~ sl \ S0 is added. To determine whether a tile is safe or a mine, PGMS iteratively applies the following rules until none are applicable 7 :

7 In these rules lSI is the cardinality of S and So \ S1 is the dif­ ference between So and S1.

• If 0 ~ S, all tiles in S are safe.
• If c ~ Sand c = lSI, all tiles inS are a mine.
• Let co ~ So and Ct ~ St be two equations and tube an undetermined tile such that eo < Ct, and tu E So and tu E St. If Ct -Co = ISt \Sol, all the tiles in St \So are a mine and all the tiles in So \ St are safe.

PGMS must guess when presented with a board to which none of the rules apply. For each tile t it computes the value P(t) as follows. Given an equation c ~ S, define its single equation probability to be c/ISI. P(t) is equal to maxtEs(c/ISI). PGMS picks the tile t that minimizes P(t). A random choice is made when there is more than one tile that minimizes P(t).

We were surprised to notice that although Mio was only given general background knowledge about Minesweeper, the rules it learned are similar to the rules programmed in PGMS. For example, Mio's Rule S-1 and Rule S-2 corre­ spond to the first and third rule in PGMS, respectively; and Mio's Rule M-1 is similar to PGMS second rule. To compare PGMS performance with the performance ofMio's best play­ ing strategy, we let our best player (i.e., the player using the rules in Table 3 and probabilities) play 10000 random games in a 8 x 8 board with 10 mines. Its winning rate is also 60%.

5.2 Multirelational Learning for Games

Other work has been done which applies ILP systems to learn heuristics or playing strategies for games. Ramon et a!. [200 1] used Tilde [Blockeel and Raedt, 1998] to learn a theory that predicts the value of a move in Go. Morales [1996] applied the system PAL to learn chess pat­ terns for constructing chess playing strategies. Nakano et a!. [1998] presented an approach to generate an evaluation function for Shogi mating problems using ILP.

6 Conclusions and Future Work

In this paper we described how the use of new ILP techniques such as macros, greedy search with macros, and active in­ ductive learning allow Mio to learn a Minesweeper playing strategy. This learning task proved itself to be a challenging testbed for general purpose multirelationallearning systems.

The best rules obtained by Mio win 52% of the games in a 8 x 8 board with 10 mines, while on average a non-expert human player wins 35% of the games. The performance of the playing program using these rules as playing strategy im­ proves to 60% when adding the use of probabilities.

By examining the games played using Mio's rules, we no­ tice that there are still situations where the player guesses without need (i.e., a sure move can be deduced). As fu­ ture work, we want to use other ILP systems (e.g., Tilde), and other machine learning approaches to learn Minesweeper playing strategies and compare their performance.

Acknowledgments

We thartk all the persons who participated as guinea pigs play­ ing Minesweeper, the anonymous reviewers for their com­ ments, and Oscar Meruvia for proofreading. The second au­ thor was partially supported by DFG (German Science Foun­ dation), projects WR40/l-3 and WR40/2-l.