Google ai challenge 2011

[317070]

De Logger start niet, en de bot crasht bij het compilen. Anyway, de bot die je nu reeds hebt geschreven, bevat geen bijdrage van mij, dus ik ga er braaf afblijven Jij hebt al het werk eraan gedaan.

Kun je posten wat er misgaat bij het compilen?

En voor mij hoef je er helemaal niet af te blijven, als je de code momenteel niet verstaat, vraag maar raak of ik ga dan wel wat meer documentatie schrijven. Dat er nog geen code van jou inzit komt omdat je nog niet gecommit hebt?

Edit: je hebt clean&rebuild gebruikt na het updaten?

Edit2: ik heb net een foutje uit de logger gevist die zorgde dat hij crashte als hij geen logfile had dat verklaart een deel van het probleem waarschijnlijk...

Edit3: nu is suicide compleet onmogelijk.

Edit4: een kleine bug opgelost als een Ant echt onmogelijk gelijk welk pad kon reserveren, zelfs niet kon stilstaan. Nu geraakt de code ook weer door de testen op de officiële site. Suicide is nu dus ook een ietsiepietsie mogelijk, maar screw that...

[Arai]

Danku voor het aanbod! Maar ik denk dat ik toch maar beter zelf eens iets probeer in ruby. Heb wel een paar probleempjes met de simulator op mijn linux machine, maar daar geraak ik wel uit.

Ik heb naar een paar test spelletjes van jullie bot gekeken. En dat ziet er super goed uit. Door de spreiding hebben grote groepen mieren van de vijand bijna geen nut. En je hebt vlug een groot deel van de oppervlakte bedekt.

[In physics I trust]

@317070: Dit is geschreven door het compile-script. Als je dit leest is de logger nooit gestart. En ja, ik heb clean en build gedaan...

En ik versta je code wel (al zou ik ze niet zomaar zelf uit mijn mouw kunnen schudden )

Vreemd overigens, want je gesubmitte versie slaagt er duidelijk wel in te compilen. overigens vreemd dat die (voorlopig) lager scoort?

En verder @317070: ik ben intussen nog aan het experimenteren met een snake-achtige bot. Al denk ik niet dat dat optimaal kan worden aangewend. Als het op iets trekt, maak ik wel een Mybot2.java file aan Kan je er - indien het je iets lijkt - ook eens naar kijken.

@Arai: indien je het op Linux (Ubuntu? Mint? Slackware? Fedora? ...) niet aan de praat kijkt, wil ik er ook wel eens naar kijken.

[317070]

Die formaties lijken nu wel al min of meer te gaan lukken Die dingen zijn nog verdomd veel moeilijker dan je eerst zou denken. De mieren mogen elkaar niet platlopen, je moet zorgen dat alle mieren op hun plaats komen en dat liefst nog min of meer efficiënt, dat andere mieren die niets van de formatie afweten niet alles overhoop lopen en dat ze mooi allemaal synchroon bewegen zodat iedereen meekan en indien nodig de formatie ook hersteld wordt.



En ik wil gerust je code bekijken. Dat van die fout die je hebt weet ik ook niet, heeft java wel write-permission naar de logfile? Dat probleem ben ik eigenlijk nog niet tegengekomen, ik heb die tekst daar geplaatst om een eigen probleem te onderzoeken, maar het bleek iets anders te zijn.

Overigens, de reden dat hij verslechterd is, is omdat ik nog niet naar tactiek aan het kijken ben. Ik probeer eerst de structuur voor een algemene AI in orde te krijgen om dan aan de tactiek te kunnen werken, eenmaal de regels vastliggen.

[317070]

Jups, dat lijkt nog goed te lukken met die formaties. Vooral als je in defensieve positie zit kun je er sterk mee terugkomen.

Nu nog eens kijken hoe ik ze "in vijandelijk gebied" kan sturen, want nu lummelen ze maar wat rond achter de dichtste vijand, en dat werkt niet zo goed.

In ieder geval, als iemand eens wil bewonderen hoe mooi de formaties door fijne openingen stromen, of zelfs door elkaar: http://ants.zeroviz.us/cS5Wb/

Verder heb ik zelfmoord compleet onmogelijk gemaakt, zelfs in situaties als de volgende waarin alle ants a een pad naar rechts hebben, en ant b geen pad gekregen heeft, wordt de situatie volledig opgelost en blijft iedereen stilstaan!

