Je suis fan du jeu d´echec et je me posais cette question concernant l´intelligence artificielle :

Croyez-vous qu´un jour une machine sera capable d´annoncer de façon fiable à 100 pour 100, dès le premier coup des blancs : mat en x coups, quelques soit les "répliques" possibles des noirs.

Je sais pas si vous allez me comprendre mais je pense que les joueurs d´échecs verront de quoi je parle et seront aussi capable de réaliser en quoi cette performance serait extraordinaire

Sans être un mordu d´échec, ce que tu dis est et restera toujours impossible. Dans la mesure où un seul coup (le premier qui plus est) n´est pas suffisant pour déterminer l´issue d´une partie. Le premier mène à plusieurs solutions de toute façon donc impossible de savoir Mais dans une partie plus avancée c´est surement possible (et déjà possible actuellement)

Altonfrere-->tu dis que le premier coup n´est pas suffisant pour déterminer l´issu de la partie....je n´en suis pas si sur !

Tu sais, les champions, selon qu´ils jouent avec les noirs ou les blancs adoptent un jeu très différent : bien souvent-->avec les blancs, le jeu est tourné vers l´attaque et avec les noirs, c´est le contraire, le jeu est défensif.

oui mais c´est eux qui choisissent la stratégie, mais c´est tout simplement mathématique, un seul coup, surtout le premier n´est pas suffisant pour déterminer l´issue. Il existe plusieurs solutions, gagnantes, perdantes ou nulles (j´ai pas calculé mais c´est surement le cas).

Je ne connais pas bien les règles des échecs sur ce point, mais il me semble que si l´on revient plusieurs fois a la même position, la partie est considéré comme nulle.
Partant de ce principe, on peut dire que le nombre de coup maximale de coup dans une partie d´échec est fini.
Maintenant que l´on sait que le nombre de coup est fini, il suffit de tous les énumérer et de voir si tous les coups de noirs permettent a blanc de se placer dans un état ´gagnant´ (même raisonement éventuelleent pour noir)
Le nombre de coup étant fini, on peut tous les calculer (mais ca prend tres longtemps).
A ce que lo´n me dit, cette étude a déjà été fait (mais je n´ai pas plus d´info la dessus).

Apres la question est dans combien de temps disposerons nous d´un PC "de salon" qui répondra en moins de 1 millisecondes a cette question et nous pillera donc la gueule au blitz...

Le nombre de coup étant fini, on peut tous les calculer (mais ca prend tres longtemps)

le truc c´est que ce n´est pas "tres" longtemps, c´est "trop" longtemps. Il existe plein de probleme en informatique qui possedent une solution mais qui n´est pas trouvable en moins de plusieur milliers d´années (et meme en tenant compte des amélioration technique).

Il y a plein d´étude qui vise a chercher des solution "potable" a des probleme irresolvable dans un temps correct.
Par exemple :
prenons un vendeur ambulant, il a 75 villes a visiter; quel est le chemin le plus cours?
le nombre de chemin est fini et pourtant on peut toujours essayer de trouver le plus court chemin mais le marchand sera mort avant que la solution n´arrive...

donc pour le jeu d´echec je pense qu´une solution existe vu que le nb de partie différentes est fini mais il ne sera jamais possible de trouver LA solution

Dans le même genre mais pour un jeu beaucoup plus simple on peut assez facilement faire un jeu de morpion où l´ordinateur est invincible. Pour les échecs par contre le nombre de coups et de situations possibles est tellement plus vaste que cà parait effectivement assez difficile de faire un ordinateur qui prévoit tout à l´avance. Avec énormément de temps devant soi on pourrait, mais la question c´est justement de savoir combien de temps cà prendrait.

Oups, j´ai été un peu vite

C´est dès le premier coup qu´il demande, bah non , ce n´est possible.

Ya peut être un cas où ca peut s´appliquer à 100% dés le premier coup ....

si le joueur déclare forfait après son 1er coup, l´ordi peut à coup sur dire qu´il a gagné

je penses que la question de base était de savoir s´il y a une stratégie gagnante pour blanc (ou noir) au echec. On ne parle pas ici de trouver cette solution.

Par exemple le jeu K6 definit pas:
"on place 6 point en cercle. Deux joueurs de couleurs differente tracent chacun leur tour un trait de leur couleur. Le jeu est perdu par le premier jouer qui fait un triangle avec sa couleur."
(le jeu a toujours une fin car une bi-coloration des arretes du graphes complet a 6 sommets contient un triangle unicolore)
Ce jeu a une stratégie gagnante pour joueur 2. Elle a été prouvé par énumération de toutes les combinaisons. En outre on a pas d´algorithme donnant un coup gagnant a coup sur en temps raisonable.

guyver: 75 villes. trop facile, un b&c convergera en temps acceptable.

Pour info, je travaille sur la découverte d´algorithme d´approximation pour les problèmes d´ordonnancement.

