EnglishisÍslenska

Member institutions

Search in


ThesisReykjavík University>Tölvunarfræðideild>Meistaraprófsritgerðir>

Please use this identifier to cite or link to this item: http://hdl.handle.net/1946/7426

Titles
  • Gradual focus : a method for automated feature discovery in selective search

  • is

    Gradual Focus: sjálfvirk uppgötvun á valbundnum leitar sérkennum

Published
January 2009
Abstracts
  • 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.

  • is

    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.

Comments
is

Tölvunarfræði, Thesis

Issued Date
25/01/2011


Artifacts
Name[Sortable]Size[Sortable]Visibility[Sortable]Description[Sortable]Format
MSc_Palmi-Skowronski.pdf2.8MBOpen Complete Text PDF View/Open