Algoritme vraag: Oplossen puzzelspel

[Emiel L]

Inleiding

Al weer enige jaren heb ik in de App Store een puzzelspelletje staan genaamd Exit16. De bedoeling van het spel is om blokjes met dezelfde kleur met elkaar te combineren, waarna ze verdwijnen. Blokjes kunnen niet door muren en kunnen alleen horizontaal en verticaal bewegen. Als het speelveld leeg is, komt er weer een nieuwe puzzel. Op dit moment bevat het spel 104 puzzels, en ben ik van plan er nog een behoorlijk aantal bij te maken.



Hier zit meteen de crux... alle 104 levels die er nu in zitten zijn tot stand gekomen door een puzzel te maken en vervolgens zelf te kijken of ik 'm op kan lossen. Daarbij schat ik zelf in hoe ingewikkeld een level is, zodat tijdens het spelen van het spel er niet te veel heel moeilijke puzzels achter elkaar komen, maar je als speler ook even op adem kan komen.

Nu zou ik het 'testen' van een puzzel en een optimale oplossing graag door de computer willen laten uitrekenen, zodat ik het spel kan uitbreiden met een sterren rating per level, een score, achievements, etc, etc. Ik kan alleen niet een handig en snel algoritme bedenken om dit voor elkaar te krijgen.

Relevante software en hardware die ik gebruik

Het spel is ontwikkeld in Swift en geschikt voor iOS. Maar voor een level solver maakt de taal natuurlijk helemaal niets uit. De levels zijn opgeslagen als een JSON bestand, dus het inlezen kan ook in elke denkbare taal relatief eenvoudig gedaan worden.

Wat ik al gevonden of geprobeerd heb

Ik heb dus Google lastig gevallen en heb geprobeerd zelf wat te verzinnen. Ik kwam daarbij termen als wave function collapse tegen, maar ik weet niet helemaal zeker of dat een route is die ik zou moeten volgen.

Dus... zijn er hier algoritmische alleskunners die me in de juiste richting kunnen duwen?

[RobIII]

Is het niet veel handiger om achteruit te werken? Zoals je een Rubik's cubus door elkaar husselt (en onthoudt hoe je dat gedaan hebt) en dan de gehusselde cubus presenteren als puzzel. Ditto voor jouw game?
Het aantal stappen is dan niet garandeerd 't minst aantal stappen, maar wel een goede indicatie van in hoeveel stappen 't minimaal mogelijk moet zijn.

[ Voor 27% gewijzigd door RobIII op 15-05-2023 14:43 ]

[Emiel L]

RobIII schreef op maandag 15 mei 2023 @ 14:41:
Is het niet veel handiger om achteruit te werken? Zoals je een Rubik's cubus door elkaar husselt (en onthoudt hoe je dat gedaan hebt) en dan de gehusselde cubus presenteren als puzzel. Ditto voor jouw game?

Ja, waarschijnlijk wel. Maar dat gaat me niet helpen voor de bestaande puzzels die ik al heb. En de puzzels zijn nu ook zo dat ze er soort van OK uit zien in hun beginsituatie, ik weet niet of ik dat achteruit werkend ook voor elkaar zou krijgen.

Ik vind het wel een leuke invalshoek.

[RobIII]

Nja, zonder je game daadwerkelijk te downloaden en spelen kan ik je iig niet helpen met de informatie die je geeft in je topicstart. Er staat heel veel, maar inhoudelijk hebben we eigenlijk alleen iets aan "De bedoeling van het spel is om blokjes met dezelfde kleur met elkaar te combineren, waarna ze verdwijnen." en ik denk dat daar wel iets meer regeltjes in zitten (zoals: blokjes kunnen niet door muren of rode blokjes zijn 5 keer zoveel waard of... ).
Kijk, jij kent je game als geen ander, maar probeer je even voor te stellen hoe iemand je topicstart moet lezen die nog nooit van je game gehoord heeft of nog nooit dergelijke games gespeeld heeft.

[ Voor 17% gewijzigd door RobIII op 15-05-2023 14:47 ]

[naitsoezn]

