Chess with Artificial Intelligence
Introduction to the "AI and Games" Course
This project was developed as part of the "AI and Games" course, where I learned the basics of artificial intelligence algorithms applied to games. The course introduced techniques such as Breadth-First Search (BFS), Depth-First Search (DFS), and the A* algorithm to solve classic problems like the N-Queens, Knight's Tour, and Sliding Puzzle. These practical exercises provided a foundational understanding of solution-finding in strategy games.
A detailed report on these concepts is available via the button below for those interested in learning more (in french).
Final Project: Chess Game with AI
The final project is a chess game where players can compete against an artificial intelligence (AI). Developed in C with the SDL library for graphics, this project allowed me to apply learned concepts while tackling real-world challenges of creating a complete game.
Key Features :
Game Engine :
Implementation of chess rules, including the movement of all pieces (pawn, rook, knight, bishop, queen, and king).
Advanced rules such as castling and en passant were not implemented due to time constraints.
Use of a matrix to store and manage piece positions and movements.
Graphical Interface :
Dynamic rendering of the chessboard and pieces using SDL.
After each turn, the board updates dynamically by clearing and redrawing all pieces in their new positions.
AI Using Minimax Algorithm :
The AI simulates strategic thinking by generating a decision tree of potential moves.
A linked list structure is used to build this tree, where each node represents a new game state after a move.
The Minimax algorithm enables the AI to maximize its advantage while anticipating the opponent’s best responses.
Technical Details of the AI
The AI was designed to simulate strategic thinking using the Minimax algorithm.
Here’s how it works:
Move Generation :
From the current position, the AI explores all legal moves.
Each move generates a new game state, which is added to a linked list to form a decision tree.
Position Evaluation :
Each game state is assigned a score based on factors such as the value of captured pieces and the king’s safety.
A high score indicates a favorable position for the AI, while a low score reflects a disadvantageous position.
Search Optimization :
Moves are sorted by relevance (from best to worst), allowing the AI to focus its calculations on the most promising scenarios.
This approach enhances the search depth without significantly affecting performance.
Depth Search :
The algorithm alternates between maximizing scores for the AI and minimizing scores to simulate the opponent’s decisions.
Excessive depth slows down gameplay, so a balance was struck between performance and calculation time.
Best Move Selection :
After reaching the maximum search depth, the algorithm backtracks to choose the move that leads to the most favorable outcome.
Results
Despite implementing optimizations like move sorting for deeper searches and refined score calculations, the AI remains underperforming. It can be easily defeated by players with a basic understanding of chess strategy. These limitations stem from the constraints of the Minimax algorithm, including the lack of pruning or use of strategic databases.
Possible Improvements
Feature Enhancements : Adding castling, en passant, and pawn promotion would enrich the gameplay and provide a more complete chess experience.
Calculation Optimization : Integrating alpha-beta pruning would reduce computation times and allow deeper exploration of possible moves.
Strategic Databases : Using known move databases could enhance the AI’s efficiency in openings and mid-games.
Machine Learning Integration : Employing machine learning techniques, such as neural networks, would enable the AI to improve by playing against itself or analyzing existing games.
These improvements would not only enhance the AI’s strategic capabilities but also make the project more robust and competitive.
Access the Chess with AI Project
The complete source code for this project is available on my GitHub repository. There, you can explore the implementation of chess rules, the graphical interface, and the Minimax algorithm used for the AI.
Click the button below to view the project: