Morpion Solitaire

Authors :: LAITINEN, JOUNI
Tietojenkäsittelytieteiden laitos - Department of Computer and Information Sciences
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
University of Tampere
Publication Year :: 2010
Abstract: Morpion Solitaire on säännöiltään yksinkertainen peli, jonka ratkaiseminen tietokoneella on kuitenkin NP-vaikea optimointiongelma. Tässä tutkielmassa esitellään aluksi erilaisia optimointimenetelmiä, joilla on aikaisemmin saavutettu hyviä tuloksia Morpion Solitairessa. Tämän jälkeen tutkielmassa perehdytään Morpion Solitairen ongelman ominaisuuksiin useiden testien avulla ja pohditaan tarkemmin, miksi hyvien tulosten löytäminen Morpion Solitairessa on vaikeaa. Lopuksi tutkielmassa esitellään tekijän ehdottama uusi ratkaisumenetelmä, jossa pyritään yhdistelemään aikaisemmin esiteltyjen optimointimenetelmien hyviksi todettuja ominaisuuksia sekä tekijän omia huomioita Morpion Solitairen ongelmasta. Tekijän ehdottamaa menetelmää arvioidaan kokeellisesti. Asiasanat:Morpion Solitaire, optimointimenetelmät, evoluutioon perustuvat algoritmit