Ik zou het denk ik iteratief aanpakken door bij het begin te beginnen: Alle regels duidelijk hebben, en de stappen die de speler moet doorlopen om de puzzel op te lossen. Welke opties zijn er allemaal op welk moment in het spel, en welke van die opties is de beste keus en waarom. Dan kun je gaan beginnen met een 'domme' computer-speler die gewoon domweg alle opties doorloopt. Daarna kun je slimmere trucjes gaan toepassen en eventuele optimalisatie-stappen. Begin bij een simpele puzzel die in een paar stappen op te lossen is en ga dan langzaam door richting complexere puzzels. Als je de logica voor de simpele puzzels goed geïmplementeerd hebt, zou die ook moeten werken op de complexere puzzels

Als je dan een computer-solver hebt, kun je gaan nadenken hoe je eventuele complexiteit kwantificeert.

[ Voor 17% gewijzigd door naitsoezn op 15-05-2023 14:51 ]

[Emiel L]

RobIII schreef op maandag 15 mei 2023 @ 14:46:
"De bedoeling van het spel is om blokjes met dezelfde kleur met elkaar te combineren, waarna ze verdwijnen." en ik denk dat daar wel iets meer regeltjes in zitten (zoals: blokjes kunnen niet door muren of rode blokjes zijn 5 keer zoveel waard of... ).
Kijk, jij kent je game als geen ander, maar probeer je even voor te stellen hoe iemand je topicstart moet lezen die nog nooit van je game gehoord heeft of nog nooit dergelijke games gespeeld heeft.

Nou ja, de enige onbeschreven regel heb je zelf al gededuceerd. Blokjes kunnen niet door muren heen. En ze kunnen alleen horizontaal en verticaal bewegen. Ik heb de ts aangepast.

[RobIII]

Emiel L schreef op maandag 15 mei 2023 @ 15:11:
[...]

Nou ja, de enige onbeschreven regel heb je zelf al gededuceerd.

En twee blokjes van dezelfde kleur "naast elkaar" is voldoende? Moeten 't er vier zijn? Op een rij? Of is een T-vorm ook goed? Wat als ik in je screenshot het oranje blokje in het (verticale) midden naar links beweeg en daarna het meest rechtse groene blokje 1 positie naar links zet? Verdwijnen die "drie op een (verticale) rij" dan en waar moet ik dan blijven met het overgebleven groene blokje linksonder? Als er in een level 12 groene blokjes zijn, verdwijnen ze dan pas als alle 12 de blokjes 'elkaar raken' of kan ik ook groepjes van 2, 3 of 4 maken en verdwijnen dan die groepjes?

Je hebt vanuit elke positie maar een X aantal mogelijke zetten. Dat lijkt me dan toch vrij makkelijk te brute-forcen, zoals @naitsoezn ook al aangeeft? (Afgaand op de puzzel uit je TS). Doe dat recursief, reken voor elke positie de mogelijke zetten door, kies de kortste oplossing als beste.

[ Voor 67% gewijzigd door RobIII op 15-05-2023 15:44 ]

[Emiel L]

RobIII schreef op maandag 15 mei 2023 @ 15:15:
[...]

En twee blokjes van dezelfde kleur "naast elkaar" is voldoende? Moeten 't er vier zijn? Op een rij? Of is een T-vorm ook goed? Wat als ik in je screenshot het oranje blokje in het (verticale) midden naar links beweeg en daarna het meest rechtse groene blokje 1 positie naar links zet? Verdwijnen die "drie op een (verticale) rij" dan en waar moet ik dan blijven met het overgebleven groene blokje linksonder? Als er in een level 12 groene blokjes zijn, verdwijnen ze dan pas als alle 12 de blokjes 'elkaar raken' of kan ik ook groepjes van 2, 3 of 4 maken en verdwijnen dan die groepjes?

Dat staat in de tekst. Combineren, en dat mag op alle mogelijke manieren, dus hoeft niet verder uitgewerkt te worden. Voor score berekening zou het kunnen zijn dat 1x 4 blokjes meer punten oplevert dan een oplossing met 2x 2 blokjes, maar zo ver zijn we nog niet.

