Discussion :

[euroval]

Je suis plutot débutant en informatique, mais récemment, j'ai essayé d'écrire un programme d'échecs en caml, avec algorithme minimax et élagage alpha-béta. Le programme semble marcher comme sur des roulettes mais, problème : quand je le lance pour une profondeur de recherche un peu plus élevé, soit en pratique si je le lance sur un truc où il va devoir travailler plus de 20 secondes, il s'arrête de manière inexpliquée au milieu des calculs (ça se voit quand je fait #trace). D'où je me demande s'il n'y a pas une surcharge de la mémoire, ou quelque chose comme ça. Ne me connaissant pas trop en gestion de la mémoire et autre (j'ai juste suivi les cours d'informatiques de mp), j'aimerais savoir si quelqu'un comprend quel doit être le problème, et, si possible, saurait y remédier.
Merci d'avance.

[gasche]

Ça peut être un "stack overflow" lié à un dépassement de la limite de la pile d'appel, si tu as une fonction récursive qui s'appelle beaucoup en position non-terminale.
Ça peut aussi tout simplement être un problème de mémoire (tu alloues trop de mémoire et ton ordinateur tue le programme).
Normalement Caml devrait renvoyer une exception qui t'informe de la cause du problème. Tu es sûr qu'il ne dit rien ?
Dans les deux cas, une modification du code pourrait aider à régler le problème; difficile à dire sans ton code.

Si tu fais des programmes gourmands en ressource, je te conseille d'utiliser plutôt Objective Caml (je suppose que tu utilises Caml Light) qui possède un compilateur natif plus performant (je dirais de 5x à 100x plus rapide en général) et de meilleurs outils d'instrumentation pour repérer les problèmes de performance.

[euroval]

En fait j'utilise déja ocaml, par contre je ne connais pas ses "outils d'instrumentation".

En fait, j'ai essayé de voir si le programme continuait à marcher en utilisant l'instruction "top" sous linux, et il semble que cela soit le cas. C'est bizarre, car j'ai beau pacienter, il ne me renvoie rien (en tout cas pas dans un temps comparables avec celui avec lequel il me renvoie quelque chose pour d'autres données en entrée). Et je confirme qu'il ne me renvoie pas de "stack overflow". Autre bizarrerie : quand je "trace" le programme, je vois des centaine d'appels récursifs défiler, ce qui est normal au vu de mon programme, mais au bout d'un moment, il s'arrête soudainement...

Si vous voulez essayer, vous pouvez aller à http://admin.ordi.euroval.operaunite...aring/content/,
il s'agit du dossier presentation.ml (à télécharger et à ouvrir avec un programme adapté, sinon vous verrez tous les programmes collés sans dessus dessous). Le problème survient par exemple lorsque je lance

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

# negamax [] position1 3;;

ou si je lance negamax sur d'autres positions avec des profondeurs plus importantes. Par contre, quand je lance par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

# negamax [] position4 3;;

où le nombre de positions à analyser est un peu inférieur, il me répond en quelques secondes...

En tout cas, merci pour votre aide, et désolé de mettre tant de temps à répondre, je suis assez pris en ce moment (concours d'entrée aux grandes écoles oblige)

[gasche]

Désolé de ne pas avoir regardé plus tôt. Maintenant tes sources ne sont plus en ligne, donc difficile de faire quoi que ce soit.

Je pense qu'il pourrait s'avoir d'un excès de consommation mémoire. Quand tu dis que le programme s'arrête soudainement, je ne comprends pas très bien s'il termine, ou s'il se "fige" en continuant à tourner en arrière-plan (ce qui pourrait arriver dans le cas d'une boucle infinie).

Bonne chance pour les concours.

[euroval]

En fait, le programme ne s'arrête pas, mais par contre il ne renvoie jamais rien. Et, quand je tape

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

#trace negamax;;

et que je le relance, je vois défiler tous les appels récursifs, mais au bout de quelques temps, plus rien ne défile, ça s'arrête, sans toutefois que le programme ne me renvoie quelque chose. Il semble toutefois que le programme continue à marcher en arrière plan, mais c'est bizarre, car j'ai beau attendre, il ne me renvoie jamais rien, et je n'ai pas l'impression de l'avoir lancé dans une boucle infinie.
Je l'ai mis sur http://www.upndl.com/partage/, c'est le fichier "presentation.ml', mais je crois qu'il faut aussi s'inscrire pour y accéder (c'est gratuit). Il me fait le coup par exemple quand je tape

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

negamax [] position1 3;;

Merci pour votreaide

[aubanel]

Tu peux essayer de tracer différents paramètres de ton programme au cours de son execution, en utilisant par exemple des print_endline.
Par exemple, essaye d'afficher ta profondeur d'execution, les principales valuers de tes fonctions récursives, etc.
En analysant ces traces, tu pourras sûrement complrendre ce qui ne fonctionne pas dans ton programme (récursivité non terminale, boucle infinie, mauvais algo, etc.)
C'est très "low tech" mais je n'ai rien trouvé de plus efficace.

[ceciestunpseudo]

C'est toujours difficile de répondre sans les sources.
Pourrais-tu au moins fournir ici la fonction negamax en cause ? et éventuellement les fonctions que negamax appelle ?