Discussion :

[PastisBertrand]

Bonjour, je reprends la programmation orientée jeu et mes bons vieux algos de MiniMax/Alphabeta.
Je n'ai que le projet en tête et après avoir relu les fondamentaux de ces deux concepts sur wikipedia il y a une question qui me turlupine, la priorisation (prioritisation?) des coups en fonction de la "vitesse" à laquelle un gain se produit. En substance, je peux avoir deux coups qui mènent au même gain en profondeur disons 5 (moi opp moi opp moi), mais l'un peut se réaliser plus rapidement dans l'arbre que l'autre. Or dans l'algo fondamental, il ne me semble pas que ce soit pris en compte (vu que minimax est un algo où l'on développe le jeu jusqu'à sa profondeur souhaitée, où l'on y évalue les feuilles - il n'y a pas d'évaluation en amont).

Je me fends d'un exemple n'étant à cet instant pas bien sûr d'être limpide

Disons que deux coups jouables, remontés en prof. 1 produisent un gain de 10. La prof. de l'arbre est 5 (on ne se soucie pas ici de alpha-bèta qui n'intervient pas directement). Nommons ces coups A et B, et pour faire simple, on dit que le "10" se gagne en prof. 5 pour A et en prof. 3 pour B (donc, pour B, si on évaluait le coup en prof. 3 on verrait qu'on gagne 10, et en prof. 5 on dit qu'on ne gagne rien de plus - pour A, on dit qu'on ne gagne rien en 3 mais on gagne 10 en prof. 5. Ce sont deux coups symétriques, l'un des deux se gagne plus rapidement).

Disons que sur 3 coups possibles (A:10, B:10, C:7) mon algo ne voit pas la différence entre A et B, et prend le premier, A. Alors que je préfèrerais que cette vitesse de gain soit prise en compte dans l'algo et que B soit préféré.
On pourrait me dire "de toute façon les deux mènent à 10" - oui mais, il vaut mieux s'assurer d'un gain le plus tôt possible (il me semble qu'on doit pouvoir montrer que pour deux coups menant à un même gain mais à différentes profondeurs le "moins profond" prime pour la raison que il a été évalué des réponses en profondeurs supérieures qui ne menacent pas ce gain, alors que le même gain en prof. max pourrait être rapidement menacé au coup suivant (non vu par l'algo) par exemple) - et puis, si le gain est par ex. la partie tout court, il vaut mieux que cela se produise le plus tôt possible...

Je suppose que cette question doit être classique, mais je ne vois pas de réponse sur Google (je dois probablement mal formuler la recherche).

Quelqu'un a-t'il eu à faire face à ce problème? La réponse à cela est-elle une évaluation suplémentaire dans les couches inférieures pour donner légèrement plus de poids à un coup rapide? Quelle est la meilleure stratégie?

[SpiceGuid]

La réponse est dans la question. Minimax n'est pas en général un algorithme pratiquable, il faut davantage le considérer comme un modèle idéal, une référence pour des algos plus pratiquables que lui, c'est-à-dire qui renverront un résultat pratiquement aussi bon dans un temps bien plus raisonnable.

Comme tu l'as remarqué Alpha-béta a justement pour but de ne pas explorer plus profond que strictement nécessaire pour obtenir le score attendu.
De plus il est conseillé de trier les positions dans l'ordre décroissant (par iterative deepening) afin d'explorer les meilleures positions d'abord pour élaguer au mieux. De cette façon on explore pas plus large que strictement nécessaire pour obtenir le score attendu.

[PastisBertrand]

Heu... merci. Je comprends que MiniMax est à adapter à un problème.
Par contre tu ne réponds à la question du post: en substance, comment prendre en compte "la vitesse" d'un gain (voir 1er post pour plus de précisions sur cette notion)?

(j'avais pris soin d'élaguer "alpha-béta" de la question pour être sûr que ce ne soit pas compris comme un objet du problème, mais apparemment ça n'a pas suffi...)

[SpiceGuid]

donc, pour B, si on évaluait le coup en prof. 3 on verrait qu'on gagne 10, et en prof. 5 on dit qu'on ne gagne rien de plus - pour A, on dit qu'on ne gagne rien en 3 mais on gagne 10 en prof. 5.

Dans ce cas les coups se valent, ce qui change c'est la vitesse de convergence de la fonction d'évaluation, elle se trompait plus dans le cas de A que dans le cas de B.
La fonction d'évaluation ne dit pas la vérité. Si la fonction d'évaluation disait la valeur véritable des coups il n'y aurait pas besoin d'exploration.
Il n'y a pas de notion de "vitesse" de gain, la valeur du coup est sa valeur au moment où on le joue, cette valeur est à l'horizon de l'exploration de l'arbre de jeu. Le but est d'en obtenir une approximation acceptable dans un temps acceptable.