University of Oulu

Shakkirobotin pelitekoäly rajallisen laskentatehon ympäristössä

Saved in:
Author: Eskola, Janne1; Haapamäki, Eetu1; Jarkima, Jani1
Organizations: 1University of Oulu, Faculty of Information Technology and Electrical Engineering, Department of Computer Science and Engineering, Computer Science
Format: ebook
Version: published version
Access: open
Online Access: PDF Full Text (PDF, 1.1 MB)
Pages: 37
Persistent link: http://urn.fi/URN:NBN:fi:oulu-201906202587
Language: Finnish
Published: Oulu : J. Eskola; E. Haapamäki; J. Jarkima, 2019
Publish Date: 2019-06-20
Thesis type: Bachelor's thesis
Description:

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ä.

Artificial intelligence of a chess robot in a system with limited computational power

Abstract

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.

see all

Subjects:
Copyright information: © Janne Eskola; Eetu Haapamäki; Jani Jarkima, 2019. This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.