[Optimalisatie] Langste Doolhof

[KopjeThee]

Ik heb dit spel een aantal keer gespeeld. Een belangrijk aspect is om de vijanden te dwingen een zo lang mogelijke route te lopen. Nu vraag ik me af of hier een leuk algoritme voor is te verzinnen, die het doolhof met de langste route bepaald.

Iets nauwkeuriger: de kortste route uit het doolhof moet zo lang mogelijk zijn, maar er moet wel een uitweg zijn. In feite zijn er geen beperkingen op het aantal blokjes dat je kunt neerzetten, anders dan de grootte van het speelveld. Ik weet niet precies hoe "bochten" moeten meetellen in de lengte van het pad, ik denk gewoon als 1.

Brute force lijkt mij onmogelijk. Ik weet niet precies hoeveel mogelijke velden er zijn, maar ik schat in de orde van 2^200. Backtrackend er doorheen gaan zal de mogelijkheden wel iets uitdunnen, maar lijkt mij nog steeds te veel.

Een voor de hand liggende optie bij elk optimalisatie probleem is een genetisch algoritme, maar helaas is dit niet gegarandeerd optimaal.

Is er hier iemand met inspiratie voor een leuk algoritme?

[H!GHGuY]

Wikipedia: Longest path problem

need I say more

[ Voor 5% gewijzigd door H!GHGuY op 29-12-2008 11:48 ]

[KopjeThee]

H!GHGuY schreef op maandag 29 december 2008 @ 11:47:
Wikipedia: Longest path problem

need I say more

Ja, OK het langste pad vinden in een graaf is NP compleet. Maar dat is niet echt het probleem. Het probleem is eigenlijk om een doolhof te maken waarin het kortste pad naar een uitgang zo lang mogelijk is, dus vooral gebruik maken van het kortste pad algoritme om te bepalen hoe goed het doolhof is.

[BCC]

Dit is ook prima te bruteforcen, maar een genetisch algoritme is hier natuurlijk heel gaaf. De hoeveelheid poppetjes die er doodgaan / overleven is een hele mooie feedback voor een GA.

Je weet trouwens ook nog helemaal niet of de 'langste route' de optimaalste strategie is. Misschien komt een GA wel met iets heel anders

[ Voor 27% gewijzigd door BCC op 29-12-2008 17:59 ]

[KopjeThee]

BCC schreef op maandag 29 december 2008 @ 17:57:
Dit is ook prima te bruteforcen, maar een genetisch algoritme is hier natuurlijk heel gaaf. De hoeveelheid poppetjes die er doodgaan / overleven is een hele mooie feedback voor een GA.

Je weet trouwens ook nog helemaal niet of de 'langste route' de optimaalste strategie is. Misschien komt een GA wel met iets heel anders

Brute force lijkt me in dit geval erg onpraktisch, gezien de grote hoeveelheid mogelijke speelvelden. Backtracken is ook lastig, aangezien ik geen goed criterium kan verzinnen om een tak voortijdig af te kappen (je laatste blokje kan misschien net je pad erg verlengen).

Hoeveel poppetjes overleven is ook van je torens afhankelijk (type, upgrade, positie). Vanuit 1 toren gezien is hij het meest effectief als het pad binnen zijn range zo lang mogelijk is. Maar mijn idee was: Hoe langer de monstertjes zich in je doolhof bevinden, hoe meer mogelijkheden je hebt om ze kapot te schieten. Nadat ik een lang pad heb gecreeerd, kan ik gaan kijken naar een gunstige positionering van torens. Maar je hebt gelijk het gehele probleem is uitgebreider, en mogelijk is de langste pad strategie niet optimaal.

[BCC]

Je genereert gewoon random een stuk 'DNA' met:
[{Torentje_type, upgrade, X, Y}, {Torentje_type, upgrade, X, Y}]

Met een willekeurige lengte die natuurlijk wel aan de maximale kosten eis voldoet.
Dan laat je ze het spelletje spelen. De algoritmes die hoog scoren kruis je vervolgens op een paar manieren (bij elkaar optellen, half half, random, etc..)

Voeg wat random mutaties toe (torentje weg, torentje extra, torentje op een andere plek) en gaan

Ohja, daarna moet er natuurlijk wel een YouTube filmpje van gemaakt worden .

[ Voor 11% gewijzigd door BCC op 29-12-2008 18:45 ]

[mocean]

Daar gaat mn avond.....

[KopjeThee]

