|
| Pour matheux et informaticiens... par JR***nb****12063 le
[Aller à la fin] |
| Problèmes | |
Un petit probleme de denombrement qui me tracasse depuis longtemps :
Quel est le potentiel moyen par coup, sur echiquier vide, pour un Cavalier ?
pour preciser l'idee et le vocabulaire, prenons une Tour sur echiquier vide, elle peut jouer sur 14 cases, partout ou on la place elle peut jouer sur 14 cases, son potientiel moyen par coup, sur 1 coup est de 14 (soit 14x64/64)
sur 2 coups il est aussi de 14, (racine carree[14x14])x64/64 etc pour n coup avec la racine n-ieme de 14 puissance n.
par analogie, definissons le potentiel moyen par coup pour le Cavalier sur n coups : (racine n-ieme[somme de tous les parcours possibles du Cavalier sur n coups a partir d'une case quelconque]/64)
Le resultat (un peu etonnant) que j'intuite est que pour n croissant la moyenne ainsi calculee oscille en convergeant vers une limite.
le probleme apres peut se compliquer en envisageant des echiquiers non vides.
meme probleme pour les Rois, Fous, et Dames
etc.
|
|
|
J'avoue que je ne me suis jamais posé ce genre de question existentielle. Je joue aux échecs, c'est déjà pas mal ...
|
|
|
impressionnant en effet! apres l'autre qui parle d'échange entre matiere et énergie a travers le sacrifice (référence a un post récent), voila que le cavalier a un potentiel moyen de n coup par rapport a la racine carré de l'échiquier!!
J 'en apprends aussi tous les jours sur FE!lol!
|
|
|
je vois à peu près la notion de potentiel moyen sur un coup, mais pas du tout ce qu'est un potentiel sur plusieurs coups. Par analogie avec la définition j'aurais eu tendance à dire que le potentiel sur deux coups d'une tour est de 64 cases puisqu'elle peut aller n'importe où y compris revenir au point de départ. Manifestement ce n'est pas ça mais alors qu'est-ce ?
|
|
|
@El cave Le nombre de chemins longs de 2 coups que peut parcourir une tour sur un echiquier vide, a partir d'une case donnee est de 14x14 puisque sur sur chaque case qu'elle atteind au premier coup, elle peut a nouveau jouer 14 coups.
|
|
|
Intéressant En tout cas si tu arrives à démontrer que ton potentiel moyen est croissant, comme il est majoré (par 8) tu sais déja qu'il converge.
Mais comme tu as utilisé le mot oscille, peut être ne l'est il pas(croissant).
|
|
|
ne devenez pas fou! Jouez les ECHECS naturellement et simplement!.
Apprenez déjà à jouer une combinaison dans une partie aulieu de chercher le potentiel carré et la probabilité qu'un cavalier va se poser le cul sur l'une ou l'autre case.
|
|
|
Oui; mais si léchiquier n'est pas vide, le potentiel moyen sur le coup convergera t il egalement?
|
|
|
je sais résoudre Je sais résoudre ce problème numériquement (analytiquement j'ai la flemme).
Ca peut se modéliser par de l'algèbre linéaire.
|
|
|
Je supposerai sans plus tarder Que ta limite est peu ou prou égale au potentiel moyen sur 1 coup. Sur un échiquier vide, bien entendu.
À partir du moment où toutes les cases atteignables par une pièce le sont effectivement (au bout d'au plus 2 coups pour une T ou une D, 3 coups pour un F, plus pour le C, 7 coups pour le R), après on construit les chemins récursivement.
Ensuite, la formule qui donne la moyenne est pourrie : j'avais fait ce genre de calculs immondes en prépa (moyennes de racines n-ièmes contre racines n-ièmes de moyennes, Cauchy-Schwarz et Minkowski, etc...), je vais pas réessayer.
En plus, comme je pressens que la symétrie de l'échiquier vide me favorise, je pose donc fièrement :
- Tour : 14 (facile à démontrer)
- Fou : 8,75
- Dame : 22,75
- Cavalier : 5,25
- Roi : 6,5625
J'appuie mon raisonnement absolument pas rigoureux
sur le fait que, vu qu'au bout d'au plus 7 coups, chaque pièce atteint toutes les cases accessibles par elle, et qu'elle peut ensuite indéfiniment faire des aller-retours, ce qui induit forcément une égalisation, une dilution entre les différents potentiels des diverses cases de départ. De plus, la formule avec sa racine n-ième, tend à "écraser" les contributions initiales.
Pour avoir l'absolue certitude de ce que j'avance, il faudrait faire une simulation numérique. Car j'ai aussi le pressentiment qu'une démonstration manuelle est impossible...
|
|
|
ref JRotenberg Regarde le sujet suivant :
http://france-echecs.com/index.php?mode=showComment&art=20040528114603274
|
|
|
d'accord pour un coup ça ne doit pas être trop compliqué à dénombrer, 8 possibilités pour chacune des 16 cases centrales, 6 pour les cases de deuxième travée non situées dans les grandes diagonales (4 cases) , 4 pour les cases de 2ème travée des diagonales et pour les cases de première travée située dans les quatre travées centrales dans l'autre dimension, soient 32 cases en tout, 3 pour les cases de première travée voisines des coins (8 cases) et 2 pour les coins.
Si j'ai bien compté, 8x16 + 6x4 + 4x32 + 3x8 + 2x4 donc 312 mouvements, ce qui représente un peu moins de 5 par case.
A partir du second coup c'est plus délicat en effet, peut-être faut-il définir des zones de départ et leur associer une "espérance de déplacement" suivant la zone des cases d'arrivée du premier mouvement ?
|
|
|
Oulala, j'ai besoin d'un sérieux rattrapage en maths En résummé, je crée pour chaque pièce une matrice M de 64x64, où l'élément (i,j) contient 1 si la pièce peut aller de la case i à la case j (la numérotation des cases pouvant être arbitraire, par exemple a1=12 et c2=25), et 0 sinon. M est symétrique et contient vraiment beaucoup de 0, donc est diagonalisable ? ;-)
Ensuite, ce que propose Rotenberg, ca revient peu ou prou à calculer M à la puissance n, de sommer tous les éléments, d'en prendre la racine n-ième et de diviser par 64. Bref, il s'agit d'une norme, et on doit démontrer que la norme pour n converge vers une limite qui doit être égale à la norme 0... ;-)
Bon, bref, la prépa c'est loin. Heureusement que mon prof est pas dans le coin ! :-)
|
|
|
ref elcave tu as mal compté, ya 336 mouvements de caval soit 5.25 par case en moyenne.
|
|
|
pour revenir à la question voici les 5 premières valeurs pour un cavalier
336 2008 12000 72288 433872
c'est-à-dire le nombre de parcours en 1,2,3,4,5 coups en sommant ce qui se passe avec les 64 cases possibles de départ.
La limite du quotient de deux termes consécutifs de la suite tend vers 6.0107.
|
|
|
j'ajoute que la division par 64 proposée me semble inutile, car la racine neme de 64 tend vers 1 quand n augmente.
|
|
|
dan31 Le fil auquel tu nous renvoies ne contient pas la réponse au problème posé. L'as-tu?
|
|
|
D'ailleurs tu as écrit :
"(racine n-ieme[somme de tous les parcours possibles du Cavalier sur n coups a partir d'une case quelconque]/64)"
mais peut-être voulais tu dire :
(somme sur 64 cases[toutes racine n-ieme du nb de parcours possibles du Cavalier sur n coups a partir d'une case donnée]/64), ce qui serait plus logique vu la division par 64.
|
|
|
toujours pareil je l'ai numériquement mais pas analytiquement. J'avais cherché un peu et j'ai laissé tomber. Faut demander à anselan (si jamais il a une soluce).
|
|
|
Calcul rapide Sur n->infini, la limite tend vers un nombre très proche de 8, me semble-t-il.
Premièrement, il faut calculer le nombre possible de coups par case pour un cavalier (s'il est dans un coin, il ne pourra se déplacer que de 2 cases par exemple.
A l'aveugle (reprenez-moi si je me trompe), je dirais que le nombre possible de coups par case pour un cavalier est de :
carré a1-h8 : 4*2 + 8*3 + 16*4
carré b2-g7 : 4*4 + 16*6
le reste : 16*8
Si la présence du cavalier sur chaque case était équiprobable, nous obtiendrions le potentiel suivant : 336 / 64 = 5.25
Malheureusement, elle n'est pas équiprobable. Par exemple, seuls 8 cases permettent au cavalier de se retrouver dans un coin (et d'avoir un nombre possible de coups égal à 2). Naïvement, nous pourrions ainsi calculer le potentiel (en élevant tout au carré): 30592 / 64^2 = 7.46875
Cepndant, dans l'exemple précédent, les 8 cases permettant d'accèder aux coins sont également soumis aux probabilité. Il est moins probable que le cavalier se retrouve sur ces 8 cases que sur les cases du milieu, où son nombre possible de coups est alors au maximum. Le poids des cases du coin s'en trouve donc encore réduit, et puisque tel est le cas, le poids des 8 cases permettant d'y accéder est aussi réduit, les probabilités de ces cases s'influençant mutuellement (par exemple). Nous devons donc calculer une limite de probabilité de présence du cavalier pour chaque case (assez long), mais il doit y avoir des outils mathématiques permettant de réaliser ces calculs plus rapidement.
|
|
|
ref nil tu as l'explication plus haut : il suffit d'élever une matrice (64x64) à la puissance n pour avoir la réponse. On numérote les cases de 1 à 64. La matrice contient uniquement des zeros et des uns : elle a zeros dans la case A(i,j) si on ne peut aller de i à j et un si on peut aller de i à j. Alors A élevée à la puissance n donne en ligne i et colonne j le nombre de parcours pour aller de i à j en n coups exactement.
De cette manière, on peut calculer de manière très simple qu'il y a exactement 5781124 façons d'aller de g1 à f7 en exactement 11 coups (véridique).
|
|
|
sinon je confirme que la limite recherchée est très proche de 6 (entre 6 et 6.02) c'est-à-dire plus que ce qui se passe en 1 coup (5.25) car les parcours passent peu dans les coins, mais tout de même largement moins que 8 (ya quand même que 16 cases qui donnent 8 possibilités et ensuite on passe direct à 6 possibilités).
|
|
|
@dan31 Peut tu regarder si le potentiel moyen est croissant sur ta simulation? Merci d'avance
|
|
|
ref dan 31 Citation :
De cette manière, on peut calculer de manière très simple qu'il y a exactement 5781124 façons d'aller de g1 à f7 en exactement 11 coups (véridique).
br>
Je parle de calculer les limites des probabilités de présence du cavalier sur chaque case et non les probabilités pour un n donné.
"car les parcours passent peu dans les coins, mais tout de même largement moins que 8 (ya quand même que 16 cases qui donnent 8 possibilités et ensuite on passe direct à 6 possibilités)."
Ces 16 cases sont soumises aux probabilités que j'explique plus haut. Il y a plus de chances que le cavalier se retrouve sur ces 16 cases donnant 8 possibilités que sur les autres, et ce poids augmentent au fur et à mesure que n croit.
|
|
|
@dan31 Merci pour la correction:
(somme sur 64 cases[toutes racine n-ieme du nb de parcours possibles du Cavalier sur n coups a partir d'une case donnée])/64
sonne plus juste
|
|
|
un petit programme informatique qui fait le calcul concretement doit faire l'affaire
pour les petites valeurs de n
|
|
|
valeur propre maximale de la matrice de transition blaylock est sur le bon chemin avec sa matrice de transition 64x64. Il calcule correctement le "potentiel moyen sur 1 coup", qui correspond à la somme des éléments de cette matrice divisée par 64:
C: 5.250000000
F: 8.750000000
T: 14.000000000
D: 22.750000000
R: 6.562500000
Pour la limite, ça revient à demander la plus grande valeur propre de cette matrice. Pour une matrice plus grosse il faudrait procéder par simulation, mais 64x64 peut être traité directement. Voici les résultats, calculés à 20 décimales par Mathematica:
C: 6.0106605830393516865
F: 9.1612747819625292762
T: 14.000000000000000000
D: 22.936022136221168960
R: 7.2908593693815896066
|
|
|
ce qui donne ? pour n=2 ?
n=3 ?
n=4 ?
|
|
|
pour une fois Je suis d'accord avec caalforever!
|
|
|
et le pion si l'on présuppose qu'il a une probabilité equiprobable de se promouvoir en C, en F, en T ou en D? Ca donne la moyenne des 4 valeurs pour T F C et D? :)
|
|
|
n=1..10,20,30,40,50 Pour n > 1 il y a plusieurs définitions possibles (qui tendent toutes vers la même limite). Ma définition préférée est l'originale mais avec le "/64" à l'intérieur de la racine, ce qui permet d'exprimer les réponses sous la forme (entier/64)^(1/n). Pour le cavalier ça donne, pour n=1..10,20,30,40,50:
(336/64)^(1/1) = 5.25
(2008/64)^(1/2) = 5.60133913
(12000/64)^(1/3) = 5.72357121
(72288/64)^(1/4) = 5.79724372
(433872/64)^(1/5) = 5.83762684
(2609968/64)^(1/6) = 5.86690697
(15680080/64)^(1/7) = 5.88682582
(94273872/64)^(1/8) = 5.90236988
(566555408/64)^(1/9) = 5.91419751
(3405696976/64)^(1/10) = 5.92383022
(209610366527189008/64)^(1/20) = 5.96707696
(12901337314739237099415248/64)^(1/30) = 5.98156957
(794066316639745037256542497276560/64)^(1/40) = 5.9888291
(48874105088508956622153299408584747851856/64)^(1/50) = 5.99318904
|
|
|
Pas d'oscillation Jacques va être déçu, d'après les calculs de François, il n'y a apparament pas d'oscillation pour le cavalier : la suite croit en convergeant.
|
|
|
exact, je suis decu mais je ne renonce pas encore tout a fait
La formule la plus "naturelle" reste la moyenne des racines n-iemes
|
|
|
Félicitation pour cette résolution rapide Cela a vraiment été rapide en mode coopératif 1/2 journée pour résoudre un problème pas évident.
Pour revenir à un sujet plus purement échiquéen, il me semblerait intéressant de rapprocher le potentiel moyen d'une pièce (fort justement calculé par Flab) a la valeur que l'on donne traditionnelement à ce pièces.
soit :
C, F = 3
T = 5
D = 10
R = ?
Comment expliquez vous que le potentiel moyen du fou = 9 est autant supérieur à celui du cavalier = 6 ?
Peut être est ce lié à la capacité du cavalier de sauter au dessus des obstacles ce que ne peut faire le F. Dans ce cas il faudrait calculer le potentiel du fou comparé à celui du cavalier dans une partie , avec tous les obstacles qui jonchent l'échiquier?
Plus la partie avance plus le différentiel entre le potentiel du fou et celui du cavalier augmente (au fur et à mesure que les obstacles disparaissent). par ex au 1er coup le potentiel du fou est de 0 alors que celui du cavalier est de 2..
Le résultat pour le roi est peut être aussi à analyser pour en tirer un enseignement...
|
|
|
Bravo Flab
|
|
|
tu m'obliges a reflechir. Ca n'arrive pas si souvent, et ce n'est pas si agreable qu'on dit
Si j'ai bien compris, tu as un outil puissant qui te permet de faire des produits de matrices deja d'une belle taille.
Premiere question, ou peut acheter ca ?
Deuxieme question, l'idee de l'oscillation, vient de ce que les cases centrales se "decharchent" sur la peripherie, et vice versa, hors la situation initiale etant desequilibree, la question se pose. (Je reconnais que ma formulation est un peu elliptique, mais j'essaye d'etre bref).
Si tu fais la manip suivante : tu place sur chaque case autant de Cavaliers qu'il y a de coups jouables (8 sur c3, d4, 6 sur c2 etc., 2 sur a1) a chaque coup chaque case se vide de ses Cavaliers, un dans chaque sortie, et se remplie de ceux que lui donnent ses voisines.
La tranformation est stable (a chaque Cavalier sortant correspond un entrant), et dans une telle situation, le potentiel tel que defini reste stable quelque soit n
|
|
|
"dechargent" et "or" la fatigue ? la deprime ?
|
|
|
du fait qu'on compte un Cavalier par case, on sur-represente les bords et les angles, et ou sous-represente le centre (par rapport a la situation stable decrite plus haut). Ce dont rend bien compte le calcul. J'avais dans l'idee que les bords se dechargeant plutot au centre, il etait bien possible de retrouver ce desequilibre en sens inverse.
|
|
|
@meteore : entre le cavalier et le fou il y a une différence qualitative : si la portée du fou est supérieure, il n'accède potentiellement qu'à la moitié de l'échiquier, ce qui compense plus ou moins cette supériorité de principe. D'où l'intérêt de la paire de fous qui remédie à cet inconvénient également, et la supériorité du cavalier dans les positions bloquées où le potentiel de déplacement supérieur du fou ne peut s'exprimer faute de place.
|
|
|
@JRotenberg Quand j'étais étudiant, j'ai effectivement utilisé des outils comme Mathematica et Matlab/Simulink, qui sont des programmes commerciaux spécialisés et assez chers.
Une licence Mathematica standard coûte environ 2600 Euros (cf http://www.ritme.com/fr/tarifs/mathematiques.html), Matlab coûte 1900 dollars (sans modules additionnels).
Je crois que le prix est extrêmement dissuasif pour un amateur. Surtout que, pour bien utiliser ces logiciels, il faut consacrer du temps à bien comprendre la documentation, ou suivre une formation (qui coûte aussi €€€...).
Il y a cependant des outils libres et gratuits, par exemple GNU Octave, un clone de Matlab/Simulink : http://www.gnu.org/software/octave/ ; ou bien Maxima (qui essaie de faire un peu comme Mathematica) : http://maxima.sourceforge.net/
Pour un usage à la maison par un non-spécialiste, ces 2 logiciels devraient largement suffire. Bon amusement !
|
|
|
Pour la supériorité du Fou sur le Cavalier en Finale (9 contre 6) Elle est assez logique si on considère qu'il y a des cibles à atteindre des 2 côtés de l'échiquier. Le Fou peut alors contrôler les 2 ailes. Le Cavalier, lui, est trop lent.
En revance, si nous nous limitons à un demi-échiquier (soit une matrice de 32x32 au lieu de 64x64), on a :
* Cavalier : 4
* Fou : 4,75
Le Fou perd alors clairement de son avantage (+18,75% contre +66,67% sur 64 cases), et est bien handicapé sur le long terme, puisqu'il ne contrôle qu'une couleur...
|
|
|
une autre manip on dessine un echiquier special : une case centale, et les huit sorties du cavalier,
exemple : d4 et b3, c2, e2, f3, f5, e6, c6, b5
le potentiel moyen sur 1 coup est de (8+8)/9, sur 2 coups (tel que defini par dan31) il est 9 fois (racine carree de 8)/9 soit, 2 racine de 2.
Pour 3 coups il est de 8 fois racine cubique de 8 plus 1 fois racine cubique de 64 le tout divise par 9, soit 8 fois 2 plus 1 fois 4 soit 20 divise par 9.
on resume 1 coup donne un potentiel moyen par coup egal a presque 2, sur 2 coups on trouve presque 3, et sur 3 coups, un peu plus que, la voila l'oscillation !!
|
|
|
sur 3 coups un peu plus que 2 ! (ah, mais!)
|
|
|
merci bcp blaylock pour "...Il y a cependant des outils libres et gratuits, par exemple GNU Octave, un clone de Matlab/Simulink : http://www.gnu.org/software/octave/ ; ou bien Maxima (qui essaie de faire un peu comme Mathematica) : http://maxima.sourceforge.net/..."
|
|
|
Encore faut-il bien interpréter les résultats de ces outils sinon l'on risque de croire en regardant ces résultat, que, par exemple, la limite de potentiel d'un cavalier est égale à 6. C'est pourquoi une bonne analyse est un complément indispensable à ces outils.+inf) = +inf.
Cela dit, dans la pratique, connaître les limites à +inf du potentiel du cavalier n'est guère primordiale, j'en conviens.
|
|
|
(une partie de mon texte a été mangée) Je disais (depuis le début d'ailleurs) que le poids des cases centrales (où le potentiel du cavalier est au maximum) augmente par rapport à celui de toutes les autres, lorsque n croit. Cette augmentation est, certes, logarithmique, mais souvenons-nous que ln (x->+inf) = +inf.
|
|
|
Il faut réfléchir un peu plus, JRotenberg :) Pour la configuration stable, c'est donné par le vecteur propre correspondant à la valeur propre maximale. Pour le cavalier ça donne les poids suivants (mesurés par rapport à a1).
a1: 1.0000000000000000000
b1: 1.5682690265528684037
c1: 2.0567129142321231913
d1: 2.2849006758641213505
b2: 2.2419025028353121610
c2: 3.0053302915196758433
d2: 3.3358470995898552081
c3: 4.0337728076808421113
d3: 4.4527568265406182451
d4: 4.9338028060247615805
Les autres cases se déduisent par symétrie. Ces nombres ont la propriété que si on additionne les poids des cases connectées à une case particulière, on obtient 6.0106605830393516865(=lambda) fois le poids de la case particulière. Par exemple, pour les cases connectées à a1: p(c2)+p(b3) = 2*p(c2) = lambda*p(a1).
|
|
|
@flab Ne penses tu pas que le poids que tu donnes montrent qu'il ne faut pas calculer comme tu le fais, mais plutot comme l'a indique dan31 ?
|
|
|
@flab qu'as tu a redire aux deux manips que je propose ?
|
|
|
ref JR Je pense que flab a fait la même chose que moi, d'ailleurs les résultats coincident pour n= 1 ,...5.
En ce qui concerne l'histoire de plus grande valeur propre, je suis aussi convaincu de ce qu'il avance (d'autant qu'on converge vers la même chose, cad 6,01), mais n'y a-t-il pas des conditions sur l'unicité de cette valeur propre ou de la dimension de sous espace associé ? (la flemme de fouiller).
Enfin, ne pas oublier le plus important, ce potentiel moyen est un outil intéressant, mais son utilité pratique reste limitée (à part en finale avec très peu de pièces et pions), puisqu'il se calcule pour n infini. Cependant, il est amusant de constater qu'un roi est un peu plus fort qu'un cavalier, ce qui corroboré ce que disait je ne sais quel auteur à savoir qu'un roi valait une pièce mineure en finale (dans le sens a la même activité). Enfin, on note qu'il a déjà été dit que le fou est plus fort que le cavalier en finale en général, mais qu'on peut considérer que c'est le contraire quand l'échiquier est encore rempli (ce qui justifie beaucoup d'échanges de fou contre un cavalier au début de la partie).
|
|
|
@JRotenberg Pour la première manip, je voulais dire qu'elle n'était pas stable. Ce que tu as décrit est la distribution après 1 coup, mais la distribution continue d'évoluer.
distribution de départ:
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1
distribution après 1 coup:
2, 3, 4, 4, 4, 4, 3, 2,
3, 4, 6, 6, 6, 6, 4, 3,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
3, 4, 6, 6, 6, 6, 4, 3,
2, 3, 4, 4, 4, 4, 3, 2
distribution après 2 coups:
12, 18, 23, 26, 26, 23, 18, 12,
18, 24, 32, 37, 37, 32, 24, 18,
23, 32, 42, 48, 48, 42, 32, 23,
26, 37, 48, 56, 56, 48, 37, 26,
26, 37, 48, 56, 56, 48, 37, 26,
23, 32, 42, 48, 48, 42, 32, 23,
18, 24, 32, 37, 37, 32, 24, 18,
12, 18, 23, 26, 26, 23, 18, 12
Si ces nombres font du sens pour toi, ils montrent qu'il faut calculer comme moi et pas comme l'a indiqué dan31. (La formule de dan31 ne calcule pas l'évolution de la distribution uniforme, mais l'évolution de chaque case individuellement.)
Pour l'oscillation, tu en avais déjà une si tu calculais les rapports entre les sommes successives plutôt que leur racine n-ième:
336/64 = 5.25000000
2008/336 = 5.97619048
12000/2008 = 5.97609562
72288/12000 = 6.02400000
433872/72288 = 6.00199203
...
|
|
|
La première manip c'est celle que fait flab et les valeurs qu'il donne correspondent aux nombres de cavaliers par cases. Je ne vois pas le problème. Je n'ai pas compris le calcul de la deuxième manip.
Sinon, si j'ai bien compris, le "potentiel" limite calculé, c'est juste le nombre de cases qu'un cavalier parcourant l'échiquier au hasard aurait en moyenne à sa disposition. Et les dernières valeurs données par flab correspondraient alors à la probabilité du cavalier de se trouver sur chaque case (à 1 facteur près).
En normalisant, ça donnerait :
a1: 0,008594741
b1: 0,011271609
c1: 0,012522169
d1: 0,012286522
b2: 0,016470411
c2: 0,018281775
d2: 0,022106687
c3: 0,024402887
d3: 0,027039211
d4: 0,152976010
|
|
|
Le nombre de cavaliers par case dans le cas stable, bien sûr
|
|
|
Attention aux calculs de ces probabilités Comme je l'ai dit plus haut, les probabilités de présence du cavalier sur chaque case s'influencent mutuellement. Prenons l'exemple de la case a1 et c2/b3. Les probabilités de a1 sont influencées par celles de c2/b3. Pruisque celles de a1 sont modifiées, celles de c2/b3 sont elles aussi modifiées, ce qui influence encore les probabilités de a1. Bref, plus n croît, plus le cavalier aura de chance de tomber sur une case du milieu que sur n'importe quelles autres. C'est ce qui explique que le potentiel du cavalier croît de manière logarithmique vers 8.
|
|
|
Désolé, je me suis planté dans la présentation des nombres Ils sont décalés d'une ligne :
a1: 0,005480400
b1: 0,008594741
c1: 0,011271609
d1: 0,012522169
b2: 0,012286522
c2: 0,016470411
d2: 0,018281775
c3: 0,022106687
d3: 0,024402887
d4: 0,027039211
|
|
|
ref flab je ne pense pas qu'une des deux formules ait le plus de sens que l'autre. Ce qui a un sens, c'est le nombre de parcours total possible en n coups, en partant d'une case donnée. Une fois qu'on a ces 64 suites, on en fait ce qu'on veut non ? Chacune de ces suites u_n doit tendre en racine n ieme vers 6,01 (car l'influence de la case de départ disparaît évidemment quand n grandit). Le reste, c'est couper des cheveux en 4.
Par contre il serait intéressant de voir ce qui se passe quand on ne raisonne plus en nombre de parcours mais en probabilité de parcours. Quelle est la probabilité limite d'être sur chacune des cases quand le temps de parcours devient grand ? Dans ce cas, il faut considérer des probabilités de transition d'une case à l'autre : en d4, une proba de 1/8 d'aller dans les 8 cases accessibles, mais en a1, une proba 1/2 (chaine de Markov). Cela ne revient pas au même il me semble que le vecteur propre calculé que FPC a normalisé, car chaque ligne de la matrice n'est pas divisé par le même coefficient (mais peut-être que je dis des c...), et donc la matrice de la chaine de Markov que j'évoque n'est pas simplement multipliée par un scalaire. J'ai pas matlab sous la main, mais je jetterai un oeil demain.
|
|
|
Tiens, c'est rigolo mais en fait les deux problèmes sont différents C'est juste que les valeurs trouvées sont très proches, ce qui m'a induit en erreur.
|
|
|
ref FPC comprends pas ? De quoi tu parles ?
|
|
|
Je croyais que le potentiel moyen correspondait au nombre de cases disponibles en moyenne pour un cavalier parcourant l'échiquier au hasard. En fait, ce nombre moyen est 251/42 = 5,976...
La probabilité de chaque case est
a1 = 1/168 = 0,005952...
b1 = 1/112 = 0,008929...
c1 = d1 = b2 = 1/84 = 0,011905...
c2 = d2 = 1/56 = 0,017957...
c3 = d3 = d4 = 1/42 = 0,023810...
Enfin, si ça se trouve, je me plante complètement.
|
|
|
On peut se poser la question : Pourquoi la case c3 est-elle aussi probable que la case d4, alors que les voisines de c3 (par exemple b1) sont moins probables que les voisines de d4 (par exemple c2) ?
En fait, c'est tout simplement que b1 est moins probable que c2 parce qu'elle a moins de voisines. Mais comme elle a moins de voisines, un cavalier en b1 est plus susceptible d'aller en c3, qu'un cavalier en c2 d'aller en b4 !
Autre manière de voir : on met sur chaque case autant de cavaliers que de cases voisines. C'est à dire 2 cavaliers en a1, 3, en b1, 4 en c1, 4 en d1, etc...
Ensuite, chaque cavalier fait mouvement vers une des cases voisines de manières équirépartie : de a1, un cavalier va en c2 et l'autre en b3, etc. On se retrouve bien entendu dans la même situation qu'au départ !
|
|
|
Je termine : c'est une situation stable Il y a 336 cavaliers au départ, et donc on retrouve les probabilités que j'ai données : a1 = 2/336 = 1/168 etc...
|
|
|
Multiplicité des valeurs propres Pour répondre à un point de dan31, dans certains cas la valeur propre maximale est répétée ou son négatif apparait:
C: 6.01066, -6.01066
F: 9.16127, 9.16127
T: 14.0000
D: 22.9360
R: 7.29086
La deuxième valeur négative pour le C représente le fait que la case du cavalier change de couleur à chaque coup (graphe biparti). La valeur double pour le F représente le fait que la case du fou reste la même couleur (graphe déconnecté).
La marche aléatoire d'un cavalier est un autre problème avec une matrice de transition différente. La distribution stable de la marche aléatoire est la distribution "après 1 coup" de l'autre problème. On peut la normaliser en divisant les valeurs par 336, comme l'a fait FPC.
|
|
|
@flab "La formule de dan31 ne calcule pas l'évolution de la distribution uniforme, mais l'évolution de chaque case individuellement." Pour moi, c'est justement ce qu'il faut chercher, apres quoi tu sors la valeur moyenne en additionnant tout et en divisant par 64 ? Pourquoi pas ?
|
|
|
La manip 1 que j'ai decrite est seulement un truc bizarre qui fait loucher.
tu pars du 2eme tableau de repartition, tu dis que chaque chiffre represente un nombre de Cs que tu envoies chacun sur une case differente alentours (ce qui est tres different de notre calcul, ou on envoie tous les Cs sur chaque case alentours). Et la tu obtiens une situation stable comme explique plus haut.
|
|
|
La manip 2 que j'ai decrite montre un cas extreme d'asymetrie centre/peripherie : on fabrique un echiquier de 9 cases avec 1 case centrale et 8 peripheriques, lesquelles ne sont connectees qu'a la centrale.
On applique le meme type de calcul pour l'evaluation du potentiel moyen par coup et par case. Le calcul simple a la main montre l'oscillation cherchee.
|
|
|
@flab Je trouve ta remarque sur les rapports successifs des sommes tout a fait fantastique. C'est effectivement un moyen simple de montrer une oscillation.
|
|
|
La signification de ces chiffres l'extraction de la racine n-ieme equivaut a une expansion theorique moyenne M(n) recalculee a posteriori, et dit ceci " compte tenu de tous les chemins possibles du C, tout se passe comme si il avait M(n) coups a jouer a chaque coups". Tandis que les rapports successifs proposes par flab montrent a chaque fois l'expantion reelle E(n) et indiquent "pour passer de n a n+1 coups, tout se passe comme si le Cavalier avait E(n) coups a sa disposition"
|
|
|
ref FPC Oui j'avais bien vu que les deux problèmes étaient différents. Dans le cas exposé au début du post, on s'intéresse au NOMBRE de parcours possibles en n coups pour un cavalier, dans l'autre problème (marche aléatoire du cavalier), on s'intéresse à la STRUCTURE d'un parcours aléatoire du cavalier. Il semble que le nombre de parcours se mulitplie (en moyenne) par 6.0107 à chaque nouveau coup quand n devient grand. Apparemment, il est légèrement différent du nombre de cases moyen accessible à un cavalier qui suit une marche aléatoire (tu confirmes ton 5.98 ?). Que les valeurs trouvées soient très proches n'est malgré tout pas étonnant.
|
|
|
ref FPC Je suis d'accord avec ton post de 21h57 et 21h59. Par contre, je n'ai pas utilisé la même méthode : d'où vient ton 251/42 , 1/168 ... ?
J'obtiens aussi la distribution suivaznte stable de probabilité pour le cavalier suivant une marche aléatoire :
0.0060 0.0089 0.0119 0.0119 0.0119 0.0119 0.0089 0.0060
0.0089 0.0119 0.0179 0.0179 0.0179 0.0179 0.0119 0.0089
0.0119 0.0179 0.0238 0.0238 0.0238 0.0238 0.0179 0.0119
0.0119 0.0179 0.0238 0.0238 0.0238 0.0238 0.0179 0.0119
0.0119 0.0179 0.0238 0.0238 0.0238 0.0238 0.0179 0.0119
0.0119 0.0179 0.0238 0.0238 0.0238 0.0238 0.0179 0.0119
0.0089 0.0119 0.0179 0.0179 0.0179 0.0179 0.0119 0.0089
0.0060 0.0089 0.0119 0.0119 0.0119 0.0119 0.0089 0.0060
|
|
|
ah oui j'ai capté pas la peine de répondre et je confirme par la même le 5.9762
|
|
|
Les nombres viennent bêtement de la configuration stable avec 2 cavaliers en a1, 3 en b1, etc... divisé par le nombre total de cavaliers (336).
Pour a1 : 2/336 = 1/168 = 0,0060
Pour b1 : 3/336 = 1/112 = 0,0089
...
Pour d4 : 8/336 = 1/42 = 0,0238
Pour trouver le nombre moyen de coups à la disposition du cavalier, il suffit de le faire dans la configuration stable, c'est à dire :
(2*2 (pour a1) + 3*3 (pour a2) +... )/336 =2008 / 336 = 251 /42 = 5,9762. Donc, oui, je confirme ce nombre.
En fait, je n'ai pas du tout calculé ces valeurs comme cela, au départ, mais en résolvant le système 10x10 pour trouver la configuration stable. Ce n'est qu'après coup que je me suis rendu compte que la configuration stable était élémentaire.
PS : C'est moi qui ai cru que les problèmes étaient les mêmes. D'ailleurs, j'ai eu du mal à comprendre pourquoi les résultats étaient différents. Et je ne comprends vraiment l'interprétation du potentiel que depuis le dernier commentaire (particulièrement clair) de JRotenberg.
|
|
|
Wouah, je suis vachement lent pour taper :-)
|
|
|
bon bref on s'est compris reste à trouver la solution du second problème pour les autres pièces lol
|
|
|
Et pour les autres pièces avec la même méthode Fou : 5120/560 = 64/7 = 9,142857
Tour : 12544/896 = 14 (ouf!)
Dame : 33344/1456 = 2084/91 = 22,901099
Roi : 2940/420 = 7
|
|
|
Décidément !
|
|
|
Pour le pion À la question originale sur le taux de croissance asymptotique du nombre de parties possibles, la réponse est le maximum de C F T D, donc la même valeur que la dame: 22.936022...
À l'autre question sur le nombre de coups possibles moyen asymptotique dans une marche aléatoire, la moyenne C F T D proposée par sigloxx est la bonne démarche, mais avec les nombres de FPC: (251/42 + 64/7 + 14 + 2084/91)/4 = 28403/2184 = 13.005036...
|
|
|
Un sujet passionnant ! Je viens de mettre cette page dans mes favoris et elle figurera aussi dans mes liens sur
Chess-Theory
La question d'origine est très pertinente et tout le fil est conduit avec intelligence ! De plus les résultats exposées sont parfaitement cohérents et justes.
J'ai moi-même fait des calculs similaires, mais je ne dispose plus des moyens de calcul que j'avais lorsque j'étais professeur d'université. D'ailleurs j'avoue avoir commis deux à trois erreurs avant de rejoindre vos résultats.
En tout cas bravo à tous !
Michel
|
|
|
Un problème de martinguale Il y a une autre voie, connue des mathématiciens et statisticiens, qui est la théorie des martingales. Je ne parle pas de martingales au sens du jeu (concept usuel), mais prises au sens mathématique moderne.
On ne peut raisonner, au moins au départ, qu'en termes d'échiquier vide. Sinon le problème devient astronomiquement compliqué et finit par échapper à toute théorisation. D'ailleurs tout serait banalisé avec un échiquier vide infini...
Donc, considérons un Cavalier et son déplacement aléatoire sur l'échiquier. L'étude faite ici permet une mise en forme exacte de son processus aléatoire de déplacement.
Le déplacement d'une pièce, du Cavalier donc en particulier, est a priori un processus de Markov, ce qui veut dire sans mémoire. Que ce processus soit une martingale est beaucoup moins évident et relève d'un calcul compliqué (d'autant plus qu'il s'agit ici de processus vectoriels de dimension 2).
Lorsque j'aurai le temps je mettrai tout ceci en forme d'un point de vue théorique ; laissant à ceux qui disposent des moyens informatiques adéquates (et du temps nécessaire !) le soin d'effectuer les calculs de l'espérance conditionnelle qui intervient ici. Il faut savoir que la théorie moderne des martingales permet principalement d'obtenir des théorèmes de convergence
Seul point rassurant, nous sommes dans le domaine de la finitude et il n'est donc pas nécessaire de faire appel à l'abstraite théorie de la mesure de Henri Lebesgue !...
Michel
|
|
|
oui j j'ai effectiv
|
|
|
j'ai effectivement trouvé ce fil de bonne tenue (sans verser trop dans l'auto congratulation). Ca devient trop rarement le cas sur france echecs (excepté à la rubrique problèmes), mais ca fait plaisir. Par contre faudrait que je trouve quelques minutes pour interpréter la légère différence dans les valeurs limites trouvées pour les deux problèmes. J'avoue que je suis aussi un peu connaisseur des chaines de Markov, ce qui m'a aidé pour le second problème. Néanmoins FPC a prouvé qu'on pouvait aussi le résoudre sans cette artillerie un peu lourde. Quant au premier problème posé par JRotenberg, il faisait intervenir de l'algèbre linéaire plus "basique", car le calcul de la puissance n ieme d'une matrice permettait d'y répondre.
|
|
|
En effet !.... Il est vrai que l'algèbre linéaire bien utilisée peut déjà beaucoup... mais ce n'est pas trop ma tasse de thé :-)
Quant à la qualité des débats, je l'ai évoquée, car c'est malheureusement loin d'être la règle ... Oh ! Sur ce forum comme sur d'autres.
J'ai quand même le souvenir, sur France-Echecs justement, de débats très contradictoires sur le thème "Echecs et Hasard" , qui avaient franchement été passionnants !
|
|
|
Sur la différence des deux problèmes Prenons l'exemple d'un cavalier en d2 et d'un parcours de longueur 2. Comparons le nombre de coups disponibles après 1.Cf3 2.Ce5 (8 coups)et après 1.Cb1 2.Ca3 (4 coups).
Dans le problème initial, ces deux valeurs ont le même poids. On compte simplement le nombre de coups disponibles sur tous les parcours.
Dans le problème de la marche aléatoire, le parcours d2-f3-e5 est moins probable (1/6 * 1/8 = 1/48), et donc a moins de poids que le parcours d2-b1-a3 (1/6 * 1/3 = 1/18).
Paradoxalement, entre deux parcours, celui qui passe le plus par les bords est plus probable ! Ça explique la valeur plus petite trouvée pour le parcours aléatoire.
|
|
|
Si dan31 et FPC Voulaient bien preciser les problemes qu'ils traitent... je ne suis pas tres sur d'avoir compris qqchose
|
|
|
Le premier problème, c'est le tien On dénombre tous les parcours de longueur n. On s'intéresse en gros à la limite (ou à la limite de la moyenne, suivant la formule employée) du facteur qui permet de passer de n à n+1. On construit donc l'arbre de tous les parcours possibles de longueur n. Le facteur pour passer de l'étape n à l'étape n+1 est alors le nombre moyen de coups disponibles à l'étape n, la moyenne étant calculée en donnant le même poids à chaque parcours.
Le deuxième problème, c'est le nombre de coups disponibles en moyenne pour un cavalier parcourant l'arbre de manière aléatoire. En gros, on s'intéresse aussi au nombre moyen de coups disponibles à l'étape n, mais cette fois la moyenne est calculée en tenant compte de la probabilité de chaque branche.
|
|
|
Des petites zones d'ombre Pour le probleme d'origine, je n'arrive pas bien a comprendre a quoi doit correspondre la difference qu'il doit y avoir entre le potentiel moyen par coup calcule au global, et la moyenne des potentiels moyens par coup calcules case case case
Le calcul case par case doit reveler des proprietes interessantes : les phenomenes oscillatoires ne doivent pas apparaitre au meme temps pour chaque type de case.
Y a-t-il des cases sur lesquelles l'amplitude des oscillations est maximun ?
L'amplitude des oscillations diminue-t-elle homogenement pour chaque case en fonction du nombre de coups ?
y a-t-il des cases pour lesquelles l'oscillation apparait meme avec le calcul par racines n-iemes ? (temporairement ?)
Pour bien montrer la difference entre ce calcul et l'approche probabiliste, il suffit d'imaginer un Cavalier sur echiquier infini, a partir d'une case de depart precise ;
Le potentiel moyen par coup reste constant a 8 evidemment.
Tandis que la repartition moyenne sur l'echiquier va representer une fonction plus ou moins homogene de la distance a la cese de depart. On a donc une espece de phenomene dispersif.
Sur un echiquier normal, les bords ont un effet de reverberation. Peut-on mettre ici aussi en evidence des phenomenes d'oscillation ? voire des figures d'interferences ?
|
|
|
A tous les mathématiciens Je suis à la recherche du livre de Bronstein : Aide mémoire de mathématique. Qui n'en n'a plus besoin ?
|
|
|
