Board game AI and minimax algorithm
Nguyen, Viet Hoang (2022)
2022
All rights reserved. This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-2022060114050
https://urn.fi/URN:NBN:fi:amk-2022060114050
Tiivistelmä
The objective of this thesis was to develop a turn-based two-player board game called Dobutsu Shogi (Let’s catch the lion) and implement a simple AI using minimax algorithm with alpha-beta pruning optimization techinique. The game was a single-page web application built using web development technologies: ReactJS and Redux with Typescript. It provided two play modes: two users against each other and a user against a computer.
In the theoretical part, some of the most basic concepts of game theory were introduced and followed by the explanation of minimax algorithm with alpha-beta pruning variation. Furthermore, in the implementation part, the process of making the game and programming its AI was described in detail.
In the end, the goal to make Dobutsu Shogi board game and develop its simple AI was successful. Minimax algorithm implementation worked well, and its optimization technique alpha-beta pruning showed its effectiveness in terms of performance. However, the AI was using a quite poor static evaluation function, and as a result, users can still defeat it if they have a certain amount of experiece about the game.
In the theoretical part, some of the most basic concepts of game theory were introduced and followed by the explanation of minimax algorithm with alpha-beta pruning variation. Furthermore, in the implementation part, the process of making the game and programming its AI was described in detail.
In the end, the goal to make Dobutsu Shogi board game and develop its simple AI was successful. Minimax algorithm implementation worked well, and its optimization technique alpha-beta pruning showed its effectiveness in terms of performance. However, the AI was using a quite poor static evaluation function, and as a result, users can still defeat it if they have a certain amount of experiece about the game.