Posté le 08/03/2008 à 19:58 Membre depuis le 25/12/2006, 499 messages
Je vois que tu partages mon avis. Juste un truc pour le mastermind, tu es d'accord pour que tous les choix effectués par l'AI soient aléatoires ?
Posté le 08/03/2008 à 20:25 Membre depuis le 01/12/2005, 413 messages
Hum a la base, pour le premier choix veux tu dire? Genre quand elle ne peux pas savoir, elle prend un chiffre au hasard? Ben bien sur, c'est une solution logique (hasard/logique, bizarre quand meme comme rapprochement ^^).

A mon avis c'est comme ca que je vais proceder. Je vais faire un brouillon vite fait d'algo ce soir, et je verrais demain pour le transcrire, l'ameliorer, voire l'accelerer.
Posté le 08/03/2008 à 23:54 Membre depuis le 25/12/2006, 499 messages
Ben dis donc, tu sembles confiant pour trouver la structure de l'algo. Moi c'est là-dessus que je bosse surtout, j'essaye de ne pas trop penser à la transcription.
Posté le 09/03/2008 à 01:44 Membre depuis le 09/07/2003, 21783 messages
Baruch (./21) :
Euh tu peux donner un exemple stp ?

Avec la précision "utilisable en temps convenable sur une machine actuelle", tous les problèmes sauf les quelques que l'on résout bien (on a des algos utilisables qui donnent une solution optimale. Genre tous les problèmes gentils d'optimisations). Ceux que l'on résout pas trop mal (on a des algos qui refilent en temps convenable une 'bonne' solution. C'est le cas des échecs actuellement. ), c'est déjà plus rigolo par ce que les AIs peuvent êtres pus ou moins bonnes, ce n'est pas juste une question d'optimisation du code (une fois trouvé un bon algo )

Alors des trucs comme le go (ou a des algos qui, en temps convenable, donnent des résultats encore moyen, ie bien moins bon que l'homme ) c'est encore plus rigolo...
Baruch (./25) :
Il me semble qu'il existe pour tous les jeux de logique une solution (ou une stratégie) optimale.

Avec quelques bonnes hypothèses voui.
Mais bon c'est un résultat d'existence que nous apprends la théorie des jeux, ça ne veut pas du tout dire qu'il existe un algo 'suffisament rapide' actuellement (ça veut dire soit polynomiale, soit dans NP ou plus mais que pour les cas courants c'est utilisable.. ).
Et même s'il existait la théorie des jeux nous aide très moyennement pour le trouver: le seul algo naturel qui découle, c'est de dérouler le graphe des états jusqu'au bout (les problèmes de cycle ça se bricole pas trop mal) et de faire un minmax avec juste les valeurs 1 (victoie), -1 (défaite), 0 (égalité, cyles, ..). évidement c'est infaisable en pratique actuellement sur un jeu d'échecs ou de go, alors on déroule 'un peu' le graph (20 coups, .. ) en bricolant ( on évite de regarder les coups possibles après un coup suicidaire ) et on 'note' subjectivement les positions. De manière totalement empirique ( c'est cette note entre-autre qui est très dure à donner pour le Go. ) et nécessairement améliorable, sinon il suffirait de dérouler un coup et noter puis choisir...
Et on ait du minmax (on part du bas pour remonter les meilleurs coups d'avant en connaissant la valeur des positions d'après.. ) sur ces notes..

Et il y a bien des cas 'logiques' où l'on ne se situe pas dans la théorie des jeux et où l'existence d'un algo optimal n'est pas certain voir on sait qu'il n'en existe pas.
Enfin, il peut être utile à mon avis de "sacrifier" un peu de justeté pour gagner en rapidité.

La réalité physique des machines nous l'impose forcément... (pasque genre un aglo qui va te donner la stratégie optimale en 20 millions d'années sur un dual core actuel, c'est pas utilisable en pratique.. )
Baruch (./28) :
On a trouvé l'algo optimal pour les échecs, blanc comme noirs. Si les 2 joueurs utilisent cet algo, alors le jeu ne se termine pas.

