Computational methods in codes and games
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu |
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
Verkkokirja (304 KB, 42 s.)
Series
Aalto University publication series DOCTORAL DISSERTATIONS ,
119/2011
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.Description
Supervising professor
Östergård, Patric R.J., Prof.Thesis advisor
Östergård, Patric R.J., Prof.Keywords
Other note
Parts
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 4]: Esa Antero Seuranen. 2007. New lower bounds for multiple coverings. Designs, Codes and Cryptography, volume 45, number 1, pages 91-94.
- [Publication 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.
- [Publication 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.