Third year project:

An exploration of the complexity of various Minesweeper questions and strategies for game playing

 

 

 

Progress Report

 

 

 

December 3, 2003

Kasper Pedersen

(0103026)

 

Supervisor: Dr Leslie A. Goldberg

 

Progress in the first Term

We begin by classifying the achievements of Term 1 under general headings and subsequently use them to compare the actual progress with progress expected from the specification.

Ach. 1: Thorough background reading on the complexity hierarchy to a point where we felt that a working knowledge was achieved. This has been an ongoing event during the first term, as several new types of problems were identified and required placement in the complexity hierarchy. The complexity classes we have been concerned with are NP, coNP, #P, FNP, and DP. The background reading has been a continuation of the intractability component of the second year module “Data Structure and Algorithms” and the course textbook Fundamentals of Algorithmics [2] by Brassard and Bratley was very useful in the early stages. After we gained a sufficient understanding of the concepts, Computers and Intractability [3] by Garey and Johnson has been frequently consulted; in particular the listing of NP-complete problems has been useful for identifying possible sources of reductions. The most important reference has been Computational Complexity by Papadimitriou [7], which covers in greater depth — and taking a significantly more modern approach — the properties of the complexity classes in question illustrated with several useful examples. Several papers have also been consulted; see the bibliography for details.

Ach. 2: Gaining an in-depth understanding of Kaye’s proof. We have spent a considerable amount of time studying and verifying Kaye’s proof as we felt that in order to enable us to construct proofs of the complexity of related problems, an expert knowledge of the methodologies used in the original work was imperative. We feel that the understanding of an NP-completeness proof of this nature is itself an achievement worthy of mention.

Ach. 3: Identifying new Minesweeper configurations. We created and verified — independently of Kaye — configurations for the logic gates or and xor. Furthermore, we created some ‘nice’ Minesweeper puzzles that we feel will be useful when testing the approximation algorithms later in the project. These configurations are available on the project web page (www.dcs.warwick.ac.uk/~csviq).

Ach. 4: Proving some general results about Minesweeper. To conclude the study of Minesweeper configurations we looked at how varying the dimension of the game would affect the configurations required to prove NP-completeness. Firstly, we managed to prove that n-dimensional Minesweeper (n > 1) is NP-complete using the existing configurations and an induction on n. This result is not surprising since we would intuitively expect that adding dimensions would not make the problem easier. Secondly, we found a Deterministic Finite Automata (DFA), which solves the consistency problem for a 1-dimensional variation of Minesweeper. The DFA is based on recognising inconsistent sub strings of length three, which is sufficient for a 1-dimensional game. We proved by induction that the DFA is correct.

Ach. 5: Researching the complexity of Minesweeper. We summarise the most important accomplishments from the first Term by listing the theorems we have proved. The wording of the theorems that appear in the report is rather more precise and uses several definitions we have not included here, but the following list is a good summary of the theoretical content of the project to date:

Along with proving these theorems we have given serious consideration to their implications for game playing strategies.

Ach. 6: Invention of game playing strategies. During the research we gained sufficient insight to design some heuristics for solving Minesweeper configurations. One heuristic is based on reducing the search-time of the standard backtracking algorithm by reducing the search-area. This idea was developed from the concept of a “critical region” used by Peña and Wrobel [9]. We have also outlined a possible constraint satisfaction approach using Artificial Intelligence: A Modern Approach [10] as a reference. The ideas are currently at an English language/diagrammatic level, but we expect to be able to successfully translate them into pseudocode and high-level programs.

Ach. 7: Software analysis and design. We have completed an analysis and design of the software we aim to produce in Term 2. We are confident that the design fully meets the requirements set for allowing different types of players (human or algorithmic) access to the game and that the required features are included and sufficiently documented. The design is currently in the form of some UML diagrams and several Java Interfaces.

Comparison of achievements with original timetable

According to the specification, the following four tasks should be completed by the end of the first Term:

  1. Background reading and research. This has been accomplished and is described in Ach. 1 and Ach. 2.
  2. Software analysis and design should be completed. Again, this is meet and described in Ach. 7.
  3. Obj. 1 should be completed. Obj. 1 is related to the study of new Minesweeper configurations (see Appendix) and we feel that the accomplishments described in Ach. 3 and Ach. 4 fulfil this. A rough first draft of a chapter of the final report has been produced, mainly to summarise the findings while they are still current. Although we have officially completed this objective, we will continue the search for other interesting configurations during Term 2, although this will no longer be considered an activity important to the success of the project as several configurations already have been identified.
  4. Obj. 2 should be completed. Obj. 2 is the study of variations of the original Minesweeper question. This objective is the main theoretical component of the project and we feel that it has been achieved with the accomplishments in Ach. 5. At this point it is worth mentioning that we have changed the aims of Obj. 2 after submitting the specification, as we are now interested in problems belonging to various complexity classes and not exclusively NP-complete problems as originally stated. We have also for this objective drafted a chapter of the final report. We are pleased to consider this objective successful as it has proven a major intellectual challenge, and we believe that the project has beneficiated from this component. Again, although we have asked some interesting and relevant questions about Minesweeper and proved the complexity of each question in Term 1, we will not eliminate the possibility of further relevant questions arising during the later stages of the project, and we intend to deal with them in such an event. This objective is also kept open due to the author’s interest in further pursuing it if time permits.

