Baza danych każdego możliwego ruchu w szachach

14

Wyobraź sobie, że istnieje baza danych szachów z każdym możliwym ruchem i pozycją. Ta baza danych zawiera wszystkie możliwe ruchy od otwarcia do końca gry.

Jeśli grałem intuicyjnie przeciwko silnikowi szachowemu, może przewidzieć, który ruch sprawi, że przegram i wygram.

Oznacza to, że nie ma potrzeby „silnika szachowego”, ponieważ wszystkie możliwe ruchy są już zarejestrowane.

Jeśli taka baza danych istnieje, miałaby następujące zalety:

  • W szybkich grach błyskawicznych silnik szachowy na pewno przegra z bazą danych możliwości przeniesienia szachów.
  • Możemy dokładnie wiedzieć, które otwarcie będzie miało więcej okazji do wygrania z innymi.

Lub gdyby taka baza danych jeszcze nie istniała, moglibyśmy dokonać obliczeń matematycznych wszystkich możliwych ruchów od otwarcia do końca gry.

Czy istniałaby taka baza danych?

Ahmad Azwar Anas
źródło
5
Nie, nie jest to możliwe przy żadnej możliwej do wyobrażenia technologii.
Tony Ennis,
Wędruję chwilę .. I wciąż go nie stworzyłem. Masz rację. Ahaha.
Ahmad Azwar Anas
3
Powodzenia w tworzeniu bazy danych zawierającej więcej bajtów niż atomów we Wszechświecie
David
Hej, jestem nowy w tej społeczności i pochodzę z MathStack. Po prostu podzielmy się informacją, że we Wszechświecie jest mniej atomów niż liczba możliwych gier szachowych w meczu szachowym. Wypróbuj numer Shannon ( youtube.com/watch?v=Km024eldY1A ).
Sujit Bhattacharyya

Odpowiedzi:

32

Uważam, że twoje pytanie sprowadza się zasadniczo do tego, czy możliwe jest całkowite „rozwiązanie” szachów. Wikipedia ma doskonały artykuł na ten temat, który powinien dać ci dobry przegląd.

Podsumowując, liczbę możliwych odmian gry w szachy szacuje się na 10 ^ 120. Jest to zadziwiająco duża liczba, dla porównania weź pod uwagę, że liczbę atomów we obserwowalnym wszechświecie szacuje się na około 10 ^ 80 . Innymi słowy, jeśli używałeś całego obserwowalnego wszechświata jako dysku twardego, nadal musiałbyś przechowywać 10 ^ 40 kombinacji gier szachowych na każdym atomie , aby po prostu przechowywać wszystko. Nie trzeba dodawać, że jest to tak daleko poza naszymi obecnymi i przewidywalnymi technologiami, że większość ludzi uważa to za całkowicie niemożliwe.

Końcowe gry w szachy są znacznie mniej skomplikowane i doszliśmy do punktu, w którym można obliczyć wszystkie możliwe kombinacje dla pięcioelementowych i sześcioczęściowych gier końcowych . Są to zazwyczaj ogromne przedsięwzięcia podejmowane przez badaczy z dostępem do superkomputerów, a powstałe bazy danych gier końcowych są ogromne (rzędu setek terabajtów). Za każdym razem, gdy dodawany jest nowy element, rozmiar i złożoność obliczeń rośnie wykładniczo, co oznacza, że ​​w dającej się przewidzieć przyszłości możemy oczekiwać, że wyniki te wzrosną tylko o kilka elementów.

