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/7426

Titill: 
  • Titill er á ensku Gradual focus : a method for automated feature discovery in selective search
  • Gradual Focus: sjálfvirk uppgötvun á valbundnum leitar sérkennum
Námsstig: 
  • Meistara
Leiðbeinandi: 
Útdráttur: 
  • Útdráttur er á ensku

    The aim of selective search in adversary board games is to concentrate the search capacity on important lines of play, as to mimic the cognitive approach of humans. This is achieved by placing available moves into move categories, where interesting categories are examined more closely while less interesting ones are terminated early. One of the main challenges with selective search is designing effective move categories (features), which is a manual trial and error task that requires both intuition and expert human knowledge. Automating this task potentially enables the discovery of both more complex and more effective move categories. In this work we introduce Gradual Focus, an algorithm for automatically discovering interesting move categories for selective search. The algorithm iteratively creates new more refined move categories by combining mutually exclusive features from an atomic feature set. Each iteration selectively creates more detailed move categories. This enables the assessment of a move categories’ evolutionary progress, making Gradual Focus a merit driven method which continues to evolve move categories while it is still beneficial. Empirical data is presented for the games Breakthrough and chess showing that Gradual Focus looks at two orders of magnitude less than a brute force method would do.

  • Tilgangur valbundinnar andstæðings leitar (e. selective adversary search) í hefðbundnum leikjum á borð við skák er að stýra leitinni á þann hátt að áhugaverðir leikir eru skoðaðir nánar, sem er svipuð nálgun og við mennirnir notum til að leysa sambærileg vandamál. Þetta er útfært þannig að allar mögulegar aðgerðir (e. moves) eru flokkaðar í aðgerðaflokka eftir því hversu áhugaverðar aðgerðirnar eru. Með þessum hætti getur leitin eytt meiri tíma í að skoða áhugaverðar aðgerðir og minni tíma í að skoða óáhugaverðar aðgerðir. Það að skilgreina áhugaverða aðgerðaflokka er bæði flókið og villugjarnt ferli þar sem um er að ræða handvirkt ferli sem krefst sérfræði þekkingar mannanna. Ef ferlið yrði aftur á móti sjálfvirkt mundu opnast nýir möguleikar í að mynda flóknari og áhrifaríkari aðgerðaflokka en áður. Í þessari ritgerð lýsum við algrímnum Gradual Focus sem uppgötvar sjálfkrafa áhugaverða aðgerðaflokka fyrir valbundna leit. Með honum eru nýir og sértækari aðgerðaflokkar búnir til í ítruðu ferli þar sem aðgerðaflokkar úr síðustu ítrun eru sameinaðir við hóp af fyrirfram skilgreindum grunn (e. atomic) aðgerðaflokkum sem útiloka hvor aðra. Með þessu móti er hægt að meta þróun aðgerðaflokkanna sem gerir algrímnum kleift að þróa nýja aðgerðaflokka þangað til þeir eru ekki lengur gagnlegir. Gæði algrímsins eru sýnd í leikjunum Breakthrough og skák þar sem það kemur í ljós að Gradual Focus skoðar einungis tvær stærðargráður af aðgerðaflokkum til samanburðar við allar mögulegar samsetningar.

Samþykkt: 
  • 25.1.2011
URI: 
  • http://hdl.handle.net/1946/7426


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
MSc_Palmi-Skowronski.pdf2.74 MBOpinnHeildartextiPDFSkoða/Opna