Apprendre les règles des échecs

11

Une question similaire demande si un ordinateur peut apprendre à jouer de manière optimale aux échecs en analysant des milliers de jeux.

Si une machine peut regarder l'état du plateau pour quelques parties d'échecs (ou quelques parties de dames) au début et après chaque coup, peut-elle être programmée pour apprendre les règles du jeu?

Si c'est le cas, dans quelle mesure (par exemple, serait-il en mesure de rendre compte du roque ou de la promotion) est-ce que cela fonctionnerait? Quels algorithmes d'apprentissage automatique rendraient cela possible?

Yktula
la source
3
La machine devrait pouvoir atteindre un état où elle peut dire "J'ai vu ce mouvement effectué, je suppose donc que je peux le faire dans des circonstances similaires." Que cela constitue "l'apprentissage des règles" est presque une question philosophique. ;)
décompose le
@deceze Eh bien, vous n'avez pas tout à fait raison. En apprenant les règles, on veut dire pouvoir bouger compte tenu de la disposition qui n'était jamais arrivée au programme auparavant. Sinon, ce n'est pas apprendre les règles mais mémoriser les mouvements.
2
@Max L'ordinateur pourrait-il effectuer correctement des mouvements qu'il n'avait jamais vus auparavant? Disons, il a vu le chevalier se déplacer deux fois en avant et un sur le côté plusieurs fois, mais jamais deux en arrière, un sur le côté. Comment pourrait-il dire en toute confiance quelles sont les règles concernant le mouvement des chevaliers? Peut-être y a-t-il une clause spéciale dans les règles qui stipule que "les chevaliers ne peuvent pas reculer, seulement avancer" (tout comme les pions). Déduire des règles avec certitude semble donc impossible. Cela vaut également pour les humains.
décompose le
8
@Max En fait, il pourrait y avoir un nombre infini de règles que l'ordinateur ne peut pas déduire . On the 8th turn the knight may not turn right. On a sunny day the pawns may jump over bishops.L'ordinateur ne peut pas dire pourquoi ce pion n'a pas bougé à un tour particulier. Peut-être y avait-il une règle interdisant son déplacement dans cette circonstance particulière. Par conséquent, l'ordinateur ne doit pouvoir reproduire que des modèles similaires (en fait, exacts), mais ne doit jamais pouvoir déduire les règles avec une confiance de 100%.
décompose le
@deceze Oui, c'est possible si vous lui avez montré cette règle. De la même manière que vous devez enseigner les règles à l'homme (par exemple, donnez-lui l'impression des règles à lire), vous devez en quelque sorte fournir ces règles à la machine. Le moyen le plus simple est de rejouer TOUTES les règles dans une certaine quantité de jeux pour que la machine les apprenne. Il en va de même pour les humains - les humains ne le sauront pas On a sunny day the pawns may jump over bishops.si vous ne lui avez jamais montré cela.

Réponses:

10

Si une machine peut regarder l'état du plateau pour quelques parties d'échecs (ou quelques parties de dames) au début et après chaque coup, peut-elle être programmée pour apprendre les règles du jeu?

Certainement pas pour quelques parties d'échecs; vous devez en analyser un nombre incroyablement élevé pour l'empêcher de faire des mouvements invalides. Combien, je ne sais pas; ce problème appartient au domaine de la théorie de l'apprentissage computationnel, de l'apprentissage PAC et du problème de la capacité d' apprentissage dans la limite .

Les algorithmes de classification suggérés par les autres affiches pourraient être capables d' apprendre de manière discriminatoire les règles des échecs: étant donné deux configurations de plateau, ils pourraient répondre «oui» ou «non» à la question de savoir si un mouvement valide se transforme l'un en l'autre. Avec un certain effort, ils pourraient également être utilisés pour générer des mouvements. Cependant, ils généreront uniquement des mouvements qu'ils ont vus dans les jeux sur lesquels ils ont été formés, ou généreront une combinaison de mouvements valides et invalides, chacun avec un score indiquant la probabilité qu'ils considèrent le mouvement en question, avec des règles invalides. j'espère obtenir de très faibles probabilités.

(C'est-à-dire que le programme ne reconnaîtrait pas certains mouvements valides à sa disposition; ou vous pourriez être en mesure de tricher sans qu'il s'en aperçoive; ou vous devriez le former pendant si longtemps que vous perdez tout intérêt pour le jeu.)

Pour les techniques qui peuvent apprendre les règles, consultez la programmation logique inductive et la programmation génétique . Je ne sais pas si quelqu'un a déjà essayé de les appliquer à l'apprentissage des échecs; étant donné que les règles des échecs sont fixes, il est beaucoup plus intéressant (même pour les universitaires) de créer de bons programmes de jeu d'échecs plutôt que ceux qui doivent apprendre les règles de base à partir de zéro.

Fred Foo
la source
4

Les règles des échecs sont assez complexes et certaines sont très rarement exécutées dans une partie.

Par exemple la règle en passant . Combien de jeux devrez-vous observer pour en déduire que le premier mouvement n'est autorisé qu'après le mouvement en deux étapes?

Un autre exemple. Le carré B peut être attaqué en long roque. Combien de jeux voyez-vous où cela se produit?

En d'autres termes, vous aurez besoin de beaucoup, de très nombreux jeux pour dériver correctement toutes les règles.

Mais, peut-être, Google trouvera un coin de son cloud pour une archive complète des jeux d'échecs "bientôt" ...


la source
"Le carré b peut être attaqué en long roque" quel est ce mouvement? Pouvez-vous l'expliquer ou le lier pour moi?
CaffGeek
@chad, également appelé castling queenside - la notation "0-0-0" est utilisée. Seuls les trois domaines que les rois "touchent" ne peuvent pas être attaqués.
2
En outre, le carré d ne peut pas être attaqué lors du roque queenside (ou le carré f lors du roque kingside) ; vous ne pouvez pas non plus roquer après avoir déplacé votre roi. Comment êtes-vous censé savoir que quelque chose ne peut pas être fait en observant des jeux où cela n'a pas été fait? Comme le mentionne Lars, l'ordinateur pourrait attribuer des probabilités qu'un mouvement soit valide, mais il est impossible de déterminer cette règle spécifique en observant les jeux.
BlueRaja - Danny Pflughoeft
De plus, il y a eu des matchs, même par des grands maîtres dans un cadre de tournoi, où les règles ont été enfreintes , et aucun des joueurs ne l'a remarqué! Selon les règles du tournoi, si aucun joueur ne le remarque dans les 10 coups, le jeu est valide et continue. (Je me souviens très clairement d'un jeu où un grand maître a déplacé son roi, puis l'a reculé, et plus tard roque. Je ne le trouve pas maintenant, cependant)
BlueRaja - Danny Pflughoeft
1
en passant est assez rare mais il y a des règles de tirage forcé qui sont BEAUCOUP plus rares. Je joue depuis 40 ans et je n'ai jamais vu un jeu où vous pourriez avoir un tirage forcé d'avoir 50 coups sans mouvements de pion et sans captures. Je pense qu'il y a une autre règle de ce genre dont je ne me souviens même pas. Dans la pratique, les joueurs vont accepter un match nul avant d'être invoqués. (Ils existent pour vous assurer que vous ne pouvez pas "gagner" une position tirée en la faisant glisser jusqu'à ce que votre adversaire quitte.)
Loren Pechtel
2

Oui et non

Je ne sais pas si vous demandez s'il est possible d'apprendre les règles des échecs en utilisant l'apprentissage automatique / les réseaux de neurones ou s'il est possible de former une machine d'échecs de niveau "grand maître" en l'utilisant.

Vous pouvez certainement enseigner à un ordinateur les règles et un certain niveau d'échecs en les utilisant. Cependant, je ne pense pas que vous puissiez le former à un niveau supérieur en l'utilisant. L'informatique n'a pas encore réussi à produire une machine capable de "comprendre" les échecs d'un point de vue positionnel / intuitif. Tous les ordinateurs d'échecs actuels utilisent une base de données étendue, des calculs de force brute et éventuellement un apprentissage automatique.

Je suppose que cela dépend si vous comptez utiliser une base de données de référence pour tricher ou non :) En outre, il est difficile de savoir si vous pouvez réellement séparer le fait de savoir que beaucoup de jeux sont bons. Les humains qui sont bons aux échecs sont bons précisément parce qu'ils ont vu tellement de jeux qui sont référencés par la partie du cerveau qui est généralement connue pour reconnaître les visages. De ce rappel, il semble que les joueurs d'échecs humains soient capables de développer une «intuition» de la force d'une position.

Homde
la source
les meilleurs grands-maîtres mémorisent de vastes livres d'ouverture et ce n'est pas considéré comme de la triche. Et de toute façon, il arrive tout le temps que ce qui était autrefois considéré comme une bonne variation d'ouverture soit brisé par une nouvelle idée. Ainsi, la "triche" de jouer les mouvements du livre n'est peut-être même pas le moyen optimal pour un ordinateur de jouer.
Kevin
2

Comme beaucoup de commentaires l'ont dit, il s'agit presque d'une question philosophique débattant de la définition de «apprendre». La plupart des programmes d'intelligence artificielle reposent sur la détermination de solutions rationnelles. Étant donné suffisamment de données, un programme d'apprentissage des échecs en IA déterminera une liste de mouvements rationnels à effectuer dans certaines situations. Cela ne signifie pas qu'il connaît les règles des échecs, il comprend simplement quels mouvements sont bénéfiques et lesquels ne le sont pas. Même si l'ensemble de données comprend des joueurs effectuant des mouvements illégaux, le mouvement illégal entraînera une perte instantanée, donc l'IA l'ignorera et n'utilisera jamais ce mouvement car il n'est jamais bénéfique.

Peu importe que des réseaux de neurones ou des algorithmes évolutionnaires ou tout autre type d'algorithme d'apprentissage soient utilisés, un ai ne peut jamais apprendre explicitement des règles en observant quelque chose, il ne peut que déterminer une liste d'options rationnellement bénéfiques.

SC Ghost
la source
2

Si vous considérez les règles des échecs comme le moteur physique du jeu et les lois de la physique comme les règles acceptées permanentes et inflexibles de l'univers, pensez au peu de "lois" réelles dans notre univers naturel. Il est extrêmement difficile, voire impossible, de faire une règle dure et rapide, mais nous pouvons faire un certain nombre de théories testées et acceptées à partir d'un moment précis.

Cela POURRAIT être possible en supposant que l'ordinateur observe et enregistre les mouvements, mais NE fait PAS directement d'affirmations sur les mouvements valides.

Par exemple, il observerait un pion avancer d'une pièce et ferait de nouvelles hypothèses que toutes les pièces ne peuvent avancer que d'une case, et une autre qu'un pion ne peut avancer que d'une case. Il formera autant d'hypothèses restrictives que possible jusqu'à ce que le prochain mouvement se produise et un certain nombre d'entre elles peuvent être levées ou rendues plus libérales.

Finalement, après tant de mouvements, vous aurez un ensemble de théories solides, mais ce sera un ensemble de données vivant approchant en permanence de 0 mais ne l'atteignant jamais.

Donc, la réponse est qu'un ordinateur pourrait faire une très bonne estimation, mais il (EDIT: NON) connaîtra les règles à coup sûr.

maple_shaft
la source
1

En théorie - oui, c'est possible. Il peut même devenir grand maître d'échecs. La réponse que vous cherchez est des réseaux de neurones . Les réseaux de neurones sont essentiellement la même chose qui se produit à l'intérieur de notre cerveau. De plus, étant donné le réseau neuronal parfaitement conçu (lu - incroyablement parfait) et un matériel parfait - il peut apprendre tout ce qu'un être humain peut apprendre de la même manière, voire mieux.

En savoir plus à ce sujet:

bezmax
la source
2
Cette "réponse" n'est qu'un ensemble de liens Wikipédia, dont deux décrivent le même concept, dont l'un est extrêmement large, et dont l'un n'a rien à voir avec le problème en question. Veuillez montrer comment une carte de Kohonen serait utilisée pour apprendre efficacement les règles des échecs.
Fred Foo
1
L'ANN et le NN ne sont pas du tout proches de la complexité d'un véritable neurone / cerveau humain, un ANN est au mieux une approximation grossière hideuse.
Darknight
"en théorie, la théorie et la pratique sont les mêmes, mais en pratique elles ne le sont jamais." Les programmes d'échecs peuvent jouer comme des grands maîtres, mais je ne pense pas que ce soit à cause des réseaux de neurones ou de l'apprentissage automatique. La plupart des bons programmes utilisent de vastes livres d’ouverture, des bases de table de fin de partie et une recherche approfondie en premier ("negamax avec élagage alpha bêta"), et une fonction d’évaluation probablement très compliquée (qui est très probablement écrite avec l’aide de grands maîtres).
Kevin
Les réseaux de neurones ne peuvent apprendre que ce pour quoi ils sont formés. Les échecs ont des règles qui sont très rarement appliquées, mais qui font partie du jeu. Serait-il légal de devenir évêque? Serait-il légal de devenir un roi?
2
Ha ... la promotion au roi rend l'échec et mat un peu plus difficile!
Kevin
1

Je pense qu'il peut apprendre les mouvements qu'il est autorisé à faire simplement en analysant, mais comment pourrait-il apprendre les mouvements qu'il n'est pas autorisé à faire? Par exemple, le pion ne semble jamais avancer d'une case quand une pièce adverse est devant lui. Comment l'ordinateur sait-il si c'est par choix du joueur ou s'il n'est pas autorisé à le faire? Vous pouvez trouver un algorithme qui dit que si 99,99% du temps ou plus un événement ne se produit pas, cela signifie que vous n'êtes pas autorisé à le faire, mais cela pourrait également être 99,99% du temps considéré comme un événement. mauvais coup, mais que 0,01% du temps c'est le coup qui gagne la partie. Donc, ma réponse est non, il ne peut pas apprendre toutes les règles simplement en analysant les jeux, mais il peut probablement en apprendre suffisamment pour jouer à un jeu.

Tremper
la source
1

C'est une question philosophique. Vous pourriez aussi bien demander si une personne pourrait apprendre à jouer aux échecs uniquement en observant les gens pendant qu'ils jouent aux échecs. En fait, c'est fondamentalement le même genre de question que Nelson Goodman pose dans son grand livre Fact, Fiction, and Forecast : comment passer d'un ensemble fini déjà fait à une prédiction d'observations futures. Les observations déjà faites seraient les mouvements d'échecs observés jusqu'à présent et les observations futures seraient tous les mouvements d'échecs qui ne se sont pas encore produits. La question est de savoir s'il existe une relation nomologique entre les observations passées et les observations futures (par opposition à la relation purement causale entre les événements passés et les événements futurs)?

Si nous interprétons le mot nomologique comme par une loi de la nature ou de la logique et que rien ne peut jamais arriver en désaccord avec cette loi alors, il n'y a certainement pas une telle relation, car la première personne qui déplace un château en diagonale, violerait la loi de la nature et l'univers tel que nous le connaissons s'effondrerait.

Mais même si, en fait, par un accident de la nature, chaque coup que n'importe quel joueur d'échecs dans le monde ferait à partir de maintenant, était valide (personne ne ferait jamais d'erreurs ou essayerait de tricher et même les gens ne savent rien des règles des échecs commencerait à pousser des pièces d'échecs au hasard dans tous les sens, mais accidentellement toujours selon les règles), cela ne nous convaincrait pas qu'il existe une loi de la nature (ou une loi de la logique) qui a forcé tout cela. Nous considérerions cela comme purement accidentel.

Ludwig Wittgenstein a couvert un terrain similaire dans ses recherches philosophiques . Il insiste sur le fait que toute série d'observations est conforme à de nombreuses règles arbitraires, voire contradictoires. Par exemple, si tous les jeux d'échecs observés par moi auraient happend dans l'après - midi, ma règle pourrait être l'après - midi , l'évêque ne peut être déplacé en diagonale . Le fait que l'heure ne soit pas importante pour le jeu est quelque chose que je n'ai pas pu observer car je n'ai pas observé les parties d'échecs à différents moments de la journée. Ou, incidemment, si je n'ai jamais vu une femme jouer aux échecs, alors la règle pourrait être que l'évêque ne peut être déplacé que par des hommes.. Ce qui est pertinent pour une observation et ce qui ne l'est pas est déterminé comme une condition préalable à l'observation et ne peut pas faire partie de l'observation elle-même.

BTW: La solution de Wittgenstein au problème est assez similaire à celle de Goodman. Je ne gâcherai pas la surprise;-)

Addenda:

À l'époque où Sussman était un novice, Minsky est venu une fois vers lui alors qu'il était assis à pirater le PDP-6.

"Que faites-vous?", A demandé Minsky. "J'entraîne un réseau neuronal câblé au hasard pour jouer au Tic-tac-toe", a répondu Sussman. "Pourquoi le réseau est-il câblé au hasard?", A demandé Minsky. "Je ne veux pas qu'il ait des idées préconçues sur la façon de jouer", a déclaré Sussman.

Minsky ferma alors les yeux. "Pourquoi fermez-vous les yeux?" Sussman a demandé à son professeur. "Pour que la pièce soit vide." À ce moment, Sussman était éclairé.

pillmuncher
la source
-4

Non

Parce que simplement apprendre des schémas (via quelle méthode que ce soit) n'est pas la même chose que "apprendre à jouer aux échecs de manière optimale".

Cela nécessite une planification et une stratégie, ce qui est très différent du simple apprentissage de modèles d'ensemble.

Nuit noire
la source
1
Vous ne le savez pas vraiment; en outre, la question est de savoir s'il est possible (pour un ordinateur, mais les mêmes contraintes s'appliqueraient probablement également aux humains) d'apprendre les règles réelles des échecs simplement en analysant des exemples de jeux.
tdammers
1
Je pense que vous avez mal compris la question ...
maple_shaft
Après avoir travaillé (mémoire de maîtrise) avec l'IA (réseaux de neurones), je suis pratiquement sûr que non. Sauf si vous avez des preuves pour dire le contraire, vous ne pouvez pas simplement dire "vous ne savez pas cela"
Darknight