Jaka jest najwyższa znana dolna granica dla wiązania w N od pozycji początkowej?

Edycja : Wydaje się, że moje pytanie nie było wystarczająco jasne. Pozwólcie, że sformułuję: Jaka jest największa liczba N, dla której możemy świadomie powiedzieć, że „szachy, z pozycji wyjściowej, nie są przymusowym partnerem w przypadku ruchów N”?

Szachy nie są rozwiązane, tzn. Nie wiadomo, jaki wynik z pozycji wyjściowej daje idealna gra.

Jeśli jednak pozycja początkowa jest wygrana dla któregokolwiek gracza, jest to kolega w N. dla niektórych N. Również na przykład, jeśli wiemy na pewno, że pozycja początkowa nie jest wygrywalna w 5 ruchach (dla każdego gracza), 5 to dolna granica dla N.

Z grubsza, jak głębokie jest dogłębne wyszukiwanie w praktyce z pozycji wyjściowej? Jak wysoka jest dolna granica dla N?

Jest to zasadniczo pytanie o złożoność gry w szachy. Pamiętaj, że po skończeniu wiemy, że szachy są determinowane, ale nie wiemy, czy pozycja początkowa to wygrana dla białych, wygrana dla czarnych, czy remis. Złożoność gry w szachy to w przybliżeniu minimalna liczba pozycji, które musimy sprawdzić w drzewie gry, aby określić stan początkowej pozycji. Jest to znane jako liczba Shannona . W wpływowym artykule Programowanie komputera do gry w szachy Shannon oszacował, że liczba Shannona wynosi co najmniej 10 ^ {120). Zauważ, że liczbę cząstek we Wszechświecie szacuje się na 10 ^ (80). Aby odpowiedzieć na pytanie, tak naprawdę chcemy znać wysokośćdrzewa gry, gdy pozycja początkowa zostanie ustalona. Tę wysokość powinniśmy także podzielić przez 2, ponieważ ruch w szachach jest zwykle uważany za ruch biały i czarny. Współczynnik rozgałęzienia drzewa szacuje się na około 30. Zatem możemy przyjąć największy N taki, że 30 ^ (2N) <10 ^ (120).

Odpowiedź. Z tyłu koperty działa N = 40. Tak się składa, że ​​jest to długość przeciętnej gry pomiędzy arcymistrzami (chociaż często rezygnują i nie grają w grę do końca).

Edytować. Morał tej historii jest taki, że próbowałem oszacować górną granicę dla dolnej granicy. Pierwsza część rozumowania Shannona nie ma charakteru kołowego; mówi, że z każdej pozycji jest około 30 legalnych ruchów, a liczba ta jest względnie stała w pierwszej części gry.

Zatem możemy oszacować bieżącą znaną wartość N (która jest naprawdę tym, o co prosisz, nazwijmy to N '), aby była co najwyżej log_30 (C), gdzie C jest równe mocy obliczeniowej istniejącej w historii ludzkości. Nawet przy ostrożnych szacunkach dla C, otrzymujemy coś w rodzaju N 'co najwyżej 20. W praktyce nie sądzę, aby ktokolwiek przeprowadził to obliczenie bardzo daleko od drzewa, ponieważ z góry wiemy, że obliczenia stają się niemożliwe do wykonania po bardzo niewielkiej wysokości i nie trzeba wyczerpująco przeszukiwać drzewa, aby pisać dobre programy szachowe.

Pamiętaj jednak, że zadajesz nieco słabsze pytanie, ponieważ możliwe jest, że początkowym stanem gry jest remis z optymalną grą. Tak więc można uzyskać granice dla N, pisząc program, którego celem było nie tracić tak długo, jak to możliwe. Następnie moglibyśmy zagrać w ten program z najlepszymi programami lub ludzkimi graczami na świecie i zobaczyć, jaka jest długość najkrótszej gry. Ponownie, to nie odpowiada poprawnie na pytanie, ponieważ nie możemy zakładać, że nasi przeciwnicy grają optymalnie . Prawdziwa optymalna gra wymaga pełnej znajomości drzewa gry, ale widzieliśmy, że jest to niemożliwe obliczeniowo. Zatem najlepsze, co możemy obecnie zrobić, to zbliżyć optymalnie grającego przeciwnika z Kasparowem lub bardzo dobrym programem szachowym.

Nie jest prawdą, że pozycji początkowej nie można wygrać w 5 ruchach lub mniej, używając kanonicznej definicji pełnego ruchu w szachach. Można to zrobić w 2 ruchach za pomocą Fool's Mate .

Aby odpowiedzieć na twoje pytanie, siła silnika szachowego zależy od oprogramowania i sprzętu. W 1997 roku Deep Blue było dowodem koncepcji sprzętowej, masywnie równoległego superkomputera zdolnego do oceny 200 milionów ruchów na sekundę ze średnią głębokością 7-8 ruchów. Jednak w 2006 roku Deep Fritz działający na dwurdzeniowym komputerze osobistym uzyskał równoważne wyniki, oceniając jedynie 8 milionów ruchów na sekundę.

Dzisiaj najsilniejszym superkomputerem zastosowanym do szachów jest Blue Gene . Używając 131 000 procesorów, Blue Gene może obliczyć 280 bilionów operacji na sekundę . Chociaż nie ma danych potwierdzających głębokość, na którą można obliczyć Blue Gene, przypuszczam, że byłby dość głęboki. Oczywiście zależy to od czasu działania komputera.

Nie możemy jednak w tym przypadku używać terminu „wyczerpujący” przy „rozwiązywaniu” i otwieraniu. Silnik szachowy nie musi iść na koniec linii, gdy jest pewne, że wynik końcowy jest decydujący. W takim przypadku program zostałby zakończony, gdy stało się jasne, że ocena jednoznacznie popiera jedną ze stron. Jest to znane w informatyce teoretycznej jako przycinanie alfa-beta .

Gdybym musiał dokonać przybliżonej oceny, powiedziałbym, że Blue Gene byłby w stanie obliczyć około 15 do 20 ruchów na sekundę. Chociaż jego sprzęt i oprogramowanie są niezwykle imponujące, musimy pamiętać, że złożoność szachów skaluje się wykładniczo. Według najnowszych szacunków złożoność szachów drzewa gry wynosi co najmniej 10 ^ 123, a liczba potencjalnych pozycji wynosi 10 ^ 46,7.

Zakładając, że wygrana jest kontynuacja z danej pozycji i przy założeniu idealnej gry, oznacza Nto ustaloną i nieograniczoną (w przeciwnym razie nie jest to idealna gra!).

W tym przypadku trzeba naprawdę pracować wstecz - co osiąga Endgame Tablebase

Podstawy wszystkich gier końcowych z maksymalnie sześcioma częściami są dostępne do pobrania za darmo i można je również przeszukiwać za pomocą interfejsów internetowych (patrz zewnętrzne linki poniżej). Baza tabel Nalimov wymaga więcej niż jednego terabajta miejsca do przechowywania

Możesz poszukać tutaj dyskusji. Oczywiście nie powinieneś używać zasady 50 ruchów, ale zgodnie z tym forum, rekord jest do tej pory utrzymywany przez tę pozycję (czarny, aby przenieść):

517 przesuwa się do zwycięskiej pozycji, a 525 do kojarzenia (najlepsza gra po obu stronach). Zobacz tutaj wpis 316. Zatem jest to pozycja wygrywająca bez wygranej w mniej niż 525 ruchach.

Powtórzę też komentarze Bourzutschky'ego: „Mogą istnieć jeszcze głębsze zakończenia dla 7 osób, ale wątpię w to. To, że tak duża głębokość jest wciąż możliwa przy tak dużej sile ognia na planszy, sugeruje, że nawet głębsze zakończenia mogą powstać z 8 częściami, być może w krnnkbbn. To zakończenie może zostać wygenerowane z 64 GB pamięci RAM w ciągu kilku miesięcy na szybkiej maszynie z jednym procesorem i około 5 terabajtami pamięci.

Edycja: Przepraszam, wygląda na to, że źle odczytałem pytanie. Domyślam się, że każdy rozsądny N znajduje się daleko poza horyzontem komputera. Jeśli skonfigurujemy bardzo wydajny komputer do obliczania pozycji początkowej, który jest prawdopodobnie jedynym pewnym X, jaki możemy pokazać, powiedzmy, że mógłby 10 milionów węzłów na sekundę po 10 dniach, moglibyśmy obliczyć 10 * 86400 * 10 ^ 8 węzłów = 8,64 * 10 ^ 13 węzłów. Jeśli założymy, że średnia pozycja w pierwszych 20 ruchach ma około 15 legalnych ruchów (niższa, ponieważ początek ma znacznie mniej, a prawdopodobnie nawet nieco niższa z powodu przycinania alfa-beta), która wynosi tylko około 12 ruchów po 10 dniach (pozycja tylko po ruchu 6 ), więc rozumiesz, dlaczego ten problem jest brzydki. Myślę jednak, że praktyczna gra prawdopodobnie sugeruje o wiele, wiele, wiele większą wartość. JA'

Zignorujmy, że szachy to najprawdopodobniej remis. Musimy rozważyć zasady, zgodnie z którymi gra się w szachy w praktyce. W prawie każdej sytuacji turniejowej obowiązuje zasada 50 ruchów, która stwierdza, że ​​gra jest remisem, jeżeli „ostatnich 50 kolejnych ruchów wykonał każdy gracz bez ruchu pionka i bez schwytania dowolnego elementu”.

Oznacza to, że możemy wykonać 49,5 ruchów na ruch do zdobycia lub pionka. Każdy pionek może poruszać się do 6 razy, a po każdej stronie można schwytać 15 elementów (chociaż jeden element musi pozostać, aby dostarczyć mat), abyśmy mogli ustalić górną granicę liczby ruchów.

Działa to do 49,5 * (8 * 2 * 6 (ruchy pionka) + 29) = 6187,5 Oznacza to, że JEŻELI szachy są wymuszoną wygraną dla białych z zachowaniem zasady 50 ruchów, to dla maksymalnie 6188 ruchów dla białych . Prawdopodobnie mógłbym to nieco obniżyć, nie robiąc zbyt wiele, mówiąc, że wszyscy partnerzy K + kawałek v K, którzy są zmuszeni (tylko Wieża w Queen) są wykonalni w znacznie mniej niż 50 ruchach (myślę, że 16 gra z Nalimovem dla niektóre „trudne” przypadki. Myślę więc, że możemy pewnie odjąć 34 ruchy od tej sumy pewnie dla 6134!

Dlatego: Jeśli szachy są wymuszoną wygraną dla białych z zachowaniem zasady 50 ruchów, to maksymalnie 6134 ruchów.