Ditt arbete under HT1 ska leda till ett personligt planeringsdokument där du har tänkt genom specifika aspekter av det valda problemet:

• Du behöver veta exakt vilket problem du vill lösa. Luddiga problemställningar leder till problem med både implementation, utvärderingar och slutrapport. Ju mer arbete som läggs på en tydlig beskrivning nu, desto mindre arbete senare.

• Man behöver koordinera problemställningarna inom gruppen, så att inget överlapp uppstår och inga funktionaliteter saknas.

• Du behöver välja en konkret AI-teknik, för att kunna verifiera att den faktiskt löser problemet.

• Du behöver tänka på hur problemet ska modelleras (förklaras senare), så att du vet att den information du har om världen räcker till och att du faktiskt kan applicera tekniken som du har tänkt dig.

• När detta är gjort behöver man koordinera informationsbehovet inom gruppens ansvarsområden, så att någon faktiskt skapar den information som behövs om StarCraft-världen.

Det individuella planeringsdokumentet examineras inte och måste inte följa någon specifik mall, men är ändå mycket viktigt för ditt eget arbete liksom för grupparbetet. Vi kommer därför att gå genom det inom grupperna (kamratgranskning) och se till att det hålls tillräckligt uppdaterat.

Tänk samtidigt på att arbeta inkrementellt och hålla det lagom genombearbetat. Lägger man till exempel alltför mycket tid på den perfekta problembeskrivningen, kanske man i nästa avsnitt upptäcker att problemet inte är lösbart och att att man därför måste gå tillbaka och ändra i den del av dokumentet som redan var perfekt. Då är det bättre att gå genom dokumentet i flera pass: Skapa en första version av hela dokumentet för att se att allt verkar genomförbart, och gå sedan tillbaka och förbättra det i omgångar.

En agent som självständigt ska spela StarCraft har en hel del olika problem att lösa. Den behöver till exempel kunna välja vilka enheter som ska byggas i vilken ordning, hitta sätt att ta sig från position A till position B på kartan utan att springa in i kända fiendeenheter, hitta trånga passager att blockera så att fienden inte kan anfalla från alla håll, och så vidare. Fler exempel på problem diskuterar vi under en av de inledande föreläsningarna.

Parallellt med steg 1b (att skapa projektgrupper) behöver du själv välja vilka problem eller problemklasser du vill undersöka, med utgångspunkt i föreläsningens beskrivningar. I senare steg på denna sida ska du undersöka hur det valda problemet faktiskt kan lösas med hjälp av publicerade AI-tekniker, och under projektarbetet ska du implementera och utvärdera en sådan lösning. (Det kan också gå att välja alternativa problem som vi inte har tagit upp under föreläsningen, men diskutera då gärna med examinatorn i god tid!)

Den största begränsningen i vilka problem du kan välja är att du behöver:

• Lösa ett tillräckligt intressant och omfattande problem för att implementationen och utvärderingen ska kunna räcka till examinationen.

• Undvika överlappande problem inom projektgruppen. Varje gruppmedlem behöver ett eget ansvarsområde, med tydligt huvudansvar för sitt problemområde / AI-teknik.

• Undvika att ta dig vatten över huvudet vid implementation och utvärdering.

Det är detta vi försöker hjälpa till med när vi föreslår problem och litteratur.

Efter föreläsningen om problemområden är det dags att bilda projektgrupper om cirka 5-7 personer (kursledningen meddelar antalet beroende på exakt antal kursdeltagare detta år). Inom projektgruppen behöver man därefter samordna sina problemområden för att undvika överlapp. Man kan behöva anpassa sitt val av ansvarsområde för att det ska passa in i gruppen, eller anpassa grupperna så att de som väldigt gärna vill arbeta med samma område hamnar i olika grupper.

Vad menas då med "eget" ansvarsområde? Här är några exempel. Diskutera gärna med handledarna!

• Två personer i samma grupp kan inte tilldelas ansvarsområdet hitta en bra byggnadsordning givet vad vi redan har och vad vi vet om fienden. Detta är en problemställning.

• Däremot skulle en person kunna ha hand om att uppskatta vilken strategi fienden troligen använder just nu medan en annan person kan ta hand om att hitta en bra byggnadsordning givet vilken strategi vi tror fienden använder just nu. Detta är två tydligt separerade problemställningar, även om lösningen på den ena ger information som behövs för att kunna applicera den andra.

