Bah moi en tout cas j'avais fait un petit advance wars basique, avec un vehicule longue portée (20 cases par exemple), le calcul de toutes les destinations possibles pouvait légèrement se ressentir dans le framerate avec du dijkstra pour le pathfinding. Donc calculer toutes les possibilités 3 ou même 2 tours en avance est carrément impensable, leur nombre étant exponentiel.

D'ailleurs même aux échecs: à raison de 15 coups possibles par tour (des fois y'en a bien plus), calculer 10 tours en avance par exemple est totalement impossible en bruteforce, même avec un très bon PC (15^(10*2)).

Après je me trompe peu-être quelque part

Ce dont Ark avait l'air de parler est d'un jeu tour a tour. Du fait, c'est assez faisable de faire un peu de prevision. Je rejoue a Shining Force ces jours ci. Et ca me tue de voir a quel point l'IA est conne. Une simple prediction a 2 ou 3 tours d'avance lui permettrait d'etre BEAUCOUP plus forte et aussi beaucoup plus logique. les IA d'echecs sont au contraire assez forte pour explorer l'espace des possibilite. En generale, les IA font de la prediction a au moins 5 coups d'avance. Les IA de go font des analyse de monte carlo pour estimer la qualite d'un coup.
Bref, il y a plein de solution possible pour essayer de rendre les IA un peu plus intelligente qu'un comportement completement scripte ou completement greedy.
Un jeu de strategie avec une mauvaise IA sera chiant a mourrir.

Moi aussi, le A* je le trouvais lourd à partir du moment où je devais gérer plusieurs unités. Il doit y avoir moyen, ce serait interessant de savoir comment Advance Wars a été fait là dessus

hexabeast, en general, il y a plein de coup que tu peux facilement taggue comme etant mauvais, donc tu ne les explores pas (ou pas tout de suite). C'est un peu ce que fait alppha/beta.

En fonction de la taille de la carte, il peut etre possible de separer plusieurs front et donc de reflechir sur chaque front separement: ce qui diminue la combinatoire enormement. Si tu coupe en deux fronts de meme taille, tu prends la racine carre de la complexite.

Comme j'ai dis au dessus, tu peux aussi regarder le probleme avec une approche de monte carlo ou tu explore les 3 premier coups explicitement, et ensuite tu joue une partie aleatoire pour ce qui reste. Ou encore tu joues le reste de la partie avec un algo glouton de type "fait le plus de dommage".

Apres, 15^(10*2) c'est beaucoup mais 15^(10) ce n'est pas tant que ca: c'est 537 Milliard de combinaison. Une bonne machine pourrait te bouffer ca en quelques secondes. Une NVIDIA GTX660 (c'est une carte a $200), ca fait 960 core cuda a 1Ghz, soit en gros 960 milliard d'operation par seconde. Bon il faut que les alignement memoire marche bien et cie. On a l'impression que des milliards c'est beaucoup, mais en fait non...

Pour ton pathfinding qui faisait tomber le framerate. C'est certainement plus un probleme lie au fait que ton moteur etait synchrone qu'autre chose. Si le calcul se fait dans ta boucle d'affichage, alors en effet tout calcul de plus de 1/60 seconde fait tomber le FPS en dessous de 60. Mais si tu fais le pathfinding dans ta boucle principale, tu met deja a la poubelle la majorite des perf de ta machine, ton processeur a certainement 4 coeurs dont 3 restent inutilises... (En passant, un implementation de SingleSourceShortestPath devrait compter en million d'arete par seconde sur une machine moderne. donc ca ne devrait pas prendre 1/60 secondes compte tenu de la taille dont tu parles.)

"il y a plein de coup que tu peux facilement taggue comme etant mauvais [...]il peut etre possible de separer plusieurs front et donc de reflechir sur chaque front separement [...] monte carlo"

Je suis tout à fait d'accord, j'ai justement critiqué le bruteforce pur et simple sans aucune optimisation.

