The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Computational Methods in Codes and Games

Esa A. Seuranen

Doctoral dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the School of Electrical Engineering for public examination and debate in Auditorium S4 at the Aalto University School of Electrical Engineering (Espoo, Finland) on the 25th of November 2011 at 12 noon.

Overview in PDF format (ISBN 978-952-60-4370-8)   [304 KB]
Dissertation is also available in print (ISBN 978-952-60-4369-2)

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.

This thesis consists of an overview and of the following 6 publications:

  1. Patric R. J. Östergård and Esa A. Seuranen. 2004. Constructing asymmetric covering codes by tabu search. Journal of Combinatorial Mathematics and Combinatorial Computing, volume 51, pages 165-173. © 2004 Charles Babbage Research Centre (CBRC). By permission.
  2. Patric R. J. Östergård and Esa A. Seuranen. 2006. Unidirectional covering codes. IEEE Transactions on Information Theory, volume 52, number 1, pages 336-340. © 2006 Institute of Electrical and Electronics Engineers (IEEE). By permission.
  3. Esa A. Seuranen and Patric R. J. Östergård. 2006. New lower bounds for asymmetric covering codes. Congressus Numerantium, volume 178, pages 57-63. © 2006 Utilitas Mathematica Publishing. By permission.
  4. Esa Antero Seuranen. 2007. New lower bounds for multiple coverings. Designs, Codes and Cryptography, volume 45, number 1, pages 91-94.
  5. Esa A. Seuranen. 2007. Introducing playing style to computer go. In: Jaap van den Herik, Jos Uiterwijk, Mark Winands, and Maarten Schadd (editors). Proceedings of the Computer Games Workshop 2007 (CGW 2007). Amsterdam, The Netherlands. 15-17 June 2007. Maastricht, The Netherlands. Maastricht University. MICC Technical Report Series, 07-06, pages 81-91. © 2007 Maastricht University. By permission.
  6. Esa A. Seuranen. 2009. Entropy in go. ICGA Journal, volume 32, number 1, pages 34-40. © 2009 International Computer Games Association (ICGA). By permission.

Keywords: covering codes, exhaustive search, go, tabu search

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2011 Aalto University

Last update 2012-03-02