Code: Selecteer alles

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

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab*

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

[Arai]

Oplossing voor mijn probleem gevonden op Ubuntu. Met de tools map van https://github.com/aichallenge/aichallenge/tree/epsilon/ants lukte het wel!

Later vanavond eens beginnen in Ruby of PHP. Maar eerst moet ik nog wat echt programmeer werk afwerken

[In physics I trust]

Allereerst: je bot levert heel mooie resultaten, 317070! Knap werk!

Ten tweede: ik loop vast op iets heel vreemds: ik heb in bijlage het java-bestandje gezet, geen zorgen, het is geen uitgebreide code.

Waar ik niet uit geraak is de reden waarom

Code: Selecteer alles

List<Ant> thisant=GameData.getMyAnts();

   if( thisant.size()>0){

Snake MainSnake = new Snake((thisant.get(0)));

MainSnake.move();

   }

een crash oplevert als ik er >= 0 van maak.

Dat zou immers betekenen dat GameData.getMyAnts(); een lege lijst oplevert. Weet jij waarom?

MyBot2

(1.36 KiB) 101 keer gedownload

Als je geen tijd/zin hebt, moet je er niet naar kijken hoor.

[Cycloon]

Ik ken de code niet, maar ik vermoed dat de move actie er vanuit zal gaan dat er op zijn minst 1 ant aanwezig is en dus faalt als dit niet zo is.

Maar de reden dat ik deze post maak: Als die if daar staat en als de code binnenin de methods daarin faalt dan staat die conditie op de verkeerde plaats. Als er toch bepaalde precondities zijn die niet binnen de method afgedwongen kunnen worden dan is het nog zo mooi om daar een duidelijke exceptie over te geven. Dit maakt het makkelijker voor andere die met je code moeten werken om problemen zelf op te lossen. Zie dit als een nuttige tip die in alle projecten handig is. Het lijkt een zware investering, maar goede foutafhandeling is een zéér groot voordeel in een teamproject.

Tot hoe lang loopt de contest eigenlijk? Anders ga ik mogelijks volgende week ook eens de handen uit de mouwen steken

[317070]

Dat zou immers betekenen dat GameData.getMyAnts(); een lege lijst oplevert. Weet jij waarom?

Ik mis de klasse Snake om echt het probleem te zien.

Maar de eerste beurt draait de code zonder 1 enkele ant. (op een lege map) Dit was zo in de startersbot, en dit heb ik er niet uitgehaald omdat dit bij goede code niet zou mogen uitmaken. Je weet namelijk niet met hoeveel ants gestart wordt en of die überhaupt wel kunnen bewegen of elkaar kunnen bereiken.(zoals op de testmap getest wordt) Ook zou hij anders crashen op het moment dat de bot verloren is.

Maar ik heb me al geërgerd aan het protocol dat ze bedacht hebben. Zo wordt de laatste beurt van een spelletje 2x gespeeld wat mij ook al een uurtje zoekwerk geleverd heeft over waarom dat dat ding vastliep... er wordt letterlijk aan de bot doorgegeven van "speel nu turn 165", de bot geeft door wat hij wil doen, die ouput wordt genegeerd, hetzelfde spelbord wordt doorgegeven en dan opnieuw "speel nu turn 165". Natuurlijk sloeg de AI compleet in verwarring want dat is niet wat ze verwachtte.

Verder...

Ik zit met een probleem, eigenlijk. Ik hoop dat je er nog geen last van gehad hebt, maar de formationcode die er nu in zit kan time-outen omdat de path-finding veel te complex kan worden om binnen die seconde uit te rekenen. Daar weet ik wel een oplossing voor, maar eigenlijk is dit een symptoom van een architectuurprobleempje.

Op dit moment wordt iedere mier een object, terwijl alle mieren eigenlijk volledig equivalent zijn op hun positie na. Vanuit architectuurstandpunt was het eigenlijk niet goed om de mieren als apart te beschouwen, als mier A naar punt B wil, en mier B naar punt A, dan kunnen ze beter allebei stilstaan.