Daniel B.
źródło
teraz wyobrażam sobie, że istnieją algorytmy reprezentujące stół do gry
końcowej
3
@AhmadAzwarAnas Cóż, myślę, że proste silniki są już używane w silnikach szachowych, a te bardziej kompletne zostaną dodane, jeśli pozwoli na to technologia. Jeśli chodzi o algorytm, myślę, że można „skompresować” końcowy stół do gry, analizując go pod kątem wzorców i uogólniając go na zbiór zasad, które wyraźnie prowadzą do wyniku. Jednak najprawdopodobniej ten zestaw reguł byłby nadal absolutnie ogromny, ponieważ małe różnice (takie jak sprzeciw lub nie) mogą zmienić wynik gry.
Daniel B
@AhmadAzwarAnas właściwie, dlaczego nie tylko algorytm szachowy? w każdej przegranej grze musi być jakiś ruch, prawda? tzn. ruch, przed którym istniała ścieżka, aby nie stracić niezależnie od ruchu przeciwnika, ale po którym to już nie jest prawdą. wtedy „wszystko” algorytm musi zidentyfikować te ruchy, abyś mógł ich uniknąć.
Michael
1
@Michael jest trudniejszy - skąd możesz wiedzieć, że istnieje ścieżka do wygranej bez względu na ruch przeciwnika? w najlepszym razie byłoby tylko 50% czasu, ponieważ jeśli jedna osoba wygrywa, wówczas druga jest zmuszona przegrać. Właściwie pozwala to cofnąć się do pozycji początkowych - aby w dalszej części gry istniała ścieżka, powinna istnieć „ścieżka absolutnej wygranej” - gdybyśmy to wymyślili, to dlaczego ktokolwiek miałby grać w przegrywającym kolorze , wiedząc, że niezależnie od tego, co ruszą, stracą? dlaczego ktokolwiek miałby w ogóle grać w szachy, skoro moglibyśmy to zrobić?
user2813274,
2
+1, ale Twoja analiza jest błędna. Aby przechowywać tabelę, musisz tylko zapisać każdą pozycję, a nie każdą możliwą grę. Shannon szacuje, że istnieje około 10 ^ 43 pozycji , co w porównaniu do około 10 ^ 50 atomów na ziemi . Możesz rozwiązać szachy, zmieniając całą ziemię w komputer .
David Richerby
8

Nie, istnienie takiej bazy danych nie byłoby możliwe. Obliczenie tego wymagałoby niewiarygodnie dużego komputera, a obliczenie zajęłoby tak długo, że komputer nie istniałby wystarczająco długo, aby ukończyć zadanie.

Claude Shannon oszacował, że istnieje około 10 43 możliwych pozycji w szachach, a twoja baza danych musiałaby przechowywać wyniki wszystkich z nich (byłby to w zasadzie 32-osobowy stół ). Szacuje się jednak, że Ziemia zawiera tylko około 10 50 atomów, więc nawet gdybyś mógł zbudować komórkę pamięci z zaledwie 10 000 000 atomów, nadal potrzebujesz komputera wielkości Ziemi tylko do przechowywania wszystkich pozycji.

Ale tak ogromny komputer stwarza duże problemy. Średnica Ziemi wynosi około 12 800 kilometrów, a pokonanie tej odległości zajmuje około 43 ms. Oznacza to, że jeśli cykl zegara trwa dłużej niż 43 ms, to nie tylko masz straszne przekrzywienie zegara, ale różne części komputera nie są nawet w tym samym cyklu zegara. Unikanie tego ogranicza szybkość zegara do około 23,5 Hz (nie GHz lub MHz; tylko Hz). Nawet jeśli możesz w pełni ocenić pozycję w jednym cyklu zegara, oznacza to, że komputer zajmie około 4,3x10 41 sekund. To około 1,4x10 34 lat. To 14 milionów miliardów miliardów lat.

Astrofizycy uważają, że wszechświat będzie wyglądał radykalnie inaczej za 1,4x10 34 lat niż obecnie. Do tego czasu gwiazdy już dawno przestały istnieć, a nawet pierwiastki, które nie są w znaczącym sensie radioaktywne, uległyby znacznemu rozpadowi radioaktywnemu. Nawet protony, które tworzą jądra atomowe, ulegną znacznemu rozpadowi radioaktywnemu. Twój komputer wielkości Ziemi po prostu już nie będzie istniał.

David Richerby
źródło
2
Masz na myśli, że jest szansa?
bpromas
6

Myślę, że odpowiedź Daniela jest doskonała (+1), ale i tak chcę dodać kilka przemyśleń.

Czy 32-częściowy stolik rzeczywiście zastąpiłby silniki szachowe? Odpowiedź jest zdecydowanie nie!

Aby grać w dobre szachy, potrzeba więcej informacji niż to, czy ruch wygrywa, rysuje czy przegrywa. Oczywiście taka baza danych byłaby nie do pokonania, ale nikogo też nie pobiłaby.

Aby grać w szachy silnie, nie wystarczy wybrać ruch bez przegrania na każdym kroku. Z wielu ruchów rysujących w każdej pozycji, tylko kilka wywiera rzeczywistą presję na przeciwnika.

Istniejące silniki szachowe są znacznie wzmocnione dzięki dostępowi do stolików. Ale wraz z rozwojem baz danych czas dostępu stałby się czynnikiem zakazującym na długo przed użyciem każdego atomu we wszechświecie do pamięci ;-).

Myślę więc, że twój wniosek jest po prostu błędny: taka baza danych nigdy by nie przegrała i prawie nigdy nie wygrała. Nie powiedziałoby nam nic o otwarciu, z wyjątkiem tego, że prawie wszystkie są remisami. Prawdopodobnie moglibyśmy opracować nowe algorytmy do wydobywania tej bazy danych i wyciągnąć ciekawe wnioski na temat wszelkiego rodzaju pozycji, ale myślę, że nie zmieniłoby to w żaden sposób świata szachów.

