Ricochet Robots pelin analysointi ja ratkaisualgoritmi
Manninen, Ville-Petteri (2022)
Kandidaatintyö
Manninen, Ville-Petteri
2022
School of Engineering Science, Laskennallinen tekniikka
Kaikki oikeudet pidätetään.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi-fe2022053141261
https://urn.fi/URN:NBN:fi-fe2022053141261
Tiivistelmä
Ricochet Robots on vuonna 1999 Alex Randolphin kehittämä lautapeli, jossa tavoitteena on neljää pelinappulaa hyödyntämällä siirtää niistä tietty maaliruutuun. Ratkaisua vaikeuttaa pelinappuloiden liikkeen pysähtyminen vasta laudalla olevaan seinään tai toiseen nappulaan, jolloin niiden on toimittava yhdessä toisilleen seininä ratkaisun saavuttamiseksi. Ongelma on osoitettu olevan NP-vaikea.
Työssä rakennettiin leveyshakuun perustuva algoritmi, joka ratkaisee sille syötetyn lautapelin tilanteen optimaalisesti. Algoritmin toimintaa tehostettiin rajaamalla tarkasteltavia tilanteita muun muassa poistamalla turhia siirtoja ja implementoimalla heuristiikkaa. Samalla algoritmin tekemiä operaatioita optimoitiin koodin ja toteutuksen puolella.
Lopullinen algoritmi sisältää lähes kaikki testatut menetelmät, joista suurin osa nopeutti ratkaisun löytymistä sadoilla prosenteilla. Lisäyksien kannattavuudesta varmistuttiin parittaisella t-testillä. Algoritmi pystyy ratkaisemaan tapaukset rajattuun 15:een siirtoon asti, kattaen 99.94% lautapelin tilanteista alle kolmessa minuutissa. Regressioanalyysin avulla luotiin ennuste, jonka mukaan tapaukset 24:ään siirtoon asti ratkeavat päivässä. Kerättyjen 100 000:n ratkaisun perusteella saatiin optimaalisen ratkaisun pituuden keskiarvon 99.9% luottamusväliksi [6.28, 6.33]. Lautapelin tilanteista 34.07% on myös ratkaistavissa siirtämällä vain yhtä pelinappulaa, jotka painottuvat pienille siirtojen määrille. Ricochet Robots is a game designed by Alex Randolph in 1999, in which the goal is to move a specific one of the four game pieces to the goal cell. Finding a solution is made more difficult by limiting the movement of the pieces, since they stop only when colliding with a wall on the board or another piece. This way the pieces must be used as walls for one another to find a solution. Solving the problem has been proved to be NP-hard.
The objective of this thesis was to build a breadth-first search algorithm which could solve the case of the game provided to it optimally. The algorithm was made more efficient by limiting the moves and positions it must consider and by implementing heuristics. Also the operations used by the algorithm were optimized both in the code and implementation.
The final algorithm included almost all the tested methods, most of which allowed the algorithm to find solutions hundreds of percent’s faster. Paired t-test was used to determine whether a method was worthwhile to implements or not. The algorithm could solve the cases to the limit of 15 moves covering 99.94% of the board games cases in three minutes. Using regression analysis, the algorithm could solve cases up to 24 moves in a day. Using the collected 100 000 solutions the 99.9% confidence interval for the optimal solutions length was calculated to be [6.28, 6.33]. From the board games cases, 34.07% can also be solved using only one game piece, which are weighted towards lower number of moves.
Työssä rakennettiin leveyshakuun perustuva algoritmi, joka ratkaisee sille syötetyn lautapelin tilanteen optimaalisesti. Algoritmin toimintaa tehostettiin rajaamalla tarkasteltavia tilanteita muun muassa poistamalla turhia siirtoja ja implementoimalla heuristiikkaa. Samalla algoritmin tekemiä operaatioita optimoitiin koodin ja toteutuksen puolella.
Lopullinen algoritmi sisältää lähes kaikki testatut menetelmät, joista suurin osa nopeutti ratkaisun löytymistä sadoilla prosenteilla. Lisäyksien kannattavuudesta varmistuttiin parittaisella t-testillä. Algoritmi pystyy ratkaisemaan tapaukset rajattuun 15:een siirtoon asti, kattaen 99.94% lautapelin tilanteista alle kolmessa minuutissa. Regressioanalyysin avulla luotiin ennuste, jonka mukaan tapaukset 24:ään siirtoon asti ratkeavat päivässä. Kerättyjen 100 000:n ratkaisun perusteella saatiin optimaalisen ratkaisun pituuden keskiarvon 99.9% luottamusväliksi [6.28, 6.33]. Lautapelin tilanteista 34.07% on myös ratkaistavissa siirtämällä vain yhtä pelinappulaa, jotka painottuvat pienille siirtojen määrille.
The objective of this thesis was to build a breadth-first search algorithm which could solve the case of the game provided to it optimally. The algorithm was made more efficient by limiting the moves and positions it must consider and by implementing heuristics. Also the operations used by the algorithm were optimized both in the code and implementation.
The final algorithm included almost all the tested methods, most of which allowed the algorithm to find solutions hundreds of percent’s faster. Paired t-test was used to determine whether a method was worthwhile to implements or not. The algorithm could solve the cases to the limit of 15 moves covering 99.94% of the board games cases in three minutes. Using regression analysis, the algorithm could solve cases up to 24 moves in a day. Using the collected 100 000 solutions the 99.9% confidence interval for the optimal solutions length was calculated to be [6.28, 6.33]. From the board games cases, 34.07% can also be solved using only one game piece, which are weighted towards lower number of moves.