Shakkirobotin pelitekoäly rajallisen laskentatehon ympäristössä
Eskola, Janne; Haapamäki, Eetu; Jarkima, Jani (2019-06-18)
Eskola, Janne
Haapamäki, Eetu
Jarkima, Jani
J. Eskola; E. Haapamäki; J. Jarkima
18.06.2019
© 2019 Janne Eskola, Eetu Haapamäki, Jani Jarkima. Tämä Kohde on tekijänoikeuden ja/tai lähioikeuksien suojaama. Voit käyttää Kohdetta käyttöösi sovellettavan tekijänoikeutta ja lähioikeuksia koskevan lainsäädännön sallimilla tavoilla. Muunlaista käyttöä varten tarvitset oikeudenhaltijoiden luvan.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-201906202587
https://urn.fi/URN:NBN:fi:oulu-201906202587
Tiivistelmä
Shakki pelinä on kiinnostanut tiedemiehiä jo vuosisatoja. Peliä on käytetty historiassa erilaisten matemaattisten ongelmien ja varhaisten algoritmien havainnollistamiseen. Myös nykyaikana shakista on tullut laaja mielenkiinnon aihe varsinkin erilaisten tekoälyjen kehittämisessä. Shakki on pelinä liian monimutkainen ratkaistavaksi raa’alla laskentateholla, mikä tekee siitä erinomaisen kehitysalustan tekoälyjen tehokkuuden vertailemiseen.
Tässä työssä toteutettiin tekoäly shakkia pelaavalle robotille. Robotin työlle merkittävät osat koostuivat mekaanisesta käsivarresta ja kamerasta, joka tunnisti pelilaudan tilanteen konenäön avulla. Laiteympäristönä käytettiin erittäin rajallisen laskentatehon Raspberry Pi 3 -minitietokonetta.
Laskentateho vaikuttaa suoraan sekä algoritmin pelikykyyn että ihmisvastustajan kokemaan odotusaikaan siirtojen välillä, joten tekoälyn suorituskyky oli tärkeässä asemassa työn kannalta. Suorituskykyä testattiin vaiheittaisesti, aloittaen naiivista minimax-algoritmista siirtyen alfa-beta karsintaan ja sen erilaisiin optimisaatiotekniikoihin. Näitä eri algoritmillisia toteutuksia ja niiden suoritusaikoja vertailtiin keskenään, mikä auttoi määrittämään minimax-pohjaisten algoritmien soveltuvuutta vakuuttavan shakkitekoälyn luomiseen vähäisellä laskentateholla. Vertailuissa havaittiin selvästi perinteisen minimaxin hitaus suhteessa alfa-beta -karsintaan, varsinkin suuremmilla hakusyvyyksillä. Nopein suorituskyky ilman pelaamisen tason vähentymistä saavutettiin alfa-beta -karsintaa optimoimalla shakin avauskirjoja hyödyntämällä. Chess as a game has interested scientists for centuries. In history, the game has been used to demonstrate different kinds of mathematical problems and early algorithms. Even today, chess has become a subject of great interest, especially in the development of various artificial intelligence. Chess is too complex to solve by raw computing power, which makes it excellent platform to compare the strength of artificial intelligence.
In this work, an artificial intelligence was made for a chess robot. The parts of the robot that were relevant to the work consisted of a mechanical arm and a camera that recognized the situation of the game board with the help of machine vision. Raspberry Pi 3 was used as a hardware of the artificial intelligence.
Computational power directly effects the strength of the algorithm and the time experienced by the human opponent which makes the performance of the artificial intelligence very important factor for the project. Performance was tested step by step, starting with a stripped minimax algorithm and moving to alpha-beta pruning and its various optimization techniques. These different algorithmic implementations and their execution times were compared to help determining the suitability of minimax-based algorithms to create convincing chess artificial intelligence with limited computing power. Comparisons clearly showed the slowness of the traditional minimax relative to alpha-beta pruning, especially at higher search depths. The fastest performance without any reduction in the level of gaming was achieved by optimizing alpha-beta pruning by utilizing the chess opening books.
Tässä työssä toteutettiin tekoäly shakkia pelaavalle robotille. Robotin työlle merkittävät osat koostuivat mekaanisesta käsivarresta ja kamerasta, joka tunnisti pelilaudan tilanteen konenäön avulla. Laiteympäristönä käytettiin erittäin rajallisen laskentatehon Raspberry Pi 3 -minitietokonetta.
Laskentateho vaikuttaa suoraan sekä algoritmin pelikykyyn että ihmisvastustajan kokemaan odotusaikaan siirtojen välillä, joten tekoälyn suorituskyky oli tärkeässä asemassa työn kannalta. Suorituskykyä testattiin vaiheittaisesti, aloittaen naiivista minimax-algoritmista siirtyen alfa-beta karsintaan ja sen erilaisiin optimisaatiotekniikoihin. Näitä eri algoritmillisia toteutuksia ja niiden suoritusaikoja vertailtiin keskenään, mikä auttoi määrittämään minimax-pohjaisten algoritmien soveltuvuutta vakuuttavan shakkitekoälyn luomiseen vähäisellä laskentateholla. Vertailuissa havaittiin selvästi perinteisen minimaxin hitaus suhteessa alfa-beta -karsintaan, varsinkin suuremmilla hakusyvyyksillä. Nopein suorituskyky ilman pelaamisen tason vähentymistä saavutettiin alfa-beta -karsintaa optimoimalla shakin avauskirjoja hyödyntämällä.
In this work, an artificial intelligence was made for a chess robot. The parts of the robot that were relevant to the work consisted of a mechanical arm and a camera that recognized the situation of the game board with the help of machine vision. Raspberry Pi 3 was used as a hardware of the artificial intelligence.
Computational power directly effects the strength of the algorithm and the time experienced by the human opponent which makes the performance of the artificial intelligence very important factor for the project. Performance was tested step by step, starting with a stripped minimax algorithm and moving to alpha-beta pruning and its various optimization techniques. These different algorithmic implementations and their execution times were compared to help determining the suitability of minimax-based algorithms to create convincing chess artificial intelligence with limited computing power. Comparisons clearly showed the slowness of the traditional minimax relative to alpha-beta pruning, especially at higher search depths. The fastest performance without any reduction in the level of gaming was achieved by optimizing alpha-beta pruning by utilizing the chess opening books.
Kokoelmat
- Avoin saatavuus [32009]