À la question de Wirth et des chaînes

Algorithmes + structures de données = programmes - Virt N.

«Nous avons eu une merveilleuse occasion de mener un petit exercice tactique extrêmement instructif»

Malgré la première épigraphe de ce billet, je me permets d'être en désaccord avec l'auteur et d'essayer de montrer que dans certains cas, le bon choix de structure de données peut être plus important que le bon choix d'algorithmes. Pour illustrer une thèse aussi séditieuse, considérons une tâche simple mais prometteuse pour étudier le jeu "Chain".

Tout d'abord, sur les règles du jeu - deux joueurs jouent, la position de départ se compose de N objets situés à proximité. La prochaine étape consiste à supprimer un ou deux objets situés à proximité (vous pouvez essayer de donner une définition formelle de "emplacement à proximité", mais cela est compréhensible à un niveau intuitif). Le joueur qui retire le dernier objet gagne - le jeu direct, ou celui qui doit (vous ne pouvez pas sauter le coup) ramasser le dernier objet - le jeu inverse gagne. Étant donné que dans cette version des règles, un jeu direct sera tout simplement inintéressant (plus de détails plus tard), une restriction supplémentaire est introduite - un seul objet peut être supprimé au premier coup.

Tout d'abord, nous déterminons que le jeu est fini, car à chaque mouvement le nombre d'objets diminue strictement et le jeu se termine lorsque le nombre d'objets calculé par zéro est atteint, nous avons donc le droit de compter sur le succès dans l'étude de ce jeu. De plus, il est évident que le jeu ne peut pas durer plus de N coups, rappelons-le.

L'étude du jeu consiste à déterminer si pour un nombre initial spécifique d'objets le joueur effectuant le premier coup gagne (puisqu'il s'agit d'un jeu à somme nulle, sinon il perd) avec un jeu optimal des deux côtés et dans quel nombre minimum de coups le gain est réalisé (ou par quel est le nombre maximum de coups la perte s'éloigne).

Pour certains de H, la réponse est évidente - avec un objet, le premier gagne une partie directe en un tour et perd également une partie inverse (P1 = 1, I1 = -1). Avec deux objets, le premier joueur perd en deux coups en partie directe et gagne en deux coups en inverse (P2 = -2, I2 = 2), ce qui peut donner lieu à une hypothèse sur la simplicité de l'évaluation de ce jeu, ce qui est confirmé par le cas de trois objets (P2 = 3, I3 = -3). Heureusement (sinon ce billet n'aurait pas été publié) un jeu avec quatre objets change quelque peu l'image (P4 = -4, mais I4 = -3), donc rechercher le jeu est vraiment nécessaire.

Pour certains de H et pour un certain type de jeu, il existe des algorithmes heuristiques qui donnent un gain garanti. Par exemple, pour une partie directe avec un H initial impair, vous pouvez être assuré de gagner si vous supprimez l'objet central avec le premier mouvement et répétez ensuite les mouvements de l'adversaire en utilisant une place centrale comme axe de symétrie, alors nous sommes garantis de ramasser le dernier objet et de gagner. La même stratégie fonctionnerait avec un nombre pair d'objets, sinon pour les restrictions sur le premier coup, ce qui rend le jeu pas si trivial. D'une manière générale, l'utilisation de stratégies symétriques est assez courante dans le comptage des jeux, mais pas une panacée, car, par exemple, dans notre jeu inverse, cette stratégie échoue. Il convient de noter que l'heuristique donne un algorithme gagnant mais ne donne pas d'estimation précise de la position, car il peut y avoir des stratégies qui conduisent à des gains plus rapides (c'est le cas pour ce jeu particulier).

Comment pouvons-nous donner une évaluation du jeu - exactement comme j'ai reçu les estimations précédentes pour 1-4 objets - la méthode est appelée recherche exhaustive de haut en bas - nous devons considérer l'arborescence complète du jeu, c'est-à-dire tous les mouvements possibles des deux côtés et évaluer chaque position, y compris source, selon certaines règles. Il convient de noter que l'existence d'heuristiques réussies ne nous garantit pas une évaluation précise, car elle ne répond qu'à la première moitié de la question - qui gagne, mais ne donne pas le nombre minimum de coups requis.

