Bonjour.

Je suis désolé si je suis pas sur le bon furum. Voila, j'ai lu quelque part (et j'ai malheureusement oublier mes sources) qu'il y avait pour tout les jeux "logique", "mathématique" (je ne sais pas si mes thermes sont correct) un algorythme qui pouvait gagner a tout les coups (100 % de chnace mathematiquement) ; j'en est conclue que quelqu'un fairait un jour un programme qui pourrait battre n'importe qui au echec.

Ma question est clair : est que c'est possible ?

J'ai essayer d' y réfléchir mais je n'est pas assz de connaissances sur le sujet. Quelqu'un a t-il une réponse sur (démontrable) ?

Merci d'avance de me répondre et exusez moi si ce n'est pas le bon forum.

Dans la théorie, oui tu as toujours un algo pour gagner et il est très simple : il suffit de simuler tous les coups possibles tour après tour, et de regarder quelle succession de coups mène le plus rapidement à la victoire.

Mais en général, ce nombre de coups est en pratique énorme, ce qui empêche de simuler plus loin que les quelques premeirs coups.

Aux échecs par exemple, pour le premier mouvement, on a une trentaine de mouvements possibles. Le joueur d'en face, pour chaque coup que tu as fait, peut en faire également une trentaine. Ce qui monte déjà à 30x30 = 900 coups. Et ça continue à grimper tres tres rapidement !

Pour te donner une idée, il me semble que le nombre de parties d'échecs possibles est de l'ordre de 10¹²⁰,soit 10⁴⁰ fois plus que le nombre de particules dans l'univers. Ce qui est bien sûr impossible à calculer.

Il existe donc des techniques qui permettent de ne pas explorer tous les coups, de ne sélectionner que les meilleurs. Mais la croissance du nombres de coup reste très rapide, et on ne pas très bien prédire des dizaines de coups à l'avance. C'est pourquoi des humains arrivent encore à battre des ordinateurs aux échecs. P

Par essaie de défier l'I.A. la plus pourrie pour un Awalé, tu ne peux pas gagner ! Dans ce jeu, le nombre de coups est très limité, et l'ordi peut calculer sans problèmes le déroulement de toutes les parties possibles, et donc choisir celle qui lui convient le mieux :p.

je crois qu'on a en gros 35 coup possible par tour (qui va en diminuant bien sûr) et qu'une partie se joue en une cinquantaine de tours (en gros). on a donc 50^35 états de jeux possible.
(pour plussoyer ce que dit sebsheep)

Hedi

Donc ce que je dois retenir c'est que c'est theoriquement possible mais qu'il faudrait un gros supercalculo qui fonctionnent pendant des annes c'est ca ? :heu:

Pas tout-à-fait car aux échecs il peut y avoir match nul, et un algorithme pour ce jeux peut t'assurer aux mieux de ne pas perdre, mais pas de gagner. Mais c'est un problème très complexe actuellement hors de portée ! Même pour un "gros supercalculo qui fonctionnent pendant des annes"

je pense à un truc : on ne peut pas assurer un gain parce que si on fait jouer notre algo contre lui même, les deux ne peuvent pas gagner ?
mais dans ce cas, si un jeu ne tolère pas de match nul, ça voudrait dire qu'il est infini (puisque l'un des deux doit forcément gagner) ?

Deep blue, c'est 1996 - 1997...

Petit rappel pour les plus jeunes :
http://fr.wikipedia.org/wiki/Deep_Blue

Un entretien - et pourquoi il n'y a plus pareil match.
http://www.lemonde.fr/sport/article/20 [...] 765_3242.html

Deep blue est très bon mais pas infaillible. Il ne suit pas une stratégie gagnante !

Citation : revan

Mais c'est un problème très complexe actuellement hors de portée !

Hors de portée pour les programmeurs ou faute de machine assez puissantes ??

@hedi07 tu as réson : comme revan l'a dit, il y a un algo qui peut t'assurer de ne pas perdre mais pas de gagner.

@namo Article interessant masi moi je m'interresse a la theorie des jeux ; je sais tres bien que les programme sont "tres fort". Ce que je veut savoir c'est si il peut y en avoir un "theoriqument", "mathematiquement" inbatable.

Citation : revan