De tekst zegt dat je een nieuwe puzzel krijgt als je veld leeg is, dus je mag niet één blokje van een kleur overhouden.

Je hebt vanuit elke positie maar een X aantal mogelijke zetten. Dat lijkt me dan toch vrij makkelijk te brute-forcen, zoals @naitsoezn ook al aangeeft? (Afgaand op de puzzel uit je TS). Doe dat recursief, reken voor elke positie de mogelijke zetten door, kies de kortste oplossing als beste.

Dat loopt heel erg snel op qua mogelijkheden, en bij het naar links schuiven van een blokje is daarna naar rechts schuiven een geldige ‘zet’. Een simpele recursieve aanpak komt er dus niet; een vorm van backtracking die eerder ontstane varianten/lay-outs blokkeert is wel nodig.

[Feanathiel]

Emiel L schreef op maandag 15 mei 2023 @ 16:40:

[...]

Dat loopt heel erg snel op qua mogelijkheden, en bij het naar links schuiven van een blokje is daarna naar rechts schuiven een geldige ‘zet’. Een simpele recursieve aanpak komt er dus niet; een vorm van backtracking die eerder ontstane varianten/lay-outs blokkeert is wel nodig.

Emphasis-mine. Dat bijhouden is dan ook geen optie als ik het zo lees? Er zijn heel wat mogelijkheden om af te gaan, en net zoveel mogelijkheden om bij te houden of dat je die stap al gemaakt hebt. Of als je twee/drie stappen doet, en de laatste brengt je weer naar het initiële speelveld, is dat dan dezelfde actie?

Wellicht dat een (vorm van) Monte Carlo zoekboom interessant kan zijn? Je geeft je speelveld een score, hoe "opgelost" of hoe "slecht" men er voor staat (kun je heel ver in gaan). Dan kun je ook objectief beoordelen of een zet beter of slechter is tegenover de huidige staat. Je werkt een paar stappen willekeurig uit, eventueel daar de stappen weer van, om vervolgens te kunnen zien of je de goede richting op gaat. Dan zal daar allicht niet de beste oplossing terug komen, maar dan weet je wel in hoeveel stappen het in ieder geval kan. Paar keer laten oplossen dan een optie?

Edit zonder meteen een nieuw commentaar te plaatsen: De methodiek kan prima eerst een slechtere stap zetten om vervolgens een veel betere stap dan de rest te maken. Dat hangt af hoe je het resultaat laat terugbubbelen hoger de boom in.

[ Voor 7% gewijzigd door Feanathiel op 15-05-2023 23:42 ]

[skimine]

Emiel L schreef op maandag 15 mei 2023 @ 16:40:
De tekst zegt dat je een nieuwe puzzel krijgt als je veld leeg is, dus je mag niet één blokje van een kleur overhouden.

Maar het is dus wel mogelijk dat dat gebeurt? Want dat geeft al een mogelijkheid om een route die niet werkt voortijdig af te kappen.

[Emiel L]

skimine schreef op maandag 15 mei 2023 @ 20:05:
[...]

Maar het is dus wel mogelijk dat dat gebeurt? Want dat geeft al een mogelijkheid om een route die niet werkt voortijdig af te kappen.

Zeker, dat kan gebeuren. Als je het spel speelt gaat dat blokje heen en weer wiebelen en een tap op het scherm herstart die specifieke puzzel dan.

Feanathiel schreef op maandag 15 mei 2023 @ 19:50:
[...]
Emphasis-mine. Dat bijhouden is dan ook geen optie als ik het zo lees? Er zijn heel wat mogelijkheden om af te gaan, en net zoveel mogelijkheden om bij te houden of dat je die stap al gemaakt hebt. Of als je twee/drie stappen doet, en de laatste brengt je weer naar het initiële speelveld, is dat dan dezelfde actie?

