Prolog Minesweeper

From UBC Wiki

Authors: Connor Quigg, Aidan Frost, James Zang

What is the problem?

How suitable is prolog for the classic Minesweeper game in terms of the UI and event handling aspects? Is it possible to effectively replicate classic games using SWI prolog?

What is the something extra?

We will be using the XPCE library for the GUI and using random tile map generation.

What did we learn from doing this?

From the GUI side of the project using the XPCE library, we had to spend a significant amount of time learning the UI concepts from an old instruction manual as it was the best resource available rather than modern documentation. This reduced the approachability and made the use of this library less suitable for making games. We also learned that the library used callbacks for the event listeners that had their own scope which made it difficult to coordinate game state efficiently and we were forced to use singleton UI elements to record the global state. This may hinder larger-scale games due to the inefficiencies involved. Having object-oriented capabilities in XPCE did help a bit in general programming as it was approachable and familiar which helped us with the static elements of our design.

As for the game logic, we realized that the best way to track the game state is through careful use of “assertz” and “retract”. We first attempted to thread a 2D array representation of the local state throughout our event handlers and callbacks, but quickly realized that Prolog is pass-by-value. As such, since each individual tile had it’s own callback function attached, there were essentially 16x16=256 individual state arrays floating around, which obviously wasn’t working. Thus, we “assertz” a fact such as “revealed(X,Y)” or “flagged(X,Y)” and “retract” it as appropriate. To clean up the game state when the reset button is pressed, we do a “retractall” in our cleanup function.

As far as map generation and tile handling, the main hurdle was learning how to work with 2 dimensional lists, and what it actually means to "set" a tile in such a list. This became especially important during the initial map generation, where mines are first distributed randomly throughout the map before the "adjacency" tiles can be retroactively computed (for those who are unfamiliar with Minesweeper, a tile is either a mine, or a number representing the amount of adjacent (touching) mines, so anywhere within the range [0,8]). Thus during construction of the actual map, for each non-mine tile we had to track up to 8 neighbors in order to compute the tile's value. Additionally, the random mine generation posed some problems at first - Prolog's "random" predicate was used to choose a tile at random from a base map (all zeros), then place a mine and update the mine count. Because this base map would slowly become more populated with mines, and since we imposed a strict mine count on a given map, we had to handle the case where a random tile would be selected and already contain a mine - here we would retry and not decrement the mine counter. Unfortunately, too many cases like these would sometimes cause conflicts between the random values generated as the recursion unravelled which would then lead to the query failing (or sometimes execution would take too long as the predicates repeatedly sampled the map looking for an empty tile to place another mine). We solved this and similar issues by making use of Prolog's if-else (->) facility, some sneaky code, and in some cases, making use of "intermediate" variables to handle more complex copy/changing of larger maps.

The bottom line is: making a relatively simple, classic game like Minesweeper is doable in Prolog with respect to UI and event handling. We found that our Minesweeper is just as good (dare we say better?) as any online Minesweeper game you could find. One word of caution, though, to any would-be Prolog game devs: as noted above, the more you need to globally track your game state, the harder it will be!

Links to code etc