[c++ backtrack] Opslaan en vergelijken toestanden systeem

[xos]

Hallo allemaal,

ik ben bezig met een programma waarmee sokoban puzzels opgelost kunnen worden. Dit wil ik gaan doen met een backtrack algoritme. Hopelijk kan ik het probleem duidelijk maken.

Nu heb ik een 2d veld array gemaakt waarin een speelbord uitgedrukt kan worden. Waarin veld een enum is welke de verschillende mogelijkheden van veldtypes kan uitdrukken, bv diamant of leeg.

Om het backtrack algoritme enigzins te optimaliseren wil ik graag testen of een bepaalde toestand van het veld al eerder is voorkomen. In dat geval kan worden gestopt met het uitwerken van de betreffende tak. Het probleem is dat ik niet weet hoe ik dit efficient kan controleren. Een controle is nodig aangezien er anders een oneindige loop wordt veroorzaakt. Immers je gaat verder met een toestand die al eerder is voorgekomen. Deze toestand zal later weer worden gegenereerd...

Ik kan natuurlijk in een vector compleet alle veldtoestanden (nodes) gaan bijhouden en telkens wanneer ik een nieuwe toestand genereer die lijst doorlopen en vergelijken. Dit lijkt mij bijzonder inefficient. Zeker wanneer de velden groot worden.

Is het mogelijk om een soort unieke code te genereren (hash) van elke compleet veld en deze op te slaan? Dan zou het mogelijk moeten zijn om hashes te vergelijken wat een heel stuk sneller kan gaan. In principe is de combinatie van alle velden uitgedrukt in 1 lange rij uniek voor een toestand. Ik zou iets kunnen maken waarmee een zo klein mogelijke _unieke_ hash van deze rij wordt gemaakt en hierop vergelijken. In java zit een hashset welke dit soort functionaliteit biedt.

Is er zoiets ook in c++ of heeft iemand een ander idee?

[ Voor 7% gewijzigd door xos op 05-03-2005 17:09 ]

[MrBucket]

Cool!

Ik ben zelf ook nog wel eens aan het brainstormen gegaan over hoe je zo'n sokoban probleem nu het beste op zou kunnen laten lossen. Maar wees erop voorbereid dat je search space heel snel heel groot gaat worden.

Een aantal ideeen:
• Genereer je hash uit de posities van de kisten en de positie van je mannetje (niet uit het hele veld).
• Omdat het erg waarschijnlijk is dat je collisions krijgt (twee verschillende spelsituaties die dezelfde hash opleveren), ontkom je er waarschijnlijk niet aan om, als de hashes van twee situaties overeenkomen, alsnog de complete spelsituaties met elkaar te vergelijken.
• Essentieel bij zo'n grote search space is om het zo snel mogelijk in te dammen. Controleren of een spelsituatie al eens eerder is uitgewerkt is een goed begin. Daarnaast zou ik ook prunen op spelsituaties die niet op te lossen zijn (kist in een hoek, vier kisten tegen elkaar, etc.).
• Overweeg anders om, bij dezelfde configuratie van kisten, maar bij een andere positie van het mannetje*, dit toch als dezelfde spelsituatie te beschouwen.

* Dit zou je eigenlijk alleen moeten doen wanneer het mannetje zich in dezelfde "connected component" bevindt.

[xos]

MrBucket schreef op zaterdag 05 maart 2005 @ 18:22:
Cool!

Een aantal ideeen:
• Genereer je hash uit de posities van de kisten en de positie van je mannetje (niet uit het hele veld).

Dat is idd een slim idee, dat zal al veel schelen.

• Essentieel bij zo'n grote search space is om het zo snel mogelijk in te dammen. Controleren of een spelsituatie al eens eerder is uitgewerkt is een goed begin. Daarnaast zou ik ook prunen op spelsituaties die niet op te lossen zijn (kist in een hoek, vier kisten tegen elkaar, etc.).

