Om du är intresserad av något projekt som finns listat här, eller har egna ideér kontakta gärna Fredrik Niemelä.
Om man vill att en dator ska spela ett spel kan man t.ex. implementera en draggenerator, en evalueringsfunktion och en sökalgoritm. Draggeneratorn talar om vilka drag som är möjliga från en given position och definierar därmed ett sökträd. Evalueringsfunktionen talar om vilka positioner som är bra och sökalgoritmen försöker hitta ett sätt att ta sig till de bra positionerna.
Exjobbet går ut på att skriva ett program som givet en beskrivning av ett spel producerar en draggenerator för detta spel.
En viktig metod inom arificiell intelligens är sökning i beslutsträd. Ofta använder man sig av någon variant på minimax-sökning tillsammans med några mer eller mindre oberoende sökoptimeringar. Exempel på sökoptimeringar är "History heuristic", "Null move extension"och "Transposition table". Vilka sökoptimeringar som faktiskt ger ett förbättrat resultat är problemberoende.
Två problem när man ska applicera sökning på ett nytt problem är att man inte vet vilka optimeringar som ger effekt samt att vissa optimeringar bör implementeras specifikt för problemet, t.ex. för att optimeringen är beroende av problemrepresentationen.
För detta exjobbkommer alla problem att vara formulerade som spel. Exjobbet går ut på att skriva ett program som givet en beskrivning av ett spel väljer ut en bra uppsättning optimeringar samt producerar implementationer av dessa.
Inom kombinatorisk spelteori finns metoder för att beräkna spelvärdet av kombinatoriska spel på normalform. Givet detta värde kan man i för en given position avgöra vem som bör vinna vid perfekt spel samt vilket drag som är det bästa. Med andra ord; om man kan beräkna spelvärdet för alla giltiga positioner har man löst spelet.
Problemen är att spelvärdet kan ta väldigt lång tid att beräkna samt att spel inte alltid är formulerade på normalform. Det första problem kan avhjälpas genom att parallellisera beräkningarna och det andra av att översätta spelen till normalform när det är möjligt.
Exjobbet går ut på att ta reda på om det är möjligt att göra detta effektivt samt, beroende på svaret, hur eller varför inte.
|
|