Algorithmes de recherche

1. Introduction

On se place dans le cas simple d'un jeu séquentiel et déterministe à un seul joueur. La première discussion consiste à déterminer une problèmatique générale pertinente. On choisi un jeu séquentiel par souci de simplicité en quantifiant les actions chronologiquement. On choisie un jeu déterministe pour ne pas avoir à introduire une probabilité venant de l'exterieur. Ce qui n'empêchera pas les probabilités d'intervenir, mais elles seront générées de l'intérieur du système. Dire qu'un système est indéterminé cela signifie qu'une cause d'évènements est à l'exterieur du système. Et on choisi un seul joueur car le cas de plusieurs joueurs, comme on le verra, ne change pas la nature du problème autrement que par l'ajout de causes extérieurs que constituent les autres joueurs exterieurs, leus profiles psychologiques..., le mécanisme qui détermine leurs décisions.

L'algorithme de recherche consiste à trouver un chemin dans le graphe du jeu qui aboutie à un état gagnant.

Du fait de l'aspect séquentiel du jeu, les différents états possibles du jeu sont représentés par les sommets d'un graphe, et les différentes actions possibles du joueur sont représentées par les arrètes orientées du graphe.

Dans le cas générale, le jeu n'est pas fini, et il se peut qu'il n'y est pas d'états finaux. Le but du joueur est alors plus difficile à définir...

Le but, est par principe défini dans les règles du jeux, et s'appuit donc sur une évaluation objective de l'état du jeu. Si l'évaluation introduit des conditions sur les états anterieurs, on peut toujours regrouper ces conditions passées pour en faire une variable d'état présente.

Le but peut ne pas être final, en particulier lorsqu'il n'y a pas d'état finaux. Cette question est intéressante à plusieur égards. Par analogie au système capitaliste, elle se pose pour le capitaliste, toujours en quète de capital, toujours remis en cause et dont l'accumulation n'a pas de limite. Par analogie à la recherche, elle se pose pour le chercheur. La recherche peut-être sans fin et pourtant elle a une finalité.

L'approche capitalistique consiste à évaluer objectivement le jeu selon un unique indicateur appelé valeur, un indicateur totalement ordonné. Le but est d'obtenir une valeur la plus élevée possible. Mais il apparait alors une seconde problèmatique incontournable qu'est le temps, à savoir combien de temps voulons nous prendre pour atteindre cette valeur. il y a alors nécessairement 2 indicateurs que sont la valeur et le temps.

On pourrait simplifier l'approche soit en arrêtant le jeu à un temps précis ou en rendant le jeu fini, soit en ne considérant qu'un seul indicateur qu'est le temps de jeu. Cela suppose que le jeu présente des états finaux de fin de jeu. Le but est alors de jouer le plus long temps possible, ou le plus court temps possible. Tout se passe comme si ces états finaux était tous perdants ou tous gagnants, mais où le temps en nombre d'actions, est l'unique élément pour évaluer la partie jouée. On remarquera que l'indicateur capitalistique de l'état du jeu continu encore d'exister, et il ne contient que 2 valeurs, dans le cas de la rechechre du plus court temps (+1 : gagné), (0 : jeu pas fini), et dans le cas de la rechechre du plus long temps (-1 : perdu), (0 : jeu pas fini).

On limite l'introduction du temp dans les critères de victoire ou de défaite, aux seuls critères monotones. Exclu donc, le critère de terminer la partie à un instant précis. Seul compte la duré en tant qu'indicateur totalement ordonné. On commence ainsi une classification des jeux par une approche simple et intuitive.

La recherche du plus court temps gagnant et du plus long temps perdant se regroupent en un seul jeu à trois états (-1 perdu, 0 jeu pas fini, +1 gagné). Le jeu peut ne jamais s'arréter. On peut introduire une limite subjective k à partir de la quelle si le jeu n'est pas terminé il est considéré qu'il ne se terminera probablement jamais. Les joueurs sont alors notés dans cet ordre :

g1, g2, g3..., gk, ∞ ,pk..., p3, p2, p1

g3 signifie gagné en 3 coups, p3 signfie perdue en 3 coup, et signifie ni gagné ni perdu et que la partie n'est pas fini après k coups.