Ja dat had ik zelf ook bedacht. Dat zijn dingen die later wilde oplossen nadat ik een werkend systeem heb.

• Overweeg anders om, bij dezelfde configuratie van kisten, maar bij een andere positie van het mannetje*, dit toch als dezelfde spelsituatie te beschouwen.

* Dit zou je eigenlijk alleen moeten doen wanneer het mannetje zich in dezelfde "connected component" bevindt.

Ik snap je laatste * opmerking niet zo. Ik vermoed dat het iets te maken heeft met wanneer het mannetje 1 stap zet zonder een kist te verplaatsen, dit niet altijd als dezelfde speelsituatie gezien moet worden. Anders kan imho nooit alle oplossingen worden onderzocht.

[MrBucket]

basterd schreef op zaterdag 05 maart 2005 @ 18:38:
Ik snap je laatste * opmerking niet zo. Ik vermoed dat het iets te maken heeft met wanneer het mannetje 1 stap zet zonder een kist te verplaatsen, dit niet altijd als dezelfde speelsituatie gezien moet worden. Anders kan imho nooit alle oplossingen worden onderzocht.

Was ook erg onduidelijk omschreven, maar een mens moet ook een hapje eten he

De uitgebreide versie:
Het lijkt me niet verstandig om elke spelsituatie waar de kisten op dezelfde plek staan maar het mannetje op een andere plek te beschouwen als verschillende spelsituaties. Gevolg is dan namelijk dat je voor elk stapje dat je neemt een nieuwe spelsituatie in je search-space krijgt, waardoor het heel snel heel groot wordt.

Aan de andere kant kan je een spelsituatie niet alleen definieren aan de hand van de posities van de kisten, omdat je ook rekening moet houden met welke kistjes vanuit de huidige positie van je mannetje te bereiken (en dus te verschuiven) zijn.

Het beste zou dus een combinatie van beiden zijn: beschouw twee spelsituaties hetzelfde als
a) De posities van de kisten hetzelfde zijn
b) Het mannetje dezelfde kisten kan verschuiven (in dezelfde richtingen).

De laatste voorwaarde geldt als voor beide spelsituaties het mannetje zich in dezelfde connected component bevindt. Een connected component zou je in dit geval kunnen definieren als: als het mannetje van positie P naar positie Q kan komen zonder kisten te hoeven verschuiven, dan bevinden P en Q zich in dezelfde connected component.

Ik zal zo eens een afbeelding proberen te posten dat e.e.a. misschien verduidelijkt.

[MrBucket]

----

De afbeelding linksboven illustreert wat ik bedoel met het begrip "connected component". In bovenstaande spelsituatie staan 3 connected components aangegeven in resp. rood, groen en blauw. Stel dat je mannetje zich bijvoorbeeld ergens in het groene gebied bevindt, dan zijn alle andere vakjes in het groene gebied ook te bereiken zonder een kist te hoeven verschuiven.

Dus alle spelsituaties waarin de kisten bovenstaande positities hebben, en het mannetje zich ergens binnen de groene connected component bevindt, kunnen beschouwd worden als hetzelfde.

Echter, een spelsituatie met dezelfde positie voor de kisten maar waarin het mannetje zich in het blauwe gebied bevind moet wel beschouwd worden als een andere spelsituatie dan die waarin het mannetje zich in het groene gebied bevindt, omdat vanuit het blauwe gebied niet dezelfde kisten bereikt kunnen worden en/of de kisten in andere richtingen geschoven kunnen worden.

Ik zou daarom een spelsituatie definieren als:
- De positie van de kisten
- De connected component waarin het mannetje zich bevind.

Voor elk van deze spelsituaties kan je vervolgens bepalen welke kisten verschoven kunnen worden en in welke richting. De afbeelding rechtsboven geeft de 7 mogelijke verschuivingen aan voor de groene connected component. Elk van deze 7 verschuivingen geeft dus een nieuwe spelsituatie.

