Artificial Intelligence (AI) final project #01 - Summer 2024
||| In the name of Allah |||
---------------------------
Implementation of a digital Othello game using minimax (alpha-beta pruning) algorithm and Pygame library.
All functions and variables are written in a Python file Othello - Execute.py; run it to play.
Read the guides and explanations of this projcet in the Othello - Review.pdf file.
Minimax is a backtracking algorithm used in decision-making and game theory to determine the best move for a player, provided that your opponent also plays optimally. It is commonly employed in two-player turn-based games like Tic-Tac-Toe, Backgammon, Mancala, Chess and etc.
In Minimax the two players are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible (zero-sum).
For eaxmple in a board game (zero-sum game), every board state has a value associated with it. In a given state if the maximizer has upper hand then, the score of the board will tend to be some positive value. If the minimizer has the upper hand in that board state then it will tend to be some negative value. The values of the board are calculated by some heuristics which are unique for every type of game.
More guides and explanations:
- Link #01: GeeksForGeeks - Minimax
- Link #02: Youtube #1 - Minimax
- Link #03: Youtube #2 - Minimax
- Link #04: Aparat - Minimax
- Link #05: Youtube - Minimax for TicTocToe
Alpha-Beta pruning is not actually a new algorithm, but rather an optimization technique for the minimax algorithm. It reduces the computation time by a huge factor. This allows us to search much faster and even go into deeper levels in the game tree. It cuts off branches in the game tree which need not be searched because there already exists a better move available. It is called Alpha-Beta pruning because it passes 2 extra parameters in the minimax function, namely alpha and beta.
Let’s define the parameters alpha and beta with the pruning condition:
- Alpha: the best value that the maximizer currently can guarantee at that level or above.
- Beta: the best value that the minimizer currently can guarantee at that level or below.
- Pruning: for each node, if beta ≤ alpha, subtree of this node is pruned.
See the links below:
- Link #01: GeeksForGeeks - AlphaBeta Minimax
- Link #02: Youtube #1 - AlphaBeta Minimax
- Link #03: Youtube #2 - AlphaBeta Minimax
- Link #04: Aparat #1 - AlphaBeta Minimax
- Link #05: Aparat #2 - AlphaBeta Minimax