• Två personer i samma grupp kan möjligen ha ansvar för olika ansvarsområden där lösningarna överlappar till viss del. De kan t.ex. arbeta med två helt olika problemställningar där det visar sig att båda de valda lösningarna applicerar flow fields, fast på olika sätt. Man kan då samarbeta om implementationen av grundläggande flow fields, men behöver fortfarande ha en signifikant "egen" funktionalitet att implementera och utvärdera ovanpå detta. Den delen av implementationen ska då vara separerad så att det gemensamma, t.ex. "flow fields", är en tydligt avgränsad del av koden.

  Detta gäller alltså projektdelen. Den individuella utredningen är alltid individuell: Skriv inte gemensamma avsnitt om t.ex. flow fields, utan gör din egen utredning.

I detta steg kan man också börja tänka på övriga ansvarsområden som inte är direkt kopplade till problemområden. Ska några fokusera mer på integration av olika funktionaliteter? Hur fördelar man arbetet så att gemensamma uppgifter inte främst faller på ett fåtal personer? Ska man ha veckomöten och ska någon vara sammankallande i detta?

När grupperna är bildade, och du är säker på vilket allmänt problemområde du kommer att vara ansvarig för, är det dags att börja beskriva detta mer detaljerat och tydligt i ditt personliga planeringsdokument.

I ett första steg behöver du åtminstone beskriva problemområdet för dig själv. Då kan det vara frestande att beskriva det väldigt kort och ytligt för att spara tid, men det kan lätt straffa sig senare: En otydlig problembeskrivning kan lätt leda in på villovägar när man letar lösningar. Dessutom kan du behöva diskutera problemet med andra gruppmedlemmar, som behöver mer och tydligare information, och din slutliga rapport kommer att behöva en mycket tydlig beskrivning för den som inte alls är bekant med problemet.

Det vi beskriver nedan är det du kommer att behöva till din slutliga individuella rapport när hela projektet är klart. Välj själv hur detaljerad du vill vara i din första version, och vilket verktyg du skriver det i (slutrapporten skrivs främst i LaTeX).

Tänk dig att du i din slutliga rapport ska beskriva detta för någon annan, som är den som faktiskt ska lösa problemet utan att behöva kontakta dig för att reda ut detaljerna! Då hamnar du förhoppningsvis på en lagom tydlig nivå för rapporten.

Du behöver beskriva och tydligt definiera ett konkret och avgränsat problem som du vill lösa i StarCraft. Vi förtydligar:

1. Du ska beskriva ett problem i StarCraft. Ursprungligen kanske du var mer intresserad av att testa en viss AI-teknik och letade efter ett problem du kunde lösa med detta. Här måste du ändå beskriva det problem du hittade: Du vill se till att agenten kan göra något, åstadkomma något, bestämma något, ha en viss förmåga... för att den sedan ska kunna spela bättre.

   Att "jämföra Q-learning med supervised learning" är inte något som direkt uppkommer från StarCraft utan handlar om att undersöka egenskaper hos tekniker. Att göra "opponent modeling" (punkt) är inte tillräckligt specifikt och konkret. Hitta istället ett problem vars lösning direkt bidrar till att spela bättre StarCraft.

2. Problemet ska vara konkret och avgränsat med en tydlig definition.

   På hög nivå har man kanske en vision att "agenten ska vinna oftare" eller att "marines ska överleva längre" – men det ligger på en så hög nivå och är så brett i sin definition att det inte ger dig någon särskild vägledning, och då blir det svårt för dig själv att styra ditt arbete åt rätt håll.

   Du behöver beskriva problemet så tydligt att läsaren förstår precis vad du vill uppnå. För att nå dit kan du tänka dig att du i själva verket skriver en kravspecifikation som ska lämnas över till någon annan. Vad behöver du skriva för att den personen ska arbeta på rätt uppgift fram till du kommer tillbaka om ett par månader? Dina tankar får inte stanna kvar i huvudet utan behöver komma ner på papper.

   Det ska synas vad du vill försöka lösa men också vad du inte tänker lösa. Du får mycket gärna uttryckligen skriva att vissa problemställningar inte ingår!

3. Problemet behöver vara lagom stort.

   Tänk på att kursen ger 5 hp och att du inte ska försöka lösa för många eller stora problem på en gång. Då hinner du inte gå på djupet med implementation och utvärdering.

   Samtidigt får problemet inte vara alldeles för enkelt. Det är exempelvis trivialt att ta reda på vilka byggnadstyper man måste konstruera innan man kan bygga något av typ X: Det kan lätt hårdkodas och löses annars genom att titta på Tech Tree med en trivial algoritm. Du behöver få en chans att visa upp att du kan applicera AI-tekniker!

   Storleken på problemet kan komma på flera håll. Exempelvis kan du använda komplexa algoritmer, men du kan också använda enklare algoritmer som istället behöver mer djup i modelleringen. Att räkna ut sannolikheter från ett Bayesianskt nätverk kan t.ex. vara enkelt, men det finns desto mer djup i modelleringsarbetet där du måste lägga ner arbete på att undersöka vilka noder och kopplingar som ska finnas i detta nätverk och på att komma fram till bra sannolikhetstabeller.