Natuurlijk is het zo dat door kisten te verschuiven de indeling van de connected components zal veranderen; er kunnen ook connected components splitsen of connected components samenvoegen.

[ Voor 28% gewijzigd door MrBucket op 05-03-2005 19:56 ]

[MrBucket]

Overigens, nog even over de complexiteit van je hash-functie: In het level wat ik zojuist gebruikte zijn er 39 vrije plaatsen, en 10 kisten. Het aantal spelsituaties (zonder mee te nemen in welke connected component je zit) is dan een combinatie van 10 uit 39, ofwel

n! / k! (n - k)!, met
k = 10 en n = 39.

Dit is 39! / (10! * 29!) = 635745396 mogelijke combinaties (van posities van kisten).

Als je nagaat dat een unsigned int 4294967296 mogelijke waarden heeft (ong. 7 keer zoveel), zou dit met een perfecte hashfunctie toereikend moeten zijn. Echter, naarmate het aantal kisten dichter bij [de helft van het aantal vrije plaatsen] komt, neemt het aantal mogelijke combinaties erg snel toe, en is een unsigned int niet meer voldoende om een collision-vrije hashwaarde in op te slaan.

Stel dat je niet 10 maar 13 kisten te verdelen hebt over 39 vrije plaatsen, dan zit je al aan 8122425444 mogelijke combinaties - 2 keer zoveel als wat een unsigned int aankan.

[MSalters]

Waarom de drukte over perfect hashen? Als gemiddeld 10 posities dezelfde hash opleveren dan heb je nog steeds geen enkel probleem; je bent dan nauwelijks duurder uit dan met een perfect hash. De logica om te bepalen welke posities van het mannetje equivalent zijn is heel veel duurder.

[MrBucket]

MSalters schreef op zondag 06 maart 2005 @ 15:03:
Waarom de drukte over perfect hashen? Als gemiddeld 10 posities dezelfde hash opleveren dan heb je nog steeds geen enkel probleem; je bent dan nauwelijks duurder uit dan met een perfect hash. De logica om te bepalen welke posities van het mannetje equivalent zijn is heel veel duurder.

Tuurlijk. Sterker nog, volgens mij kan je niet eens de volle 32-bits gebruiken voor een hash-code, want dan zit je hele geheugen vol met (alleen al de vector van) de hashmap.

Ik wilde ermee illustreren dat je er niet aan ontkomt om naast je hash-code ook nog een andere representatie van je spelsituatie op te slaan, omdat je onvermijdelijk collisions krijgt tussen je hash-waarden.

Trouwens, zijn er implementaties bekend van disk-backed hashmaps? De hashmap-varianten van de STL vereisen dat alle elementen zich in het werkgeheugen bevinden, en omdat het aantal elementen erg groot kan zijn, heb je kans dat windows zich een ongeluk gaat swappen (zeker omdat de geheugen-indeling van een hashmap geen rekening houdt met paginering van en naar disk).

Ik heb wel een link gevonden van een artikel dat een en ander omschrijft, maar ik geloof niet dat dit heel spetterend is.
Bovendien gelden veel van de beperkingen die in de eerste alinea genoemd worden niet voor dit probleem: zo hoeven er geen elementen uit de hashmap te worden verwijderd (het aantal onderzochte spelsituaties groeit alleen maar), en hoeven er ook geen variable-length elementen opgeslagen te worden.

[ Voor 11% gewijzigd door MrBucket op 06-03-2005 18:07 ]

[xos]

Sorrie voor de late reactie. Inmiddels wil het poppetje goed door het veld lopen en is het nu dus zaak om zo efficient mogelijk de verschillende oplossingen te vinden.

MrBucket: Het idee van "connected components" is wel een goed idee. Alleen ik ben nog maar een paar maanden bezig wat aan te prutsen in c++. Dit soort dingen maken het voor mij nog even iets te moeilijk. En dan heb ik het nog niet over algoritmes als disk-backed hashmaps Ik wil in eerste instantie even iets produceren wat werkt met simpele velden en wat eenvoudig te implementeren optimalisaties. Daarna komt de rest wel.

