Ktos pytal co to za algorytm.

Alpha-beta. Szachy.

W algorytmie tym analizujemy drzewko gry. Ciecia galezi zaleza od
wartosci zwroconej przez poprzednia galaz. Jesli liczymy na wielu
watkach czesc galezi musi byc liczona przy braku danych z poprzednich,
co powoduje duzo wiekszym drzewkiem do policzenia. Stad az tak duza
nie liniowosc w skalowaniu algorytmu.

do góry

mgk <m...@w...pl> napisał(a):

> Ktos pytal co to za algorytm.
>
> Alpha-beta. Szachy.

Więc mamy do rozwiązania ten sam problem :) Osobiście zrównoleglenie odkładam
na sam koniec, więc może za jakiś rok albo dwa zrobię, gdy już standardowo w
każdym komputerze będzie kilkanaście jednostek.

Zapraszam na forum programowania szachów:
http://tech.groups.yahoo.com/group/progszach/message
s

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

mgk <m...@w...pl> napisał(a):

> Poprostu algorytm ten z natury jest szeregowy. Podzial zadan na kilka
> watkow wymusza liczenie wiecej z tego powodu ze rdzen 2, 3, 4 musza
> zaczynac juz liczyc gdy nie ma jeszcze wynikow z rdzen 1, a te wyniki
> przyspieszyly by dalsze obliczenia. Spadek predkosci wynika z samego
> rozciecia szeregowych zaleznych od siebie obliczen na kilka grup nie
> zaleznych.

Mam jeszcze jedno pytanie, bo pewnie za kilka miesięcy będę musiał też
zrównoleglić alpha-betę: jakiego używasz algorytmu do zrównoleglenia?
Możesz podać pseudokod, albo link? Słyszałem że 4 wątki (oczywiście na
czterech procesorach) pozwalają przeszukać w drzewo gry w szachach o jeden
ruch głębiej. Czy używasz tablicy transpozycji w swoim programie? Tablica
transpozycji musi być globalna (tzn wspólna dla wszystkich wątków). W "jednej
chwili" do jednego elementu tablicy może pisać tylko jeden wątek, więc chyba
tutaj też jest wąskie gardło, gdyż raz na 1-2tys taktów procesora trzeba
obsłużyć sekcję krytyczną.

Ciekawi mnie jeszcze jakby wypadł eksperyment z "gołym" algorytmem mini-max
wyposażonym tylko w tablicę transpozycji. W algorytmie mini-max (w
przeciwienstwie do alpha-beta) wynik poprzednich obliczeń, nie ma wpływu na
następne obliczenia, więc zrównoleglenie powinno być liniowe. Ciekawy jestem
o ile pogorszy się ta liniowość z powodu zastosowania tablicy transpozycji.

Algorytm mini-max jest o wiele prostszy w implementacji od alpha-beta, sądzę
że taki eksperyment byłby bardzo pouczający.

Pozdrawiam serdecznie



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Dziele zadania jedynie w korzeniu. Myslalem o dzieleniu w dowolnym
wezle ale masakrycznie duzo problemow by bylo.
Przy zalozeniu ze rdzeni i tak nie jest duzo (nie wiecej niz 32) to
taki podzial jest ok.

Tablice transpozycyjne, ruchy mordercow, history table testowalem i ze
wspoldzieleniem i osobno. Ze wspoldzieleniem wyszlo troche szybciej.
Potestuj. Moze u Ciebie np wyjsc inaczej. Nie jest to duzo roboty by
sprawdzic oba scenariusze.

Mini-max bylby porazka. Nawet z brakiem czesci informacji alpha-beta
wygeneruje mniej galezi niz mini-max. Alpha beta nigdy nie wygeneruje
wiecej galezi niz mini-max. Jasne ze mozesz sprobowac zrobic
eksperyment dla porownania. Szczegolny przypadek w moim algorytmie to
jakbys mial tyle rdzeni ile jest ruchow w korzeniu. Nawet wtedy bylo
by to szybsze od mini-max, poniewaz o ile te najwieksze galezie nie
komunikuja sie z soba (zaczynajace sie od korzenia), to juz pod
galezie w danej grupie tak i ciecia sa.

do góry

mgk <m...@w...pl> napisał(a):

> Dziele zadania jedynie w korzeniu. Myslalem o dzieleniu w dowolnym
> wezle ale masakrycznie duzo problemow by bylo.
> Przy zalozeniu ze rdzeni i tak nie jest duzo (nie wiecej niz 32) to
> taki podzial jest ok.

Czytałeś o gotowych rozwiązaniach równoległych do alpha-beta? Dużo dobrych
rozwiązań już jest opracowana. Koniecznie zapoznaj się z tym dokumentem:

http://www.cis.uab.edu/hyatt/search.html

Wynika z niego, że do 4 procesorów skaluje się niemal liniowo.

Po tym linkiem jest więcej opracowań nt szachów tego samego autora:
http://www.cis.uab.edu/hyatt/pubs.html