BCC schreef op maandag 29 december 2008 @ 18:36:
Je genereert gewoon random een stuk 'DNA' met:
[{Torentje_type, upgrade, X, Y}, {Torentje_type, upgrade, X, Y}]

Met een willekeurige lengte die natuurlijk wel aan de maximale kosten eis voldoet.
Dan laat je ze het spelletje spelen. De algoritmes die hoog scoren kruis je vervolgens op een paar manieren (bij elkaar optellen, half half, random, etc..)

Voeg wat random mutaties toe (torentje weg, torentje extra, torentje op een andere plek) en gaan

Ohja, daarna moet er natuurlijk wel een YouTube filmpje van gemaakt worden .

OK, maar als het volledige spel moet worden gespeeld, dan zijn er nog wat zaken:
A) Het spel bestaat uit meerdere rondes. Elke ronde komt een ander type vijand (normaal, snel, vliegend, ...) Ik weet niet precies welke toren in welke toestand welk effect heeft. Dat maakt het naspelen lastig. Van de hogere levels weet ik ook niet welke vijanden komen (daar was ik al af).
B ) Elke ronde krijg je een bepaalde hoeveelheid geld om torens te kopen, afhankelijk van hoeveel vijanden je neerschiet. Met dat geld kan je torens kopen of upgraden. Je kunt ook geld krijgen door torens weer te verkopen. Dus het algoritme moet er ook rekening mee houden dat je niet in 1 keer je hele speelveld kunt neerzetten, en dat het soms verstandig kan zijn een bepaald type toren te verkopen en te vervangen door een andere type. Soms is het ok handig om een ronde te "sparen".

Ik weet niet welke "DNA" representatie hier handig is. De fitness kan ik niet bepalen, omdat ik (zie punt A) niet precies weet of ik de monsters dood krijg, gegeven een aantal torens op bepaalde posities (het spel zal iets beter ge-reverse engineered moeten worden).

Ik zou liever eenvoudig beginnen door te kijken hoe je een zo lang mogelijk pad kunt maken

[ Voor 3% gewijzigd door KopjeThee op 29-12-2008 20:31 ]

[Juup]

... en toen kwamen de flyers.
Die vliegen recht over je speelveld heen.

Maar wiskundig gezien is het wel een hele leuke vraag.

[KopjeThee]

Juup schreef op dinsdag 30 december 2008 @ 04:21:
... en toen kwamen de flyers.
Die vliegen recht over je speelveld heen.

Maar wiskundig gezien is het wel een hele leuke vraag.

Ja, de flyers los je niet op met en lang doolhof. Maar met een lang doolhof kan je geld uitsparen op torens om landmonsters neer te schieten, en dit kan je investeren in anti-lucht torens.

In principe is een brute force aanpak vrij eenvoudig, lijkt me:

code:

vul_doolhof(speelveld)
{
  bepaal_vrije_posities(speelveld); /* Waar kunnen nog torens worden geplaatst? */

  if (speelveld vol) {
    int lengte = kortste_pad(speelveld);
    if (lengte > max_lengte) {
      bewaar_speelveld(speelveld);
    }
    return;
  }

  for (alle nog mogelijke posities)
  {
    plaats_toren(speelveld, huidige positie);
    vul_doolhof(speelveld);
    verwijder_toren(speelveld, huidige positie);
  }
}

vind_langste_pad_doolhof()
{
  init_speelveld(speelveld);
  vul_doolhof(speelveld);
  print_langste_speelveld();
}

Helaas zijn er wat problemen met dit algoritme:
- Er is geen ander criterium om te stoppen, anders dan dat het veld vol is. Als je eerder zou kunnen concluderen dat de ingeslagen weg kansloos is, dan zou dat veel in performance kunnen schelen.
- Veel van de performance zal afhangen van de representatie van het speelveld (2-d array ligt meest voor de hand) en met name de performance van de functies "bepaal_vrije_posities" en "kortste_pad". Met name "kortste_pad" zie ik nog niet voor me.

NB:
Het is belangrijk om bij "bepaal_vrije_posities" alleen posities te pakken die NA (volgens een of andere volgorde) de laatste toren liggen, anders komen we vaak uit op een doolhof die we eerder al hebben bekeken. Dat is een echte performance killer.

[ Voor 3% gewijzigd door KopjeThee op 30-12-2008 08:47 ]

[H!GHGuY]

er is maar 1 oplossing:

code:

+---------------------+
|                   uitgang
|   ------------------+
|                   ingang
+--------------------+