Nous optons donc sur le principe d'une notation du joueur jouant une parti, et la structure des notes doit être totalement ordonnée. Cette dernière hypothèse permet d'ordonner les joueurs selon leur note. Mais il n'y a pas de sommation canonique pour noter un joueur dans un jeu composé de plusieurs parties. C'est la règle du jeu composé qui devra décider des modalités de calcul de cette note.

Puis on généralise en considérant des victoires partielles et des défaites partielles. Le but peut être partiellement atteint. On va alors évaluer la part acquise, comme une quantité d'information. On peut définir une quantité d'information selon un model entropique, parcontre la sommation devra obéir aux lois des probabilités conditionnelles. La victoire correspond à une part de taille 1 et la défaite correspond à une part de taille 1 pour un adversaire imaginaire. Et chaque noeud est à la fois perdant et gagnant et est donc caractérisé par 2 valeurs. En faite l'adversaire imaginaire ne nous est pas utile. On s'en tiendra donc pour chaque état à une valeur comprise entre 0 et 1 désigant la quantité d'information de l'état vers la réussite. Une valeur 1 signifie 100% réussit, une valeur 0 signifie 0% réussit, une valeur comme 0.12 signifie 12% réussit, ces valeurs désignent une quantité d'information définie selon un model entropique, elles se composent, et si elles sont redondantes, elles ne s'ajoutent pas.

Une note est un élément d'un ensemble totalement ordonnée, permettant ainsi de déterminer parmis deux joueurs notés lequel des deux est vainqueur ou s'il sont ex-égaux.

On s'intéresse aux jeux composés de n mêmes jeux joué dans un ordre quelconque. Le joueur jouera n parties et selon sa note pour chacune de ses paties, il lui sera donné une note globale correspondant à un n-uplet . La note globale est pour les mêmes raisons que précédement, un élément d'un ensemble totalement ordonnée. Et elle doit vérifier les règles suivantes :

  1. L'ordre des parties ne doit pas intervenir.
  2. L'ordre des notes doit être respecté, c'est à dire la note globale correspondant à une suite de notes dans laquel une ou plusieurs notes sont plus élevées doit être plus élevée.

--- 22 déceembre 2013 ---

2. Programmation

Pour que la programmation des algorithmes de recherche soient aussi simple que les concepts qu'ils portent, il faut poser au préalable les infrastructures nécessaires à leurs libres expressions. C'est une sorte de framework, un langage avec le souci de son implémentation, que voici :

Selon la programmation orientée objet, les données sont mémorisées dans des objets qui admettent des attributs contenant d'autres objets, etc., et on accède à ces attributs en utilisant l'opérateur point "." suivi du nom de l'attribut. Les objects possèdent également des méthodes auxquels on accède également à l'aide de l'opérateur point ".".

L'état du jeu à un instant donné constitue un objet mémorisé par la variable S. A chaque état S, on calcul la liste des actions possibles du joueur, une liste exhaustive et exclusive, à l'aide d'une fonction ou méthode que l'on nomme list appliquée à l'état S du jeu. Puis à chaque action, il faut calculer l'état du jeu obtenu après l'exécution de l'action. L'action est considérée comme une fonction transformant l'état S. Puis il faut évaluer l'état S du jeu pour savoir si l'état est gagnant ou perdant ou ni l'un ni l'autre. L'évaluation du jeu se calcul à l'aide d'une fonction ou méthode val appliquée à l'état S qui retourne 1 si c'est gagné, 0 si c'est perdu et 1/2 si c'est ni gagné ni perdu. Le choix de cette évaluation s'apparente à une probabilité.

Puis on utilisera des opérations standard sur les listes que l'on décrira au moment voulu.

S : Etat du jeu.
list(S) : Liste des actions possibles exhaustives et exclusives à partir de l'état S.
A(S) : Etat du jeu obtenu à partir de l'état S après l'exécution de l'action A.
val(S) : Valeur du jeu S (1 : gagné, ½ : ni gagné ni perdu, 0 : perdu)

Selon la programmation orientée objet, on pourra écrire S.list au lieu de list(S) et S.val au lieu de val(S). De même on pourra écrire S.act(A) au lieu de A(S).

La liste des actions possibles d'un joueur ne doit jamais être vide pour ne pas bloquer le jeu. (Dans les jeux où il est possible de passer, passer constitue une action.)

