Morpion Solitaire

LAITINEN, JOUNI (2010)
 
Avaa tiedosto
Lataukset: 



LAITINEN, JOUNI
2010

Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2010-06-11
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-20745
Tiivistelmä
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
Kokoelmat