Vous avez du temps pour coder ? concours d'Intelligence Artificielle - Page 7

malloc/realloc/free marchent très bien

Ca, par contre, je ne connais pas, n'ayant jamais utilisé ceci, puisque mon apprentissage du C resta dans le cadre scolaire ... mais bon, j'ai facilement de quoi apprendre, donc ça ira.
Le problème, en fait, concerne ce qui est spécifique à la TI et la compatibilité avec le reste : pour permettre aux IA en TI-Basic de jouer, il faut que je sache gérer, en C, la variable colonne de manière à ce qu'elle puisse être gérée par un programme en TI-Basic.

Pour ton IA tu n'en as pas besoin, et si c'est seulement pour débugger tu as clrscr()/printf()/ngetchx() qui sont relativement standard.

Il n'y a pas que mon IA à porter, il y a aussi l'arbitre (fini depuis longtemps) ... arbitre que je pourrai alors vous fournir compilé, sans les sources, pour que chacun puisse tester son IA dans son coin sans être influencé par mon algo.

Aussi rapide qu'en asm, mais fais quand même attention à prendre des largeurs puissances de 2 pour les matrices...

Oui oui, bien sûr, t'inquiète, j'ai l'habitude de ces histoires d'alignement !

@++

malloc/realloc/free : on les utilise assez rapidement, même à l'école, donc ça devrait venir
Pour la variable colonne, ça doit se trouver dans la doc de TIGCC - peux pas te dire où, j'ai pas lu -
A la limite, t'es obligé de porter l'arbirtre ? ça t'économisera la recherche de l'exécution d'un prgm en C.
A mon avis, il parlait plutôt des optimisations que des alignements

Bon déjà si tu n'utilises pas malloc et free tu ne connais pas vraiment le C.
Ensuite, les principaux trucs que tu as à savoir sont:

