Czy głębokość (liczba warstw) nadal ma znaczenie, gdy jest wystarczająco wysoka?

To nie jest prawdziwe, wyobraź sobie, że tak się dzieje.

Computer Ajest superkomputerem. Może obliczyć 30 warstw na głębokość w ciągu 20 sekund.

Computer Bjest superkomputerem. Może obliczyć 15 warstw na głębokość w ciągu 20 sekund.

Grają ze sobą w szachy.

Czy te 15 głębokości naprawdę mają znaczenie? Sądzę, że w obrębie tych 15 głębokości może istnieć tryliony sposobów na ucieczkę przed matą lub złapanie ważnego elementu. Jasne, Computer Awie więcej. Ale Computer Bjest w stanie przewidzieć przyszłość także dość daleko, moim zdaniem, wystarczająco daleko, aby bronić się naprawdę dobrze.

Tak, te 15 głębokości mają ogromne znaczenie.

Rozważ tę pozycję, która wystąpiła w Nieśmiertelnej grze Kasparowa przeciwko Topałowowi.

Testowałem tę pozycję z kilkoma silnikami. Niektóre silniki na głębokości 15 nie wykryły, że 24 ... cxd4 to przegrywający ruch i uważały, że wygrywa. Te same silniki, na większej głębokości, wykonały prawidłowy ruch 24 ... Kb6!

Na przykład nawet silnik tak potężny jak Sztokfisz 4 początkowo na głębokości 21 uważa, że ​​ruch przegrywający 24 ... cxd4 jest poprawny.

Stockfish DD 64 SSE4.2: 24...cxd4 25. Re7+ Kb6 26. Qxd4+ Kxa5 27. Qc3+ Kb6 
28. Qd4+ Qc5 29. Qxf6+ Bc6 30.Qxc6+ Qxc6 31. dxc6 Rd1+ 32. Ka2 f5 33. c7 Rc8 
34. Rxh7 Rxc7 35. Rh6 Rc6 36. g4 f4 37. g5 Rd2 38. c3 Rxc3 39. Rxg6+ Kc5 
40. Bg4 Rcc2 41. Rxa6 Rxb2+ 42. Ka1 Rbc2 43. Kb1 
(-1.45/21)

Ten sam silnik, gdy jest włączony na nieco większej głębokości, pokazuje 24 ... Kb6 prawidłowego ruchu.

Stockfish DD 64 SSE4.2: 24...Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 
28. axb4 Rhe8 29. Rxe8 Rxe8 30. Nb3 Re1+ 31. Kb2 Re2 32. Rxh7 Nxb4 
33. Kc3 Nd5+ 34. Kd3 Rxh2 35. Rh4 Ne7 36. Nd4 Nc6 37. Nxc6 Bxc6 38. f4 Kc5 
39. Be6 Rxh4 40. gxh4 Bd5 41. f5 gxf5 42. Bxf5 a5
(-0.78/26)

Fritz 11 SE, na głębokości 15, również zawiódł. Ale znalazł właściwy ruch na głębokości 16!

Fritz 11 SE: 24... cxd4 25. Qxd4+ Qb6 26. Re7+ Nd7 27. Qe5 f6 28. Qc3 Qg1+ 
29. Ka2 Bxd5+ 30. Nb3 f5 31. Qc7+ Ka8 32. Rxd7 Rxd7 33. Qxd7 Bxf3 34. Qd6 Qa7  
(-1.44/15) 

Fritz 11 SE: 24... Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 28. axb4 Nxb4 
29. Nb3 Bd5 30. Rf6+ Nc6 31. Nd4 Rdf8 32. Rd6 Kc5 33. Rxc6+ Bxc6 34. Ne6+ Kd6 
35. Nxf8 
(-0.59/16)

Weź również pod uwagę ten niesamowity problem, jak pozycja, którą tu znalazłem .

Sztokfisz nie był w stanie znaleźć zwycięskiej linii 1. Be2 +! do głębokości 31 i do tej pory uważał, że to zły ruch. Tutaj demonstruję zwycięstwo. Chodzi o to, że czarne są w zugswang z powodu zagrożeń ze strony partnera i muszą albo oddać królową, albo poruszyć pionka, co pozwoli białym stworzyć pionka i wygrać.

Oto dziennik silnika ze Sztokfiszy 4. Jak widać, wykrywa on, że 1. Be2 + wygrywa, tylko na głębokości 31!

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2.Bc4 c6 3. Ne2 Qf6 4. Kg2 Kg4 5. Nf4 Qxd4 
6. Bd3 Qe3 7. Be2+ Kf5 8. Bf3 Qd2+ 9. Kh3 Qxb4 10. e7 Qe1 11. Ne2 Qf1+ 12. Kh2 Qf2+
13. Kh3 Qe3 (-1.05/22) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. Bxa6 Qxe6 5. Bd3+ Kf6 
6. Nf4 Qe1 7. d5 Qxb4 8. dxc6 Qxc5 9. Be4 Ke7 10. c7 Kd7 11. Nd5 Kd6 12. Kh3 Qc4 
13. Bg2 Qg4+ 14. Kh2 Qc8 15. Be4 (-1.15/26) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. d5 cxd5 5. Bxd5 Qb2 
6. Bc4 Kf6 (-1.01/28) 

Stockfish DD 64 SSE4.2:  1. Be2+ Kf5 2. Nd5 Qxe6 3. Bd3+ Kg4 4. Be4 Qh6 5. Nf4 Qf6 
6. Nd3 Qxd4 7. c6 Qxe4 8. Nf2+ Kf3 9. Nxe4 Kxe4 10. Kg2 Ke5 11. Kf3 Kf5 12. g4+ Kf6
13. gxh5 Kg7 14. Kf4 Kf6 15. h6 Kg6 16. h5+ Kh7 17. Kg5 Kg8 18. h7+ Kxh7 19. Kf5 Kg7
20. Ke6 Kh6 21. Kd7 Kxh5 22. Kxc7 Kg5 23. Kd7 (6.06/31) 

Zależność między wzrostem wydajności a głębokością wyszukiwania jest od dłuższego czasu aktywnym obszarem badań w społecznościach programistów komputerowych. Istnieje teoria, że ​​zwiększenie głębokości poszukiwań spowodowało zmniejszenie zwrotów siły ... wydawało się to potwierdzone w wynikach eksperymentalnych.

Z mojej perspektywy ma to intuicyjne podstawy. Wyobraź sobie swoje hipotetyczne dopasowanie między dwoma superkomputerami, zaczynając od pozycji tabeli bazowej gry końcowej. Większość wygranych wymuszonych w bazach tabeli ma miejsce na horyzoncie mniejszym niż (na przykład) 50 warstw. Większość pozostałych pozycji jest wylosowanych, tylko niewielka część postanawia wygrać na większej głębokości. Komputer wyszukujący na 100 warstwach miałby ograniczoną przewagę nad komputerem 50 warstwowym, ponieważ (jak wspomniałeś) słabszy program jest w stanie nawigować przez prawie wszystkie linie, które tracą, wszystkie występujące na bardziej ograniczonej głębokości. Program 50-warstwowy miałby znacznie większą przewagę nad programem 25-warstwowym ... podobnie jak program 4-warstwowy miałby jeszcze większą przewagę nad programem 2-warstwowym.

Po raz pierwszy zetknąłem się z tą koncepcją około 15 lat temu w serii artykułów na temat Mrocznej Myśli , eksperymentując w głębokich poszukiwaniach. To świetna lektura, jeśli interesuje Cię szachy komputerowe.

Chociaż nie mogłem znaleźć referencji online, istnieje artykuł z zeszłego roku na ten temat ...

Diogo R. Ferreira (2013). Wpływ głębokości wyszukiwania na siłę gry w szachy. ICGA Journal, tom. 36, nr 2

Pytanie brzmi: czy masz na myśli 15/30 warstw wyczerpujących poszukiwań, czy nominalną głębokość / iterację 15/30 nowoczesnego silnika szachowego, takiego jak Sztokfisz?

Jeśli chodziło ci o to drugie, 15 warstw niekoniecznie wiele znaczy. Nowoczesne silniki szachowe mocno przycinają i redukują ruchy, które są rzekomo złe, więc może się zdarzyć, że poświęcenie, które wydaje się złe na pierwszy rzut oka, na nominalnej głębokości / iteracji 15 jest w rzeczywistości przeszukiwane tylko na głębokość np. 5-10. Na głębokości / iteracji 30 ruch prawdopodobnie nadal jest przeszukiwany tylko na zmniejszonej głębokości, ale wtedy może to być efektywna głębokość 15-20, co może być wystarczające, aby stwierdzić, że poświęcenie jest rzeczywiście dobre, i to zaraz po uruchomieniu silnika odkrywa, że ​​ruch jest obiecujący, zmniejszy redukcję, dzięki czemu ruch zostanie przeszukany na głębokości bliższej do 30 warstw (lub jeszcze głębiej z powodu rozszerzeń i wyszukiwania spoczynku). Więc tak, myślę, że może to coś zmienić, nawet jeśli kombinacja mieści się w nominalnym horyzoncie 15 warstw.

Jeśli miałeś na myśli wyczerpujące wyszukiwanie, to myślę, że silnik o głębokości 15 byłby bardzo silny, pod warunkiem, że ma dobrą funkcję oceny i pewnego rodzaju wyszukiwanie bezruchu (po opuszczeniu węzłów na głębokości 15). Ze względu na malejące zwroty, myślę, że zysk podwajając głębokość byłby znacznie mniejszy niż w przypadku dopasowania dwóch nowoczesnych silników o głębokości 15 do głębokości 30. Ale to oczywiście tylko teoretyczne, ponieważ wyczerpujące poszukiwanie głębokość 15 zajęłaby kilka rzędów wielkości dłużej niż silniki zwykle osiągają głębokość / iteracja 15, więc taki eksperyment byłby możliwy tylko na niższych głębokościach.

FWIW Kiedy ARM był nowy, napisałem zoptymalizowany wyczerpujący program wyszukiwania ARM z oceną pozycji tylko materialnej po warstwie 1.

Użyłem sztuczek ze zoptymalizowanym kodem maszynowym, iteracyjnego pogłębiania, okienkowania alfa-beta podczas posortowanych ruchów (prawie wszystkie pozycje miały wartość 0, więc uzyskałem prawie optymalne przycinanie alfa-beta) - i tablice skrótów, które zmniejszyły współczynnik rozgałęzienia do znacznie mniejszego niż teoretyczny pierwiastek kwadratowy dla alfa-beta, zwykle około 4 w najgorszej części gry.

Podczas rywalizacji ze standardowymi programami w tym czasie mój program E6P znalazł się w okropnych pozycjach, ale z dodatkową warstwą lub dwoma wyczerpującymi wyszukiwaniem w porównaniu do oprogramowania w tym czasie (tj. Zwykle 6 warstw wyczerpujących + wyszukiwanie ciche w najgorszym etapie, z nawet do 12 warstw, gdy gra się uprościła), wciąż walczył z przegraną, pomimo pewności swoich przeciwników. Prawie wszystkie gry zostały rozstrzygnięte po wielu godzinach, ponieważ programy przeciwne nie mogły wygrać.

Później zoptymalizowałem go dla StrongARM, gdzie został przeniesiony do 10 warstw. Ta wersja mogłaby z łatwością pokonać wszystkich graczy niebędących szachami, chociaż oczywiście brakowało jej świadomości strategicznej, więc zastosowano słynny komentarz: tak, to ruchy szachowe - ale to nie są szachy!

Było to kilka lat temu, ale kusi mnie, by spróbować ponownie wyczerpująco, biorąc pod uwagę bardziej strategiczną ocenę pozycji w warstwie 1 - i z Intel XEON teoretycznie 10 000-100 000 razy szybszym (i 30k razy większą pamięcią tabeli skrótów) niż 4MIPS ARM2 Acorn Archimedes.

Trzeba przyznać, że nie jest to główny nurt, ale zabawa.

Szacuje się, że +1 warstwa + 55..70 przyrost ELO (wiele badań na ten temat)

Sądzę, że w obrębie tych 15 głębokości może istnieć tryliony sposobów na ucieczkę przed matą lub złapanie ważnego elementu.

Chodzi o to, że wszystkie te „biliony” zostały obliczone przez A @ D = 30, a jeśli A wybierze ruch z wygraną eval, oznacza to, że obliczył wszystkie te „biliony” i bez względu na to, który z „bilionów” poruszy odpowiedź przeciwnika - ruch wciąż wygrywa