Google ai challenge 2011

[Arai]

AI heeft me al altijd mateloos geïnteresseerd en dit soort wedstrijden zeker. Heb al heel wat vraagstukken op bijvoorbeeld Project Euler opgelost dus een kleine basis heb ik volgens mij wel. Alleen denk ik niet dat ik het niveau kan halen van bovenstaande gebruikers. Maar moesten jullie toch nog iemand nodig hebben, ik wil gerust eens wat proberen.

[317070]

AI heeft me al altijd mateloos geïnteresseerd en dit soort wedstrijden zeker. Heb al heel wat vraagstukken op bijvoorbeeld Project Euler opgelost dus een kleine basis heb ik volgens mij wel. Alleen denk ik niet dat ik het niveau kan halen van bovenstaande gebruikers. Maar moesten jullie toch nog iemand nodig hebben, ik wil gerust eens wat proberen.

Proberen is geen probleem, je kunt nu al perfect onze code binnenhalen en lokaal eens kijken of het je zou lukken. Als je wil meehelpen, stuur me een PM met je gmail-adres, dan kan ik je ook de toestemming geven om code te committen.

Moest het toch te moeilijk zijn, je kan nog altijd beginnen van de starterspakketten die ze zelf aanbieden op http://aichallengebeta.hypertriangle.com/s...er_packages.php

Ik heb nog wat geprogrammeerd vandaag, en ik heb wat aangepast aan de startersbot.

1) Je hebt objecten genaamd Ants met een geheugen, die kun je paden meegeven voor meteen een aantal beurten die ze dan zo goed mogelijk afleggen.

2) Ik heb ook een shortest path geschreven met een A*-algoritme.

Nu heb ik eventjes een basisstrategie geschreven die als volgt werkt.

1) Alle ants die niet bezig zijn, kijken rond zich naar alle vakjes die binnen 10 stappen te bereiken zijn.

2) Is er ooit al een ant die naar die plaats vertrokken, dan doen we er niets mee.

3) Voor alle dingen (voedsel en vijanden) die ze gevonden hebben, wordt gekeken naar de ant zonder werk die het dichtst bij is, die wordt er naar toe gestuurd.

4) als er nog ants over zijn, dan vluchten die een stapje weg van hun dichtste buur

De resultaten kun je hier zien: http://aichallengebeta.hypertriangle.com/p...le.php?user=186

Wel kijken naar een wedstrijd van na 3h15 vandaag

[In physics I trust]

Er lijkt me iets niet te kloppen: op je profielpagina heb je alle spelletjes gewonnen vanaf de eerste turn. dat is logisch veronderstel ik omdat de tegenspelers daar vanonder in de ranking allemaal hetzelfde doen: een versie van de startersbot: iedereen is dus eerste in de spelletjes. Maar waarom wordt je bot niet uitgebracht tegen de 'hogere' bots?

Heb je trouwens ook gezien dat je 4 meest recente uploads de test cases niet haalden (en met andere woorden niet spelen)?

Want nu ik de repo heb geüpdatet, compilet de boel precies niet meer:

Updating property file: /home/glenn/NetBeansProjects/trunk/GoogleAIAnts/build/built-jar.properties

Compiling 276 source files to /home/glenn/NetBeansProjects/trunk/GoogleAIAnts/build/classes

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Aim.java:6: duplicate class: Aim

