Problème des 8 reines

[Liet Kynes]

Bonjour,

vieux problème, 92 solutions.
Le problème étendu aux grands échiquiers semble être résolu : https://arxiv.org/abs/2107.13460

https://interestingengineering.com/a...m-about-queens
-----

[Deedee81]

Salut,

Ah ben dis donc c'est costaud ! Merci pour la ref.

[Liet Kynes]

C'est pas compréhensible pour un joueur d'échecs

En tout cas cela montre qu'un problème simple à poser est souvent difficile à transposer dans une approche permettant de développer des outils de résolutions..
J'espère que l'on aura un bel article dans PLS

[Deedee81]

Salut,

C'est vrai. Et ce serait formidable d'avoir quelque chose d'équivalent pour le problème de la balade du cavalier. On n'a qu'une estimation "à la louche" du nombre (faramineux) de solutions.
Quand j'étais jeune (il y a quarante ans) je me suis beaucoup amusé à chercher toutes sortes de solutions. Difficile mais faisable.
Je l'ai aussi programmé avec un système expert : misère, beaucoup plus difficile qu'on ne pourrait croire !

Par contre la programmation optimisée des 8 reines, ça c'est facile. Je l'avais fait .... en BASIC Avec un truc amusant :
- Sur TRS 80 : calcul une nuit entière affichage des 92 solutions quasi instantané
- sur VAX : calcul : quelques secondes, affichage (sur terminal imprimante) : une bonne demi-heure

J'espère que l'on aura un bel article dans PLS

Bonne remarque. Qui sait

[A voir en vidéo sur Futura]

[Liet Kynes]

Salut,

C'est vrai. Et ce serait formidable d'avoir quelque chose d'équivalent pour le problème de la balade du cavalier. On n'a qu'une estimation "à la louche" du nombre (faramineux) de solutions.
Quand j'étais jeune (il y a quarante ans) je me suis beaucoup amusé à chercher toutes sortes de solutions. Difficile mais faisable.
Je l'ai aussi programmé avec un système expert : misère, beaucoup plus difficile qu'on ne pourrait croire !

Par contre la programmation optimisée des 8 reines, ça c'est facile. Je l'avais fait .... en BASIC Avec un truc amusant :
- Sur TRS 80 : calcul une nuit entière affichage des 92 solutions quasi instantané
- sur VAX : calcul : quelques secondes, affichage (sur terminal imprimante) : une bonne demi-heure


Bonne remarque. Qui sait

la programation c'est un truc que j'aurai aimé apprendre, j'ai juste bricolé un peu avec visual basic sur excel mais depuis que je suis sur libre office j'ai laissé cela de côté.. Cela devrait être enseigné au collège comme une matière à par entière car c'est bon pour l'esprit (logique/language/créativité...).

Pour le problème du cavalier, Wikipedia donne des dénombrements pour les circuits ouverts et fermés: https://fr.wikipedia.org/wiki/Probl%..._des_solutions
Pour les circuits ouverts la référence de la suite est donnée mais pas la méthode (à priori via ordinateur): https://oeis.org/A165134

On aura un jour un sujet: quelle est la nature mathématique des echecs?

[Liet Kynes]

Une petite perle à lire : http://eulerarchive.maa.org/docs/originals/E309.pdf (le site est sympa : http://eulerarchive.maa.org/ )

[Deedee81]

Salut,

merci, bizarrement j'avais un chiffre infiniment plus grand en tête. Je crois que j'ai confondu avec le nombre de parties légales : https://fr.wikipedia.org/wiki/Nombre_de_Shannon

On aura un jour un sujet: quelle est la nature mathématique des echecs?

Facile : combinatoire et arbres de décision Discipline, théorie des jeux (avec ce bon vieux théorème du minimax de von Neumann et la bonne vieille amélioration alpha-bêta bien connue de ceux qui programment des jeux de ce style)

[Deedee81]

On s'est croisé (ma faute, j'ai mis longtemps pour répondre après avoir ouvert la page). Merci pour la ref, elle est vraiment chouette (j'aime bien le "paroit" ). Je connaissais son existence (lue dans le Que sais-je sur les échecs quand j'étais enfant) mais je ne l'avais jamais vu.

[Liet Kynes]

Facile : combinatoire et arbres de décision Discipline, théorie des jeux (avec ce bon vieux théorème du minimax de von Neumann et la bonne vieille amélioration alpha-bêta bien connue de ceux qui programment des jeux de ce style)

