Eternity II -reunatäsmäyspelin heuristiikoista
KUJALA, TUOMAS (2011)
2011
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden yksikkö - School 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ä
2011-05-27
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-21405
https://urn.fi/urn:nbn:fi:uta-1-21405
Tiivistelmä
Reunatäsmäyspelit ovat lautapelejä, jotka näennäisestä helppoudestaan huolimatta ovat NP-täydellisiä. Niiden ratkaisemiseen ei siis ole tiedossa tehokasta algoritmia. Reunatäsmäyspeleille voidaan kuitenkin kehittää erilaisia heuristiikkoja, jotka pyrkivät ratkaisemaan pelin mahdollisimman hyvin.
Tässä tutkielmassa esitellään neljä erilaista heuristiikkaa, joista kaksi perustuu evoluutioalgoritmeihin, yksi hill climbing -tekniikkaan ja yksi simuloituun jäähdytykseen. Kaikilla esitellyillä heuristiikoilla pyritään ratkaisemaan Eternity II -reunatäsmäyspeli mahdollisimman hyvin.
Tuloksista selvisi, että molemmat evoluutioalgoritmit tuottivat mainituista heuristiikoista tässä tutkielmassa parhaan yksittäisen tuloksen, 407/480 pistettä. Tulos on vielä melko kaukana Eternity II:n täydellisestä ratkaisusta, mutta algoritmeja edelleen kehittämällä paremmatkin pistemäärät lienevät mahdollisia.
Asiasanat:reunatäsmäyspelit, metaheuristiikat, geneettiset algoritmit, hill climbing, simuloitu jäähdytys, kombinatorinen optimointi
Tässä tutkielmassa esitellään neljä erilaista heuristiikkaa, joista kaksi perustuu evoluutioalgoritmeihin, yksi hill climbing -tekniikkaan ja yksi simuloituun jäähdytykseen. Kaikilla esitellyillä heuristiikoilla pyritään ratkaisemaan Eternity II -reunatäsmäyspeli mahdollisimman hyvin.
Tuloksista selvisi, että molemmat evoluutioalgoritmit tuottivat mainituista heuristiikoista tässä tutkielmassa parhaan yksittäisen tuloksen, 407/480 pistettä. Tulos on vielä melko kaukana Eternity II:n täydellisestä ratkaisusta, mutta algoritmeja edelleen kehittämällä paremmatkin pistemäärät lienevät mahdollisia.
Asiasanat:reunatäsmäyspelit, metaheuristiikat, geneettiset algoritmit, hill climbing, simuloitu jäähdytys, kombinatorinen optimointi