Je ne participe pas à des tournois de haut niveau.

Les ouvertures de départ que j'aime bien sont:

• la sicilienne: je trouve ça vachement sympa de forcer l'autre à suicider un pion dès le début du jeu, avec D2-D4.
  
• la défense russe: E2-E4 E7-E5 ChevalierF3 Chevalier F6. Je trouve ça cool de viser le match nul.
  
• le gambit roi: super casse gueule. J'ai jamais réussi à en faire un correct, pour l'instant.
  
• le gambit de Budapest: vachement galère à jouer, mais c'est la technique utilisée par Homer Simpson

This post was edited by Chevaucheur on May 9 2018 03:19pm

Aux échecs, il y a deux façons de jouer:

• soit on joue par la catégorisation: on cherche à conquérir le centre, on cherche à obtenir un avantage matériel (plus de pièces) ou positionnel (des fous bien placés, en position d'attaque)
  
• soit on joue par l'anticipation: on analyse les parties qui ont été jouées, on s'entraîne en jouant contre Deep Fritz, on fait des analyses mathématiques pour chercher le meilleur coup.

Avec les échecs "modernes", c'est-à-dire les échecs depuis qu'il existe une base de données importante, le jeu a bien changé.
Magnus Carlsen représente bien ce concept d'échecs "modernes", en atteignant le score historique de 2882 au classement ELO.





Désormais, les deux approches ont été faites:

• la catégoriation
  
• et l'anticipation

Alors on peut espérer que le jeu des échecs sera bientôt résolu.

This post was edited by Chevaucheur on May 11 2018 02:19am

Le jeu d'échecs ne sera pas résolu avant qu'une technologie plus avancée permettent soit de créer tout l'arbre de coups d'une partie, soit d'évaluer toutes les positions sur l'échiquier. Bon, il y a quelques cas particuliers, ou des patterns de fin de partie, mais ce n'est pas encore suffisant pour "résoudre" le jeu. On sait qu'il existe au moins une stratégie optimale, encore faut-il la trouver !

C'était la minute théorie des jeux, présentée par Brelmen !

C'est intéressant, est-ce que vous pouvez développer?
Qu'est-ce que vous entendez par "évaluer toutes les positions sur l'échiquier"?

Le problème du jeu d'échecs (qui est encore plus visible dans le jeu de Go d'ailleurs, mais c'est un peu différent) c'est qu'il y a un très grand nombre de coups possible (10^140)."Résoudre" le jeu signifie trouver une combinaison de coups qui nous amène à un solution optimale du jeu (la meilleure possible).
Ici, on est dans un jeu fini (il y a 2 joueurs, un échiquier de taille fini et un nombre de pièces fini), donc on sait qu'une stratégie optimale (meilleure que les autres) existe forcément. Pour arriver à cette stratégie, il faut évaluer tous les coups possibles (bon, il y a des shortcuts mais en gros on va dire qu'il faut évaluer tous les coups possibles), afin de déterminer le gain qu'il y a pour chaque coup.
Par conséquent, tu es "obligé" d'évaluer toutes les positions des pièces sur l'échiquier pour arriver à trouver le meilleur coup, parmi tous les coups possibles. Il y a beaucoup de profondeur, parce que le meilleur coup n'est pas forcément celui qui t'apporte le plus gros gain à l'instant t, mais celui qui t'apporte le plus gros gain à l'instant t + n.
C'est un problème qu'on appelle "combinatoire", parce qu'il faut tester toutes les combinaisons possibles, sans exception, et choisir la meilleure.

D'ailleurs, on est aussi capable de dire à quoi ressemble la solution optimale des échecs : c'est un nul entre les deux joueurs. Ca s'explique assez simplement : en théorie des jeux, les deux joueurs du jeu ont accès à la même information (toute l'information possible ici, puisque c'est un jeu complet), et chaque joueur cherche à maximiser un gain. A un certain moment, on va arriver à ce qui s'appelle un "équilibre de Nash", c'est à dire un point où les deux joueurs ne peuvent plus changer de stratégie : si ils changent de stratégie, ils ne gagnent rien. Ca se traduit par un match nul. C'est la stratégie optimale puisque le gain des deux joueurs est ... maximisé. Tout ça est vrai uniquement si les deux joueurs prennent à chaque fois les meilleures décisions (et donc jouent selon la stratégie optimale).

