Puissance 4 en Python : Réactualisation de la compétition entre IA (0 à 9)

Suite à l’introduction d’une faible part d’aléatoire dans le codage des IA (voir article précédent), une mise à jour s’imposait :

Présentation des résultats : (en cours)

Sur 1 million de parties, les résultats bruts sont :

IA0 / IA0 / Nulles : 498 749 / 498 630 / 2 621
IA1 / IA0 / Nulles : 877 813 / 122 165 / 22
IA2 / IA0 / Nulles : 970 751 / 29 249 / 0
IA3 / IA0 / Nulles : 963 172 / 26 350 / 10 478
IA4 / IA0 / Nulles : 986 385 / 13 601 / 14
IA5 / IA0 / Nulles :
IA6 / IA0 / Nulles :
IA7 / IA0 / Nulles :
IA8 / IA0 / Nulles :
IA9 / IA0 / Nulles :

IA1 / IA1 / Nulles :
IA2 / IA1 / Nulles :
IA3 / IA1 / Nulles :
IA4 / IA1 / Nulles :
IA5 / IA1 / Nulles :
IA6 / IA1 / Nulles :
IA7 / IA1 / Nulles :
IA8 / IA1 / Nulles :
IA9 / IA1 / Nulles :

IA2 / IA2 / Nulles :
IA3 / IA2 / Nulles :
IA4 / IA2 / Nulles :
IA5 / IA2 / Nulles :
IA6 / IA2 / Nulles :
IA7 / IA2 / Nulles :
IA8 / IA2 / Nulles :
IA9 / IA2 / Nulles :

IA3 / IA3 / Nulles :
IA4 / IA3 / Nulles :
IA5 / IA3 / Nulles :
IA6 / IA3 / Nulles :
IA7 / IA3 / Nulles :
IA8 / IA3 / Nulles :
IA9 / IA3 / Nulles :

IA4 / IA4 / Nulles :
IA5 / IA4 / Nulles :
IA6 / IA4 / Nulles :
IA7 / IA4 / Nulles :
IA8 / IA4 / Nulles :
IA9 / IA4 / Nulles :

IA5 / IA5 / Nulles :
IA6 / IA5 / Nulles :
IA7 / IA5 / Nulles :
IA8 / IA5 / Nulles :
IA9 / IA5 / Nulles :

IA6 / IA6 / Nulles :
IA7 / IA6 / Nulles :
IA8 / IA6 / Nulles :
IA9 / IA6 / Nulles :

IA7 / IA7 / Nulles :
IA8 / IA7 / Nulles :
IA9 / IA7 / Nulles :

IA8 / IA8 / Nulles :
IA9 / IA8 / Nulles :

IA9 / IA9 / Nulles :

Bilan (Nombre de victoires franches) :

IA0 :
IA1 :
IA2 :
IA3 :
IA4 :
IA5 :
IA6 :
IA7 :
IA8 :
IA9 :

Code source sur GitHub.

Puissance 4 en Python

Introduction d’un peu de hasard au niveau des IA : Si plusieurs positions sont possibles (égalité de poids), l’IA tire au hasard parmi ces meilleures positions plutôt que de s’arrêter à la première dans la liste. Reste à voir ce que cela va changer au niveau de la compétition précédente.

Le codage des IA devient donc :

IA0 : Priorité H
IA1 : Priorité PH
IA2 : Priorités A4PH / A3PH / A2PH / PH
IA3 : Priorités B4PH / B3PH / B2PH / PH
IA4 : Priorités A4PH / B4PH / A3PH / B3PH / A2PH / B2PH / PH
IA5 : Priorités A4PH / B4PH / A3PH / B3PH / B2PH / A2PH / PH
IA6 : Priorités A4PH / B4PH / B3PH / A3PH / A2PH / B2PH / PH
IA7 : Priorités A4PH / B4PH / B3PH / A3PH / B2PH / A2PH / PH
IA8 : Priorités A4PH / B4PH / A2PH / B2PH / PH
IA9 : Priorités A4PH / B4PH / B2PH / A2PH / PH

Code source sur GitHub.

Puissance 4 en Python : Compétition entre intelligences artificielles

Dans un premier temps, l’objectif est de mettre au point une intelligence artificielle (IA) la meilleure possible pour jouer à Puissance 4, sans avoir à descendre en profondeur dans un arbre comme avec l’algorithme minimax ou alpha-bêta. Viendra ensuite le temps des arbres, puis de l’apprentissage…

Présentation des IA :

Codage de la stratégie :