> Tablice transpozycyjne, ruchy mordercow, history table testowalem i ze
> wspoldzieleniem i osobno. Ze wspoldzieleniem wyszlo troche szybciej.
> Potestuj. Moze u Ciebie np wyjsc inaczej. Nie jest to duzo roboty by
> sprawdzic oba scenariusze.

No tak, w każdym programie szachowym te same techniki sprawują się
inaczej. Ja zrównoleglanie zostawiam na sam koniec. Teraz od dwóch miesięcy
badam wpływ null-move na mój program :)

> Mini-max bylby porazka.
Do realnej gry oczywiście że byłaby porażka. Chodziło mi o to, że na
min-max łatwiej jest zaimplementować różne sposoby zrównoleglenia, można
nabyć doświadczenia podczas takich eksperymentów. A po tym podjąć się
trudniejszego wyzwania, czyli implementacji na alpha-beta ze spamiętywaniem.

Pytanie: będziesz na mistrzostwach polski programów szachowych? Ja niestety
nie mogę w tym roku :/

Pytanie: czy wysłałeś już swój program do człowieka od tego serwisu?
http://wbec-ridderkerk.nl/

Prowadzony jest tam ranking programów szachowych:
http://wbec-ridderkerk.nl/html/BayesianElo_ed16.htm

Mój program wywalili bo przez dwa lata nie zrobiłem nowej
ulepszonej wersji :)

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Nie wiem czy bede. A kiedy sa?

Zreszta moj program i tak by nie zajol wysokiego miejsca.

Ja zrownoleglenie tez zostawilem na koniec. Wszystko inne juz
zakodzilem. Ale na serwerach z silnikami szachowymi i tak wypada
ponizej polowy stawki..

do góry

mgk <m...@w...pl> napisał(a):

> Nie wiem czy bede. A kiedy sa?

Z poniższego linka wynika że jutro i pojutrze w Łodzi.
http://mpps.maciej.szmit.info/current.htm

> Zreszta moj program i tak by nie zajol wysokiego miejsca.

Na zawodach jest mało czasu i mało rozgrywek, więc wygrywa
ten który ma więcej szczęścia. Zawody mają inną zaletę: można
porozmawiać z innym ludźmi którzy robią to samo, można dużo
się dowiedzieć.

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Niestety mam dzis egzamin takze odpada. Moze za rok.

Juz bede miec wtedy prace magisterska napisana o silnilach szachowych
i dokoncze moj program. Co prawda tylko kilka rzeczy w GUI mi zostalo.
ALgorytm chyba juz nie ulepsze. Wszystko co mozna juz chyba
zaimplementowane/przetestowane mam.

Za to moj program walczy tutaj:
http://lpps.maciej.szmit.info/

Arabian Knight.

do góry

mgk <m...@w...pl> napisał(a):

> Niestety mam dzis egzamin takze odpada. Moze za rok.
>
> Juz bede miec wtedy prace magisterska napisana o silnilach szachowych
> i dokoncze moj program.
To mam nadzieję że za rok się spotkamy w Łodzi na zawodach i pogadamy
przy desce o programowaniu szachów :)

> Co prawda tylko kilka rzeczy w GUI mi zostalo.
Ja GUI nie robię, całkowicie korzystam z protokołu XBoard.

> ALgorytm chyba juz nie ulepsze.
Ulepszanie algorytmu szachowego to jedno z trudniejszych wyzwań
programistycznych. Niby jest znana lista technik i każda technika
nie wydaje się zbyt trudna w implementacji. Jednak w jednych programach
te techniki z sobą współpracują a w innych gryzą się ze sobą.

Np testowałem dwa sposoby na heurystykę historii. Sposób pierwszy był
dużo lepszy od sposobu drugiego, ale za to drugi współpracował z
heurystyka ruchów morderców, a pierwszy nie.

> Wszystko co mozna juz chyba zaimplementowane/przetestowane mam.
Ciekawe co jest zaimplementowane w programie szachowym o nazwie 'Rybka'.
Program ten bardzo rzadko przegrywa nawet z najlepszymi programami na
świecie, co najwyżej remisuje. Od początku jak powstał miał ogromną
przewagę nad całą światową czołówką. Ma taki dobry algorytm przeszukiwania,
czy taką dobrą funkcję oceniającą? Może jedno i drugie? Nie daje mi to
spać po nocach :)

> Za to moj program walczy tutaj:
> http://lpps.maciej.szmit.info/
>
> Arabian Knight.
Mój też tam jest, zwie się: Bearded :)

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Czyli masz silniejszy progs od mojego.

A co do null move bo mowisz ze testowales. Testowalem to w moim
poprzednim silniku i aktualnym. Niby troche przyspiesza. Czasem prawie
2 razy, czasem nic (zalezy od sytuacji), ale predkosc to nie wszystko.
Pytanie czy ciecia ktore powoduje null move nie pogarszaja na tyle
jakosci gry by to przyspieszenie bylo warte. Zrobilem chyba ze 20
walk. I nie uzyskalem jakiejs przewagi wersji algorytmu z null move
nad wersja bez niego... Wiec zrezygnowalem z tej techniki.

do góry