A framework for visualizing hardness reductions to grid-based games

Hardness proofs for grid-based games often use gadgets connected together to represent computational problems. We present an open-source framework to implement these reductions, producing actual game instances out of hard computational instances. Our framework first converts the input problem instance into a graph, then draws the graph in an integer grid (a kind of orthogonal graph drawing problem), and finally replaces nodes and edges in this layout with gadgets. To ensure that the final output is aligned, we use linear programming to constrain how gadgets connect. We apply this framework to Circuit SAT and use it to show examples of reductions to Akari and Minesweeper. Lastly, we describe possible future optimizations to the framework to make the output smaller and how to extend it for a wider variety of games.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2016

Author dc:creator

• Shen, Jeffrey David

Advisor dc:contributor.advisor

• Erik Demaine.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/113165

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/113165