During the research phase we have attempted to keep the invention of game playing strategies in mind. Although we did mention this intention in the original timetable we feel that we have made slightly more progress in the area than expected. Ach. 7 summarises the findings in this area, and we are confident that this extra progress could help to relax the otherwise stringent timetable during the software development period in Term 2. 

Modification of the original specification

We now examine each part of the specification to identify errors and inconsistencies that have become apparent during Term 1.

The Title

The initial title was restrictive, and is no longer a good indicator of the essence of the project. As we have been mainly concerned with exploring the complexity hierarchy of various Minesweeper questions we feel that it would be appropriate to change the title to reflect this. The new project title is: “An exploration of the complexity of various Minesweeper questions and strategies for game playing,” which we feel is a better summary of the project content.

Problems

For the same reasons as the project title, the second stated problem is too restrictive to fully comprise the research content of the project. This problem has been reworded to reflect that we are exploring the complexity hierarchy and attempting to ask questions relevant to game playing rather than simply searching for NP-completeness proofs. In general we believe that the problems set out (with the above modification) are sufficiently challenging, while remaining achievable in the prescribed timeframe.

Objectives

Again, we have reworded Obj. 2 to reflect our interest in several different complexity classes, and in particular ones relating to the complexity of playing Minesweeper.

Furthermore, we have decided to leave Obj. 3.5 as an extra objective that should only be attempted if it appears that sufficient time remains after the majority of the objectives have been meet. This has been done in order to ensure that the core aspects of the project — such as the development of good game heuristics — are completed prior to any extra features.

We have extended Obj. 4 to contain an evaluation component, namely the intention to compare the developed heuristics with some known heuristics for SAT. We hope to find that the heuristics we develop specifically for Minesweeper will be more successful than the general methods.

Methods

The methods have not changed, except for a wording change to reflect the intention to explore other complexity classes than NP as described in the preceding sections.

Timetable

The timetable has not changed.

Resources

The resource requirements have not changed.

Plans for future progress

While we clearly consider the objectives not completed in the first Term as outstanding items, it is useful to briefly consider the plan for the first weeks of the second Term. According to the timetable, we need to do the majority of the software development during this period. This is sensible since it provides us with a platform for implementing and testing the heuristics we intend to implement during the second part of the second Term. Given the existing design, we believe that producing the source code within three weeks is reasonable, leaving a full week as a ‘buffer period’ in which the progress of the project as a whole can be reviewed. We also intend to thoroughly edit the drafts of the final report that we produced during Term 1, as it will be important to explain the theory in detail while the issues related to it are still current.

Conclusion

We feel that the project is in a condition that indicates that a successful completion is possible. We are pleased with the progress made on the theoretical content during the first Term, and are confident that the insight gained from the research will be invaluable during the later stages of the project. Given the robust software design we believe has been completed, we feel that the software development — the stage most immediate at this point — will be relatively swift, allowing sufficient time for the final implementation of heuristics. With that completed, we will have completed all the objectives originally set out.

Bibliography

[1] Blass, A. & Gurevich, Y. (1982) On the Unique Satisfiability Problem. Information and Control 55: 80–88.

[2] Brassard, G. & Bratley, P. (1996) Foundations of Algorithmics. Prentice Hall, New Jersey.

[3] Garey, M. R. & Johnson, D. S. (1978) Computers and Intractability: A Guide to the Theory of NP-Completeness. Bell Telephone Laboratories, Inc.

[4] Karp, R. M. (1972) Reducibility Among Combinatorial Problems. Proceedings of a symposium on the Complexity of Computer Computations: 73–85.

[5] Kaye, R. (2000) Minesweeper is NP-complete. The mathematical intelligencer, 22 (2): 9–15.

[6] Kaye, R. (2000) Some Minesweeper configurations. Available from http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm.

[7] Papadimitriou, C. H. (1994) Computational Complexity. Addison-Wesley.

[8] Papadimitriou, C. H. & Yannakakis, M. (1984) The Complexity of Facets (and Some Facets of Complexity). Journal of Computer and System Sciences 28: 244–259.

[9] Peña, L. C. & Wrobel, S. (2003) Learning Minesweeper with Multirelational Learning. Proceedings of the 18th International Joint Conference on Artificial Intelligence: 533–538.

[10] Russell, S. & Norvig, P. (2003) Artificial Intelligence: A Modern Approach (2edn.). Prentice Hall, New Jersey.

 

 

 

 

Appendix:

Project Specification