Games en Puzzles en hun Complexiteit

Abstract

Een algoritme rijkt een oplossing aan voor een bepaald probleem. Het heeft een complexiteit die bepaalt hoeveel tijd en/of geheugen het algoritme nodig heeft, naargelang de grootte van de input, om een oplossing voor het probleem te vinden. De complexiteit van algoritmen horende bij puzzels en spellen doet pas begin jaren ’80 zijn intrede, met het EXPTIME-compleetheids bewijs voor schaken als voorloper. Hierna is de interesse om spellen en complexiteit te laten samensmelten steeds gegroeid. De analyse van puzzels en spellen bleek een leuke invalshoek om complexiteit te bekijken. Vandaag de dag zijn reeds complexiteitsresultaten voor tientallen, zo niet honderde puzzels en spellen bekend. Het blijkt dat deze in verschillende klassen zijn onder te verdelen, en dit naargelang de moeilijkheid van het spel in kwestie. Deze thesis begint met een introductie tot de complexiteitstheorie, gevolgd door de fundamenten van de klasse NP en het begrip compleetheid. Hierna volgt een overzicht van een paar gekozen puzzels en spellen waarvoor complexiteitsresultaten bekend zijn, en dit naargelang de klasse waartoe ze behoren. Uiteindelijk wordt dieper ingegaan op Minesweeper dat NP compleet is. Aangaande dit spel zullen meerdere varianten bekeken worden, als ook de bijbehorende complexiteits resultaten. De complexiteitsresultaten van de varianten van Minesweeper die in deze thesis besproken worden, zijn nieuw en vormen mijn belangrijkste bijdrage aan dit werk.