This thesis discusses the games Hex, and two variants Cylindrical Hex and Torus Hex. We start by giving the rules of the games, and showing that no tie can take place, meaning that there will...Show moreThis thesis discusses the games Hex, and two variants Cylindrical Hex and Torus Hex. We start by giving the rules of the games, and showing that no tie can take place, meaning that there will always be a winner. After that we discuss some existing strategies for Cylindrical Hex and program a Pure Monte-Carlo player to play this game. From smart strategies observed from the Pure Monte-Carlo player, a new strategy is determined for Cylindrical Hex. To test this new strategy, experiments are carried out and discussed.Show less
Na de aanslagen op het World Trade Center in New York in 2001 rees de urgente vraag naar het brein achter de organisatie. Deze vraag werd na verloop van tijd beantwoord, maar wiskundigen vroegen...Show moreNa de aanslagen op het World Trade Center in New York in 2001 rees de urgente vraag naar het brein achter de organisatie. Deze vraag werd na verloop van tijd beantwoord, maar wiskundigen vroegen zich af of dit probleem ook speltheoretisch aangepakt kon worden. Er is een netwerk gemaakt van de onderlinge relaties tussen alle betrokkenen. Al snel werd vermoed dat degene met de meeste verbindingen de belangrijkste was uit het terrorismenetwerk. Meer specifiek, als we het netwerk als graaf presenteren, dat de knoop met de hoogste Shapleywaarde ook de belangrijkste persoon representeert. Echter is de Shapleywaarde computationeel heel lastig. Om deze te berekenen moest het netwerk kleiner gemaakt worden, waardoor de gevonden waarde afwijkt van de werkelijke waarde. In 2018 hebben T.C. Van der Zanden, H.L. Bodlaender en H.J.M. Hamers [9] een algoritme ontwikkeld, waarmee de Shapleywaarde van het totale netwerk berekend kan worden in een fractie van de tijd die nodig was om het gereduceerde probleem op te lossen. In deze scriptie wordt dit algoritme besproken en hoe dit algoritme de Shapleywaarde van een knoop kan berekenen. Hiervoor wordt eerst de benodigde achtergrond samengevat en doorgenomen en worden enkele stellingen bewezen. De bedoeling was eerst om een code te schrijven aan de hand van het algoritme om het vervolgens toe te kunnen passen op metronetwerken. Echter bleek dit een onbegaanbaar pad te zijn. In het artikel dat besproken wordt in deze scriptie staat een aantal foutjes, die gedeeltelijk repareerbaar bleken. Ook zijn niet alle details volledig uitgewerkt in het artikel. Dit maakte het schrijven van een correcte code te tijdrovend, hetgeen ertoe leidde dat dit plan werd stilgelegd na een jaar. Besloten is toen om meer te richten op het toelichten van het algoritme en, waar mogelijk, de kleine foutjes te repareren. Echter is dit ook maar gedeeltelijk gelukt. De achtergrondartikelen zijn vaak wat kort door de bocht. De stellingen zo helder mogelijk te formuleren en bewijzen was hierdoor wat lastig. Het kort door de bocht zijn, geldt in het bijzonder voor het artikel met het algoritme. Er is zeer veel tijd besteed aan het identificeren en repareren van fouten in het algoritme, en toch is het nog steeds niet gelukt om dit zodanig te interpreteren dat het goede uitkomsten geeft. Het is in dit licht dan ook opmerkelijk dat [9] in 2022 nog steeds niet gepubliceerd is. Wel is het gelukt te identificeren waar in het algoritme iets misloopt.Show less
Het is weer tijd voor een spelletjesmiddag. De chips staat op tafel en de bier- of Cola flesjes wordenopen geploft. Nu de vraag: welk spel gaan we spelen? Helaas zijn niet veel van je vrienden...Show moreHet is weer tijd voor een spelletjesmiddag. De chips staat op tafel en de bier- of Cola flesjes wordenopen geploft. Nu de vraag: welk spel gaan we spelen? Helaas zijn niet veel van je vrienden opkomen dagen en zijn jullie met zijn twee ?en.DOMINEERING,NIMofHACKENBUSH? Of tochMAZE,PUSHof AMAZONS? Na wat discussie wordt besloten het spelHEXte spelen. Echter is dit spel alvaak genoeg gespeeld, dus de ducttape wordt gepakt en een andere versie ontstaat:CILINDRISCHHEX. Hier zijn de linker- en rechter randen van het speelbord aan elkaar geplakt, wat het speelbordniet vlak maar cilindrisch maakt. Jij en je vriend zijn echter zeer fanatiek, en gaan eerst goednadenken wat de strategie moet zijn om dit spel te spelen. In deze scriptie wordt onderzocht watde winnende strategie ?en zijn bij het spel Cilindrisch Hex, en of het mogelijk is een strategie vooreen cilindrisch bord met omtrek 5 te construeren.Hierbij wordt vanuit gegaan dat beide spelers optimaal spelen. Dit betekent dat een speler altijdeen zet zal doen, die het meest gunstigst voor hem is. Dit doet hij wetend dat zijn tegenspelerdit ook zal doen. Neem bijvoorbeeld het spelBOTER, KAAS EN EIEREN. Als spelerOdrie-op-een-rij kan maken, zal die dit ook zeker doen. Maar als spelerOtwee-op-een-rij kan maken, maardaardoor spelerXin de volgende zet drie-op-een-rij, moet spelerOspelerXblokkeren.In het spel Cilindrisch Hex is al het een en ander bekend, maar ook nog veel onbekend. Het spelwordt gespeeld op een cilindrisch bord vannrijen en omtrekmdoor speler Blauw en speler Rood,die om en om een tegel kleuren in hun kleur. Rood probeert een pad van boven naar beneden temaken en Blauw een kring om de cilinder heen. In [4] is bewezen dat er altijd een winnaar is; in[1] is een winnende strategie voor Rood bepaald voor een bord met even omtrek, en in [3] is ookeen winnende strategie gevonden voor Rood voor een bord met omtrek 3. Voor de andere bordenwordt vermoed dat hiervoor ook Rood een winnende strategie heeft, maar dat is nog niet bewezen[3]. Wat de strategie ?en zijn voor omtrekmmetm?5 oneven, is dus nog onbekend, en in dezescriptie wordt een poging gedaan deze te vinden; in het bijzonder voorm= 5.In Hoofdstuk 2 wordt het spelHEXenCILINDRISCH HEXuitgelegd. In Hoofdstuk 3 wordt eennieuw bewijs gegeven op de Cilindrische Hex-stelling. Deze stelling houdt in dat het spel niet ingelijkspel kan eindigen. Vervolgens worden in Hoofdstuk 4 de bestaande strategie ?en onderzochten voor de even omtrek een nieuw bewijs gegeven. Als laatste wordt dan het spel met omtrek 5onderzocht in Hoofdstuk 5.Show less
CE Delft has developed the CEGOIA-model to counsel Dutch governments and municipalities in the energy transition. CEGOIA can be used in any area, consisting of a certain number of neighbourhoods....Show moreCE Delft has developed the CEGOIA-model to counsel Dutch governments and municipalities in the energy transition. CEGOIA can be used in any area, consisting of a certain number of neighbourhoods. Using an integer linear programming optimization, it computes an allocation of energy systems to the neighbourhoods, such that the total cost for the area is minimized. Di?erent solvers have been used in CEGOIA to perform this optimization, but when the number of neighbourhoods is too large, the problem can not be solved within a reasonable amount of time. In combination with the fact that the problem is NP-hard, a heuristic has therefore been constructed. This heuristic consists of three di?erent parts that have all been developed and implemented in the python-based CEGOIA-model currently used by CE Delft. The final goal of this thesis was to be able to run CEGOIA on the Netherlands in its entirety. This thesis sets the mathematical framework for the optimization problem and gives a detailed description of the heuristic. Then, the results of the heuristic are shown and compared with problems that have already been optimized by CE Delft. Also, an analysis of the algorithm is given in which the complexity, existence of a solution and the general performance of the heuristic are investigated. Finally, the results are discussed and some alternative optimization methods are provided.Show less
Een geliefd uitje tijdens een vakantie in Griekenland is een bezoek aan de Dik-teon Grot op Kreta. Volgens de Griekse mythologie is deze grot de geboorteplekvan de oppergod Zeus, daarom wordt deze...Show moreEen geliefd uitje tijdens een vakantie in Griekenland is een bezoek aan de Dik-teon Grot op Kreta. Volgens de Griekse mythologie is deze grot de geboorteplekvan de oppergod Zeus, daarom wordt deze grot ook wel de grot van Zeus ge-noemd. De ingang van de grot ligt echter boven op een berg en is moeilijkbereikbaar met de auto. De weg naar de top is een hele klim dus lopen is,alhoewel mogelijk, niet altijd te prefereren. Gelukkig is er de mogelijkheid omde trip per ezel af te leggen. Aan de voet van de berg en bij de ingang van degrot zijn ezelverhuurplekken vanwaar je een ezel naar boven respectievelijk naarbeneden kan nemen. Er is echter maar een beperkt aantal ezels inzetbaar ende grot trekt grote aantallen toeristen die allemaal een ezeltocht willen maken.Een voor de hand liggende vraag is dan ook hoeveel ezels er minimaal nodig zijnom de grote aantallen toeristen te vervoeren. Wanneer veel toeristen enkel eenezel mee naar boven nemen en vervolgens besluiten zonder ezel af te dalen, kanhet voorkomen dat er bij de ezelverhuurplek aan de voet van de berg geen ezelsmeer beschikbaar zijn. In dat geval kan het handig zijn om een aantal ezels vanboven naar beneden te sturen, ook zonder passagier, om zo effici ?enter de ezelste verdelen over de twee verhuurplekken. Voor de ezelverhuurder kan het dusvoordelig zijn om een effici ?ente strategie te verzinnen wat betreft de ezelverde-ling. Deze strategie zouden we kunnen vinden met behulp van modelleren.In deze scriptie gaan we het systeem met de twee ezelverhuurplekken nader on-derzoeken. Dit doen we door een model van de situatie te construeren en teanalyseren. We proberen hiermee vragen over dit systeem te beantwoorden zo-als: Wat is de verwachte rijlengte van de klanten die per ezel naar boven willengaan? Of bijvoorbeeld: Wat is de gemiddelde verwachte tijdsduur dat de ezelsgeen klanten aan het vervoeren zijn?Het eerste en meest vereenvoudigde model bleek niet nauwkeurig genoeg om ge-makkelijk expliciete resultaten te vinden waarna we een tweede, nauwkeurigermodel hebben opgesteld en geanalyseerd. De modellen die we hiervoor constru-eren zijn niet eerder uitvoerig beschreven in de literatuur dus is het nodig dezeeerst grondig te bestuderen. In deze scriptie beginnen we met het beschrijvenen analyseren van de twee modellen. Vervolgens vergelijken we de modellen on-derling en onderzoeken we in welke mate het gecompliceerdere model ons meerkan vertellen over het systeem ten opzichte van het vereenvoudigde model.We kunnen met behulp van deze modellen een effici ?ente strategie proberen teformuleren wat betreft de verdeling van de ezels over de twee verhuurplekken.Helaas bleek naast de analyse van beide modellen een effici ?ente strategie vindente ambitieus en is het niet gelukt de scriptie uit te breiden met het vinden vaneen dergelijke strategie. Voor een volgend onderzoek kan het interessant zijnom voor dit model de meest effici ?ente strategie proberen te vinden.Show less
Combinatorial games where both players choose a move simultaneously are called synchronized games. If we consider games where any pair of Left and Rights moves can always be performed in some order...Show moreCombinatorial games where both players choose a move simultaneously are called synchronized games. If we consider games where any pair of Left and Rights moves can always be performed in some order, then a synchronized version of the game comes naturally. As it turns out, such games are always numbers as combinatorial games. However, games which are equal to each other as combinatorial games may behave differently as synchronized games. We may still assign each game a numerical value. One approach is to view synchronized games as zero-sum matrix games, and we call the value of the zero-sum game associated to a game its Nash value. Push and Shove are examples of rule sets which have natural synchronized versions, and for synchronized Push and Shove we show a result which is similar to the number avoidance theorem for combinatorial games. We also show that, for certain positions of Push and Shove, the difference in Nash value of n copies of the position and n?1 copies of the position tends to the combinatorial value of the position as n tends to infinity.Show less