Bha on a trouvé l'algo optimale pour tout jeux qui rentre bien dans le carde de la théorie des jeux, c'est celui que je décrivait ci-dessus, mais on est incapable de l'appliquer en pratique (et probablement pur encore très très très longtemps sauf révolution informatique majeure. ) et cf ce que je disais ci-dessus, encore aujourd'hui les algos utilisés pour les échecs sont clairement non optimaux. Pas trop mauvais mais non-optimaux (enfin on a aucune garantie d'optimalité... ).


Bon sinon y'a pleins de cas qui soient ne rentrent pas dans la théorie des jeux, soit pour lesquels les méthodes naturelles qui découlent de la théorie des jeux sont aujourd'hui nullissimes, et c'est souvent des cas plus rigolos à traiter (pasque minmax co et montecarlo, bon c'est vite plus très marrant....)


Posté le 09/03/2008 à 08:51 Membre depuis le 11/04/2007, 1076 messages
Je pense que c'est pas mal une partie d'aléatoire... (mais pas que, sinn ça avance pas)
Posté le 09/03/2008 à 09:47 Membre depuis le 11/04/2007, 1076 messages
C'est vrai qu'on ne sait pas résoudre bcp de problèmes avec un temps limite... En fait, souvent, on a un pb au niveau de la taille des entrées (parce que bon, la taille d'un jeu d'échecs et d'un jeu de Go, c'est pas pareil :P).
Mais quand même, y'a bcp de problèmes qui avancent (bon, je parle pas des graphes et autres trucs infaisables =D)
Posté le 09/03/2008 à 10:26 Membre depuis le 01/12/2005, 413 messages
Entierement d'accord Very, et c'est pour cette raison que ce que je pensais faire pour le bot n'etait pas du tout la recherche du meilleur coup possible (deja horrible sur PC, alors sur calc...), mais plutot des solutions pratiques pour que le bot joue pas trop mal.

Baruch, tu as raison, j'ai sous estime la difficulte de l'algo d'une AI meme pour un mastermind, j'ai ete assez vaniteux pour tenter de le coder directement. Apres la creation de ma 6eme liste j'ai decide de m'y mettre d'abord sur papier. Je suis loin de l'avoir fini mais j'ai les idees.
Posté le 09/03/2008 à 11:52 Membre depuis le 25/12/2006, 499 messages
Merci beaucoup very pour toutes ces précisions ! Est-ce qu'il est possible d'ajouter au problème d'optimisation pour un jeu le paramètre de la longueur da l'algo ?

Syfo, j'ai bien envie de partager mes idées, mais bon c'est un concours ^^. Moi j'ai même pas encore trouvé une solution claire et automatique pour analyser n'importe quelle série d'essais.
Posté le 09/03/2008 à 14:18 Membre depuis le 01/12/2005, 413 messages
Moi j'y travaille aussi. Si j'ai de gros problemes, je te demanderais de l'aide, mais ca m'etonnerait. J'te dirais ca dans la soiree.
Posté le 09/03/2008 à 17:54 Membre depuis le 09/07/2003, 21783 messages
Baruch (./37) :
Est-ce qu'il est possible d'ajouter au problème d'optimisation pour un jeu le paramètre de la longueur da l'algo ?


