rozproszone przycinanie alfa beta

Szukam wydajnego algorytmu, który pozwala mi przetwarzać drzewo wyszukiwania minimax dla szachów z przycinaniem alfa-beta w architekturze rozproszonej. Algorytmy, które znalazłem (PVS, YBWC, DTS, patrz poniżej) są dość stare (najpóźniej 1990). Zakładam, że od tego czasu nastąpiło wiele istotnych postępów. Jaki jest obecny standard w tej dziedzinie?

Proszę również wskazać mi idiotyczne wyjaśnienie DTS, ponieważ nie rozumiem tego z artykułów naukowych, które przeczytałem.

Algorytmy wspomniane powyżej:

PVS: Zasada podziału wariacji
YBWC: Young Brothers Wait Concept
DTS: Dynamiczne dzielenie drzew

wszystkie są omówione tutaj .

algorithms distributed-systems board-games

— okabluj
źródło

Może to ciekawa lektura: chessbase.com/newsdetail.asp?newsid=8047

— Alex ten Brink

Jest to problem szczególnie trudny (równoległe wyszukiwanie minimax lub którykolwiek z jego wariantów). W artykule opublikowanym w tym roku przez Richarda Korfa zatytułowanym „Wyzwania badawcze w wyszukiwaniu kombinatorycznym” można przeczytać: „[...] wyszukiwanie minimax z przycinaniem alfa-beta było niezwykle trudne do zrównoleglenia” Szczerze wątpię istnieje algorytm, który sprawia, że zawsze jest wydajnie ...

— Carlos Linares López

Biorąc pod uwagę, że jestem tylko bardzo skromnym studentem informatyki w 4. semestrze, czy powinienem skorzystać z serializowanego algorytmu, czy powinienem spodziewać się akceptowalnego przyspieszenia sublinearnego?

— okabluj

Przepraszam za opóźnienie w odpowiedzi, minęło to zupełnie niezauważone w mojej skrzynce odbiorczej. W rzeczywistości spodziewałbym się, że ostateczne oszczędności całkowicie zależą od rozkładu wyników przypisanych przez twoją funkcję oceny do liści drzewa wyszukiwania. Zasadniczo nie ma gwarancji, że algorytm wyszukiwania rozproszonego będzie działał znacznie lepiej niż szeregowy algorytm wyszukiwania alfa-beta. Zdecydowanie wybrałbym jego wersję seryjną, próbując tylu udoskonaleń, jak to możliwe (zamawianie ruchów, tabele transpozycji itp.)

— Carlos Linares López

Odniosłem pewien sukces z równoległą wersją alfa-beta (w zasadzie tak, jak opisano na stronie wiki, do której linkujesz).

— Jeremy List,

tak, teoria znacznie się rozwinęła, zarówno ze względu na literaturę analizy szachów, jak i ogólne techniki programowania równoległego. oto kilka nowszych odniesień do (szachy) przycinania wersji beta alfa nad rozproszonymi klastrami / równoległością. także niektóre z wczesnych rozproszonych literatury komputerowej szachowej wyprzedzają wiele podstawowych równoległych wzorców projektowych i mogą być konceptualizowane w ramach tego środowiska.

Równoległy algorytm alfa-beta na GPU / Strnad, Guid (2011)
Parallel Alpha-Beta Search on Shared Memory Multiprocessors / Manohararajah (2001) 98pp!
Równoległy prosty program szachowy / Greskamp, 2003
Równoległe przycinanie alfa-beta drzew decyzyjnych w grze: implementacja szachowa / Steele 1999
Czy można uruchomić wyszukiwanie Minimax z przycinaniem alfa-beta równolegle z OpenMP? (przepełnienie stosu)
Wysokowydajny algorytm wyszukiwania drzewa równoległego DTS (Hyatt 1994)

podstawową ideą DTS jest to, że drzewa wyszukiwania są rozdzielane między węzły obliczeniowe w oparciu o złożoność ruchu / układu. nieużywane procesory, które „kończą się wcześnie”, mogą wykonać dodatkową pracę poza początkowym przydziałem, który może być początkowo rozłożony możliwie równomiernie, ale okaże się nierównomierny. stąd jest to w zasadzie rodzaj kolejki „równoważenia obciążenia” i „producenta / konsumenta” lub podobny do planowania zadań.

Ten bezczynny procesor rozgłasza (używając pamięci współdzielonej), że jest bezczynny i jest dostępny, aby „pomóc” każdemu innemu procesorowi w zakończeniu wyszukiwania jego drzewa. Zajęte procesory zbierają dane „stanu drzewa” i przechowują je w pamięci współużytkowanej w celu zbadania bezczynnego procesora. Ten bezczynny procesor analizuje te dane i decyduje, który (jeśli w ogóle) z zajętych procesorów wydaje się mieć drzewo, które jest na tyle skomplikowane, że byłoby pomocne w wyszukiwaniu. Jeśli taka pozycja zostanie znaleziona, bezczynny procesor informuje procesor, który jest właścicielem tego węzła, i łączą siły.

— vzn
źródło