Note: A French version of this README is available right after this section.
Pygame interface which allows you to play the Othello game with friends or against an AI.
Our goal was to apply the theoretical knowledge learned on these different so-called artificial intelligence algorithms such as min max or alpha beta, and analyze them statistically to understand which is the best and why?
- Node.js
- Docker
- Git
- GPG
- SonarQube
- GitHub
- Heroku
- Semantic Release
- Husky
- Commitlint
- Conventional Commits
- Python 3.X
- Pygame
- Using Minimax Algorithm for decision-making
- Optimizing with Alpha-Beta pruning
- Using memory with a transpose table to store evaluations of platter positions
- Time management with a timeout system
- Evaluation of tabletop positions via four personalized evaluation functions
git clone https://github.com/robjo82/othello-ai.git
cd othello-ai
pip install -r requirements.txt
python src/main.py- Player vs Player : Play against a friend on the same computer.
- Player vs AI : Play against an AI.
- AI vs AI : Watch two AIs play against each other.
Minimax:
Minimax is a decision search algorithm for two-player games (like chess, checkers, etc.). The algorithm evaluates possible moves and chooses the best move, assuming that the opponent will also play optimally. Minimax uses a game tree to represent possible moves and a depth system to limit the search.
In the Minimax algorithm, two types of nodes are evaluated:
“Maximizing” nodes: The AI searches for the move with the maximum value. “Minimizing” nodes: The AI anticipates that the opponent will choose the move with the minimum value.
Alpha-Beta Pruning:
Alpha-Beta pruning is an optimization of the Minimax algorithm that reduces the number of nodes evaluated in the search tree. The idea is to maintain two values, Alpha and Beta, which respectively represent the best option for the player so far and the best option for the opponent. When traversing the tree, branches are "cut" or ignored as soon as it is obvious that they will not produce a better decision than the one already found.
Alpha-Beta pruning allows you to search deeper in the game tree with the same calculation time, or reduce the time needed for a given depth.
Both algorithms are often used in game programs to help AI decide which moves to make. They are particularly effective when the game has a limited set of possible moves and clearly defined rules for winning or losing.
main: Main branch of the project. It is protected and can only be modified through pull requests. It is automatically deployed to Heroku.develop: Development branch. It is protected and can only be modified through pull requests. It can be considered as a pre-production branch, and deployed to Heroku if needed.feature/<ticket_number>: Feature branch. Created fromdevelopand merged back intodevelopthrough a pull request.hotfix/<ticket_number>: Hotfix branch. Created frommainand merged back intomainthrough a pull request.
- Commit messages should be written in English, in the present tense.
- Commit messages should be written using the Conventional Commits convention, i.e., following the format:
<type>[optional scope]: <description> [optional issue]. - Adhering to these conventions allows for automated version management and package publishing.
- Pull requests should be written in English, in the present tense.
- A pull request template is available in the
.github/PULL_REQUEST_TEMPLATE/pull_request_template.mddirectory. - Pull requests should be assigned to a reviewer.
Contributions are welcome! Please first create a branch with the name of the feature you want to add, then create a pull
request to merge your branch into the develop branch.
This project is under the MIT license - see the LICENSE file for more details.
Interface Pygame qui vous permet de jouer au jeu Othello avec des amis ou contre une IA.
Notre objectif était d'appliquer les connaissances théoriques apprises sur ces différents algorithmes dits d' intelligence artificielle, comme Minimax ou l'élagage Alpha Beta, et de les analyser statistiquement pour comprendre lequel est le meilleur et pourquoi ?
- Node.js
- Docker
- Git
- GPG
- SonarQube
- GitHub
- Heroku
- Semantic Release
- Husky
- Commitlint
- Conventional Commits
- Python 3.X
- Pygame
git clone
cd othello-ai
pip install -r requirements.txt
python src/main.py- Joueur contre Joueur : Jouez contre un ami sur le même ordinateur.
- Joueur contre IA : Jouez contre une IA.
- IA contre IA : Regardez deux IA jouer l'une contre l'autre.
Minimax :
Minimax est un algorithme de recherche de décision pour les jeux à deux joueurs (comme les échecs, les dames, etc.). L'algorithme évalue les coups possibles et choisit le meilleur coup, en supposant que l'adversaire jouera également de manière optimale. Minimax utilise un arbre de jeu pour représenter les coups possibles et un système de profondeur pour limiter la recherche.
Dans l'algorithme Minimax, deux types de nœuds sont évalués :
Nœuds "Maximisants" : L'IA recherche le coup ayant la valeur maximale.
Nœuds "Minimisants" : L'IA anticipe que l'adversaire choisira le coup ayant la valeur minimale.
Élagage Alpha-Beta :
L'élagage Alpha-Beta est une optimisation de l'algorithme Minimax qui réduit le nombre de nœuds évalués dans l'arbre de recherche. L'idée est de maintenir deux valeurs, Alpha et Beta, qui représentent respectivement la meilleure option pour le joueur jusqu'à présent et la meilleure option pour l'adversaire. Lors du parcours de l'arbre, les branches sont " coupées" ou ignorées dès qu'il est évident qu'elles ne produiront pas une meilleure décision que celle déjà trouvée.
L'élagage Alpha-Beta permet de rechercher plus en profondeur dans l'arbre de jeu avec le même temps de calcul, ou de réduire le temps nécessaire pour une profondeur donnée.
Les deux algorithmes sont souvent utilisés dans les programmes de jeu pour aider l'IA à décider quels coups faire. Ils sont particulièrement efficaces lorsque le jeu a un ensemble limité de coups possibles et des règles clairement définies pour gagner ou perdre.
main: Branche principale du projet. Elle est protégée et ne peut être modifiée que par le biais de pull requests. Elle est automatiquement déployée sur Heroku.develop: Branche de développement. Elle est protégée et ne peut être modifiée que par le biais de pull requests. Elle peut être considérée comme une branche de pré-production, et déployée si besoin sur Heroku.feature/<numéro du ticket associé à la tache>: Branche de fonctionnalité. Elle est créée à partir dedevelopet fusionnée dansdeveloppar le biais d'une pull request.hotfix/<numéro du ticket associé à la tache>: Branche de correction. Elle est créée à partir demainet fusionnée dansmainpar le biais d'une pull request.
- Les messages de commit doivent être rédigés en anglais, au présent.
- Les messages de commit doivent être rédigés en utilisant la convention Conventional Commits, c'est-à-dire en respectant le format suivant :
<type>[optional scope]: <description> [optional issue]. - Le respect de ces conventions permet d'automatiser la gestion des versions et la publication du package.
- Les pull requests doivent être rédigées en anglais, au présent.
- Un template de pull request est disponible dans le dossier
.github/PULL_REQUEST_TEMPLATE/pull_request_template.md. - Les pull requests doivent être assignées à un reviewer.
Les contributions sont les bienvenues ! Veuillez d'abord créer une branche avec le nom de la fonctionnalité que vous
souhaitez ajouter, puis créer une pull request pour fusionner votre branche dans la branche develop.
Ce projet est sous licence MIT - voir le fichier LICENSE pour plus de détails.