Leer of solitaire kan worden opgelost door algoritmes, hoe AI-solvers werken en wat ze onthullen over strategie.
Ja — en nee, afhankelijk van wat “opgelost” precies betekent en over welke variant we spreken. Computationele oplossers hebben elke deal in de standaard genummerde set van FreeCell volledig geanalyseerd, de acht onwinbare deals met zekerheid gecatalogiseerd en bevestigd dat de overige ruim 32.000 allemaal winbaar zijn. Dezelfde soorten oplossers hebben ook de winbaarheidsgrenzen vastgesteld die in deze strategische cluster terugkomen: het aandeel Klondike-, Spider- en Forty Thieves-deals dat int
Ja — en nee, afhankelijk van wat “opgelost” precies betekent en over welke variant we spreken. Computationele oplossers hebben elke deal in de standaard genummerde set van FreeCell volledig geanalyseerd, de acht onwinbare deals met zekerheid gecatalogiseerd en bevestigd dat de overige ruim 32.000 allemaal winbaar zijn. Dezelfde soorten oplossers hebben ook de winbaarheidsgrenzen vastgesteld die in deze strategische cluster terugkomen: het aandeel Klondike-, Spider- en Forty Thieves-deals dat intrinsiek oplosbaar is, is met hoge betrouwbaarheid geschat via geautomatiseerde uitputtende zoektochten over miljoenen willekeurig gegenereerde deals. In die zin is solitaire algoritmisch in grote mate opgelost: de wiskunde van welke deals winbaar zijn, is grotendeels vastgesteld, en geautomatiseerde oplossers kunnen voor de meeste winbare deals die ze tegenkomen een winnende zetvolgorde vinden.
In een andere betekenis is solitaire nog niet volledig algoritmisch opgelost, en de onopgeloste aspecten zijn oprecht moeilijke computationele problemen. De winbaarheidsanalyse van Klondike is niet exact — het blijft een kansbereik van ongeveer 79–91% winbaar in plaats van een precieze waarde — omdat de onzekerheid van de gesloten kaarten in Klondike een verborgen-informatieprobleem creëert dat volledige uitputtende analyse op schaal computationeel onhandelbaar maakt. Zelfs in volledig zichtbare varianten zoals FreeCell is het bepalen of een specifieke positie winbaar is een probleem in de complexiteitsklasse PSPACE-compleet — een klasse die algemeen als moeilijker wordt beschouwd dan NP-complete problemen en waarvoor geen polynomiaal algoritme bekend is. Het bestaan van efficiënte algoritmen die alle solitairevarianten perfect en binnen redelijke tijd oplossen, wordt door geen enkel huidig wiskundig resultaat gegarandeerd, en verschillende varianten blijven open onderzoeksvragen in de informatica.
Vanuit een algoritmisch perspectief is solitaire een zoekprobleem voor één speler: beginnend vanuit een beginstaat, dus de geschudde deal, moet de oplosser een reeks legale zetten vinden die de beginstaat omzet in de winstaat, waarin alle kaarten in correcte volgorde op de foundations liggen. De toestandsruimte — het totale aantal verschillende bordposities waar het spel doorheen kan gaan — is astronomisch groot. Een enkel spel Klondike heeft een toestandsruimte die wordt geschat op miljarden tot biljoenen verschillende posities wanneer alle mogelijke zetreeksen vanuit alle mogelijke startdeals worden meegeteld. Forty Thieves, met zijn 80-kaarten tellende tableau op twee decks, heeft een proportioneel grotere toestandsruimte die uitputtend zoeken computationeel duur maakt, zelfs voor moderne hardware.
Uitputtende depth-first search: exacte antwoorden, hoge rekenkosten. Depth-first search, of DFS, verkent elke mogelijke zetreeks vanaf de beginpositie en keert terug zodra doodlopende takken worden bereikt, totdat ofwel een winnende weg is bevestigd, of alle paden als verliezend zijn vastgesteld. Voor FreeCell, waar volledige informatie de toestandsruimte volledig opsombaar maakt, kan DFS sluitend bepalen of een specifieke deal winbaar is en een winnende zetreeks vinden als die bestaat. De acht onwinbare FreeCell-deals, waaronder de bekende deals 11.982 en 146.692, zijn geïdentificeerd door DFS-oplossers die via uitputtende verkenning bevestigden dat geen enkele legale zetreeks vanaf die beginposities naar winst leidt. Voor Klondike botst DFS op het verborgen-informatieprobleem: gesloten kaarten kunnen één van verschillende mogelijke kaarten zijn, en de oplosser moet ofwel specifieke verborgen kaartwaarden aannemen, wat conclusies oplevert die afhankelijk zijn van die aannames, of vertakken over alle mogelijke toewijzingen van verborgen kaarten, wat de zoekruimte vermenigvuldigt met het aantal mogelijke verborgen configuraties en volledige uitputtende analyse voor grote steekproeven onhaalbaar maakt. Daarom is Klondikes winbaarheidspercentage een bereik in plaats van een exact cijfer — het is het resultaat van probabilistische steekproeven over veel willekeurige deals in plaats van volledige uitputtende analyse van alle mogelijke deals.
Heuristische best-first search: snelle bijna-optimale oplossingen, maar geen volledigheidsgarantie. Best-first search gebruikt een evaluatiefunctie — een heuristische score die de kwaliteit van een bordpositie schat — om te bepalen welke toestanden eerst worden onderzocht. Een goede heuristiek voor solitaire kan posities waarderen op basis van het aantal foundationkaarten, het aantal blootgelegde gesloten kaarten, het aantal beschikbare legale zetten en de mate van suit-consolidatie in de tableaureeksen. Best-first search met een goede heuristiek vindt winnende oplossingen dramatisch sneller dan DFS op winbare deals, maar kan niet garanderen dat de gevonden oplossing optimaal, dus het kortst, is, en kan zelfs falen op deals waarbij het winnende pad tijdelijk wegloopt van wat de heuristiek als een goede positie beschouwt. De heuristische best-first aanpak is het meest direct analoog aan menselijke expertstrategie: beide gebruiken een kwaliteitsfunctie voor posities om zetkeuzes te sturen, beide verkennen eerst veelbelovende paden, en beide kunnen oplossingen missen die contra-intuïtieve tussenposities vereisen die er eerst slechter uitzien voordat ze beter worden.
Het heuristische zoekmodel verklaart waarom de geforceerde scanvolgorde werkt. De geforceerde scanvolgorde — Foundation? Openleggen? Pure build? Lege kolom? Stock als laatste — is een menselijk uitvoerbare heuristiek die prioriteitsgewichten toekent aan zettypen op dezelfde manier als een algoritmische heuristiek prioriteitsscores toekent aan bordposities. Foundationzetten krijgen prioriteit omdat ze de winconditie direct bevorderen. Openlegzetten krijgen prioriteit omdat ze de toestandsruimte van toekomstige winbare posities uitbreiden. Stocktrekkingen worden naar achteren geschoven omdat ze eindige middelen verbruiken waarvan de waarde het hoogst is wanneer het tableau volledig is geëvalueerd. Deze prioriteitsvolgorde is niet willekeurig — ze komt nauw overeen met de zetprioriteiten die empirisch getrainde solitaire-heuristieken aan dezelfde zettypen toekennen. De geforceerde scanvolgorde is in feite een handmatig uitvoerbare benadering van de best-first heuristiek die geautomatiseerde oplossers gebruiken.
De undo-functie maakt menselijk hypothese-testen mogelijk dat analoog is aan algoritmisch vertakken. Geautomatiseerde oplossers verkennen meerdere takken van de zetboom tegelijk en keren terug vanuit doodlopende takken om alternatieve paden te proberen. Menselijke spelers kunnen niet tegelijk meerdere takken verkennen, maar de undo-functie in online solitaire biedt een benadering: de speler kan een zet doen, enkele zetten later de gevolgen observeren, en teruggaan naar het vertakkingspunt om een alternatief te proberen als het eerste pad weinigbelovend blijkt. Dit speculatieve vertakken — een zet doen om een hypothese te testen over wat hij mogelijk maakt, en terugdraaien als de hypothese wordt weerlegd — is het menselijk speelbare equivalent van de backtrackingstap in DFS. Spelers die undo systematisch gebruiken voor hypothese-testen in plaats van alleen voor foutcorrectie, passen een menselijke versie toe van het uitputtende zoeken dat DFS-oplossers effectief maakt op complexe posities.
Het herkennen van circulaire afhankelijkheden is de menselijk uitvoerbare versie van dead-end detectie. Wanneer een DFS-oplosser een positie bereikt van waaruit geen winnend pad bestaat, ontdekt hij dit door alle mogelijke voortzettingen uit te putten en vast te stellen dat geen ervan naar winst leidt — een computationeel dure procedure. Menselijke spelers kunnen een deel van zulke doodlopende posities veel sneller detecteren door circulaire afhankelijkheden te herkennen: configuraties waarin kaart A niet kan bewegen voordat kaart B beweegt en kaart B niet kan bewegen voordat kaart A beweegt, zonder dat er een externe oplossing beschikbaar is. Deze controle op circulaire afhankelijkheid is een menselijk uitvoerbare dead-end-detectieheuristiek die, wanneer hij positief uitvalt, dezelfde informatie geeft als algoritmische dead-end detectie zonder uitputtend zoeken te vereisen. Het ontwikkelen van de gewoonte om circulaire afhankelijkheden te identificeren is het belangrijkste praktische voordeel van begrijpen hoe algoritmische oplossers werken — het zet een dure computationele procedure om in een snelle, menselijk uitvoerbare controle die tot hetzelfde opgeefbesluit leidt.
Geloven dat het bestaan van algoritmische oplossers betekent dat elke deal oplosbaar is. Algoritmische oplossers vinden winnende paden op winbare deals — ze creëren geen winnende paden waar die niet bestaan. De acht onwinbare FreeCell-deals zijn juist door algoritmische oplossers geïdentificeerd omdat die alle mogelijke paden uitputten en geen enkel pad naar winst vonden. In varianten met hogere percentages onwinbare deals, zoals Forty Thieves met ongeveer 40–60% en Spider 4-Suit met ongeveer 45–60%, bevestigen algoritmische oplossers dat een groot deel van de willekeurige deals geen winnend pad heeft, wat betekent dat geen enkel algoritme — hoe geavanceerd ook — die spellen kan winnen. Het bestaan van krachtige oplossers verandert de structuur van de dealruimte niet; het maakt het alleen mogelijk die structuur nauwkeuriger te analyseren.
Aannemen dat het door een oplosser gevonden winnende pad het enige winnende pad is. De meeste winbare solitairedeals hebben meerdere winnende paden — meerdere verschillende zetreeksen die allemaal naar de winstconditie leiden. Een oplosser die één winnend pad vindt, heeft niet noodzakelijk het enige pad gevonden; hij heeft één pad gevonden uit mogelijk honderden of duizenden. Dit is belangrijk voor menselijke spelers omdat het specifieke pad van de oplosser sterk contra-intuïtief kan zijn — het kan een zet vereisen die er enkele zetten lang actief schadelijk uitziet voordat het voordeel zichtbaar wordt — terwijl andere winnende paden voor dezelfde deal toegankelijker zijn voor menselijke patroonherkenning. Het bestaan van een door de oplosser gevonden winnend pad bevestigt dat de deal winbaar is; het is niet per se een handleiding voor de efficiëntste menselijke aanpak van diezelfde deal.
FreeCell is het optimale spel om de verbinding tussen algoritme en strategie te ervaren, omdat de volledige informatie de relatie tussen systematische zoekopdrachten en correct spel direct observeerbaar maakt. Een FreeCell-speler die methodisch de zetboom volgt — alle legale zetten evalueert, het hoogste prioriteitspad selecteert, ongedaan maken gebruikt om alternatieve takken te testen, en cirkelvormige afhankelijkheden identificeert die doodlopende wegen bevestigen — voert een vereenvoudigde versie uit van de heuristische best-first search.
Het door mensen uitvoerbare algoritme dat het dichtst in de buurt komt van wat geautomatiseerde oplosprogramma's doen, combineert drie componenten: de gedwongen scanvolgorde als een zet-prioriteitsheuristiek (Fundament → Ontdekken → Pure opbouw → Lege kolom → Voorraad), ongedaan maken-gebaseerde hypothesetests als een backtrackingmechanisme, en identificatie van cirkelvormige afhankelijkheden als een snelkoppeling voor het detecteren van doodlopende wegen. Samen implementeren deze drie componenten een vereenvoudigde heuristische best-first search met backtracking en gedeeltelijke doodlopende wegdetectie.
Het menselijk uitvoerbare algoritme dat het dichtst benadert wat geautomatiseerde oplossers doen combineert drie componenten: de geforceerde scanvolgorde als heuristiek voor zetprioriteit, dus Foundation → Openleggen → Pure build → Lege kolom → Stock; undo-gebaseerd hypothese-testen als backtrackingmechanisme; en het identificeren van circulaire afhankelijkheden als snelkoppeling voor dead-end detectie. Samen implementeren deze drie componenten een vereenvoudigde heuristische best-first search met backtracking en gedeeltelijke dead-end detectie — precies de drie componenten die de effectiefste geautomatiseerde oplossers definiëren, maar dan teruggebracht tot menselijke cognitieve schaal. Een speler die alle drie als consequente gewoonten ontwikkelt, voert de dichtstbijzijnde menselijke benadering uit van het algoritme dat de winrate over de volledige dealverdeling maximaliseert.
FreeCell is het makkelijkst voor algoritmen om op te lossen om dezelfde redenen dat het ook het meest tractable is voor menselijke strategische analyse: volledige informatie elimineert het vertakkingsprobleem van verborgen kaarten, bijna-100% winbaarheid betekent dat bijna alle posities winnende paden bevatten, en vier vrije cellen plus acht kolommen bieden genoeg stagingflexibiliteit zodat de oplossingsroute zelden contra-intuïtieve regressieve zetten vereist. De computationele complexiteit van het oplossen van een specifieke FreeCell-positie is in het slechtste geval nog steeds PSPACE-compleet — wat betekent dat geen polynomiaal algoritme gegarandeerd bestaat — maar in de praktijk vinden goed geïmplementeerde heuristische oplossers voor bijna alle FreeCell-deals binnen milliseconden winnende paden. Spider 1-Suit is op soortgelijke wijze tractable vanwege de beperking tot één soort. Aan het moeilijke uiteinde maakt de verborgen informatie van Klondike het voor algoritmen moeilijker om definitieve oplossingen te geven dan de schijnbare eenvoud doet vermoeden, en Forty Thieves’ grote toestandsruimte op twee decks met beperkte bouwregels maakt het computationeel duur, zelfs wanneer volledige informatie wordt aangenomen.
Voor varianten met volledige informatie, zoals FreeCell en Yukon, kan een voldoende krachtige computer elke specifieke deal oplossen via uitputtend zoeken — de winbaarheid bevestigen en een winnend pad vinden als dat bestaat. Voor varianten met verborgen informatie, zoals Klondike, vermenigvuldigen de toewijzingen van verborgen kaarten de zoekruimte: een Klondike-deal definitief oplossen vereist het oplossen van alle mogelijke verborgen kaartconfiguraties, wat op schaal computationeel onhandelbaar is, zelfs met zeer krachtige hardware. Het theoretische antwoord is ja — onbeperkte rekenkracht lost alle gevallen op — maar het praktische antwoord is dat Klondike en soortgelijke varianten met verborgen informatie computationeel moeilijk blijven, zelfs voor huidige geautomatiseerde oplossers, en daarom worden hun winbaarheidspercentages als kansschattingen uitgedrukt in plaats van als exacte waarden. Deze computationele moeilijkheid is geen tijdelijke beperking die vanzelf verdwijnt naarmate hardware beter wordt; ze weerspiegelt een structurele eigenschap van het verborgen-informatieprobleem, behorend tot een klasse van problemen waarvoor geen efficiënte algemene oplossing bekend is.