2048

[Zanshin]

Je reviens à la charge avec une autre passion tout autant "de niche" que le jonglage de feu.

Cela fait lontemps que je chercher une sorte de jeu parfait qui serait à la fois simple et source infinie de divertissement en ce sens qu'on s'en lasserait très difficilement.
Et je crois m'être approcher de cela en trouvant 2048.

Pour ceux qui ne connaissent toujours pas. Vous avez une matrice carrée de 4 colonnes et 4 lignes. Vous avez 4 actions possibles correspondant chacune à une direction dans laquelle projeter toutes les tuiles contenues dans la matrice. Les tuiles sont des puissances de 2 (2,4,8,16,32,...) par défaut mais on peut les remplacer par n'importe quoi du moment qu'on admet une relation d'ordre entre elles.
Le but du jeu est de fusionner des tuiles en les projetant les unes contre les autres sachant qu'on ne fusionne des tuiles uniquement si elles ont la même valeur. La difficulté est qu'à chaque action, une tuile 2 ou 4 apparait aléatoirement sur une place libre. On gagne si on forme un 2048 (mais on peut continuer) et on perd quand le jeu se bloque (plus aucune possiblité de mouvement).

Si je postes ici c'est pour tenter d'attirer l'attention sur ce que j'ai entrepris autour de cela. Etant passionné par le jeu, je me suis attelé à faire une version VBA via Excel (et oui, c'est le language que je maitrise le mieux sinon, j'aurais fait de l'Action Script). Le programme est abouti et les algorithmes sont relativement optimisés. Mais le plus intéressant c'est que j'ai mis en place des outils pour faire des statistiques et maintenant, je tente de créer des algorithmes de résolutions. Autrement dit, je laisse le pc résoudre le 2048 tout seul et en boucle et ensuite je collecte les données pour mesurer son efficacité.

J'aimerais donc savoir si des gens sont intéressés pour développer des algorithmes de résolutions et les tester ? Sinon, ça peut être intéressant pour apprendre à programmer en VBA.

[Zanshin]

J'aurais au moins eu le mérite de présenter le loisir suscitant le moins d'intérêt chez les autres ^^

[W4x]

Le 2048 est loin d'être inintéressant en soi, par contre l'algorithmique n'est pas forcément la tasse de thé de tout le monde ^^

[Nexus-6]

Tu utilises quoi comme algorithme de résolution, le min-max ?

[Zanshin]

Désolé du retard, je n'avais pas été prévenu des réponses. Pour l'instant, mon algorithme se base sur un peu de prévision. C'est-à-dire que j'effectue une série d'actions (sans prendre en compte l'apparition aléatoire des tuiles de bases évidemment sinon, on ne s'en sort plus) et ensuite, je calcul un facteur qui prend en compte les valeurs des tuiles, les positions et le fait que l'on a une suite de termes décroissant. Ensuite, je compare les facteurs entre eux et j'oriente les choix de déplacements vers la matrice qui permet d'obtenir la plus haute valeur parmis toutes celles auxquelles amènent les prévisions. Pour des prévisions sur le tour suivant, c'est parfait puisqu'il n'y pas l'aléatoire qui risque de m'empécher de parvenir à la matrice attendue mais dès que je fais des prévisions sur plus d'un tour, ça devient tellement problématique que j'ai constaté que la méthode n'a plus d'intérêt au-delà de deux tours de prévision. Mon but suivant est donc de trouver un moyen pour que l'algorithme discrimine les tuiles aléatoires néfastes de celles qui ne posent pas de problème pour ensuite décider s'il doit s'arrêter dans l'exécution de la série de déplacements choisi. Pour l'instant, j'obtiens une moyenne de 250 coups environ par partie avant le gameover (avec un écart type assez élevé toutefois). Sachant qu'un bon joueur fait en moyenne des parties à 2500 coups voir bien plus sans avoir à compter sur la chance. Je suis donc encore bien loin d'avoir un algorithme véritablement efficace.

[Nexus-6]

Tu es obligé de prendre en compte les tuiles aléatoires sinon ton programme n'a aucun moyen d'anticipé et de faire un mouvement qui sera productif dans le long terme. Donc c'est pour ça que je t'ai proposé l'algorithme min-max, c'est une IA basique qui dans un état donné simule tous les coups possibles qui en découlent comme cela :



Bien sûr tu ne peux pas à chaque fois aller jusqu'à la réussite ou non de la partie car c'est trop gourmand, il faut que tu définisses une profondeur d'arrêt et que tu évalues pour chaque fin de branche si la configuration est plus ou moins favorable ensuite tu minimises les mouvements de l'ia et tu maximise les configurations donné par les tuiles aléatoires ainsi de suite jusqu'à prendre une décision pour le meilleur coup à jouer. Tu peux aussi utiliser l'algorithme min-max avec élagage alpha-béta qui permet de ne pas visité l'arbre en entier. Tu trouveras des cours sur le net qui expliqueront cet algorithme beaucoup mieux que moi.

[Nexus-6]

Je viens de me rendre compte que j'ai écrit une bêtise, il faut maximiser les mouvements de l'ia et minimisé les tuiles aléatoire autrement ça n'a pas de sens , maintenant l'algorithme min-max est efficace pour les jeux à deux joueurs, donc peut-être qu'il faudra faire une adaptation.

[Zanshin]

Intéressant, je vais m'intéresser à ça. Mais pour mon programme, j'avance petit à petit. J'ai amélioré le calcul de mon facteur en faisant varier le coefficient de valeur de tuile en une fonction puissance de deux. De même que pour le coefficient prenant en compte la position de la tuile. Ainsi, j'ai réglé le problème où l'algorithme n'orienté pas son choix dans le fait de fusionner des cases en priorité et où il est resté bloqué à effectuer en boucle des mouvements qui ne changés pas la matrice. Maintenant, je crois que la voie à suivre, c'est de faire varier la position des coefficients de positions en fonction de la situation. En effet, en gardant une carte de coefficient de position constante de façon à ce que la matrice cherche à effectuer sa suite décroissante d'une seule manière, il n'y a pas de problème jusqu'au moment où un mouvement dangereux pour l'intégrité de la suite doit être effectué et où une tuile aléatoire apparait là où il ne faut pas. A partir de là, le programme ne me calcul plus que des facteurs très petits et constants puisqu'il constate que le premier terme de la suite est petit. On remarquera que c'est exactement ce qu'il se produit pour un joueur humain. Au début, on cherche à construire sa suite décroissante en bloquant la plus haute valeur dans un coin prédéfini mais à un moment donné, lorsque l'on est obligé de prendre des risques pour continuer la partie et que l'on casse notre suite, à ce moment-là, on change de stratégie. Cette nouvelle stratégie étant de réussir à faire remonter le terme qui coupe la suite décroissante. C'est cette adaptation que je dois parvenir à programmer et, à partir de là, je crois que j'aurais bien fait progresser l'algorithme et que je pourrais arriver à ce qu'est capable de faire un humain. Et même mieux, puisque le programme ne peut pas faire d'erreur entre ce qu'il a prévu de faire et ce qu'il fait.

[Le Renard]

Même si ce jeu ne satisfait pas aux hypothèses du "vrai" minimax (deux joueurs dans un jeu à somme nulle), la piste n'était pas si conne : dans l'affaire on peut effectivement voir deux joueurs, même si l'un d'eux n'a pas d'intention de gagner. Le deuxième joueur c'est le truc qui, au hasard, remettra un 2 ou un 4 dans un emplacement vide. Le minimax permet d'en tenir compte, et reste utile dans une variante moins parano et donc plus simple. On peut aussi alors en faire une description démystifiée : un parcours en largeur de l'arbre de possibles, en élaguant au fur et à mesure les branches les moins prometteuses, et en fixant une profondeur maximale de recherche relativement limitée (surtout vu le choix de VBA comme plateforme ) avant de jouer un coup et recommencer l'exploration pour le coup suivant.

D'ailleurs pour gagner un peu en vitesse (et donc en nombre de possibilités explorées et donc en pertinence des choix effectués par le joueur virtuel) on peut imaginer une mémorisation des explorations déjà faites, parce que d'un coup à l'autre il y aura une part commune dans l'arbre des possibles.

Ce permettrait de rester, au départ, relativement agnostique quant à la stratégie, et de laisser l'ordinateur explorer un peu des idées qu'on n'aurait pas eu en cherchant trop vite à restreindre le champ de recherche. La seule décision qui reste alors à prendre pour le programmeur c'est la fonction d'évaluation. Moi qui n'ai jamais joué, je dirais que pour juger si une situation de jeu est désirable ou pas il peut suffire de faire la somme des points présents sur le plateau, avec deux exceptions : valeur max si on atteint 2048, et valeur min éliminatoire si on est bloqué. Mais en vérité c'est probablement là que l'expérience du jeu aide à en concevoir une bonne.

Sur ce point, d'ailleurs, vu que la fonction d'évaluation est centrale dans le succès ou l'échec de l'algorithme, une fois que la phase 1 marche bien tu peux imaginer de geeker en bon coup en phase 2 et essayer de placer à cet endroit un petit réseau neuronal ou autre support d'apprentissage automatique.

[Nexus-6]

Hier, j'ai fait une IA dérivée du min-max pour l'appliquer au 2048, pour la fonction heuristique, j'ai utilisé 3 contraintes, le nombre de case vide, le nombre de couples de tuiles adjacents ayant la même valeur et la valeur max des tuiles, je les ai pondéré pour que la valeur max soit la plus importante. J'ai laissé tourner 1000 parties, résultat 12 % des parties ont été gagnées. Donc voilà peut mieux faire, mais c'est une piste.

[Zanshin]

J'aimerais bien voir ton code du coup. Tu utilises quel langage ? Je précise que j'utilise VBA parce que c'est le langage que je maîtrise le mieux et que j'ai pas pris le temps de vraiment programmer sur autre chose.

[Nexus-6]

C'est du c++ par contre

[Le Renard]

Bin c'est malin : tu l'as fait fuir.

[Nexus-6]

Non je ne crois pas et ce serait dommage son topic est très intéressant. En tout cas pour l'instant j'explore la voie du réseau de neurones.

[Zanshin]

Désolé encore une fois. Non, je n'ai pas fuis mais ce que je ne reçois pas de notification alors je passe quand j'y pense.
Si c'est du C++, ça m'intéresse encore plus. Je n'ai pas trouvé la motivation pour me mettre à se langage. C'est surement l'occasion.

[Le Renard]

La question c'est : pourquoi en 2014 quelqu'un qui n'y est pas obligé voudrait se mettre au C++ ?

[Nexus-6]

Voilà le code, j'ai modifié l'un de mes anciens projets, donc la fonction min en faite maximise. Pour expliquer vite fait min simule la tuile aléatoire pour des zones verticale et horizontale par exemple si trois cases vides sont aligner je ne teste que une seule case, la fonction max simule les mouvements (horizontalement si je test une tuile aléatoire d'une zone horizontale). pour l'évaluation, je prends en compte plusieurs facteurs pour évaluer les positions.

J'utilise Code::Blocks

[Quzqo]

La question c'est : pourquoi en 2014 quelqu'un qui n'y est pas obligé voudrait se mettre au C++ ?

Peut-être juste pour le plaisir du paradigme objet sans le côté ayatollah d'autres langages ?
Peut-être juste pour le plaisir de manipuler des concepts proches du système, comme avec le C ?
Peut-être juste... pour le plaisir

[Le Renard]

Salut.

Maintenant qu'une discussion enflammée sur Linux a fait jurisprudence sur le forum, faut croire qu'on a le droit d'importer ici les débats houleux propres aux outils informatiques en général ?
Alors allons-y !

Peut-être juste pour le plaisir de manipuler des concepts proches du système, comme avec le C ?

Faire de la programmation système en C++ !?
Ca me fait penser à ces deux réponses Torvaldsiennes devenues célèbres : http://harmful.cat-v.org/software/c++/linus
En vrai y'en a qui le font. Des pros dont c'est l'activité principale, (dé)formés pendant des années et qui malgré tout produisent le plus souvent du soft de qualité moyenne au prix d'efforts élevés. Sérieusement le soft système de bonne qualité écrit en C++ est rarissime (c'est pas tous les jours qu'on tombe sur de la belle ingénierie comme V8 ou Hotspot).
Mais soyons honnêtes : qui ici fait de la programmation système ?

Alors pour la programmation applicative :

Peut-être juste pour le plaisir du paradigme objet sans le côté ayatollah d'autres langages ?

Oui, C++ permet ça.

Tout comme Ada, Go, Objective-C, Clojure, OCaml, etc. Ceux-là sont assez différents les uns des autres pour que quelqu'un puisse trouver son compte avec au moins l'un d'entre eux, et ils sont tous :
- aussi capables que C++
- beaucoup plus faciles à apprendre que C++
- beaucoup plus faciles à utiliser que C++ (utiliser c'est pas pareil qu'apprendre)
- suffisamment répandus pour bénéficier d'un écosystème où la roue a déjà été inventée
- dans des écosystèmes parfois plus fiables que C++

Et du côté des langages interprétés, certes lents et dont l'apparente facilité est parfois trompeuse, y'a des trucs comme Python qui satisfont aux mêmes critères.

Pourquoi, alors ?

Peut-être juste... pour le plaisir

Là c'est clair, c'est les goûts et les couleurs.

Cela dit le posteur de départ affirme ne maîtriser que les macros Office, autrement dit c'est un débutant quasi complet en programmation.
Pour la plupart des gens qui entament cette aventure, le plaisir passe alors en général par l'obtention rapide de résultats intéressants et utiles, pas par une lutte contre un langage à la syntaxe piégeuse et à la sémantique vaste et peu structurée. Ecrire un bon programme c'est difficile de toutes façons dans n'importe quel langage. Je ne vois pas comment on rend service à un débutant en l'encourageant à commencer par se préoccuper de toute la complexité accidentelle du C++.

Pour le non-débutant qui veut apprendre un nouveau langage pour s'ouvrir de nouveaux horizons, il peut constater que l'indice de popularité TIOBE du C++ a été divisé par trois depuis 2004.

Le C++ n'est pas un intemporel. Il était juste un compromis vendeur à l'époque où on voulait emmener des programmeurs C vers un niveau d'abstraction supérieur en faisant croire à leurs managers qu'il ne faudrait pas tout réapprendre. Le résultat est un monstre. Aujourd'hui on a quand-même plus pratique. Hier aussi, d'ailleurs.

My two cent.


PS : d'ailleurs le code de Nexus-6 n'est pas vraiment du C++. Il aurait qu'à replacer << par printf et un compilateur C en ferait son quatre heures.