Los een simpel schaakprobleem op en win een miljoen dollar

Wiskunde en schaken

Wiskunde en schaken hebben veel met elkaar gemeen. Een belangrijk voorbeeld is hierbij het leren schaken en wiskunde leren. Wat is de beste methode? Zowel bij het schaken als bij wiskunde bestaan er verschillende methoden en over deze methoden vindt veel discussie plaats. Bij het schaken scoort de Stappenmethode om didactische redenen hoog en er is een soortgelijke methode om wiskunde te leren die eveneens hoog scoort.

Wiskundigen hebben zich door de eeuwen heen laten inspireren door het schaakbord en de stukken en hebben hiermee mooie problemen gemaakt. Bij onze publicaties over Wie is de slimste? kregen we de mooiste oplossingen van voorgelegde problemen van wiskundig onderlegde schakers, soms doctors in de wiskunde! Het is overigens maar een zeer kleine groep die dit soort problemen oplossen interessant vindt. En natuurlijk worden er bij het zoeken  van oplossingen computerprogramma’s gebruikt.

Acht koninginnen

Een klassiek probleem uit het midden van de negentiende eeuw is het koninginnenprobleem. Plaats acht koninginnen op het schaakbord zodat ze elkaar niet aanvallen. In veel boeken en artikelen over schaken en wiskunde kom je dit probleem in de een of andere vorm tegen. Met oudere basisschoolkinderen wordt dit probleem met behulp van chocoladeschaakkoekjes spelenderwijs opgelost onder begeleiding van de schaakdocent. En het mooiste is natuurlijk de koekjes aan het einde te mogen opeten.

Frustr8tor

 

 

In deze moderne tijd van gamen heeft de heer Eckhart een aantal jaren geleden een elektronisch zakpuzzelspel ontwikkeld en uitgebracht onder de naam Frustr8tor met het thema van acht koninginnen plaatsen op het elektronisch schaakbordje. Voor deze braingame maakte Hans Böhm nog een reclamefilmpje.

 

Computer lost het probleem op

Volgens wiskundigen kunnen acht koninginnen op meer dan 4 miljard manieren op een schaakbord worden geplaatst. En er zijn slechts 92 goede oplossingen. Als rotaties en spiegelingen e.d. worden geëlimineerd blijven er slechts 12 basisoplossingen over. Computers hebben met meer dan vier miljard te onderzoeken mogelijkheden natuurlijk geen enkele moeite. In een mum van tijd (microseconden) hebben ze dit opgelost met brute force.

Maar stel je nu eens een schaakbord voor van 100 bij 100 velden waarop je 100 koninginnen moet plaatsen of een bord van 1000 bij 1000 velden waarop je 1000 koninginnen moet plaatsen. Dat is andere koek zelfs voor de sterkste en snelste supercomputers. Met brute force moeten ze misschien duizend jaar rekenen om dit probleem te kunnen oplossen.

De vraag is of er door toepassing van kunstmatige intelligentie, zelflerende computers of andere technieken aanzienlijk snellere methoden zijn om dit probleem op te lossen?

Win een miljoen dollar!

De computerwetenschappers en onderzoekers van de Universiteit van St Andrews in Schotland,  Ian P. Gent, Cristopher Jefferson en  Peter Nightingale dagen ons uit een computerprogramma te maken  waarmee het probleem aanzienlijk sneller kan worden opgelost. Dit is belangrijk want als er een snelle oplossing is kan dit mogelijk worden gebruikt om andere belangrijke problemen op te lossen die ons dagelijks raken. Zij publiceerden hun bevindingen recent in The Journal of Artificial Intelligence Research nr. 59 (2017), p 815-848.

 

Peter Nightingale en Ian Gent

Internationaal kreeg dit veel aandacht. Frederic Friedel schreef op Chessbase een artikel met daarin ook de mogelijkheid om  het acht koninginnenprobleem met een Java-applet op te lossen op de site.  Friedel beperkte zich tot een eerste stap, maar er wordt meer gevraagd.

 

Gevraagd: een algemeen geldend algoritme en snelle oplossing (in polynomiale tijd) voor N-koninginnen (met completeren)  op een N bij N schaakbord.

Het Clay Mathematics Institute in Amerika meldt dat hiervoor een miljoen dollar beschikbaar is, als onderdeel van de zgn. Millennium Prijzen. Het koninginnenprobleem is een belangrijke benchmark voor kunstmatige intelligentie toegepast op zeer complexe problemen.

 

 

Bovenstaande oplossing is nog niet voldoende om een miljoen dollar te verdienen. Er is nog een tweede stap nodig. Hierbij worden enkele koninginnen willekeurig op het schaakbord geplaatst en moet het bord gecompleteerd worden met het plaatsen van de resterende koninginnen onder de voorwaarde dat de koninginnen elkaar niet mogen aanvallen. Dit geldt natuurlijk ook bij het willekeurig plaatsen van de koninginnen. Als hier voor een supersnel algoritme (in polynomiale tijd) wordt gevonden is het miljoen binnen. Deze oplossingsmethode moet ook algemeen geldend zijn. En het miljoen verdien je mogelijk ook als aangetoond en bewezen kan worden dat dit probleem onoplosbaar is.

Ook dit koninginnenprobleem met completeren stamt uit het midden van de negentiende eeuw. Probeer het maar eens op het klassieke schaakbord. Hoeveel oplossingen zijn er dan?

Het probleem van Nauck uit 1850

Zet de resterende zes koninginnen op het bord zodat ze elkaar niet aanvallen.

Mooi dat zo’n klassiek probleem uit de negentiende eeuw nog zo actueel is in een tijd van supercomputers en kunstmatige intelligentie. En dan is er ook nog eens een miljoen dollar mee te verdienen. Lijkt me een leuke uitdaging voor studenten!