Les algorithmes de recherche vont parcourir le graphe du jeu selon différentes stratégies pour essayer de trouver un chemin aboutissant à un état gagnant. Ils pourront par la suite optimiser ce chemin pour en trouver un plus court, et dans le cas ou il ne trouve pas de chemin aboutissant à un état gagnant, optimiser un chemin le plus long possible avant de tomber sur un état perdant.

Pour programmer nos algorithmes, nous utiliserons le langage Ruby, un langage pure object avec tout le sucre syntaxique nécessaire pour le rendre agréable, un langage libre, open source et en vogue.

Les différentes prima-recherches

Ce pose alors la question de savoir quels sont les algorithmes de recherche les plus simples. Est-il possible d'explorer toutes les premières constructions d'algoritmes possibles ?. Qu'elle démarche nous permettrait-elle d'explorer de façon exhaustive toutes ses constructions ?

Les plus simples algorithme n'effectuent pas de recherche, et détermine l'action à faire selon l'état en cours et selon un mécanisme de choix prédéfini. Parmi eux, le plus simple s'appuit sur un mécanisme de choix au hasard.

Puis on considère une première recherche passant en revue tous les choix possibles pour un tour seulement. Et en utilisant une fonction prédéfinie d'évaluation de l'état, l'algorithme choisie l'action qui aboutie à l'état de plus grande valeur selon cette fonction d'évaluation.

..../....

 

Fil d'ariane :

On classifie les jeux selon des critères de complexité et de ressource spécifiques à certaines opérations jugées fondamentales. Et la première opération qui vient à l'esprit est de déterminer si l'on a déjà exploré un état pour éviter de tourner en rond. Cela peut se faire en mémorisant les états explorés. Mais cette méthode limite le nombre d'états explorés Ne en fonction de la taille des états Te et de la taille de la mémoire Tm. Nous avons la condition Ne*Te<Tm. Cela constitue un premier critère de classification des jeux séquentiels finis déterministes à un joueur.

La grandeur de la taille mémoire des états constitue une difficultée. Et-il possible de les désigner par des identifiants de taille mémoire plus petite ?. Cela se peut grâce à une opération informatique fondamentale qu'est le codage, et qui peut permettre de trouver un identifiant de taille mémoire plus petite.

Codage :

On calcule à partir de l'état S un code entier identifiant l'état en question. Le codage est par définition injectif, c'est à dire que deux états distincts doivent produire nécessairement deux codes distincts.

Et ce codage est plus ou moins dense, c'est à dire que les codages des états forment un ensemble d'entiers plus ou moins dispersés, non contigus, et inclus dans {0,1,2,...,N-1}N-1 est le code le plus grand possible correspondant à un état. On apprécie cette densité en prenant connaissance du nombre A d'états possibles et du codage N-1 le plus grand. Le codage est totalement dense lorsque N = A. Un codage totalement dense représente l'identifiant de plus petite taille possible.

Dans la pratique, le codage, même s'il représente un identifiant de taille mémoire plus petite que l'état lui-même, est loin d'être dense et sa taille reste d'un ordre de grandeur plus grand que le nombre d'états qu'il code. Son occupation en mémoire peut encore être trop grande pour pouvoir être stocker en grand nombre. Dans ce cas on a recours à une autre opération informatique fondamentale qu'est le hachage, et qui permet de calculer un presque-identifiant de taille mémoire plus petite.

Le codage d'un état S sera implémenté dans une fonction code(S) ou dans une méthode S.code. Mais pour nos démonstrations, on utilise simplement l'expression mathématique c(S) pour désigner le code de S. Le codage c est une injection quelconque de l'ensemble des états E vers {0,1,2...,N-1}.

Hachage :

A partir d'un état on calcul son code entier parmi {0,1,2...,N-1} puis on effectue un modulo par la taille H de la table de hachage qui est par définition plus petite, H<N, et on obtient ainsi un code de hachage parmi {0,1,2...,H-1}. Mais ce code de hachage n'est pas un identifiant sûr!. C'est un presque-identifiant. Même si la probabilité est trés faible, il se peut que deux états différents aient un même code de hachage. Contrairement au procédé de codage, le procédé de hachage ne garantie pas que deux états différents aient deux codes de hachages différents.