Ho oui touça se formalise pas trop mal (avec des classes de complexité, touça), même si c'est toujours relié au bout à un coté assez expérimental, physique, qui est la puissance actuelle de nos machines.
On sait même prouver parfois que pour tel problème le mieux que l'on puisse faire est en tel genre de temps en fonction de l'entrée (genre O(n.log(n)) pour trier une liste sans plus d'information..), enfin y'a plein de résultats cools.


Bon sinon j'y plancherais bien mais heu... je connais pas le mastermind grin
Posté le 09/03/2008 à 19:20 Membre depuis le 11/04/2007, 1076 messages
http://fr.wikipedia.org/wiki/Mastermind#R.C3.A8gles_du_jeu

Si Baruch te passe son jeu, tu devrais te faire une idée...
Posté le 09/03/2008 à 19:29 Membre depuis le 25/12/2006, 499 messages
Tu as l'air calé en algorithme, ça m'intéresse beaucoup tout ça !

Bon allez je t'explique les règles :

Le but est de découvrir une combinaison de couleurs aléatoire et cachée.
Cette combinaison a une longueur définie au début de partie, et contient des couleurs appartenant à un nombre défini de couleurs différentes.
Selon les variantes, on admet ou pas la répétition de couleurs dans la combinaison (dans notre cas, non).

Pour que le joueur puisse trouver cette combinaison, il dispose d'un nombre de coup limité défini.
A chaque coup, le joueur donne une combinaison de couleurs. L'AI (ou un autre joueur) donne ensuite les informations suivantes :
Pour chaque pion de couleur présent dans la combinaison tentée :
- Si le pion est présent dans la combinaison secrète, et bien placé, il indique à côté un pion noir.
- Si le pion est présent dans la combinaison secrète, mais mal placé, il indique un pion blanc
- Si le pion n'est pas présent dans la combinaison secrète, il ne met rien

Les indices donnés ne sont pas ordonnés, on ne peut donc pas savoir à quel indice correspond quel pion.

Notre problème consiste à trouver un algorithme capable de donner la série de combinaisons la plus rapide pour trouver la combinaison secrète.

Pour l'instant, on se contente de chercher l'algo en fixant le nombre de couleurs à 6, la longueur de la combinaison à 4, sans répétitions de couleurs (pour la combinaison secrète et pour chaque essai).

D'ailleurs, il est plutôt facile de généraliser.

Voilà, à toi d'essayer si tu veux !

Posté le 09/03/2008 à 19:34 Membre depuis le 25/12/2006, 499 messages
Arch, j'ai voulu rédiger les régles moi-même, et me voilà pris de court par gon ! Bon tant pis, en tout cas j'espère que tu as compris. Oui je peux toujours te passer mon prog (et aux autres... ^^), je le mettrai ce soir sur un host.
Posté le 09/03/2008 à 19:41 Membre depuis le 11/04/2007, 1076 messages
?? Vous pouvez pas mettre 2 fois la même couleur dans la combinaison eek
Mais ça devient trop facile!
Posté le 09/03/2008 à 19:47 Membre depuis le 25/12/2006, 499 messages
Bon eh ! ^^ C'est pas moi qui ai lancé le défi ^^
Posté le 09/03/2008 à 19:55 Membre depuis le 01/12/2005, 413 messages
gon33 (./43) :
?? Vous pouvez pas mettre 2 fois la même couleur dans la combinaison eek
Mais ça devient trop facile!


J'avoue que j'ai longtemps joue avec plusieurs fois le meme nombre possible dans la combinaison, mais ce ne sont pas les vraies regles. De plus, mon algo est plus long a coder de maniere a ne pas mettre plusieurs fois le meme nombre, meme si ca ne se joue qu'a quelques lignes de differences (et je pense que ca doit etre un peu la meme chose pour Baruch, non?).
De plus, c'est juste pour se faire une idee, personnellement, ca fait longtemps qu'on me parle d'AI, mais je n'en ai jamais code une seule.
Posté le 09/03/2008 à 22:12 Membre depuis le 25/12/2006, 499 messages
Je sens que tu veux savoir ce que je fais ^^. Moi je pense que ça ne prendrait aucune ligne d'autoriser les répétitions, en tout cas d'après ce que je crois.
Posté le 10/03/2008 à 19:37 Membre depuis le 01/12/2005, 413 messages
Bon j'ai fini mon algo, pas besoin du tien tongue
Par contre, j'en ai fais une trace (test des valeurs de toutes les variables pour chercher un exemple de combinaison: [4,6,3,1] ), et je me suis apercu qu'il y avait une optimisation possible de l'algo, un bug qui arrive pour un cas precis (heureusement peu frequent), et pas mal de truc a corriger pour qu'il fasse une partie le plus rapidement possible.
Donc je vais le reprendre demain pour en faire une nouvelle mouture (1h de philo, ca devrait suffire ^^), et peut etre que mercredi j'en aurais une version ti-basic (mais ca m'etonnerait).