Här är några viktiga steg i att vara tydlig:

• Definera dina termer och begrepp noggrannt. Vad menar du med orden?

• Tala om i vilka StarCraft-situationer problemet behöver lösas. Vad gör/har motståndaren, vad gör/har du, vad händer i spelet när ditt problem är aktuellt?

• Tala om vilka antaganden du gör om världen.

Du behöver också välja en AI-teknik eller algoritm som löser det problem du har ställt upp, samt en eller flera vetenskapliga artiklar som beskriver denna teknik.

Här ska du alltså läsa vetenskaplig litteratur för att avgöra vad du tycker är mest intressant att implementera och testa i praktiken. Du kan till exempel utgå från litteratur som visas på kursens wikisidor. Sök gärna vidare – leta gärna efter mer information om teknikerna. Använd primärt vetenskapliga artiklar, sekundärt kursböcker. Google Scholar kan hitta relaterade artiklar som citerar det ni läser!

Det kan vara bra att först skumma genom artiklar i upp till 10--20 minuter innan man går genom dem noggrannare, för att få en känsla för om man vill gå vidare eller inte. Allra först kan man också fokusera mer på inledning och slutsatser, och hoppa över de tekniska delarna.

Det du kommer fram till att du vill använda ska skrivas ner i det personliga planeringsdokumentet. Till skillnad från tidigare år behöver du inte skriva en egen utförlig beskrivning av hela tekniken, utan kan helt enkelt hänvisa till en vetenskaplig artikel där den definieras.

Lite att tänka på:

• Lösningsmetoder och tekniker som du väljer att undersöka ska normalt vara generellt applicerbara. Även om vi t.ex. enbart använder en enda karta i kursen, ska man inte använda tekniker som man bara fungerar om man hårdkodar en specifik karta, eller som kräver väldigt specifika egenskaper hos en karta.

• Samtidigt måste metoderna vara konkreta. Reinforcement learning är exempelvis en kategori av metoder som har vissa gemensamma egenskaper på en abstrakt nivå. Detta är ingen konkret lösningsmetod utan behöver konkretiseras mer i din planering. Även supervised learning och unsupervised learning är kategorier av metoder, liksom sökning och automatisk planering. Däremot är Q-learning en konkret metod inom kategorin reinforcement learning.

Riskabla tekniker

Vi vill varna för att vissa typer av tekniker har sina risker – de kan mycket väl fungera alldeles utmärkt, men vi har sett att några (inte alla) av de som satsar på dessa tekniker behöver lägga ner mycket arbete under den senare projektdelen av kursen. Om du gärna vill använda sådana tekniker, tänk då ett varv extra innan du tar ditt slutliga beslut!

• Tekniker som baseras på maskininlärning är intressanta för många. Samtidigt blir resultatet alltid beroende av hur väl inlärningen lyckas, och detta är något som man inte kan påverka till 100% själv. I media ser vi bara de lyckade exemplen.

  Man kan så klart bli godkänd även om utfallet (i fråga om hur bra agenten spelar) inte blir det man har önskat sig, men man kan då behöva lägga ner mer arbete på att förklara varför det hände och att visa att det inte helt enkelt är den grundläggande implementationen som är felaktig. Man kan också behöva visa att man har kunnat göra en rimlig ansats på själva inlärningen: Det är problematiskt om man helt enkelt inte har hunnit köra den tillräckligt länge eller inte har haft tillgång till rimliga indata.

  Om du använder maskininlärning, satsa då hårt på att bli klar med implementationen i god tid. Det räcker inte med att köra själva inlärningen en gång, utan du kommer med största sannolikhet att vilja fixa buggar, köra om, prova att justera någon parameter, köra om... och varje ny inlärningsomgång skulle kunna ta flera dagar, även om du själv inte behöver sitta vid datorn.

• Deep Learning syns speciellt mycket i media och kräver särskilt mycket tid, både datortid och tid att förstå vad man ska göra. Vi rekommenderar mycket starkt att man inte ger sig in i det området i den här kursen om man vill ha en chans att hålla sig inom den tänkta kurstiden.

