Comment utiliser l'intelligence artificielle dans les échecs informatiques

19

Dans certains articles (historiques), les échecs ont été appelés la drosophile de l'intelligence artificielle. Bien que je suppose que dans la recherche actuelle, la simple application d'un algorithme de recherche est au mieux une science informatique avancée , je pense qu'il existe encore des domaines où appliquer (et pratiquer) les techniques d'IA.

Un exemple simple serait l' apprentissage du livre d'ouverture où l'on peut enseigner au programme s'il faut utiliser ou non certains mouvements dans l'ouverture parce que le programme n'est pas adapté à certains types de position. Nous pouvons utiliser une forme d'apprentissage par renforcement et automatiser ceci: je suppose que je pourrais jouer le programme contre lui-même et augmenter la probabilité de gagner des lignes et diminuer la probabilité de perdre des lignes.

L'exemple le plus complexe consiste à utiliser une fonction d' évaluation des apprentissages (par exemple, on pourrait modifier les valeurs des tableaux carrés ). Cependant, je pense:

  • étant donné tout le bruit dû à l'énorme quantité de positions réalistes (par opposition à la quantité de lignes d'ouverture réalistes)
  • et avec le coût (durée) d'une partie d'échecs sur ordinateur et la nécessité de jouer des charges.

Comment faire cela efficacement? (ou devrais-je regarder d'autres techniques, par exemple les réseaux de neurones.)

ljgw
la source
3
L'approche standard est l'alpha-beta minimax élagué. avec une heuristique. Il s'agit de la famille de recherche de l'IA, plutôt de la famille d'apprentissage automatique.
Lyndon White
2
Les vrais maîtres d'échecs se souviennent essentiellement de tous les jeux auxquels ils ont déjà joué ... Ils ont donc une forte mémorisation.
2
Il y a aussi la demande reconventionnelle. Je ne me souviens pas qui l'a dit mais ça se passe comme ça. Les biologistes utilisent des expériences sur la drosophile pour obtenir une compréhension de plus en plus profonde de la physiologie, de la génétique, etc. Les gens de l'IA écrivent des ordinateurs d'échecs pour être de mieux en mieux aux échecs. Cela ne nous apprend pas grand-chose sur l'informatique; ce serait comme les biologistes qui élèvent des drosophiles ultra-rapides et super-fortes et les font se battre.
David Richerby
par rapport à la métaphore, elle est vraisemblablement plus que "la drosophile de l'intelligence artificielle" sous différents aspects, surtout en considérant qu'elle n'a pas battu de façon décisive le meilleur humain jusqu'en ~ 1997, et que les recherches s'y poursuivent, etc.
vzn

Réponses:

16

L'espace d'état entier pour les échecs est énorme - il peut être approximativement estimé à 10 43 (nombre Shannon (Shannon, 1950) , ( Wikipedia )).

L'idée que vous présentez - des agents d'apprentissage par renforcement jouant ensemble pour apprendre le jeu - a été appliquée avec succès à Backgammon - TD-Gammon (Tesauro, 1995) , ( chapitre sur l'apprentissage par renforcement de Sutton & Barto ). Il a également utilisé Neural Networks pour estimer la fonction de valeur du jeu. Ce problème est cependant beaucoup plus simple, car le nombre d'états dans Backgammon est significativement plus petit que dans les échecs, à savoir: 18,528,584,051,601,162,496 (thread Backgammon Forum Archive ).

Si toutefois vous mettiez fin au jeu après quelques mouvements initiaux et ne visiez qu'à apprendre de "bonnes ouvertures", vous pourriez réussir avec une approche analogue. Le principal problème serait d'évaluer le jeu après le match d'ouverture, ce qui semble difficile. Une simple mesure de similitude avec les positions établies après des ouvertures bien connues ne suffit pas, car la position peut être loin d'eux si l'adversaire fait un geste stupide (ce ne serait donc pas à cause de l'erreur de l'agent d'apprentissage, donc la position même si "incorrecte" "devrait être évalué comme un bon résultat).

Les références:

BartoszKP
la source
1
La partie la plus difficile est en effet de trouver un moyen empirique de noter le résultat des ouvertures. Différentes ouvertures sont bonnes de différentes manières, il existe donc probablement une multitude d'ouvertures acceptables.
JDong
3

Je suis à peu près sûr que toute méthode possible (ou bizarre) d'IA ou de ML dans les manuels a été essayée et a échoué à peu près par rapport à la simple force brute.

Mon point de vue personnel est que les échecs en soi ne sont plus d'aucun intérêt pour l'IA moderne ... Simplement, parce qu'ils sont résolus : en utilisant simplement un ordinateur moderne et la force brute. Donc, je ne pense pas qu'il soit nécessaire de créer un système "intelligent" pour le résoudre plus efficacement (fonctionne très bien sur mon téléphone portable), et je pense qu'il n'y a même pas besoin d'un inconnu et plus approche "intelligente" pour exister.

iliasfl
la source
1
Je ne sais pas pourquoi cela a été rejeté. L'argument selon lequel les échecs sont "résolus" est un peu inexact, en ce sens qu'aucun ordinateur ne peut regarder une position possible et l'évaluer parfaitement. Cela dit, iliasfl est convaincu que les échecs ont perdu l'essentiel de son attrait pour la recherche sur l'IA. D'une part, les meilleurs programmes d'échecs informatiques sont désormais beaucoup plus puissants que les meilleurs humains, étant donné suffisamment de puissance de traitement et de temps. Cela rend de plus en plus difficile pour les programmeurs d'évaluer même le fonctionnement d'un algorithme.
elixenide
1
Merci, j'ai dit résolu en ce sens que la force brute est une solution. Bien sûr, la communauté de l'IA (en général pas seulement ici) n'est pas satisfaite de cette "solution". Cependant, nous avons déjà un système informatique qui présente un comportement "intelligent" pour résoudre cette tâche, et même gagner les meilleurs humains, point. Personnellement, je crois que les échecs seront hors sujet pour l'IA après quelques années, lorsque la masse actuelle des universitaires qui ont consacré une carrière à l'attaquer prend sa retraite.
Je n'appellerais pas les implémentations d'échecs informatiques actuelles comme `` résolues par la force brute '' - elles recherchent toujours d'énormes quantités de gamestates, mais il y a de nombreux composants de force non brute là-bas. Bien sûr, ce n'est pas une solution "de style humain" qui se généraliserait bien à d'autres problèmes, mais je ne serais pas surpris que si nous avions une IA d'échecs "de style humain", alors ce serait plusieurs ordres de grandeur en moins efficace que les solutions spécialisées actuelles, ce qui la rend tout simplement inférieure.
Peteris
Je pense que cette réponse et ses commentaires ont été clairement réfutés par AlphaZero de Google: en.wikipedia.org/wiki/AlphaZero Même si vous acceptez les critiques concernant la configuration de Stockfish et qu'ils ont dessiné toutes les correspondances, un système qui est arrivé à ce niveau avec quelques heures de formation est nettement supérieur.
Kamal
2

Je pense qu'il convient de noter que pour déterminer comment résoudre un problème d'IA, vous devez le définir. Qu'il soit entièrement observable ou partiellement observable , et qu'il soit déterministe ou stochastique / chance.

Les échecs sont entièrement observables (contrairement au backgammon, au monopole ou au poker par exemple). Il est également déterministe (comme les dames et les go par exemple). Enfin, des adversaires existent et, pour cette raison, lors de la détermination du meilleur coup suivant, il est utile d'utiliser le type de recherche contradictoire. des algorithmes tels que MiniMax. La classification d'un problème peut nous aider à déterminer le type d'algorithme de recherche que nous souhaitons appliquer. Et en cas d'échecs, la recherche contradictoire conviendrait.

Minimax en particulier a un

O(bn)

O(bm)

Donc, en cas d'échecs, b serait 35 et m serait 100. Il existe des moyens de le contourner ou des stratégies pour le rendre plus efficace, comme la coupure alpha-bêta.

Iancovici
la source
Il convient également de noter dans ce contexte que les jeux de fin d'échecs pour un maximum de pièces sont déjà tabulés - une optimisation supplémentaire.
BartoszKP
Il s'agit de l'approche normale mais pas d'une approche d'apprentissage automatique. La question utilise la balise Machine-learning.
Lyndon White
@Oxinabox bien que cela soit vrai, le demandeur n'a mentionné aucun endroit dans le titre ou le corps qui l'intéressait dans l'approche d'apprentissage automatique, seulement à la fin où il partageait un exemple d'une approche qu'il avait en tête. Il n'est pas nécessaire de limiter le problème à l'apprentissage automatique, ni à un seul algorithme d'apprentissage (NN).
Iancovici
En effet, c'est bien
Lyndon White
pour être précis, les échecs ne sont pas pleinement observables, car étant donné une position que nous ne savons pas, par exemple, un roi ou une tour a déjà été déplacé ou non, bien qu'il soit important pour la génération de mouvements (le roque est-il toujours possible?), mais un programmeur peut le rendre entièrement observable en modifiant la représentation de la position en différenciant le roi / tour non déplacé et le roi / tour déplacé en tant que figures différentes, bien que cela ajoute quelques difficultés.