Le hachage produit une perte d'information et permet de mémoriser une variable à N états possibles dans une variable à H états possibles avec le moins de perte d'information possible. Cette propriété n'est pas l'exclusivité de l'appication x--> x mod H. C'est la propriété de surjectivité. Une application f de E vers F est dite surjective si et seulement si pour tout y appartenant à l'ensemble d'arrivé F, il existe une images réciproque x tel que f(x)=y. Autrement f est surjectif ssi f(E) = F.

Mais la notion du "moins de perte d'information possible" est plus subtile. Elle ne s'applique pas uniquement à une valeur mais à une distribution de valeurs

---- 27 mars 2013 ----

 

 

c'est à dire à une suite des valeurs possibles initiales [0,1,2,3...,N-1]. Noter l'usage des [ ] au lieu des { } qui précise que c'est une liste et non en ensemble. Le hachage h va transformer cette liste en [h(0), h(1), h(2), h(3)..., h(N-1)]

davantage encore ce hachage appliqué à un produit une perte d'information et permet de mémoriser une variable à N états possibles dans une variable à H états possibles avec le moins de perte d'information possible.

Le hachage d'un état S sera implémenté informatiquement par l'instruction hach(code(S)) ou par l'appel de méthode S.code.hach, mais pour nos démonstrations on utilisera simplement l'expression mathématique h(c(S)). Le hachage h est une surjection quelconque de {0,1,2...,N-1} vers {0,1,2...,H-1}.

Quantité d'information :

Une variable x désignant un éléments de E, occupe log(|E|) bits au minimum, car si elle possède une taille mémoire plus petite, elle ne pourra pas parcourir tout les éléments de E. Le logarithme est en base 2 car l'unité est le bit.

Une variable A désignant un sous-ensemble de E occupe au minimum |E| bits, un bit par élément présent ou non dans A. Nous avons donc log(|P(E)|) = |E| et |P(E)| = 2|E|, où P(E) est l'ensemble des parties de E.

Une variable W désigant un sous-ensemble de l'ensemble des partie de E occupe au minimum 2|E| bits. Nous avons log(|P(P(E))|) = 2|E|, et donc |P(P(E))| = 2(2|E|).

 

 

---- 25 mars 2013 ----

 

est dite répartie ssi pour tout entier z appartenant à {0,1,2...,H-1} le nombre d'images inverses |h-1(z)| doit toujours être plus grand ou égale à N/H.

répartivité. Une application f de E vers F, où E et F sont des ensembles finies, est dite répartie, si et seulement si pour tout y appartenant à F, le nombre d'images inverses |f-1(y)| est plus grand ou égale à |E|/|F|.

Le mécanisme de codage et de hachage va répartir les A états en les codants préalablement en des entiers compris entre 0 et N-1, puis en les plaçant dans des cases numérotées de 0 à H-1. Ce mécanisme de codage et de hachage est caractérisé par trois nombres : Le nombre A d'états possibles, le nombre N d'entiers intermédiaires à hacher, et la taille H de la table de hachage.

Mais nous n'allons pas considérer que cette seul fonction de hachage. Nous en utiliserons plusieurs distinctes et ces fonctions seront des applications quelconques possèdant cette même propriété recherchée en terme de discernement désignée par le qualificatif "répartie".

c'est à dire, injective et davantage encore, répartie, c'est à dire tel que pour tout entier z appartenant à {0,1,2...,H-1} le nombre d'images inverses |h-1(z)| doit toujours être plus grand ou égale à N/H.

 

 

Ensemble des états explorés

A partir d'un codage des états en {0,1,2...,N-1} il devient possible de mémoriser l'ensemble des états explorés, comme un sous-ensemble. On réserve N bits consécutifs de mémoires initialisés à zéro appelé table. Et à chaque fois que l'on explore un état, on met a 1 le bit dont l'adresse correspond au code de l'état en question. Une telle table peut facilement occuper 1 Go de mémoire et donc fonctionner pour des codages allant jusqu'à N = 8 Milliards.

