Sigmar's Garden Autosolver

Demo

Opus.Magnum.Sigmar.s.Garden.-.CV.+.Backtracking.Autosolver.mp4

Implementation Details

Image processing (BoardVision.java)

I'm using OpenCV's Template Matching functionality to compare captured tiles to previously classified examples.

I initially thought about using a structual metric, for example SSIM, but it turned out that perfect classification could be achieved with a template matching approach and some preprocessing, despite the reflections on the tiles.

I'm using several preprocessing steps, namely:

• Tiling the board
• Cropping tiles to exclude irrelevant details that might make it harder for the classifier to recognise the relevant parts of the image
• Convert to monochrome, as it turned out, value was the only channel needed to achieve perfect matching
• Equalize histogram to take advantage of the full range of available values
• Several contrast increasing steps to separate the relevant parts of the tiles

An example process can be found here:

processing.mp4

Move Generation (Board.java)

Once the board is obtailed, generating valid moves is easy enough. First, find tiles that are playable, aka that have three successive free spaces.

Then generate all combinations of one, two and five tiles.

Then reject

• all one-moves that
  • aren't gold
• all two-moves that
  • don't have two Elements
  • don't have two Salt
  • don't have one Salt and one Element
  • don't have Mors and Vitae
  • don't have Quicksilver and any Metal
• all five-moves that
  • don't have every Element and the Universal tile

Additionally, reject all metal moves that are blocked by a previous metal.

Solving (BoardSolver.java)

Solving the game is probably the easiest part of the project. I'm using a simple Backtracking algorithm, enhanced by a Transposition Table, with hashes generated from two longs, in which each bit represents a board hex and is set if the corresponding hex is empty.

Playing the game (BoardRobot.java)

The game is played by a java.awt.Robot that is able to start a new game, captures board and click tiles to play moves.

Running the project

Prerequisites:

• JDK 15 or newer
• Maven

Instructions

• Clone this project and navigate into it's root directory
• Run mvn clean compile to compile the project
• Run mvn exec:java to run the project. It will start solving automatically. Please note the limitations in the Acknowledgements & Limitations section of this readme.

Acknowledgements & Limitations

If you want to run this yourself, be warned that the code as it stands now is optimized for 1080p resolution and 100% scaling and will probably break on anything but 1080p 100%.

This project uses OpenCV.