[li]l'adresse de l'écran est LCD_MEM ($4c00 mais t'as pas besoin de le savoir en C)
[li]chaque pixel est representé par un bit et comme le buffer est le même pour 89 et 92+, ça te fait LCD_WIDTH=240*128/8=3840 octets.
[li]Tu peux utiliser les fonctions standarts de stdio.h, mais tout est documenté dans la doc (ici ou plus simplement dans le .chm fourni avec TIGCC) presque complète de TIGCC. Pour la gestion des fichiers vat.h, pour l'affichage graph.h, le clavier kbd.h. Voilà il suffit de regarder l'index des fonctions pour choisir celles dont tu as besoin.

Tu n'as même pas besoin de connaître la représentation interne de l'écran. Il y a des fonctions d'affichages de sprites et de caractères

malloc/realloc/free : on les utilise assez rapidement, même à l'école, donc ça devrait venir

Nan nan, pas à PG : on en fait en 1A pour apprendre l'algorithmie, et c'est tout ...
En 2A, c'est du Matlab, c'est-à-dire de l'utilisation de logiciel numérique sans réelle programmation.

A la limite, t'es obligé de porter l'arbirtre ? ça t'économisera la recherche de l'exécution d'un prgm en C.

Faire l'arbitre en C permet :
1/ de l'accelérer un peu
2/ de cacher les sources, donc de pouvoir être fourni à tous les participants du concours tout en les laissant chercher par eux-même

A mon avis, il parlait plutôt des optimisations que des alignements

Je ne connais pas les optimisations du C, mais je suppose que comme en Asm x86, mieux vaut faire commencer chaque ligne de tableau à une adresse multiple de 4 (d'où des lignes en 4*n, c'est que que j'appelle 'alignement'), mais avec des lignes en 2^n, la transformation (ligne;colonne) <=> (adresse linéaire) est en effet plus rapide ...

@++

Nan nan, pas à PG : on en fait en 1A pour apprendre l'algorithmie, et c'est tout ...

Vous apprenez l'algorithmie et vous avez jamais besoin de malloc? Donc je présume que vous avez jamais fait d'arbres ou de structures de données autres que le tableau de taille prédéfinie?

Faire l'arbitre en C permet :
1/ de l'accelérer un peu 2/ de cacher les sources, donc de pouvoir être fourni à tous les participants du concours tout en les laissant chercher par eux-même

C pas forcément un problème, surtout le 2)... Si on n'est pas capable de détecter si on a gagné, alors on ne peut évidemment pas faire une IA. Et y a tjs la solution de "protéger" ton prog, même si c loin d'être infaillible (mais c pas le but, et de toute façon un prog C n'est pas infaillible non plus de ce point de vue là).

Je ne connais pas les optimisations du C, mais je suppose que comme en Asm x86, mieux vaut faire commencer chaque ligne de tableau à une adresse multiple de 4 (d'où des lignes en 4*n, c'est que que j'appelle 'alignement'), mais avec des lignes en 2^n, la transformation (ligne;colonne) <=> (adresse linéaire) est en effet plus rapide ...

Il n'y a pas de problème d'alignement sur 68000, mais les types de données différents de (unsigned-)char doivent être à une adresse paire sinon plantage (mais ça le compilo s'en occupe à ta place ).

@+++

matlab, c'est aussi de la programmation... On peut même tranformer son code en C... Et il utilise des libs du commerce programmées en C

Vous apprenez l'algorithmie et vous avez jamais besoin de malloc? Donc je présume que vous avez jamais fait d'arbres ou de structures de données autres que le tableau de taille prédéfinie?

En fait, si, maintenant que j'y repense, on a bien vu malloc, mais mal (le prof était totalement Moisi ... il l'est toujours, mais je ne l'ai plus #soulage# ... tiens, il n'y a pas de smiley pour le soulagement ?).
Avec ça, on a vu les listes chaînées et les tableaux dynamiques (que j'ai utilisés pour mon projet d'Info sur les algorithmes génétiques).

Faire l'arbitre en C permet :
1/ de l'accelérer un peu 2/ de cacher les sources, donc de pouvoir être fourni à tous les participants du concours tout en les laissant chercher par eux-même

C pas forcément un problème, surtout le 2)... Si on n'est pas capable de détecter si on a gagné, alors on ne peut évidemment pas faire une IA. Et y a tjs la solution de "protéger" ton prog, même si c loin d'être infaillible (mais c pas le but, et de toute façon un prog C n'est pas infaillible non plus de ce point de vue là).

Comment peut-on planquer les sources d'un programme en TI-Basic ?
Mais ceci ne m'empêchera de tenter le portage en C pour l'accelérer, bien que ce ne soit pas critique, puisque l'arbitre se contente de vérifier les alignements immédiats.

Il n'y a pas de problème d'alignement sur 68000, mais les types de données différents de (unsigned-)char doivent être à une adresse paire sinon plantage (mais ça le compilo s'en occupe à ta place ).

Woki, merci de l'info.
Il n'y a pas de données en 32 bits ?

matlab, c'est aussi de la programmation... On peut même tranformer son code en C... Et il utilise des libs du commerce programmées en C

En TD de Méthodes numériques, on se contente d'utiliser des programmes déjà faits, et éventuellement de modifier légèrement la loi physique pour en voir l'effet, rien de plus ...

@++

En fait, si, maintenant que j'y repense, on a bien vu malloc, mais mal (le prof était totalement Moisi ...)

Avec un peu de chance vous n'avez peut-être pas vu free

Comment peut-on planquer les sources d'un programme en TI-Basic ?

Par exemple :

Loop
EndLoop
ClrIO

puis tu hex-édites l'offset de EndLoop une fois tokenizé pour le faire pointer après ClrIO et tu remplaces ClrIO par une commande invalide. Enfin ça se fait, quoi (faut juste avoir lu la doc de TIGCC sur l'estack).

Woki, merci de l'info. Il n'y a pas de données en 32 bits ?

Si, mais il les lit par paquets de 16 bits (donc oui, c pas un processeur 32 bits).

Avec un peu de chance vous n'avez peut-être pas vu free

Si je me souviens bien des rôles respectifs de malloc et free (le second annulant l'effet du premier), alors si, on a bien free ... une semaine après avoir vu malloc !
Et bien évidemment, la semaine où on a vu malloc, on a fait le programme d'application ...

Par exemple :

Loop
EndLoop
ClrIO

puis tu hex-édites l'offset de EndLoop une fois tokenizé pour le faire pointer après ClrIO et tu remplaces ClrIO par une commande invalide. Enfin ça se fait, quoi (faut juste avoir lu la doc de TIGCC sur l'estack).

Tokenisé ???
n code modifié (en repointant le EndLoop) n'est-il pas équivalent à :Goto debut ClrIO Lbl debutEt au niveau du code Asm, to?
Et en quoi le fait de mettre une commande invalide cache le code ? En faisant planter l'AMS je suppose ...

Si, mais il les lit par paquets de 16 bits (donc oui, c pas un processeur 32 bits).

Au niveau de l'Asm, il n'y a donc que des bytes et des words, je suppose ...

@++

Non, il y a des opérations sur 32 bits, mais elles sont plus lentes que leurs homologues 16/8 bits.

Mais il n'y a pas la multiplication/division sur 32 bits.

La multiplication fournit quand même un résultat 32 bits, et le numérateur de la division est sur 32 bits.

Au fur et à mesure que j'implémente mon IA en TI-Basic, je trouve en live des optimisations Asm ... qui ne me servent pas vraiment ...
Aussi, je crois que je vais directement tout refaire en Asm, surtout que ce n'est que de la programmation interne, exception faite de la gestion de la variable colonne.
Par contre, pour l'arbitre, il y a de l'affichage graphique et de la gestion de programmes (lancer les joueurs présents dans divers dossiers), donc pas glop en Asm ...
Je pense que le mieux à faire, pour l'arbitre, est de laisser la partie graphique comme elle est (en TI-Basic), et d'appeler le programme en Asm qui détermine si un des joueurs gagne.

Mais bon, afin de voir si mon IA n'est pas trop bête, je vais d'abord finir de l'implémenter en TI-Basic, ajouter quelques éléments de débug graphique, et la faire jouer contre elle-même, pour voir si elle joue les même coups que moi j'aurais fait.
D'ailleurs, je crois que je vais améliorer l'arbitre en lui faisant faire un log de chaque partie, ça peut être extrêmement utile !

@++

Question par rapport au post initiale : qqn a déjà réussi à faire un "bot" capable de tenir une conversation de base (à part le bot de telchar que tout le monde connait mais dont on est pas prêt d'avoir les sources)

Laëtitia en son temps.

Hop là, petit repêchage du topic juste avant qu'il se fasse attraper par les méchants cadenas !

Je refais une synthèse (complétée et remise à jour) du comportement que devront avoir les IA et les interface pour permettre à un humain de jouer (je qualifierai cependant génériquement le tout d'IA) ...

* Le jeu de Puissance 4 (rappel : 7 colonnes et 6 lignes) se joue sur TI 89/92+/V200
* Les IA peuvent être programmées en n'importe quel langage acceptée par ces calculatrices (TI-Basic, C, Asm)
* Les IA sont lancées à tour de rôle par un méta-programme, l'arbitre
* L'IA dispose d'un répertoire complet de nom quelconque pour y faire ce qu'elle veut
* Par défaut, le programme principal de l'IA s'appelle joueur(), mais n'importe quel autre nom peut être choisi, il suffit d'en avertir le programme arbitre (ceci n'est pas de votre ressort, vous n'avez pas à vous en occuper)
* Le programme joueur() (ou tout autre nom) ne devra pas utiliser d'arguments
* Pour communiquer avec l'arbitre, l'IA utilise 2 variables appelées par défaut colonne (qui servira toute la partie) et nom (qui ne servira qu'au début) ; là aussi, d'autres noms peuvent être choisis
* C'est au programme joueur de gérer sa représentation de la partie en cours, en sachant uniquement dans quelle colonne vient de jouer son adversaire

* L'arbitre se charge de compléter les variables colonne et nom de l'IA qui va jouer, puis lance le programme principal joueur()
* Une fois lancé (le répertoire courant est celui de l'IA), joueur() analyse les variables colonne et nom, ainsi que toutes les variables de son répertoire qu'il aura jugé bon de créer pour enregistrer l'état de la partie, puis modifie en conséquence les variables colonne et nom avant de se terminer normalement
* Une fois le programme joueur() terminé, l'arbitre récupère les variables colonne et nom modifiées et les vérifie, met à jour l'affichage graphique, avant de recommencer le cycle pour l'autre IA

* Lorsque joueur() est lancé, la variable colonne contient une valeur numérique (type NUM) entière comprise inclusivement entre -1 et 10

* Si colonne = -1 :
>> l'IA sait qu'elle est le joueur 2 (pions X) et qu'une nouvelle partie a été lancée
>> la variable nom contient une valeur numérique valant soit 1 (jeu sur 89), soit 2 (jeu sur 92+/V200)
>> la nouvelle partie n'étant pas encore commencée, joueur() doit en profiter pour initialiser ses variables
>> au moment où joueur() se termine et rend la main à l'arbitre, la variable colonne doit toujours valoir -1, et la variable nom doit contenir une chaîne de caractère nommant l'IA et faisant au maximum N caractères, N dépendant de la taille de l'écran de la calculatrice, donc dépend de la valeur de nom (1 ou 2) au moment du lancement de joueur() (je n'ai pas terminé la partie graphique de l'arbitre, donc je ne sais pas encore combien vaudront N, désolé ...)

* Si colonne = 0 :
>> l'IA sait qu'elle est le joueur 1 (pions O) et qu'une nouvelle partie a été lancée
>> la variable nom contient une valeur numérique valant soit 1 (jeu sur 89), soit 2 (jeu sur 92+/V200)
>> la nouvelle partie venant de commencer, joueur() doit en profiter pour initialiser ses variables, avant de jouer le premier coup
>> au moment où joueur() se termine et rend la main à l'arbitre, la variable colonne doit contenir une valeur numérique entière comprise inclusivement entre 1 et 7, et désignant le numéro de la colonne jouée (les colonne sont numérotées normalement d'un bord à l'autre), et la variable nom doit contenir une chaîne de caractère nommant l'IA et faisant au maximum N caractères, N dépendant de la taille de l'écran de la calculatrice

* Si colonne est compris inclusivement entre 1 et 7 :
>> la variable colonne contient le numéro de la colonne venant d'être jouée par l'adversaire
>> au moment où joueur() se termine et rend la main à l'arbitre, la variable colonne doit contenir le numéro de la colonne que l'IA décide de jouer, tandis que la variable nom n'a dorénavant plus d'utilité

* Si colonne = 8 :
>> l'IA sait qu'elle vient de gagner et que la partie est finie
>> si nom = "N", l'IA a gagné par victoire 'normale', alors que si nom = "D", l'IA a gagné par disqualification de l'adversaire
>> la partie venant de s'achever, joueur() doit en profiter pour effacer ses variables au besoin

* Si colonne = 9 :
>> l'IA sait qu'elle vient de perdre et que la partie est finie
>> si nom = "N", l'IA a perdu par victoire 'normale' de l'adversaire, alors que si nom = "D", l'IA a perdu par disqualification
>> la partie venant de s'achever, joueur() doit en profiter pour effacer ses variables au besoin

* Si colonne = 10 :
>> l'IA sait qu'il y a match nul et que la partie est finie
>> la partie venant de s'achever, joueur() doit en profiter pour effacer ses variables au besoin

* Si une IA ne respecte pas les règles venant d'être définies sur la gestion des variables colonne et nom, ou si elle joue un coup interdit (dans une colonne pleine), elle est immédiatement disqualifiée
* Chaque IA dispose d'une zone graphique de l'écran où elle est libre d'afficher ce qu'elle veut (mais qu'elle doit elle-même effacer pour écrire par-dessus), zone qui est déterminée par son numéro de joueur (selon que colonne vaille -1 ou 0 en début de partie) et la taille de l'écran (selon que nom vaille 1 ou 2 en début de partie) (je n'ai pas terminé la partie graphique de l'arbitre, donc je ne sais pas encore quelles sont ces zones, désolé ...)
* Une fois la partie finie, le programme arbitre affecte dans son propre dossier des variables colonne et nom (ces noms ne peuvent pas être changés) qui pourront éventuellement être récupérée par un méta-méta-programme (typiquement, un programme d'algorithme génétique) avant de se terminer normalement :
>> colonne vaudra soit 0 (match nul), soit 1 (IA 1 gagnante), soit 2 (IA 2 gagnante)
>> nom vaudra soit "N" (fin de partie normale), soit "D" (fin de partie par disqualification d'une IA)
* Il est à noter que l'arbitre enregistre un log de chaque partie, et un petit programme annexe permet de visionner pas à pas ces parties

Si quelqu'un veut utiliser un algorithme génétique, donc un méta-méta-programme qui lance l'arbitre de nombreuses fois de suite, je me dépêcherai de terminer complètement l'arbitre pour donner ici comment se fait son interfaçage ...

@++

Il existe encore ce concours
Tu as programmé une IA Ethaniel ?

Ethaniel est complexe.

-plexe

ça suffit comme ça !

Martial Demolins a écrit :Vu la complexité de ses règles... Après avoir tout lu, je pense que tu aurais pu imaginer un protocole plus simple.

Les règles de qui ? De l'arbitre ?
Pas de problème, ça fait des mois (depuis novembre-décembre) qu'il est programmé ...

Quand au protocole du programme joueur (l'IA), il n'y a pas plus simple : il reçoit la colonne jouée par l'adversaire, et renvoit la colonne où il veur jouer (avec des petites nuances en début et en fin de partie pour prévenir les IA, puisque les programmes ne tournent pas durant toute la partie, seulement durant leur coup).
Et si je ne fais pas tourner les IA tout au long d'une partie, c'est pour pouvoir faire s'affronter 2 IA quelconques (pour tester une IA contre elle-même et voir sa subtilité, d'où les logs et le replay, ou pour utiliser des algos génétiques).
Il n'y a que l'arbitre qui tourne du début à la fin d'une partie et qui s'occupe de la partie graphique, mais vous n'avez pas à vous en préoccuper, il est déjà programmé et pleinement fonctionnel.

@Albert : Il suffit de remonter de quelques posts (le ./194 par exemple) pour lire que mon IA est en partie implémentée depuis le mois de décembre.
Comme écrit dans ce post, sur papier, mon IA calcule 6 demi-coups de prévision en un minimum de tests, et donc de temps.
L'implémentation sur TI (qui n'a pas avancé depuis le post ./194, puisque c'est à ce moment que j'ai découvert le PHP) en est encore, si mes souvenirs sont bons, à 4 demi-coups.
Il faut vraiment que je termine ceci (et il faut d'abord que je retrouve mon IA sur papier ), mais les cours de Master ne vont pas aider ...

@squale92 : Merci.


Pour le moment, je vais d'abord refaire entièrement l'arbitre pour le rendre plus bête (détection basique des alignement), puisqu'il utilise pour le moment une technique hyper-optimisée (du moins sur la base de mes maigres connaissances) qui se trouve également dans mon IA et qui sera également dans l'autre future version de l'IA (laquelle utilisera les Réseaux de Neurones Formels et des algorithmes génétiques pour en déterminer les poids synaptiques, bref, rien à voir avec l'IA actuelle, excepté la détection optimisée des alignements).
En effet, il est prévu que chacun garde ses petits secrets (jusqu'à la grande bataille entre toutes les IA en compétition) pour ne pas influencer les autres programmeurs et permettre d'avoir le plus de diversité et d'inventivité possible.
A l'inverse, l'arbitre est prévu pour être librement distribué à chacun pour que tout le monde puisse tester son/ses IA dans les 'conditions rélles' de la compétition finale (et éventuellement utiliser des algorithmes génétiques).

Si vous voulez un peu de (semi-)théorie sur les algorithmes génétiques, je vous conseille ce post.
Je sais qu'il y a bien mieux et surtout plus complet sur Internet, mais n'hésitez pas à poser vos questions, mes réponses rendront le post plus complet.

Quant aux RdNF (Réseaux de Neurones Formels) ... je n'ai pas encore eu l'occasion de faire de post semi-théorique sur yAronet à ce sujet, mais je suis à votre disposition si besoin est ...

@++

Je veux bien un post semi-théorique sur les réseaux de neurones

Sinon, pour ceux qui utilise un minimax, vous construisez votre arbre en largeur ou en profondeur ?
Comment faites-vous pour que les besoin de mémoire ne soient pas énormes ? (un arbre de hauteur 5 et d'ordre 7 comporte tout de même 20000 noeuds environ)

Pk tu voudrais stocker quoi que ce soit en mémoire

J'ai dû mal réfléchir.
J'imaginais qu'il fallait stocker des infos pendant le déroulement de l'algo.

Bah je sais pas, tu évalues chaque position, si c rentable tu gardes, sinon tu zappes, non ? Tu n'as pas besoin de stocker les résultats de toutes tes évaluations, à moins de vouloir ré-évaluer après (mais j'y vois pas trop d'utilité)

Alors après, si tu veux faire des trucs un peu plus subtils, tu peux peut-être stocker certaines informations (genre tu fais un parcours en profondeur avec une profondeur max qui augmente au fur et à mesure, et tu veux avoir des estimations du meilleur coup à jouer à partir du parcours précédent), mais ça n'est pas du tout nécessaire dans la version de base...