Computational methods in codes and games

Esa A. Seuranen

Research output: ThesisDoctoral ThesisCollection of Articles

Abstract

This dissertation discusses exhaustive search algorithms and heuristic search methods in combinatorial optimization, including combinatorial games. In this work unidirectional covering codes are introduced and some theoretical foundations for them are laid. Exhaustive search is used to construct asymmetric covering codes, unidirectional covering codes and multiple coverings with given parameters—or to show that no such codes exist. Integer programming formulations, bounds on maximal coverages of partial codes and code isomorphisms are used to prune the search space. Tabu search is used to construct asymmetric and unidirectional covering codes—with several record-breaking codes for the former. A new definition for neighborhood is derived. The traditional board game of go and computer go results are reviewed. The concept of entropy is introduced into the game context as a metric for complexity and for relevance (of features—like distance to the previous move). Experimental results and questionnaire studies are presented to support the use of entropy.
Translated title of the contributionComputational methods in codes and games
Original languageEnglish
QualificationDoctor's degree
Awarding Institution
  • Aalto University
Supervisors/Advisors
  • Östergård, Patric, Supervising Professor
  • Östergård, Patric, Thesis Advisor
Publisher
Print ISBNs978-952-60-4369-2
Electronic ISBNs978-952-60-4370-8
Publication statusPublished - 2011
MoE publication typeG5 Doctoral dissertation (article)

Keywords

  • covering codes
  • exhaustive search
  • go
  • tabu search

Fingerprint

Dive into the research topics of 'Computational methods in codes and games'. Together they form a unique fingerprint.

Cite this