Efficient zoeken in collectie van subsets?

[MrBucket]

Ik ben bezig met een oplosser te schrijven voor het spelletje Sokoban (http://en.wikipedia.org/wiki/Boxxle). Kort gezegd komt het erop neer dat je met een mannetje dozen door een doolhof moet schuiven totdat ze allemaal op een geldige lokatie staan. Alleen de dozen kunnen bewogen worden, en alle dozen zijn gelijk.

Een van de dingen die ik daarbij nodig heb is een datastructuur die subsets van doos-configuraties kan opslaan, en waarin ik vervolgens met een complete doos-configuratie als query efficient kan zoeken naar alle subsets die hieraan voldoen.

Minder abstract: stel dat een bepaald level 10 dozen bevat. Van dit level heb ik bepaald dat, als een subset van 4 dozen in een bepaalde configuratie CS staan (bijv. op de lokaties P0, P1, P2 en P3), dat het level dan al niet meer op te lossen valt. Nu zullen er meerdere van deze subset-configuraties CS0...CSn van dozen zijn waarvoor dit geldt (maar niet noodzakelijk met 4 dozen).

Nu wil ik deze subset-configuraties CS0...CSn op een intelligente manier opslaan in een datastructuur zodat ik, gegeven een complete configuratie C (in dit geval van 10 dozen), efficient alle* subset-configuraties CS kan vinden waarvan alle dozen in CS op dezelfde lokaties staan als in C. Nu heb ik mijn hoofd lopen breken over de opzet van zo'n datastructuur, maar ik kom er maar niet uit. Ik denk dat ik een variant van een hashmap of balanced binary tree wil gebruiken, maar de precieze details ontbreken nog.
(* - in principe zou het voldoende zijn om te bepalen of er minimaal 1 zo'n CS bestaat die op C van toepassing is).

Het probleem is dat als er in C een doos op lokatie P staat, dat CS niet per se ook een doos op lokatie P hoeft te hebben om een match op te kunnen leveren. De enige manier waarop een CS geen match oplevert, is wanneer het een doos op lokatie P heeft staan, en op diezelfde lokatie P in C geen doos staat.

Ik zat eraan te denken om alle posities in een level opeenvolgend te nummeren (een 'index' te geven), en elke CS op te slaan als de geordende reeks indexen van de dozen in CS. Binnen de datastructuur worden de CSen dan lexicografisch gesorteerd op hun indexen opgeslagen.
Het doorzoeken van de datastructuur met een query-configuratie C zou dan als volgt gaan. Neem de indexen I[0]...I[n] van alle dozen in C (I is oplopend gesorteerd)
Van x = 0 tot x = n
..ga op zoek naar alle matchende CSsen M = {CS0...CSn} die I[x] als hun eerste index hebben.
..Voor elke CS uit M:
....bepaal of de indexen van de dozen uit CS ook voorkomen in I[x]...I[n]. Zo ja, dan heb je een match.

Nu lijkt me dit wel een mogelijkheid, maar ik betwijfel of het erg efficient is. Heeft iemand misschien een beter idee?

[KopjeThee]

Misschien een domme vraag, maar hoe bepaal je dat een bepaalde subset dozen in een bepaald veld NOOIT tot een oplossing kan leiden? Heb je daar bepaalde regels voor oid?

Voor een dergelijk spel zou ik tijdens het zoekproces bijhouden welke spelsituatie "vastloopt" en een hashkey berekenen en 'm opslaan in een hashtabel. Als je weer terugkomt (langs een andere weg, door dozen in een iets andere volgorde te schuiven) op dezelfde situatie, dan zie je dat je een "hit" hebt in je hash tabel en hoef je dat pad niet verder af te zoeken.

[MrBucket]

kopjethee schreef op donderdag 20 juli 2006 @ 19:50:
Misschien een domme vraag, maar hoe bepaal je dat een bepaalde subset dozen in een bepaald veld NOOIT tot een oplossing kan leiden? Heb je daar bepaalde regels voor oid?

Zeker geen domme vraag
De meeste simpele situaties waardoor een level niet meer opgelost kan worden kan ik al herkennen, en dan merk je dat het programma nog steeds teveel tijd verdoet aan complexere situaties waarvan je als mens vaak al kan zien dat het nooit meer opgelost kan worden. Bijvoorbeeld:

code:

XXXXX
X   X
X ##X
X# oX  (X = muur, # = doos, o = mannetje)

Dit fragment kan nooit meer opgelost worden omdat je niet 'achter' de dozen kan komen. Stel dat er nu nog 6 dozen in de rest van dit level staan, dan wil je voorkomen dat hij alle mogelijkheden met die 6 andere dozen gaat doorrekenen, want dat is alleen maar verloren tijd.

Veel van dit soort complexere situaties hebben trouwens te maken met zgn. "connected spaces": als je vanuit de ene space niet naar de andere space kan komen (omdat het verschuiven van de dozen die de grens tussen die spaces bepalen niet mogelijk is zonder het level te verknallen), dan weet je al dat de rest van de dozen er niet meer toe doet.

Voor een dergelijk spel zou ik tijdens het zoekproces bijhouden welke spelsituatie "vastloopt" en een hashkey berekenen en 'm opslaan in een hashtabel. Als je weer terugkomt (langs een andere weg, door dozen in een iets andere volgorde te schuiven) op dezelfde situatie, dan zie je dat je een "hit" hebt in je hash tabel en hoef je dat pad niet verder af te zoeken.

Yep, en dat doe ik ook al. Maar het punt is dus dat hij dan alleen die exacte situatie niet nog een keer doorrekent, terwijl je eigenlijk wilt voorkomen dat 'ie geen enkele situatie nog doorrekent waar de 3 dozen op die manier in het level staan.

[DroogKloot]

Een solver voor een NP-hard probleem? Dan kan je datastructuur maar beter heel efficient zijn ja.

(Niet ontmoedigend bedoeld verder, maar aan een solver die voor niet-triviale levels een miljoen jaar nodig heeft heb je zelf ook niet bijster veel natuurlijk. )

[ Voor 54% gewijzigd door DroogKloot op 20-07-2006 21:01 ]

[MrBucket]

DroogKloot schreef op donderdag 20 juli 2006 @ 20:56:
Een solver voor een NP-hard probleem? Dan kan je datastructuur maar beter heel efficient zijn ja.

(Niet ontmoedigend bedoeld verder, maar aan een solver die voor niet-triviale levels een miljoen jaar nodig heeft heb je zelf ook niet bijster veel natuurlijk. )

Ook al is het probleem NP-hard, dat wil nog niet zeggen dat er geen mogelijkheid is om praktische instanties ervan op te lossen

Het grootste probleem, voor zover ik het nu kan overzien, is de branching factor: Tijdens een state space search genereert elke state zoveel vervolgstates, dat je binnen een mum van tijd al een miljoen states hebt onderzocht, waarvan verreweg de meesten nooit tot een oplossing kunnen leiden.
Mijn insteek is nu: probeer zoveel mogelijk states direct te schrappen (ook al duurt het analyseren van zo'n state dan wat langer), zodat ze niet de kans krijgen te vertakken in een hele tree van nutteloze states.

[KopjeThee]

Als je niet meer dan 64 posities hebt in je veld is er misschien iets efficients mogelijk met bitwise vergelijkingen. Elk bit in een 64-bit data type stelt een positie in je veld voor. Een 1 is bijv een blokje en een 0 een lege positie. Zo kan je de huidige situatie representeren (C). En ook kan je de subsets (S) zo representeren. Dan heb je: if (C & S == S) then {C voldoet aan S} else {C voldoet niet aan S}

[Dido]

Terwijl ik even zat te denken was kopjethee me voor.
Je hoeft je niet per se tot 64 posities te beperken, maar als je alle posities in je level waar een doos kan staan als bits achter elkaar zet zijn je subsets eenvoudig te herkennen, lijkt me.

Het maximum aantal situaties in een level is dan meteen ook gedefinieerd als kleiner 2 ^ dan aantal velden waar een doos kan staan * (het aantal velden - het aantal dozen). Dat is nog steeds erg veel, maar er zijn heel snel heel veel beperkingen aan te brengen (je maximum aantal 1-tjes is de eerste).

Sterker nog, als je 100 mogelijke posities hebt (geen muren), en tien dozen, dan kunnen die tien dozen op 100!/90! manieren geplaatst worden (100*99*98*97*96*95*94*93*92*91), en je poppetje kan op 90 plaatsen staan. 100!/89! mogelijkheden. Dat zijn er maar 5.65*10^21

Een enkele situatie met 4 dozen die een oplossing blokkeren betekent dat je 96!/89! mogelijkheden kwijtraakt.

Dat moet je dan nog wel 94 miljoen keer doen

[ Voor 61% gewijzigd door Dido op 20-07-2006 21:36 ]

[MrBucket]

kopjethee schreef op donderdag 20 juli 2006 @ 21:17:
Als je niet meer dan 64 posities hebt in je veld is er misschien iets efficients mogelijk met bitwise vergelijkingen. Elk bit in een 64-bit data type stelt een positie in je veld voor. Een 1 is bijv een blokje en een 0 een lege positie. Zo kan je de huidige situatie representeren (C). En ook kan je de subsets (S) zo representeren. Dan heb je: if (C & S == S) then {C voldoet aan S} else {C voldoet niet aan S}

Hmm... eenvoud siert de kunst. Ik moet eerlijk bekennen dat ik hier nog niet eens aan heb gedacht 't Is welliswaar een lineair algoritme, maar wel 1 die qua implementatie razendsnel kan zijn. Deze ga ik zeker onthouden.

Maar ik was eigenlijk in eerste instantie op zoek naar een sub-lineair algoritme (logaritmisch, bij voorkeur). Zou dit eigenlijk uberhaupt wel mogelijk zijn?

[MrBucket]

Dido schreef op donderdag 20 juli 2006 @ 21:25:
Het maximum aantal situaties in een level is dan meteen ook gedefinieerd als kleiner 2 ^ dan aantal velden waar een doos kan staan * (het aantal velden - het aantal dozen). Dat is nog steeds erg veel, maar er zijn heel snel heel veel beperkingen aan te brengen (je maximum aantal 1-tjes is de eerste).

Sterker nog, als je 100 mogelijke posities hebt (geen muren), en tien dozen, dan kunnen die tien dozen op 100!/90! manieren geplaatst worden (100*99*98*97*96*95*94*93*92*91), en je poppetje kan op 90 plaatsen staan. 100!/89! mogelijkheden. Dat zijn er maar 5.65*10^21

Een enkele situatie met 4 dozen die een oplossing blokkeren betekent dat je 96!/89! mogelijkheden kwijtraakt.

Dat moet je dan nog wel 94 miljoen keer doen

Ik hoor het al, je probeert me op te beuren he?

Ik zal je analyse een beetje nuanceren. De vakjes naast de meeste muren aan de buitenkant van het level kun je al schrappen, omdat als je daar een doos neerzet, je 'm dan nooit meer van die muur weg krijgt. Deze vakjes hoef je dan ook niet mee te tellen voor de opslagruimte. Extra pluspunt: deze analyse kun je per level doen, voordat je de state space search uitvoert.

Dan: ik sla van het poppetje geen positie op, alleen de connected space waarin hij zich bevindt. Alle dozen die aan die connected space grenzen kunnen vanaf elk vakje binnen die connected space bereikt en dus geduwd worden. Ik hoef dus geen states te genereren waarbij alleen het mannetje verplaatst wordt, ik kan nu "reuze-stappen" nemen door een doos te verschuiven per nieuwe state.

[Dido]

MrBucket schreef op donderdag 20 juli 2006 @ 21:51:
Ik hoor het al, je probeert me op te beuren he?

Ik mag graag mensen aanmoedigen

Ik zal je analyse een beetje nuanceren. De vakjes naast de meeste muren aan de buitenkant van het level kun je al schrappen, omdat als je daar een doos neerzet, je 'm dan nooit meer van die muur weg krijgt. Deze vakjes hoef je dan ook niet mee te tellen voor de opslagruimte. Extra pluspunt: deze analyse kun je per level doen, voordat je de state space search uitvoert.

Ik zou oppassen met die buitenmuren: het kon wel eens de enige plek zijn om een doos uit de weg te krijgen en het level op te lossen. Het zou lullig zijn als je die mogelijkheid mist omdat die doos "toch tegen een muur staat waar je hem niet meer vandaan krijgt"

Dan: ik sla van het poppetje geen positie op, alleen de connected space waarin hij zich bevindt. Alle dozen die aan die connected space grenzen kunnen vanaf elk vakje binnen die connected space bereikt en dus geduwd worden. Ik hoef dus geen states te genereren waarbij alleen het mannetje verplaatst wordt, ik kan nu "reuze-stappen" nemen door een doos te verschuiven per nieuwe state.

Dan kun je je mogelijkheden bijna door 10 delen, dat schiet ook alweer op

Leuk probleem trouwens, dit soort dingen zijn absoluut mijn sterke kant niet, maar ik mag er graag over nadenken. Ik vond het wel grappig dat ik niet de enige was met het idee om in plaats van de posities de "box-state" van een veld op te slaan

[MrBucket]

Dido schreef op donderdag 20 juli 2006 @ 22:05:
Ik zou oppassen met die buitenmuren: het kon wel eens de enige plek zijn om een doos uit de weg te krijgen en het level op te lossen. Het zou lullig zijn als je die mogelijkheid mist omdat die doos "toch tegen een muur staat waar je hem niet meer vandaan krijgt"

Natuurlijk moet je die analyse wel zorgvuldig uitvoeren voordat je zo'n vakje schrapt. Maar die analyse is eigenlijk belachelijk simpel, en je hoeft het niet eens efficient te doen omdat het toch maar een voorbereidingsstap is.

Dan kun je je mogelijkheden bijna door 10 delen, dat schiet ook alweer op

In het begin van een level ja. Maar naarmate je dichter bij de oplossing komt worden de connected spaces groter en wordt de invloed van werken met connected spaces ook steeds groter.

Leuk probleem trouwens, dit soort dingen zijn absoluut mijn sterke kant niet, maar ik mag er graag over nadenken. Ik vond het wel grappig dat ik niet de enige was met het idee om in plaats van de posities de "box-state" van een veld op te slaan

Ja, 't is ook echt een leuk probleem om over te brainstormen en uit te vinden van "hoe ga ik dit nu in hemelsnaam weer aanpakken".

Wat dat betreft: Sudoku is voor mietjes

[Soultaker]

Wat betreft de algemene oplossingsmethode: ik heb wel enig succes geboekt met het oplossen van Sokoban puzzels met een A* algoritme. Daarvoor zijn twee dingen heel belangrijk: ten eerste het rigoreus afkappen van onoplosbare situaties; met een beetje moeite is dat heel goed te doen voor de meest voorkomende situaties (zonder dat je fouten introduceert zoals waarvoor Dido waarschuwt). Ten twee (en dat is altijd met A*) help een goede heuristiek (een schatting van hoeveel stappen je van de oplossing verwijderd bent).

Het helpt ook om niet een minimale oplossing in stappen, maar in aantal keren duwen te zoeken. Je kunt dan posities waarin het mannetje op verschillende plekken staat (maar waar hij zonder te duwen van de ene naar de andere plek kan lopen) als gelijk beschouwen en dat scheelt flink in het aantal toestanden.

Mijn ervaring met state search is dan ook dat meestal het geheugen de bottleneck is, en niet de rekentijd. Ik vraag me dan ook af of de techniek die jij wil toepassen efficient is: er zijn echt een heleboel dode situaties te bedenken, en als je die allemaal apart op wil slaan ben je snel door je geheugen heen. Mijn intuïtie zegt me dat je ze beter ter plekke kunt herkennen (al zul je dan niet álle dodo situaties makkelijk kunnen herkennen, de simpelste gevallen komen verreweg het vaakste voor). Maar je moet het misschien zelf uitproberen.

[MrBucket]

Soultaker schreef op donderdag 20 juli 2006 @ 22:18:
Wat betreft de algemene oplossingsmethode: ik heb wel enig succes geboekt met het oplossen van Sokoban puzzels met een A* algoritme. Daarvoor zijn twee dingen heel belangrijk: ten eerste het rigoreus afkappen van onoplosbare situaties; met een beetje moeite is dat heel goed te doen voor de meest voorkomende situaties (zonder dat je fouten introduceert zoals waarvoor Dido waarschuwt). Ten twee (en dat is altijd met A*) help een goede heuristiek (een schatting van hoeveel stappen je van de oplossing verwijderd bent).

Hmm, ja en nee. Ik heb bij Sokoban de indruk dat je met A* wel een 'redelijke' indruk kan krijgen van hoever je ongeveer gevorderd bent richting de oplossing, maar dat de weg naar de oplossing vaak juist via omwegen loopt - vandaar dat het ook zo'n lastig spelletje is. Maar dit zeg ik op basis van m'n gevoel en ervaring met zelf het spel spelen - geen idee of het ook daadwerkelijk zo werkt.

Het helpt ook om niet een minimale oplossing in stappen, maar in aantal keren duwen te zoeken. Je kunt dan posities waarin het mannetje op verschillende plekken staat (maar waar hij zonder te duwen van de ene naar de andere plek kan lopen) als gelijk beschouwen en dat scheelt flink in het aantal toestanden.

Het cursieve gedeelte omschrijft precies een connected space. Leuk om te zien dat er meerdere mensen met dit idee komen

Mijn ervaring met state search is dan ook dat meestal het geheugen de bottleneck is, en niet de rekentijd. Ik vraag me dan ook af of de techniek die jij wil toepassen efficient is: er zijn echt een heleboel dode situaties te bedenken, en als je die allemaal apart op wil slaan ben je snel door je geheugen heen. Mijn intuïtie zegt me dat je ze beter ter plekke kunt herkennen (al zul je dan niet álle dodo situaties makkelijk kunnen herkennen, de simpelste gevallen komen verreweg het vaakste voor). Maar je moet het misschien zelf uitproberen.

Die instelling heb ik dus ook, en de simpele gevallen moet je niet opslaan maar gewoon on-the-fly bepalen, maar aan de andere kant: om de meer complexe situaties te kunnen herkennen waarbij het level niet meer opgelost kan worden, zul je toch lokaal een state space search moeten uitvoeren (bijvoorbeeld, alleen met de dozen die grenzen aan een connected space die ogenschijnlijk niet meer door het mannetje bereikt kan worden zonder het level te verknallen). En omdat dit toch ook wel redelijk rekenintensief kan worden leek het me handig om, als dit eenmaal voor een subset van dozen is bepaald, om dat dan op te slaan voor toekomstig gebruik.

[Soultaker]

Om trouwens op je vraag terug te komen: het is dus de bedoeling dat je je datastructuur tijdens het uitvoeren bijwerkt? Dat maakt de boel nog wel iets lastiger.

Twee technieken die ik me kan indenken (geen van beide gegarandeerd logaritmisch van complexiteit) gaan uit van de formulering als bitfields:
• een binaire zoekboom waarin de leaf nodes waarden zijn, en elke non-leaf node de vereniging van zijn twee children bevat. Dit is efficiënter te doorzoeken dan een grote lijst, mits je de leaf nodes in de goede volgorde hebt staan (zoniet, dan reduceert het naar lineair zoeken, met extra overheid).
• een trie (of beter nog: een PATRICIA trie), waarbij je bij het doorzoeken ofwel één richting inslaat (als de corresponderende bit in je invoer 0 is) of twéé richtingen (als de corresponderende bit 1 is). De complexiteit hiervan is worst case O(2^N + X) met X het aantal oplossingen en N het aantal 1-bits -- vooral efficiënt dus als je level niet al te veel dozen (zeg, zeker <20, liever <10) bevat.

offtopic:
Gefeliciteerd met je mijlpaal van 300 posts!

[ Voor 4% gewijzigd door Soultaker op 20-07-2006 22:57 ]

[KopjeThee]

Structuren van Soultaker klinken erg bruikbaar, zou ik zeker proberen!

Misschien kan je ook denken aan heuristieken die bepalen in welke volgorde je mogelijke nieuwe "zetten" gaat uitvoeren. Misschien kan je vuistregels bedenken die bepalen of een bepaalde zet "kansrijker" is dan een ander. Dit garandeert natuurlijk niets, maar zou in de praktijk wel een sneller tot oplossingen kunnen leiden. In schaakprogramma's en dergelijke gebeurt dat volgens mij ook.

[Soultaker]

kopjethee schreef op vrijdag 21 juli 2006 @ 08:41:
Misschien kan je ook denken aan heuristieken die bepalen in welke volgorde je mogelijke nieuwe "zetten" gaat uitvoeren. Misschien kan je vuistregels bedenken die bepalen of een bepaalde zet "kansrijker" is dan een ander. Dit garandeert natuurlijk niets, maar zou in de praktijk wel een sneller tot oplossingen kunnen leiden. In schaakprogramma's en dergelijke gebeurt dat volgens mij ook.

Het hangt ervan hoe het zoekalgoritme opgezet is. Met een breadth-first-search helpt het je niets. Bij A* doe je het impliciet al -- wat is de 'beste zet' anders dan de zet die tot de beste situatie leidt? (In dit probleem is de beste situatie die, waarin het aantal zetten dat nodig is om een eindoplossing te bereiken, minimaal is.)

Dat het in schaakprogramma's werkt, is trouwens om een andere reden. Door zo vroeg mogelijk een zo nauwkeurig mogelijke schatting van de werkelijke waarde van een stelling te krijgen, kunnen andere delen van de zoekboom afgekapt worden, maar dit afkappen werkt alleen omdat je er van uit gaat dat je tegenstander je optimaal tegenwerkt. Bij een zoekprobleem zoals dit is er geen tegenstander en valt er niets af te kappen.

[ Voor 3% gewijzigd door Soultaker op 21-07-2006 13:49 ]