|
| Une partie au hasard par w***9760 le
[Aller à la fin] |
| Informatique | |
Qui est capable de programmer rapidement un petit programme capable de jouer au échecs, pour qu'il joue contre lui meme avec des coups au hasard.
J'aimerais savoir quel est le pourcentage de gains par rapport à celui de nulles dans ces parties jouées au hasard.
Alors un programmateur dévoué ? trop facile pour certains, non ?
Merci pour votre réponse
P.S. : Je ne compte pas la règle des 50 coups ni des 3 positions répétées.
|
|
|
Pourquoi ne pas compter ces causes principales de nullité ?
Sinon une partie au hasard se terminerai-t-elle ? Je ne le pense pas.
PS: vaut mieux dire "programmeur" que "programmateur".
|
|
|
ayè, c'est fait je n'ai évidemment pas écrit un nouveau programme, juste modifié GNU Chess. Ceci est rendu possible par la publication de son code source, vive le source ouvert ! Vive le logiciel libre !! Euh... bref. Voici le patch :
diff -Naur gnuchess-5.07/src/eval.c random-gnuchess/src/eval.c
--- gnuchess-5.07/src/eval.c 2003-08-07 10:39:52.000000000 +0200
+++ random-gnuchess/src/eval.c 2005-06-14 23:15:58.000000000 +0200
@@ -1311,6 +1311,8 @@
side = board.side;
xside = 1 ^ side;
+ return rand () % 255;
+
/* If we are looking for a MATE, just return the material */
if (alpha > MATE-255 || beta < -MATE+255)
return (MATERIAL);
diff -Naur gnuchess-5.07/src/gnuchessx random-gnuchess/src/gnuchessx
--- gnuchess-5.07/src/gnuchessx 2003-06-12 23:33:06.000000000 +0200
+++ random-gnuchess/src/gnuchessx 2005-06-14 23:18:05.000000000 +0200
@@ -8,5 +8,5 @@
# bug in some old Unix-like systems; see the GNU autoconf documentation
# for the rationale.
-gnuchess xboard ${1+"$@"}
+./gnuchess xboard ${1+"$@"}
diff -Naur gnuchess-5.07/src/init.c random-gnuchess/src/init.c
--- gnuchess-5.07/src/init.c 2003-06-12 23:33:06.000000000 +0200
+++ random-gnuchess/src/init.c 2005-06-14 23:04:28.000000000 +0200
@@ -24,6 +24,8 @@
cracraft@ai.mit.edu, cracraft@stanfordalumni.org, cracraft@earthlink.net
*/
+#include
+
#include
#include
#include
@@ -41,6 +43,10 @@
*
**************************************************************************/
{
+ struct timeval tv;
+ gettimeofday (&tv, NULL);
+ srand (tv.tv_sec);
+
InitLzArray ();
InitBitPosArray ();
InitMoveArray ();
à mettre dans un fichier, appelons-le "gnuchess-patch", appliquer comme ceci : dans le répertoire de GNU Chess, taper
patch -Np1 -i gnuchess-patch
on peut ensuite l'installer normalement (./configure && make && make install), puis l'utiliser (xboard -fcp /chemin/vers/gnuchessx -scp /chemin/vers/gnuchessx, le mettre en mode "two machines"). Le résultat est assez... spécial ;-)
Maintenant, il est évident que le résultat va fortement dépendre de la fonction utilisée pour produire des nombres (pseudo-)aléatoires. M'enfin, tu as déjà de quoi t'amuser avec ça...
:wqa
|
|
|
exemple de partie C'est assez étrange à regarder...
[Event "Computer chess game"]
[Site "Naoned"]
[Date "2005.06.14"]
[Round "-"]
[White "GNU Chess 5.07"]
[Black "GNU Chess 5.07"]
[Result "0-1"]
[TimeControl "-"]
1. e4 c6 2. Qg4 Qb6 3. Be2 Kd8 4. Qf4 Qxf2+ 5. Kxf2 e5 6. Qg5+ Be7 7. d3
Ke8 8. Qxe7+ Nxe7 9. Bh5 Na6 10. Bxf7+ Kxf7 11. Nh3 Rf8 12. Be3 Kg8+ 13.
Ke1 Nc5 14. Na3 Nd5 15. Bxc5 Rf3 16. Ng5 Re3+ 17. Kf1 Nc3 18. Bxe3 b5 19.
b3 h6 20. Bc5 Nxe4 21. Ke1 Nd2 22. Nf3 Nxf3+ 23. Kd1 Ng1 24. Be3 d5 25. Kc1
Ne2+ 26. Kd2 Nc3 27. Raf1 Nb1+ 28. Nxb1 Bg4 29. Rf7 Kxf7 30. Rf1+ Kg8 31.
a4 h5 32. Rf8+ Rxf8 33. a5 Rf1 34. Nc3 d4 35. Bf2 Rxf2+ 36. Ke1 Rxc2 37.
Ne4 a6 38. h3 Kf8 39. hxg4 h4 40. Kf1 Rc1+ 41. Ke2 Ra1 42. g5 Rg1 43. Kd2
Ke7 44. Ke2 g6 45. Kf2 Rc1 46. Ke2 c5 47. Kf3 b4 48. Nf6 Kf7 49. Nd7 Ke8
50. Nxe5 Re1 51. Nc4 Kd8 52. Kg4 Ke7 53. Kxh4 Kf8 54. Kg4 Re7 55. Kg3 Kf7
56. Kf3 Kg8 57. Nd6 c4 58. Kf4 Re2 59. Kf3 cxd3 60. Kg3 d2 61. Ne4 d1=Q 62.
Nf6+ Kh8 63. Ng4 Qh1 64. Kf4 Qf1+ 65. Kg3 Rxg2+ 66. Kh4 Qh1+ 67. Nh2 Qxh2#
{computer wins as black} 0-1
|
|
|
Y a pas à dire C'est agressif pour les noirs, la Caro-Kann.
|
|
|
allez, une autre Visez le 42e coup noir, c'est trop... Mais ne nous étonnons pas, c'est normal de la part de la Réponse à la grande Question de la Vie, de l'Univers et de Tout Ça... (traduction libre de Douglas Adams, pour ceux qui ne connaissent pas c'est une star de la littérature geek).
[Event "Computer chess game"]
[Site "Naoned"]
[Date "2005.06.14"]
[Round "-"]
[White "GNU Chess 5.07"]
[Black "GNU Chess 5.07"]
[Result "0-1"]
[TimeControl "-"]
1. Nc3 e5 2. e3 Qg5 3. Qf3 Qf5 4. Qxf5 Kd8 5. Qg5+ f6 6. Qg4 Bc5 7. Qxd7+
Nxd7 8. Nd5 Bb4 9. a3 Bxd2+ 10. Ke2 Nc5 11. Nf3 Ne4 12. Nxc7 Bd7 13. Bxd2
Nc3+ 14. bxc3 Kc8 15. c4 Ne7 16. Rd1 Nd5 17. Ke1 Nf4 18. Bb4 a5 19. Nd5 Be8
20. Nb6+ Kb8 21. Bd6+ Ka7 22. Bb8+ Rxb8 23. exf4 Rd8 24. Nd4 Rxd4 25. Nc8+
Ka8 26. Rxd4 Kb8 27. Rd8 Kc7 28. Rd7+ Bxd7 29. Ne7 Kd8 30. Nd5 exf4 31. c5
Re8+ 32. Be2 Rxe2+ 33. Kxe2 Bg4+ 34. Kd2 Be6 35. Nxf4 g5 36. Re1 Kc8 37.
Re4 gxf4 38. Rxe6 f3 39. Re8+ Kd7 40. Rf8 fxg2 41. c6+ Kxc6 42. Re8 g1=R
43. Re6+ Kc7 44. Re7+ Kb6 45. Rf7 Ka7 46. Rxf6 Rf1 47. Ra6+ bxa6 48. Kd3
Re1 49. Kd4 h6 50. a4 Re7 51. f3 Ka8 52. c3 Rd7+ 53. Ke5 Kb8 54. c4 Re7+
55. Kf6 Rc7 56. Ke5 Rc5+ 57. Ke4 Rxc4+ 58. Kd5 Rc7 59. Kd4 Rd7+ 60. Ke4 Kb7
61. h3 Kc6 62. Kf4 Rd5 63. Kg3 h5 64. h4 Rd7 65. Kf4 Kd6 66. Kg5 Rd8 67.
Kg6 Ke5 68. Kf7 Ra8 69. Kg6 Rc8 70. f4+ Ke6 71. f5+ Ke7 72. Kg7 Rf8 73. Kg6
Rg8+ 74. Kh7 Rg1 75. Kh8 Kf6 76. Kh7 Rb1 77. Kh6 Rb8 78. Kxh5 Rb4 79. Kh6
Rxh4#
{computer wins as black} 0-1
|
|
|
@ pessoa tout est dans le sacrifice de dame, très tôt dans la partie, à infliger à l'adversaire lorsqu'il ne s'y attend pas :-))
|
|
|
Bien vu le parallèle avec le guide du routard galactique, oeuvre majeure dont je recommande chaleureusement la lecture (vous pourrez faire les malins quand le film sortira en France). Pas réservé aux geeks (moins que la SF lourde qui sévit actuellement).
|
|
|
ah, le Guide... à lire en anglais bien évidemment, c'est bourré de jeux de mots et je ne veux même pas savoir comment ils se sont fait massacrer par la traduction...
The mattress flurred and glurried. It flolloped, gupped and willomied, doing this last in a particularly floopy way.
"Voon", it wurfed at last[...].
(Douglas Adams, in Life, the Universe and Everything).
ça ne rate jamais, à chaque fois que je lis ça je me marre...
|
|
|
J'ai en effet rarement lu une chose aussi bourrée et truffée de calembours douteux. Cela dit, après avoir fait le snob, je peux avouer que j'ai franchement beaucoup ri !
Speedy, que oui, les littéraires ont accès à la littérature de geeks...
|
|
|
quand même, le sacrifice d'extraction 4 .. Dxf2+ qui mate en 63 coups, c'est superbe mais je ne sais pas si j'aurais osé le jouer. Pas à dire, ces bécanes voient beaucoup plus loin que nous !
|
|
|
Je suis très sceptique sur le fait que les coups soient totalement aléatoires. Bien sûr, il me serait difficile de le démontrer, mais en regardant j'ai vraiment l'impression qu'il y a un certain biais dans le tirage des coups.
|
|
|
Même que Cyrillev Je trouve que beaucoups de coups normaux sont joués pour une partie 'random'. Notamment le Txh4# de la deuxième qui n'est qu'un coup parmis une multitude d'autres.
|
|
|
il est possible bien sûr que quelque chose m'ait échappé... mais quoi ? J'ai remplacé la fonction d'évaluation par un tirage au sort et il n'y a pas de bibliothèque d'ouverture ni de table de finales, normalement il n'y a plus que du hasard...
|
|
|
Une piste le tirage au sort pourrait favoriser certains nombres ? En particulier, que se passe-t-il lorsque le tirage sort un nombre supérieur au nombre de coups légaux dans la position ?
|
|
|
le tirage favorise bien sûr certains nombres mais on n'y peut rien, sauf si on a un dispositif matériel produisant des nombres aléatoires pas pseudo. Quant au résultat, il ne sert pas à choisir un coup dans la liste mais à juger un coup donné, a priori je ne crois pas que du favoritisme soit possible. Peut-être faudrait-il chercher s'il n'y a pas une vérification quelque part conduisant, par exemple, à ne pas appeler la fonction d'évaluation du tout si on trouve un coup conduisant directement au mat. J'ai autre chose à faire pour le moment...
|
|
|
ref cyrillev division euclidienne ?
|
|
|
à mon avis des parties aléatoires devraient se conclure par la nulle après bien 300 coups aussi débiles les uns que les autres. Le mat serait le 0.01% de chance comme au loto. Je pense que les parties sont à 90% de coups réfléchis et 10% de débilités.
|
|
|
Le guide désolé de revenir là-dessus, mais le guide du Routard est fort bien traduit en français, avec un réel effort sur les calembours stupides. Mais j'avoue ne pas avoir lu l'original.
|
|
|
ref wqa Je viens de mettre au point un petit programme capable de tirer des coups au hasard. En comptant la règle des 50 coups, et en ignorant la répétition de position, on trouve les résultats suivants :
- 85 % de nulles et 15 % de gains
- les parties durent 200 coups en moyenne (ça va de 20 à 330 coups)
- le programme tire plusieurs centaines de parties à la seconde (avec un Pentium 4 à 2.6 Ghz et 512 Mo de RAM sous Windows XP)
Note : le générateur de hasard utilisé est la fonction rand() du C++... il faut donc prendre ces résultats avec prudence.
|
|
|
Mes résultats Je ne pense pas que daik ait fait la bonne modification. On dirait que son random-gnuchess joue pour le mat lorsqu'il en voit un.
Voici les résultats que j'obtiens après 5 millions de parties aléatoires jouées en 10h par mon propre moteur d'échecs:
victoire des blancs: 7.775%
victoire des noirs: 7.781%
nulle (pat): 6.757%
nulle (position morte): 77.687%
Par position morte, j'entends une finale roi+roi, roi+roi+cavalier, roi+roi+fous (n'importe quel nombre de fous sur des cases de la même couleur), et position bloquée.
Donc une partie aléatoire typique, c'est plutôt ceci:
1. Nc3 a6 2. Rb1 c6 3. d3 c5 4. Be3 g6 5. h3 f6 6. Rh2 Kf7 7. Bc1 h6 8. e4 a5 9. Rh1 a4 10. Qf3 d6 11. Qe3 Na6 12. Qe2 Ke6 13. Nb5 Nb4 14. Na7 b6 15. Be3 Qe8 16. Nc6 Na6 17. Na7 Qd7 18. Kd2 d5 19. Rc1 Ke5 20. d4+ Kd6 21. Bf4+ Ke6 22. g4 dxe4 23. f3 Qd5 24. b3 Qxb3 25. Qb5 Qb2 26. Qd7+ Kxd7 27. Bh2 e3+ 28. Kd3 c4+ 29. Kxc4 h5 30. Bg2 Bb7 31. gxh5 Rc8+ 32. Bc7 Rh6 33. Rh2 Qb3+ 34. axb3 axb3 35. Kxb3 Rd8 36. Ka3 Bd5 37. f4 gxh5 38. Nc8 e6+ 39. Bd6 Bg7 40. Bf3 Nb8 41. c3 Ba8 42. Bxb8 Re8 43. Nd6 Rxb8 44. Ra1 Be4 45. Rf1 e2 46. Rff2 Bh7 47. Bxe2 Kxd6 48. Nf3 Bf8 49. Nd2 Bg6 50. Bxh5 Ra8+ 51. Kb4 Ra7 52. Rfg2 Ra6 53. Rg1 Ra2 54. Nb3 Be4 55. Be2 f5 56. Bh5 Rf6 57. Rg6 Rf7 58. Rhg2 Ne7 59. Bf3 Nc6+ 60. Kc4 Nxd4 61. Rxe6+ Kc7 62. Rg1 Ba3 63. Rd6 Nc2 64. Rg7 Bc1 65. Rdg6 Be3 66. Re6 Kd7 67. Bg4 Bf2 68. Rxf7+ Kd8 69. Rff6 Ne1 70. Rf8+ Kd7 71. Bf3 Be3 72. Rxe4 Kd6 73. Rfe8 Bc1 74. Na5 b5+ 75. Kd4 Bd2 76. Re3 Rb2 77. Bb7 Rb4+ 78. c4 Bc3+ 79. Rxc3 Ng2 80. h4 Nxh4 81. Rc2 Ng6 82. Bd5 Nxf4 83. Rb8 Ra4 84. Rh2 Nd3 85. Rh1 Rxc4+ 86. Nxc4+ Kd7 87. Rh5 f4 88. Ba8 f3 89. Ne3 Kd6 90. Nf1 Nc5 91. Nd2 Ne6+ 92. Ke3 Nc7 93. Rd8+ Ke7 94. Rh7+ Kf6 95. Rdh8 Nxa8 96. Rh4 Kf7 97. Ra4 Ke7 98. Rhxa8 Ke6 99. Kd4 f2 100. Kd3 Kf7 101. Ra3 f1=B+ 102. Ke3 Bc4 103. Kf2 Ke7 104. Rd3 Bxd3 105. Rf8 Kd7 106. Nb1 Bc4 107. Nd2 Bd5 108. Rf4 Ke6 109. Nb1 Bg2 110. Ra4 bxa4 111. Kg3 Bf1 112. Kg4 Bc4 113. Na3 Bb3 114. Nc4 Bc2 115. Kh4 Kd5 116. Nb2 Ke6 117. Nd1 Kf6 118. Nb2 Bd3 119. Nxa4 Bf5 120. Nb2 Ke6 121. Kg3 Kf7 122. Kg2 Bg6 123. Kf2 Ke7 124. Nc4 Bh7 125. Kg2 Ke6 126. Nb2 Kf6 127. Kh1 Bc2 128. Nc4 Kg7 129. Kh2 Be4 130. Kh3 Bg2+ 131. Kxg2
Notez que la probabilité qu'une pièce soit jouée est proportionnelle au nombre de coups légaux de cette pièce.
Histogramme de la longueur d'une partie aléatoire:
de 0.0 à 0.5 coups: 0.000%
de 1.0 à 1.0 coups: 0.000%
de 1.5 à 2.0 coups: 0.003%
de 2.5 à 4.0 coups: 0.034%
de 4.5 à 8.0 coups: 0.116%
de 8.5 à 16.0 coups: 0.290%
de 16.5 à 32.0 coups: 1.144%
de 32.5 à 64.0 coups: 4.350%
de 64.5 à 128.0 coups: 12.486%
de 128.5 à 256.0 coups: 66.556%
de 256.5 à 512.0 coups: 14.455%
de 512.5 à 1024.0 coups: 0.561%
de 1024.5 à 2048.0 coups: 0.005%
de 2048.5 à 4096.0 coups: 0.000%
de 4096.5 à 8192.0 coups: 0.000%
de 8192.5 à 16384.0 coups: 0.000%
...
arrêté après 1 million de coups: 0.0004%
Les positions bloquées sont trop difficiles à détecter directement. Je les détecte par l'arrêt de la partie après 1 million de coups. En voici un exemple:
Les résultats sont intéressants, donc c'était une excellente question, wqa!
|
|
|
G E N I A L Vous etes géniaux. Cette question me trottait depuis quelques temps dans la tete. Je la pose hier soir, je reviens le lendemain soir, et je vois que ds personnes ont passé du temps à y répondre et meme tres en détail. De voir tous ces chiffres statistiques, ça me rejouis, meme si ça ne servira surement à rien, sauf à ma curiosité.
En tous cas un très GRAND merci aux programmeurs Flab et Pages pour la précision de leurs réponses.
|
|
|
Superbe et original De mémoire de france-échiquéen (et ça fait un bout de temps que je traîne ici), cette question n'avait jamais été abordée.
Je retiens un point du message de Flab :
de 1.5 à 2.0 coups: 0.003%
Ce qui veut dire que sur ses 5 millions de parties, le hasard a amené 150 fois le "mat du niais". (1 f3 e5 2 g4 Dh4# et équivalents).
Or, mon propre calcul (de la combinatoire pas trop complexe) me donne une probabilité de 1/30000 pour ariver au mat du niais en jouant au hasard, soit 0,003% pareillement.
Donc j'aurais tendance à croire en la validité des résultats de Flab (et ceux de pages, qui concordent).
Bravo aux programmeurs pour ce moment de détente para-échiquéenne !
|
|
|
Pffffff la honte Les vrais geeks ne lisent pas le Hitchhiking's Guide, ils écoutent la série radio qui lui est antérieure....
|
|
|
Tout pareil que l'ami Pessoa... C'est un domaine où je ne comprends rien et je suis épaté par la vitesse et la qualité des réponses. Ca change de certaines embrouilles à 0,3 euros qu'on peut lire sur ces pages :-)
Pour ma part, je retiens deux choses:
- Si l'on faisait des stats du pourcentage de nulles selon le niveau, on aurait sans doute une courbe marrante, commençant à 85%, chûtant très vite (les débutants font très peu nulle) puis remontant progressivement jusqu'à atteindre le niveau de Peter Leko (=95%) puis rebaissant un peu (Anand, Topalov, ex-Kaspy) :-)
- Il faudrait aussi faire des stats sur l'avantage que donne le trait. En aléatoire, visiblement, il est nul (il y a même léger avantage aux Noirs dans les stats de Flab, non significatif à mon sens). Donc 50-50. Il faudrait voir ensuite comment évolue la courbe selon le classement...
Je parle je parle, et puis un doute m'étreint: est-ce que, comme je l'ai supposé légèrement, le jeu aléatoire constitue le niveau le plus faible des Echecs? Eh beh non... On peut supposer qu'il est possible de jouer plus mal qu'un programme jouant de manière totalement aléatoire! Donc il est abusif de placer le jeu aléatoire au début de la courbe du N'elo sans faire jouer ledit programme contre un échantillon représentatif d'humains. Non mais.
De la même manière (scusez, j'ai une imagination débordante, aujourd'hui), ne pourrait-on essayer de programmer un programme pour qu'il soit le plus nul possible? Avoir un logiciel capable de perdre contre n'importe qui, même contre Peter Leko, quoi de plus émoustillant pour un programmeur? Et voir la mine des humains dépités, "putain, j'ai tout fait pour trouver le perpet mais il a réussi à m'imposer une suite gagnante", ce serait énorme...
|
|
|
En "mat inverse" On a déjà débattu ici du jeu d'échecs "inversé", où chaque camp tenterait de forcer l'adversaire à le mater.
Très probablement, le résultat de presque toutes les parties serait la nulle. La seule stratégie de victoire plausible qui ait été proposée est la suivante : essayer de gagner beaucoup de matériel, ne laisser à l'adversaire, par exemple, qu'une pièce et surtout quelques pions contre une armée presque au complet, puis bloquer ces pièces jusqu'à forcer le mat comme dans un problème de mat inverse...
Ce qui est intéressant, ce que puisque pour arriver à ces fins il faut d'abord s'assurer l'avantage matériel, dans une position donnée le "meilleur coup pour perdre" pourrait être le même que le "meilleur coup pour gagner"...
|
|
|
moi aussi j'ai fait un programme d'échecs :) en 1 demi-coup il fonctionne à peut près en mode 4 ...Dxf2+ (ben vi après les blancs ont un pion de moins :-/), et en 2 demi-coups j'ai le choix entre la multiplication de pièces (sisi, une partie avec 16 pions noirs et 5 cavaliers blancs sur l'échiquieret après qqes coups d'ouverture..) et la "java.util.ConcurrentModificationException".
Bref, déjà c'est en java, et en plus c'est po au point (les règles du jeu, le mode deux joueurs et l'interface graphique sont assez propres d'après mes tests, mais bizarrement au delà de 2 demi-coups.. sniff..)
|
|
|
fq
|
|
|
ref pessoa Il y a un exemple joué par correspondance (en 1878 !) qui illustre tes propos.
|
|
|
Argl pas réveillé, moi ... ... oublié de fermer la balise.
|
|
|