Pas tout-à-fait car aux échecs il peut y avoir match nul, et un algorithme pour ce jeux peut t'assurer aux mieux de ne pas perdre, mais pas de gagner. Mais c'est un problème très complexe actuellement hors de portée ! Même pour un "gros supercalculo qui fonctionnent pendant des annes"

On ne sait pas actuellement si il n'existe pas un moyen pour un des deux camps de gagner toute les partie. La possibilité de match nul ne prouve pas l'inexistence d'une telle solution.

Citation : hedi07

je crois qu'on a en gros 35 coup possible par tour (qui va en diminuant bien sûr) et qu'une partie se joue en une cinquantaine de tours (en gros). on a donc 50^35 états de jeux possible.

On peut monter a bien plus de 50 coups, surtout si l'on s’intéresse aux partie hautement improbable (les deux joueur joue cette partie volontairement)... La seule limite au nombre de partie est le fait que le match est nul si la même position réapparait trois fois.

Citation : ramiK

Citation : revan

Mais c'est un problème très complexe actuellement hors de portée !

Hors de portée pour les programmeurs ou faute de machine assez puissantes ??

L'algo est déjà la (minmax) pour les programmeurs c'est très simple... L'ennui c'est la puissance, aucune machine n'est pour le moment capable de parcourir l'arbre complet des coups.

Oui la simple possibilité d'un nul n'assure pas qu'il n'y a pas de stratégie gagnante, mais il me semblait que c'était le cas aux échecs, au temps pour moi.

Citation : youyou

L'algo est déjà la (minmax) pour les programmeurs c'est très simple... L'ennui c'est la puissance, aucune machine n'est pour le moment capable de parcourir l'arbre complet des coups.

L'idée serait justement de trouver un meilleur algorithme. On ne compte pas seulement sur l'augmentation de la puissance de calculs sinon on ne s'en sortirait pas. Ici la puissance demandée est certainement au delà de ce qu'il semble actuellement "physiquement possible".

Citation : revan

Ici la puissance demandée est certainement au delà de ce qu'il semble actuellement "physiquement possible".>

"physiquement possible" ?? Pour avoir plus de puissance il ne suffit pas de rajouter des microprocceusseur ?? Ou bien il y a une limitte ?

La discussion part dans deux directions différentes.

On parle à la fois de :

1) Un logiciel capable de battre n'importe qui. Peut importe comment il s'en sort, quel que soit l'adversaire, il gagne. Pas forcément le plus vite ou le plus simplement.

2) Résoudre (par un logiciel ou autre) le jeu d'échec, comme on peut "résoudre" le morpion - trouver la partie parfaite, quel que soit le critère : la plus rapide, la plus imparable, etc.) - connaitre devant chaque situation les issues possibles, et les chemins pour y parvenir.

______________________________________

Au sujet de 1), depuis Deep Blue, les supercalculateurs ont prouvé qu'ils étaient au moins d'un niveau similaire à n'importe quel joueur. Certains champions, par une vision à long terme du jeu qui fait encore défaut à ces super-calculateurs, parviennent parfois à les vaincre.
Pour mieux faire, on peut tenter de taper plus fort (plus de puissance de calcul) ou de taper plus précis (modéliser ce que signifie une "stratégie de partie").

Au sujet de 2), le problème est entier (sauf pour la plus courte : trouvé, mat de l'idiot, ie : f4 e5 ; g4 Dh4).
On peut naïvement (sans offense) produire l'arbre de tout les coups possible, ce qui suppose une quantité de partie monstrueuse.
Mais est ce utile ?
2 rois qui se courent après, est ce vraiment la peine d'attendre le pat (2 pions face à face, ça ne change pas toujours tout) ?
À l'inverse, roi+dame contre roi, faut-il vraiment tout tester ?
Il existe donc un moyen plus efficace (= plus rapide / plus économe) qu'un algorithme naïf pour ça.
Et il faut probablement ET un algorithme travaillé ET une bonne puissance de calcul pour trouver la partie parfaite.
Personne n'a a ce jour réuni un algorithme assez efficace et une machine assez puissante.

Merci namo, c'est le sujet 2 qui m'interressait. Je crois que c'est toi qui a le mieux resumer tout ca : on utiliser la "solution naive" mais on le sais tous : c'est trop...euh...naive. :))