J'ai quelques questions de precision sur le jeu par contre:
-le nombre de vie de l'AI, j'ai mis 10, puis je me suis dit que je devais faire en sorte que le nombre de vie soit variable, correct?
-le mode de determination du nombre de pions bien/mal places: on doit le coder soi-meme ou le demander a l'utilisateur. Je pense que je vais le coder moi meme, non?
Posté le 10/03/2008 à 23:24 Membre depuis le 25/12/2006, 499 messages
Bravo, moi j'ai pris du retard à cause de quelques devoirs à rendre ^^. Le nombre de vie, c'est le nombre d'essais j'imagine ? Ben je trouve qu'il faut en mettre un maximum (moi j'en ai mis 16), car le nombre d'essais possibles fixé n'a pas d'incidence sur l'algo. Oui je trouve qu'il vaut mieux créer un bot qui donne les indices plutôt que de les donner à la main.
Posté le 11/03/2008 à 19:55 Membre depuis le 01/12/2005, 413 messages
Bon ma nouvelle mouture comporte encore pas mal de problemes, et n'est pas terminee, mais je m'approche du resultat optimal (en prenant un exemple particulier, que l'AI joue au moins aussi bien que moi). Juste pour savoir, tu penses qu'au final ton algo fera a peu pres quelle longueur? Moi un peu plus d'une centaine de lignes, et c'est assez long pour en faire une trace, generalement je faisais tout plein de petits algos, et celui la est un des plus longs que j'ai jamais fait.
Posté le 11/03/2008 à 21:58 Membre depuis le 25/12/2006, 499 messages
Enfait j'ai pris du retard, je pourrai vraiment avancer demain aprem. Je n'ai codé pour l'instant que le correcteur de combinaison et le début de la première partie de l'algo. Je n'ai vraiment aucune idée de la longueur qu'il fera en tout. Juste une question : Quand tu affiches la combinaison tentée, est-ce que toute la combinaison est déjà générée ou est-ce que tu affiches chaque chiffre généré un à un ?
Posté le 12/03/2008 à 16:55 Membre depuis le 01/12/2005, 413 messages
Non, je stocke dans une liste la combinaison tentee, que je modifie tout au long de l'algo avant de l'afficher d'un coup a la fin.
Posté le 12/03/2008 à 19:00 Membre depuis le 11/04/2007, 1076 messages
Bon, Nitacku voudrait participer. (il doit me confirmer ce soir ou demain)
Il est américain, donc j'espère que vous comprendrez ce qu'il écrit.
Je traduirai si vous avez des trucs à lui dire que vous savez pas dire en anglais...

Il voudrais savoir quelle est la limite de temps pour coder l'IA.
(Ah et au fait, vous avez toujours besoin de moi comme juge? => je suis tjrs partant hein, faut pas croire^^)
Posté le 12/03/2008 à 19:29 Membre depuis le 01/12/2005, 413 messages
La limite de temps? On en a pas vraiment defini une, disons 2-3 semaines, en fait comme c'est entre nous, on peux rallonger le temps ou le raccourcir si tout le monde a fini.
Qu'en dis tu Baruch?

Moi je comprends parfaitement l'anglais (je le parle tres mal par contre xD).

Et oui on a toujours besoins de juges, bien que si toutes les AI marchent, en fait je ne sais pas trop comment vous allez juger (taille, vitesse du prog, mais est ce que les juges vont devoir analyser le code?)
Posté le 12/03/2008 à 21:15 Membre depuis le 25/12/2006, 499 messages
Ben à mon avis, tous ceux qui veulent participer sont les bienvenus. L'anglais ne me dérange pas trop ^^. Pour juger, il faut bien sûr que les juges analysent le code. Bon allez, je retourne coder ^^.
Posté le 13/03/2008 à 12:14 Membre depuis le 01/10/2006, 80 messages
Syfo-Dias (./17) :
Si t'es motive, on m'a deja propose un combat d'AI, c'est marrant et pas trop dur, alors pourquoi pas (mais c'etait tombe a l'eau). Par exemple, on fait une AI qui resolve un mastermind, et avec 5 situations donnees, on voit quelle AI est la plus rapide. Ca peut etre interessant.

Tu connais la citation des sources? Méchant Syfo, va! C'était mon idée!
http://tamasteam.actifforum.com/defis-optimisation-f44/68k-mastermind-inverse-t829.htm
Posté le 13/03/2008 à 19:31 Membre depuis le 25/12/2006, 499 messages
J'ai eu une illumination dans le métro ! Sorry.^^
Posté le 13/03/2008 à 19:47 Membre depuis le 01/12/2005, 413 messages
C'est vrai ProgVal, c'est ton idee, et je n'ai pas pense sur le moment a le preciser. Mais je t'ai tout de meme prevenu qu'on avancait ton idee (un peu en retard c'est vrai), donc ce n'etait pas avec la volonte de te piquer ta gloire.

Une illumination dans le metro? Tant mieux, tu devrais donc bien avancer. Moi par contre, rien de plus de fait.
Posté le 14/03/2008 à 03:15Edité par nitacku le 23/11/2009 à 08:19 Membre depuis le 13/03/2008, 2 messages
n.
Posté le 14/03/2008 à 18:38 Membre depuis le 11/04/2007, 1076 messages
Welcome! happy
Well, you have a 2 or 3 weeks delay to code your project...
Good luck!



Very, tu avances???
Posté le 14/03/2008 à 18:52 Membre depuis le 09/07/2003, 21783 messages
( non j'ai jamais dit que je participais à qqch )