public enum Aim {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Bot.java:1: duplicate class: Bot

public interface Bot {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Ilk.java:5: duplicate class: Ilk

public enum Ilk {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Tile.java:1: duplicate class: Tile

public class Tile {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/util/EngineKill

Dus van een spelletje starten is voorlopig geen sprake bij te drukken op de run-knop.

EDIT: Als ik naar de code zelf kijk, weigert hij Ilk.ENEMY_ANT te herkennen

Dat begrijp ik niet.

[317070]

Heb je trouwens ook gezien dat je 4 meest recente uploads de test cases niet haalden (en met andere woorden niet spelen)?

Dat heb ik ook net deze ochtend gezien, ik heb de testmap eens gekopieerd om lokaal te kijken wat er misging, en er zat een fout in de shortestpath als er geen pad bestond. De versie die ik net gesubmit heb overleefd de testen wel, dus nu kan je het resultaat echt zien.

Want nu ik de repo heb geüpdatet, compilet de boel precies niet meer:

Updating property file: /home/glenn/NetBeansProjects/trunk/GoogleAIAnts/build/built-jar.properties

Compiling 276 source files to /home/glenn/NetBeansProjects/trunk/GoogleAIAnts/build/classes

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Aim.java:6: duplicate class: Aim

public enum Aim {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Bot.java:1: duplicate class: Bot

public interface Bot {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Ilk.java:5: duplicate class: Ilk

public enum Ilk {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/sample_bots/java/Tile.java:1: duplicate class: Tile

public class Tile {

/home/glenn/NetBeansProjects/trunk/GoogleAIAnts/src/util/EngineKill

Dat is waarschijnlijk omdat je nog niet gecommit hebt. De SVN ziet dus dat jij iets aangepast hebt, en ik ook, dus hij kan ze niet mergen. Die files heeft hij dus nog niet ge-updatet.

Mijn voorstel zou zijn dat je de files die je nu hebt weggooit, en gewoon opnieuw inlaad. Maar als je al iets gedaan hebt/had in de code zelf, kun je misschien proberen te mergen?

(rechtsklik->subversion->diff om de verschillen te bestuderen)

(rechtsklik->subversion->merge om samen te smelten)

[317070]

Een eerste wedstrijd

(en uiteraard gewonnen)

http://aichallengebeta.hypertriangle.com/v...186&turn=17

Het algoritme dat je hier ziet werkt als volgt:

1) Kijk rond je naar alle dingen (voedsel of vijand) die op 10 stappen van je af ligt. Doordat hij ook vijanden al voedsel beschouwt, is hij erg aggressief.

2) dingen waar al een mier naar onderweg is, of aan passeert, worden genegeerd.

3) Ga naar het ding het dichtst van jou, tenzij er een andere mier dichter is. Je volgt het pad bepaalt met een A*-algoritme, paden worden niet meer geannuleerd. Dus als een vijand weggelopen is ondertussen blijf je lopen naar waar je hem het eerst zag.

4) Heb je niets om naar toe te lopen, vlucht dan weg van je dichtste vriend.

MAAR: je kunt niet naar een vakje lopen waar je al gepasseerd bent. Zo kun je door te vluchten niet heen en weer wippen tussen een paar vakjes. Dit blijkt heel mooi gedrag op te leveren, waarmee er efficiënt verkend en verdeelt wordt over de map en mieren snel wegbewegen van plaatsen met al veel mieren.

5) Zijn er geen zo'n vakjes, neem dan een willekeurige stap.

Problemen:

soms vermoorden ze elkaar per ongeluk, er is nog geen enkele controle in die zin.

ieder mier werkt grotendeels afzonderlijk, er is nog geen 'plan'

[In physics I trust]

Super, alle foutmeldingen en dergelijke zijn verdwenen. Volgende week maar ik er dus ook werk van.Enkel het xml-documentje proberen bewerken zodat het de rechten heeft om het sh-bestand uit te voeren

Dat ze elkaar vermoorden valt eenvoudig op te lossen: een HashSet waaraan elke mier zijn locatie wordt teogevoegd tijdens een turn, geeft de verboden tiles aan voor de mieren die nog geen opdracht hebben gekregen. Ik zal het morgen implementeren.

[317070]

Ik ben aan het denken om een 'plan'-object te maken, waarmee je verschillende mieren ineens bestuurd, om een bepaald vastgelegd doel te bereiken.

Dat heeft enkele voordelen:

1) Je kunt op ieder moment verifiëren of het nog wel zinvol is wat je aan het doen bent. Nu leg je gewoon een pad af, maar wordt niet bij gehouden waarom of waarheen.

2) Je kunt corrigeren indien nodig, als je het doel weet, kun je je een pad alsnog corrigeren, zonder het gewoon volledig te moeten annuleren

3) Je kunt duidelijker kijken bij het maken van een nieuw plan of daar al geen andere mier mee bezig is. In tegenstelling van het kijken nu of er niet gewoon een mier van plan is om te passeren.

4) Je kunt een prioriteit vastleggen, zodat kleine plannen kunnen geannuleerd worden ten voordele van een groter plan.

5) Doordat een plan paden voor verschillende mieren maakt, kun je eenvoudig formaties gaan vormen en besturen.

[In physics I trust]

Mee eens, vooral aan dat laatste was ik ook aan het denken: op die manier is het eenvoudiger om geïsoleerde mieren bijvoorbeeld te vermoorden zonder er zelf mieren voor op te offeren. Maar dat is voor morgen, ik heb wel slaap nodig

[317070]

Dat ze elkaar vermoorden valt eenvoudig op te lossen: een HashSet waaraan elke mier zijn locatie wordt teogevoegd tijdens een turn, geeft de verboden tiles aan voor de mieren die nog geen opdracht hebben gekregen. Ik zal het morgen implementeren.