• Användandet av replays / repriser för maskininlärning kan ta lång tid. Det kan också vara svårt att hitta tillräckligt många / tillräckligt tillämpliga repriser som kan läsas i verktygen och som har den information som du behöver. Vilka replays som fungerar kan variera från år till år, och vi har inte haft möjlighet att bygga upp ett stabilt bibliotek.

• Tänk på att supervised learning kräver att man har en form av "facit". Vill du lära dig i vilka situationer man bör spela offensivt respektive defensivt? Du kan säkert hitta gott om intressanta indata i replays – hur många enheter du har, hur många enheter motståndaren har, med mera – men det är desto svårare att automatiskt analysera om spelaren spelade offensivt eller defensivt vid en specifik punkt i en specifik replay. Då blir det upp till dig att manuellt skapa sådana "etiketter/labels" för en mindre uppsättning replays, vilket tar mycket tid och energi.

• Vi har främst använt en och samma karta under kursen. Det finns en karteditor, men att använda den kan vara mer knepigt.

De flesta AI-tekniker kräver att man tänker en del kring hur problemet man har ska modelleras:

• Om du vill lösa ett problem med Bayesianska nätverk, räcker det inte med att implementera en inferensalgoritm för detta. Du måste också veta vilka indata du ska ge till algoritmen. Vilka noder ska finnas i ditt nätverk? Är det alltid samma eller beror det t.ex. på vilka enheter som finns? Vilka kopplingar ska finnas mellan noderna för att ge en struktur till nätverket? Vilka vikter? Hur beräknar du de vikterna?

• Om du vill lösa ett problem med hjälp av en planeringsalgoritm, vilka tillstånd ska du då anta att världen har? Vilka handlingar finns och exakt vilka villkor och effekter har de? Behöver du en algoritm som klarar tid och parallella handlingar, eller räcker det med en sekvensiell algoritm?

• Och så vidare...

Detta kräver att du gör en ordentlig utredning för att komma fram till lämpliga modeller. Resultatet ska skrivas ner i den individuella planeringsrapporten, men kommer också att användas som underlag till ett av de viktigaste avsnitten i slutrapporten!

Samtidigt som detta behöver du fundera på hur den färdiga implementerade lösningen ska integreras i gruppens gemensamma agent, där din implementation ska interagera med omvärlden. Du behöver indata och genererar utdata; du blir anropad och du kanske anropar andra. Du behöver beskriva hur detta är tänkt, både för tydlighetens skull och för att kunna samordna med dina gruppmedlemmar.

• Hur anropas funktionaliteten? Vill du att den ständigt kör "i bakgrunden" och gör något, t.ex. styr scouting? Eller tänker du dig att någon anropar dig när du ska göra eller beräkna något? Skickar de med några parametrar då? Vilka?

• Vilken information förutsätter du finns tillgänglig för dig? Det kan gälla information om världen/kartan, om motståndaren, om vad andra delar av gruppens agent håller på med, med mera. Definiera den informationen tydligt, så att man kan avgöra om informationen räcker till för att faktiskt lösa problemet! Diskutera sedan inom gruppen vem som är ansvarig för att ta fram den nödvändiga informationen.

  Exempel: Inom klassisk planering förutsätts tillgång till (a) information om exakt vilka handlingar som finns och deras precisa exekveringsvillkor (preconditions) och effekter, (b) fullständig information om världens nuvarande tillstånd (vilka fakta som är sanna och vilka som är falska), och (c) ett målvillkor uttryckt i termer av vilka fakta som ska bli sanna efter att en lösningsplan har exekverats.

  Tänk dig att den information som inte tas med här inte kommer att finns tillgänglig vid körningen!

• Vilken information tänker du dig att ge till resten av systemet? Även här behöver du vara tillräckligt tydlig och konkret, inte minst för att man ska kunna avgöra vilka lösningsmetoder som är lämpliga. Om du t.ex. vill välja strategi, tala då om vilka alternativa strategier du har tänkt dig (du kan så klart ändra dig i det senare utredningsarbetet).

  Exempel: Inom klassisk planering är utdata en sekvens av utvalda handlingar sådan att om världen är i det angivna tillståndet, och sekvensen exekveras i den angivna sekvensen, kommer målvillkoret att bli sant i det resulterande tillståndet.

  Eller tänker du dig att din funktionalitet inte ger information till andra delar av systemet, utan istället själv styr något? Beskriv då detta. Exempelvis kan det finnas en funktionalitet som direkt styr hur agenter rör sig vid en attack.