AI-løser finder den mest effektive vej i Sokoban direkte i browseren
En port af en C++-solver bruger makro-skub og bitmasker til at finde optimale løsninger direkte i browseren.
Læs i dit tempo
Kort
En ny AI-løser i JavaScript kan nu løse de første 14 Sokoban-puslespil på millisekunder. Det er betydeligt, da optimerede søgemetoder gør det muligt at finde den korteste vej meget hurtigt. Fordi bane 15 kræver for meget hukommelse til en browser, skal den løses offline.
Begynder
Har du nogensinde prøvet at løse et Sokoban-puslespil, hvor man skal skubbe kasser på plads? En ny kunstig intelligens (AI) kan nu løse de første 14 baner på blot millisekunder. Projektet er skrevet i programmeringssproget JavaScript, som bruges til hjemmesider, og er baseret på en tidligere løsning i det hurtigere sprog C++. AI'en bruger en metode kaldet A-stjerne (A*), som er en smart måde at finde den korteste vej til et mål. For at spare tid bruger den noget, der hedder »macro-push«. Det svarer til, at man ikke tæller hvert enkelt lille skridt, man går, men i stedet kun fokuserer på selve skubbet til kassen.
For at programmet kan køre lynhurtigt, fylder hver tilstand i spillet kun 8 bytes. Normalt ville informationen om kasserne fylde 1 KB, men her er de pakket ind i et 32-bit heltal. Man kan forestille sig det som en ekstremt kompakt kode, en såkaldt bitmaske, der fylder meget lidt. Sammen med en effektiv organisering af data – en såkaldt »bucket queue« og en »flat typed-array hash« – slipper computeren for at bruge tid på at lede efter ny ledig plads i hukommelsen undervejs.
AI'en er også god til at spotte fælder. Den bruger en fast tabel over »døde felter« og tjekker for positioner, hvor kasserne sidder fast. Det betyder, at den hurtigt kan sortere uløselige veje fra, så A-stjerne-metoden forbliver optimal. Men nogle baner er bare meget sværere end andre. Bane 15 kræver for eksempel 1 gigabyte (GB) arbejdshukommelse (RAM) og 49 millioner forskellige tilstande. Fordi det er så tungt for computeren, er løsningen på 184 træk beregnet på forhånd uden for browseren.
Vil du have, at jeg forklarer mere om, hvordan bitmasker fungerer i praksis?
14 af de første baner løses på millisekunder med denne nye AI-løser. Projektet er en JavaScript-port af en tidligere C++-løsning, der finder den mest effektive vej gennem Sokoban-puslespil.
1 træk plus den korteste vej til kassen udgør omkostningen ved hver kant i denne 'macro-push A*'-søgning. Metoden gør det muligt at springe over enkelte gå-trin og kun fokusere på kasse-skub.
8 bytes er det samlede hukommelsesbehov for en tilstand. Kasserne pakkes ind i et 32-bit heltal, hvilket reducerer størrelsen fra 1 KB til en kompakt bitmaske.
Søgeprocessen er hurtig på grund af en bucket queue og en flat typed-array hash. Denne struktur gør løseren fri for hukommelsesallokeringer.
Søgefeltet beskrives via en statisk tabel over døde felter og et tjek for fastlåste positioner. Dette sorterer uløselige positioner fra og sikrer, at A*-algoritmen forbliver optimal.
1 GB RAM og 49 millioner tilstande kræves for at løse bane 15. Denne specifikke løsning på 184 træk er derfor beregnet offline i stedet for i browseren.
Kilder
- Sokoban AI Solver mkornreich.me
Produktionshistorie
- Radar Signal ? af 100 · spredning 1 kilder
- Vurdering Nyheds 5/5 — Konkret teknisk implementering af en AI-solver.
- Skrevet Model: mimo-v2.5-free · temperatur 0.4
- Overskrift 5 kandidater, valgt af chat.dk
- Korrektur 2 chatdk · 1 rettelser
- Vedtagelse Godkendt af Lars Louvre