élagage alpha bêta distribué

Je recherche un algorithme efficace qui me permette de traiter l'arbre de recherche minimax pour les échecs avec un élagage alpha-bêta sur une architecture distribuée. Les algorithmes que j'ai trouvés (PVS, YBWC, DTS voir ci-dessous) sont tous assez anciens (1990 étant le dernier). Je suppose qu'il y a eu depuis de nombreuses avancées importantes. Quelle est la norme actuelle dans ce domaine?

Veuillez également me signaler l'explication d'un idiot sur le DTS car je ne peux pas le comprendre dans les documents de recherche que j'ai lus.

Les algorithmes mentionnés ci-dessus:

PVS: fractionnement de variation de principe
YBWC: Concept d'attente pour les jeunes frères
DTS: division dynamique des arbres

sont tous discutés ici .

algorithms distributed-systems board-games filaire
la source

Peut-être que c'est une lecture intéressante: chessbase.com/newsdetail.asp?newsid=8047

Alex ten Brink

Eh bien, c'est un problème (parallélisant la recherche minimax ou l'une de ses variantes) particulièrement difficile. Dans un article publié cette année par Richard Korf intitulé "Les défis de la recherche en recherche combinatoire", on peut lire ce qui suit: "[...] la recherche minimax avec élagage alpha-bêta a été notoirement difficile à paralléliser" Je doute sincèrement il y a un algorithme qui le rend toujours efficace ...

Carlos Linares López

Donc, étant donné que je ne suis qu'un très humble étudiant en informatique du 4e semestre, devrais-je opter pour un algorithme sérialisé ou devrais-je m'attendre à une accélération sub-linéaire acceptable?

filaire

Désolé pour le retard dans ma réponse, cela est passé complètement inaperçu dans ma boîte de réception. En fait, je m'attends à ce que les économies finales dépendent complètement de la distribution des scores attribués par votre fonction d'évaluation aux feuilles de l'arbre de recherche. En général, il n'y a aucune garantie qu'un algorithme de recherche distribué fonctionnera nettement mieux qu'un algorithme de recherche alpha-bêta sérialisé. Ainsi, j'opterais certainement pour une version sérialisée de celui-ci en essayant autant d'améliorations que possible (commandes de mouvements, tables de transposition, etc.)

Carlos Linares López

J'ai eu un certain succès avec l'alpha-bêta parallèle (essentiellement comme décrit sur la page wiki à laquelle vous avez lié).

Jeremy List

Réponses:

oui, la théorie a avancé de manière significative et quelque peu grâce à la littérature sur l'analyse des échecs et aux techniques générales de programmation parallèle. voici quelques refs plus récents sur l'élagage alpha beta (d'échecs) sur des clusters distribués / parallélisme. certaines des premières publications d'échecs en informatique distribuée datent d'avant de nombreux modèles de conception parallèle de base et peuvent être conceptualisées dans ce cadre.

Algorithme alpha-bêta parallèle sur le GPU / Strnad, Guid (2011)
Recherche alpha-bêta parallèle sur les multiprocesseurs à mémoire partagée / Manohararajah (2001) 98pp!
Paralléliser un programme d'échecs simple / Greskamp, 2003
Élagage parallèle alpha-bêta des arbres de décision de jeu: une mise en œuvre des échecs / Steele 1999
Est-il possible d'exécuter une recherche Minimax avec Alpha-Beta Pruning en parallèle avec OpenMP? (stackoverflow)
L'algorithme de recherche d'arbre parallèle haute performance DTS (Hyatt 1994)

L'idée de base derrière DTS est que les arbres de recherche sont répartis entre les nœuds de calcul en fonction de la complexité de déplacement / disposition. les processeurs inutilisés qui "finissent tôt" peuvent faire un travail supplémentaire au-delà d'une allocation initiale qui peut être distribuée aussi uniformément que possible au départ mais qui s'avérera inégale. il s'agit donc essentiellement d'une sorte de file d'attente «d' équilibrage de charge» et de «producteur / consommateur» , ou également similaire à la planification des travaux.

Ce processeur inactif diffuse (en utilisant la mémoire partagée) qu'il est inactif et est disponible pour "aider" tout autre processeur à terminer la recherche dans son arborescence. Les processeurs occupés collectent les données "d'état de l'arborescence" et les stockent dans la mémoire partagée pour que le processeur inactif les examine. Ce processeur inactif analyse ces données et décide lequel (le cas échéant) des processeurs occupés semble avoir une arborescence suffisamment compliquée pour être efficace pour faciliter la recherche. Si une telle position est trouvée, le processeur inactif en informe le processeur qui possède ce nœud et ils "joignent" leurs forces.

vzn
la source