H veut dire Hasard
P veut dire Poids des cases (il y a plus de possibilités d’alignements pour certaines cases)
AX veut dire Alignement de X pions (l’IA essaye d’aligner X pions ; les alignements « troués » de 2 ou 3 pions ne sont pas encore pris en compte)
BX veut dire Blocage de X pions (l’IA essaye d’empêcher l’adversaire d’aligner X pions ; les alignements « troués » de 2 ou 3 pions ne sont pas encore pris en compte)

IA0 : Priorité H
IA1 : Priorité P
IA2 : Priorités A4P / A3P / A2P / P
IA3 : Priorités B4P / B3P / B2P / P
IA4 : Priorités A4P / B4P / A3P / B3P / A2P / B2P / P
IA5 : Priorités A4P / B4P / A3P / B3P / B2P / A2P / P
IA6 : Priorités A4P / B4P / B3P / A3P / A2P / B2P / P
IA7 : Priorités A4P / B4P / B3P / A3P / B2P / A2P / P
IA8 : Priorités A4P / B4P / A2P / B2P / P
IA9 : Priorités A4P / B4P / B2P / A2P / P

Présentation des résultats :

Sur 1 million de parties (ou 10 000 pour des mécaniques répétitives bien que 2 suffiraient), les résultats bruts sont :

IA0 / IA0 / Nulles : 498 180 / 499 269 / 2 551
IA1 / IA0 / Nulles : 878 082 / 121 899 / 19
IA2 / IA0 / Nulles : 971 125 / 28 874 / 1
IA3 / IA0 / Nulles : 962 081 / 26 922 / 10 997
IA4 / IA0 / Nulles : 987 349 / 12 637 / 14
IA5 / IA0 / Nulles : 984 923 / 14 995 / 82
IA6 / IA0 / Nulles : 989 355 / 10 538 / 107
IA7 / IA0 / Nulles : 986 549 / 13 043 / 408
IA8 / IA0 / Nulles : 971 554 / 28 431 / 15
IA9 / IA0 / Nulles : 948 080 / 51 821 / 99

IA1 / IA1 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 10 coups)
IA2 / IA1 / Nulles : 10 000 / 0 / 0
IA3 / IA1 / Nulles : 10 000 / 0 / 0
IA4 / IA1 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA5 / IA1 / Nulles : 10 000 / 0 / 0
IA6 / IA1 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA7 / IA1 / Nulles : 10 000 / 0 / 0
IA8 / IA1 / Nulles : 10 000 / 0 / 0
IA9 / IA1 / Nulles : 5 000 / 0 / 5 000 (quand IA9 commence, IA9 gagne)

IA2 / IA2 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 4 coups)
IA3 / IA2 / Nulles : 0 / 5 000 / 5 000 (quand IA2 commence, IA2 gagne)
IA4 / IA2 / Nulles : 10 000 / 0 / 0
IA5 / IA2 / Nulles : 10 000 / 0 / 0
IA6 / IA2 / Nulles : 10 000 / 0 / 0
IA7 / IA2 / Nulles : 10 000 / 0 / 0
IA8 / IA2 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA9 / IA2 / Nulles : 0 / 10 000 / 0

IA3 / IA3 / Nulles : 0 / 0 / 10 000 *
IA4 / IA3 / Nulles : 0 / 5 000 / 5 000 (quand IA4 commence, IA3 gagne)
IA5 / IA3 / Nulles : 10 000 / 0 / 0
IA6 / IA3 / Nulles : 0 / 10 000 / 0
IA7 / IA3 / Nulles : 0 / 5 000 / 5 000 (quand IA7 commence, IA3 gagne)
IA8 / IA3 / Nulles : 5 000 / 0 / 5 000 (quand IA8 commence, IA8 gagne)
IA9 / IA3 / Nulles : 0 / 0 / 10 000 *

IA4 / IA4 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence perd en 17 coups)
IA5 / IA4 / Nulles : 10 000 / 0 / 0
IA6 / IA4 / Nulles : 0 / 0 / 10 000 *
IA7 / IA4 / Nulles : 5 000 / 0 / 5 000 (quand IA7 commence, IA7 gagne)
IA8 / IA4 / Nulles : 0 / 10 000 / 0
IA9 / IA4 / Nulles : 0 / 10 000 / 0

IA5 / IA5 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 13 coups)
IA6 / IA5 / Nulles : 0 / 10 000 / 0
IA7 / IA5 / Nulles : 0 / 10 000 / 0
IA8 / IA5 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence perd)
IA9 / IA5 / Nulles : 0 / 10 000 / 0