Ik denk dat je dat dan wel als dezelfde actie moet beschouwen, het speelveld is immers niet veranderd ten opzichte van een paar zetten terug. Ik had al zitten denken of ik een hashfunctie zou kunnen verzinnen en de hashes van eerder gepasseerde posities zo snel kan vergelijken. Het zorgt er wel voor dat hele grote delen van de zoek-boom snel weggeknipt kunnen worden.

Bij het bepalen van de hash zouden alleen de kleuren (en posities natuurlijk) van de blokjes er toe doen, en daar zijn er 12 van. Dat past in 4 bits. Een puzzel is max 10x10 blokjes, dus een level is in theorie volledig te beschrijven in 400 bits (50 bytes), als je de muren weglaat. Da's voor een hash nog wat aan de grote kant, maar zou best een mogelijke richting kunnen zijn.

Wellicht dat een (vorm van) Monte Carlo zoekboom interessant kan zijn? Je geeft je speelveld een score, hoe "opgelost" of hoe "slecht" men er voor staat (kun je heel ver in gaan). Dan kun je ook objectief beoordelen of een zet beter of slechter is tegenover de huidige staat. Je werkt een paar stappen willekeurig uit, eventueel daar de stappen weer van, om vervolgens te kunnen zien of je de goede richting op gaat. Dan zal daar allicht niet de beste oplossing terug komen, maar dan weet je wel in hoeveel stappen het in ieder geval kan. Paar keer laten oplossen dan een optie?

Dat is ook wel een leuke om wat verder te onderzoeken. Blokjes die verdwijnen zonder een enkel blokje over te houden is sowieso een verbetering richting de oplossing, maar blokjes die naar elkaar toe bewegen is dat niet persé altijd. Hier ga ik eens een nachtje over slapen.

[RobIII]

Emiel L schreef op maandag 15 mei 2023 @ 23:06:
Ik denk dat je dat dan wel als dezelfde actie moet beschouwen, het speelveld is immers niet veranderd ten opzichte van een paar zetten terug. Ik had al zitten denken of ik een hashfunctie zou kunnen verzinnen en de hashes van eerder gepasseerde posities zo snel kan vergelijken. Het zorgt er wel voor dat hele grote delen van de zoek-boom snel weggeknipt kunnen worden.

Bij het bepalen van de hash zouden alleen de kleuren (en posities natuurlijk) van de blokjes er toe doen, en daar zijn er 12 van. Dat past in 4 bits. Een puzzel is max 10x10 blokjes, dus een level is in theorie volledig te beschrijven in 400 bits (50 bytes), als je de muren weglaat. Da's voor een hash nog wat aan de grote kant, maar zou best een mogelijke richting kunnen zijn.

Ik zie niet hoe een hash hier iets toevoegt behalve complexiteit en het verspillen van CPU cycles?
Zoals ik dit lees ben je van plan álle permutaties van de 10x10 grid door te rekenen en, ja, dán ben je mogelijk wel even bezig. Maar ik neem aan dat 95% van die permutaties helemaal geen bereikbare state zijn als je het spel vanaf de eerste uitgangspositie gaat spelen? Waarom dan in hemelsnaam allemaal doorrekenen? Je wil vanuit een positie alle nieuwe posities berekenen en vanuit die posities weer de volgende posities. Alle posities die, zoals je zelf aangeeft, equivalent zijn (niet resulteren in nieuwe mogelijke zetten), kun je weg snijden.

In jouw screenshot heeft het onderste oranje blokje 1 naar links verplaatsen dezelfde ("functionele") uitkomst als 2 naar links en 3 naar links. Pas vanaf 4 naar links verandert er iets wezenlijks. Datzelfde voor het groene blokje: 1 naar boven en 3 naar boven is wezenlijk equivalent, alleen 2 naar boven levert iets anders op. En voor blauw geldt 'tzelfde maar dan omgekeerd naar beneden.

