AI Challenge: Ants!

[H!GHGuY]

Ik heb nu even de waarden behoorlijk verhoogd en de huidige versie maakt gehakt van de meegeleverde bots.
Even deze versie gettagged in git en geupload... Zien wat het wordt?

[Skinny]

Wat me nu al twee avonden tot waanzin drijft is dat ik blijkbaar soms een order kan geven om E(ast) te gaan en vervolgens een regel lager (dus South) uit te komen. Dit is met de tools-package op windows, maar ik kan maar niet boven water krijgen hoe dit komt. Iemand enig idee ?

Er is geen water, voedsel of andere ants in de buurt, maar toch als ik in turn 7 zeg : 9,71 E) , dan kom ik in de volgende beurt uit op 10,71.. Wat mis ik hier!

[Verwijderd]

Je coordinaten zijn omgekeerd? De bot doet eerst row (Y dus), en daarna col (X).

[Skinny]

Please correct me if i'm wrong (hopelijk ben ik dat ) :

0,0 = Linksboven
9,71 = (rij 9, kolom 71)
Als ik dan EAST ga, kom ik toch op 9,72 uit ?

In de beurten erboven gaat het namelijk wel zoals ik verwacht (9,69 e => 9,70)

[Noq]

Ben een beginner met C#, dacht dat dit weleens een leuke test kon zijn.
Bij nader in zien, na het bekijken van de starter kit, is dit nog iets te ver weggelegd. Jammer dat ze Java en Python hebben uitgelegd en niet een begin voor C#.

[Soultaker]

Persoonlijk zou ik de starter kit negeren en gewoon tegen de protocolspecificatie aan coden. Dat heb ik met C++ uiteindelijk ook gedaan omdat ik me ergerde aan bepaalde dingen in de starter kit (zoals de zinloze puntkomma's die ze overal neerplempen).

M'n complete speler is minder dan 100 regels edit: oeps, toch al weer 350 regels code, maar dat moet in C# ook nog wel te behappen zijn.

[ Voor 7% gewijzigd door Soultaker op 08-11-2011 21:42 ]

[Caelorum]

Soultaker schreef op dinsdag 08 november 2011 @ 21:39:
Persoonlijk zou ik de starter kit negeren en gewoon tegen de protocolspecificatie aan coden. Dat heb ik met C++ uiteindelijk ook gedaan omdat ik me ergerde aan bepaalde dingen in de starter kit (zoals de zinloze puntkomma's die ze overal neerplempen).[...]

Hier heb ik ook over zitten te denken, maar kon zo snel geen protocolspecificatie vinden. Enig idee waar deze staat? Ben namelijk lui en heb geen zin om te kijken welke berichten heen en weer worden gegooid. Ik las trouwens ook in de aichallenge forums dat er een tcp versie bestaat?

[Bolukan]

Bolukan schreef op dinsdag 08 november 2011 @ 10:40:
[...]
Het lijkt dat mijn ants in het water willen springen.

En na 1,5 uur debuggen voeg je toe:

code:

&& state[movement.Location].IsLand

en is dat probleem weer opgelost.

Dit vond plaats als de 'Smell' alle kanten op 0 was. En water heeft ook 0.

Het komt bij me voor dat Ants elkaar als lemmings verdringen. Alle ants komen achter elkaar aan de beurt en bepalen hun stap. Een ant kan dan soms geen plek meer hebben als hij aan de beurt is. North, South, East, West en het eigen plekje zijn al bezet geraakt of zijn water. Gevolg is dat 2 ants sterven. Hoe voorkomen jullie dat?

[ Voor 30% gewijzigd door Bolukan op 08-11-2011 23:56 ]

[D-Raven]

Mijn laatste replay: http://aichallenge.org/visualizer.php?game=76398

Zoals je ziet gaan mijn ants wel voor de vijandige hills, maar kunnen ze niet die laatste stap zetten. Zeer irritant. Ben er nog steeds niet uit waarom dat is.

Heb ondertussen de huidige versie als "leuk probeersel" bestempeld en ben met een nieuwe versie vanaf scratch begonnen.

[Verwijderd]

Bolukan schreef op dinsdag 08 november 2011 @ 22:23:
Het komt bij me voor dat Ants elkaar als lemmings verdringen. Alle ants komen achter elkaar aan de beurt en bepalen hun stap. Een ant kan dan soms geen plek meer hebben als hij aan de beurt is. North, South, East, West en het eigen plekje zijn al bezet geraakt of zijn water. Gevolg is dat 2 ants sterven. Hoe voorkomen jullie dat?

Je ants kunnen ook stil blijven staan hoor

[IWriteCode]

Punt is dat de andere mieren al allemaal bewogen hebben... en dat die ene mier dus 'opgesloten' zit tussen de andere mieren... waarvan er eentje al richting die mier beweegt...

[Caelorum]

IWriteCode schreef op woensdag 09 november 2011 @ 09:24:
Punt is dat de andere mieren al allemaal bewogen hebben... en dat die ene mier dus 'opgesloten' zit tussen de andere mieren... waarvan er eentje al richting die mier beweegt...

Gewoon niet richting een mier bewegen. Richting een vriendelijke mier dan De vijand mag je best mee colliden vooral als je outnumbered bent

[ Voor 13% gewijzigd door Caelorum op 09-11-2011 09:31 ]

[IWriteCode]

Als je niet richting een vriendelijke manier beweegt, dan hebben je mieren altijd een tussenruimte van 1... en dat is weer minder efficient!

[D-Raven]

Bolukan schreef op dinsdag 08 november 2011 @ 22:23:
[...]


En na 1,5 uur debuggen voeg je toe:

code:

&& state[movement.Location].IsLand

en is dat probleem weer opgelost.

Dit vond plaats als de 'Smell' alle kanten op 0 was. En water heeft ook 0.

Het komt bij me voor dat Ants elkaar als lemmings verdringen. Alle ants komen achter elkaar aan de beurt en bepalen hun stap. Een ant kan dan soms geen plek meer hebben als hij aan de beurt is. North, South, East, West en het eigen plekje zijn al bezet geraakt of zijn water. Gevolg is dat 2 ants sterven. Hoe voorkomen jullie dat?

Bijhouden naar welke locaties al gemoved is, en deze uitsluiten in je move functie. Wat ook helpt is ants die bv naar het noorden gaan, de meest noordelijke Ant eerst verzetten, en daarna de rest. Wat inhoud dat je wat met Sortering en move prioriteiten moet gaan doen.
Ikzelf doe dit momenteel door pseudo code

C#:

while(ant in queueOfUnorderedAnts)
{
    
    ....
    probeer ant te moven
        andere mier is in de weg?
                is andere mier al verteld dat ie op moet zouten?
                   nee? doe niks
                     ja? haal ant uit queue, blijkbaar kan hij nergens naartoe, dus dan wachten we maar een ronde

}

Wellicht niet meest efficiente manier, maar op deze manier blijft hij mieren afgaan totdat iedereen een move order gehad heeft, of zeker weten niet verder kan bewegen.
Ander alternatief (aangezien ik oa A* gebruik) was om bij het bepalen van het pad rekening te houden met paden van andere mieren, maar dit was 1, te rekenintensief, en 2 leidde vaak tot tijdelijke dead ends waardoor ik per target niet 1, maar 3 of 4 keer een pad moest berekenen terwijl hij onderweg is.
Dit wordt natuurlijk meer zodra je veel ants richting een doelwit hebt gaan.

Heb overigens echt grootste lol met dit project. Lang geleden dat ik met priority queus en array search algoritmes gewerkt heb. In mn dagelijks werk heb dit soort dingen zo goed als niet.

[ Voor 21% gewijzigd door D-Raven op 09-11-2011 09:48 ]

[Koopmans]

Hmm,, de 1e ronde van mijn nieuwe versie is geeindigd in een timeout.
Wel gek dat van de 7 bots er 6 eindigden met een timeout.

Misschien toch maar eens wat meer lokaal testen, met grotere maps.
Ik gebruik nog steeds dat voorbeeld uit de tutorial waar je eigen bot tegen die hunterbot speelt. Tegen welke testbots en met welke map testen jullie?

code:

python tools/playgame.py "java -jar MyBot.jar" "python tools/sample_bots/python/HunterBot.py" --map_file tools/maps/example/tutorial1.map --log_dir game_logs --turns 60 --scenario --food none --player_seed 7 --verbose -e

Dit is mijn opstart commando...

[D-Raven]

Koopmans schreef op woensdag 09 november 2011 @ 09:45:
Hmm,, de 1e ronde van mijn nieuwe versie is geeindigd in een timeout.
Wel gek dat van de 7 bots er 6 eindigden met een timeout.

Misschien toch maar eens wat meer lokaal testen, met grotere maps.
Ik gebruik nog steeds dat voorbeeld uit de tutorial waar je eigen bot tegen die hunterbot speelt. Tegen welke testbots en met welke map testen jullie?

code:

python tools/playgame.py "java -jar MyBot.jar" "python tools/sample_bots/python/HunterBot.py" --map_file tools/maps/example/tutorial1.map --log_dir game_logs --turns 60 --scenario --food none --player_seed 7 --verbose -e

Dit is mijn opstart commando...

Ik heb zelf meerdere test fases. Eerste test is op een kleine 2p relatief open map, Tweede test is op 2p doolhof map. Derde 4p open map, etc...

Heb een unit test geschreven die meerdere games tegelijkertijd opstart. Zodra ze klaar zijn mag ik 5 minuten lang gaan kijken hoe mijn bot alles inmaakt, of hopeloos faalt

[Sjaaky]

Ik speel tegen dezelfde en/of oudere versies van mijn bot. Een vriend van me is ook bezig, dus we wisselen bots uit. Testen doe ik meestal op random_walk_04p_02.map, af en toe pak ik een andere.

Hij gaat wel lekker, nog steeds versie 1: http://aichallenge.org/profile.php?user=9683

[IWriteCode]

Sjaaky schreef op woensdag 09 november 2011 @ 09:53:
Ik speel tegen dezelfde en/of oudere versies van mijn bot. Een vriend van me is ook bezig, dus we wisselen bots uit. Testen doe ik meestal op random_walk_04p_02.map, af en toe pak ik een andere.

Hij gaat wel lekker, nog steeds versie 1: http://aichallenge.org/profile.php?user=9683

Die gaat inderdaad erg goed... :-) Na een aantal dagen flink knutsellen ga ik ff een dagje of 2 pauze inlassen :-)

