A framework for visualizing hardness reductions to grid-based games
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/113165 |
| _version_ | 1811069997859995648 |
|---|---|
| author | Shen, Jeffrey David |
| author2 | Erik Demaine. |
| author_facet | Erik Demaine. Shen, Jeffrey David |
| author_sort | Shen, Jeffrey David |
| collection | MIT |
| description | Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. |
| first_indexed | 2024-09-23T08:20:17Z |
| format | Thesis |
| id | mit-1721.1/113165 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:20:17Z |
| publishDate | 2018 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1131652019-04-09T18:04:15Z A framework for visualizing hardness reductions to grid-based games Shen, Jeffrey David Erik Demaine. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 67-70). 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. by Jeffrey David Shen. M. Eng. 2018-01-12T21:01:12Z 2018-01-12T21:01:12Z 2016 2016 Thesis http://hdl.handle.net/1721.1/113165 1018309999 eng 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. http://dspace.mit.edu/handle/1721.1/7582 70 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Shen, Jeffrey David A framework for visualizing hardness reductions to grid-based games |
| title | A framework for visualizing hardness reductions to grid-based games |
| title_full | A framework for visualizing hardness reductions to grid-based games |
| title_fullStr | A framework for visualizing hardness reductions to grid-based games |
| title_full_unstemmed | A framework for visualizing hardness reductions to grid-based games |
| title_short | A framework for visualizing hardness reductions to grid-based games |
| title_sort | framework for visualizing hardness reductions to grid based games |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/113165 |
| work_keys_str_mv | AT shenjeffreydavid aframeworkforvisualizinghardnessreductionstogridbasedgames AT shenjeffreydavid frameworkforvisualizinghardnessreductionstogridbasedgames |