Przeszukiwanie drzewa gier metodą Monte Carlo

licenciate
dc.abstract.enThe key to development of artificial intelligence lies in finding a good strategy algorithm for a decision process. The creation of advanced structures often leads to heavy calculations in terms of performance and eventually gives average results. The risk of a base algorithm being a weak foundation is smaller, the simpler and more elegant the solutions are.The purpose of this study is to implement a search algorithm of a decision tree for deterministic games using Monte-Carlo playouts. This method has shown to be successful in AlphaZero program who dominated all previous algorithms for the game of Go and Chess. The beginning of the work explains basic concepts, necessary to understand the method and then demonstrates a pure version of the algorithm, widely known as Monte Carlo Tree Search. The idea of simulations along with competent classification of game samples is concise and simple thus allowing quick understanding of the problem. Yet, a large number of iterations is required for the solution to converge to optimum implying the use of optimizations without which the algorithm could fail. All in all, the complexity increases depending on how long a game lasts and how many possibilities a game has. Implemented games are Tic-tac-toe 3x3, 5x5 and English Draughts (Checkers).pl
dc.abstract.plKluczowym elementem niezbędnym do rozwoju sztucznej inteligencji jest odnalezienie dobrej strategii w procesie podejmowania decyzji. Konstruowanie zaawansowanych struktur często prowadzi do zbyt złożonych wydajnościowo obliczeń i w rezultacie daje przeciętne skutki. Ryzyko, że bazowy algorytm jest słabym fundamentem, maleje, gdy wprowadza się prostsze i bardziej eleganckie rozwiązania.Głównym celem pracy jest implementacja algorytmu przeszukiwania drzewa decyzji w grach deterministycznych wspomagane symulacjami Monte-Carlo. Metoda odniosła duży sukces w programie AlphaZero, który zdominował wszystkie poprzednio istniejące programy do gry Go, jak i szachów. W pierwszej części pracy wprowadzone są podstawowe pojęcia potrzebne do zrozumienia tej metody, a następnie przedstawiona jest najprostsza wersja algorytmu przeszukiwania, powszechnie znanego pod nazwą Monte Carlo Tree Search. Idea wykorzystania symulacji i umiejętnej klasyfikacji próbek jest zwięzła i nieskomplikowana, pozwalając na szybkie zrozumienie problemu. Jednakże, aby rozwiązanie zbiegało się do optimum, wymagana jest duża liczba iteracji, co powoduje, że bez modyfikacji optymalizujących mogą być podjęte złe decyzje. Wszystko zależy od rodzaju gry, a dokładniej od tego ile jest możliwości oraz jak długo trwa jedna rozgrywka. Zaimplementowane gry to kółko krzyżyk 3x3, 5x5 i warcaby angielskie.pl
dc.affiliationWydział Fizyki, Astronomii i Informatyki Stosowanejpl
dc.areaobszar nauk ścisłychpl
dc.contributor.advisorGörlich, Andrzej - 135185 pl
dc.contributor.authorParuzel, Pawełpl
dc.contributor.departmentbycodeUJK/WFAISpl
dc.contributor.reviewerPłaczek, Wiesław - 131447 pl
dc.contributor.reviewerGörlich, Andrzej - 135185 pl
dc.date.accessioned2020-07-27T17:01:15Z
dc.date.available2020-07-27T17:01:15Z
dc.date.submitted2018-06-29pl
dc.fieldofstudyinformatykapl
dc.identifier.apddiploma-124410-198076pl
dc.identifier.projectAPD / Opl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/228696
dc.languagepolpl
dc.subject.engame tree, Monte-Carlo playouts, artificial intelligence, AlphaZero, Tic-tac-toe, Checkerspl
dc.subject.pldrzewo gry, symulacje Monte-Carlo, sztuczna~inteligencja, AlphaZero, kółko-krzyżyk, warcabypl
dc.titlePrzeszukiwanie drzewa gier metodą Monte Carlopl
dc.title.alternativeSearching through game tree using Monte-Carlo methodspl
dc.typelicenciatepl
dspace.entity.typePublication
dc.abstract.enpl
The key to development of artificial intelligence lies in finding a good strategy algorithm for a decision process. The creation of advanced structures often leads to heavy calculations in terms of performance and eventually gives average results. The risk of a base algorithm being a weak foundation is smaller, the simpler and more elegant the solutions are.The purpose of this study is to implement a search algorithm of a decision tree for deterministic games using Monte-Carlo playouts. This method has shown to be successful in AlphaZero program who dominated all previous algorithms for the game of Go and Chess. The beginning of the work explains basic concepts, necessary to understand the method and then demonstrates a pure version of the algorithm, widely known as Monte Carlo Tree Search. The idea of simulations along with competent classification of game samples is concise and simple thus allowing quick understanding of the problem. Yet, a large number of iterations is required for the solution to converge to optimum implying the use of optimizations without which the algorithm could fail. All in all, the complexity increases depending on how long a game lasts and how many possibilities a game has. Implemented games are Tic-tac-toe 3x3, 5x5 and English Draughts (Checkers).
dc.abstract.plpl
Kluczowym elementem niezbędnym do rozwoju sztucznej inteligencji jest odnalezienie dobrej strategii w procesie podejmowania decyzji. Konstruowanie zaawansowanych struktur często prowadzi do zbyt złożonych wydajnościowo obliczeń i w rezultacie daje przeciętne skutki. Ryzyko, że bazowy algorytm jest słabym fundamentem, maleje, gdy wprowadza się prostsze i bardziej eleganckie rozwiązania.Głównym celem pracy jest implementacja algorytmu przeszukiwania drzewa decyzji w grach deterministycznych wspomagane symulacjami Monte-Carlo. Metoda odniosła duży sukces w programie AlphaZero, który zdominował wszystkie poprzednio istniejące programy do gry Go, jak i szachów. W pierwszej części pracy wprowadzone są podstawowe pojęcia potrzebne do zrozumienia tej metody, a następnie przedstawiona jest najprostsza wersja algorytmu przeszukiwania, powszechnie znanego pod nazwą Monte Carlo Tree Search. Idea wykorzystania symulacji i umiejętnej klasyfikacji próbek jest zwięzła i nieskomplikowana, pozwalając na szybkie zrozumienie problemu. Jednakże, aby rozwiązanie zbiegało się do optimum, wymagana jest duża liczba iteracji, co powoduje, że bez modyfikacji optymalizujących mogą być podjęte złe decyzje. Wszystko zależy od rodzaju gry, a dokładniej od tego ile jest możliwości oraz jak długo trwa jedna rozgrywka. Zaimplementowane gry to kółko krzyżyk 3x3, 5x5 i warcaby angielskie.
dc.affiliationpl
Wydział Fizyki, Astronomii i Informatyki Stosowanej
dc.areapl
obszar nauk ścisłych
dc.contributor.advisorpl
Görlich, Andrzej - 135185
dc.contributor.authorpl
Paruzel, Paweł
dc.contributor.departmentbycodepl
UJK/WFAIS
dc.contributor.reviewerpl
Płaczek, Wiesław - 131447
dc.contributor.reviewerpl
Görlich, Andrzej - 135185
dc.date.accessioned
2020-07-27T17:01:15Z
dc.date.available
2020-07-27T17:01:15Z
dc.date.submittedpl
2018-06-29
dc.fieldofstudypl
informatyka
dc.identifier.apdpl
diploma-124410-198076
dc.identifier.projectpl
APD / O
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/228696
dc.languagepl
pol
dc.subject.enpl
game tree, Monte-Carlo playouts, artificial intelligence, AlphaZero, Tic-tac-toe, Checkers
dc.subject.plpl
drzewo gry, symulacje Monte-Carlo, sztuczna~inteligencja, AlphaZero, kółko-krzyżyk, warcaby
dc.titlepl
Przeszukiwanie drzewa gier metodą Monte Carlo
dc.title.alternativepl
Searching through game tree using Monte-Carlo methods
dc.typepl
licenciate
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
59
Views per month
Views per city
Krakow
14
Warsaw
8
Wroclaw
5
Gdansk
4
Gliwice
4
Ashburn
2
Dublin
2
Katowice
2
Lodz
2
Poznan
2

No access

No Thumbnail Available