IA6 / IA6 / Nulles : 0 / 0 / 10 000 *
IA7 / IA6 / Nulles : 10 000 / 0 / 0
IA8 / IA6 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)
IA9 / IA6 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)

IA7 / IA7 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence perd en 19 coups)
IA8 / IA7 / Nulles : 10 000 / 0 / 0
IA9 / IA7 / Nulles : 0 / 5 000 / 5 000 (quand IA7 commence, IA7 gagne)

IA8 / IA8 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 8 coups)
IA9 / IA8 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne)

IA9 / IA9 / Nulles : 5 000 / 5 000 / 0 (l’IA qui commence gagne en 11 coups)

Bilan (Nombre de victoires franches) :

IA0 : 0
IA1 : 1
IA2 : 3
IA3 : 3
IA4 : 4
IA5 : 8
IA6 : 2
IA7 : 4
IA8 : 3
IA9 : 1

Sur les parties entre IA4, IA5, IA6 et IA7 : IA5 écrase les autres IA.

Si on compare les stratégies IA4 et IA5 (une seule inversion), B2P doit être avant A2P pour gagner. Si on compare les stratégies IA6 et IA7 (une seule inversion), B2P doit être avant A2P pour gagner. Si on compare les stratégies IA5 et IA7 (une seule inversion), A3P doit être avant B3P pour gagner. Si on compare les stratégies IA4 et IA6 (une seule inversion), A3P avant B3P n’apporte aucun gain (match nul).

Dans tous les cas, B2P doit être avant A2P pour gagner. A3P avant B3P ne prend tout son potentiel que si B2P est avant A2P. Supprimons A3P et B3P pour voir… (IA8 et IA9)


Petite réflexion pour le futur : Si on décompose une stratégie en micro-stratégies, cela nous amène comme ici à un codage (une sorte d’ADN de la stratégie). Je verrais bien comme développement futur quelque chose avec les algorithmes génétiques…


Quel est ce paradoxe ? IA5 écrase IA4, IA4 écrase IA8 et pourtant on n’arrive pas à départager IA5 et IA8. C’est un peu comme si des micro-logiques internes s’interpénétraient jusqu’à s’anéantir… un peu comme le mangeur de planeurs dans le jeu de la vie.

Code source sur GitHub.

* Extrait de WarGames (1983) :

GREETINGS PROFESSOR FALKEN

HELLO

A STRANGE GAME.
THE ONLY WINNING MOVE IS
NOT TO PLAY.

HOW ABOUT A NICE GAME OF CHESS?

Puissance 4 en Python

Bien que le travail sur l’IA ne soit pas encore fini (il reste quelques manques comme les alignements « troués » de 2 ou 3 pions), on a déjà des résultats intéressants (98 % de victoires pour l’IA / 2 % pour un jeu aléatoire). Notez que je n’ai pas encore implémenté les algorithmes minimax et alpha-bêta qui amèneront eux de la profondeur. Pour jouer contre l’ordinateur, le code source est sur GitHub.

Pour l’IA à base de minimax et d’alpha-bêta, voir le code de Christian Schmidt qui a fait ce travail en JavaScript.

Installation du scanner Epson Perfection V37 sous Debian 10

Brancher et allumer le scanner.

Dans la console :
lsusb (Pour récupérer ID idVendor:idProduct)
sudo nano /etc/udev/rules.d/60-sane-missing-scanner.rules

Compléter le fichier ci-dessus avec :
# Epson Perfection V37
ATTRS{idVendor}=="04b8", ATTRS{idProduct}=="014a", MODE="0664", GROUP="scanner", ENV{libsane_matched}="yes"

Télécharger le fichier iscan-perfection-v370-bundle-2.30.4.x64.deb.tar.gz depuis cette adresse. En cas de lien rompu, faire une nouvelle recherche depuis EPSON Download Center et adapter les instructions ci-dessous.

Dans la console :
cd Téléchargements
tar -zxvf iscan-perfection-v370-bundle-2.30.4.x64.deb.tar.gz
cd iscan-perfection-v370-bundle-2.30.4.x64.deb
sudo gdebi data/iscan-data_1.39.1-2_all.deb => IGNORER LE PROBLÈME
sudo gdebi core/iscan_2.30.4-2_amd64.deb
sudo gdebi plugins/iscan-plugin-perfection-v370_1.0.1-1_amd64.deb

Installation de Debian 10 (Buster)

RÉCUPÉRER L’ISO :