Le théorème du minimax est-il possible dans une partie contre une IA ou deux IA entre elles?

Par exemple, un truc qui m'interesse aux echecs sont les cases contrôlées dans une partie, j'essaie depuis un moment d'observer des parties uniquement de ce point de vue là. J'ai l'idée de donner des couples de valeurs puis de calculer des indices.. cela permet de s'extraire du bias classique que l'on peut avoir en connaissant le materiel en jeu..
Mais j'ai du boulôt avec ce truc

[Ernum]

Le théorème du minimax est-il possible dans une partie contre une IA ou deux IA entre elles?

Par exemple, un truc qui m'interesse aux echecs sont les cases contrôlées dans une partie, j'essaie depuis un moment d'observer des parties uniquement de ce point de vue là. J'ai l'idée de donner des couples de valeurs puis de calculer des indices.. cela permet de s'extraire du bias classique que l'on peut avoir en connaissant le materiel en jeu..
Mais j'ai du boulôt avec ce truc

Il va falloir aussi détecter derrière la position, quelle stratégie est mise en place, ou voir si un piège tactique ne si cache pas; ce qui changera de facto la valeur de tes indices. Bon courage .

[Liet Kynes]

Il va falloir aussi détecter derrière la position, quelle stratégie est mise en place, ou voir si un piège tactique ne si cache pas; ce qui changera de facto la valeur de tes indices. Bon courage .

Bof, je veux voir le côté point d'équlibre/point de rupture de façon globale, la stratégie ou le piège tactique vont diminuer des valeurs à certains points clé de la partie mais pas forcement changer l'équilibre de forces. Quelque part c'est un peu comme chercher le moment ou la fourmi de Langton prends la bretelle d'autoroute

[Ernum]

Ben tu te fais piquer ta dame par une tactique que tu ne connais pas alors que stratégiquement tu semble gagnant, ça peut faire basculer la partie. Le problème est de détecter le point de rupture à l'avance dans ce cas.
Intéressant que tu parles des "véhicules", la fourmi de Langton comme dans le go offre des figures connues, on peut les répertorier. Mais bon je ne suis pas informaticien ou algorithmicien (ça se dit ça?) , juste un très petit joueur d'échecs et je risques ici de ne plus rien comprendre à la discussion .

ps: pour Deedee, les échecs pour moi dans les années 80, c'était uniquement comme adversaire à Sargon III sur Apple2 . Apprentissage de la programmation (Basic uniquement, assembleur j'ai laissé tomber) en solo avec des bouquins fourni avec la bestiole achetée d'occase à un ingénieur (ma première paye de boulot d'été y est passée, on ma pris pour un fou, mais je me suis bien éclaté pendant mes nuits blanches). Pas d'interface graphique il va sans dire, un écran noir et un curseur vert en bas, même pas de minuscules sur le clavier QWERTY.

[Ernum]

Voila à quoi je faisais référence pour le go entre autre:

Shischo

[Deedee81]

Salut,

Le théorème du minimax est-il possible dans une partie contre une IA ou deux IA entre elles?

Le théorème concerne le jeu en lui-même, pas les opposants ou leur manière de jouer.

Par exemple, un truc qui m'interesse aux echecs sont les cases contrôlées dans une partie, j'essaie depuis un moment d'observer des parties uniquement de ce point de vue là. J'ai l'idée de donner des couples de valeurs puis de calculer des indices.. cela permet de s'extraire du bias classique que l'on peut avoir en connaissant le materiel en jeu..
Mais j'ai du boulôt avec ce truc

Ah là oui, je confirme, les cas faibles et contrôlées c'est un ENORME chapitre dans tout bon livre de stratégie. Donc les étudier sur partie aussi forcément.
(c'est pas le seul élément, mais c'est un élément important).

Après tu parlais d'équilibre/rupture, c'est aussi très important et presque un art de détecter ça (pour les joueurs humains).
Et Ernum a raison, mixer tactique et stratégie est aussi unart. Mon opinion est qu'il ne faut jamais faire l'impasse sur les possibilités tactiques mais que celles-ci doivent rester au service de la stratégie (par exemple, une difficulté classique est évaluer la position obtenue après une dizaine de coups de part et d'autre évalués mentalement pour une manoeuvre tactique.... bon l'horloge aussi est une difficulté, j'ai vu une partie de Fine où il s'est fait mater par Alekhine simplement parce qu'il ne l'a pas vu venir : plus que quelques secondes à l'horloge.... heu, quand je dis vu, je veux pas dire à l'époque hein, j'étais pas né ) C'est rare de voir un mat entre grands maîtres.

Ernum, j'ai pas connu Sargon III, l'outil que j'ai préféré est ChessMaster (mais j'ai beaucoup apprécié comme beaucoup le fameux battle chess, il avait fait sensation ).