C'est un problème qui nécessite énormément de capacité de calcul avec les algorithmes qu'on connaît. Donc à moins d'avoir une capacité de calcul bien supérieur à la normale OU de trouver un algorithme beaucoup plus efficace (c'est possible mais improbable), les échecs ne peuvent être résolusen l'état. Mais ils le seront un jour, c'est certain ! Ils le sont déjà partiellement d'ailleurs, grâce à des heuristiques.

This post was edited by Brelmen on May 11 2018 06:03am

??

A ma connaissance personne ne sait avec certitude s'il existe une stratégie gagnante pour blanc, noir, ou aucun des deux (je suis d'accord que c'est probablement "aucun des deux", mais rien n'est prouvé).

Le fait que le jeu soit à information complète ne permet pas de conclure car l'ordre blanc -> noir introduit une asymétrie entre les joueurs.

Je vois pas d'où tu sors ton 10^140 non plus, y'a beaucoup beaucoup plus de coups possibles aux échecs. Et quand bien même tu prendrais le chiffre plus raisonnable de 10^50=2^166, on arrivera jamais à bruteforcer ça

La combinatoire, c'est ce qui correspond à "l'arbre de coups d'une partie", non?

Vous avez parlé d' "évaluer toutes les positions sur l'échiquier".
Ça me paraît être une meilleure solution.

Avec la combinatoire, le logiciel doit:

• faire attention à éviter la redondance (si ce sont les mêmes coups qui sont joués en boucle, la partie n'a plus de sens)
  
• vérifier que les cases sont libres à chaque mouvement (comme si un humain qui marche devait chaque fois vérifier qu'il y a bien le sol sous ses pieds, à chaque pas): ça complique le programme, et ça requière plus de capacités de calcul

Avec la combinatoire, j'ai l'impression que la partie ça ne consiste plus en un déplacement des pièces.
Avec la combinatoire, la partie consiste en une sorte d'échange entre une case vide et une case avec une pièce.
Je me trompe peut-être.

Moi, ce qui me paraît intéressant plutôt, c'est d'évaluer toutes les positions sur l'échiquier.



Imaginons par exemple qu'on attribue un nombre à chacune des cases de l'échiquier.
Ça ferait donc un total de 64 nombres attribués.
Et ces nombres dépendraient de la position des pièces sur l'échiquier (les nombres changeraient donc à chaque tour).

Ces nombres seraient une méthode de quantification.
C'est un peu comme si on réussissait à quantifier notre victoire.

Ces nombres n'auraient pas la prétention d'anticiper toutes les combinaisons possibles.
Ces nombres auraient par contre la prétention de permettre de jouer le meilleur coup possible.



En fait, cette technique est déjà possible.
Quand un joueur a un fou de retard, on peut par exemple "quantifier sa victoire" à ~20 unités arbitraires.
L'idée, c'est d'avoir une quantification plus précise.
Et elle finirait par être tellement précise qu'elle permettrait de trouver le meilleur coup à jouer.

Le défi, ce n'est donc pas de trouver la stratégie de victoire.
Le défi, c'est d'affiner nos méthodes de quantification de la victoire.

Ce n'est pas un défi absolu qui finirait:

• soit par une réussite (tous les coups optimaux ont été découverts)
  
• soit par un échec (les coups optimaux n'ont pas été découverts)

C'est un défi relatif: l'objectif étant alors seulement de progresser, doucement, à notre rythme.
[Comme Ellana, la chevaucheuse de brume]

This post was edited by Chevaucheur on May 11 2018 09:33am

Voici les calculs que fait Deep Fritz:



On voit bien qu'il fait de l'anticipation, il fait de la combinatoire.
Il fait des calculs de profondeur.
Moi, mon idée, ce serait de rompre avec ce système, et de créer de la quantification de victoire.

Moi, ce que je pense, c'est que c'est possible de jouer de manière optimale aux échecs, et ce, sans rien anticiper.
Si la catégorisation est suffisamment bonne, et si la quantification de victoire est suffisamment bonne, alors il me semble qu'il n'y a pas besoin de faire des calculs de "profondeur".

This post was edited by Chevaucheur on May 11 2018 09:41am