Citation : youyou

Citation : hedi07

je crois qu'on a en gros 35 coup possible par tour (qui va en diminuant bien sûr) et qu'une partie se joue en une cinquantaine de tours (en gros). on a donc 50^35 états de jeux possible.

On peut monter a bien plus de 50 coups, surtout si l'on s’intéresse aux partie hautement improbable (les deux joueur joue cette partie volontairement)... La seule limite au nombre de partie est le fait que le match est nul si la même position réapparait trois fois.

Oui bien sur, je voulais seulement parler des parties les plus courantes (donc avec envie de gagner et de ne pas passer des heures dans le même cycles).

Hedi

Il ne suffit pas d'appliquer des algorithmes non naïfs pour faire diminuer le temps de calcul.

Je donne une exemple précis : la multiplication matricielle. On sait qu'en théorie la complexité de l'algorithme ne peut être en dessous de O(n²) et l'algorithme naïf est en O(n^3). On arrive à des algorithmes en O(n^2.27) avec l'algorithme de Coppersmith-Winograd. Mais aucune implémentation n'a été trouvé jusqu'à présent ce qui montre bien la complexité en terme de mise en œuvre par un programmeur.
De même, il ne faut pas oublier que même si l'on gagne en complexité, on perd en stabilité numérique et les constantes multiplicatives dans le calcul de complexité sont tellement énormes qu'il est impensable de les utiliser.

Bref, tout ça pour dire que il y a une différence entre IA et algorithme. Si une IA peut-être très bonne mais faillible, un algorithme ne le sera pas. Par contre, l'implémentation peut-être très délicate, ou / et le temps de calcul irréaliste sur nos machines actuelles.

Quand tu peux voir que l'algorithme de résolution du problème du voyageur de commerce est en factoriel (à titre de comparaison, le problème pour 50 destinations prendrait 10^48 ans pour être résolu), on peut se demander combien de temps il faudrait à une machine chaque tour pour évaluer la situation de jeu.

Remarque : pour le dénombrement des coups, c'est plutôt <math>\(35^{50}\)</math>, et pas <math>\(50^{35}\)</math> : en gros, au premier tour, 35 possiblités, au second tour, 35 , donc <math>\(35 \times 35\)</math> possibilités.
Plus rigoureusement, on compte le nombre de 50-uplets possibles d'un ensemble à 35 éléments (de listes de coups possibles, où pour chaque coup, il y a 35 possibilités ).

Bon, pour revenir sur le thème initiale. Car tout le monde l'a zappé alors que pourtant c'est totalement faux.

Il n'y a pas toujours de stratégie gagnante pour le premier joueur (prenons par exemple le morpion, qui d'un point de vu théorique est identique aux échecs : les joueurs se partagent les mêmes informations et il peut y avoir gagne/perte/nulle, ainsi qu'un nombre fini de coups).

Néanmoins on sait que l'une de ses trois propositions est vérifiée :
*Blanc a une stratégie gagnante;
*Noir a une stratégie gagnante;
*Noir peut forcer le nul.

Ce théorème qui est quasiment évident provient du fait que le jeu est fini, et que chaque joueur détient les mêmes informations sur le court de la partie (on joue face visible).

Donc non, le premier joueur n'a pas forcément de stratégie gagnante.
D'ailleurs Capablanca pensait que le second joueur peut toujours forcer la nulle. Est-ce vrai ? On ne le saura sans doute jamais.

Il n'y a pas de stratégie gagnante pour une bonne raison : les échecs sont un jeu à somme nulle.
Deep Blue qui a battu Kasparov utilise un algorithme min/max amélioré, c'est à dire un calcul de probabilité de victoire selon un poids donné à un coup et aux coups à venir. Ces coups sont calculés par le parcours d'un arbre. Une probabilité de l'infini fait gagner ou perdre un joueur à coup sur selon le signe.

Cependant, en théorie il est possible d'explorer toutes les combinaisons de manière récursive mais en pratique non, tout simplement par qu'en informatique on ne peut pas gérer l'infini (donc ni obtenir une valeur qui serait l'infini en terme de poids (même si en fait c'est possible plus ou moins avec l'aide de calcul formel), ni explorer une infinité de combinaisons (c'est à dire le nombre de combinaison jusqu'à ce qu'un cheminement soit connu pour arriver à la victoire quelque soit les déplacements de l'adversaire).