BlindKungFuMaster
źródło
Źle zrozumiałeś, co zawiera baza danych. Każdy możliwy ruch byłby oznaczony jako „Jeśli zagram, mój przeciwnik może wymusić wygraną, co zrobię dalej”, „Jeśli zagram, mogę wymusić wygraną, niezależnie od tego, co zrobi mój przeciwnik” lub „zremisować”. Więc nie grałbyś w „nie przegrane ruchy na każdym kroku”: grałeś wymuszone zwycięstwa na każdym kroku, o ile taki ruch istniał.
David Richerby
1
Cóż, właściwie zrozumiałem dokładnie, co będzie zawierać baza danych… Chciałem podkreślić, że w grach szachowych na wysokim poziomie „Nie ma wygranych wygranych!” na ponad 90% pozycji. Potrzebujesz więcej informacji niż „ten ruch dobiera, a ten ruch przegrywa”, aby dostać się do zwycięskiej pozycji przeciwko porządnemu graczowi.
BlindKungFuMaster,
2
Na przykład: w pozycji początkowej, według wszelkiego prawdopodobieństwa, jedyną informacją w bazie danych byłoby „Wszystkie ruchy losują”. Więc byłbyś całkowicie sam. A jeśli jesteś całkowicie sam, jak zdobyć zwycięską pozycję przeciwko silnemu graczowi? Odpowiedź brzmi: nie. Twoja pozycja będzie się pogarszać do tego stopnia, że ​​będziesz podążał za jedyną linią rysowania.
BlindKungFuMaster,
Nie, to nie w porządku. Zdobycie zwycięskiego ruchu jest banalne. Wystarczy obliczyć wszystkie możliwe ruchy z bieżącej pozycji, sprawdzić wynikowe pozycje na DB i wybrać taki, który wygra lub zremisuje. Z definicji, jeśli twoja obecna pozycja to „wygrywasz”, na następnych pozycjach będzie co najmniej jedna „wygrywasz”; a jeśli twoja obecna pozycja to „remis”, co najmniej jedna z następnych pozycji będzie „remisować” (i być może niektóre „wygrywasz”, jeśli przeciwnik nie gra idealnie).
Ignacio Calvo,
1
Chodzi o to, że obecna pozycja zazwyczaj nie jest „wygrywasz”. Na przykład jest bardzo prawdopodobne, że nie ma wymuszonej wygranej na pozycji wyjściowej.
BlindKungFuMaster
3

Myślę, że kiedyś szachy zostaną rozwiązane. Czemu? Ponieważ, nie tak dawno temu, gra w szachy z komputerem była dziwna i nie do pomyślenia! Jak mógłbyś nauczyć komputer grać w szachy? Zrobili to! (Ponadto pomysł komputera był dziwny ...) Chodzi mi o to, że może wydawać się dziwny, ponieważ nigdy o nim nie słyszeliśmy. To nie jest coś, co możemy sobie łatwo wyobrazić. Ale technologia rozwija się w tempie wykładniczym. Nie zdziwiłbym się, gdyby w niedalekiej przyszłości (ponad 10 lat) to zostało rozwiązane, w takiej czy innej formie.

Ryan Orr
źródło
1
Przeszkodą w rozwiązywaniu szachów jest dosłownie astronomiczna ilość danych, którą trzeba by posortować. Shannon oszacował, że w szachach jest około 10 ^ 43 pozycji i musisz zapisać wynik dla każdej z nich. Aby spojrzeć na to z innej perspektywy, Ziemia zawiera około 10 ^ 50 atomów, więc nawet gdybyś mógł zbudować komórkę pamięci z 10 000 000 atomów, nadal musiałbyś przekonwertować całą Ziemię na bank pamięci, aby zapisać wynik!
David Richerby
1
@DavidRicherby Powiedzmy, że szachy to remis z najlepszą grą. Następnie dla każdego białego ruchu istnieje odpowiednia odpowiedź dla czerni. Do następnego białego ruchu czarny ma również odpowiednią reakcję i tak dalej. Można sobie wyobrazić, że zbudowanie takiego „drzewa rysującego” wymaga dużo mniej niż 10 ^ 43 pozycji.
Dag Oskar Madsen
4
@DagOskarMadsen Tak, możliwe, że przechowywanie drzewa wymagałoby znacznie mniej pamięci (choć wciąż astronomicznej). Jednak obecna technika budowy takich drzew polega na przeprowadzeniu analizy wstecznej ze wszystkich pozycji końcowych, co wymaga zbudowania kompletnej bazy danych tego, co należy zrobić na każdej pozycji, co najmniej na etapie pośrednim.
David Richerby
1
Z przykrością informuję, że się mylisz! @DagOskarMadsen Ale jeśli nie wiesz, jak obalić „nieadekwatne” odpowiedzi, czy naprawdę możesz twierdzić, że rozwiązałeś grę?
David
2

