Oplossingen voor Dreshers hoger lager spel voor N <= 980

Bachelor thesis (2018)

Authors

M.J. Stassen Electrical Engineering, Mathematics and Computer Science

Contributors

R.J. Fokkink (supervisor 1)
B. van den Dries (supervisor 2)
Dion Gijswijt (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2018 Misha Stassen
Game Theory Dynamic Programming Linear optimization Speltheorie Lineair programmeren Dynamisch programmeren Linear programming
More Info
expand_more

Published Date

16-05-2018

Language

Dutch

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

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.