Dan krijg ik dus (toch wéér) vragen: Kúnnen blokjes überhaupt zo verplaatst worden als ik beschrijf, of schuiven ze altijd "de hele weg" (dus is "pijltje links" vanuit je screenshot het oranje blokje meteen volledig naar links zoals bijvoorbeeld in 2048 zonder 'tussenstops)? Dat zie ik niet aan die screenshot

[ Voor 20% gewijzigd door RobIII op 16-05-2023 02:24 ]

[Emiel L]

RobIII schreef op dinsdag 16 mei 2023 @ 01:44:
[...]

Ik zie niet hoe een hash hier iets toevoegt behalve complexiteit en het verspillen van CPU cycles?

Hoe zou jij het aanpakken om eindeloze cycli te voorkomen? Mijn eerste gedachte was een hash, zodat ze herkend kunnen worden, maar er zijn waarschijnlijk ook nog wel andere manieren.

Zoals ik dit lees ben je van plan álle permutaties van de 10x10 grid door te rekenen en, ja, dán ben je mogelijk wel even bezig. Maar ik neem aan dat 95% van die permutaties helemaal geen bereikbare state zijn als je het spel vanaf de eerste uitgangspositie gaat spelen? Waarom dan in hemelsnaam allemaal doorrekenen? Je wil vanuit een positie alle nieuwe posities berekenen en vanuit die posities weer de volgende posities. Alle posities die, zoals je zelf aangeeft, equivalent zijn (niet resulteren in nieuwe mogelijke zetten), kun je weg snijden.

Ik wil alle zetten doorrekenen die een speler zou kunnen maken. En als ik daar zetten kan knippen die aantoonbaar zinloos zijn, dan is dat pure winst.

Dan krijg ik dus (toch wéér) vragen: Kúnnen blokjes überhaupt zo verplaatst worden als ik beschrijf, of schuiven ze altijd "de hele weg" (dus is "pijltje links" vanuit je screenshot het oranje blokje meteen volledig naar links zoals bijvoorbeeld in 2048 zonder 'tussenstops)? Dat zie ik niet aan die screenshot

Dat spreekt inderdaad niet uit de screenshot, en ook niet uit de tekst. Het 1 positie verplaatsen van een blokje in horizontale of verticale telt als een zet. Een blokje dus 3 posities naar links schuiven is 3 zetten. Op de telefoon pak je een blokje op met je vinger, verschuif je het, en laat je het vervolgens weer los op de positie die je hebben wilt. Als je in de tussentijd een geldige combinatie maakt (lees: een blokje raakt met dezelfde kleur) verdwijnen alle blokjes die bij die combinatie horen.

[naitsoezn]

Een eerste poging hoe ik het zou aanpakken zou er ongeveer zo uitzien (ik begrijp nog steeds niet alle regels van het spel, dus je zult zelf de details moeten invullen):
Stap 1: Bepaal van een specifieke configuratie alle mogelijke zetten.
Stap 2: Reken door welke van die mogelijke zetten de 'optimale' zet is (waarschijnlijk wordt dit suboptimaal omdat je misschien niet letterlijk alle mogelijkheden zult kunnen doorrekenen). Hiervoor zul je dus een inschatting moeten kunnen maken van welke volgende configuratie waarschijnlijk dichterbij de gewenste uitkomst zit. Hiervoor zul je wat heuristieken moeten opstellen, en je loopt dan het risico dat je niet de ultieme volgende zet kiest, als je er maar voor zorgt dat de volgende zet niet eindigt in een deadlock (die situatie zul je dus ook moeten herkennen en zien aankomen).
Stap 3: Doe een zet en ga terug naar stap 1, totdat je in een deadlock zit of totdat je de oplossing hebt gevonden.

De crux zit hem dan in Stap 2. In Stap 2 zul je uiteindelijk Stap 1-3 waarschijnlijk meerdere keren simuleren om zo tot een inschatting te komen van welke zet de (sub)optimale is. Je kunt dan denken aan bijvoorbeeld 3 of 5 zetten vooruit alles te simuleren, of met Monte Carlo bijvoorbeeld 10 of 20 zetten vooruit. Maar in alle gevallen kom ik erop uit dat je een heuristiek nodig hebt om te bepalen wat de betere keus is qua 'volgende zet'. Die heuristiek zou bijvoorbeeld een inschatting kunnen zijn van hoeveel zetten er nog nodig zijn om de puzzel op te lossen, maar vooral bij de complexere puzzels zal dat een schatting zijn. Een andere aanname zou kunnen zijn: Minder blokjes is beter. Of minder verschillende kleuren is beter.

[ Voor 3% gewijzigd door naitsoezn op 16-05-2023 08:56 ]

[Janoz]

Ik zou een breadth first search doen. De stack waar je mee bezig bent sorteren op hoe dicht je bij de oplossing zit (hoeveel gekleurde blokjes er nog over zijn) en zo snel mogelijk states afwijzen die niet meer kunnen. Dat KAN behoorlijk uit de klauwen groeien, maar wees eens eerlijk. Zo'n puzzeltje zou toch binnen zeg 20 zetten op te lossen moeten zijn om het leuk te houden? Alles daarboven zou ik sowieso afkappen op 'niet leuk meer' waardoor je uiteindelijk ook de complexiteit beperkt.

[ThomasG]

Je heb waarschijnlijk een variatie op breadth-first search (BFS) of misschien wel A* nodig.

[Oon]

Ik heb je spel even gedownload en geprobeerd, en ik kan me voorstellen dat het efficiënter gaat zijn om via Fiverr iemand in te huren dan om dit in code op te lossen, maar het blijft een interessante uitdaging.

Om te beginnen zou ik berekenen welke groepen mogelijk zijn, in sommige puzzels heb je verschillende groepen blokjes, en in sommige puzzels heb je bijv. 4 blokjes van een kleur. Of je ze nou allevier bij elkaar schuift of 2x2 doet maakt niet uit, maar als je 2 groepen van 2 blokjes hebt die van elkaar zijn afgeschermd dan gaat dat niet werken.

Dus je krijgt dan iets als;
- zoek eilandjes
- zoek per eilandje alle kleuren, groepeer deze
- bekijk welke combinaties mogelijk zijn binnen een kleurgroepje, even niet meegerekend welke andere kleuren aanwezig zijn

Daarna kun je met pathfinding gaan bekijken welke groepjes je al op kunt lossen (zonder bij die kleuren geen andere mogelijke groeperingen van 2 of meer over te houden).

Je kunt daarmee al heel erg beperken hoeveel stappen je hoeft te simuleren, want als je met één beweging geel weg kunt krijgen hoef je dus niet te simuleren of het sneller is om eerst groen op te lossen.


Maar zelfs als je dit oplost, vergeet niet dat aantal zetten niet persé een goede maatstaaf is voor moeilijkheid. Als je eenmaal doorhebt dat je twee blokjes niet naast elkaar kunt zetten dan krijg je meteen een situatie waar je blokjes om elkaar heen gaat schuiven zonder dat je daar echt over na hoeft te denken, en dan wordt het meer een 'lompe' schuifpuzzel dan echt denkwerk. De moeilijke oplossing heeft dan dus minder zetten dan de makkelijke.

[Emiel L]

Oon schreef op dinsdag 16 mei 2023 @ 09:10:
Ik heb je spel even gedownload en geprobeerd, en ik kan me voorstellen dat het efficiënter gaat zijn om via Fiverr iemand in te huren dan om dit in code op te lossen, maar het blijft een interessante uitdaging.

Ik ben even stil geweest; andere dingen kregen prioriteit. Het zoeken naar oplossingen voor een puzzel blijkt met een simpele brute force methode best te doen. Ik heb nu een simpele recursive solver gemaakt die gewoon systematisch alle blokjes gaat verplaatsen.
Echter... het vinden van de optimale oplossing duurt op deze manier veel te lang voor alles behalve de meest triviale puzzels. Het aantal iteraties loopt best op als het minimum aantal zetten om een level op te lossen groeit. Als ik uit ga van 20 zetten voor een level (en de meeste levels zijn nog iets meer dan dat)...

Ik hoop dat mijn berekening een beetje klopt, maar mijn proof of concept solver lijkt het er qua performance wel mee eens te zijn:
Er zijn 4 moves per blokje... een recursiediepte van 20 geeft dan 4^20 mogelijke zetten om door te rekenen. Dat zijn er 1099511627776 in totaal. Zonder verregaande optimalisatie en op een enkele core kosten 100000 iteraties ongeveer 0.33 seconden. Da's per level dus 41 dagen stampen om 'm door te rekenen, en dan mogen er nog niet meer dan 20 zetten nodig zijn.

Vermoeden bevestigd dus en het geeft ook wel aan dat in ieder geval de allerdomste mens nog oneindig veel slimmer is dan het willekeurig schuiven van blokjes wat de computer nu doet 😃.

Maar zelfs als je dit oplost, vergeet niet dat aantal zetten niet persé een goede maatstaaf is voor moeilijkheid. Als je eenmaal doorhebt dat je twee blokjes niet naast elkaar kunt zetten dan krijg je meteen een situatie waar je blokjes om elkaar heen gaat schuiven zonder dat je daar echt over na hoeft te denken, en dan wordt het meer een 'lompe' schuifpuzzel dan echt denkwerk. De moeilijke oplossing heeft dan dus minder zetten dan de makkelijke.

Dat klopt. Sommige levels zijn maar een paar zetten, maar heel lastig om te zien, terwijl anderen weer meer 'gewoon werk' zijn. De reden dat ik het wilde weten is omdat ik het leuk zou vinden om per level de speler een aantal sterren te kunnen geven. Een optimale oplossing is bijvoorbeeld 3 sterren, en heb je meer zetten nodig, dan neemt dat aantal af.

Ik denk dat ik het voorlopig hierbij laat. Misschien dat ik de solver wel laat lopen en per puzzel een een uur de tijd geef om een oplossing te vinden. Dan accepteer ik die waardes als 'optimaal', voor nu.

Voor de volledigheid, mijn lompe code:

code:

func solve(level: Level, depth: Int) -> Evaluation {
    for tile in level.tiles {
        for direction in directions {
            if let newLevel = level.moveTile(at: tile.key, inDirection: direction) {
                levelStack.append(newLevel)
                
                switch canWeContinue(level: newLevel) {
                case .improved:
                    bestSolution = levelStack
                    break
                case .undecided:
                    hashStack.insert(newLevel.simpleHash)
                    solve(level: newLevel, depth: depth + 1)
                    hashStack.remove(newLevel.simpleHash)
                default:
                    break
                }
                
                levelStack.removeLast()
            }
        }
    }
    
    return .solved
}

func canWeContinue(level: Level) -> Evaluation {
    if hashStack.count > 20 { return .deep }
    if hashStack.contains(level.simpleHash) { return .revisit }

    switch level.status {
    case .playing: return .undecided
    case .failed: return .failed
    case .completed:
        let oldMinDepth = minDepth
        
        if hashStack.count < oldMinDepth {
            minDepth = hashStack.count
            print("Found a better solution at depth \(hashStack.count), compared to \(oldMinDepth)")
            return .improved
        }
        
        return .solved
    }
}

[Oon]

Emiel L schreef op dinsdag 25 juli 2023 @ 10:02:
[...]
Ik denk dat ik het voorlopig hierbij laat. Misschien dat ik de solver wel laat lopen en per puzzel een een uur de tijd geef om een oplossing te vinden. Dan accepteer ik die waardes als 'optimaal', voor nu.

Is het niet een optie om de scores gewoon door de app op de achtergrond naar een endpoint ergens te sturen? Dan krijg je heel snel inzicht in hoeveel zetten mensen daadwerkelijk nodig hebben, en zou je zelfs automatisch kunnen scoren op basis van gemiddelden.
Je zit dan wel weer met dat je de score van de client niet kunt vertrouwen, maar als je geen leaderboards laat zien oid dan zullen er weinig mensen op zoek gaan naar een manier om het aantal gebruikte zetten te veranderen, en mensen die overal minder zetten hebben dan theoretisch mogelijk kun je er snel uitvissen.

Of dat efficiënter is dan iedere puzzel een maand laten kraken weet ik niet, maar je krijgt er wel meteen inzicht mee over hoe snel een mens het kan ipv puur theoretisch met willekeurige zetten