La réponse est simple c´est NON!

On ne peut déterminer un nombre de coups précis apportant le mat, dès le premier coup on sait que le mat va varier de quelques coups jusqu´à environ 90. La limite fixée de 90 coups est abstraites, la question plus exacte serait de se poser: Combien faut-il de coups dans une partie pour voir un des deux camps prendre l´avantage?

Un mat peut trainer sur beaucoup de coups(cf finale roi fou cavalier vs roi).

Les ordinateurs du futur seront programmés et connaitront toutes les variantes des ouvertures même les moins utilisées. Le joueur d´échecs humain n´aura plus aucune chance face à la machine, les échecs ne vont pas tarder à signer leur fin!

Mais JAMAIS au grand JAMAIS un ordinateur pourra calculer un schéma de mat, cela demanderait une puissance jamais connue! De plus cela demanderait un travail très long d´analyse à la machine et le joueur humain en profiterait à la pendule!

euh je pense que ce que tu dis n´a pas vraiment de sens... Déjà toutes les pièces n´ont pas la faculté de revenir en arrière (cf les pions). Et même si un joueur s´amusait à faire cela, l´adversaire lui peut continuer à avancer et préparer son "attaque". Donc même en faisant le guignol on arrivera peut être plus vite à un mat ;)

Altonfrere > De la même façon qu´au morpion tu peux être sûr de ne pas gagner avant même d´avoir jouer le premier coup, aux echecs tu peux également être sûr de ne pas gagner avant d´avoir jouer le premier coup. Dans les deux jeu, dans le meilleur des cas tu fera nul (égalité).Le seul problème étant le temps de calcul beaucoup trop long qui fait qu´aujourd´hui il faudrait plusieurs millers d´années à un ordinateur pour calculer tous les coups possibles dans une partie d´échecs. Mais en théorie cela reste possible, comme pour n´importe quel jeu de plateau.

On peut être déjà sur d´une chose, les pc ne pourront jamais calculer tous les coups à l´avance. En revanche, ils sont assez puissant pour détroner n´importe quel joueur humain(cf fritz 9).
Les devellopeurs vont devoir s´orienter sur une accélération de la réfléxion de l´ordinateur pour procurer à celui-ci une quasi-invincibilité face aux humains.
En bref, dans moins d´une décénnie le jeu d´échecs va perdre de son attrait et c´est bien dommage...

Mouuh> et pourtant je peux t´assurer qu´après avoir joué le 1er coup (même sans avoir à calculer toutes les solutions) il est IMPOSSIBLE de dire que tu peux faire mat en x coups à coup sûr (c´est l´objet du post) quels que soient les actions de l´autre. Car tout simplement il y a de nombreuses solutions DIFFERENTES avec 1 seul coup joué dans la partie. Dans une partie déjà entamée (et bien entamée) c´est surement le cas, mais 1 seul coup je peux dire que non. Et l´exemple du morpion en est également un exemple, 1 seul pion joué et tu peux affirmer que quel que soit les coups suivans que tu gagneras ? ben non, tu l´as dit toi même tu peux assurer un nul ....

Altonfrere: tu dis ca comme ca ou tu peux le prouver ?
peutetre que noir arrive a faire un nul parceque blanc a mal jouer, mais peut etre blanc en jouant tout le temps bien peut s´assurer au premier coups qu´il joue qu´il gagnera a coup sur...

il est "logiquement" impossible de s´assurer de gagner à tout les coup : si on logiciel en était capable, en jouant contre lui-même il serait forcément mis en défaut.

Donc un logiciel capable de ne jamais perdre c´est "possible" (logiquement parlant), un logiciel capable de toujours gagner, c´est impossible.

Et bien comment dire ... j´ai l´impression de me répéter mais peut être que quelquechose m´échappe ;) Jouer 1 seul coup aux échecs, le premier donc n´est en rien suffisant pour dire que le mat en x coups est à 100% prédéterminé.

Tout simplement parcequ´il n´existe pas QUE des solutions qui mènenet au mat avec seulement 1 coup joué ... voilà tout, enfin c´est ainsi que je vois la chose.

Donc prétendre qu´il existe une (au moins une) solution en x coups pour arriver au mat dés le premier coup joué, ca OUI c´est surement vrai (calculable ca c´est autre chose). Mais dire qu´il existe QUE des solutions qui mènent au mat et d´après la question du post peu importe comment le joueur déplacera les pions, ca j´y crois pas ;)

Sinon cette histoire d´echec et de machine qui gagnet dés le début....

Tu l´as pas vu dans Futurama????

non parceque dans une episodes ya un robot qui bat tout le monde aux echecs en annoncant le resultat en x coups au début de la partie ^^

Altonfrere > Ok t´as raison désolé, j´ai en effet pas vraiment répondu à la question posée initialement, on ne parlait simplement pas de la même chose ^^