MSalters: daarin heb je geheel gelijk. Ik zal eens opzoek gaan naar een handige manier om een semi unique hash te genereren van een status van het speelveld.

Bedankt tot dusverre.

[ Voor 4% gewijzigd door xos op 06-03-2005 21:16 ]

[MrBucket]

basterd schreef op zondag 06 maart 2005 @ 21:15:
MrBucket: Het idee van "connected components" is wel een goed idee. Alleen ik ben nog maar een paar maanden bezig wat aan te prutsen in c++. Dit soort dingen maken het voor mij nog even iets te moeilijk. En dan heb ik het nog niet over algoritmes als disk-backed hashmaps Ik wil in eerste instantie even iets produceren wat werkt met simpele velden en wat eenvoudig te implementeren optimalisaties. Daarna komt de rest wel.

hehe
Prima hoor, het gegeven idee is ook niet echt makkelijk uit te programmeren voor iemand die net begint met C++. Maar ik vind het zelf ook een gaaf probleem waar ik al een tijdje over heb lopen brainstormen, vandaar de gecompliceerde aanpak...

Ik zal me een beetje inhouden qua ideeen spuien, maar als je vragen hebt...

[MSalters]

MrBucket schreef op zondag 06 maart 2005 @ 18:05:
[...]
Sterker nog, volgens mij kan je niet eens de volle 32-bits gebruiken voor een hash-code, want dan zit je hele geheugen vol met (alleen al de vector van) de hashmap.

Nee, alle hashmaps gebruiken een conversie van de hashkey naar een kleinere range, gebaseerd op het daadwerkelijk aantal gebruikte elementen. Daarbij worden in principe alle bits gebruikt.

[Soultaker]

MrBucket schreef op zondag 06 maart 2005 @ 18:05:
Trouwens, zijn er implementaties bekend van disk-backed hashmaps? De hashmap-varianten van de STL vereisen dat alle elementen zich in het werkgeheugen bevinden, en omdat het aantal elementen erg groot kan zijn, heb je kans dat windows zich een ongeluk gaat swappen (zeker omdat de geheugen-indeling van een hashmap geen rekening houdt met paginering van en naar disk).

Geen STL klassen, maar je kunt natuurlijk wel eens simpele database als BerkeleyDB gebruiken, al is die in de eerste plaats geoptimaliseerd voor toegangssnelheid en niet voor ruimtegebruik. Geen idee wat voor fill factor je krijgt, maar dat is in theorie wel te tweaken.

Kun je ook gelijk je state queue in een disk-backed queue stoppen en dan is het probleem van beperkte geheugenruimte in principe opgelost.

Qua optimaliseren van het zoeken moet je (zoals MrBucket al zei) zoveel mogelijk afkappen; dat scheelt vaak al enorm. Verder lijkt het me zinnig om een heuristisch algoritme te gebruiken (A* ofzoiets), dat scheelt vaak ook een flink deel van de search space, als je tenminste een goede heuristiek kan verzinnen; iets wat voor de hand ligt is de minimale manhattan distance van alle dozen naar alle doelen, bijvoorbeeld, maar het bepalen van die afstand is helaas wel NP-compleet (maar voor een beperkt aantal dozen goed te doen).

[ Voor 32% gewijzigd door Soultaker op 06-03-2005 23:14 ]

[MrBucket]

MSalters schreef op zondag 06 maart 2005 @ 23:01:
[...]

Nee, alle hashmaps gebruiken een conversie van de hashkey naar een kleinere range, gebaseerd op het daadwerkelijk aantal gebruikte elementen. Daarbij worden in principe alle bits gebruikt.

Waardoor ze dus in dezelfde bucket terechtkomen en een collision veroorzaken

[MrBucket]