maw, 1 lange zigzag. Dan heb je echt wel het hele speelveld gezien.
of is mijn oplossing weer te simpel?

Het zou mij niet verwonderen dat je met een algoritme ook op deze oplossing uitkomt.

[ Voor 13% gewijzigd door H!GHGuY op 30-12-2008 13:06 ]

[Voutloos]

Dat leek mij ook gewoon, dat bij een rechthoekig speelveld de meest brede zigzaggende pad zeer dicht bij het optimale antwoord zit. Snapte het idee om te bruteforcen daarom al uberhaupt niet.

[ Voor 3% gewijzigd door Voutloos op 30-12-2008 13:39 ]

[mr_obb]

Het probleem is eigenlijk ook ingewikkelder dan het bouwen van de langste route. Je wilt de route bouwen waarbij de vijandelijke eenheden zo lang mogelijk binnen het bereik van je zware, opgewaardeerde torens zijn. Je bouwt het doolhof met goedkope torens en op strategische punten waardeer je torens op, die de schade aanrichten. Mijn doolhof bij het bovengenoemde spel is dan ook in een soort spiraalvorm om het middelpunt, waarbij in het midden dus de zware torens staan. Als je alleen een zigzaggend pas maakt, dan gebruik je volgens mij je torens niet optimaal.

Oh btw: Er zijn ook verschillende torens geschikt voor verschillende tegenstanders, wat het nog iets ingewikkelder maakt.

Kanon: redelijk grote schade aan meerdere tegenstanders binnen de ontploffingsradius. Goed voor grote hoeveelheden eenheden.

Normaal geschut: Grote schade aan één tegenstander. Niet geschikt voor groepen tegenstanders, maar uitermate effectief tegen eindbazen.

Luchtafweer: De vliegende tegenstanders.

Bevriezende toren: Heel handig om je doolhof nog langer te maken. Vertraagt tegenstanders, waardoor je langer op ze kunt blijven schieten. Eigenlijk wil je de vijandelijke eenheden door je hele doolhof wel bevriezen.

[ Voor 36% gewijzigd door mr_obb op 30-12-2008 13:53 ]

[BCC]

Een trechter vorm lijkt me dan ook erg efficient.

[stp_4]

Wellicht kun iets met breadth-first search algoritme doen

[ Voor 6% gewijzigd door stp_4 op 30-12-2008 16:43 ]

[Voutloos]

Je noemt nu enkel voor de lol een mogelijke zoekalgoritme, dus vertel maar hoe je die wil toepassen en waarom breadth-first een efficiente aanpak is.

[stp_4]

Voutloos schreef op dinsdag 30 december 2008 @ 15:27:
Je noemt nu enkel voor de lol een mogelijke zoekalgoritme, dus vertel maar hoe je die wil toepassen en waarom breadth-first een efficiente aanpak is.

Ik heb hem ooit gebruikt om de korste route te bepalen. Vond hem redelijk snel. Met dit algoritme evalueer je niet een bepaald vlak wat je reeds doorlopen hebt om een mogelijke route te bepalen. Wellicht kun je hem ook gebruiken om langste route bepalen. Dit zou wellicht in combinatie met dit algoritme mogelijk moeten zijn. Of het de meest efficiente manier is, daar is het alweer even voor geleden. Misschien de moeite waard om er even naar te kijken.

[ Voor 3% gewijzigd door stp_4 op 30-12-2008 16:48 ]

[Voutloos]

Nofi, maar je komt nog altijd niet verder met je toelichting. Je hebt 'een keer' iets 'redelijk snel' gevonden, maar je legt helemaal niet uit waarom je niet zomaar 'Depth-first!', 'IDA*' of wist ik het maar riep...

[stp_4]

Voutloos schreef op dinsdag 30 december 2008 @ 16:52:
Nofi, maar je komt nog altijd niet verder met je toelichting. Je hebt 'een keer' iets 'redelijk snel' gevonden, maar je legt helemaal niet uit waarom je niet zomaar 'Depth-first!', 'IDA*' of wist ik het maar riep...

Volgens mij is de vraag uit de TS: Nu vraag ik me af of hier een leuk algoritme voor is te verzinnen, die het doolhof met de langste route bepaald....Is er hier iemand met inspiratie voor een leuk algoritme?. Nou ik antwoord enkel op de vraag dat dit misschien in combinatie met breadth-first kan. Het is aan de topicstarter om te kijken of het kan, en of het zou kunnen voldoen aan zijn specifieke wensen.

