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....)