Cela signifie que nous devons construire un arbre de jeu complet, mais avant de procéder à la construction, nous devons créer un modèle de l'objet à l'étude, dans notre cas, le jeu.

Pourquoi je me concentre sur cette étape - parce que nous ne pouvons pas explorer l'objet dans son incarnation matérielle. Non, purement théoriquement, cela est possible («peu de choses sont possibles dans le monde en général purement théoriquement») et je peux imaginer une image où un très grand nombre de robots jouent à beaucoup de jeux dans le monde réel, mais les coûts matériels pour une telle solution au problème d'évaluation du jeu dépassent le quantités, nous sommes donc obligés de se lancer sur la voie de la modélisation d'objets réels avec leurs homologues logiciels. Et ici, il est très important de suivre une ligne fine, en combinant un niveau suffisant d'adéquation du modèle et la simplification nécessaire.

Mais d'abord, un peu de mathématiques pour évaluer la complexité de la tâche - nous devons trier tous les mouvements possibles dans le jeu (l'attention n'est pas toutes les positions possibles, c'est le sujet d'une autre méthode, à savoir les mouvements) et nous aimerions évaluer la quantité de ressources requise avant de commencer le travail - pour déterminer l'ordre de la tâche. Au premier coup, nous avons la possibilité de retirer toute puce (je continuerai d'appeler des objets) de H disponible, au prochain coup - n'importe laquelle des H-1 ou deux puces restantes à proximité (il n'y aura pas plus de paires que H-2), ce qui donne le nombre total d'options Hx (H-1 + H-2). Il est facile de voir qu'après le troisième mouvement, nous avons Hx (H-1 + H-2) x (H-2 + H-3 + Δ) et ainsi de suite.

Si nous nous limitons dans chaque tranche aux seuls premiers termes de la somme, alors nous obtenons une estimation du nombre total de mouvements comme H!, Ce qui nous donne une estimation en quadratures de H ^ H.

Il s'agit d'un résultat très désagréable, qui prétend que nous aurons de très gros problèmes avec un H significatif, de sorte que la modélisation «frontale» entraînera très probablement des coûts de calcul importants. Par exemple, pour 16 jetons dans la position de départ, nous devrons considérer environ 16! = 1013 coups, et si un coup est de 10E-9 secondes (estimation assez optimiste), alors le temps total sera d'environ 10E4 secondes ou presque 3 heures, ce qui est un peu trop , mais acceptable, mais pour seulement 20 puces, le temps de calcul prévu est de 77 ans, ce qui est clairement inacceptable. Le factoriel se développe très rapidement et il n'y a rien à faire.

Nous attirons l'attention sur le fait que le nombre de mouvements dépasse de manière significative le nombre de positions possibles, qui n'est que de 2 ^ N, et il est évident que nous tomberons dans une position distincte pour 16 jetons 10E (13-5) = 10E7 fois, ce qui est assez courant pour tâches de recherche. N'oubliez pas ce fait, il nous sera utile plus tard.

Néanmoins, nous allons commencer à écrire un programme, dont nous déterminerons le modèle. Tout d'abord, nous numérotons les puces de 1 à H, puis créons un tableau avec le nombre d'éléments H, et déterminons que le numéro 1 dans l'élément de tableau avec l'index n signifie la présence du numéro de puce n, et le nombre 0 - son absence dans une position spécifique. Un tel modèle est adéquat, simple, intuitif et vous permet de rendre efficaces les opérations d'élimination des copeaux, ainsi que de déterminer la condition de "proximité".

Maintenant que nous avons un modèle (structure de données), nous pouvons commencer à extraire (hiboux sur le globe) l'algorithme sur ce modèle. L'algorithme d'énumération complète avec retour est simple dans le schéma fonctionnel et se compose de deux parties indépendantes - l'énumération réelle et l'évaluation des positions, pour commencer nous allons implémenter la première partie. Notez que cet algorithme n'est pas mieux implémenté dans le cadre du paradigme de programmation structurelle et serait un peu plus efficace si nous nous permettons d'utiliser une transition ou de répéter le code, mais même sans ces écarts par rapport au style, l'implémentation n'est en aucun cas prétentieuse (la complexité cyclomatique est tout à fait acceptable) . Étant donné que nous n'avons pas encore introduit d'évaluation, et que nous aimerions obtenir les résultats du programme, nous dérivons simplement les positions considérées et les examinons avec nos yeux pour évaluer la mise en œuvre correcte et nous assurer que les résultats correspondent aux résultats attendus.

Ajoutons maintenant une estimation de position - bien sûr, un code bien écrit est auto-documenté (bien qu'il existe des opinions différentes concernant cette déclaration), mais cette partie est mieux décrite en mots. L'idée est que nous donnons une évaluation sans ambiguïté des positions finales (dans notre cas, elle est unique et se compose de zéro jetons), sur la base des règles du jeu, et pour toutes les autres positions, nous donnons une évaluation neutre préliminaire, puis nous commençons à l'affiner en déplaçant l'estimation vers le haut de l'arbre . Lorsque vous reculez, l'estimation de la position actuelle change de un dans la direction de zéro, puis elle est inversée et transférée à la position précédente, où elle est combinée avec l'estimation précédente selon les règles suivantes:

1. les évaluations neutres passent à une nouvelle,
2. une note positive passe à une note positive plus petite,
3. une évaluation négative devient un grand négatif ou positif.

Après avoir complètement parcouru tous les mouvements, l'évaluation de la position initiale est définitive.

Nous ajoutons des estimations à notre procédure de génération de toutes les positions et nous pouvons admirer les résultats de l'analyse, qui sont affichés dans un tableau, ajouter un compteur de progression et un compteur de temps pour l'analyse. Sur le compilateur gcc (en mode d'optimisation -O2) sur une machine avec un processeur, j'ai obtenu une telle table qui confirme pleinement nos hypothèses initiales sur l'ordre factoriel de complexité de la tâche. À partir du même tableau, nous voyons que j'ai cessé d'attendre des résultats avec H supérieur à 11, car le temps de calcul est devenu inacceptable (pour moi, vous êtes peut-être prêt à attendre une demi-heure) et notre hypothèse sur le cours et la nanoseconde ne correspond pas à la réalité (temps moyen considération de la position est de 100 ns). La question se pose - que devons-nous faire si nous voulons avoir une estimation de plus de 11 jetons dans la position initiale.

Nous pourrions prendre le chemin de petites optimisations, jouer avec les transitions et les drapeaux, aller dans les insertions d'assembleurs, appliquer des opérations vectorielles délicates à partir du système d'instructions de notre processeur, et de cette façon, vous pouvez gagner de la vitesse sans ambiguïté parfois, par un ordre de grandeur - peut-être deux ordres de grandeur - c'est très peu probable, mais nous avons besoin d'un gain de plusieurs ordres de grandeur, car l'ordre (et même plus) nous mangerons une augmentation de H de un sur 10. Soit dit en passant, si vous activez simplement l'optimisation du compilateur, cela fera quelque chose pour nous et le temps d'exécution diminuera J'ai 4 fois - pas mal du tout et conformément à nos attentes.

Par conséquent, nous devons d'abord essayer d'améliorer les algorithmes appliqués, et la première de ces améliorations (et la principale) est la méthode de coupure par force brute ou la "procédure alpha-bêta". Son idée principale semble assez robuste et consiste dans le fait que si nous évaluons une certaine position comme gagnante, nous cessons d'améliorer la note pour celle-ci et retournons à l'arbre. Cette approche peut augmenter considérablement la vitesse de l'algorithme, surtout si nous étudions les mouvements réussis (conduisant à une victoire) en premier lieu. Mais cela peut également augmenter le temps, puisque la vérification de l'évaluation actuelle est ajoutée et que la procédure de choix du cours est compliquée, il est très difficile d'estimer à l'avance l'influence de cette méthode, il est nécessaire de mener une expérience. Et encore une considération - nous ne devons pas oublier que dans le cas d'une recherche avec coupure, dans le cas d'une position gagnante, nous donnons une estimation vraie, mais pas précise, car nous ne considérons pas une partie des options, et ils pourraient donner une victoire en moins de coups. Si une telle diminution de précision nous convient, alors pourquoi ne pas utiliser cette méthode, mais pour une évaluation précise, rien d'autre qu'une recherche exhaustive ne fonctionne.

Les résultats de l'énumération d'écrêtage sont présentés dans le tableau suivant, et nous voyons qu'il y a un gain de performances et une augmentation significative, mais pas suffisant pour étudier de grandes valeurs de N.Dans quelle direction nous poursuivrons nos recherches - nous allons d'abord examiner une autre structure de données, eh bien, et ensuite, vous l'avez deviné (agréable de traiter avec un public rusé) est un autre algorithme.

Prenons attention au fait que la structure de données que nous adoptons rend les puces uniques et, par exemple, une seule puce (n'ayant pas de puce adjacente) en position n'est pas équivalente à une seule puce en position n + 2, ce qui est complètement faux. Nous sélectionnons l'élément clé de la position de jeu - le groupe de jetons situé à côté et déterminons sa principale caractéristique - le nombre de jetons dans le groupe. Ce sont ces informations qui déterminent de manière unique toute position dans le jeu, et nous devons les présenter sous une forme pratique pour la programmation. Nous choisissons la structure de données la plus simple et la plus évidente - nous commençons un tableau d'éléments H et stockons dans l'élément n du tableau le nombre de groupes avec exactement n puces. Ensuite, par exemple. Pour la position de départ avec 3 jetons, nous aurons la représentation {0,0,1}. La procédure d'exécution pour la présentation donnée est toujours simple et efficace, bien que, bien sûr, plus compliquée que dans la première version. Après le premier coup (dont il y en avait deux au lieu de trois) on obtient les positions {0,1,0} et {2,0,0}.

Essayons d'estimer le gain attendu du nombre de déplacements pour une structure de données donnée. Pour le premier coup, nous avons (H-1) / 2 + 1 options, pour le second (nous avons divisé le groupe H en m et N-m-1) (m-1) / 2 + (N-m-1-1) / 2 (prendre 1 puce) + (m-2) / 2 + (N-m-1-2) / 2 (prendre 2 jetons) = (H-3) / 2 + (H-5) / 2 et par analogie , nous concluons qu'à chaque étape, nous économisons au moins la moitié des mouvements. Ensuite, notre gain devrait être d'au moins 2 ^ H, ce qui est très, très bon pour les grands H. En fait, le gain sera encore plus important, par exemple, pour la position {8,0 ...} dans le premier mode de réalisation, vous devez trier 8 mouvements, et dans le second seulement 1 et le gain dans ce cas sera 8 fois. Nous pouvons donc fermement compter sur 2 ^ H, mais attendons beaucoup plus, ce que nous vérifierons. Et pour sûr, pour le programme selon cette représentation, nous obtenons le tableau 4, la dernière ligne montre le gain de performance lors du passage à la deuxième version de la structure de données (calculée à la main). La croissance est tout simplement colossale et nous avons franchement (atteint le bas) franchi le plafond de la possibilité d'analyser jusqu'à 20 jetons en position de départ à un coût raisonnable.

De plus, nous pouvons nous engager dans une optimisation subtile de l'algorithme pour une structure de données donnée et obtenir même un gain de performances, mais nous n'obtiendrons pas une croissance aussi spectaculaire (par ordre de grandeur), ce qui indique une fois de plus que Wirth avait tort. Par exemple, dans le programme ci-dessus, la procédure pour créer le prochain candidat pour le mouvement n'était délibérément pas optimale et sa correction évidente (laissons le lecteur curieux) augmenter la vitesse de 3 fois, mais c'est une bagatelle, quoique agréable.

Faisons attention aux résultats et voyons des choses pas évidentes. Par exemple, le programme prétend qu'une victoire garantie dans un jeu direct pour 9 jetons n'est pas obtenue du tout en 9 coups, comme suit de l'algorithme symétrique heuristique, mais en seulement 7, et le premier coup coïncide avec l'heuristique (et, de plus, est la seule position gagnante ), mais le troisième et les suivants ne devraient pas du tout répéter les mouvements de l'adversaire, comme suit à partir de l'algorithme naïf, et la clé ici est {1,0,0,1}, qui a une note de +4. Maintenant que nous avons donné une évaluation précise du jeu, nous pouvons poser des questions intéressantes concernant la présence de positions avec une évaluation stable (dans laquelle nous pouvons laisser l'adversaire partir pour nous-mêmes), la présence de positions clés dans l'arbre d'énumération, trouver des positions avec le seul mouvement à droite, etc. (et même obtenir des réponses à ces questions, et les bonnes).

Voici le tableau récapitulatif des notes

Chips	Direct	Rétroaction	Positions / Temps	Positions / Temps
1	1	-1	1/0	1/0
2	-2	2	4/0	2/0
3	3	-3	17/0	7/0
4	-4	-3	82/0	20/0
5	5	4	463/0	71/0
6	5	-5	3032/0	263/0
7	7	6	22693/0	1107/0
8	-8	-7	191422/0	4945/0
9	7	-7	1798427 / 0,1	24,283 / 0
10	9	8	18634228 / 0,8	125419/0
11	11	-9	211177537 / 10.4	699165 / 0,1
12	-10	-9	*** / 127	4057686 / 0,6
13	11	10		25056975 / 3,84
14	-12	-11		160643971/28
15	13	12		1082854607/213
16	-14	-13		*** / 1698

Néanmoins, nous constatons que l'estimation de la durée d'exploitation est restée factorielle, bien qu'avec une baisse significative du taux de croissance. Cherchons d'autres façons d'explorer l'arbre du jeu.

Nous avons perfectionné l'algorithme de haut en bas (eh bien, bien sûr, nous ne l'avons pas fini sous la forme laide que j'ai esquissée au dos de l'enveloppe, vous pouvez améliorer considérablement les performances en réécrivant soigneusement les procédures de base, et cela est sûr d'être fait, mais le problème n'est pas cardinal décide), alors allons dans l'autre sens - de bas en haut. L'idée de cette méthode est intuitivement simple et compréhensible, mais très difficile à utiliser par l'homme - nous partons de la position finale, qui est estimée selon les règles du jeu, et commençons à transférer l'estimation vers le haut de l'arbre selon les mêmes règles que pour la recherche descendante. Bien sûr, en même temps, nous considérons qu'il n'est pas possible de descendre de la position actuelle, mais nous considérons toutes les positions à partir desquelles nous pourrions entrer dans la position actuelle d'un coup. Nous transférons le devis selon les règles ci-dessus. De plus, nous appliquons cette procédure de manière itérative et lorsqu'elle cesse de produire des résultats, c'est-à-dire qu'au cours du tour suivant, pas une seule position n'a changé l'évaluation, la tâche est terminée et l'évaluation de la position initiale est correcte et exacte. Cette approche vous permet de réduire considérablement le temps de recherche, surtout si vous apportez quelques améliorations, mais elle présente un inconvénient majeur (et c'est un classique - nous changeons le temps pour la mémoire), limitant considérablement sa portée - des exigences de mémoire élevées, car nous devons stocker des estimations , ( ). , , ( ), , , , . , , 20, 2^20, , -20 20, 8- , . , . , , . , , , , , 2* ( ). *2* , , , *2**.

2^**2^=2^(2*)* ( , ) , , =20 - 20!~1018, - 2^40*20=(2^10)^4*40=(10^3)^4*40~10^14, 20 106 , . 9 , 9!~106, 2^9*2^9*18~106, . , — , (1).

, . 9 , : 1+(1+4)+(1+3+2)+(1+3+3+2)+(1+2+2+1+1)+(1+2+1+1)+(1+1+1)+(1+1)+1=1+5+6+9+7+5+3+2+1=39.
**=39*39*9~104, , . , , .

, -, . , . . — ( , /2), , 2 .

— , , . , , ( ) .

, () — , , , , ( ) . , — , .

PS. (, ), — , , , , - ( , ), ( ), 1.878^ ( ). , , , , (ars longa, vita brevis).