Sinon l'algo de pathfinding faisait un léger freeze, mais sur une vieille machine de mon lycée (qu'ils ont foutu sous linux car 512Mo de ram c'est un peu juste pour windows), dans la boucle de rendu, et en python ^^
De toutes façons quand la machine passe au calcul des coups possibles du joueur, puis encore une fois à celui de ses propres coups, imaginons qu'à la base avec n mouvements ça faisait un très léger freeze dans de mauvaises conditions sur un mauvais PC, avec n^3 ça devient vraiment trop pour à peu près n'importe quelle machine il me semble. Et même si ça passait, prévoir 2 coups à l'avance (n^5) serait impensable avec du bruteforce non optimisé.

De toutes façons quand la machine passe au calcul des coups possibles du joueur, puis encore une fois à celui de ses propres coups, imaginons qu'à la base avec n mouvements ça faisait un très léger freeze dans de mauvaises conditions sur un mauvais PC, avec n^3 ça devient vraiment trop pour à peu près n'importe quelle machine il me semble. Et même si ça passait, prévoir 2 coups à l'avance (n^5) serait impensable avec du bruteforce non optimisé.

Comme d'habitude avec les exponentielles, ca depend entierement de la base. Si c'est une base 10, alors ajouter un facteur 10^2 ne fera pas grand chose, peut etre une decision par seconde. Un autre facteur 10^2 fera une decision en 1 minutes 30. C'est un peu lent mais pas forcement impossible a gerer compte tenu que tu peux utiliser le temps du joueurs pour commencer a calculer les possibilites et que tu peux reutiliser les calcul d'un tour a l'autre.

Probablement aucune decision gloutonne ne devrait alterer le framerate, certainement le code etait tres mal ecrit et c'est pour ca que le framerate a souffert. Pour un jeu d'echec tu fais du niveau 2 ou 3 sans aucun soucis.
C'est aussi difficile de predire les performances d'une machine a l'autre. Ajouter un peu de cache peut couper un temps de calcul en 2. passer d'une machine a 1 coeur a 4 coeurs peut donner un facteur 4. Passer de SSE a AVX 2 peut donner un facteur 2. Si tu passes d'une machine avec un GPU non programmable a une machine avec un GPU programmable, c'est encore un facteur 10 qui est gagnable. Dans mon experience entre du code ecrit "pour que ca marche" et du code ecrit "pour aller au plus vite" tu as frequement un facteur 1000.

En general, je trouves que les gens ont tendace a reflechir trop algorithmiquement en mettant des facteur partout et en disant "on est cuit" alors qu'en fait, on peut grater des ordres de grandeurs en pratique.

"passer d'une machine a 1 coeur a 4 coeurs peut donner un facteur 4."

Et s'il s'agit d'une de ces cartes mères à plusieurs sockets de processeur, et plusieurs banques de RAM, et que tu mets deux processeurs dual-core? Je veux dire, que la quantité de mémoire disponible soit elle-même partagée en deux influe de manière significative sur les performances?

Une question difficile:

Et s'il s'agit d'une de ces cartes mères à plusieurs sockets de processeur, et plusieurs banques de RAM, et que tu mets deux processeurs dual-core? Je veux dire, que la quantité de mémoire disponible soit elle-même partagée en deux influe de manière significative sur les performances?

Il y a une difference entre les coeurs et les processuer. Ici je parlais d'une machine a 1 processeur, mais a 4 coeur (genre un i7 qu'on trouve dans plein de laptop de nos jours). Les machines a plusieurs processeurs ne se trouvent pas beaucoup dans les machines "normales", surtout dans le marche serveur et "workstation de bourrin".

Il y a plusieurs choses. Si tu as deux processeurs, alors tu as deux controlleur memoire et deux bus DRAM<->cache. ce qui veut dire que tu peux doubler ta bande passante totale. Mais ca veut souvent aussi dire qu'il y a une partie de la memoire qui est "proche" d'un processeur et "loin" de l'autre. et il faut passer par un bus special (QPI chez intel) pour acceder a de la memoire "lointaine". C'est ce que les gens appellent des effet NUMA (Non Uniforme Memory Access).

