Tietokoneshakki funktionaalisella ohjelmoinnilla

Abstract

Tämän opinnäytetyön aiheena on tutkia, kuinka tietokoneshakki voidaan toteuttaa funktionaalisella ohjelmoinnilla. Työssä käsitellään miten tietokoneshakit rakentuvat. Siinä tutkitaan pelipuun muodostamista, karsintaa ja hakualgoritmien toimintaa. Työ esittelee myös muutaman tunnetun shakkitietokoneen.

Työssä käytetään funktionaalista ohjelmointia. Työ tutkii hieman ohjelmointityylin pohjana olevaa lambdakalkyyliä ja kuvaa sen jälkeen funktionaalisen ohjelmoinnin ominaisuuksia. Näiden tietojen pohjalta on työssä kehitelty tietokoneshakki. Se on toteutettu Clojureohjelmointikielellä, joka perustuu vanhimpaan funktionaaliseen ohjelmointikieleen. Työ kuvaa, kuinka Clojurella voidaan esittää tietokoneshakki käyttäen funktionaalista ohjelmointitapaa.

Työn tuloksena toteutettu Tursas-shakkimoottori pelaa riittävän hyvin shakkia, mutta siihen jäi työn valmistumisen jälkeen vielä parantamisen varaa. Memoisaation ja laiskojen sekvenssien tehokkaalla käytöllä se saataisiin toimimaan tehokkaammin. Työssä huomattiin, kuinka hyvin funktionaalinen ohjelmointi tukee dynaamista ohjelmakehitystä. Siinä voidaan ohjelmoinnin abstraktiotaso nostaa korkeammalle, jolloin ei tarvitse kiinnittää paljoa huomiota toteutuksen yksityiskohtiin.

The purpose of this thesis was to study how computer chess can be implemented using functional programming. The thesis goes through how computer chess programs are constructed, it shows how chess game trees are created and pruned and it also shows a few common search algorithms. The work also covers the introduction to the most famous chess computers.

The study applied functional programming. It presents the basics of Lambda Calculus which is the foundation for functional programming languages. It then shows the most common characteristics of functional programming. A computer chess implementation was developed based on this knowledge. It was done using Clojure programming language which is based on the oldest functional programming language. Furthermore, the work describes how one can implement computer chess with Clojure by using functional programming style.

The Tursas chess engine which was developed as result of the thesis plays reasonable well game of chess but it leaves room for improvement. The engine could be made more efficient by using memoization and lazy sequences. It was also noted how well functional programming supports dynamic software development during the making of Tursas. The abstraction level of the programming could be made higher and as a result, one would not need to pay attention to the details of implementation.