Het is nog niet zo simpel als je op het eerste gezicht zou denken, vrees ik

Als je een pad opstelt, dan zou je namelijk al 10 beurten eerder moeten weten dat die andere mier van jou daar op dat vakje ook binnen 10 beurten passeert. Als je zoiets echter ad hoc zou oplossen, kom je in de problemen met formaties, omdat de mieren zich niet meer aan het opgelegde traject houden en ad hoc hun trajecten aanpassen, met een complete chaos als gevolg.

Het is, voor mij althans, de bedoeling dat die paden volledig vast liggen, en dat de mieren zelf geen logica meer uitvoeren op die paden. Op die manier heb je een laag waarmee je eenvoudig kunt verder werken en redeneren. Op de laag erboven kun je dan proberen dingen te corrigeren, zoals dat mieren elkaar kruisen of dat sommige paden over water kunnen leiden.

Je zou op een gegeven moment het zo moeten kunnen maken, dat als een mier een pad heeft dat hem het water op stuurt, of hem zelfmoord doet plegen, dat hij dan gewoon crasht. De definitie van zijn laag is dan dat hij zijn pad strikt volgt, op die manier word je als programmeur verplicht om je controle op de juiste plaats uit te voeren. Bij een foutje loopt het spel direct vast, en dat kun je dan eenvoudig oplossen. Als je een structuur hebt met een heleboel ad-hoc correcties van fouten hogerop, dan kan het soms erg moeilijk debuggen zijn. Dan krijg je vreemd gedrag, maar er crasht helemaal niets en je vindt ook niet echt iets in de logger... Je ziet de chaos in de formaties, maar je weet niet goed waar ze vandaan komt, want je gaf toch de juiste paden door?

Op de laag die erop ligt heb je dan enkel nog rekening te houden met de laag daaronder, zonder rekening te moeten houden met dat de mier eventueel met originele ad hoc oplossingen komt of ad hoc oplossingen in nog verder onderliggende lagen. Die laag erboven, boven de mieren en de paden, lijkt me een 'plan'-laag. Bij het maken van het pad moet dan gekeken worden of ze elkaar niet kruisen, niet bij het afleggen van het pad zelf.

Het gaat ook, alleen moet je ergens een informatiestructuur hebben, waarbij GameData kan zeggen hoe de toekomst er uit ziet volgens de paden die er nu liggen.

Edit: en als een run niet werkt (de log file is helemaal leeg), probeer eens clean en rebuild vooraleer op run te klikken. Daar heb ik net even op zitten zoeken...

[317070]

Op 19 juli zijn er 11 van de 20 wedstrijden gewonnen, tegen gemiddeld 6,7 tegenstanders! Alle wedstrijden tegen 4 spelers of minder hebben we op 1 na allemaal gewonnen

..we zijn dus op goede weg...

[In physics I trust]

Ik heb intussen je code doorgenomen en ze zit echt knap in elkaar, ze leent zich zeker tot het eenvoudig uitbreiden van de code zonder te beginnen 'rommelen'.

Als we even op een rijtje zetten wat er aangepast zou kunnen worden, dan denk ik aan volgende zaken:

• implementatie om te vermijden dat mieren elkaar kunnen uitmoorden
• beheer van 'inwendig gebied is reeds in orde: er wordt efficiënt voor gezorgd dat het voedsel wordt verzameld
• zoeken naar voedsel gaat efficiënt, ik stel me echter de vraag of dat steeds absolute prioroteit moet hebben: een plan-object zou naar mening inderdaad moeten worden gecreëerd om niet alleen mieren samen te laten werken, maar ook een pad te kunnen annuleren
• policy aan de grenzen moet op punt worden gesteld: vijandelijke mieren als doel markeren levert ruwweg goede resultaten op, maar moet worden verfijnd: voorstel is bijvoorbeeld mier te laten terugtrekken totdat een andere mier dicht genoeg is, vanaf dan kan je gaan hunten: 'met twee achter één enkele mier lopen'
• eventueel na te gaan door de omgeving te evalueren? Zoals bijvoorbeeld gunstig indien meer friend dan enemy ants? En afhankelijk van die test overgaan op hunter mode indien een gunstige omgeving; overgaan op defensive mode indien ongunstige omgeving

Welke ben je mee eens, welke zie je niet zitten of zijn niet verstandig?

Dan kan ik - na je mening - eens zien of ik er iets van kan coden...

[317070]

[*]implementatie om te vermijden dat mieren elkaar kunnen uitmoorden

