Oplossingen voor Dreshers hoger lager spel voor N <= 980

Title

Oplossingen voor Dreshers hoger lager spel voor N <= 980

 Author

Stassen, Misha (TU Delft Electrical Engineering, Mathematics and Computer Science)

Contributor

Fokkink, Robbert (mentor)
van den Dries, Bart (graduation committee)
Gijswijt, Dion (graduation committee)

Degree granting institution

Delft University of Technology

 Date

2018-05-16

 Abstract

Melvin Dresher beschouwde in zijn boek uit 1961 over speltheorie een getallenraadspel over N getallen. Hij liet zien hoe de optimale strategieën van beide spelers kon worden gevonden met behulp van lineair programmeren. Later toonde Selmer Johnson oplossingen voor N<=11 en merkte op dat de berekeningen steeds complexer werden bij toenemende N. Deze thesis beschrijft technieken om het spel op te lossen voor N<=980. Het algoritme van Dresher vormt nog steeds de basis, maar er zijn enkele aanpassingen. Niet alle voorwaarden worden bijvoorbeeld in het begin gegenereerd. Voorwaarden worden alleen op het moment dat ze nodig zijn gevonden met een subroutine. Dit is een vorm van delayed column generation. Er wordt ook gebruik gemaakt van heuristieken, zoals het schatten van de optimale kansverdeling van één van de spelers. Dit werk verschaft meer inzicht in het patroon van de oplossingen van dit spel en of enkele eerder geformuleerde vermoedens van Selmer Johnson en Edgar Gilbert over dit spel kloppen.

 Subject

Game Theory
Dynamic Programming
linear programming
Linear optimization
speltheorie
lineair programmeren
dynamisch programmeren

 To reference this document use:

http://resolver.tudelft.nl/uuid:6b5bf43a-85e8-4e3a-a04f-f27a3df3ddbe

 Part of collection

Student theses

 Document type

bachelor thesis

 Rights

© 2018 Misha Stassen
Files
PDF BSc_thesis_Misha_Stassen_final.pdf 614.98 KB
MP4 kansverdeling_Alice.mp4 464.22 KB
Close viewer