Neural networks in solving minesweeper

• Autorzy: Lubarski Kamil , Samujło Beniamin , Wszeborowski Kacper

Identyfikatory

DOI

10.34808/FTWJ-Q764

• Języki publikacji: EN

Abstrakty

EN

The purpose of this article is to present the operation of certain neural networks in solving the Minesweeper game and to assess whether it is possible to represent the decisions made by these neural networks in an understandable way using logical rules. Existing solutions such as CSP (Constraint Satisfaction Problem) were utilized to design an algorithm that analytically solves the Minesweeper game. The results obtained were then used to train Multi-Layer Perceptron (MLP), Encoding Neural Network (ENN), and Convolutional Neural Network (CNN) models. The CNN emerged as the best-performing network. Based on the tests conducted by this network, a decision tree was constructed that represents the network’s logic for these specific tests with approximately 90% accuracy. Ultimately, none of the tested neural networks were able to match the analytical approach. However, based on the decision trees obtained for the functioning networks (mainly CNN), it was inferred that, in theory, with a sufficiently large number of tests, it should be possible to closely replicate the network’s operation using logical rules (nested conditional statements).

Słowa kluczowe

EN

artificial neural networks; minesweeper; decision tree

PL

sztuczne sieci neuronowe; saper; drzewo decyzyjne

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2023
• Tom: Vol. 27, No 4
• Strony: 1--10
• Opis fizyczny: Bibliogr. 10 poz., rys., tab., wykr.

Twórcy

autor

Lubarski Kamil

• Department of Computer Communications, Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Samujło Beniamin

• Department of Computer Communications, Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Wszeborowski Kacper

• Department of Computer Communications, Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland

Bibliografia

• [1] Z. W. Preslav Nakov, “Minesweeper, #minesweeper,”BerkeleyEECS, 2003. doi: 10.1109/TKDE.2003.180.
• [2] M. H. Sajjad, “Neural network learner for minesweeper,”Loughborough University, 2022. doi: 10.1109/TKDE.2022.180.
• [3] B. David, “Algorithmic approaches to playing,”Harvard University’s DASH repository, 2015. doi: 10.1109/TKDE.2015.180.
• [4] R. Massaioli, “Solving minesweeper with matrices,”Programming by Robert Massaioli, 2013. doi: 10.1109/TKDE.2013.180.
• [5] B. Y. C. Ken Bayer, Josh Snyder, “An interactive constraint-based approach to minesweeper.” American Association for Artificial Intelligence, 2006. doi: 10.1109/TKDE.2006.180.
• [6] C. Studholme, “Minesweeper as a constraint satisfaction problem.” American Association for Artificial Intelligence, 2000. doi:10.1109/TKDE.2000.180.
• [7] R. K. N. Yash Pratyush Sinha, Pranshu Malviya, “Algorithmic approaches to playing,”International Institute of Information Technology Bhubaneswa, 2021. doi: 10.1109/TKDE.2021.180.
• [8] B.Smulders,“Optimizing minesweeper and its hexagonal variant with deep reinforcement learning.”https://research.tue.nl/en/studentTheses/bcceee8c-dea7-4309-8c4d-4d03cee6a2d4,2023. doi:10.1109/TKDE.2023.180.
• [9] S. C. C. Z. Z. G. Jinzheng Tu, Tianhong Li, “Exploring efficient strategies for minesweeper,” The AAAI-17 Workshop on What’s Next for AI in Games? WS-17-15, 2017. doi:10.1109/TKDE.2017.180.
• [10] J.C.B.Jozef Fekiač, Ivan Zelinka, “A review of methods for encoding neural network topologies in evolutionary computation.” https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=814e438666496db4126e23404b2baf707218d7f2, 2011. doi: 10.1109/TKDE.2011.180.