Le meilleur algorithme améliorant l'alpha-bêta?

8

J'étudie l'IA. Mon professeur nous a donné le code source d'un jeu d'échecs et nous a demandé de l'améliorer. Mon exercice consiste à améliorer l'algorithme alpha / bêta implémenté dans ce jeu. Le programmeur utilise déjà des tables de transposition, MTD (f) avec mémoire alpha / bêta + (MTD (f) est de loin le meilleur algorithme que je connaisse). Existe-t-il un meilleur algorithme pour améliorer la recherche alpha-bêta ou un bon moyen d'implémenter MTD (f) dans le codage d'un jeu?

algorithm ai chess Risa
la source

Réponses:

6

Je répondrai généralement puis plus spécifiquement. D'abord, d'après mon expérience, lorsqu'un professeur demande s'il existe une meilleure solution. Je vais immédiatement dans le livre et cherche des choses que l'auteur a notées comme des lacunes de l'algorithme en question. Deuxièmement, je regarde les optimisations qui m'ont aidé dans le passé.

Pour un algorithme de recherche d'arbre comme l'alpha-bêta, je voudrais ajouter une heuristique qui réduit le nombre de recherches ou le fait rechercher d'abord dans des emplacements plus probables.

J'attribuerais des poids aux chemins qui peuvent être empruntés dans l'arbre en fonction des résultats passés. Si un chemin a abouti à un score plus élevé dans le passé, c'est probablement un bon chemin à reprendre. Donc, pour faire court, ajoutez des heuristiques aux chemins et choisissez de les suivre pour que l'algorithme puisse se terminer plus tôt.

Notez que je ne me souviens pas vraiment de l'algorithme spécifique, juste que c'est un arbre et son approche naïve n'implique pas cette heuristique.

brandon
la source
Je pense que vous parlez de en.wikipedia.org/wiki/Killer_heuristic
Adam
Ça y ressemble. J'ai essayé de donner une réponse moins spécifique pour résoudre les problèmes futurs car l'approche est la même. Le vrai problème n'était pas que risa ne connaît pas l'optimisation alpha-bêta, c'est qu'ils ont besoin de voir l'approche commune des optimisations, en particulier dans l'IA car c'est un domaine très lié à la recherche.
brandon
4

Vous n'avez pas mentionné d'élagage de mouvement nul ou de réduction de mouvement tardif. Ils sont assez faciles à mettre en œuvre et sont encore plus efficaces pour réduire la taille de la recherche que l'élagage alpha-bêta. Les extensions de recherche sont également importantes pour atténuer l'effet d'horizon; la recherche de repos en particulier est un élément très important pour une IA d'échecs.

Kira Chow
la source
1

Examiner l'ordre de déplacement et la recherche de variation de principe

Druzil
la source