Et le shisho, ah oui, je ne me souvenais plus du nom mais c'est un des grands classiques dans l'étude du go (vraiment très classique vu que je le connais Je suis vraiment un joueur médiocre au go, pas assez d'entrainement).

[polo974]

Une petite perle à lire : http://eulerarchive.maa.org/docs/originals/E309.pdf (le site est sympa : http://eulerarchive.maa.org/ )

Une perle avec une coquille...

dans le premier tableau, en haut à gauche, il y a la 42, il faut donc passer à la 43 pour aller à la 44, hors il n'y a que la 45, mais en fait, c'est bien la 43 (avec La coquille), la "vraie" 45 se trouvant sur là 2ème ligne, plus à droite...

[Deedee81]

Salut,

Une perle avec une coquille...
dans le premier tableau, en haut à gauche, il y a la 42, il faut donc passer à la 43 pour aller à la 44, hors il n'y a que la 45, mais en fait, c'est bien la 43 (avec La coquille), la "vraie" 45 se trouvant sur là 2ème ligne, plus à droite...

C'est pas grave, on peut s'arrêter à 42 car c'est la solution à toute chose
(ceci dit, bien vu, tu as l'oeil)

[Liet Kynes]

J’ai tendance à penser que la coquille vient de l’imprimeur

[polo974]

J’ai tendance à penser que la coquille vient de l’imprimeur

Je ne pense pas qu'il y aura une réédition pour corriger ça...

[Liet Kynes]

Salut,



Le théorème concerne le jeu en lui-même, pas les opposants ou leur manière de jouer.



Ah là oui, je confirme, les cas faibles et contrôlées c'est un ENORME chapitre dans tout bon livre de stratégie. Donc les étudier sur partie aussi forcément.
(c'est pas le seul élément, mais c'est un élément important).

Après tu parlais d'équilibre/rupture, c'est aussi très important et presque un art de détecter ça (pour les joueurs humains).

Perso je cherche à relier cela à un concept traduisible d'un point de vue maths mais c'est franchement complexe (combinaisons juxtaposées d'algorythmes ? )
Il n'y a rien d'exploitable à l'oeil humain ( comme pour les problèmes des 8 reines ou de la marche du cavalier) mais clairement assez d'infos pour entrainer une IA.

[Deedee81]

Salut,

Traduire ça en math ? Galère.

En algorithme à la rigueur : algorithmes d'évaluation d'une position et algorithmes d'analyse "a priori" de l'arbre de coups. J'ai beaucoup joué avec ce type de programmation (je prenais souvent des jeux plus simples pour expérimenter). J'ai parfois obtenu des résultats sensibles et je les ait testé à l'époque sur l'othello réversi (qui a le bon goût d'être facile à programmer et optimiser).

On peut aussi jouer avec des IA par la technique des systèmes experts ou diverses méthodes d'apprentissages (auto-évaluation, stockage de positions). J'ai beaucoup joué à ça aussi mais les résultats sont médiocres aux échecs.

Et pour le deep learning.... là je ne sais pas comment on pourrait faire. Je n'aurais pas pu expérimenter à l'époque, ça n'existait pas

Et si c'est exploitable par l'oeil humain. Ou as-tu été chercher une telle idée absurde ???? Ca fait partie de la formation de tout bon maître ! Les bouquins sur l'analyse des cases faibles et des contrôles de cases ça n'a pas été écrit pour des machines
(en fait dans le domaine stratégique, l'homme a toujours été infiniment meilleur que la machine.... jusqu'à l'arrivée du deep learning. Me rappelle ce foutu problème de l'horizon qui rendait les programmes médiocres surtout en finale : c'est le fait qu'en analysant à 10 coups de profondeur, ce qui est ultra long, tu peux rater un truc visible au 11eme coup alors qu'un humain y arrive sans difficulté en finale car lui ne fait pas d'analyse combinatoire)

[Deedee81]

Traduire ça en math ? Galère.

Un exemple. J'ai étudié la théorie des jeux (au sens des maths, pas juste de la programmation) (par moi-même, ça ne faisait pas partie du cursus d'un ingénieur civil en électricité ).
Et je m'étais posé la question suivante. Soit un jeu à information parfaite donné. Soit une technique de type minimax basée sur une analyse arborescente de profondeur N.
Peut-on, déterminer s'il existe une valeur de N à partir de laquelle la technique donne la meilleure stratégie (au sens théorique) ?

Evidemment il y en a une : la profondeur maximale du jeu quand elle existe (c'est le cas aux échecs). Mais j'espérais trouver une valeur plus faible évidemment.

Résultat : je me suis cassé les dents. C'est pourtant une question relativement simple, juste au-dessus de la théorie actuelle comme le théorème du minimax. Et je me suis même persuadé que d'un point de vue algorithmique la réponse est du style NP-Complet. Une horreur.

Bien sûr ce n'est pas une preuve. Mais obtenir une formulation mathématique (pas algorithmique) des questions de stratégie échiquéennes : autant vouloir décrocher la Lune avec un filet à papillons : c'est beaucoup plus facile

[Liet Kynes]

Bien sûr ce n'est pas une preuve. Mais obtenir une formulation mathématique (pas algorithmique) des questions de stratégie échiquéennes : autant vouloir décrocher la Lune avec un filet à papillons : c'est beaucoup plus facile

Oui et c'est là que je trouve rien d'exploitable pour l'oeil humain dans les valeures données par chaque case ou groupes de case pour le contrôle.
Pour une IA ces valeurs peuvent servir d'indicateur stratégique mais je pense de plus en plus qu'il ne s'agit plus vraiment de calculs.. ce qui est absurde s'agissant d'un ordi.

[Deedee81]

Salut,

Oui et c'est là que je trouve rien d'exploitable pour l'oeil humain dans les valeures données par chaque case ou groupes de case pour le contrôle.

J'avoue que je ne comprend pas. On trouve ça dans pleins de bouquins sur les échecs.... pour humains. Les valeurs des cases, les cases faibles, les contrôles de case, c'est presque le b.a.ba de tout joueur !!!!

Ou alors je ne comprends pas ce que tu veux dire ce qui est bien possible.

ce qui est absurde s'agissant d'un ordi.

Pourquoi ça ? Les ordis ne font pas que des calculs Même au niveau processeur classique : tu as des instructions de test, de copie de données, etc...
Au niveau des datas, c'est binaire mais ce n'est pas nécessairement des nombres, ça peut être juste un codage/une manière "d'écrire" autre chose (images, lettres....)
Et en deep learning c'est encore pire puisque c'est des réseaux de neurones formels. Ce n'est plus du tout du calcul.

Et de toute façon l'algorithmique c'est quand même un aspect fort particulier des maths.

Le domaine mathématique sans doute le plus proche des deux (le jeu et l'ordi joueur) est sans doute la théorie des graphes. Il y a énormément de choses là derrière (théorèmes, conjectures,...) Mais j'ignore si tu y trouverais ton bonheur.

[Liet Kynes]

Salut,



J'avoue que je ne comprend pas. On trouve ça dans pleins de bouquins sur les échecs.... pour humains. Les valeurs des cases, les cases faibles, les contrôles de case, c'est presque le b.a.ba de tout joueur !!!!

Ou alors je ne comprends pas ce que tu veux dire ce qui est bien possible.

En fait je ne trouve rien qui puisse être un concept mathématique dans les cases contrôlées.
Pour illustrer à une position donnée correspond pour chaque case un nombre de fois pour laquelle elle est contrôlée par les blancs et un nombre pour les noirs, il est possible d'en tirer une différence ( ce que l'on fait toujours avant chaque coup) et on sait qu'il est important généralement de bien contrôler le centre.

Pourquoi ça ? Les ordis ne font pas que des calculs Même au niveau processeur classique : tu as des instructions de test, de copie de données, etc...
Au niveau des datas, c'est binaire mais ce n'est pas nécessairement des nombres, ça peut être juste un codage/une manière "d'écrire" autre chose (images, lettres....)
Et en deep learning c'est encore pire puisque c'est des réseaux de neurones formels. Ce n'est plus du tout du calcul.

Et de toute façon l'algorithmique c'est quand même un aspect fort particulier des maths.

Le domaine mathématique sans doute le plus proche des deux (le jeu et l'ordi joueur) est sans doute la théorie des graphes. Il y a énormément de choses là derrière (théorèmes, conjectures,...) Mais j'ignore si tu y trouverais ton bonheur.

Ah ben oui je suis d'accord qu'il y a un process logique pour décider d'un coup pour l'ordi (if/then/else) mais il lui faut quand même ces valeurs de contrôle des cases à chaque coup à priori mais pour le deep learning l'apprentissage est décrit comme se passer des règles et c'est là que je ne comprends pas.
Si par exemple la base d'apprentissage est l'information contenant les valeurs des cases en terme de contrôle et que l'ordi propose comme coup une nouvelle répartition des valeurs avec pour feed back coup illégal/coup légal et quand la partie se termine le résultat de la partie gagné/perdu/nul est-ce qu'une IA type alpha go progresserait ?

Je mets une illustration de ce que j'entends par cases contrôlées
(en haut à droite: case contrôlées par les blancs à gauche par les noirs et en dessous les différences pour la position de l'échiquier)

controles.jpg

[Deedee81]

Salut,

Je ne m'y connais malheureusement pas assez en deep learning pour répondre à ça.

[Liet Kynes]

A priori méthode de Monte Carlo, mais il me semble qu’il faut quand même une simulation des coups possibles et donc intégrer des règles de déplacement et de prise basé les cases contrôlées cela semble interessant: mais je n'y connais rien et quelque part même si les approches pour résoudre les problème type 8 reines ou marche du cavalier sont balaises c'est d'une certaine façon plus facile à comprendre

[Deedee81]

Salut,

A priori méthode de Monte Carlo, mais il me semble qu’il faut quand même une simulation des coups possibles et donc intégrer des règles de déplacement et de prise basé les cases contrôlées cela semble interessant: mais je n'y connais rien et quelque part même si les approches pour résoudre les problème type 8 reines ou marche du cavalier sont balaises c'est d'une certaine façon plus facile à comprendre

Ah tiens, ça a été tenté ça (pas par moi, je l'ai lu sous la plume de David Levy). Une analyse de type Monte-Carlo des positions aux échecs a donné un programme terriblement médiocre. (je n'ai pas la référence, j'avais lu ça dans un "vieux" magazine de l'Ordinateur Individuel à l'époque où il n'était pas encore trop "commercial" ).

Personellement j'ai aussi utilisé une méthode statistique mais sur les coefficients d'évaluation et sur un jeu fort simple : le tic tac toe. Résultats ..... catastrophiques.

Clairement les jeux combinatoires se prètent très mal à ce type d'approche sauf peut-être à un niveau plus profond ? (ne connaissant pas bien le deep learning, je ne veux pas trop avancer en disant s'il s'apparente ou pas à ce type d'approche).

[Liet Kynes]

Clairement les jeux combinatoires se prètent très mal à ce type d'approche sauf peut-être à un niveau plus profond ? (ne connaissant pas bien le deep learning, je ne veux pas trop avancer en disant s'il s'apparente ou pas à ce type d'approche).

C'est évoqué comme mode de fonctionnement "Similar to AlphaGo and AlphaZero before it, MuZero uses Monte Carlo Tree Search2, short MCTS, to aggregate neural network predictions and choose actions to apply to the environment." dans cette page d'explication du fonctionnement de muzero : https://www.furidamu.org/blog/2020/1...ntuition/#fn:2

[Deedee81]

Salut,

C'est évoqué comme mode de fonctionnement "Similar to AlphaGo and AlphaZero before it, MuZero uses Monte Carlo Tree Search2, short MCTS, to aggregate neural network predictions and choose actions to apply to the environment." dans cette page d'explication du fonctionnement de muzero : https://www.furidamu.org/blog/2020/1...ntuition/#fn:2

D'accord, merci. Faudra que je me penche sur le deep learning (je connaissais bien les techniques de neurones formels mais.... avant le deep learning, avec la fameuse méthode de propagation des erreurs et la limitation à trois couches. Je suis comme Cromagnon essayant de comprendre le monde moderne )

[Liet Kynes]

Perso j’aimerais bien juste un peu comprendre mais je crois que c’est arrivé à un stade ou il n’y a plus de vulgarisation "grand public" possible, il y a la définition des hyperparamètres qui me fait m'interoger sur MuZero mais je ne suis même pas certain d'avoir vaguement saisi cette notion

Le top du top est d'entendre parler désormais de neurosciences de l'inteligence artificielle :

https://www.polytechnique-insights.c...-a-lautonomie/