Si N est trops grand, on utilise un hachage de taille plus petite H, et on réserve pareillement H bits consécutifs de mémoires initialisés à zéro appelé table de hachage. Et à chaque fois que l'on explore un état, on met a 1 le bit dont l'adresse correspond au code de hachage de l'état en question. Ainsi nous pouvons savoir si un état a déjà été exploré, mais l'information n'est pas sûre !. En effet il existe des états distint ayant le même code de hachages. Si on tolère ces erreurs, on obtient une stratégie de recherche qui n'est pas exhaustive, mais qui peut être efficace.

Une telle table de hachage peut facilement occuper 1Giga de mémoire, soit mémoriser 8 Milliards d'états distincts.

Propabilité :

Pour des raisons que l'on n'exposera pas ici, on peut supposer que le hachage est neutre, c'est à dire qu'il met chaque entier compris entre 0 et N-1 dans une case au hasard de 0 à H-1, de probabilité égale, et de façon indépendante. Chaque entier est mis au hasard dans une des H cases de la table de hachage, avec la même probabilité pour chaque case et de façon indépendante entre chaque entiers. La probabilité que le hachage de l'entier x noté h(x) soit égal à z vaut donc :

p(h(x)=z) = 1/H

De même on peut supposer que le codage des états est neutre, c'est à dire qu'il code chaque état par un entier au hasard compris entre 0 et N-1, de probabilité égale, et de façon indépendante. Chaque état est codé au hasard par un entier compris entre 0 et N-1, avec la même probabilité pour chaque entier, et de façon indépendante entre chaque état. La probabilité que le codage de l'état S noté c(S) soit égal à x vaut donc :

p(c(S)=x) = 1/N

Pour définir les pobabilitées formellement, il faut définir l'univers qui contient tous les mondes possibles avec leurs probabilités. L'univers contient toutes les applications hi de {0,1,2...,N-1} vers {0,1,2...,H-1} avec une probabilité égale. Il y en a HN et chacune d'elle peut jouer le rôle d'une fonction de hachage notée de façon générique par h. On note par {0,1,2,...,N-1}{0,1,2,...,H-1} l'ensemble des applications de {0,1,2,...,N-1} vers {0,1,2..H-1}.

Ω = {0,1,2,...,N-1}{0,1,2,...,H-1}       variable d'univers : h

La probabilité p(h(x)=z) est alors définie égale au rapport entre le nombre d'applications hi tel que hi(x)=z, diviser par le nombre totale d'applications HN, et comme le nombre d'applications dont l'image de x est fixée s'avère égale au nombre d'applications de l'ensemble de départ moins l'élément x vers l'ensemble d'arrivé {0,1,2...,H-1}, c'est à dire H(N-1), ce rapport est égal à 1/H.

Mais il convient d'introduire aussi les différents codages possibles qui font partie de la loi de probabilité. On concidère un univers équiprobable plus grand, comprenant une variable supplémentaire qu'est le codage c qui peut être égale à n'importe quelle injection ci de l'ensemble des états E vers l'ensemble {0,1,2...,N-1} avec une probabilité égale. Il y en a N!/(N-A)! et chacune d'elle peut jouer le rôle d'une fonction de codage notée de façon générique par c. On note par Injection(E,{0,1,2..N-1}) l'ensemble des injections de E vers {0,1,2..N-1}.

Ω = Injection(E,{0,1,2..N-1}) * {0,1,2,...,N-1}{0,1,2,...,H-1}       variable d'univers : (c, h)

Le produit * étant directe, les variables c et h peuvent se séparer, on peut se projeter dans un univers plus petit Ω = Injection(E,{0,1,2..N-1}) avec comme seul variable d'univers, c. La probabilité p(c(S)=x) est alors définie égale au rapport entre le nombre d'injections ci tel que ci(S)=x, diviser par le nombre totale d'injections N!/(N-A)!, et comme le nombre d'injections dont l'image de S est fixée s'avère égale au nombre d'injections de l'ensemble de départ moins l'élément S vers l'ensemble d'arrivé moins l'élément c(S), c'est à dire (N-1)!/(N-1-(A-1))! = (N-1)!/(N-A)!, ce rapport est égal à 1/N.

On concidère un univers équiprobable encore plus grand, comprenant deux variables supplémentaires contenant des états (éléments de E). Les variables de l'univers se nomment u, v, c, h. Pour chaque monde, il existe une valeur de u, v, c, h. Toutes les configuration de valeurs sont envisagées, et sont équiprobables :

