RÉSOLUTION TOTALE DU JEU D'ÉCHECS: RÉFLEXIONS,MÉTHODOLOGIES DE RÉSOLUTION, OUVER
acx01b
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
-
24 avril 2007 à 20:43
cs_OFE Messages postés 1 Date d'inscription mardi 18 décembre 2007 Statut Membre Dernière intervention 18 décembre 2007 - 18 déc. 2007 à 22:43
cs_OFE Messages postés 1 Date d'inscription mardi 18 décembre 2007 Statut Membre Dernière intervention 18 décembre 2007 - 18 déc. 2007 à 22:43
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/42426-resolution-totale-du-jeu-d-echecs-reflexions-methodologies-de-resolution-ouvertures-correlatives-du-sujet-algorithme-et-programme-de-calcul-de-tous-les-tableaux-principaux-successifs-possibles-a-partir-d-une-position-valide-quelconque
https://codes-sources.commentcamarche.net/source/42426-resolution-totale-du-jeu-d-echecs-reflexions-methodologies-de-resolution-ouvertures-correlatives-du-sujet-algorithme-et-programme-de-calcul-de-tous-les-tableaux-principaux-successifs-possibles-a-partir-d-une-position-valide-quelconque
18 déc. 2007 à 22:43
je dois dire que tout cela n'est pas très sérieux. Les commentaires du genre, "mais les instructions de saut d'échappements : continue; break; return [ expression ] n'ont pas fonctionné correctement sans doute dû au fait que la gestion des empilements et dépilements multiples imbriqués successifs n'est pas correctement gérée par Windows XP" me font bien rigoler. Qui peut sérieusement croire à ce genre d'inepties ? Il faut être bien naïf pour se laisser impressionner par ce déluge de termes techniques sans queue ni tête.
Je propose que ootbtdkg2 publie son code source afin qu'on puisse juger de la qualité de son code !!!!!!!!
17 déc. 2007 à 18:43
17 déc. 2007 à 16:59
"N'oubli pas qu'une partie d'échec peut durer facilement 200 coups"
or au final, ces parties la sont uniquement celles qui sont disputees entre deux joueurs qui conaissent parfaitement la theorie...
pour info, j'ai joue seulement un an en club, donc pour le titre de GMI, on pourra attendre plusieurs decenies :)
maintenant, si t'es GMI, tu sais probablement que sur les N coups possibles sur chaque plateau, t'as pas enormement de coups qui ne conduisent pas a une situation avec un gros desaventage, donc t'as pas tant de coups que ca qui ammeneront a une partie de 200 coups
17 déc. 2007 à 05:11
16 déc. 2007 à 17:46
16 déc. 2007 à 17:42
Tu semble avoir des théories assez posées et intelligente. J'ai compris les principes sur lequel tu t'appui et je n'en tire qu'une conclusion : elles sont très bien théoriquement du fait de leurs complexité ainsi que leur profondeur idéal. PAR CONTRE, je tien a t'informer que ton idée de résoudre le jeu d'échec est beaucoup trop ambitieuse. Il ne faut pas oublier la pratique car même avec les meilleures théories, la seule façon de «résoudre» les échecs est d'analyser tout les coups possibles à partir de la position de départ. N’oubli pas qu'une partie d'échec peut durer facilement 200 coups (fait le calcul : ( 400*35)exp 197) si on considère que les 2 partie ne font aucune erreurs. Bref, tes idées sont excellentes mais irréalisable jusqu'à preuve du contraire. Si tu complète ton programme envoi le moi et je le testerais contre mes chess engines.
13 déc. 2007 à 14:32
Voici quelqes ordres de grandeur.
* Nombres de parties d'échecs possibles 10 puissance 128
* Nombre d'atomes dans l'univers 10 puissance 80
* Limite de Bremermann 10 puissance 93
Un calculateur de la taille de la Terre et, ayant travaillé depuis son origine à la vitesse maximum théorique, n'aurait pas encore identifié toutes les parties d'un jeu d'échec.
Cela dit, si quelqu'un veut calculer exhaustivement les parties d'échecs, il peut toujours essayer. Il lui faudra juste beaucoup de temps (quelques milliards d'années) et beaucoup de matière (quelques univers ?).
Références:
http://villemin.gerard.free.fr/Puzzle/EchecSol.htm
http://villemin.gerard.free.fr/Puzzle/EchecSol.htm#terre
http://villemin.gerard.free.fr/Science/Atome.htm#Approche
16 nov. 2007 à 14:51
16 nov. 2007 à 13:49
4 nov. 2007 à 04:04
en résumé, il marche ou pas le programme?
14 mai 2007 à 13:12
Salut PapiVB
je voudrais grandement te remercier pour les pertinentes adresses URLs que tu mentionnes !!
j'en ferais bon usage !!!!!
Pour ce que précisément combine l'algorithme et le programme ! :
c'est la combinatoire des pièces sur l'échiquier et leurs couleurs respectives !
ainsi que leurs cases de déplacement pour les fous et de couleurs de prises pour les pions!!!
c'est tout !!!
cela a pour but de déterminer le nombre de tableaux principaux !!!! quelquesoit leur positions
sur l'échiquier !!!!!
en fait leur position précise n'est pas déterminée!!!
seule leur validité d'existence est vérifiée !!!!!
ainsi avec cette estimation maximale de près d'1 milliard de tableaux principaux !!!!!
on peut estimer donc le nombre de positions totales au jeu d'échecs !!!!!
l'objectif indirectement atteint !!!!!
qui si on s'en tient au nombre maximal de coups jouables pour une position donnée par toutes
les pièces présentes sur l'échiquier !
donne un nombre maximal de positions différentes au jeu d'échecs qui sera de
quelques milliers de milliards seulement !!!!!
et c'est là où cela devient intéressant!!!!!
comme tu l'as dit je ne passes pas par les théories d'estimation de coups minimax et
alpha beta , etc!!!! car elles ne tiennent pas compte des cycles qui peuvent se répéter de
manière infinie et de manière finies quelconques!! et donc sont de mauvaises méthodes qui
donnent !! malgré tout des résultats partiels !!
et qui font avancer quelque peu les choses!!
mais ne sont pas la bonne méthode à appliquer pour la résolution totale du jeu d'échecs !!!!!
qui est spécifiquement un jeu combinatoire et cyclique !!!!!
et comme tel !! il faut chercher à le résoudre !!!
s'il n'y avait pas les cycles !! avec ces méthodes le jeu serait depuis longtemps résolu !!!!!
mais qui pris comme tels ne peuvent résoudre complètement le jeu d'échecs car elles ne
permettent pas !! de résoudre les choix litigieux quant à la sortie de cycles imbriqués distincts
et pouvant permutés de très nombreuses fois!!!
Pour ce qui est des calculs à effectuer pour résoudre totalement le jeu d'échecs !!!!! je dois dire qu'il n'est pas
nécessaire de faire 10 puissance 47 calculs !!!!!
ou tout autre chiffre exorbitant !!
car plusieurs positions sont immédiatement déclarables comme nulles ou pats ou perdantes!!!!
par exemple lorsque le matériel ne permet pas de mater ! 2 rois et 2 cavaliers par exemple !
ou lorsque les coups sont successivement forcés par des échecs menant au mat!!!
de plus par symétrie on peut résoudre les positions réciproques pour le camp adverse dans la
base de donnée des positions sans calculs complexes !! simplement en permutant les
valeurs des couleurs !!!
bref !!!!!
il ne sera pas nécessaire d'effectuer la combinatoire des milliers de milliards de parties entre
elles !!!!!
néanmoins la difficulté reside dans les cycles possibles infinis et relatifs combinables sur
plusieurs niveaux d'imbrications et dont la résolution est quelque peu sensible!!!!!
mais reste faisable sans forcément !! évidemment faire plus de 2 fois un même cycle !
principal !!! car la seconde fois on sait qu'on est dans la reprise du même cycle et on a alors
le choix sur les coups suivants à jouer !!!!!
on peut donc choisir de répéter une troisième fois ????? la succession de coups hiérarchiquement
ordonnée, structurée et stockée dans notre base de donnée de la structure de donnée des
positions du jeu d'échecs !!!!!
mais cela est inutile !!!!!
d'où d'ailleurs la très logique règle FIDE qui veut que l'on puisse annuler une partie lorsque
la même position se répète 2 fois et que le trait revient au joueur qui l'a commencée !!!!!
ou rentrer dans un sous-cycle partiel ! qui lui aussi sera ordonnancé, structurée et stocké !!!
ainsi de suite on fera la liste hiérarchique de toutes les posssibilités de cycles infinis ou
partiels possibles par le cycle principal dans lequel on se trouve !!!!!
et ainsi de suite on fera toutes les positions du jeu d'échecs ! et on résolvera le problème
entièrement et parfaitement !!!!!
Ceci dit!! pour les quelques milliards éventuels de parties qui auront chacune plusieurs milliers,
millions ou milliards de cycles possibles de permutations de positions des pièces sur l'échiquier sans
aucune prise !!!!!
Il faudra pouvoir stocker toutes ces positions respectives !!!! et les classer !!!!
selon quelles sont des combinaisons :
d'un même ou de plusieurs sous-cycles distincts mais convergeants à divers sous-cycles gagnants !
d'un même ou de plusieurs sous-cycles distincts mais convergeants à divers sous-cycles perdant !
d'un même ou de plusieurs sous-cycles distincts mais convergeants à divers sous-cycles pat !
d'un même ou de plusieurs sous-cycles distincts mais convergeants à divers sous-cycles nul !
Ce qui donne un nombre faramineux de calculs à effectuer !!!!! et je ne pense pas raisonnablement !!
que cela puisses être autre chose qu'un travail collectif humain pour ne serait-ce que analyser
globalement l'étendue des données recoltées !!! quelquesoit le travail de synthèse des algorithmes et
programmes qui seront appliqués !!!!!
aussi loin d'être découragé !! je suis enthousiaste et dois même être réconforté par le fait que cette
entreprise puisse être résolue par un travail d'ensemble de plusieurs personnes !!!
il ne faudra pas non plus négliger l'utilisation d'un supercalculateur !! ou alors un réseau important de
pcs effectuant du calcul distribué !!!!! pour venir à bout de ces milliards de milliards de calculs à
effectuer !!!!!
Néanmoins toute bonne résolution doit passer par des algorithmes intelligemments conçus et des
programmes optimisés au mieux pour faciliter les temsp de calculs et de réponses !!!!!
mais surtout !!!!! les temps d'accèes et de transmissions entre les bases de données et les
ordinateurs !!!!! car au vu du nombre de données!!!
les délais de transmissions pourraient générer des années !!! de temps de calculs si on néglige de
méticuleusement répartir et distribuer les données !!!!!
donc cela est très !!!!! très !!!!! primordial !!!!!
pour ne pas dire même est le centre névralgique du problème en termes de résolution en temps
humain du jeu !!!!! contrairement à ce que l'on pourrait penser !! de prime abord !!!
car les calculs des coups au jeu d'échecs se résument à des intersections de lignes d'attaques et
sont donc simplement du niveau de calcul de l'intersection de 2 droites d'un plan !! donc sont
de niveau de difficultés celles des équations linéaires de 1er degré et élémentaires donc !!!!!
et se font donc comme de simples additions de nombres pour un processeur !!!!!
Ce qui prend plus de temps processeur est d'établir le listing relationnel ordonnancé, structuré,
hiérarchique et non multivalents de toutes les positions reliées entre elles et qui peuvent
conduire à la position d'intersection d'attaque de pièces calculée qui correspond à un mat par
exemple !!!!!
et c'et là ou intervient les méthodes logiques, algébriques, combinatoires et de géométrie
algorithmique sur la gestion des structures de données !!
afin de classifer toutes les données obtenues de la meilleure manière ou des meilleures
manières possibles qui soient !!!!
le reste est question de choix stratégique ou technique ! dû par exemple au matériel dont
on dispose !!!!! et aux méthodologies de programmation appliquées !!!!! pour résoudre le
jeu d'échecs !!!!!
14 mai 2007 à 13:07
Salut VladislavIV
je vous demande sincèrement de m'excuser pour ces termes " te mélange les pédales", envers PapiVB !!
ce n'est pas bien méchant! je voulais simplement dire qu'il se méprenais sur ce que calcule et combine
l'algorithme et le programme!!!
Pour ce qui est de la raison du choix de terme astrophysique !! pour le moteur de recherche !!
il y a plusieurs raisons !!!
la première est que j'ai depuis longtemps réfléchi sur le comment ! de gestion de voyages
interstellaires par passion et par nécessité pour le devenir du genre humain!!!!!
comme on le dit habituellement sans vouloir en altérer ! toute la portée!!
haute en signification pour le non profane !
le lien avec le jeu d'échecs ! je l'ai estimé intéressant au vu des difficultés de la communauté
mondiale à le résoudre !!!!! tant du point de vue conceptuel et idéologique ! que matériel !!
il s'agit de résoudre dans le cas de la trajectologie spatiale donc en trois dimensions ! donc plus
complexe !!! au niveau trajectographie ! et possibilités d'intersections de courbes d'équations de
degrés quelconques !!!!!
un problème typique par exemple pour un ensemble de sondes spatiales !!!
qui représente la totalités des pièces sur l'échiquier !
le problème d'analyse des données locales du milieu environnant ! qui ne peuvent être obtenues
que in situ ! donc risque de perdre une sonde !
donc qui correspond au sacrifice d'une pièce dans une position donnée au jeu d'échecs !
pour avoir des données mesurées des températures , radiations, et divers champs
gravitationnels et autres dans l'espace étudié!
qui correspondent à un gain de temps ou positionnel sur l'échiquier !!!!
cela dans le but de calculer pour les autres sondes spatiales !!
en temps réel !!!
les meilleures orbites d'entrées et de sorties dans l'espace considéré après multiples cycles
autour de différents astres !!!
et qui correspond donc aux différents repositionnements stratégiques de pièces pour obtenir une
position gagnante au jeu d'échecs !
Ce n'est qu'une manière simpliste de comparer ces 2 enjeux !!!
mais c'est pour montrer le lien entre contraintes spatiales et temporelles dans une mission
complexe autonome d'un véhicule spatial tel une sonde ! et la résolution de trajectoires
multi-cycliques avec contraintes et qui est équivalente au problème à résoudre au jeu d'échecs!
et où la difficulté reste l'autonomie de la sonde qui au vu de la distance ou de l'endroit ne peut
être controllée depuis un centre de contrôle humain !!
donc reste équivalente au joueur livré à lui-même face à la résolution d'une position donnée
du jeu d'échecs!
la solution géométrique et logique pour les contraintes !!!
passe par une résolution alégbrique des relations entre les diverses possibilités combinatoires
de trajectoires les unes avec les autres !!!!
puisque les contraintes sont fluctuantes dans l'espace !!! et ne peuvent pas le plus souvent
être déterminées une fois pour toute initialement !!
donc il faut s'adapter au jeu de l'adversaire !!!
mais il faut jouer prudemment !! et logiquement!!
ausi il ne faut pas essayer de jouer une position non gagnante qui peut mener au mat en 5 coups
par exemple quand on ne connait pas les possibilités de réflexion de l'adversaire ! qui peut ! ne
pas tomber dans le piège et chercher à annuler cette position par exemple !!!
et plutôt chercher à continuer de jouer dans une position équilibrée ! ni gagnante ni perdante
ni menant au pat afin d'attendre ! l'erreur du joueur adverse !! pour chercher à faire
un mat en 1000 coups si nécessaire !!!!!
aussi ne faut il pas chercher à prendre la trajectoire la plus courte parmi certaines trajectoires
en risquant de croiser des astéroides dont on ne connait pas précisément les tajectoires dans
l'espace considéré !
et il vaut mieux ce mettre en orbite cyclique infinie le temps qu'il faudra !! par exemple !
pour déterminer précisément la trajectoire de chacun des astéroides croisant sur la trajectoire
qu'on va entreprendre plus tard !! afin de les éviter si nécessaire et arriver à établir un bilan
énergétique moyen de l'espace considéré pour les autres sondes à venir !! objectif à atteindre !
à moins qu'il n'y est d'autres raisons plus importantes comme une contrainte de temps et qu'il
y est d'autres sondes éclaireuses en réserve !!!
Bref c'est pour dire que si on sait résoudre ce type de problème au jeu d'échecs conceptuellement
et méthodologiquement de manière exacte !!!
on peut résoudre tout type de problème géométrique !!!!!
puisque on allie cyclicité, combinatoire et contrainte géométrique sur des classes d'objets
eux-mêmes combinés ! avec de surcroit une contrainte temporelle !!! alternée !!!! donc un
paramètre permettant la correction des données et des calculs à chaque étape !!!!! du
problème qui est continuellemnt fluctuant !!!!!
voilà le pourquoi de ce rapprochement des genres entre astrophysique et jeu d'échecs !!!!!
1 mai 2007 à 19:05
Reste plus qu'à espérer que ça ne se répande pas partout, ça nuirait pas mal au sérieux du site !
Maintenant, si tu crois ce que tu dis, faudrait vraiment que tu choisisses entre quelques discussions couché sur un banc avec un monsieur à lunettes, et des cours (les plus chers) de communication (écrite, hein, manquerait plus que ça qu'il parle à l'écran...).
Je crois que je vais envoyer tout ça à un ami à moi, qui maîtrise les échecs avec le petit doigt. Il a passé haut la main un Doctorat en mathématiques appliquées, il saura donc me donner une appréciation juste et scientifique de ce joyeux bazar ! Je crois qu'il va bien rigoler... ;)
1 mai 2007 à 16:37
Je suis allez relire les théories de Galois, voir ce qu'était les travaux de Shannon, relire des articles sur la théorie des échecs, relire les articles sur les combinatoires et les permutations...
Ensuite j'ai relus tes documents et tes commentaires...
Et je l'avoue, dans la brume, je crois voir un début de compréhention de ta démarche, cependant je reste convaincu que ton estimation des volumes et fausse (D'ailleurs je n'ai toujours pas compris ta démonstration qui ta permis d'arriver à ce nombre).
--- Pour ceux qui voudrais ce faire un refresh sur la théorie de Galois, je conseil ce lien sur wikipedia (hélas en Anglais)
http://en.wikipedia.org/wiki/Galois_theory
En résumé: une théorie sur les ensembles combinatoires et leur simplification. Enrichis depuis par les travaux de Richard Dedekind, Leopold Kronecker and Emil Artin (automorphisme, endomorphisme, etc... La transformation d'un objet vers lui-même... en clair dans notre cas les transformations du plateau de jeux suite à un déplacement d'une pièce. Ces théories travail sur les transformations et sur les ensembles de transformations)
--- Pour ceux qui voudrait des informations sur Shannon :
http://en.wikipedia.org/wiki/Claude_Elwood_Shannon
Voici un extrait (désolé en Anglais):
"Shannon's computer chess program
In 1950 Shannon published a groundbreaking paper on computer chess entitled Programming a Computer for Playing Chess. It describes how a machine or computer could be made to play a reasonable game of chess. His process for having the computer decide on which move to make is a minimax procedure, based on an evaluation function of a given chess position. Shannon gave a rough example of an evaluation function in which the value of the black position was subtracted from that of the white position....."
Ceci ce passai en 1950 et les travaux de Shannon était sur le bon vieux algo minimax, ainsi que sur les fonctions d'évaluation d'une position. Depuis l'algo minimax a été dépassé en efficacité par l'algo AlphaBeta, qui lui même a été optimisé avec le "sort quick evaluation node". De plus l'évaluation d'une position a été affiné depuis avec de nouveaux facteurs pris en compte (en profitant des puissances de calcul supérieure à la puissance des ordis de 1950)
C'est le papa des programmes de réflexion des jeux, il a posé les bases.
--- Un autre lien sur les volumes aux échecs (en Anglais):
http://en.wikipedia.org/wiki/Chess
Extrait:
"The number of legal positions in chess is estimated to be between 10 exposant 43 and 10 exposant 50, with a game-tree complexity of approximately 10 exposant 123. The game-tree complexity of chess was first calculated by Claude Shannon as 10 exposant 120, a number known as the Shannon number. Typically an average position has thirty to forty possible moves, but there may be as few as zero (in the case of checkmate or stalemate) or as many as 218."
(Aussi sur: http://en.wikipedia.org/wiki/Shannon_number
The game-tree complexity of chess is now evaluated at approximately 10 exposant 123 (the number of legal positions in the game of chess is estimated to be between 10 exposant 43 and 10 exposant 50). ..... As a comparison, the number of atoms in the Universe, to which it is often compared, is estimated to be between 4x10 exposant 79 and 10 exposant 81)
Donc d'après cet article: j'avais le bon ordre de grandeur sur le nombre de position de plateau (nombre de 50 Chiffres pour le maxi et une estimation que le nombre de plateaux valides est compris entre un nombre de 43 chiffres et un nombre de 50 chiffres)
De plus: Une estimation de la taille de l'arbre de jeux est un nombre de 123 chiffres (wahoo!...) et oui différents chemins mène à la même position de plateau de jeux... ce qui est plus que le nombre d'atomes dans l'univers... (wahoo!...)
J'ai du mal à imaginer.....
--- Selon moi pourquoi tes volumes sont faux
Quelque soit ta méthode il te faudra envisager les 10 puissances 47 position de jeux valide.
Dans le cas des programmes « classique » avec les méthodes minimax ou AlphaBeta on s'affronte à l'arbre de réflexion à parcourir, c'est-à-dire les 10 puissances 123 et comme on fait une recherche que sur quelque coût en avance et qu'on élague on ne parcours que quelques branches et que quelque coups en avances (si 8 coups en avance cela fait a peut prêt 10 puissance 11 feuilles, les algos actuel permette de n'en parcourir que 5%).
Dans ton cas tu travailles sur les permutations, c'est-à-dire que tu n'approches pas le problème par l'arbre de réflexion, ce qu'y t?élimine les séquences de jeux différentes qui arrive sur la même position de jeux (mais tu pars des positions de jeux et de leur transformation). Cependant tu aboutiras forcément à un ensemble de fonction de transformation global égale aux positions de jeux possible c'est-à-dire 10 puissances 47.
Au lieu de l'approche « classique » qui demande de travailler sur l'ensemble des 10 puissances 123 possibilités. Tu travailles sur l'ensemble des 10 puissances 47 possibilités de transformations du plateau de jeux (pour chaque position de jeux, il y a une séquence (non obligatoirement unique) de coup à jouer qui transforme le jeu de la position de départ à la position d'arrivé).
Bien que ton point de départ soit les transformations du plateau de jeux, et que tu souhaites les passer en revus (en les prenant de manière global), tu arriveras forcément sur les positions de plateau de jeux possible. C'est-à-dire un nombre de 47 ou 50 chiffres.
Maintenant : Ce n'est qu'un avis, et je ne souhaite pas te décourager dans ton aventure. Personnellement je ne crois pas que ton objectif soit possible (à cause des volumes mis en ?uvre), je souhaite me tromper et que tu atteindras ton objectif. Je promets de revenir régulièrement suivre l'évolution de ton projet.
Bonne chance,
1 mai 2007 à 09:53
"slt PapiVB !
je dois te dire ! que tu te mélanges les pédales!!!"
Sans vouloir paraître désagréable, entre ton reverse engineering qui n'a rien à faire ici et ta "sortie de boucles circulaires infinies", je me demande qui c'est qui se mélange les pédales...
Quand on sait que les machines spécialisées (type Deep Blue) ne calculent pas la totalité des positions car c'est impossible, aussi bien au niveau temps qu'au niveau mémoire, alors qu'elles ont été conçues et programmées par des personnes plus que compétentes, je rigole un peu face à ta prétention. Surtout avec seulement un ordinateur grand public, 762 lignes de code et un discours d'allure très "savante!!!!!!!!!!" mais qui ne veut pas dire grand-chose.
Au fait, faudrait aussi expliquer ce que l'astrophysique a à voir là-dedans (catégorie de la source)...
27 avril 2007 à 18:14
Tous ces "!!!!!" c'est affreux ça empèche de lire !
On est déjà crevé au bout de 5 lignes ...
Le texte peut etre intéressant, si tu pouvais mettre un peu moins d'exclamation dans tes écrits on te lirait plus facilement :( ...
Sinon j'avoue là on a qqchose de compliqué :D
26 avril 2007 à 11:40
j'ai mis un autre source explicatif !!! et entièrement détaillé !!!!! sur le pourquoi et le comment de l'algorithme !!! ainsi que d'autres add-ons!!!
sous la catégorie Maths& Algorithmes avec mots clés Algorithme,Combinatoire,Calculfactoriel,Algèbredesgroupes,Jeud'échecs ; niveau de la source: Débutant !
donc à lire absolument !!!!! pour mieux comprendre !! le programme
qui se rapporte à cet algorithme!!
je tiens toutefois à préciser que je n'ai pas depuis lors vérifier explicitement et en profondeur !!! qu'il n'y a pas trop d'erreurs dans l'explication textuelle de l'algorithme par rapport aux valeurs numériques de l'algorithme !!!
donc être relativement prudent !! et prendre bien soin de vérifier globalement puis méticuleusement si nécessaire !! pour éviter de reprendre des erreurs de frappe ou des fautes sur les pièces mises en jeu à chaque étape !!!
a+
didkac
25 avril 2007 à 23:02
25 avril 2007 à 22:13
merci
25 avril 2007 à 17:36
J'ai pourtant lu et relu l'introduction, mais je n'arrive pas à comprendre, et ce que je crois comprendre en faite je ne l'ai pas compris... J'ai pas le niveau... trops fort pour moi...
Si tu écris un livre vas falloir que tu commence à un niveau plus bas, sinon tu vas perdre du monde dés le démarage...
Comme je suis curieux, je vais chercher à comprendre tes réponces, je vais faire des recherches sur google pour me remettre à niveau... entre autre sur les théorie de Galois et les traveaux de Shannon?!? et plein d'autre choses qui me disent plus rien ou ne m'ont jamais rien dis....
Je pense que je ne peux rien t'apporter sur le sujet... je vais donc suivre la dicution et faire des recherches sur les termes utilisés pour tenté de comprendre la démarche... A la longue je comprendrais... peut-être...
J'ai une expérience en algorithme de recherche de solution type jeux de réflexion, mais là... trops fort... trops novateurs... je suis largué...
Si d'autre on compris je suis preneur d'une explication "pour les nuls"...
25 avril 2007 à 15:26
25 avril 2007 à 15:20
je dois te dire ! que tu te mélanges les pédales!!!
l'algorithme est valable sur un échiquier quelquesoit le nombre de cases !!!! qu'il contient !!
l'algorithme n'en tient pas explicitement compte!!
c'est comme la théorie de Galois sur les équations polynômiales à coeeficients quelconques et nombre quelconques de variables et de dégré quelconque !!!
il donne la résolution complète du problème par la méthode de regroupement algébrique !!! sans tenir compte des individualités!!
il n'a évidemment pas pris la peine même d'envisagere les combinaisons une à une à des degrés divers mais à comprendre les relations entre les différents groupes d'ensemble qui interviennent dans la résolution d'une équation polynomiale!!!
donc les inter-relations entre groupes dans la théorie des ensembles !!! relativement là aux variables - fonctions - coefficients - puissances donc facteurs multiplicatifs des fonctions et c'est rendu compte qu'on pouvait généraliser !!! la méthode par regroupement selon les théories de la combinatoire que l'on connait sur la combinaison des éléments d'un groupe !!! en tenant compte des symétries des plus importantes au moins utiles entre fonctions coefficients et variables !!!!
c'est totalement différent ici! ce n'est pas le même sujet !!
évidemment !!!
si ce n'est!!!!! qu'il y a également ici des possibilités de combinatoires cycliques!!! dont on peut tenir compte avec la théorie de Galois!!!
mais je te prierais d'éviter d'extrapoler des calculs sur des positionnements complexes des pièces sur un échiquier sans mettre des formules de combinatoire qui déterminent les pièces en conflits et donc qui vont permuter entre elles!! et le nombre de combinaisons possibles des chemins durant lesquels ces pièces peuvent se repositionner !!!
c'est tout autre chose !!!!! et j'en traitrais dans mon second algorithme sur lequel je suis en train de bosser pour calculer toutes les positions au jeu d'échecs !! sans les résoudrent entre elles!!! dans cette seconde étape!!!
puis avec la base de donée générée !!!!! je ferais un troisième algorithme plus poussé et un programme nettement plus complexe pour résoudre totalement le jeu !!!
avec des techniques :
de reverse engineering !!!
de symétrisations !!!
de sorties de boucles finies dans des boucles circulaires infinies
et inversément de sortie de boucles infinies combinées à des boucles finies concomitamment il va de soi !!!!! puisque c'est une des possibilités permise au jeu d'échecs !!!!!
du calcul à intelligence artificielle pour les calculs statistiques-stochasstique et heuristiques liés aux fréquences les plus pertinentes de combinaisons de pièces menant au gain !! si cela permet !! de manière corrélatives !! de résoudre plus rapidement les postions !?
mais là il s'agit du cours du jeu !!!
il serait bon que tu prennes le temps de lire !!!!! et relire !!!!! mon introduction dans le source !!!!! et!!! je pense que tu comprendras mieux le pourquoi des choses !!! en espérant que tu n'erres pas comme certains !! sur des spéculations non fondées !!!!! tels le calcul du nombre de Shannon !
que j'ai très bien expliciter dans la mesure du possible !! au vu du peu de donnée que j'ai sur les travaux de Shannon sur le sujet !!!!!
mais je ne t'en tient pas rigueur !!!
c'est une simple incompréhension quelque peu généralisée des divers aspects et possibilités d'aspects spécifiques !!! des divers compartiments du jeu d'échecs !!!!!
et je me propose justement d'écrire un bouquin dessus!!! dès que j'en aurais le temps!! et la possibilité!! j'y réfléchis et y travailles dessus dans tous les cas !!!!!
cet algorithme est comme je l'ai expliqué dans ma présentation de l'algo statique !!!!! cela veut dire plusieurs choses!! dont notamment qu'il procède step by step !!!
cela veut dire qu'il n'est pas itératif comme par exemple on fait plusieurs coups en même temps au jeu de dames!!!
cela tient évidemment du fait que aux échecs on joue de manière statique !!! step by step !
soit 1/2coup après 1/2coup pour chaque camp!!!!!
pour jouer sur plusieurs coups à la fois !!! il suffit d'additionner les lignes d'algorithmes respectifs!!! que l'on veut utiliser et vérifier que les valeurs obtenues sont cohérentes avec la validité de nombre et présence des pièces sur un échiquier normal !!!
25 avril 2007 à 14:56
De plus lors d'une étude d'une position en dynamique (sans mémorisation) grace à des algothytmes du type AlphaBeta avec ordonnancement des noeuds (un des élagages le plus efficace des branches à ne pas étudier) et des machines musclés, l'étude sur un coup quelquonque vas à plus de 15 coûts en avances, mais pas en partie Blitz ;-).
Pour ma part j'ai programmer un Abalone qui as une largeur de cout possible plus large que les échecs (énormément plus de combinaison possible), avec un algorhitme du type AlphaBeta Ordonnancé avec "quick Evaluation", J'arrive en une quinzaine de minutes sur un pentium II à étudier 10 coups en avances.
Grâce à l'alghorhitme, avec 10 niveau en avance, j'arrive à ne pas étudier plus de 99,9% des feuilles et plus de 87% des noeuds. (évidement avec 10 coups en avances la réponce peut arrivé en 5 heures ou plus, si le "Quick Evaluation" ne donne pas des résultats proches de l'Evaluation, comme par exemple sur certaines positions viciueuses de multiples sacrifices pour un gain "relatif" à 10 coup. Les réponces que j'optien à 10 coups sont à 90% antre 10min et 30min, 9% en dessous de 2h et des exceptions à 5h ou plus.... Mais cela est un autre débat sur l'agorithme AlphaBeta ordonnancé avec Quick Evaluation......)
J'ai fait une version avec mémorisation des ouvertures, mais pour qu'une bibliothéque soit efficace il faut un grand nombre de coup stocké et une grande rapidité d'accés, hors je n'ais pas des configuration mémoires de plusieur Giga pour ne faire que des accés mémoires, ce qui fait que je vais plus vite à évaluer un coup que passé mon temps à vérifier son existance dans une DB.
Et dans le cas d'Abalone avec de bon critére d'évaluations d'une position, on as le même 10 premières réponces pour une profondeur d'étude de 2 niveaux que pour 8 niveaux..... Alors j'ai fais une version plus lentes et pas meillieur :-(, cela m'as amusé pour l'excercise... NB: évidement pour les couts suivant c'est une autre histoire et plus on analyze en profondeur meillieur et le programme ;-)
Mais le but de mon poste n'était que montrer une potentiel erreur d'évaluation des volumes du projet...
25 avril 2007 à 14:48
je te conseilles de commencer à lire l'introduction !!! mais bien la lire !!! et puis je t'expliquerais plus amplement l'algorithme!!! par contre pour que tu le comprennes mieux!! je vais demain ajouter le fichier texte de l'algorithme et l'explication de son fonctionnement !!! c'est simplement la méthode de groupe de transformation générant les diverses prises possibles au jeu d'échecs que j'ai réunies et qui font tout bonnement 762 lignes d'algos!! je ne l'ai évidemment sû précisément qu'après avoir posé les calculs !!! mais un calcul simple de combinaison Cnp entre couleurs 2 pièces 14 couleurs de cases de promotions 2 pour les pions et de déplacements 2 pour les fous permet d'estimer pour ceux qui savent faire la combinatoire de sous-ensembles en intersection !!! une approximation du résultat de 762 lignes d'algos!!!
25 avril 2007 à 14:39
je tiens à laisser le texte d'explication dans le source pour plusieurs raisons !!! je vais mettre à jour plusieurs fois ce source !!!
et de plus je vais l'utiliser à des fins didactiques !!! donc tout réuni en 1 seul fichier est plus simple à gérer et plus facile à maintenir!!
par contre j'ajouterais un zip de fichier texte pour expliquer et donner toutes les lignes de l'algorithme seul! à part !
afin que la compréhension de la méthodologie qui sous-tend les calculs soit bien assimilée! et éviter le fastidieux !! travail de réflexion sur les groupes de combinaisons de prises, de pièces majeures ou de pions, avec les possibilités de promotions qui en découlent !!!!!
25 avril 2007 à 13:37
25 avril 2007 à 13:28
Le nombre de possibilité de placer les 32 pièces sur un plateau de 64 cases est 64x63x62x61x60..x34x33 C'est à dire un nombre de 54 chiffres. Si on admet que les pionts on la même valeur, les tours d'une couleur entre elles, les cavaliers entre eux, il faut divisé les possibilité par 16 soit un nombre constitué de 53 chiffres. De plus il faut ajouter les combinaisons avec une piece prise (sauf les rois biensûre) donc + 30x64x63x62..x34 nombre de 53 chiffres, + les combinaisons ou il manque 2 piéces donc + 29x64x63x..x35 nombre de 52 chiffres, etc... etc...
Le tout donne un nombre d'environ 54 chiffres, même si on supprime quelques combinaison qui ne peuvent pas intervenir en cours de partie divison de maniére arbitraire par 100'000, il reste quand même un nombre de 49 chiffres...
Si on admet seulement 10octets pour stocker une position, cela done un nombre de 50 Chiffres d'octets que pour les data, en plus il faudra prévoir des index... ce qui fera des Tera de Tera de Tera de Tera de Tera d'octet... Pas sure qu'il y est la place de tout stocker dans la production mondial de disque dure...
Si on admet 1seconde de CPU par position du plateau, dans 1 année il y as un nombre de 9 chiffres de secondes, il faudra donc un nombre de 41 chiffres d'années, soit un nombre de 39 chiffres de siecles.... si un jour tu peux analyser 1'000 positions en 1s (avec les access DB!!! Wahou... c'est pas demain) il te faudra encore un nombre de 36 chiffres de siécles....
Voici un nombre de 49 chiffres qui corespond plus ou moins à l'ordre de grandeur des combinaisons:
10'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000
Voici ton estimation:
337'590'4869'000'000
Il me semble qu'il en manque beaucoup dans ton estimation... C'est pour cela que des algorhytmes de "reflexion" on été développé, comme le miniMax, L'AlphaBeta, ... etc... avec des systémes plus ou moins évolués d'estimation d'un plateau de jeux par une note de pondération d'attente de l'objectifs....
NB: Les programmes d'échec d'aujourd'hui qui mémorise des ouvertures classic ont juste une bibliothéque de coût sur les 2 ou 3 premiers déplacements (en prés calculé) et ne contiennent pas les coût considéré comme pas terrible par le systeme classic d'évaluation d'une position de jeux.
Bon peut-être je me trompe... et je vais revoir mes cours de combinatoires....
25 avril 2007 à 12:57
ton code parcours tout l'arbre des configurations de partie possibles à partir d'une configuration de départ ??
25 avril 2007 à 12:30
le code est un algorithme statique composé de 762 lignes de codes qui sont reprises quatre fois entre elles d'où les 1 + 762 + 762*762+ 762*762*762 + 762*762*762*762 ~= 337,5904869 possibilités !!!!!
puisqu'il n'y a que 4 pions ! sur cases blanches ou noires au jeu d'échecs pour chaque camp !
et permet de générer les tableaux principaux, à partir d'une position initiale donnée, successifs à une prise de pièce ou de pion !!!!! avec changement de colonne ou non et promotions éventuelles! voici succinctement dit !! ce qu'il génère !!!!!
sous la forme d'une suite numérique alignable comme bon semblera !! par exemple suivant l'ordonnancement que j'ai adopté:
pbb pbn pnb pnn tb tn cb cn fbb fbn fnb fnn db dn
les rb et rn, les rois blanc et noir sont omis naturellement car toujours présents sur l'échiquier !! sauf en cas de mat !!
symboles abrégés qui signifient: pion blanc sur case de promotion blanche , fou noir sur case de déplacement noire, etc...
exempli gratia de la forme:
001 002 003 004 005 006 007 008 009 008 007 006 005 004
qui sont les nombres respectifs de pièces sur l'échiquier et formant les tableaux principaux !!!!!
25 avril 2007 à 02:00
les 450 dernieres sont selon moi incomprehensibles... il est deux heures, j'ai survolle les 50 premieres :)
ca a l'air interessant
24 avril 2007 à 23:24
24 avril 2007 à 20:43