En l'occurence je parlais de machine multicoeur; c'est a dire que tu as plusieurs coeurs sur le meme processeur. Et ils partagent le meme controlleur memoire. Mais ca a plusieurs consequence sur les performances memoire. Souvent quand il y a plus de coeur, il y a plus de cache total (mais pas forcement plus de cache par coeur) ce qui veut dire potentiellement moins d'access a la memoire tout court. La taille du cache a un genre d'effet de seuil sur les performances, si tu rentre pas dans le cache tu as un temps de X et si tu rentre dans le cache tu as un temps de X/Y. Aussi, quand tu as plus de coeur dans la machine, souvent tu as un meilleur controlleur memoire. Il a plus de bande passante a la memoire, peut stocker plus de "pending request". Aussi il est classique que un seul coeur n'arrive pas a saturer la bande passante memoire. Parceque un seul coeur pourrait ne pas pouvoir emetre des instructions de LOAD (ou de prefetch) assez rapidement pour utiliser pleinement la bande passante du controlleur memoire.

Note aussi que quand tu as une machine multiprocesseur, pour pouvoir tirer parti de la bande passante double, il te faut au moins maintenir un thread actif par processeur. Et certainement plusieurs pour arriver a saturer la BP. Aussi il te faut savoir ou chaque allocation memoire est place. (Tu as plusieurs facon de controller le placement memoire, le plus courrant etant de laisser le systeme faire et de choisir la politique de placement entre "first touch", "interleave" et "static". Mais tu peux aussi specifier le placement avec des appels a un derive de malloc.)

Finalement, ca te force a utiliser plein de thread a la fois. Et pour pouvoir utiliser plein de thread, il faut un calcul assez parallel, sinon les threads vont passer leur temps en synchronisation a se marcher dessus.

Godrik qui parle de performances, c'est toujours aussi bon

"Comme d'habitude avec les exponentielles, ca depend entierement de la base. Si c'est une base 10, alors ajouter un facteur 10^2 ne fera pas grand chose, peut etre une decision par seconde. Un autre facteur 10^2 fera une decision en 1 minutes 30."