Ω = E2 * Injection(E,{0,1,2..N-1}) * {0,1,2,...,N-1}{0,1,2,...,H-1}      variable d'univers : (u, v, c, h)

On peut alors calculer la probabilité que u et v soient égaux sachant que h(c(u))=h(c(v)).

Probabilité des faux-positifs

Dans notre stratégie du fil d'ariane, on teste le code de hachage des états pour vérifier qu'on ne les a pas déjà exploré. Mais le hachage n'étant pas injectif, le teste n'est pas sûr!, il se peut qu'un état soit testé positif c'est à dire reconnu comme déjà exploré alors qu'en fait il ne l'est pas. Ce sont les faux-positifs.

Pour mesurer la fiabilité du teste on calcule dans l'univers Ω la probabilité que u et v soit égaux sachant qu'ils ont même code de hachage h(c(u))=h(c(v)).

p(u=v / h(c(u))=h(c(v))) = p(u=v et h(c(u))=h(c(v))) / p(h(c(u))=h(c(v)))
                                       = p(u=v) / p(h(c(u))=h(c(v)))

Par ailleur nous savons que :

p(u=v) = 1/A

P(h(c(u))=h(c(v)) / c(u)<>c(v) ) = 1/H

P(h(c(u))=h(c(v)) / u<>v ) = 1/H   (car c étant injectif, on a u<>v  <=>  c(u)<>c(v) )

P(h(c(u))=h(c(v)) / u<>v ) = P(h(c(u))=h(c(v)) et u<>v ) / P(u<>v)

P(h(c(u))=h(c(v)) et u<>v ) = P(h(c(u))=h(c(v)) / u<>v )* P(u<>v)
                                             = (1/H) * (1 - P(u=v))
                                             = (1/H) * (1 - 1/A)

Donc en reprenant le calcul précédement :

p(u=v / h(c(u))=h(c(v))) = p(u=v et h(c(u))=h(c(v))) / p(h(c(u))=h(c(v)))
                                       = p(u=v) / p(h(c(u))=h(c(v)))
                                       = p(u=v) / (h(c(u))=h(c(v)) et u=v) + p(h(c(u))=h(c(v)) et u<>v))
                                       = p(u=v) / (p(u=v) + p(h(c(u))=h(c(v)) et u<>v))
                                       = (1/A) / (1/A + (1/H) * (1 - 1/A))
                                       = 1 / (1 + (A - 1) / H)

Conclusion lorsqu'il y a A états possibles et que l'on choisie une table de hachage de taille H, la propabilité que deux états de même code de hachage soit égaux vaut 1/(1+(A-1)/H). Et la probabilité que cela soit un faux positif vaut 1- 1/(1+(A-1)/H) = 1/(1+H/(A-1)).

H/(A-1)
p(u=v / h(c(u))=h(c(v)))
1
.50
21
.66
22
.80
23
.89
24
.94
25
.97
26
.98
27
.99
28
.996
29
.998
210
.999
H/(A-1)
p(u=v / h(c(u))=h(c(v)))
1
.50
2-1
.33
2-2
.20
2-3
.11
2-4
.06
2-5
.03
2-6
.02
2-7
.01
2-8
.004
2-9
.002
2-10
.001
Michel Van Caneghem, "Table de hachage, dictionnaire et un peu de probabilité", cours, 2002

 

Exemples simples de recheche

En mémorisant les états explorés

En mémorisant l'ensemble des codes des états explorés

En mémorisant l'ensemble des codes de hachage des états explorés

 

 


Dominique Mabboux-Stromberg

 

 

 

 

 

 

 

 

 

 

On code les états {0,1,2...,A} avec la fonction code suivante :

def code(x) {1+x+10*x³}

On hache avec la fonction de hachage suivante

def hach(x) {x mod H}

Puis on génère des couples d'états au hasard, on calcule leur code de hachage, et s'ils sont égaux, on teste si les états sont égaux et on comptabilise.

A=20
H=(A-1)


vp=0      // vrai positif
fp=0      // faux positif


1000000.times do

  u = rand(A)
v = rand(A) if hach(code(u))==hach(code(v)) then if u==v then vp+=1 else fp+=1 end end end p( vp.to_f / (vp+fp) )