L’algorithme de Deep Blue est un alpha beta qui permet de tronquer à la volé une partie de l'arbre à parcourir pour réduire le temps de calcul mais pour donner un exemple très simple sur un jeu de puissance 4, apparenté aux echecs et au morpion dans ce cas.
Il y a 7 colonnes possibles, donc 7 choix à chaque tour (on va négliger le fait qu'au bout d'un moment la colonne est pleine et que le choix se réduit...). Si l'on procède à un algorithme min-max naïf, avec une profondeur de 4 (c'est à dire une vision à 4 coups), on obtient un temps très raisonnable de réponse. Dès une profondeur de 7, on peut attendre 30 minutes sur les machines actuelles (de particulier j'entends), pour avoir une réponse de l'ordinateur.

Bref tout ça pour dire qu'en théorie oui, tu peux. En pratique non.
Et à mon sens, ce genre d'algorithme n'est pas réellement une IA, dans le sens où il est systématique et n'évoluera jamais avec les parties.

Citation

Il n'y a pas de stratégie gagnant pour une bonne raison : les échecs sont un jeu à somme nulle.

Huh? Ça n'a absolument rien a voir, un jeu peut être à somme nulle et avoir une stratégie gagnante pour un des joueurs.

Prend par exemple le puissance 4 : c'est un jeu à somme nulle (victoire +1, égalité 0, défaite -1), pourtant il existe une stratégie gagnante pour le joueur qui commence.

Le go, les échecs, les dames, l'awale... sont des jeux à somme nulle

Un jeu à somme non nulle c'est par exemple le dilemme du prisonnier

Au temps pour moi, je voulais plutôt formuler de la manière suivante : il n'est pas possible d'avoir d'algorithme qui donnera à coup sur une victoire, ce que j'explique par la suite.

Citation

Cependant, en théorie il est possible d'explorer toutes les combinaisons de manière récursive mais en pratique non, tout simplement par qu'en informatique on ne peut pas gérer l'infini (donc ni obtenir une valeur qui serait l'infini en terme de poids (même si en fait c'est possible plus ou moins avec l'aide de calcul formel), ni explorer une infinité de combinaisons (c'est à dire le nombre de combinaison jusqu'à ce qu'un cheminement soit connu pour arriver à la victoire quelque soit les déplacements de l'adversaire).

Sauf que le nombre de combinaisons aux échecs est finie, donc c'est possible d'avoir un algorithme qui te donnera une réponse en un temps fini (mais en pratique bien trop long, on est d'accord). En effet, aux échecs il y a un nombre fini de pièces, un nombre fini de cases, et qu'il est interdit de répéter la même position plus de 3 fois. Ceci implique qu'il n'y a pas de cycles et que chaque partie se termine en un nombre fini de coups => Il y a un nombre fini de parties d'echecs

Ceci dit, avec les ordinateurs quantiques à multivers hyperboliques de l'an 4321, même un algorithme naïf donnera la solution en un temps raisonnable

Le nombre de combinaisons est finie mais pas la profondeur de vision de l'algorithme.

Et pourquoi cette dernière serrai infinie alors que toute partie se fini en un temps fini?

Si tu construit l'arbre exhaustif des coups, il aura un nombre fini de noeuds, donc l'algorithme mettra un temps fini pour l'explorer... Je ne vois vraiment pas ou tu fais intervenir de l'infini là dedans

Citation : Floooder

Prend par exemple le puissance 4 : c'est un jeu à somme nulle (victoire +1, égalité 0, défaite -1), pourtant il existe une stratégie gagnante pour le joueur qui commence.

Ah bon ?
C'est quoi ?

http://www.connectfour.net/Files/connect4.pdf

Hod -> si je comprend bien ce que tu veut dire par "vision de l'algorithme infinie", il suffit de faire faire un graphe à l'algo et comme le nombre d'état est fini, le graphe sera aussi fini et donc on peut l'explorer en un temps fini (quoique très long on est d'accord).

Hedi