<f...@g...SKASUJ-TO.pl> napisał(a):

> M.M. <m...@g...SKASUJ-TO.pl> napisał(a):
>
> > <f...@g...SKASUJ-TO.pl> napisał(a):
> >
> > > no tez w miare ciekawe; czytales to i kojarzysz co to
> > > robi i gdzie? mniejsze od dooma na oko chyba ze dwa razy,
> > > mozesz opowiedziec co tam sie dzieje to tez mozna pogadac
> >
> > Szczegółów nie rozumiem. Ogólnie ten program ma to samo co
> > każdy program do grania w tego typu grę:
> > 1) przeszukiwanie drzewa gry
> > 2) funkcję oceny pozycji
> > 3) książkę debiutową
> > 4) bazę końcówek
> > 5) do tego ma masę technik usprawniających przeszukiwanie drzewa.
> > Pozdrawiam
> >
>
> a wlasnie jak to drzewo jest 'przeszukiwane'?, dla szachow
> to rosnie bardzo szybko nap powiedzmy ze jest 30 mozliwych
> ruchow bialych na to 30 mozliwych ruchow czarnych, po ktorych
> jest 30 mozliwych ruchow bialych (dla dwu tur naprzod robi sie
> ok miliona mozliwosci) ?

Pełne drzewo właśnie tak ma. Zdaje się że współczynnik rozgałęzienia
dla szachów średnio wynosi 25 ruchów na węzeł.

Dokładne ilości węzłów dla tysiąca pozycji przeszukanych na głębokość
pięciu lub sześciu ruchów zebrałem kiedyś na tej stronie:

http://brodacz100.republika.pl/perft.htm

Tak zwane układy FEN są po prawej stronie tabelki. Układy fen można
przekopiować i wkleić do toola na tej stronie:

http://www.ee.unb.ca/cgi-bin/tervo/fen.pl

Po wklejeniu widać szachownicę z rozstawionymi bierkami szachowymi, jest
czytelniej niż zakodowana postać :)

Na stronie z brodacza są dwie kolumny "mem perft". Są w nich wyniki
przeszukiwania dla algorytmu wyposażonego w pewne usprawnienie. Usprawnienie
to polega na tym, że w hash-table zostaje zapamiętana ilość pod-węzłów dla
danego węzła. Jeśli dany węzeł pojawi się znowu, to zamiast czasochłonnego
przeszukiwania następuje szybki odczyt z hash-table.

Przykładowo dla pierwszej pozycji zwykłe przeszukiwanie na sześć ruchów w
głąb trwało 51.58s, a w poddrzewie było 675053594 węzłów. Przy zastosowaniu
spamiętywania w hash-table czas spadł do 6.5 a ilość węzłów jaką algorytm
obliczył jest identyczna. Tak więc w tym konkretnym przypadku dało się
czas skrócić około 8 razy.

Pozdrawiam



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