Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A* Pathfinding Approach forthe Geometry Friends Game
KTH, School of Engineering Sciences (SCI).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Skapande av artificiell spelare till geometry friends med hjälp av A* sökalgoritmen (Swedish)
Abstract [en]

In February 1996 the IBM computer Deep Blue beat the reigning chess world champion Garry Kasparov in a game of chess. Since then the games in which the computers are beating humans, have become more and more complex. Teaching a computer to play a game may seem like a waste if recourses, but it is a very good way to test different learning methods, that can later be applied to real life problems. This report aims to evaluate the potential of an A*-based program for the Geometry Friends game. The Geometry friends game is a 2D physics based game, where the goal is to collect all the diamonds on the map using one or both of the two available characters. For the proposed AI, the A* algorithm is used to calculated a route between these diamonds. It then identifies critical elements along the path, which when encountered need special actions to pass. The program then navigates between these critical nodes and perform the associated actions, to complete the level. The results of the proposed agents on ten levels are compared to humans trying the same levels as well as agents developed by others. Compared to another agent, the CIBot [8], which uses Montecarlo tree search for to find the best path, the proposed agent performed slightly worse on most levels but did succeed in getting a higher score on two. Compared to the humans the proposed agent only manages to perform better on one level, and loses on the other nine.

Abstract [sv]

I februari 1996 blev den regerande världsmästaren i schack, Garry Kasparov, slagen av IBM’s dator Deep Blue i ett parti schack. Sedan dess har spelen i vilka datorer presterar bättre än människor blivit allt mer komplexa. Att lära en dator att spela ett spel kan verka som ett slöseri på resurser men det är ett väldigt bra sätt att testa olika inlärningsmetoder, som senare kan appliceras på mer konkreta problem Den här rapportens mål är att undersöka potentialen av ett A*-baserat program, inom spelet Geometry Friends.

Geomtry Friends är ett fysikbaserat 2D-spel, där målet är att samla in alla diamanter på en given bana, med hjälp en eller båda av de tillgängliga spelkaraktärerna. Det, i denna rapport, föreslagna programmet använder sig av A* sökalgoritmen för att hitta en väg mellan diamanterna. Den identifierar sedan kritiska punkter längs den funna vägen, där programmet kommer behöva utföra speciella åtgärder för att kunna passera. Programmet navigerar sedan mellan dessa noder och utför respektive åtgärder för att fullborda banan.

Resultatet av det föreslagna programmet på tio banor, jämfördes mot människors resultat på samma banor, men även resultatet av andras artificiella spelare. Jämfört med en annan artificiell spelare, CIBot [8], som använder sig av Montecarlo tree search för att hitta den bästa vägen, presterade det föreslagna programmet, marginellt sämre på de flesta banor men lyckades poängmässigt slå CIBot i två fall. Jämfört med människornas resultat vinner det föreslagna programmet endast på en bana och förlorar på resterande.

Place, publisher, year, edition, pages
2018. , p. 20
Series
TRITA-SCI-GRU ; 2018-082
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-231531OAI: oai:DiVA.org:kth-231531DiVA, id: diva2:1229050
Examiners
Available from: 2018-06-29 Created: 2018-06-29 Last updated: 2018-06-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

By organisation
School of Engineering Sciences (SCI)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 13 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf