rozproszone przycinanie alfa beta

19

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
2
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,

Odpowiedzi:

3

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.

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