Erik Edin

Classification and solutions of general combinatorial games

Abstract

This master's project is an attempt to enable automatic classification and solving of combinatorial games, in the context of general game playing. The Game Description Language is used as the framework for general game playing. The classification of the combinatorial games is focused on the basic properties normal or misère form, all small games, partial or impartial games, and number of players. The methods used in making these classifications are template matching and logical deduction. This master's thesis focuses on solving only subtraction games, since they are easily analysed, while remaining interesting. Presented here is a solution, that can analyse the most common constructs, to solving a slightly generalised form of subtraction games. The classification and solving is tested on a suite of games constructed for this master's project.

Klassificering och lösning av generella kombinatoriska spel

Sammanfattning

Detta examensarbete är ett försök att möjliggöra automatisk klassificering och lösning av generella kombinatoriska spel. Som verktyg för att beskriva kombinatoriska spel används Game Description Language utvecklat på Stanford. Klassificeringen av kombinatoriska spel är fokuserad på de grundläggande egenskaperna normal- eller misèrespel, "all small"-spel, partiska och opartiska spel, samt antal spelare. Metoderna som används är igenkänning från mall och logisk härledning. Detta examensarbete fokuserar på lösning av subtraktionsspel, eftersom de är lättanalyserade, men fortfarande intressanta. Här presenteras en lösning, som kan analysera de vanligaste konstruktionerna, av en något generaliserad form av subtraktionsspel. Klassificering och lösningen testades på ett antal spel, som konstruerades för detta arbete.