On peut télécharger l’ISO proposée sur la page d’accueil du site Debian (en haut à droite) mais l’installation par le réseau est assez longue. Pour accélérer l’installation, je préfère choisir de télécharger l’ISO du premier DVD. L’adresse de base https://cdimage.debian.org/debian-cd/ est à compléter en fonction de la version choisie :
https://cdimage.debian.org/debian-cd/current/amd64/iso-dvd/
https://cdimage.debian.org/debian-cd/current/i386/iso-dvd/

Pour tester les signatures des fichiers téléchargés, utiliser dans la console :
md5sum debian.iso (à adapter)
sha1sum debian.iso (à adapter)
sha256sum debian.iso (à adapter)
sha512sum debian.iso (à adapter)

CRÉER UNE CLÉ USB BOOTABLE :

Dans la console :
sudo fdisk -l (pour avoir la liste des disques)
Attention ! Danger !
sudo dd if=/chemin/debian.iso of=/dev/sdc bs=4M && sync (à adapter)

RENTRER DANS LE BIOS :

Au préalable : Débrancher le disque « données »
Sur mon PC : F2
Rentrer le mot de passe Administrateur
F8 (Démarrage) puis UEFI (Kingston DataTraveler)

DÉBUTER L’INSTALLATION :

Choisir Graphical Install
Select a language : Français
Choix de votre situation géographique : France
Configurer le clavier : Français
Nom de machine : À adapter
Domaine : Ne rien mettre
Mot de passe du superutilisateur (root) : Ne rien mettre afin de désactiver le compte root
Nom complet du nouvel utilisateur : À adapter
Identifiant pour le compte utilisateur : À adapter
Mot de passe pour le nouvel utilisateur : À adapter
Forcer l’installation UEFI : Non
Partitionner les disques : Manuel
Choisir un disque
Faut-il créer une nouvelle table de partition sur ce disque ? Oui
/dev/sda
Remarque : Dans ce qui suit, je mets pour swap la taille de la mémoire vive :
/dev/sda1 primaire (16 GB) F swap swap
/dev/sda2 primaire (40 GB) F ext4 /
/dev/sda5 logique (le reste en GB) F ext4 home
Faut-il appliquer les changements sur les disques ? Oui
Faut-il utiliser un miroir sur le réseau ? Oui
Pays du miroir de l’archive Debian : France
Miroir de l’archive Debian : ftp.fr.debian.org
Mandataire HTTP : Ne rien mettre
Souhaitez-vous participer à l’étude statistique sur l’utilisation des paquets ? Non
Logiciels à installer :
* Environnement de bureau Debian
* Xfce
* Serveur d’impression
* Utilitaires usuels du système
Installer le programme de démarrage GRUB sur le secteur d’amorçage : Oui
Périphérique où sera installé le programme de démarrage : /dev/sda
L’ordinateur reboote…
Bienvenue ! Le tableau de bord de Xfce démarre pour la première fois : Utiliser les paramètres par défaut

MODIFIER LE FICHIER SOURCES.LIST DES DÉPÔTS :

Dans la console :
sudo nano /etc/apt/sources.list

# deb cdrom:[Debian GNU/Linux 10]/ buster contrib main
# Mises à jour de sécurité
deb http://security.debian.org/debian-security buster/updates main contrib
deb-src http://security.debian.org/debian-security buster/updates main contrib
## Miroir Debian
# Dépôt de base : buster
deb http://ftp.fr.debian.org/debian/ buster main contrib
deb-src http://ftp.fr.debian.org/debian/ buster main contrib
# Mises à jour pour stable : buster-updates, previously known as ‘volatile’
deb http://ftp.fr.debian.org/debian/ buster-updates main contrib
deb-src http://ftp.fr.debian.org/debian/ buster-updates main contrib
# Rétroportages vers stable : buster-backports
deb http://ftp.fr.debian.org/debian/ buster-backports main contrib
deb-src http://ftp.fr.debian.org/debian/ buster-backports main contrib

SAUVEGARDER LE MBR ET LA TABLE DE PARTITIONS :

Dans la console :
Pour le MBR :
sudo dd if=/dev/sda of=~/mbr.img bs=512 count=1
Pour la table de partitions :
sudo sfdisk -d /dev/sda > table_partitions_sda_$(date +%Y%m%d).dmp
Se les envoyer par e-mail par exemple.

POUR METTRE LE SYSTÈME À JOUR :