Dit moet er uiteraard sowieso in

[*]beheer van 'inwendig gebied is reeds in orde: er wordt efficiënt voor gezorgd dat het voedsel wordt verzameld

Mja, eigenlijk nog niet echt, vind ik. De mieren zouden zich zo moeten opstellen, dat alles zichtbaar is. Eigenlijk hoeft zelfs dat niet, alles zou maar iedere 4 beurten ofzo eens zichtbaar moeten worden. Het is niet zo belangrijk dat ieder stukje voedsel meteen verwerkt wordt. Je kunt beter permanent 1 mier meer hebben aan het front, dan steeds 5 beurten eerder 1 mier extra te maken.

Nu gebeurt dat allemaal impliciet, door "weg te lopen van de dichtste buur", maar eigenlijk zou dat expliciet kunnen en dan kun je ook echt een optimale plaats/traject berekenen voor iedere mier.

Dat is een beetje mijn algemene idee nu. Ik heb snel dit huidige AI in elkaar gestopt om de Path-Ant laag te testen, maar ik zou alles op een Plan-laag willen, zodat alle mieren 'optimaal' samenwerken, in plaats van iedere mier individueel een gedrag te geven, dat ook toevallig tot een min of meer goed gedrag leidt voor de volledige kolonie.

[*]policy aan de grenzen moet op punt worden gesteld: vijandelijke mieren als doel markeren levert ruwweg goede resultaten op, maar moet worden verfijnd: voorstel is bijvoorbeeld mier te laten terugtrekken totdat een andere mier dicht genoeg is, vanaf dan kan je gaan hunten: 'met twee achter één enkele mier lopen'

Ja, inderdaad. Als je nu kijkt zie je dat we ook nog geen vijandige mieren 'volgen'. Ik zou ergens ook nog willen dat in de mate van het mogelijke ook de vijandige mieren een 'geheugen' krijgen, zodat we ze gemakkelijker kunnen aanvallen, of hun beweging voorspellen.

[*]eventueel na te gaan door de omgeving te evalueren? Zoals bijvoorbeeld gunstig indien meer friend dan enemy ants? En afhankelijk van die test overgaan op hunter mode indien een gunstige omgeving; overgaan op defensive mode indien ongunstige omgeving

Dat lijkt me nog erg moeilijk om te gaan doen. Dat is iets dat eigenlijk nog bovenop de plan-laag zou horen, want het is niet zomaar een gecoördineerde beweging van mieren, maar het is echt al kijken op een macro-niveau naar mieren met verschillende plannen.

Welke ben je mee eens, welke zie je niet zitten of zijn niet verstandig?

Alles moet er sowieso ooit in Ik stel voor dat je nu anders kijkt naar puntje 3) Policy aan de grenzen?

Ik ben momenteel aan het kijken naar die Plan-laag, en probeer meteen ook ervoor te zorgen dat de mieren niet meer op hetzelfde vakje komen en zo zelfmoord plegen. Ik ben eerder een algemene structuur in elkaar aan het boxen om dan gelijk welke AI in te kunnen maken, dan echt naar het spelletje zelf te kijken wat precies goed zou werken. Ik probeer dat vanavond af te hebben en te committen.

Een idee dat ik nog had, is dat we zouden moeten symmetrie in de map detecteren zodat we eenmaal we die hebben, veel meer van de kaart kennen dan waar we ook echt geweest zijn. Als de vijand defensiever is, en we dus moeilijker kunnen verkennen, zal dat wel erg van pas komen.

[317070]

Zo, die suicide-watch is geïmplementeerd en het plannensysteem ook. De bot crasht nu (expres) als je een path wil reserveren dat ergens al gereserveerd is. Je mag dat dus niet doen

Ik heb nu 2 basisplannen als voorbeeld gemaakt, de ene gaat op zoek naar voedsel met 1 ant, de andere valt met verschillende ants de vijand aan, zich aanpassend aan de beweging van die vijand.

Ik heb nog een kleine bug opgemerkt die ook in het starterpakket zat. Zo is voedsel niet passable, terwijl het starterpakket aangaf van wel. Dit kan nog leiden tot suicide als een ant op voedsel wil gaan lopen, en dat ga ik er morgen nog uit halen. Het probleem is dat het shortest-path gebruik maakte van het feit dat voedsel passable is...

[In physics I trust]

Super, ik ga meteen er nog eens naar kijken, en morgen laat ik dan wel iets horen.

[In physics I trust]

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.

De eer komt jou toe

Al blijf ik geïnteresseerd je code bekijken!