[BCC]

Ik ga toch ook niet heel hard A* roepen... beetje zinloos.

[mocean]

Ik had zoiets, kost alleen wat tijd om te bouwen

code:

| XXXXXXXXXXXXXXXXXXXX|
| X                   |
| X XXXXXXXXXXXXXXXXX |
| X X XXXXXXXXXXXXX X |
| X X X           X X |
| X X X         X X X |
| X X           X X X |
| X XXXXXXXXXXXXX X X |
| X               X X |
| XXXXXXXXXXXXXXXXX X |
|                   X |
|XXXXXXXXXXXXXXXXXXXX |
|                     |

Maar in het midden een paar flinke torens en je kan ze echt vaak raken!
Ik ga steeds af op die vliegende dingen.

[KopjeThee]

Ik had zoiets (ingang boven, torens als 2x2 'x'-en):

code:

xx      xx     xx
xx xxxx xx xxxxxx   xx
   xxxx    xxxx   xxxx
 xx    xxxx    xx xx   xx
 xx xx xxxx xx xx   xx xx
 xx xx   xx xx   xx xx
 xx   xx xx   xx xx   xx
   xx xx   xx xx   xx xx
xx xx   xx xx   xx xx xx
xx xxxx xx   xx xx    xx
   xxxx   xx xx   xx  xx
 xx    xx xx   xx xx  xx
 xx xx xx   xx xx   xx
 xx xx   xx xx   xx xx
 xx   xx xx   xx xx   xx
   xx xx   xx xx   xx xx
xx xx xxxx xx xxxx xx xx
xx    xxxx    xxxx    xx
  xxxx    xxxx    xxxx
  xxxx    xxxx    xxxx

[Gomez12]

Mijn taktiek is gewoon een trechter naar het midden bouwen met laser torentjes ( met bovenin een doorgang van links naar rechts ) dan afbuigen en naar beneden langs de trechter dan omhoog zigzaggen met de goedkoopste torentjes die je maar kan vinden dan bovenlangs de trechter, gelijk langs de trechter weer naar beneden en weer omhoog zigzaggen met de goedkoopste torentjes.

Vertrager onderin je trechter, en dan je trechter versterken.

Je trechter rekent af met de vliegdingen, je zigzaggende torentjes voeren de lopers de hele tijd langs je sterke trechter.

Niet veel 1 of 2x upgraden, dit is waardeloos later. Gewoon paar torentjes 5 upgrades geven en daar de beeestjes zoveel mogelijk langsleiden

[KopjeThee]

Als ik kijk naar het kortste pad algoritme, dan lijkt mij de volgende aanpak mogelijk voor de functie "kortste_pad" (als ik een 2d-array gebruik, zoals in mijn voorbeeld veld):

• V = {Alle hokjes (in mijn representatie) op het veld waar geen toren staat}
• M_v = {Alle lege hokjes die direct grenzen aan hokje v}
• De gewichten van de lijnen zijn allemaal 1.
• Aangezien het kortste pad algoritme uitgaat van 1 beginpunt, voegen we een denkbeeldig leeg hokje toe die alleen grenst aan de 7 (in mijn representatie) ingangshokjes.
• We voegen ook een denkbeeldig uitgangshokje toe, die alleen grenst aan alle lege hokjes op de onderste rij (de mogelijke uitgangen)
• Het korste pad dat we willen hebben is die van het denkbeeldige ingangshokje naar het denkbeeldige uitgangshokje.
• De uitvoering van dit algoritme kan opgenomen worden in het recursieve algoritme dat ik eerder postte. De afstanden gevonden voor lege hokjes VOOR de laatst geplaatste toren, blijven natuurlijk onveranderd, dus in de functies "plaats_toren" en "verwijder_toren" kunnen ook de kortste pad verzamelingen worden ge-update.

De functie "bepaal_vrije_posities" in het eerder gepostte algoritme is ook belangrijk om efficient te krijgen. Een vereiste is dat niet alle uitgangen worden geblokkeerd door plaatsing van de toren. Het beste dat mij nu te binnen schiet, is om alle mogelijke plaatsingen uit te proberen, zonder rekening te houden met de "blokkeer eis".
Deze mogelijke plaatsingen kan ik filteren voor elk ervan het kortste pad algoritme uit te voeren en te kijken of de afstand van begin tot eind niet oneindig wordt. Helaas lijkt dit mij nogal inefficient. Betere suggesties zijn welkom.