Bonjour à tous !!
Ma problématique est de faire un programme en Arduino, où je joue à un jeu face à l'Arduino qui m'indique sur le moniteur série ce qu'il joue au coup suivant. Pour cela le programme doit analyser chacune de ses combinaisons qu'il peut jouer une par une en analysant toutes les combinaisons je peux jouer qui en découle, et choisi celle qui lui donne l'issue la moins défavorable si je joue le meilleur coup. En cas d'égalité il en sélectionne une au hasard.
L'idéal serai que le programme peut anticiper 2 coups dans l'arborescence des multitudes des cas possibles.
Comment je peux structurer le sketch d'un programme comme celui là ?
1 Like
Avant de parler d'intelligence artificielle, si on parlait d'intelligence tout court.
Tu peux structurer tes demandes pour les rendre claires à ceux qui les lisent.
La faisabilité dépend du jeu. Si c'est un jeu TRES simple, genre Tic Tac Toe, ou un jeu dont la stratégie gagnante est bien connue est bien définie, alors ça doit être faisable. Le 'doit' est lié aux contraintes de mémoire de l'Arduino, qui rendent le problème encore plus hasardeux. Tu peux les alléger avec un ESP32.
Pour un jeu plus complexe, genre Othello, ce doit être possible avec un ESP32.
Mais pas question de programmer un jeu d'échecs, de dames ou de go je pense...
En cherchant un peu sur Google, on tombe sur un programme d'échecs développé initialement sur un Arduino Méga, puis porté sur un ESP32 : donc ça existe, mais avec quelles performances ?
Quant à faire de l'IA sur un Arduino, c'est un peu pareil : l'ESP dispose de plus de mémoire, et il en faut !! J'ai commencé à travailler sur une bibliothèque pour faire tourner un perceptron multicouche sur ESP32 :
Je prépare la version 2...
Je pense que ça ne marcherait pas sur un Arduino, trop lent et trop peu de mémoire... sauf à rester sur des applications de démonstration, mais pas sur un jeu avec prise de décision.
Mais c'est juste mon avis...
Après, il existe des boards comprenant des processeurs spécialisés pour l'IA, comme le MaixDuino. Ils se programment en C ou en micro Python, ce qui permet de porter des algorithmes développés sur TensorFlow light.
Un peu de lecture ici
1 Like
Je me passe très volontiers des commentaires à la noix...
Je tiens à rester en programmation Arduino, l'exemple du jeu Othello est bien choisi.
L'utilisation de ESP32 m'est inconnu, c'est une carte que l'on branche sur l'arduino ? ou c'est une carte où l'on téléverse le script écris en arduino ?
Aussi je n'ai pas besoin que l' IA vois loin, seulement 2 coups en avance me suffit.
La difficulté pour moi est de formuler le squelette du code qui me permette d'avancer.
lesept777 c'est surement très bien un perceptron multicouche, mais c'est un peu compliqué pour moi.
1 Like
Il n’y a pas d’IA à proprement parler dans ce que vous décrivez (même si on peut en injecter)
C’est plus un bête min-max avec fonction d’évaluation de position
Cf Algorithme minimax — Wikipédia
La mémoire et/ou la rapidité peut être un souci (génération des coups suivants possibles sur plusieurs niveaux - ça peut monter vite en fonction du jeu et de la modélisation). La fonction d’évaluation peut être gourmande aussi (c’est la qu’on peut introduire éventuellement du ML mais c’est consommateur de forte ressources, sinon ça peut être un petit algo « simple » ça dépend du jeu)
1 Like
En effet, le jeu d'Othello est un jeu de stratégie dit 'à information complète' car chaque joueur voit le jeu de son opposant. Les algorithmes standards explorent l'arbre des coups possibles de chaque joueur, calculent une fonction de coût et choisissent l'option ayant le coût le plus élevé. Les algorithmes style minimax aident à accélérer l'exploration en évitant des branches sans intérêt.
Ca date des années 70-80.
Pas d'IA ici, mais un joli programme à la clé. Surtout si tu ajoutes une interface graphique pour afficher le tableau de jeu.
Tu peux chercher de l'aide sur internet. Google 'algorithme jeu othello' renvoie vers cette page :
https://www.ffothello.org/informatique/algorithmes/
1 Like
Je vous remercie tout 2 de l'intérêt des réponse vous apportez à mon projet.
C'est effectivement, JML et lesept, un algorithme minimax à information complete je souhaite faire.
Là je suis en train de faire le graphisme du jeu.
Ma plus grande difficulté est de formaliser l'arbre des coups possible à l'aide de variable en C++, quels sont les variables de bases je dois déclarer pour pouvoir faire l'algorithme, la schématique de l'algorithme est clair pour moi.
Exemple :
il y a 9 mouvements possibles, le code les étudies l'un après l'autre.
1er mouvement étudié, le code étudie les 9 autres mouvements du joueurs possible, il retiens celui qui lui est le plus négatif, et donne une "note" au 1er mouvement possible.
2eme mouvement étudié, idem. etc.
Après que les 9 mouvements ai été étudié, il compare les 9 notes et choisi celle qui est la plus élevé, en cas de note égale il en retiens une au hasard.
Cela est quand le code "voit" un coup à l'avance. Pour le code voit 2 coup à l'avance, le principe est le même mais je ne sais pas trop comment le formuler.
Quels sont les variables je dois déclarer pour faire cet algorithme ?
1 Like
imaginons que vous ayez des structures représentant une position:
// la dimension de l'échiquier pour Othello
const uint8_t nbLignes = 8;
const uint8_t nbCols = 8;
// ce que l'on peut avoir sur une case
enum t_case : uint8_t {caseVide, pionNoir, pionBlanc};
// l'échiquier
struct t_position {
t_case tableau[nbCols][nbLignes];
};
et une structure qui représente un coup - ici par exemple simplement modifier le statut d'une case
struct t_coup {
uint8_t ligne;
uint8_t colonne;
t_case coup;
};
vous pouvez alors avoir une fonction qui retourne une structure représentant une position pour un coup donné
t_position positionPourCoup(const t_coup& unCoup);
et une fonction qui évalue la solidité d'une position
int32_t fonctionCout(const t_position& unePosition);
il ne vous reste qu'à évaluer (en min ou max suivant le joueur) et à la profondeur souhaitée le coût pour l'ensemble des coups possibles pour une position donnée.
la profondeur, ça peut se traiter en récursif si on a assez de mémoire. ici je n'ai rien optimisé, une position fait 64 octets (on pourrait faire cela avec 18 octets en allouant que 2 bits par case). Donc attention à la mémoire. De la même façon ici un coup prend 3 octets, on pourrait affecter uniquement 3 bits pour les x et y (de 0 à 7) et garder 2 bits pour ce qu’on met sur la case (4 possibilités si, on en a besoin de 3)
1 Like
Merci beaucoup JML de ta réponse, l'utilisation d'une structure me sera très utile, jusque là je la remplaçait par une matrice qui avait la même utilité. L'utilisation de Struct en ressource mémoire est mieux que faire une matrice [nbCols][nbLignes][nb_Coups_possible] ?
J'ai vu tu mettais "&", cela est l'utilisation de pointeur, tu fais comme cela pour alléger la mémoire des variables de l'arduino ?
L'utilisation des deux fonctions est utile, et bien choisi, seulement je peux évaluer une position facilement, si la fonction "position pour coup" etudie le maximin de l'ensemble des coup résultant qui peuvent être jouer par le joueur si l'arduino joue un coup, ce détail me pose encore probleme.
Pour commencer, dans l'arborescence, je pense m'arreter déja là car après cela va faire beaucoup de combinaisons pour ce jeu, j'aurai déja une idée des ressources cela demande, et pourquoi pas continuer après comme m'a suggéré lesept sur une carte maixduino, car je veux vraiment le faire en language arduino.
Là j'en suis encore dans l'affichage sur un écran du jeu, j'avance bien et assez facilement.
1 Like
L’avantage d’une structure par opposition à un tableau simple est que vous pouvez traiter cela implicitement comme juste une variable. Par exemple faire a = b; pour copier dans a la structure b alors que ça ne fonctionne pas comme cela pour un tableau. Ça permet de simplifier le passage de paramètre aux fonctions ou le retour de plusieurs valeurs par une fonction.
Ensuite se pose la question de l’optimisation du passage par paramètre (par défaut une copie est créée). Pour éviter cette copie on peut passer le paramètre par référence en C++, c’est ce que fait le & dans la déclaration de type.
Étudiez comment fonctionne min max, vous générez le liste des coups possible pour une position donnée et évaluez la pertinence de chaque coup. Chaque coup conduit à une nouvelle position pour laquelle (récursivement) on peut appliquer la même approche sauf que c’est un coup pour l’autre joueur.
il y a de la littérature en ligne, par exemple (premier hit google) : Minimax Algorithm in Game Theory | Set 1 (Introduction) - GeeksforGeeks
1 Like
Deux remarques ici :
- Le langage Arduino : c'est du C ou du C++, avec des bibliothèques dédiées à l'Arduino, mais le langage de programmation n'a rien de vraiment spécial à Arduino
- MaixDuino : c'est une carte qui dispose d'un ESP32 (microcontrôleur double cœur) et d'un second processeur dédié à l'accélération des opérations typiques utilisées dans l'intelligence artificielle. Ce n'est pas parce que son nom se termine par 'duino' qu'il faut en déduire qu'il utilise le fameux 'langage Arduino' et pas les autres... Un ESP32 se programme de la même manière, en C/C++, via l'IDE Arduino (environnement de programmation et de compilation).
Donc, si tu veux faire de l'arduino, tu peux choisir une carte Arduino (nano, Uno, Mega, etc) ou un ESP32 ou un MaxDuino, ou toute autre carte compatible de l'IDE Arduino. Le choix de la carte sera fonction de ses performances : besoin mémoire, vitesse de calcul, nombre d'entrées/sorties, etc.
1 Like
J'ai regardé pour la carte ESP32, elle me semble bien pour faire ce je veux, et pas cher par rapport à une maixduino, seulement puis je brancher un écran TFT pour arduino dessus en branchant les pins dessus aux numéros j'indique sur le programme. Et aussi, il existe plusieurs modele de ESP32, est ce que le modele ESP32 38 pins ou ESP32 30 pins convient ?
1 Like
Je te remercie JML pour les précision tu me donnes, ainsi j'ai l'architecture du script pour commencer.
il faut adapter les pins pour leur fonctions suivant le type d'écran retenu et éventuellement la tension (l'ESP est en 3.3V, si l'écran a besoin de 5V il faudra effectuer la conversion de tension entre les 2)
1 Like
J'ai mis ici :
un exemple d'application avec un ESP32 et un écran TFT tactile.
1 Like
D'accord, j'ai vérifié l'ecran est compatible 3,3V et 5V, là je ne sais pas quel modele je dois choisir : ESP32-WROOM-32D ou ESP32-WROOM-32U ou bien une autre ?
Que signifie WROOM, U et D ??
C'est joli ce tu as fais sur les fractales Lesept.
1 Like
Merci... Des infos ici :
https://projetsdiy.fr/quelle-carte-esp32-choisir-developper-projets-diy-objets-connectes/
J'ai 5 possibilités par case, comment le déclarer pour alléger la mémoire au mieux ?
Dans "struct" j'ai fais comme tu m'as dis, et j'ai aussi une variable qui est rouge, bleu ou vert, donc 3 cas, comment la déclarer aussi au mieux pour alleger la mémoire ?
Faut je fasse une combinaison de boolean ? 5+3=8 donc 3 bits ?
J'ai choisi la ESP32.
1 Like
Sur un ESP32 commencez par 1 octet par case. Quand l'algo fonctionnera vous verrez bien s'il faut optimiser cela.
Pour coder 5 possibilités il faut 3 bits (c'est le plus proche, on peut coder 8 possibilités)
Vous avez 64 cases donc il faut 64x3 bits = 24 octets au mieux. ensuite il faudra des fonctions un peu intelligentes (simple calcul sur les indices) pour aller chercher les 3 bons bits en fonction du (x,y) du plateau car certains bits seront à cheval sur 2 octets.
si vous voulez éviter d'avoir à gérer cette complication, prenez 4 bits par case, ça fera 32 octets au lieu de 24 mais tous les bits tiennent dans un octet
Je ne sais pas comment on déclare en 3 bits ou 4 bits sans utiliser de boolean ou une fonction renvoie la valeur 0,1,2,3,4 en fonction de la combinaison des booleans.
Est ce la meilleurs méthode ou existe t il une méthode simple de déclaration de variable si on code en 4 bits? et pour le cas rouge, vert, bleu existe t il un une déclaration en 2 bits ou bien je dois faire en 4 bits aussi?
Ainsi soit je déclare en boolean et utilise une fonction ? soit je fais un énum ? soit il existe une déclaration 4 bits simple.