Google ai challenge 2011

[317070]

Uiteraard geldt 'behoud van miserie' en zal je dan een mogelijk complex systeem moeten schrijven om zo'n kolonie mooi te laten bewegen.

Als ik je goed begrijp, noem ik die 'kolonies' gewoon formaties. Het probleem is dus precies hoe je die mieren binnen de formatie goed laat bewegen. Je oplossing is dus equivalent aan het probleem Nu heb ik iets A*-achtigs, maar doordat de mieren constant in elkaars weg lopen, is er iets efficiënters nodig.

[Xenion]

Je oplossing is dus equivalent aan het probleem

Uit wat je eerder schreef had ik de indruk dat je voor alle mieren afzonderlijk een pad bepaalt.

Ik stel voor van een formatie/kolonie als 1 geheel te beschouwen en dan het kortste pad van de kolonie tot een doel te zoeken. Zo reduceer je het aantal berekeningen bij het pad-zoeken al serieus.

Dit door een soort van massamiddelpunt van de kolonie te beschouwen of een leider-mier aan te duiden.

[Cycloon]

Inderdaad, het geheugen is dan ook niet echt het probleem, het is vooral die verwerkingstijd. Je moet alles binnen de seconde doen, dus path-finding zou hoogstens een paar ms per mier mogen duren.

Maar heb je concretere voorstellen? Bijvoorbeeld in deze situatie:

Code: Selecteer alles

   *   A   *		*

**** V **** A	*

* A ** A**	   *

V *** **** V   *

V		  * V

*******************

V	  A	   * V

Hoe krijg je alle mieren A zo snel mogelijk voorbij alle doelen V?

Het is eigenlijk zelf meer dan pathfinding. Je hebt hier ook te maken met het travelling salesman probleem waarbij je nog eens meerdere salesmen hebt. Zoals je wel zal weten is dit probleem al uitvoerig beschreven en zijn er legio oplossingen te vinden. Het voordeel dat je hier hebt is dat je naar een optimum kan werken omdat je sowieso maar een klein gezichtsveld hebt. Ik zou het niet teveel bij grafen zoeken eigenlijk maar het vooral bij wat matrices houden. Maar ik moet de spelregels en specificaties nog eens goed bekijken en er nog eens wat verder over nadenken

[317070]

Dit door een soort van massamiddelpunt van de kolonie te beschouwen of een leider-mier aan te duiden.

Nu ga je lachen, maar dat is precies ook de manier waarop het nu gebeurt (al gebruik ik geen 'massamiddelpunt', maar een leider als 'referentiemier'. De problemen komen pas als je de weg van de anderen vervolgens ook moet bepalen. Vooral als die weg langs fijne doorgangen leidt.

Ik zou het niet teveel bij grafen zoeken eigenlijk maar het vooral bij wat matrices houden. Maar ik moet de spelregels en specificaties nog eens goed bekijken en er nog eens wat verder over nadenken

Dat van die grafen en matrices weet ik wel, maar ik zou eigenlijk al blij zijn bij EEN algoritme, die omzetten naar een handige representatie moet me wel zelf lukken.

Het grote probleem is dat de 'map' zelf verandert in de tijd, doordat de mieren nooit op elkaar mogen stappen. Die algoritmes moeten zeker bestaan, want ze worden gebruikt in games e.d. Het probleem is dat ik door het academische bos met bomen die steunen op veel rekenkracht de realtime bomen niet meer zie.

[In physics I trust]

De contest is officieel nu. Er zijn belangrijke aanpassingen gedaan die het geheel een pak moeilijker maken. Je beschikt nu over een basis waar alle nieuw verworven mieren 'ontstaan', en als die door de vijand veroverd wordt, kan je geen ants meer bijkrijgen. Het spel is geëvolueerd naar een 'verdedig the hill'-spel.

[317070]

De contest is officieel nu.

Het is volgens mij nog niet officieel hoor, ik vind nergens een einddatum.

Ook lijkt het mij niet zo'n interessant spel, ik voorspel enorm veel draws.

[In physics I trust]

Dat laatste vrees ik ook. Maar officieel toch wel (ver) dan: alle accounts zijn verwijderd en de opzet is grondig overhoop gehaald.