is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7422

Titill: 
  • Titill er á ensku Solving general game playing puzzles using heuristics search
  • General Game Playing þrautir leystar með upplýstum leitaraðferðum
Námsstig: 
  • Meistara
Leiðbeinandi: 
Útdráttur: 
  • Útdráttur er á ensku

    One of the challenges of General Game Playing (GGP) is to effectively solve puzzles. Solving puzzles is more similar to planning algorithms than the search methods used for two- or multi-player games. General problem solving has been a topic addressed by the planning community for years. In this thesis we adapt heuristic search methods for automated planning to use in solving single-agent GGP puzzles.
    One of the main differences between planning and GGP is the real-time nature of GGP competitions. The backbone of our puzzle solver is a realtime variant of the classical A* search algorithm we call Time-Bounded and Injection-based A* (TBIA*). The TBIA* is a complete algorithm which always maintains a best known path to follow and updates this path with new and better paths as they are discovered.
    The heuristic TBIA* uses is constructed automatically for each puzzle being solved, and is based on techniques used in the Heuristic Search Planner system. It is composed of two parts: the first is a distance estimate derived from solving a relaxed problem and the second is a penalty for every unachieved sub-goal. The heuristic is inadmissible when the penalty is added but typically more informative. We also present a caching mechanism to enhance the heuristic performance and a self regulating method we call adaptive k that balances cache useage.
    We show that our method both adds to the flora of GGP puzzles solvable under real-time settings and outperforms existing simulation-based solution methods on a number of puzzles.

  • Eitt af viðfangsefnum alhliða leikjaspilara er að fást við einmenningsleiki eða þrautir. Að leysa slíkar þrautir er mjög ólíkt því að spila gegn andstæðingum og á meiri samleið með reikniritum fyrir áætlunargerð. Í þessari ritgerð er byggt á margra ára rannsóknum á almennum áætlunarreikniritum og þær aðferðir heimfærðar yfir í heim alhliða leikjaspilara.
    Meginmunurinn á áætlanagerð og alhliða leikjaspilun er að leikjaspilunin er háð tímatakmörkunum þar sem leikmenn fá upphafs- og leikklukku. Kjarninn í lausnaraðferð okkar er rauntíma útfærsla af A* leitaraðferðinni sem við köllum Time-Bounded and Injection-based A*.
    Stöðumatið sem við notum byggir á hugmyndum frá Heuristic Search Planner áætlunar hugbúnaðinum og er tvíþætt. Annars vegar er vegalengdin í mark áætluð með því að leysa einfaldaða útgáfu af vandamálinu og hins vegar er bætt við refsingu fyrir hvert óuppfyllt lausnarskilyrði. Vegna þess að ein aðgerð getur uppfyllt fleiri en eitt lausnarskilyrði er ekki tryggt að stöðumatið okkar sé lágmarkandi en í mörgum tilfellum er það mun nær raunveruleikanum sem aftur flýtir fyrir leitinni. Þar sem stöðumatið er tímafrekt kynnum við uppflettiaðferð sem flýtir fyrir útreikningi stöðumata. Einnig höfum við sjálfstillandi ávörðunartöku sem við köllum adaptive k sem nýtir sér uppflettingar eftir gæðum þeirra.
    Við sýnum fram á að fyrrgreindar aðferðir virka vel á fjölda þeirra þrauta sem notaðar hafa verið í alþjóðlegum keppnum og að við höfum bætt við þann fjölda þrauta hægt er að leysa.

Athugasemdir: 
  • Project report
Samþykkt: 
  • 25.1.2011
URI: 
  • http://hdl.handle.net/1946/7422


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
MSc_Gylfi-Thor-Gudmundsson.pdf315.07 kBOpinnHeildartextiPDFSkoða/Opna