[MLM]

D-Raven schreef op dinsdag 08 november 2011 @ 12:04:
[...]


Dus als je een grid hebt met bijna 5000 locaties, dan ga jij elke beurt voor elke mier die jij hebt, bepalen of een locatie zichtbaar is?
Dan ben ik toch wel benieuwd hoe je dat doet, zonder dat je Bot timeout zodra je een deftige hoeveelheid mieren hebt (zeg 100+).

De maximale map size is 200x200, dus 40000 locaties Maar natuurlijk doe ik het niet op de naieve manier, dat gaat te lang duren
Ik bereken 1x vooraf een 2D array aan de hand van viewradius2, waarin ik op de juiste locaties de bits voor "visible" en "discovered" op 1 zet, en de rest op 0. Daarna, elke keer als ik input ophaal, ga ik voor elke van mijn ants (dat worden er niet meer dan 500 verwacht ik) een logical-or operatie doen met die array over de map, dat gaat vrij vlot

Maar goed, dat "visible" is niet wat ik belangrijk vind, het gaat om die "discovered", omdat ik dat ga gebruiken voor het pre-computen van paden, omdat A* best duur word op langere paden (vooral in die maze-maps)

[Verwijderd]

^Die truuk had ik ook al bedacht

[Bolukan]

Bedoel je dan een echte bitwise array, met andere woorden heb je de map 200x200 als 5000 bytes opgeslagen. Ik gebruik ook een list met vectors, maar mijn map bestaat uit objecten (a la starterspakket van C#, 85% changed ) en dan

code:

voor elke mier
   voor elke vector
      map[mier+vector].visible = true

[Sjaaky]

Koopmans schreef op woensdag 09 november 2011 @ 09:45:
Hmm,, de 1e ronde van mijn nieuwe versie is geeindigd in een timeout.
Wel gek dat van de 7 bots er 6 eindigden met een timeout.

Dan waren dat zeker ook java-bots? Het starterpack gebruikt een heeeele langzame manier om input te lezen. Daardoor ben je al door bijna door je tijd heen op het moment dat je alles binnen hebt. Er is meer over te vinden op het aichallenge forum.

[D-Raven]

Bolukan schreef op woensdag 09 november 2011 @ 12:28:
Bedoel je dan een echte bitwise array, met andere woorden heb je de map 200x200 als 5000 bytes opgeslagen. Ik gebruik ook een list met vectors, maar mijn map bestaat uit objecten (a la starterspakket van C#, 85% changed ) en dan

code:

voor elke mier
   voor elke vector
      map[mier+vector].visible = true

Dit doe ik momenteel ook. Dichtstbijzijnde undiscovered/unseen locatie zoek ik dmv binairy search.

[MLM]

Bolukan schreef op woensdag 09 november 2011 @ 12:28:
Bedoel je dan een echte bitwise array, met andere woorden heb je de map 200x200 als 5000 bytes opgeslagen. Ik gebruik ook een list met vectors, maar mijn map bestaat uit objecten (a la starterspakket van C#, 85% changed ) en dan

code:

voor elke mier
   voor elke vector
      map[mier+vector].visible = true

mijn map is 1 byte per hokje, waarvan 7 bits gebruikt:
1 - discovered (1 indien ooit gezien, ik weet dus zeker of het land/water is)
2 - water (1 indien water, mogelijk in de toekomst een "gok" adhv symmetrie)
3 - visible (1 indien zichtbaar deze beurt)
4 - ant (1 indien een mier in dit hokje deze beurt)
5 - hill (1 indien een "levende" hill in dit hokje deze beurt)
6 - mine (1 indien de mier of hill van mij is)
7 - food (1 indien er food is in dit hokje)
8 - ongebruikt

de enige informatie die ik dus mis in die map is welke tegenstander welke mieren bestuurd
als er dus een map is van 200x200 heb ik een stuk geheugen van 40KB voor de hele map

bijkomende voordelen van deze representatie:
1 - lineair (std::vector<std::vector<T>> is gefragmenteerd)
2 - compact (past in zijn geheel in de CPU cache)
3 - efficient te bewerken (4 hokjes tegelijk met een 32bit int)

of dit de beste representatie is, geen idee, maar dat is hoe ik het voor nu heb gedaan ik hoor graag andere ideeen over wat andere mensen doen

[mr_obb]

Sjaaky schreef op woensdag 09 november 2011 @ 12:56:
[...]


Dan waren dat zeker ook java-bots? Het starterpack gebruikt een heeeele langzame manier om input te lezen. Daardoor ben je al door bijna door je tijd heen op het moment dat je alles binnen hebt. Er is meer over te vinden op het aichallenge forum.

En wel hier: http://aichallenge.org/forums/viewtopic.php?f=25&t=1713

[Koopmans]

Hey bedankt voor die tip over de scanner

[SaphuA]

.

[ Voor 98% gewijzigd door SaphuA op 31-01-2022 15:56 ]

[D-Raven]

SaphuA schreef op woensdag 09 november 2011 @ 13:56:
Klopt het dat de standaard c# bot crashed? Krijg hem namelijk niet werkend en ben dus benieuwd of het aan mij ligt of niet. De console applicatie compiled gewoon met de starter package files.

Euh, bij mij werkte het gewoon. Wat bedoel je precies met crashen?

[SaphuA]

.

[ Voor 180% gewijzigd door SaphuA op 31-01-2022 15:56 ]

[D-Raven]

SaphuA schreef op woensdag 09 november 2011 @ 14:13:
Met andere bots werkt ie gewoon, maar als ik mijn bot probeer krijg ik:

[...]

- Zet in je main Debugger.Break;
- Verhoog --turntime naar 300000

happy debugging. Je moet alleen wel zodra je de game start en je krijgt de prompt om de debugger eraan te hangen, dit ook meteen doen. Dat ding heeft namelijk een timeout bij bot startup, dus als je te lang wacht dan killt ie je process voordat je de kans krijgt om je debugger eraan te hangen.

Zorg er vervolgens voor dat je een breakpoint in the DoTurn hebt staan en voila. happy debugging.

Edit: Ow er is ook een parameter --loadtime hiermee kun je de opstart tijd verhogen zodat je meer tijd hebt om je debugger eraan te hangen.

[ Voor 9% gewijzigd door D-Raven op 09-11-2011 19:39 ]

[IWriteCode]

Toch nog maar wat stappen gedaan... heb nu:
- simpele tactiek vijand sterker of gelijk, terugtrekken, anders aanvallen
- zoeken naar voedsel
- zoeken naar hills
- naar onverkend gebied gaan
Wat ik alleen nog moet optimaliseren (behalve betere tactiek) is het bezoek van al bezochte locaties die niet meer zichtbaar zijn... daar heb ik al ideeen over... maar moet nog even slim bedenken hoe dat toe te passen :-)

[Koopmans]

Ondanks een crash had mijn laatste versie toch gewonnen.
Heb 'm lokaal maar even wat langere partijen laten spelen van 1000 turns op "random walk" 4p en 8p. Kwam nog een paar andere foutjes tegen welke ik gefixed heb.

Ben wel benieuwd wat ie nu gaat doen, lange potjes lokaal zijn nu geen probleem meer. Dankzij een nieuwe scanner implementatie heb ik ook geen timeout problemen meer. Nog erg bedankt voor de tip.

Ik heb eigenlijk alleen nog maar het eventueel aanvallen van enemy hills er in zitten en dan ook nog erg simpel. Hoogste prio heeft toch nog het voedsel zoeken. Krijg er op het laatst zoveel binnen dat ik enkele honderden ants in de wachtrij heb staan. Eerst maar een afwachten wat mijn laatste versie vannacht gaat doen.

[Thmz159]

Koopmans schreef op woensdag 09 november 2011 @ 20:24:
Ik heb eigenlijk alleen nog maar het eventueel aanvallen van enemy hills er in zitten en dan ook nog erg simpel. Hoogste prio heeft toch nog het voedsel zoeken.

Dat vindt ik niet Het enige waar je echt punten mee kan scoren is hills razen of de andere kolonie uitmoorden. Dus als er in een game iemand met 10 ants 2 hills razed en de rest met 100 ants maar elks maximum 1 hill razed wint die met 10 hills toch omdat zijn score hoger is

Probleem bij mijn bot is dat er een bug in de pathfinding zit dat hij nooit het pad naar een hill vindt, en het met food wel werkt

[Bolukan]

Mee eens.

NB: Maar als je hoog wilt komen (in de scorelijst) moet je rekening houden met betere verdediging 'op dat niveau' en zal aandacht voor omvang belangrijk zijn.

PS:
Ik wil mijn smells wat ruimer verspreiden. Even gekeken naar de max-variant namelijk totale flooding en dat getest op alle oefenmaps (uitgaande van totale zichtbaarheid). Bij de ergste map zitten er maximaal 256 tiles in de queue. Qua geheugen dus geen issue (256 x 2 bytes = 512 bytes). Doorlooptijd per map verschilt, ik meet ca 20 ms (zonder optimalisatie). De map met de korste weg is 50 tiles en de map met de langste weg is 266 tiles.

[ Voor 74% gewijzigd door Bolukan op 10-11-2011 23:39 ]

[Soultaker]

Caelorum schreef op dinsdag 08 november 2011 @ 21:57:
Hier heb ik ook over zitten te denken, maar kon zo snel geen protocolspecificatie vinden. Enig idee waar deze staat?

Zie de Bot Input en Bot Output in de Game Specification (die je sowieso helemaal door moet lezen om uit te vinden hoe het spel werkt, of je nu de starter kit gebruikt of niet).

[Koopmans]

Voedsel zoeken heeft bij mij nu nog de hoogste prioriteit omdat ik namelijk nog moet bedenken hoe ik de aanvals strategie ga inbouwen...

[SaphuA]

.

[ Voor 100% gewijzigd door SaphuA op 31-01-2022 15:56 ]

[Verwijderd]

Ik had bedacht dat je van elke punt in de map kan berekenen wat de kortste route is naar elk ander punt is. Met 4 bits per punt (voor elke richting een) kost dat ongeveer 800MB, sla je voor de helft van de punten deze data op, dat kom je op 200MB.

De vraag is natuurlijk wanneer je dat allemaal gaat berekenen...

[D-Raven]

SaphuA schreef op donderdag 10 november 2011 @ 10:01:
Ik weet niet of ik veel tijd ga hebben voor het maken van een eigen bot, maar vind het iig erg leuk om hierover na te denken

Ik kan me indenken dat pathfinding de grootste bottleneck zal zijn bij de meeste engines. Het A* algo kan redelijk effectief geimplementeerd worden, maar als je deze per mier gaat runnen kost dat nog aardig wat tijd.

Een manier waarop het volgens mij nog een stapje effectiever zou kunnen is door het gebruik van waypoints. Dit plaatje laat ongeveer zien wat ik bedoel:
[afbeelding]

Het idee is dat je eenmalig de map effectief opdeelt mbv. waypoints. Als je een mier wilt gaan verplaatsen zoek je, met behulp van A*, de korste weg naar een waypoint. Ook zoek je de waypoint die het korste weg is van het gewenste eindpunt. Vervolgens gebruik je dijkstra's om tussen de waypoints de korste route te vinden.

In theorie zou je hier een hoop tijd mee kunnen winnen, omdat 90% van een route vooraf al bekend is, maar het is natuurlijk de vraag of het op zo'n kleine map wel effectief geimplementeerd kan worden. Tevens zal het ook van het type map afhangen of de waypoints wel fatsoenlijk gegenereerd kunnen worden.

Hier heb ik ook over na zitten denken. Je krijgt dan wel wat interesante vraagstukken, bv hoe hoog maak ik de resolutie van mijn waypoint grid? Plus een hele hoop vraagstukken die op komen zetten als er meerdere mieren op hetzelfde pad tussen de dezelfde waypoint onderweg zijn, al dan niet richting elkaar of niet.

Ik heb het uiteindelijk laten zitten (vooralsnog).

[SaphuA]

.

[ Voor 99% gewijzigd door SaphuA op 31-01-2022 15:56 ]

[D-Raven]

SaphuA schreef op donderdag 10 november 2011 @ 10:24:
@DarkStone, dan lijkt een middenweg me een betere keuze

@Death, klopt. Zal moeilijk worden om het te optimalizeren voor alle map types.

Meerdere mieren zou evt. op te lossen zijn met een flocking algo: http://www.red3d.com/cwr/steer/CrowdPath.html

Maar dat gaat allemaal erg complex worden

Flocking staat op mijn lijstje, ga ik zeker implementeren, zodra ik wat andere bugs uit de weg heb. Sterker nog. Ik wil uiteindelijk al mijn ants via flocking aansturen, en dan vanuit het middelpunt met A* een pad berekenen.

Op die manier hoef ik veel minder paden te berekenen. * D-Raven was geinspireerd door de "Borg" bot een paar pagina's terug en dacht, dat wil ik ook!!!

[Noq]

Is er een tutorial aanwezig voor C#?
Ik heb gister een tijdje erin gekeken, maar ik kom er niet ver mee

Jammer dat ze alleen Java en Python uitleggen. Python kan ik wel een beetje, maar heb ik niet zoveel ervaring in als C#.

[D-Raven]

Zo moeilijk is het toch niet om de java tutorial te volgen hiervoor en .Net types te gebruiken waar toepasbaar? De logica blijft immers hetzelfde, of je het nu in java of in c# doet..

[Noq]

D-Raven schreef op donderdag 10 november 2011 @ 10:49:
Zo moeilijk is het toch niet om de java tutorial te volgen hiervoor en .Net types te gebruiken waar toepasbaar? De logica blijft immers hetzelfde, of je het nu in java of in c# doet..

Voor iemand die nog geen 2 maanden bezig is met programmeren vind ik het toch wel een uitdaging om dat te gaan ondernemen.
Maar wellicht zie ik de logica als ik er vanavond even de Java-variant naast houdt.

[Alwinonline]

@Noq ik ben zelf ook pas sinds kort begonnen met programmeren (in C#) en vind het ook lastig. Al begin ik steeds beter te begrijpen hoe het in elkaar steekt alleen omdat ik er niet uitkom hoe ik moet debuggen vind ik het nog behoorlijk lastig.

[Bolukan]

Los van de grote discussie over pathfinding of influence map, wil ik aanvullende heuristieken toepassen op micro-situaties.

Denk aan:
* Een speler die 2 ants heel bewust slim richt op een tegenstander en opslokt.
* In mazes doorgangen blokkeren om je voedsel te beschermen.
* Een bijzondere situatie is een doorgang met breedte 1. Die kan je met 2 stilstaande ants eeuwig bewaken (totdat je in de rug wordt aangevallen).

Met betrekking tot dat laatste: naar welke theorie moet ik zoeken om cellen te vinden die een doorgang met breedte 1 zijn?
En hebben jullie meer ideeen?

[ Voor 32% gewijzigd door Bolukan op 10-11-2011 11:47 ]

[Hydra]

Bolukan schreef op donderdag 10 november 2011 @ 11:32:
Los van de grote discussie over pathfinding of influence map, wil ik aanvullende heuristieken toepassen op micro-situaties.

Denk aan:
* Een speler die 2 ants heel bewust slim richt op een tegenstander en opslokt.

Dat zie je nu al gebeuren in games, dat AI's 'team's van ants hebben die samenwerken. Grappig als beide teams een dergelijke AI hebben die zich niet zo positioneert dat ze kwetsbaar zijn, die blijven dan een beetje om elkaar heen dreutelen.

Je hoeft trouwens natuurlijk ook niet voor elke mier A* te gaan gebruiken. Als je verschillende taken hebt (blokkeren van je mound, beetje rondrennen en scouten naar voedsel, andere mieren aanvallen) dan hoef je eigenlijk alleen maar A* te gebruiken om bij bepaalde goals te komen, en daarvoor wil ej dan een mier pakken die al in de buurt is.

Daarnaast weet je ook hoe lang je beurt bezig is en zou je sowieso af moeten kappen op het moment dat je tijd op is.

[H!GHGuY]

Bolukan schreef op donderdag 10 november 2011 @ 11:32:
Los van de grote discussie over pathfinding of influence map, wil ik aanvullende heuristieken toepassen op micro-situaties.

Denk aan:
* Een speler die 2 ants heel bewust slim richt op een tegenstander en opslokt.
* In mazes doorgangen blokkeren om je voedsel te beschermen.
* Een bijzondere situatie is een doorgang met breedte 1. Die kan je met 2 stilstaande ants eeuwig bewaken (totdat je in de rug wordt aangevallen).

Met betrekking tot dat laatste: naar welke theorie moet ik zoeken om cellen te vinden die een doorgang met breedte 1 zijn?
En hebben jullie meer ideeen?

Je kan eens proberen met een hoge influence aan water te geven en zo een squares to zoeken waarvoor je waarde > de helft van die influence.

[Vaan Banaan]

Verwijderd schreef op donderdag 10 november 2011 @ 10:09:
Ik had bedacht dat je van elke punt in de map kan berekenen wat de kortste route is naar elk ander punt is. Met 4 bits per punt (voor elke richting een) kost dat ongeveer 800MB, sla je voor de helft van de punten deze data op, dat kom je op 200MB.

De vraag is natuurlijk wanneer je dat allemaal gaat berekenen...

Ik heb nog helemaal geen letter geprogrammeerd, maar ben ook met hetzelfde idee bezig.
Alleen wil ik ook de afstanden weten, dus dat gaat voor mij niet werken met bitjes.
De nog te berekenen punten wil ik in een queue gooien en dan een per beurt de queue een aantal milliseconden geven om uit te breiden. Die zal hopelijk niet meer dan een paar MB groot worden, maar dat zie ik dan wel weer.

[D-Raven]

Vaan Banaan schreef op donderdag 10 november 2011 @ 13:47:
[...]

Ik heb nog helemaal geen letter geprogrammeerd, maar ben ook met hetzelfde idee bezig.
Alleen wil ik ook de afstanden weten, dus dat gaat voor mij niet werken met bitjes.
De nog te berekenen punten wil ik in een queue gooien en dan een per beurt de queue een aantal milliseconden geven om uit te breiden. Die zal hopelijk niet meer dan een paar MB groot worden, maar dat zie ik dan wel weer.

In plaats van om van te voren alle paden te berekenen, zou ik als een mier een pad eenmaal berekend heeft, deze op dat moment in een cache stoppen. Je zou daar dan nog optimalisaties in kunnen aanbrengen, als je namelijk eenmaal een pad van x naar y weet, dan weet je ook het pad van ieder punt wat tussen x en y ligt, welke naar y gaat.

[mr_obb]

Mijn idee was om mijn (aanvallande) mieren in te delen in geweergroepen, pelotons en een compagnie. Alleen de sergeant binnen een geweergroep berekent zijn route richting het doel en de andere lopen achter hem aan. Als een peloton moet bewegen, dan berekent de kapitein de route, de sergeants volgen hem en de troepen volgen de sergeants.

De verzamelmieren wil ik maar in een beperkt gebied laten verzamelen (zeg een straal van 20 velden) en de verdedigende mieren hebben ook een kleine straal rond hun verdedigingsobject.

Daarmee is de behoefte aan het berekenen van lange paden een heel stuk ingeperkt en kan ik volgens mij af met A* als belangrijkste navigatiemiddel.

[MLM]

SaphuA schreef op donderdag 10 november 2011 @ 10:01:
Ik weet niet of ik veel tijd ga hebben voor het maken van een eigen bot, maar vind het iig erg leuk om hierover na te denken

Ik kan me indenken dat pathfinding de grootste bottleneck zal zijn bij de meeste engines. Het A* algo kan redelijk effectief geimplementeerd worden, maar als je deze per mier gaat runnen kost dat nog aardig wat tijd.

Een manier waarop het volgens mij nog een stapje effectiever zou kunnen is door het gebruik van waypoints. Dit plaatje laat ongeveer zien wat ik bedoel:
[afbeelding]

Het idee is dat je eenmalig de map effectief opdeelt mbv. waypoints. Als je een mier wilt gaan verplaatsen zoek je, met behulp van A*, de korste weg naar een waypoint. Ook zoek je de waypoint die het korste weg is van het gewenste eindpunt. Vervolgens gebruik je dijkstra's om tussen de waypoints de korste route te vinden.

In theorie zou je hier een hoop tijd mee kunnen winnen, omdat 90% van een route vooraf al bekend is, maar het is natuurlijk de vraag of het op zo'n kleine map wel effectief geimplementeerd kan worden. Tevens zal het ook van het type map afhangen of de waypoints wel fatsoenlijk gegenereerd kunnen worden.

Zoek eens naar HPA*

[Verwijderd]

Vaan Banaan schreef op donderdag 10 november 2011 @ 13:47:
[...]

Ik heb nog helemaal geen letter geprogrammeerd, maar ben ook met hetzelfde idee bezig.
Alleen wil ik ook de afstanden weten, dus dat gaat voor mij niet werken met bitjes.

Daar heb ik ook aan gedacht: als je voor elke node (= 1 hokje van het veld) weet welke richting de bestemming is, kan je aan de hand daarvan berekenen hoe ver weg de bestemming is, dat kost maar weinig tijd aangezien het pad maximaal, wat, 500 nodes? is. Als j ook de lengte gaat opslaan heb je opeens 5 a 6x zoveel ruimte nodig.

[Vaan Banaan]

D-Raven schreef op donderdag 10 november 2011 @ 13:54:
In plaats van om van te voren alle paden te berekenen, zou ik als een mier een pad eenmaal berekend heeft, deze op dat moment in een cache stoppen. Je zou daar dan nog optimalisaties in kunnen aanbrengen, als je namelijk eenmaal een pad van x naar y weet, dan weet je ook het pad van ieder punt wat tussen x en y ligt, welke naar y gaat.

Exact. Dat wil ik precies gebruiken om de hele map toch in het toegestane geheugen gepropt te krijgen.
Als een mier bijvoorbeeld naar Noord kan blijven doorbanjeren, zijn de paden naar boven (Elke richting van W naar N tot E) allemaal 1 korter en vanaf de mier naar onder allemaal 1 langer.
Dus ik ben nog aan het brainstormen, of ik dan alleen rond water paden hoef te berekenen en de rest daarvan kan afleiden. Maar met het tekenen en berekenen van kleine open kaartjes heb ik nu al problemen met de wrap arounds. Ik ben dus nog wel even bezig, maar dat houdt me van de straat.

[Bolukan]

H!GHGuY schreef op donderdag 10 november 2011 @ 12:51:
[...]
Je kan eens proberen met een hoge influence aan water te geven en zo een squares to zoeken waarvoor je waarde > de helft van die influence.

Probleem daarmee is dat een doorgang (hier in het midden) een lagere waarde kan hebben dan andere cellen en toch de doorgang is.

58	66	76	88	100
66	75	84	100	88
76	84	84	84	76
88	100	84	75	66
100	88	76	66	58

[ Voor 17% gewijzigd door Bolukan op 10-11-2011 15:32 ]

[Sh4wn]

Beetje tussen de tentamens door de logging mogelijkheden van C++ starterkit herschreven, beetje over-engineered waarschijnlijk (maar wat wil je met een vak 'software engineering methods' in deze periode), maar werkt wel lekker.

Volgende week beginnen met influence maps implementeren, vraag mij alleen af of ik wel genoeg geheugen daarvoor heb (vooral als je meerdere wil).

[D-Raven]

Sh4wn schreef op donderdag 10 november 2011 @ 16:01:
Beetje tussen de tentamens door de logging mogelijkheden van C++ starterkit herschreven, beetje over-engineered waarschijnlijk (maar wat wil je met een vak 'software engineering methods' in deze periode), maar werkt wel lekker.

Volgende week beginnen met influence maps implementeren, vraag mij alleen af of ik wel genoeg geheugen daarvoor heb (vooral als je meerdere wil).

Je hebt 1 GB tot je beschikking, dus leef je uit?

[H!GHGuY]

Bolukan schreef op donderdag 10 november 2011 @ 15:24:
[...]


Probleem daarmee is dat een doorgang (hier in het midden) een lagere waarde kan hebben dan andere cellen en toch de doorgang is.

58	66	76	88	100
66	75	84	100	88
76	84	84	84	76
88	100	84	75	66
100	88	76	66	58

Misschien even zoeken naar de juiste threshold

[Verwijderd]

2 dagen gewerkt aan collaborative diffusion in python...

En dan uiteindelijk dat moment... Waarop het helemaal werkt!

Het wordt een hybride oplossing met a* en CD...

Van het weekend nog "even" de strategie uitwerken...

Sta op dit moment met alleen a* in de top 1250...
ik ben benieuwd hoever ik kom met CD erbij

[Bolukan]

Lekkere start van de ochtend game

[Caelorum]

Ahja je hebt iig punten gekregen toch?

[ Voor 7% gewijzigd door Caelorum op 11-11-2011 08:44 ]

[D-Raven]

Bolukan schreef op vrijdag 11 november 2011 @ 08:33:
Lekkere start van de ochtend game

Nice gedaan hoor Wat gebruik je nu? Diffusion ?

lol.. mijn laatste game: http://aichallenge.org/vi....php?game=83598&user=9244

• Nog steeds dat probleem dat hij enemy hills niet wilt razen
• Exploration heuristiek is nog erg simpel, aka ga in random directie vanuit hill en blijf in die directie gaan totdat je iets tegenkomt. Vandaar het grote kruis op een gegeven moment bij mijn anthill

Ondertussen al gefixed, zit alleen nog met mn exploration heuristiek, tot nu toe nog niks bedacht waar ik tevreden mee kan zijn . De manier waarop je je dichtbijzijnde niet ontdekte punt opzoekt veranderd naarmate er meer zichtbaar is op de kaart. Tenminste, als je A* gebruikt dit soort dingen zijn dan weer rete simpel als je Diffusion gebruikt.

[ Voor 57% gewijzigd door D-Raven op 11-11-2011 08:58 ]

[Waster]

Ik heb net gekeken in het starterspaket en tools pakket. Geladen in mijn java ide, zowel netbeans als eclipse. Beide geven 15 files met erros aan ofzo. Is het niet de bedoeling om tools directory in je src directory te hebben?

[H!GHGuY]

Ik merk net dat ik in de T.net ranglijst 2de sta... Ik moet zelfs nog beginnen met een degelijke strategie implementeren... Komaan jongens, ik had wel wat meer tegenstand verwacht als ik naar de voorbije contests keek.

[SaphuA]

.

[ Voor 120% gewijzigd door SaphuA op 31-01-2022 15:56 ]

[Bolukan]

D-Raven schreef op vrijdag 11 november 2011 @ 08:47:
[...]
Nice gedaan hoor Wat gebruik je nu? Diffusion ?

Ik gebruik FoodSmell, EnemyHillSmell en MyHill (verder is beter). Maar dat laatste werkt niet goed. Ik ga daar UnknownSmell/UnseenSmell van maken.

@Deathraven: Ik doe nog niets met enemy ants. Ik zou het meer doen om ze te doden/ontwijken, dan de enemy hill te vinden. Ik zit alleen nog met de methode hoe ik 2-1 situaties creëer of mee omga. Anders gezegd: micro-gevechten coordineren. Iemand ideeën?

SaphuA schreef op vrijdag 11 november 2011 @ 09:54:
Dit werkt wel als ik mijn bot debug, maar niet als ik hem gewoon run.
Is dit by design?

Als je hem lokaal test, lukt het mij om images te maken, dus los van debug-state

[ Voor 46% gewijzigd door Bolukan op 11-11-2011 10:07 ]

[D-Raven]

Doe je ook iets met enemy ants? In mijn mening een goed hulpmiddel om op nog niet ontdekte posities te komen, en om je kans te verhogen om de EnemyHill te vinden.

Ik ben momenteel ook met target priorities aan het werken, door middel van gewichten, max ant per target en target ranges laat ik mijn mieren nu automatisch zijn doel kiezen. Werkt als een trein, alleen ben wel veel aan het itereren om de gewichten en ranges goed te krijgen.

[ Voor 46% gewijzigd door D-Raven op 11-11-2011 10:04 ]

[Sjaaky]

H!GHGuY schreef op vrijdag 11 november 2011 @ 09:16:
Ik moet zelfs nog beginnen met een degelijke strategie implementeren...

Voor mij geld hetzelfde. Ik heb diffusion geimplementeerd. Hoge scores voor enemyhills en voedsel. Een kleine score voor land dat in de huidige turn niet zichtbaar is. En een kleine negatieve penalty voor tegenstanders, zodat er een ontwijk gedrag ontstaat. Daar zit nog wel een bug in. Vooral in doolhoven is dat zichtbaar. De score van een plek waar een eigen mier op staat is geclamped op 0. Als er een tegenstander langsloopt dan freezen al mijn mieren omdat de omgeving negatief wordt. Het heeft me af en toe geholpen, maar het was niet helemaal hoe het bedacht was.

Diffusion wordt nu hooguit 5x per turn gedaan. Deze verhogen levert al veel beter gedrag op. (Dan blijft de geur minder lang hangen ).
De winst gaat zitten in het implementeren van:
- Stuur x% van de mieren op een enemy hill af.
- Verdedig de eigen hill.
- ant2ant combat.
Want dat zit er nu allemaal niet in.

[Koopmans]

Kijk eens naar deze replay, een epic battle om de hill vanaf turn 650. En geholpen door een timeout toch nog een gedeelde 1e plek.

Is overigens niet mijn bot, maar de huidige nederlandse nr 1.

[Arjan]

Sjaaky schreef op vrijdag 11 november 2011 @ 10:14:
[...]


Voor mij geld hetzelfde. Ik heb diffusion geimplementeerd. Hoge scores voor enemyhills en voedsel. Een kleine score voor land dat in de huidige turn niet zichtbaar is. En een kleine negatieve penalty voor tegenstanders, zodat er een ontwijk gedrag ontstaat. Daar zit nog wel een bug in. Vooral in doolhoven is dat zichtbaar. De score van een plek waar een eigen mier op staat is geclamped op 0. Als er een tegenstander langsloopt dan freezen al mijn mieren omdat de omgeving negatief wordt. Het heeft me af en toe geholpen, maar het was niet helemaal hoe het bedacht was.

Diffusion wordt nu hooguit 5x per turn gedaan. Deze verhogen levert al veel beter gedrag op. (Dan blijft de geur minder lang hangen ).
De winst gaat zitten in het implementeren van:
- Stuur x% van de mieren op een enemy hill af.
- Verdedig de eigen hill.
- ant2ant combat.
Want dat zit er nu allemaal niet in.

Grappig, heb precies hetzelfde ( niet precies hetzelfde, bij mij blijft de 'geur' nooit hangen )

Jammer dat de gifs van de heatmap zo groot worden, anders kon ik eens een verloopje posten van hoe mijn ants hun weg vinden, is best leuk om te zien

[Sjaaky]

Arjan schreef op vrijdag 11 november 2011 @ 10:59:
[...]
Jammer dat de gifs van de heatmap zo groot worden, anders kon ik eens een verloopje posten van hoe mijn ants hun weg vinden, is best leuk om te zien

Met ffmpeg is daar makkelijk een filmpje van te maken. Gezien je sig weet je daar vast meer van .

[Arjan]

jup, maar die zien er vrij nasty uit, aangezien er weinig pixels inzitten en de chroma-subsampling niet veel heel laat van de kleurtjes
Om dat te fixen zou ik de bitmaps eerst moeten resizen zonder interpolatie en daarna aan ffmpeg moeten voeren, waarna ik 'm op youtube kan zetten.. </veel_werk_maar_wie_weet>

[Verwijderd]

Bak er een Wikipedia: APNG van.

[SaphuA]

.

[ Voor 99% gewijzigd door SaphuA op 31-01-2022 15:56 ]

[H!GHGuY]

Sjaaky schreef op vrijdag 11 november 2011 @ 10:14:
[...]
Voor mij geld hetzelfde. Ik heb diffusion geimplementeerd. Hoge scores voor enemyhills en voedsel. Een kleine score voor land dat in de huidige turn niet zichtbaar is. En een kleine negatieve penalty voor tegenstanders, zodat er een ontwijk gedrag ontstaat. Daar zit nog wel een bug in. Vooral in doolhoven is dat zichtbaar. De score van een plek waar een eigen mier op staat is geclamped op 0. Als er een tegenstander langsloopt dan freezen al mijn mieren omdat de omgeving negatief wordt. Het heeft me af en toe geholpen, maar het was niet helemaal hoe het bedacht was.

Ik heb verschillende goals, elk met een diffusion map. Het echte AI zit hem dan in:
- kiezen van de juiste goals
- kiezen van de juiste scent/diffusion/collaboration waarden
- goal selection per ant

Diffusion wordt nu hooguit 5x per turn gedaan. Deze verhogen levert al veel beter gedrag op. (Dan blijft de geur minder lang hangen ).
De winst gaat zitten in het implementeren van:
- Stuur x% van de mieren op een enemy hill af.
- Verdedig de eigen hill.
- ant2ant combat.
Want dat zit er nu allemaal niet in.

Ik update de eerste ronde tot de tijd op is. Volgende rondes doe ik 3 iteraties. Ik moet nog verder experimenteren met andere waardes.

SaphuA schreef op vrijdag 11 november 2011 @ 11:48:
Even een paar vraagjes die zo te binnen schieten. Misschien dat ik toch een poging ga wagen voor de fun
- Hoe checken jullie of items die uit het zicht gaan er uberhaupt nog wel staan zodra ze weer in zicht zijn?

Niet. De scent met een diffusion map blijft nog wel even hangen.

- Wat heb je aan dead ant informatie?

Niets. Wordt genegeerd.

- Hoe verdelen jullie de ants bij gebruik met zo'n diffusion map? (Lijkt me toch een betere oplossing dan die waypoints waar ik eerder over schreef)

Niet. Door de juiste goals, verspreiden ze zich vanzelf.


Net een nieuwe versie geupload die volgens mij best een stukje verbeterd is... Ants verspreiden zich beter en vinden dus ook meer voedsel. Ik heb ook al de fundamenten om te beslissen of ik een gevecht moet aangaan of niet.

[ Voor 25% gewijzigd door H!GHGuY op 11-11-2011 12:18 ]

[SaphuA]

.

[ Voor 130% gewijzigd door SaphuA op 31-01-2022 15:56 ]

[Verwijderd]

SaphuA schreef op vrijdag 11 november 2011 @ 15:12:
Haha, geweldig Net even de meest eenvoudige diffuse oplossing geimplementeerd in de starter package en mijn miertjes rennen er op los! Nou heb ik iig een bot gesubmit die niet gelijk crashed

Next:
- Zorgen dat ze elkaar niet kapot rennen.
- Betere verdeling van de miertjes.

Zal vanavond wat screenshotjes plaatsen van de diffuse map voor de geinteresseerden.

Meer kennis is altijd leuk, ik ben benieuwd...

Wie van jullie publiceert hun code na de challenge?

Ik ben wel van plan de code iig ergens te plaatsen.
Zorgen dat er overal goede uitleg staat en dat alles netjes opgepoetst is, dan heeft de challenge ook echt meerwaarde voor de gemeenschap.

[Sh4wn]

Ik heb mijn code op dit moment in een private BitBucket repo staan, na de challenge geef ik hem uiteraard vrij

[D-Raven]

Ik geef m ook wel vrij. Als ik m niet klaar krijg voor t einde van de challenge ga ik m sowieso afmaken. Me wants flocking behavior

Kan ook overstappen op diffusion maps, maar dat voelt als vals spelen Ben nu al zover met A*, ga ik t ook afmaken ook

[Verwijderd]

D-Raven schreef op vrijdag 11 november 2011 @ 16:37:
Ik geef m ook wel vrij. Als ik m niet klaar krijg voor t einde van de challenge ga ik m sowieso afmaken. Me wants flocking behavior

Kan ook overstappen op diffusion maps, maar dat voelt als vals spelen Ben nu al zover met A*, ga ik t ook afmaken ook

Ik heb A* in Python helemaal uitgewerkt, functioneerde ook echt effectief... Tot je meer dan 35/40 ants had... Dan werd het simpelweg te traag...

Daarom diffusion er nu bij, schaalt veel beter naar meer ants...

[D-Raven]

Mijn bot heeft al succesvol tot 300+ ants aan kunnen sturen voordat hij een timeout gaf. Dus ik weet niet wat je doet, maar je hebt nogal wat winst te behalen.

Wellicht een stomme opmerking maar: Als een mier eenmaal een pad berekend heeft, dan kun je hem dat pad af laten lopen totdat ie klaar is, je gaat toch niet elke beurt opnieuw een volledig pad berekenen?

[Verwijderd]

D-Raven schreef op vrijdag 11 november 2011 @ 17:18:
Mijn bot heeft al succesvol tot 300+ ants aan kunnen sturen voordat hij een timeout gaf. Dus ik weet niet wat je doet, maar je hebt nogal wat winst te behalen.

Wellicht een stomme opmerking maar: Als een mier eenmaal een pad berekend heeft, dan kun je hem dat pad af laten lopen totdat ie klaar is, je gaat toch niet elke beurt opnieuw een volledig pad berekenen?

Ik weet wel waarom ie te traag was, dat lag niet aan het pathfinding algoritme...

Maar aan het feit dat voor elke mier elke ronde opnieuw de afstand naar alle foods, enemyants en enemyhills berekend werdt... Op basis daarvan werd een keuze gemaakt welke het interresantste was en daar werd dan een pad voor berekend... Elke ronde opnieuw...
Als een pad dan eenmaal berekend was werdt dat opgeslagen, als het pad dan 50 keer gebruikt was werdt het pad weggegooid en opnieuw berekend om eventueel een optimaler pad te vinden...

Dus het lag ook echt niet aan A* algoritme, dat werkte in ongeveer 1 tot 2 msec

Het lag aan de logica erachter...

Echter ICM met strikte timeremaining monitoring en random moves als er weinig tijd meer over was heeft er wel voor gezorgd dat ik nu in de top1150 sta... Niet echt verkeerd dus... Het grote voordeel van die randommoves was dat je makkelijk 1500 ants en 50.000 turns kon draaien zonder timeouts

Ik ben nu een hybride strategie aan het schrijven waarbij zowel A* als CD gebruikt wordt...

[ Voor 16% gewijzigd door Verwijderd op 11-11-2011 18:11 ]

[D-Raven]

Verwijderd schreef op vrijdag 11 november 2011 @ 17:32:
[...]


Ik weet wel waarom ie te traag was, dat lag niet aan het pathfinding algoritme...

Maar aan het feit dat voor elke mier elke ronde opnieuw de afstand naar alle foods, enemyants en enemyhills berekend werdt... Op basis daarvan werd een keuze gemaakt welke het interresantste was en daar werd dan een pad voor berekend... Elke ronde opnieuw...

..

Dat doe ik in een nieuwe versie van mijn bot nu ook. Moet nog blijken hoe goed dat schaalt.. Maar ik ga er vanuit dat ik nooit in een ronde voor al mijn mieren een doel hoef te bepalen. Als het goed is zijn de meeste mieren onderweg, en zijn er elke beurt maar een paar waar een doel voor bepaald moet worden..
Maargoed, ik wil uiteindelijk ook gedrag inbouwen dat als hij onderweg is, en er een vijandige mier in de buurt is, er bepaalt wordt wat het threat level is, en op basis daarvan wordt het pad afgebroken, of wordt de vijand genegeerd.
Maar dat kan je weer versimpelen door alleen binnen de viewradius van je mier naar vijandige mieren te zoeken en de threat level te bepalen a.d.v hoeveel vijandige mieren er in je viewradius zitten t.o.v vriendelijke mieren.
Ja dit soort dingen zijn makkelijker (bijna automatisch) met diffusie, maar ik ben nu eenmaal graag eigenwijs. Al zou een hybride oplossing waarbij diffusie puur voor battle scenario's gebruikt wordt nog een uitkomst zijn... [/random thoughts]

Dus het lag ook echt niet aan A* algoritme, dat werkte in ongeveer 1 tot 2 msec

Ook indien je in een van de grotere maze levels zit? Want juist daar is A* in het nadeel..
Aggresief caching van je paden is in die levels een uitkomst...

[ Voor 8% gewijzigd door D-Raven op 11-11-2011 18:37 ]

[Verwijderd]

Verwijderd schreef op vrijdag 11 november 2011 @ 17:32:
Echter ICM met strikte timeremaining monitoring en random moves als er weinig tijd meer over was heeft er wel voor gezorgd dat ik nu in de top1150 sta... Niet echt verkeerd dus... Het grote voordeel van die randommoves was dat je makkelijk 1500 ants en 50.000 turns kon draaien zonder timeouts

Iemand bij mij op het werk staat 500 zonder überhaubt een fatsoenlijke vorm van pathfinding...

[Verwijderd]

D-Raven schreef op vrijdag 11 november 2011 @ 18:35:
[...]

Dat doe ik in een nieuwe versie van mijn bot nu ook. Moet nog blijken hoe goed dat schaalt.. Maar ik ga er vanuit dat ik nooit in een ronde voor al mijn mieren een doel hoef te bepalen. Als het goed is zijn de meeste mieren onderweg, en zijn er elke beurt maar een paar waar een doel voor bepaald moet worden..
Maargoed, ik wil uiteindelijk ook gedrag inbouwen dat als hij onderweg is, en er een vijandige mier in de buurt is, er bepaalt wordt wat het threat level is, en op basis daarvan wordt het pad afgebroken, of wordt de vijand genegeerd.
Maar dat kan je weer versimpelen door alleen binnen de viewradius van je mier naar vijandige mieren te zoeken en de threat level te bepalen a.d.v hoeveel vijandige mieren er in je viewradius zitten t.o.v vriendelijke mieren.
Ja dit soort dingen zijn makkelijker (bijna automatisch) met diffusie, maar ik ben nu eenmaal graag eigenwijs. Al zou een hybride oplossing waarbij diffusie puur voor battle scenario's gebruikt wordt nog een uitkomst zijn... \[/random thoughts]

Ja eigenlijk moet je bij A* wel de orders bijhouden voor elke ant en de berekeningen per ronde minimaliseren op die manier...

[b]Deathraven schreef op vrijdag 11 november 2011 @ 18:35:
Ook indien je in een van de grotere maze levels zit? Want juist daar is A* in het nadeel..
Aggresief caching van je paden is in die levels een uitkomst...

Een onderdeel van het optimalisatie om de tijd overal zo kort mogelijk te houden was maximaal 200 runs diep doen in het A* algoritme... Dit zorgde ervoor dat de paden langer dan ongeveer 15 steps niet meer berekend werden...

Daardoor bleef A* overal zo'n beetje wel even effectief...

Al denk ik niet dat die beperking echt nodig is, als ik het CD gedeelte helemaal uitgewerkt heb zal ik nog eens goed gaan kijken naar het A* algoritme...

Echter, voor iemand die nog nooit met AI gewerkt heeft, nog nooit een regel Python geschreven heeft en eigenlijk amper ooit iets programmeerd ben ik best tevreden met de resultaten tot nu toe...

[Arjan]

heb de moeite genomen om een filmpje van een simpele run te maken:

Wat u ziet:

rood: points of interest
groene waas: aantrekkelijk voor mijn mieren
rode waas: onaantrekkelijk ( dit geldt alleen voor de waas, de 100% rode plekken zijn points of interest )

Je ziet dus geen mieren / food oid. Al is het niet moeilijk om de hils / food af te leiden uit de beelden

Ik heb trouwens een beetje problemen met het inzichtelijk maken van mijn heatmap. de 255 waarden die ik nu gebruik zijn bij lange na niet genoeg om een goed beeld te geven van het contrast, iemand enig idee of er een makkelijk te ondersteunen / visualiseren floating point bitmap formaat bestaat?

[ Voor 25% gewijzigd door Arjan op 11-11-2011 21:17 ]

[Sjaaky]

Arjan schreef op vrijdag 11 november 2011 @ 21:15:
Ik heb trouwens een beetje problemen met het inzichtelijk maken van mijn heatmap. de 255 waarden die ik nu gebruik zijn bij lange na niet genoeg om een goed beeld te geven van het contrast, iemand enig idee of er een makkelijk te ondersteunen / visualiseren floating point bitmap formaat bestaat?

Om een range van [0, maxScore] weer te geven gebruik ik onderstaande code. maxScore is de maximale waarde die GetFoodScore teruggeeft en vast, dus colorscalefactor hoeft maar 1x te berekend te worden (en mag geen 0 zijn).

C#:

double colorscalefactor = (255 / Math.Log(maxScore + 1.0));

double foodscore = Math.Log(state.GetFoodScore(r, c) + 1.0) * colorscalefactor;
int ifoodscore = Math.Min(Math.Max((int)(foodscore), 0), 255);

Color food = Color.FromArgb(ifoodscore, ifoodscore, ifoodscore);

edit: Oh wacht, dit had ik al gepost... Maar je kunt die 255 uitbreiden door door een hele regenboog van kleuren heen te gaan.

[ Voor 6% gewijzigd door Sjaaky op 11-11-2011 22:21 ]

[D-Raven]

Verwijderd schreef op vrijdag 11 november 2011 @ 18:50:
Een onderdeel van het optimalisatie om de tijd overal zo kort mogelijk te houden was maximaal 200 runs diep doen in het A* algoritme... Dit zorgde ervoor dat de paden langer dan ongeveer 15 steps niet meer berekend werden...

Daardoor bleef A* overal zo'n beetje wel even effectief...

Al denk ik niet dat die beperking echt nodig is, als ik het CD gedeelte helemaal uitgewerkt heb zal ik nog eens goed gaan kijken naar het A* algoritme...

Dit doe ik in mijn huidige online versie ook. Al pas ik de restrictie wat anders toe. Of die beperking wel of niet nodig is hangt helemaal af van hoe je met je routes omgaat. Als je deze eenmaal berekende paths cached, dan is het te overzien. Maar het probleem daarvan is dat je dynamische invloeden niet kunt meenemen, nouja kan wel, maar dan loop je de kans dat je paden sub-optimaal zijn. Een klein beetje is niet erg, maar kan soms wel _net_ het verschil betekenen..

[Bolukan]

@Soultaker, ik vind je mooie patronen maken. Is het de aantrekkingskracht van de hill gecombineerd met afstoting ten opzichte van een ideale afstand tussen de ants?

[Corniel]

Pff, ik ben gisterenavond bezig geweest om een bug te vinden die er voor zorgt dat het door mij bedachte verdedigingsmechanisme niet werkt. NIets gevonden tot zover...

Gelukkig gaat het door doolhof-mapjes heelnbewegen wel aardig. Nu hard door proggen om Sjaakie te verslaan.

[D-Three]

Fantastisch!! Altijd al eens willen mee doen aan zoiets. Maar rot wanneer kan je hieraan mee doen? Ik kan namelijk nergens een datum vinden en op dit moment heb ik er bitter weinig tijd voor.

[Matis]

Laagvliegerke schreef op zaterdag 12 november 2011 @ 09:49:
Fantastisch!! Altijd al eens willen mee doen aan zoiets. Maar rot wanneer kan je hieraan mee doen? Ik kan namelijk nergens een datum vinden en op dit moment heb ik er bitter weinig tijd voor.

quote: http://aichallenge.org/index.php

(onderaan)
The current phase of the contest will end December 18th at 11:59pm EST. At that time submissions will be closed. Shortly thereafter the final tournament will be started. The length of the final tournament has not yet been determined but is expected to last less than one week. Upon completion the contest winner will be announced and all results will be publically available.

[Verwijderd]

Heel interessant, jammer dat er nog maar zo weinig tijd over is. De starter kits vindt ik maar vaag en zeker die van Ruby. Denk ook dat ik zoals Soultaker gewoon met input/output ga werken in ruby.

Maar wat ik nu niet zo goed snap: Hoe houden jullie al die ants uit elkaar? Geven jullie elke ant een id? Of anders?

[D-Raven]

Godver. Mijn bot build lokaal prima, komt door testgame heen. Maar zodra ik m ga uploaden komt hij niet meer door de testgame heen. Ook lekker duidelijk, niet eens een foutmelding van waarom dan niet.. grrr.

[Matis]

Windows / Unix afhankelijkheden? Externe libraries?

Welke taal heb je?

[D-Raven]

c# compiled op .Net 3.5 daarnet mijn project helemaal opnieuw aangemaakt, opnieuw files toegevoegd en nu krijg ik in ieder geval geen foutmelding meer... neej.. nu krijg ik een timeout in turn 1 (wtf ??!?!)

Ok de eerste beurt initialiseer ik wat initial state. Dat duurt alles bij elkaar 60 ms. turn time is default 500ms. Dus dit zou geen probleem moeten zijn...

Enigste wat ik nu nog kan bedenken is dat er iets in release mode niet goed gaat. Dus dat ga ik nu maar even proberen..

Ok in release mode crashed hij hier ook.. stom dat ik dat niet eerder had getest

edit: gevonden, gefixed en "ready to play"

[ Voor 11% gewijzigd door D-Raven op 12-11-2011 11:47 ]

[Corniel]

D-Raven schreef op zaterdag 12 november 2011 @ 11:25:
Mijn bot build lokaal prima, komt door testgame heen. Maar zodra ik m ga uploaden komt hij niet meer door de testgame heen (..)

Heb ik ook gehad. Bij was het dat ik niet overweg kon met een (long) seed. Daarna als een zonnetje. Hopelijk ook voor jou.

(Gelukkig eindelijk mn bug gevonden... Tss hele avond niets nuttigs gedaan nu)

[Verwijderd]

De hybride strategie met A* en CD gecombineerd gaat zo zijn eerste wedstrijd spelen... Weinig tijd gehad om te testen dus maar hopen dat er geen buggs inzitten...

Ik ben benieuwd

[Janoz]

Zo, maar even een nieuwe versie geupload. Eigenlijk zijn de enige verbeteringen een aanpassing in het uitzoeken van de bewegingen waardoor alle ants veel dichter op elkaar kunnen bewegen. Daarnaast heb ik nog wat rudimentaire gedragsveranderingen doorgevoerd op basis van hoe ver de game al is, maar dat zal in de replay wel duidelijk zichtbaar worden (hoop ik).

[Waster]

Zou iemand mij kunnen helpen hoe ik zo'n programma als dit nou het beste kan debuggen. Ik heb nogal wat veranderingen toegepast en er blijkt ergens een runtime error op te treden. Ik zal wel iets vergeten zijn te initialiseren, maar ik kan er maar niet achter komen wat.

Ik heb namelijk geen flauw idee wat mijn programma en de playgame.py nou eigenlijk met elkaar communiceren.