Zeeslag en Sudoku even moeilijk volgens speltheorie
Promotie Logica/Theoretische informatica
woensdag 4 oktober 12.00 uur
Bestaat er gereedschap om de moeilijkheid van een Sudoku te meten? De meeste mensen die wel eens een Sudoku maken, doen dat door het herhaaldelijk toepassen van een set regels. Op die manier kun je zeggen dat de moeilijkheid van een specifieke Sudoku bepaald wordt door het minimale aantal regels dat nodig is om de puzzel op te lossen. Maar is er ook een manier om twee soorten spellen te vergelijken? Zijn puzzels (zoals Sudoku en Zeeslag) moeilijker dan tweespelerspellen (zoals schaken en Stratego) en zijn spelen met onvolledige informatie moeilijker dan spelen met volledige informatie (zoals schaken en Sudoku)? Merlijn Sevenster richtte zich in zijn onderzoek vooral op de laatste vraag. Een spel met onvolledige informatie is een spel waarin een speler op een gegeven moment niet de beschikking heeft over de volledige stand van zaken. Scotland Yard, bridge, kwartet, Mastermind en memory zijn voorbeelden van zulke spelen.
Sevenster gebruikte technieken uit de theoretische informatica waarmee de complexiteit van willekeurige computerprogramma's vastgesteld kan worden. Zoals gebruikelijk in de combinatorische speltheorie wordt de moeilijkheid van een spel gelijkgesteld aan de complexiteit van het beste computerprogramma dat een pad uitrekent dat 'leidt tot succes'. Dus in het geval van Sudoku's zou zo'n programma de oplossing moeten genereren en in het geval van schaken een strategie die wint ongeacht de zetten van de tegenstander. Volgens deze meetlat zijn Zeeslag en Sudoku precies even moeilijk zijn. Sevenster laat verder onder andere zien dat de onvolledige informatie de moeilijkheid van het spel Scotland Yard niet vergroot ten opzichte van de meeste tweespelerspellen met volledige informatie.
M. Sevenster: Branches of imperfect information: logic, games, and computation. Promotoren zijn prof. dr. J.F.A.K. van Benthem en dr. P. van Emde Boas, lector.
Meer informatie over de items in deze agenda kunt u krijgen bij de afdeling Persvoorlichting, tel. 020 - 525 2695, e-mail:
Universiteit van Amsterdam