Dans la console :
Pour récupérer les nouvelles listes de paquets :
sudo apt-get update
Pour réaliser une mise à jour :
sudo apt-get upgrade
Pour supprimer un paquet :
sudo apt-get remove nom_paquet
Pour supprimer des paquets qui ne sont plus nécessaires :
sudo apt-get autoremove

LES PAQUETS SUPPLÉMENTAIRES QUE J’INSTALLE :

Dans la console (c’est tellement plus rapide !) :
sudo apt-get install nom_paquet

audacity
calibre
filezilla
freecad
fritzing
gdebi
geany
ghex
gimp
gnome-calculator
golly
gqrx-sdr
inkscape
kazam
kdenlive
musescore
nbc
openscad
python3-pygame
python3-serial
shotwell
spyder3
stellarium
sweethome3d
thunderbird thunderbird-l10n-fr (supprimer lightning, l’extension de calendrier)

PROBLÈME DU VERROUILLAGE DE L’ÉCRAN :

Paramètres > Session et démarrage > Démarrage automatique d’application : Décocher Verrouilleur d’écran

Installer Arduino 1.0.6 sous Debian 10

Les sites officiels : Arduino et Debian

Dans la console :

Si le répertoire Arduino n’existe pas déjà, je le crée :
sudo mkdir /usr/share/arduino

Je télécharge la version 64 bits (à adapter) :
cd Téléchargements
wget -c http://downloads.arduino.cc/arduino-1.0.6-linux64.tgz

Je décompresse l’archive et l’installe à l’endroit voulu :
tar -zxvf arduino-1.0.6-linux64.tgz
sudo mv arduino-1.0.6 /usr/share/arduino

Je télécharge l’icône arduino et l’installe à l’endroit voulu :
wget http://entropie.org/3615/download/arduino.png
sudo mv arduino.png /usr/share/arduino

Pour effacer une version précédente d’Arduino (x à adapter) :
sudo rm -rf /usr/share/arduino/arduino-1.x.x

Pour intégrer le programme au menu de Xfce, je crée un fichier arduino-1.0.6.desktop dans le répertoire /usr/share/applications :
cd /usr/share/applications
sudo nano arduino-1.0.6.desktop

[Desktop Entry]
Type=Application
Name=Arduino 1.0.6
Comment=Un environnement de développement pour Arduino
GenericName=Create physical computing projects
Exec=/usr/share/arduino/arduino-1.0.6/arduino
Icon=/usr/share/arduino/arduino.png
Terminal=false
Categories=Development;Engineering;Electronics;
MimeType=text/x-arduino
Keywords=embedded electronics;electronics;avr;microcontroller;

Pour que le port série soit accessible et éviter de devoir utiliser Arduino en mode administrateur :
sudo usermod -a -G tty mon_identifiant (à adapter)
sudo usermod -a -G dialout mon_identifiant (à adapter)
Redémarrer.

Installer Arduino 1.8.9 sous Debian 10

Les sites officiels : Arduino et Debian

Dans la console :

Si le répertoire Arduino n’existe pas déjà, je le crée :
sudo mkdir /usr/share/arduino

Je télécharge la version 64 bits (à adapter) :
cd Téléchargements
wget -c http://downloads.arduino.cc/arduino-1.8.9-linux64.tar.xz

Je décompresse l’archive et l’installe à l’endroit voulu :
tar -xJf arduino-1.8.9-linux64.tar.xz
sudo mv arduino-1.8.9 /usr/share/arduino

Je télécharge l’icône arduino et l’installe à l’endroit voulu :
wget http://entropie.org/3615/download/arduino.png
sudo mv arduino.png /usr/share/arduino

Pour effacer une version précédente d’Arduino (x à adapter) :
sudo rm -rf /usr/share/arduino/arduino-1.x.x

Pour intégrer le programme au menu de Xfce, je crée un fichier arduino-1.8.9.desktop dans le répertoire /usr/share/applications :
cd /usr/share/applications
sudo nano arduino-1.8.9.desktop

[Desktop Entry]
Type=Application
Name=Arduino 1.8.9
Comment=Un environnement de développement pour Arduino
GenericName=Create physical computing projects
Exec=/usr/share/arduino/arduino-1.8.9/arduino
Icon=/usr/share/arduino/arduino.png
Terminal=false
Categories=Development;Engineering;Electronics;
MimeType=text/x-arduino
Keywords=embedded electronics;electronics;avr;microcontroller;

Pour que le port série soit accessible et éviter de devoir utiliser Arduino en mode administrateur :
sudo usermod -a -G tty mon_identifiant (à adapter)
sudo usermod -a -G dialout mon_identifiant (à adapter)
Redémarrer.