This is a small project for my Data Structure and Algorithms course. I would like to express my special thanks to my advisor, Dr. Vi Chi Thanh, for his guidance and support throughout this course.
ChessAIMinimax is a C# project that implements a chess game with an AI opponent using the Minimax algorithm and alpha-beta pruning.
- Visual Studio (2019 or later)
- .NET Framework
- Clone the repository:
git clone https://github.com/ThanhHungg19/ChessAIMinimax.git- Open the solution file
Chess.slnin Visual Studio.
- Set ChessUI as the startup project.
- Build the solution by clicking Build > Build Solution.
- Run the project by clicking Debug > Start Debugging or pressing F5.
The Minimax algorithm is a decision-making algorithm used in turn-based games. It operates by simulating all possible moves and their outcomes, assuming both players play optimally. The AI aims to maximize its score while minimizing the opponent's score.
Alpha-beta pruning enhances the Minimax algorithm by eliminating branches in the search tree that don't influence the final decision. It maintains two values, alpha and beta, representing the minimum score the maximizing player is assured and the maximum score the minimizing player is assured, respectively. Pruning occurs when these values indicate that a subtree cannot influence the final decision.
- Minimax:
$O(b^d)$ , where b is the branching factor and d is the depth of the tree. - Alpha-Beta Pruning: O(b^(d/2)) in the best case, effectively doubling the search depth achievable in the same amount of time as Minimax.
Both Minimax and Alpha-Beta Pruning have a space complexity of O(bd), where b is the branching factor and d is the depth of the tree, due to the need to store the entire search tree.