IN DANISH ONLY

Written as part of my master thesis in Information Science together with Jens Frederiksen in December 2004 at the IT-University of Copenhagen.

Abstrakt

Denne rapport og den dertilhørende Java kildekode, er kulminationen på vores 16 uger programmeringsprojekt på IT – Universitetet i efteråret 2004.

Vi har undersøgt hvilke algoritmer og datastrukturer der skal anvendes for at lave en repræsentation af Hex spillet som Piet Hein og John Nash opfandt uafhængigt af hinanden for snart 50 år siden.

Vi har kigget på to forskellige korteste vej algoritmer; brede-først-søgning og Dijktras algoritme. For at finde den korteste vej er graf strukturen et naturligt valg, til at undersøge problematikken. Der er benyttet disjunkte mængder datastrukturen for at nemt at kunne undersøge om en spiller har skabt en forbindelse med spillerens to sider.

Hex spillet er blevet brugt som case for at udforske de algoritmer og datastrukturer, for at få spillet til at fungere. Vi har implementeret to versionen af spillet i Java, hvor den ene version er den som Hein og Nash opfandt og den anden er en version hvor alle felterne på spillebrættet har en vægt som har betydning for den korteste vej i fra den vindende spillerens to sider.

Indledning

Vores mål med projektet var at kigge nærmere på spillet Hex / Polygon Game som et klassisk graf problem inden for algoritmer og datastrukturer. Vi præsenterer vores implementering af disse ved hjælp af et simpelt userinterface udarbejdet i Java, hvor de underlæggende algoritmer og datastrukturer liggende bagved også programmet i Java.

Vi valgte programmeringssproget Java, da vi tidligere har erfaringer med dette og da et af projektets formål var at udforske objektorienteret programmering virkede dette som et oplagt valg.

Det overordnende mål i vores projekt er at opnå en grundlæggende forståelse af grafer, træer og datastrukturer, samt hvordan de benyttes og udarbejdes på en hensigtsmæssig måde i forbindelse med konstruktion af spil. Implementeringen af disse i Java er sekundært, og udarbejdelsen af et userinterfase tertiært.

Projektet er derfor todelt, i henholdsvis en teoretisk og en praktisk del. Den teoretiske del skal give os en indsigt i algoritmernes og datastrukturers overordnede opbygning. Den praktiske del vil bestå i en implementering af de teoretiske elementer i Java.

For både at få den teoretiske indlæring om datastrukturer og algoritmer og for at sikre en mere praktisk tilgang til emnet har vi anvendt spillet Hex som en case. Derigennem har vi direkte kunne afprøve og af- eller bekræfte noget af den læste teori.

Problemformulering

Hvordan sikre man at spillet Hex altid har styr på om der er en vinder og dernæst for at finde den korteste vej fra den vindende spillers to sider?

Afgrænsning

Hex spillet udspringer af matematikkens verden, vi vil dog ikke dække det matematiske aspekt i spillets udformning eller forskellige strategier. Vi bruger blot Hex spillet til at udforske datastrukturer og algoritmer.

Vi beskriver ikke alle benyttede datastrukturer i detaljer, f.eks. prioritetskøer. Ligeledes har vi ikke brugt de matematiske analysemodeller for datastrukturer og algoritmer, som f.eks. Stor O notation.

Målgruppe

Det er vores mål at give en beskrivelse af de teorier og emner, som vi gennemgår i rapporten på et abstraktionsniveau, hvor essensen er bibeholdt, men hvor de matematiske beviser for de forskellige begreber træder i baggrunden. Det er for at holde fast i vores mål om at skrive denne rapporten til vores valgte målgruppe; studerende som os, som ikke har haft undervisning i algoritmer eller datastrukturer og derfor ikke kan forventes at have nogen forkundskaber eller viden omkring emnet.

Download

Download hele rapporten her i PDF (7,7 MB):