Maar, ik ken geen enkel goed algoritme dat zo een probleem oplost. Je hebt x doelen en y mieren, hoe bepaal je (heuristisch en efficiënt, niet fullblown bruteforcen) een goede manier om met de mieren de doelen te bereiken? Je kunt het ergens zien als maximum flow probleem met meerdere sources en drains, maar daar ken ik geen enkele goede heuristiek bij, en ik kan er ook geen bedenken... als er iemand iets weet of kan bedenken...

In ieder geval, mijn volgende stap zal zijn om eens een "mapping" algoritme te bouwen, waarbij ruimte wordt ingedeeld in subruimtes in subruimtes, enz. in een soort boom. Zo zou je dan kunnen zeggen welke speler welke ruimte 'controleert', wat kan helpen bij intelligentere aanvallen, en het zou zo moeten lukken om wat intelligenter de formaties te bewegen om alles weer in milliseconden te kunnen uitrekenen. Bovendien kunnen we daarmee A# i.p.v. A* gebruiken, wat efficiënter (maar moeilijker) is.

[Xenion]

Je kunt het ergens zien als maximum flow probleem met meerdere sources en drains, maar daar ken ik geen enkele goede heuristiek bij, en ik kan er ook geen bedenken... als er iemand iets weet of kan bedenken...

Wegens tijdsgebrek en het feit dat AI mijn vakgebied niet is (slechts een inleidende cursus gehad) neem ik niet deel aan dit project, maar uit interesse lees ik dit topic wel af en toe.

Snel googlen leer mij het volgende:

Een multi-source multi-drain maximum flow probleem kan gereduceerd worden naar een 'gewoon' maximum flow probleem en dan kan je de gebruikelijke technieken gebruiken.

reductie (wikipedia)

Wat betreft de mieren:

Een andere optie die ik intuïtief zie ik van ze te verdelen in kolonies. Een kolonie bestaat dan uit een aantal mieren en een 'middelpunt'. Er moet ook een methode bestaan om een kolonie te kunnen opsplitsen in 2. Misschien kunnen kolonies ook 'aanvallend' of 'verzamelend' ingesteld worden (dit heeft dan waarschijnlijk invloed op de formatie die ze aanneemt). Ik heb niks van code bekeken, dus ik weet niet of dit efficiënt zou kunnen geïmplementeerd worden.

[317070]

Snel googlen leer mij het volgende:

Een multi-source multi-drain maximum flow probleem kan gereduceerd worden naar een 'gewoon' maximum flow probleem en dan kan je de gebruikelijke technieken gebruiken.

Inderdaad, maar ken je een goede heuristiek? Want de graaf bevat ongeveer 100tiles x 100tiles x 100beurten vertices.

[Xenion]

Inderdaad, maar ken je een goede heuristiek? Want de graaf bevat ongeveer 100tiles x 100tiles x 100beurten vertices.

Helaas niet, zoals gezegd is mijn AI kennis zeer beperkt.

Mag ik vragen welke specialisatie jij volgt? Ik vermoed dat je Ingenieur studeert in Gent?

[Cycloon]

Inderdaad, maar ken je een goede heuristiek? Want de graaf bevat ongeveer 100tiles x 100tiles x 100beurten vertices.

Dit los je best ook niet op met een graaf omdat die veel te dicht is. Er zijn dan wel andere voorstellingen te vinden die minder geheugen vragen en makkelijker te verwerken zijn.

[317070]

Mag ik vragen welke specialisatie jij volgt? Ik vermoed dat je Ingenieur studeert in Gent?

Burgerlijk ingenieur elektrotechniek keuzerichting ICT, maar ik zie dat eerder als een aanvulling op mijn kennis in de informatica. Programmeren is iets dat ik gewoon echt graag doe, vooral van robotica en AI.

Dit los je best ook niet op met een graaf omdat die veel te dicht is. Er zijn dan wel andere voorstellingen te vinden die minder geheugen vragen en makkelijker te verwerken zijn.

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?

[Xenion]

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

Als je er niks beters op vindt dan biedt het 2de deel van mijn post misschien een oplossing. Als je een kolonie naar een voedsel-tegel kan leiden, dan heb je aanzienlijk minder paden te onderzoeken.

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

Je bent blijkbaar graag bezig met deze zaken, hoe komt het dat je geen Computerwetenschappen met specialisatie in de AI hebt gekozen?