Po powrocie do college'u na początku lat 80. czytałem w grze z tekstem, że jeśli komputer może zaplanować, ocenić i wykonać ruch, dowolny ruch, od początku gry do wszystkich możliwych wniosków co 1/3 nanosekundy, czyli około 3 miliardów ruchów na sekundę, aby to zrobić dla każdego możliwego wyniku, którego ukończenie zajęłoby 10 do 120 wieku. A kto ma tak długo czekać?

Kolejna oszałamiająca statystyka? Słyszałeś o googolu? Nie Google, ale numer? Jest to 10 do 100 potęgi. 10, a następnie 100 zer. Teraz wyobraź sobie googolplex. To 10 dla siły Googola.

Czytałem, że w znanym wszechświecie nie ma wystarczająco dużo niczego , nawet atomów, aby wymagać użycia googlepleksu. W rzeczywistości nawet googol jest zbyt duży, aby cokolwiek opisać. Powinieneś sprawdzić niektóre z zadziwiających ciekawostek na temat tych liczb.

Jon
źródło
1

Jeśli użyjesz „przycinania”, możesz usunąć złe opcje (te, które z pewnością doprowadzą cię do straty) i dalej zapętlać podczas przycinania. W ten sposób możesz mieć wystarczająco dużo pamięci, aby przechowywać „dobre” opcje.

ElieH
źródło
0

Chociaż realizacja szachów w bazie danych w tym wszechświecie może nie być możliwa, można powiedzieć, że abstrakcyjna struktura gry istnieje jako skończony obiekt matematyczny. Można to uzasadnić i stwierdzić, że ma on określony wynik, chociaż możemy nie wiedzieć, co to jest. A jeśli spojrzysz na to jak na matrycę, możesz zadać pytania, takie jak maksymalna przybliżona wartość własna szachów. Rzeczywiście Platon uważał, że liczby istnieją naprawdę, więc sądzę, że powiedziałby, że gra w szachy istnieje w ten sam wzniosły i niepomocny sposób.

Ale w praktyce wyobrażam sobie, że zaawansowany komputer kwantowy może rzeczywiście być w stanie to przedstawić i rozwiązać szachy. Jury wciąż nie ocenia możliwości tej technologii, ale w zasadzie nie widzę, aby było to niemożliwe

Laska
źródło
-1

Tak, myślę, że byłoby to możliwe. Ale tylko wtedy, gdy baza danych była bardziej jak sieć neuronowa, wykonując ruchy, które spowodowały jej utratę i usuwając je. Obliczenia te opierają się na potęgowaniu (proszę się ze mną) wszystkich możliwych działań w grze w szachy w punkcie 1, przesunięcia 100 lub czegoś innego. Tymczasem, jeśli pozbędziemy się powtórzeń, ((Ke3 Ke4 Ke3 Ke3) zapętlenie)) 10 ^ 120 może prawdopodobnie stać się czymś w rodzaju 10 ^ 70. To wciąż jest absurdalnie ogromne, ale gdybyśmy w jakiś sposób mogli go zakodować na płaszczyźnie 4D (co moim zdaniem jest możliwe), byłoby to dziecinnie proste.

użytkownik19889
źródło
2
Witamy w szachach ! Weź udział w wycieczce, gdy będziesz na niej. Twój post może zostać oceniony jako negatywny, ponieważ jest bardziej opinią, a nie odpowiedzią, tak jak się tutaj spodziewamy; zobacz artykuł w Centrum pomocy Jak odpowiedzieć .
Glorfindel
2
Nie jestem szachistą, i dla przypomnienia, nie jestem też jedną z osób, które cię przegłosowały, ale czytałem, że istnieje 10 ^ 43 różnych pozycji. Tylko dlatego, że masz metodę, która pozwala odfiltrować niektóre dane, dlaczego automatycznie zakładasz, że to umożliwia? Myślę, że nie doceniasz dokładnie, jak duża powinna być ta baza danych. Jest to tak daleko poza zasięg współczesnych technologii komputerowych, że nie mogę sobie wyobrazić, że jesteśmy na drodze, by stało się to za sto lat. Ale witaj w SE Chess. (I powitaj mnie też, jak sądzę: P)
Joe Majewski