Soultaker schreef op zondag 06 maart 2005 @ 23:10:
[...]

Geen STL klassen, maar je kunt natuurlijk wel eens simpele database als BerkeleyDB gebruiken, al is die in de eerste plaats geoptimaliseerd voor toegangssnelheid en niet voor ruimtegebruik. Geen idee wat voor fill factor je krijgt, maar dat is in theorie wel te tweaken.

Kun je ook gelijk je state queue in een disk-backed queue stoppen en dan is het probleem van beperkte geheugenruimte in principe opgelost.

Ik denk dat de overhead die je jezelf daarmee op de hals haalt makkelijk kunt voorkomen door een simpele disk-based hashmap te gebruiken - die hoeft dan echt niet super-geoptimaliseerd te zijn om een betere performance te krijgen.

[Soultaker]

Het argument om juist wel zo'n kant en klaar pakket te gebruiken is dat de makers goed nagedacht hebben over zaken als disk caching, OS caching, enzovoorts. Overigens hoop ik dat je een beetje bekend bent met BerkeleyDB (of GDB of zulke libraries): het zijn absoluut geen RDMS'en ofzoiets; het enige wat BerkeleyDB kan is key, value pairs opslaan in een bepaalde datastructuur (B-tree, hash table, queue of genummerde records) en verder eigenlijk niets.

Als je kijkt wat de library helemaal doet, dan valt dat dus ontzettend mee. Het is best tricky om zelf betere performance te krijgen. Dan moet je dus allerlei dingen als page allocation schemes enzo opnieuw gaan zitten tweaken.

[ Voor 26% gewijzigd door Soultaker op 06-03-2005 23:20 ]

[MrBucket]

Soultaker schreef op zondag 06 maart 2005 @ 23:10:
Verder lijkt het me zinnig om een heuristisch algoritme te gebruiken (A* ofzoiets), dat scheelt vaak ook een flink deel van de search space, als je tenminste een goede heuristiek kan verzinnen; iets wat voor de hand ligt is de minimale manhattan distance van alle dozen naar alle doelen, bijvoorbeeld, maar het bepalen van die afstand is helaas wel NP-compleet (maar voor een beperkt aantal dozen goed te doen).

Nou ja, NP-compleet is geen probleem voor ong. 20 boxes... een simpel kwadratisch algoritme is voor n=20 al snel beter dan een enigszins gecompliceerd logaritmisch of O(n log n) algoritme

Het punt is idd om een goede heuristiek te vinden. En het verraderlijke aan dit probleem is dat je de boxen vaak eerst van de 'doel'-vakjes weg moet schuiven voordat je ze in de juiste configuratie kan krijgen om het level op te lossen. Het is erg lastig om, als mens zijnde, te beoordelen of een spelsituatie beter is dan de ander, laat staan dat er een goede maat voor te vinden is (die ook nog eens redelijk efficient te berekenen is.)

Bij een simpele breadth-first search ben je er iig van gegarandeerd dat de optimale oplossing (in termen van verschuivingen of aantal passen) geretourneerd wordt.

Maar ja, wat is wijsheid...

[MrBucket]

Soultaker schreef op zondag 06 maart 2005 @ 23:19:
Het argument om juist wel zo'n kant en klaar pakket te gebruiken is dat de makers goed nagedacht hebben over zaken als disk caching, OS caching, enzovoorts. Overigens hoop ik dat je een beetje bekend bent met BerkeleyDB (of GDB of zulke libraries): het zijn absoluut geen RDMS'en ofzoiets; het enige wat BerkeleyDB kan is key, value pairs opslaan in een bepaalde datastructuur (B-tree, hash table, queue of genummerde records) en verder eigenlijk niets.

Dat wist ik idd niet nee, het enige waar ik BerkeleyDB's van kende is in de RDBMS-sfeer. En key, value-pairs zijn idd precies hetgene wat nodig is voor zo'n probleem.

Hmm, dat is idd wel een poging waard, thanks