MSc thesis defense - Pálmi Skowronski - Gradual Focus: A Method for Automated Feature Discovery in Selective Search

A MSc Thesis Defense will be held in Computer Science on Wednesday the 14th of January, Room K5, 1pm-3pm, Kringlan 1. All are welcome.

"Gradual Focus: A Method for Automated Feature Discovery in Selective Search"

Pálmi Skowronski

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 availablemoves intomove 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 than a brute force method would do.