Oui, mais justement, dans un jeu style advance war, en prenant en compte, par exemple, 10 unités de portée moyenne/basse (4 cases de portée par ex), t'as un peu plus de 30 cases possibles pour chaque unité, soit 30^10 possibilités de disposition des unité. Bon après si l'IA gère les unités individuellement (moins intelligent donc) ça fait seulement 300 possibilités.
Donc avec 300^n, même si avec n = 1 la PC freeze pas, ça peut pas aller bien loin avec n= 5 (prévision 2 tours à l'avance): 300^5= 2 430 000 000 000 possibilités (de tête, pas sûr). Et franchement même prévoir 2 tours à l'avance, avec les unités traitées individuellement (donc l'algo ne trouve même pas de solution parfaite), dans un jeu ou l'on ne peut atteindre l'ennemi qu'au bout de 3 ou 4 tours sur une grosse map, c'est loin d'être efficace.
Donc, dans ce jeu en tout cas, le bruteforce pur ne me semble vraiment pas bon du tout.

C'est vrai que dans advance wars, on deplace toutes ses unites d'un coup. Ce qui rends la combinatoire du brute force vraiement mechnate. Mais encore une fois, je veux attirer ton attention sur les calculs que tu fais. Tu compte toujours des tours comme etant l'ia joue, je joue. Tu peux aussi faire une evaluation au milieu, ce qui fait que tu peux aussi regarde du 300^4 ou du 300^6.

Aussi, regarde le chiffre que tu donnes 300^5= 2 430 000 000 000. Ca fait 2 Tera possibilite. Ca l'air beaucoup comme ca. Mais en fait ce n'est pas tant que ca. Un processeur moderne, ca a 4 coeurs a 2Ghz et chaque coeur peut faire 16 operations (addition, multiplication) par cycle: soit 0.5Tera operation par seconde. Si tu as un GPU moderne, tu peux en tirer un facteur 4 encore. 2.4 Tera possibilite, ca l'air beaucoup, mais ca depend vraiment du cout d'evaluation d'une possibilite et operations. Si on peut les estimer en 1 operations, on pourrait prendre le meilleur coup en 4 secondes. Ce qui est tres peu. Naturellement, ca prendra certainement plus proche d'un millier d'instruction ou plus, et la tu es de l'ordre de l'heure et clairement, ca ne passera pas...

Finalement, je suis d'accord avec toi. Dans advance wars, un bruteforce pure et simple ne va pas marcher. Mais ca ne veut pas dire que tu ne peux pas payer une certaine forme d'explosion combinatoire. Et en general, les gens pense que 1 millions de combinaison c'est beaucoup, alors que c'est petit a l'echelle moderne, surtout pour un jeu au tour par tour. Je me rappelle quand je jouais a heroes of might and magic. Ca me faisait chier d'attendre si l'IA prenait plus de 15 secondes pour choisir sa strategie globale. Sur une carte de combat, la carte fait en gros 15x15 et l'ia ne reflechissait jamais bien longtemps et etait assez forte. Et en 15 secondes, punaise tu peux en calculer des choses!

C'est sûr qu'on sous-estime souvent les capacités maximales d'un PC, mais elles peuvent aussi être atteintes assez vite avec quelques boucles imbriquées dans certains cas.

Ça me rappelle cette histoire d'ailleurs, que je trouve parfaite pour illustrer à quel point on peut aussi sous-estimer les exponentielles: http://lemigo.free.fr/echecsble/

En parlant d'IA forte, j'ai pensé à un truc: Pour pouvoir apprendre comme un être humain, en partant de 0 (ou presque), je me suis dit qu'une IA forte doit forcément avoir différents "sens". Genre chez l'Homme on associe des sons à des images, des images à des gouts etc. Mais on peut pas vraiment apprendre quoi que ce soit en ayant comme unique sens, de naissance, l'ouïe par exemple il me semble. Du coup sur une IA forte ça devrait être pareil, uniquement lui "parler" par écrit ne devrait pas suffire à lui apprendre quoi que ce soit si on part de 0, si?
Ou bien je dis complètement n'importe quoi?

Tien c'est bien que vous parler d'IA parce que justement hier Dorian a fait une vidéo sur les IA des jeux .

https://www.jeuxvideo.com/videos/chroniques/413334/l-i-a.htm

Tiens en parlant de multi core et compagnie, visiblement Microsoft à décidé de laisser un coeur de plus de la Xbox One pour les jeux (plus exactement un cœur mais avec une priorité basse et 20 à 50% réservé à d'autre processus).

Godrik une idée des performances que ça peut apporter ? (A l'origine la Xbox One a 8 coeurs, 6 dédié au jeu, 2 aux fonctionnalités de la console, et donc maintenant ce serait 6 dédié au jeu, un aux fonctionnalités et un partagé)
J'aurai tendance à dire pas beaucoup, surtout en considérant que c'est asymétrique par rapport à la PS4 (donc pas d'optimisations que pour xbox envisageable, à moins qu'elle ait un retard conséquent sur la ps4 ce qui est pas le cas), mais je vois bien du code spécifique (code plateforme, intrinsics) utiliser ce coeur et gagner quelques ms.

Je n'ai pas regarde trop l'architecture de la xbox one, mais de memoire, ca ressemblait beaucoup a un PC moderne. J'imagine qu'ils se sont rendu compte qu'ils n'avaient pas besoin de mobiliser 2 coeurs pour assurer les fonctionnalite du systeme et que donc il ont remis un core de plus pour les jeux.

C'est toujours difficile d'evaluer le gain de perf quand on rajoute un coeur, du cache ou quoi que ce soit. A part des cas tres particulier, on n'attends pas d'acceleration super lineaire quand on rajoute un coeur. Ici certainement ajouter un coeur n'ajoutera pas plus d'un facteur 7/6 (16%) de performance brute (mips, flops). Il etait possible de saturer le bus memoire avant, donc certainement toujours maintenant.

La ou je pense que le gain peut etre le plus important c'est au niveau de la latence au niveau des comportement temps reel en reduisant les changements de contexte. Je pense que l'ajout d'un coeur partage peut apporte le meme genre de benefice que ce qui a ete fait au debut de l'hyperthreading. Imaginons un systeme avec un coeur. Si on veut maintenir un rafraichissement a 60 frame par seconde, il faut pouvoir garantir qu'un thread va pouvoir s'activer sur ce coeur au moins 60 fois par seconde, et rester actif suffisement longtemps pour produire l'image. Maintenant si tu as un autre traitement a faire, comme decompresser le prochain niveau qui n'est pas une tache prioritaire. Si tu fais les deux (rafraichissement et decompression) en meme temps, alors tu prends le risque que la tache non prioritaires ralentisse le rafraichissement ce qui ferait tomber le frame rate. Alors les OS ont des mecanismes de scheduling pour aider, mais ce n'est pas tres tres precis. En particulier parceque tu ne peux pas empecher un thread de completement flusher le cache du processeur. Ce qui pourrait etre catastrophique. En rajoutant un coeur, tu peux deplacer tous les threads non prioritaires sur le coeur en plus et avoir un controle plus precis sur les coeurs qui executent une operation prioritaire.

Il y a plein de tache pas forcement prioritaire dans un jeu: precharger le niveau d'apres, faire une sauvegarde, verifier une condition de victoire (si ce n'est pas precis a la frame, ce n'est probablement pas grave), verifier si il y a une mise a jour, gestion des achievements, ...

Moi t'auras beau me donner la capacité de capter les infrarouges, c'est pas pour autant que je pourrais comprendre ces signaux

Bah si justement. Si tu le conjugues avec tes autres sens, au fil du temps tu vas essayer de comprendre à quoi les infrarouges correspondent. Imaginons par exemple que tu voies ce qui est chaud en rouge et ce qui est froid en bleu (en mode vision thermique trolololz ), tu vas utiliser un autre sens (toucher) pour te rendre compte en touchant que ce qui est rouge est chaud et ce qui est froid est bleu. En expérimentant, tu peux essayer de comprendre.
Par contre, là où ça devient compliqué c'est pour qu'une machine ait cette démarche...

Enfin ce que j'ai dit me semble logique, je suis pas un expert en comportement humain

"Bah je suppose qu'on peut quand même apprendre des trucs à des sourds aveugles"
Peut être, mais quelqu'un n'ayant, de naissance, ni toucher, ni odorat, ni vue, ni goût, ni aucune capacité de mouvement ou de parole, juste le fait de pouvoir entendre ce que les gens disent, ne pourra jamais rien comprendre à ce qu'il entend même si on lui parle pendant 30 ans étant donné qu'il n'a rien sur quoi se baser pour imaginer la signification des mots.

Tu prends l'exemple de sourds aveugles, mais déjà il faut qu'ils le soient de naissance, puis tant qu'il leur reste plus d'un sens, et surtout tant que ce sont des sens qui permettent d'envoyer ET de recevoir des données, comme le toucher, on ne peut pas appliquer la théorie du "besoin de plusieurs sens".

En bref il faut :
Soit plusieurs sens de récéption d'information (ex: ouïe et vue)
Soit au moins un sens permettant l'émission et la réception de données (mais là il faut un interlocuteur pour que ça fonctionne), comme le toucher.

J'aime faire des théorie absolument pas fondées