[Échecs]
Benwa a écrit:
<<
Si je ne m’abuse, il y a bien plus de parties d’échec différentes possibles que de particules de matière dans l’univers…
>>
Tentacule a répondu
<<
Je suis d’accord avec toi sur le nombre, mais l’atteindre ne me semble pas impossible.
Pas de mon vivant, en tout cas
>>
La discussion parlait de la capacité d’un ordinateur à calculer les coups d’une partie d’échec.
J’aime bien cette discussion (mais je suis peut-être un cas… spécial). Je me suis d’abord dit que Tentacule voyait juste: le nombre est grand mais fini, c’est donc une question de rapidité finalement.
Et puis le doute: imaginons qu’un ordinateur utilise une particule d’énergie pour calculer un coup, alors il n’aurait pas assez de toutes les particules de l’univers pour calculer tous les coups. Intéressant non? … non? … bon
Benwa a écrit:
<<
Si je me souviens bien, il y a 2 exposant 120 parties d’échecs différentes possibles…
>>
Ca aussi c’est amusant: si l’on se fie à la loi de Moore, qui postule un doublement de la capacité des ordinateurs tous les 18 mois, imaginons qu’un ordinateur aujourd’hui calcule un coup en une milliseconde, alors dans 180 ans un ordinateur sera capable de calculer tous les coups possibles d’une partie d’échec en une milliseconde. Etonnant, non?
si si, c’est une question que je me suis également posée…
de toute manière, même si le calcul est éventuellement possible, les résultats seraient impossible à exprimer, non?
en fait, après vérification, ce nombre serait de 10 exposant 120, et non de 2 exposant 120, soit:
10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.
000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000
nim dit:Benwa a écrit:
<<
Si je me souviens bien, il y a 2 exposant 120 parties d'échecs différentes possibles...
>>
Ca aussi c'est amusant: si l'on se fie à la loi de Moore, qui postule un doublement de la capacité des ordinateurs tous les 18 mois, imaginons qu'un ordinateur aujourd'hui calcule un coup en une milliseconde, alors dans 180 ans un ordinateur sera capable de calculer tous les coups possibles d'une partie d'échec en une milliseconde. Etonnant, non?
Oui mais dans la loi de Moore, il faut mettre le terme "loi" entre guillemets.
Par ailleurs, je viens de lire que 10 puissance 120, c'est plus qu'il n'y a eu de microsecondes depuis le big bang...
Bon, enfin, bref...
Faut vraiment etre Blege pour ce poser de telles questions 
Désolé mais elle etait vraiment facile 
Agartha
Blege toi-même !
Et voila, je veux faire une blague et ma dyslexie du clavier casse la chute !! 
Agartha
Désolé, j’étais parti manger.
Je trouve la question intéressante (intelecto-masturbatoirement parlant), pourtant je ne suis pas blege, je suis rlochelais expatrié à Blordeaux…
nim dit:Je me suis d’abord dit que Tentacule voyait juste: le nombre est grand mais fini, c’est donc une question de rapidité finalement.
Il faut aussi penser au stockage des parties ! Je ne connais pas le nombre moyen de coup dans une partie d’échec mais on pourrais calculer la place que prendrais l’archivage.
benwa dit:en fait, après vérification, ce nombre serait de 10 exposant 120, et non de 2 exposant 120
Oui, c’est ENORME, et même si manipuler des nombres de cette taille pose à mon avis quelques problèmes d’ordre informatique, ça reste possible.
Si mes calculs sont bons, il faudrait 512 bits pour coder l’identifiant d’une partie soit 64 octets, qu’il faut multiplier par le nombre de parties possibles puis par le nombre moyen de coups par partie (pour cette dernière donnée, je n’en sais fichtre rien…)
Puis on pourra calculer combien de disques dur de grande capacité il faut, puis la taille que ça prendrais, puis le temps de ma vie perdu à faire ces calculs… ok je me calme.
Le Tentacule dit:Je ne connais pas le nombre moyen de coup dans une partie d'échec
Entre 100 et 150, à mon avis.
Notons par ailleurs que le nombre dont on parle ici est le nombre de "parties" différentes. Ce qui n'est pas la même chose que le nombre de posittions différentes sur l'échiquier, lequel doit être (un peu) moins élevé sans doute.
Le nombre de configurations différentes doit être extrèmement moins élevé !
Mais je me place dans l’hypothèse d’une machine optimale, donc qui connait toutes les parties possibles (et donc toutes les fins possibles).
Il ne me manque plus que le volume de la Terre et je pourrai enfin… CONQUERIR LE MONDE euh… je pourrai calculer combien de fois la taille du système solaire une telle machine peut prendre
pfiou ! 
Oui, si le but est de garder les parties en mémoire.
Moi mon but, ce serait plutôt de répondre à la question: blanc a-t-il une stratégie gagnante?
(Je sais que ça n’a en final aucune espèce d’importance, c’est juste par curiosité intellectuelle)
nim dit:Oui, si le but est de garder les parties en mémoire.
Moi mon but, ce serait plutôt de répondre à la question: blanc a-t-il une stratégie gagnante?
C'est la même chose !
Grace à toutes les parties mémorisées, la machine saura si la partie en cours tend plutôt vers les parties gagnantes ou perdantes pour lui, et il pourra ainsi orienter ses coups suivants.
Une autre méthode, non otpimale celle là, pourrait être de calculer à chaque tour toutes les configurations possibles, puis de donner une "note" à chacune et de choisir celle dont la note est la meilleur. Le tout est de trouver une bonne méthode de notation...
La définition du stratégie gagnante est :
-quelque soit le coup de mon adversaire, il existe au moins un coup qui me pemette de gagner et ce, quelque soit le coup suivant de mon adversaire… (et cela en boucle !)
Le Tentacule dit:
Une autre méthode, non otpimale celle là, pourrait être de calculer à chaque tour toutes les configurations possibles, puis de donner une "note" à chacune et de choisir celle dont la note est la meilleur. Le tout est de trouver une bonne méthode de notation...
c'est déja comme ca que marchent les programmes qui jouent !
Pour la loi de moore, il y a semble t il, une limite. Avec les technos actuelles (puces de silicium) on n'est probablement pas loin de cette limite (d'apres les travaux d'un chercheur dont j'ai oublié le nom et que j'ai lu je ne sais plus ou
).
Oui c’est vrai la loi de Moore n’est pas une loi, j’ai d’ailleurs dit “postule” et pas “démontre”.
C’est vrai que l’on approche des limites de la physique? Ce qui est amusant c’est que l’on disait aussi ça il y a 25 ans, 20 ans, 15 ans, 10 ans, 5 ans, et pourtant la “loi” s’est toujours confirmée. La réponse facile est de dire “oui mais là on ne les avait pas vraiment atteinte tandis que maintenant c’est du sérieux”. Même si je trouve que les physiciens sont des gens sérieux, je n’oserait malgré tout rien parier sur les capacités des ordinateurs de dans 150 ans, ni même dans 30 ans, si une telle chose existe encore. Il faut faire un peu de “thinking out of the box” et se dire que l’on trouvera autre chose, seules les technologies d’aujourd’hui ont atteint leurs limites.
Bon alors maintenant c’est vrai qu’il ne faut pas compter sur Microsoft, dont la complexité de l’OS suit aussi la loi de Moore. (c’est une boutade)
nim dit:, seules les technologies d'aujourd'hui ont atteint leurs limites.
Je n'ai pas dit autre choses !
C'est sur elles que s'appuie la loi de moore.
Quand a prevoir l'avenir
Prenez un bouquin de prospective un peu daté et lisez le. C'est vraiment un exercice amusant.
Selon moi :
le doublement de la puissance des machines va peut être continuer encore quelques temps, mais en aucun cas cela ne peut être une loi absolue.
Le calcul d’une stratégie gagnante pour blanc est peut être réalisable, sans utiliser d’heuristique (à savoir sans faire des estimations de la valeur du coup comme écrit précédemment ce qui a l’inconvénient de pouvoir faire passer à côté de la stratégie gagnante), mais ca prendra du temps et de la place.
Quelques problèmes à gérer :
- chaque coup doit être étudié plus ou moins l’un après l’autre, si on ne veut pas répéter le même traitement pour un état du damier donné. Il faut donc stocker l’état des parties commencées pour pouvoir étudier chaque état “fils” de la partie commencée courante… Et l’état des parties déjà vues. Ca prend beaucoup beaucoup de place, non pas en taille d’un état de partie, il n’y a que 64 cases qui ne peuvent avoir que quelques 2x9 valeurs différentes. mais dans le nombre de parties commencées.
- Avant d’ajouter un nouvel état de partie, il faut vérifier qu’il n’a pas déjà été traité (c1) ou ajouté (c2), pour gagner de la place et assurer au programme un arrêt, un jour.
- il faudrait pouvoir déterminer qu’un état de partie ne sera plus jamais retrouvé en partant des états de parties qui n’ont pas encore été traité (pour éviter les comparaisons c1 mais surtout gagner de la place) mais le coût d’une telle vérification en temps est très élevé !
- Enfin, trouver UNE stratégie gagnante “coûte” théoriquement autant que trouver TOUTES les stratégies gagnantes, surtout si cette stratégie n’existe pas.
- Connaissez vous le projet Seti ? Pour comparaison, en utilisant 4806221 ordinateurs de par le monde depuis son lancement le 17 mai 1999, le programme a tourné 1748529.82 heures (dont 1139.994 années hier), même en multipliant par 60 x 60 x 1000 on est loin des 20 zéros !
Voila pour mes premières impressions du matin sur le sujet
jmguiche dit:Je n'ai pas dit autre choses !
Pas de problème jmguiche, je n'ai pas prétendu le contraire, je faisais juste une digression.
jmguiche dit:nim dit:, seules les technologies d'aujourd'hui ont atteint leurs limites.
C'est sur elles que s'appuie la loi de moore.
C'est vrai, la loi de Moore s'applique aux technologies d'aujourd'hui, voici d'ailleurs une petite référence intéressante (le premier hit google): http://www.volle.com/travaux/moore.htm
Quant à l'avenir, la seule chose que j'espère réellement est qu'il verra plus de volonté de préserver notre planète. Pour rebondir du sujet de la miniaturisation, même avec des méthodes d'exploitation modernes, nous utilisons de plus en plus d'énergie pour transformer une même quantité de matière, et cela se combine avec le fait que notre société de consommation utilise de plus en plus de resources. Combinez les deux, et vous pourrez en déduire un parallèle à la loi de Moore, mais relatif à la destruction des resources de la Terre. C'est triste...