Simplifier une expression booléenne

[Victor Curie Ismard]

Bonjour à tous et à et toutes.
Je m'appelle Victor, j'ai 17 ans et j'ai trouvé une idée assez intéressante pour programmer un algorithme qui joue au jeu d'échecs. En fait, je voudrais que cet algorithme soit le plus fort possible.
Pour réaliser cet algorithme, je dois coder une fonction qui me permet de simplifier une expression booléenne le plus rapidement possible. C'est un point clé de mon algorithme.
J'ai donc commencé à réfléchir sur un moyen de simplifier les expressions booléennes mais je me suis heurté à un mur : mon procédé est beaucoup trop lent.
En effet, la taille des expressions booléennes sont très conséquentes. Le nombre d'entrées peut atteindre plusieurs millions et le nombres d'entrées distinctes est d'environ 500.
De plus les expressions booléennes que l'algorithme doit manipuler sont "profondes", je m'explique. Quand on entend parler d'expressions booléennes, on pense sûrement à ceci : a.b + b.e.f + a.c.d , or il s'agit plutôt d'expressions comme celle-là avec une multitude de et et de ou imbriqués les uns dans les autres : (a.(b+a.e).(a.e(b+c.f(g+a))+a. d.f.g))+a.f(b.c.d(e.f+g))
Ayant échoué à réalisé moi-même un algorithme qui simplifie ce genres d'expressions, je me suis tourné vers internet mais je n'ai rien trouvé qui puisse me satisfaire.
Je vous demande donc si vous connaissez l'algorithme le plus rapide qui puisse simplifier une expression booléenne.
-----

[Deedee81]

Salut,

mon procédé est beaucoup trop lent.

C'est normal, le problème est NP-Complet. Voir par exemple : https://fr.wikipedia.org/wiki/Probl%C3%A8me_3-SAT
Ce problème de simplification est considéré comme difficile (comprendre "lent" dès que le nombre de variables devient conséquent).

Il y a quand même plus simple pour programmer les échecs (mais bon, là on n'est pas de le bon forum). J'ai déjà fait (et pleins d'autres jeux).

[GBZM]

Bonjour,
As tu vu ça https://en.wikipedia.org/wiki/Quine%...skey_algorithm ou ça https://en.wikipedia.org/wiki/Espres...ogic_minimizer ?

[albanxiii]

Déplacé dans la bonne rubrique (la rubrique logique est réservée à la logique mathématique)

[A voir en vidéo sur Futura]

[Deedee81]

Salut,

Tiens Victor, une question m'est venue en tête. Tu dis que ton procédé est beaucoup trop lent. Mais combien de temps ça prend ? Parce que si c'est lent mais acceptable au moins pour des essais, il serait déjà intéressant de faire des essais de partie contre ton programme (toi ou quelqu'un d'autre, il vaut mieux un fort joueur. Pas moi Je joue pas mal mais on ne peut pas me classer dans les forts joueurs). Cela me semble important car des tentatives généraliste de ce genre ont déjà été tentées, je m'y suis intéressé à l'époque où je programmais des jeux et où je m'intéressais aux mécanismes d'apprentissage : méthode par amélioration de fonction d'évaluation à grand nombre de variables ou méthode de stockage des valeurs par position par exemple. Et ça donnait des résultats médiocres avec les échecs (ça marche bien avec le morpion, les dames...) et encore moins bien avec le Go. Inutile de se casse la tête si ça ne donne pas les résultats escomptés.

Une autre question : comment détermines-tu les valeurs des 500 variables ? Par examen de la position je suppose ? Déjà, ça, ce n'est pas fort couteux ?