Czy istnieje idealny algorytm do gry w szachy? [Zamknięte]

Niedawno rozmawiałem z osobą niekodującą na temat możliwości komputerów szachowych. Nie jestem dobrze zorientowany w teorii, ale myślę, że wiem wystarczająco.

Twierdziłem, że nie może istnieć deterministyczna maszyna Turinga, która zawsze wygrywała lub znajdowała się w impasie w szachach. Myślę, że nawet jeśli przeszukasz całą przestrzeń wszystkich kombinacji ruchów gracza 1/2, pojedynczy ruch, na który komputer decyduje na każdym kroku, opiera się na heurystyce. Opierając się na heurystyce, niekoniecznie pokonuje WSZYSTKIE ruchy, które może wykonać przeciwnik.

Wręcz przeciwnie, mój przyjaciel pomyślał, że komputer zawsze wygrywa lub remisuje, jeśli nigdy nie wykonałby „błędnego” ruchu (jak to zdefiniujesz?). Jednak będąc programistą, który zajął się CS, wiem, że nawet twoje dobre wybory - biorąc pod uwagę mądrego przeciwnika - mogą w końcu zmusić cię do „błędnych” posunięć. Nawet jeśli wiesz wszystko, następnym krokiem jest chciwość w dopasowaniu heurystyki.

Większość komputerów szachowych próbuje dopasować ewentualną grę końcową do gry w toku, co jest zasadniczo dynamicznym śledzeniem programowania. Ponownie, omawianej gry końcowej można jednak uniknąć.

Edycja: Hmm ... wygląda na to, że potarłem tu kilka piór. Dobre.

Myśląc o tym ponownie, wydaje się, że nie ma teoretycznego problemu z rozwiązywaniem skończonej gry, takiej jak szachy. Twierdzę, że szachy są nieco bardziej skomplikowane niż warcaby, ponieważ wygrana niekoniecznie jest wynikiem numerycznego wyczerpania figur, ale mata. Moje pierwotne stwierdzenie jest prawdopodobnie błędne, ale z drugiej strony wydaje mi się, że wskazałem na coś, co nie zostało jeszcze zadowalająco udowodnione (formalnie).

Wydaje mi się, że mój eksperyment myślowy polegał na tym, że za każdym razem, gdy brana jest gałąź w drzewie, algorytm (lub zapamiętane ścieżki) musi znaleźć ścieżkę do partnera (bez matowania) dla każdej możliwej gałęzi na ruchach przeciwnika. Po dyskusji kupię, że mając więcej pamięci, niż możemy sobie wymarzyć, wszystkie te ścieżki można znaleźć.

"Twierdziłem, że nie może istnieć deterministyczna maszyna Turinga, która zawsze wygrywała lub zatrzymywała się w szachach."

Nie masz racji. Może być taka maszyna. Problemem jest ogrom przestrzeni stanów, którą musiałby przeszukać. To jest skończone, jest po prostu NAPRAWDĘ duże.

Dlatego szachy opierają się na heurystyce - przestrzeń stanów jest zbyt duża (ale ograniczona). Nawet wyliczenie - a tym bardziej poszukiwanie każdego idealnego ruchu na każdym etapie każdej możliwej gry - byłoby bardzo, bardzo dużym problemem związanym z wyszukiwaniem.

Otwarcia są zaplanowane tak, abyś znalazł się w środkowej fazie gry, która daje „silną” pozycję. Nie jest znany wynik. Nawet partie końcowe - gdy jest mniej elementów - są trudne do wyliczenia, aby określić najlepszy następny ruch. Technicznie są ograniczone. Ale liczba alternatyw jest ogromna. Nawet 2 wieże + król ma około 22 możliwych kolejnych ruchów. A jeśli do matowania potrzeba 6 ruchów, to widzisz 12 855 002 631 049 216 ruchów.

Oblicz ruchy otwierające. Chociaż jest tylko około 20 ruchów otwierających, jest około 30 sekund, więc przy trzecim ruchu patrzymy na 360 000 alternatywnych stanów gry.

Ale gry w szachy są (technicznie) ograniczone. Ogromne, ale ograniczone. Są doskonałe informacje. Istnieją zdefiniowane stany początkowe i końcowe. Nie ma rzutów monetą ani kostkami.

Prawie nic nie wiem o tym, co faktycznie odkryto o szachach. Ale jako matematyk mam takie rozumowanie:

Najpierw musimy pamiętać, że pierwsze są białe i może to daje mu przewagę; może daje to czarnemu przewagę.

Przypuśćmy teraz, że nie ma idealnej strategii dla czarnych, która zawsze pozwala mu wygrać / wpaść w impas. Oznacza to, że bez względu na to, co robią czarne, istnieje strategia, którą białe mogą zastosować, aby wygrać. Chwileczkę - oznacza to idealną strategię dla białych!

To mówi nam, że co najmniej jeden z dwóch graczy ma mieć doskonałą strategię, która pozwala, że gracz zawsze wygra lub zremisuje.

Są więc tylko trzy możliwości:

• Białe zawsze mogą wygrać, jeśli gra perfekcyjnie
• Czarny zawsze może wygrać, jeśli gra perfekcyjnie
• Jeden gracz może wygrać lub zremisować, jeśli gra perfekcyjnie (a jeśli obaj grają perfekcyjnie, zawsze wpadają w impas)

Ale które z nich jest rzeczywiście poprawne, możemy nigdy nie wiedzieć.

Odpowiedź na pytanie brzmi : tak : musi istnieć idealny algorytm do gry w szachy, przynajmniej dla jednego z dwóch graczy.

W przypadku gry w warcaby udowodniono, że program zawsze może wygrać lub zremisować grę. Oznacza to, że nie ma wyboru ruchów, które jeden gracz może wykonać, a które zmuszą drugiego gracza do przegrania.

Naukowcy spędzili prawie dwie dekady , przeglądając 500 miliardów możliwych pozycji w warcaby, co, nawiasem mówiąc, wciąż stanowi nieskończenie mały ułamek liczby pozycji szachowych. Wysiłek warcabów obejmował najlepszych graczy, którzy pomogli zespołowi badawczemu zaprogramować praktyczne zasady gry w oprogramowanie, które klasyfikowało ruchy jako udane lub nieudane. Następnie badacze uruchomili program na średnio 50 komputerach dziennie. W niektóre dni program działał na 200 komputerach. Podczas gdy naukowcy monitorowali postępy i odpowiednio dostosowywali program. W rzeczywistości Chinook pokonał ludzi, aby wygrać mistrzostwa świata w warcaby w 1994 roku.

Tak, możesz rozwiązywać szachy, nie, wkrótce nie będziesz.

To nie jest kwestia komputerów, ale tylko gry w szachy.

Pytanie brzmi, czy istnieje bezpieczna strategia, aby nigdy nie przegrać gry? Jeśli taka strategia istnieje, to komputer, który wie wszystko, zawsze może z niej skorzystać i nie jest to już heurystyka.

Na przykład gra w kółko i krzyżyk jest normalnie rozgrywana w oparciu o heurystykę. Ale istnieje strategia bezpieczeństwa. Cokolwiek poruszy przeciwnik, zawsze znajdziesz sposób na uniknięcie przegranej gry, jeśli zrobisz to od samego początku.

Musiałbyś więc udowodnić, że taka strategia istnieje lub nie istnieje również w przypadku szachów. Jest w zasadzie to samo, po prostu przestrzeń możliwych ruchów jest znacznie większa.

Przychodzę do tego wątku bardzo późno i że zdałeś sobie już sprawę z niektórych problemów. Ale jako były mistrz i były zawodowy programista szachowy pomyślałem, że mogę dodać kilka przydatnych faktów i liczb. Istnieje kilka sposobów mierzenia złożoności szachów :

• Całkowita liczba partii szachowych to około 10 ^ (10 ^ 50). Ta liczba jest niewyobrażalnie duża.
• Liczba partii szachowych składających się z 40 lub mniej ruchów wynosi około 10 ^ 40. To wciąż niesamowicie duża liczba.
• Liczba możliwych pozycji szachowych to około 10 ^ 46.
• Pełne drzewo wyszukiwania szachów (liczba Shannona) wynosi około 10 ^ 123, przy średnim współczynniku rozgałęzienia wynoszącym 35 i średniej długości gry 80.
• Dla porównania, liczbę atomów w obserwowalnym wszechświecie szacuje się powszechnie na około 10 ^ 80.
• Wszystkie końcówki składające się z 6 lub mniej elementów zostały zestawione i rozwiązane .

Mój wniosek: chociaż szachy są teoretycznie możliwe do rozwiązania, nigdy nie będziemy mieć pieniędzy, motywacji, mocy obliczeniowej ani pamięci masowej, aby to zrobić.

W rzeczywistości niektóre gry zostały rozwiązane. Kółko i krzyżyk to bardzo łatwy sposób na zbudowanie sztucznej inteligencji, która zawsze wygrywa lub remisuje. Niedawno rozwiązano również Connect 4 (i okazało się, że jest to niesprawiedliwe dla drugiego gracza, ponieważ perfekcyjna gra spowoduje, że przegra).

Szachy nie zostały jednak rozwiązane i nie sądzę, aby istniał żaden dowód na to, że jest to gra uczciwa (tj. Czy perfekcyjna gra kończy się remisem). Mówiąc ściśle z teoretycznej perspektywy, szachy mają skończoną liczbę możliwych konfiguracji figur. Dlatego przestrzeń poszukiwań jest ograniczona (aczkolwiek niewiarygodnie duża). Dlatego istnieje deterministyczna maszyna Turinga, która mogłaby grać doskonale. Jednak to, czy kiedykolwiek uda się coś zbudować, to inna sprawa.

Przeciętny komputer stacjonarny o wartości 1000 USD będzie w stanie rozwiązać warcaby w zaledwie 5 sekund do roku 2040 (obliczenia 5x10 ^ 20).

Nawet przy tej szybkości i tak zajęłoby 100 takich komputerów około 6,34 x 10 ^ 19 lat rozwiązanie szachów . Nadal niewykonalne. Nawet nie blisko.

Około 2080 roku nasze przeciętne komputery stacjonarne będą miały około 10 ^ 45 obliczeń na sekundę. Pojedynczy komputer będzie miał moc obliczeniową do rozwiązania szachów w około 27,7 godziny. Z pewnością nastąpi to do 2080 r., O ile moc obliczeniowa będzie rosła, tak jak miało to miejsce w ciągu ostatnich 30 lat.

Do 2090 r. Na pulpicie o wartości 1000 USD będzie wystarczająca moc obliczeniowa, aby rozwiązać szachy w około 1 sekundę ... więc do tego czasu będzie to całkowicie trywialne.

Biorąc pod uwagę, że warcaby zostały rozwiązane w 2007 roku, a moc obliczeniowa do rozwiązania go w ciągu 1 sekundy będzie opóźniona o około 33-35 lat, prawdopodobnie możemy z grubsza oszacować, że szachy zostaną rozwiązane gdzieś w latach 2055-2057. Prawdopodobnie prędzej od kiedy będzie więcej mocy obliczeniowej (co będzie miało miejsce za 45 lat), więcej będzie można przeznaczyć na projekty takie jak ten. Jednak powiedziałbym, że najwcześniej 2050, a najpóźniej 2060.

W 2060 r. Rozwiązanie szachów zajęłoby 100 przeciętnym komputerom stacjonarnym 3,17 x 10 ^ 10 lat. Uświadom sobie, że używam komputera za 1000 USD jako mojego punktu odniesienia, podczas gdy większe systemy i superkomputery będą prawdopodobnie dostępne, ponieważ ich stosunek ceny do wydajności również się poprawia. Ponadto ich rząd wielkości mocy obliczeniowej rośnie w szybszym tempie. Rozważmy, że superkomputer może teraz wykonywać obliczenia 2,33 x 10 ^ 15 na sekundę, a komputer o wartości 1000 USD około 2 x 10 ^ 9. Dla porównania 10 lat temu różnica wynosiła 10 ^ 5 zamiast 10 ^ 6. Do 2060 roku różnica rzędu wielkości prawdopodobnie wyniesie 10 ^ 12, a nawet ta może wzrosnąć szybciej niż przewidywano.

Wiele z tego zależy od tego, czy my, jako istoty ludzkie, mamy skłonność do rozwiązywania szachów, ale moc obliczeniowa sprawi, że będzie to wykonalne w tym czasie (o ile nasze tempo będzie trwać).

Z drugiej strony, gra w kółko i krzyżyk, która jest dużo, dużo prostsza, ma 2653002 możliwych obliczeń (z otwartą planszą). Moc obliczeniową do rozwiązania Kółko i krzyżyk w około 2,5 (1 milion obliczeń na sekundę) sekundy osiągnięto w 1990 roku.

Cofając się wstecz, w 1955 roku komputer miał moc rozwiązania „Kółko i krzyżyk” w około 1 miesiąc (1 obliczenie na sekundę). Ponownie, opiera się to na tym, co dałoby 1000 USD, gdybyś mógł spakować go do komputera (komputer stacjonarny o wartości 1000 USD oczywiście nie istniał w 1955 r.), A ten komputer byłby przeznaczony do rozwiązywania problemów w Kółko i krzyżyk ... po prostu nie było w 1955 r. Obliczenia były drogie i nie zostałyby wykorzystane do tego celu, chociaż nie sądzę, aby istniała data, w której komputer zostałby uznany za „rozwiązany” przez Kółko i krzyżyk, ale jestem na pewno pozostaje w tyle za rzeczywistą mocą obliczeniową.

Weź również pod uwagę, że 1000 $ za 45 lat będzie warte około 4 razy mniej niż obecnie, więc o wiele więcej pieniędzy może zostać przeznaczonych na projekty takie jak ten, podczas gdy moc obliczeniowa będzie nadal tańczyć.

To rzeczywiście jest to możliwe dla obaj gracze mają strategie wygrania w nieskończonych gier bez dobrego zamawiającego; jednak szachy są uporządkowane. W rzeczywistości, ze względu na zasadę 50 ruchów , istnieje górna granica liczby ruchów, które może mieć gra, a zatem istnieje tylko skończona liczba możliwych partii szachów (które można wyliczyć, aby dokładnie rozwiązać ... teoretycznie, przynajmniej :)

Twój koniec argumentacji jest wspierany przez sposób, w jaki działają obecnie nowoczesne programy szachowe . Działają w ten sposób, ponieważ zakodowanie programu szachowego, aby działał deterministycznie, wymaga zbyt dużej ilości zasobów. Nie zawsze będą działać w ten sposób. Możliwe, że któregoś dnia zostaną rozwiązane szachy , a jeśli tak się stanie, prawdopodobnie zostanie rozwiązane przez komputer.

Dla przypomnienia, są komputery, które mogą wygrywać lub remisować w warcabach . Nie jestem pewien, czy to samo można zrobić z szachami. Liczba ruchów jest dużo większa. Ponadto sytuacja się zmienia, ponieważ pionki mogą poruszać się w dowolnym kierunku, nie tylko do przodu i do tyłu. Myślę, że chociaż nie jestem pewien, czy szachy są deterministyczne, ale jest po prostu zbyt wiele możliwych ruchów, aby komputer mógł obecnie określić wszystkie ruchy w rozsądnym czasie.

Myślę, że nie żyjesz. Maszyny takie jak Deep Blue i Deep Thought są zaprogramowane z wieloma predefiniowanymi grami i sprytnymi algorytmami analizującymi drzewa na końce tych gier. To oczywiście dramatyczne uproszczenie. Zawsze istnieje szansa na „pokonanie” komputera w trakcie gry. Rozumiem przez to wykonanie ruchu, który zmusza komputer do wykonania ruchu mniej niż optymalnego (cokolwiek to jest). Jeśli komputer nie może znaleźć najlepszej ścieżki przed upływem limitu czasu na ruch, może popełnić błąd, wybierając jedną z mniej pożądanych ścieżek.

Istnieje inna klasa programów szachowych, które wykorzystują prawdziwe uczenie maszynowe lub algorytmy programowania genetycznego / ewolucyjne. Niektóre programy ewoluowały i do podejmowania decyzji wykorzystują sieci neuronowe i in. W takim przypadku wyobrażam sobie, że komputer może popełniać „błędy”, ale i tak kończy się zwycięstwem.

Jest fascynująca książka o tego typu lekarzach ogólnych o nazwie Blondie24, którą możesz przeczytać. Chodzi o warcaby, ale może odnosić się do szachów.

Z teorii gier, o co chodzi w tym pytaniu, odpowiedź brzmi: tak W szachy można grać doskonale. Przestrzeń gry jest znana / przewidywalna i tak, gdybyś miał komputery kwantowe wnuka, prawdopodobnie mógłbyś wyeliminować całą heurystykę.

Mógłbyś teraz napisać idealną maszynę do gry w kółko i krzyżyk w dowolnym języku skryptowym i grałaby doskonale w czasie rzeczywistym.

Othello to kolejna gra, w którą obecne komputery mogą z łatwością grać doskonale, ale pamięć i procesor maszyny będą potrzebować trochę pomocy

Szachy są teoretycznie możliwe, ale praktycznie niemożliwe (w 2008 r.)

i-Go jest trudne, jego przestrzeń możliwości wykracza poza liczbę atomów we wszechświecie, więc stworzenie idealnej maszyny i-Go może nam zająć trochę czasu.

Szachy są przykładem gry matrycowej, która z definicji ma optymalny wynik (pomyśl o równowadze Nasha). Jeśli każdy z graczy 1 i 2 podejmie optymalne ruchy, ZAWSZE zostanie osiągnięty pewien wynik (czy będzie to wygrana-remis-przegrana wciąż nie jest znana).

Jako programista szachowy od lat 70. zdecydowanie mam na ten temat zdanie. To, co napisałem około 10 lat temu, nadal jest w zasadzie prawdą dzisiaj:

„Niedokończona praca i wyzwania dla programistów szachowych”

Wtedy myślałem, że możemy układać szachy w sposób konwencjonalny, jeśli zrobimy to poprawnie.

Warcaby zostały niedawno rozwiązane (Yay, University of Alberta, Kanada !!!), ale zostało to skutecznie zrobione Brute Force. Aby grać w szachy w sposób konwencjonalny, musisz być mądrzejszy.

Chyba że, oczywiście, obliczenia kwantowe staną się rzeczywistością. Jeśli tak, szachy będą rozwiązywane równie łatwo jak kółko i krzyżyk.

Na początku lat siedemdziesiątych moją uwagę zwróciła krótka parodia w Scientific American. Było to ogłoszenie, że partię szachów rozwiązał rosyjski komputer szachowy. Zdecydował, że jest jeden doskonały ruch dla białych, który zapewni zwycięstwo przy doskonałej grze obu stron, a ten ruch to: 1. a4!

Wiele odpowiedzi tutaj przedstawia ważne punkty teoretyczne gry:

1. Szachy to gra skończona, deterministyczna z pełną informacją o stanie gry
2. Możesz rozwiązać skończoną grę i znaleźć idealną strategię
3. Szachy są jednak na tyle duże, że nie będziesz w stanie rozwiązać ich całkowicie metodą brutalnej siły

Jednak te obserwacje pomijają ważną praktyczną kwestię: nie jest konieczne idealne rozwiązanie całej gry, aby stworzyć bezkonkurencyjną maszynę .

W rzeczywistości jest całkiem prawdopodobne, że mógłbyś stworzyć maszynę szachową bezkonkurencyjną (tzn. Nigdy nie przegra i zawsze wymusi wygraną lub remis) bez przeszukiwania nawet najmniejszego ułamka możliwej przestrzeni stanów.

Na przykład wszystkie poniższe techniki znacznie zmniejszają wymaganą przestrzeń wyszukiwania:

• Techniki przycinania drzew, takie jak Alpha / Beta lub MTD-f, już teraz znacznie zmniejszają przestrzeń wyszukiwania
• Potwierdzona zwycięska pozycja. Wiele zakończeń należy do tej kategorii: nie musisz na przykład wyszukiwać KR vs K, to udowodniona wygrana. Przy odrobinie pracy można udowodnić znacznie więcej gwarantowanych wygranych.
• Niemal pewne wygrane - dla „dostatecznie dobrej” gry bez głupich błędów (powiedzmy o ELO 2200+?) Wiele pozycji szachowych to niemal pewne wygrane, na przykład przyzwoita przewaga materialna (np. Dodatkowy skoczek) bez kompensującej przewagi pozycyjnej. Jeśli Twój program może wymusić taką pozycję i ma wystarczająco dobre heurystyki do wykrywania przewagi pozycyjnej, może bezpiecznie założyć, że wygra lub przynajmniej zremisuje ze 100% prawdopodobieństwem.
• Heurystyka przeszukiwania drzewa - mając wystarczająco dobre rozpoznawanie wzorców, można szybko skupić się na odpowiednim podzbiorze „interesujących” ruchów. Tak grają ludzcy arcymistrzowie, więc nie jest to zła strategia ..... a nasze algorytmy rozpoznawania wzorców są stale ulepszane
• Ocena ryzyka - lepsza koncepcja „ryzykowności” pozycji umożliwi znacznie skuteczniejsze wyszukiwanie poprzez skupienie mocy obliczeniowej na sytuacjach, w których wynik jest bardziej niepewny (jest to naturalne rozszerzenie wyszukiwania w uśpieniu )

Przy odpowiednim połączeniu powyższych technik czułbym się komfortowo stwierdzając, że możliwe jest stworzenie „bezkonkurencyjnej” maszyny do gry w szachy. Prawdopodobnie nie jesteśmy zbyt daleko od obecnej technologii.

Zauważ, że prawie na pewno trudniej jest udowodnić, że tej maszyny nie da się pokonać. Prawdopodobnie byłoby to coś w rodzaju hipotezy Reimanna - bylibyśmy prawie pewni, że gra doskonale i miałoby empiryczne wyniki pokazujące, że nigdy nie przegrał (w tym kilka miliardów stritów przeciwko sobie), ale tak naprawdę nie mielibyśmy możliwości Udowodnij to.

Dodatkowa uwaga dotycząca „doskonałości”:

Uważam, aby nie opisywać maszyny jako „idealnej” w sensie teorii gier, ponieważ oznacza to niezwykle silne dodatkowe warunki, takie jak:

• Zawsze wygrywa w każdej sytuacji, w której można wymusić wygraną, bez względu na to, jak skomplikowana może być wygrywająca kombinacja. Będą sytuacje na granicy wygranej / remisu, w których niezwykle trudno jest to dokładnie obliczyć.
• Wykorzystywanie wszystkich dostępnych informacji o potencjalnej niedoskonałości gry przeciwnika, na przykład wnioskowanie, że przeciwnik może być zbyt chciwy i rozmyślnie rozgrywać nieco słabszą linię niż zwykle, na tej podstawie, że ma ona większy potencjał, aby skusić przeciwnika do popełnienia błędu. W przypadku niedoskonałych przeciwników optymalne może być przegranie, jeśli oszacujesz, że Twój przeciwnik prawdopodobnie nie zauważy wymuszonej wygranej i daje to większe prawdopodobieństwo wygranej.

Perfekcja (szczególnie biorąc pod uwagę niedoskonałych i nieznanych przeciwników) jest znacznie trudniejszym problemem niż po prostu bycie niepokonanym.

jeśli przeszukasz całą przestrzeń wszystkich kombinacji ruchów gracza 1/2, pojedynczy ruch, na który komputer decyduje na każdym kroku, opiera się na heurystyce.

Są tam dwa konkurujące ze sobą pomysły. Jedna polega na tym, że przeszukujesz każdy możliwy ruch, a druga polega na tym, że decydujesz na podstawie heurystyki. Heurystyka to system umożliwiający trafne przypuszczenie. Jeśli przeszukujesz każdy możliwy ruch, to już nie zgadujesz.

„Czy istnieje idealny algorytm do gry w szachy?”

Tak jest. Może białe zawsze wygrywają. Może to zawsze wygrywa czarne. Może oboje powinni zawsze przynajmniej wiązać. Nie wiemy, które i nigdy się nie dowiemy, ale z pewnością istnieje.

Zobacz też

• Algorytm Boga

Znalazłem ten artykuł Johna MacQuarrie, który odnosi się do pracy „ojca teorii gier” Ernsta Friedricha Ferdinanda Zermelo . Wyciąga następujący wniosek:

W szachach albo białe mogą wymusić wygraną, albo czarne mogą wymusić wygraną, albo obie strony mogą wymusić przynajmniej remis.

Wydaje mi się, że logika jest rozsądna.

Jest to całkowicie rozwiązalne.

Istnieje 10 ^ 50 nieparzystych pozycji. Według moich obliczeń każda pozycja wymaga co najmniej 64 okrągłych bajtów (każdy kwadrat ma: 2 bity przynależności, 3 bity elementowe). Po zestawieniu pozycji, które są matami, można zidentyfikować i porównać pozycje w celu utworzenia relacji, pokazującej, które pozycje prowadzą do innych pozycji w dużym drzewie wyników.

Następnie program musi tylko znaleźć najniższe pierwiastki matowe tylko z jednej strony, jeśli coś takiego istnieje. W każdym razie szachy zostały po prostu rozwiązane na końcu pierwszego akapitu.

Tylko w 99,9% przekonuje mnie stwierdzenie, że wielkość przestrzeni stanów nie pozwala mieć nadziei na rozwiązanie.

Jasne, 10 ^ 50 to nieprawdopodobnie duża liczba. Nazwijmy rozmiar przestrzeni stanów n.

Jaka jest granica liczby ruchów w najdłuższej możliwej grze? Ponieważ wszystkie gry kończą się skończoną liczbą ruchów, istnieje taka granica, nazwijmy ją m.

Zaczynając od stanu początkowego, czy nie możesz wyliczyć wszystkich n ruchów w przestrzeni O (m)? Jasne, zajmuje to O (n) czasu, ale argumenty dotyczące rozmiaru wszechświata nie odnoszą się bezpośrednio do tego. O (m) przestrzeń może nawet nie być zbyt duża. W przypadku przestrzeni O (m) nie mógłbyś również śledzić, podczas tej wędrówki, czy kontynuacja dowolnego stanu na ścieżce, którą przemierzasz, prowadzi do EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin lub BlackMayWinOrForceDraw? (W zależności od tego, czyja kolej jest krata, zanotuj każdy stan w historii twojego przemierzania ze spotkaniem kraty).

O ile czegoś nie brakuje, jest to algorytm przestrzenny O (n) czas / O (m) do określenia, do której z możliwych kategorii należą szachy. Wikipedia podaje szacunki dotyczące wieku Wszechświata na około 10–60 lat Plancka. Nie wdając się w kosmologię, zgadnijmy, że do upału / zimna / jakiejkolwiek śmierci wszechświata zostało mniej więcej tyle czasu. To sprawia, że ​​musimy oceniać jeden ruch co 10 ^ 10 razy Plancka lub co 10 ^ -34 sekundy. To niewiarygodnie krótki czas (około 16 rzędów wielkości krótszy niż najkrótszy czas jaki kiedykolwiek zaobserwowano). Powiedzmy z optymizmem, że z super-duper-dobrą implementacją działającą na szczycie linii obecnej-lub-przewidywanej-nie-kwantowej-P-jest-właściwym-podzbiorem-NP, możemy mieć nadzieję na ocenę (weźmy jeden krok naprzód, kategoryzuj wynikowy stan jako stan pośredni lub jeden z trzech stanów końcowych) z częstotliwością 100 MHz (raz na 10 ^ -8 sekund). Ponieważ ten algorytm jest bardzo równoległy, oznacza to, że potrzebujemy 10 ^ 26 takich komputerów lub około jednego na każdy atom w moim ciele, wraz z możliwością zbierania ich wyników.

Przypuszczam, że zawsze jest jakaś nadzieja na brutalne rozwiązanie. Możemy mieć szczęście i badając tylko jeden z możliwych ruchów otwierających białych, obaj wybierają taki, w którym fanout jest dużo niższy od przeciętnego, i taki, w którym białe zawsze wygrywają lub wygrywają lub remisują.

Moglibyśmy również mieć nadzieję, że nieco zmniejszymy definicję szachów i przekonamy wszystkich, że moralnie jest to ta sama gra. Czy naprawdę musimy wymagać, aby pozycje powtarzały się 3 razy przed losowaniem? Czy naprawdę musimy sprawić, by uciekająca drużyna wykazała się umiejętnością ucieczki na 50 ruchów? Czy ktoś w ogóle rozumie, o co chodzi z zasadą en passant ? ;) Mówiąc bardziej poważnie, czy naprawdę musimy zmuszać gracza do ruchu (w przeciwieństwie do rysowania lub przegrywania), kiedy jego jedynym ruchem jest ucieczka przed czekiem, czy pat jest bicie en passant ? Czy moglibyśmy ograniczyć wybór figur, do których pionek może być promowany, jeśli pożądany awans na królową nie prowadzi do natychmiastowego czeku lub mata?

Nie jestem również pewien, jak bardzo zezwolenie każdemu komputerowi na dostęp na podstawie skrótu do dużej bazy danych stanów późnej gry i ich możliwych wyników (co może być względnie wykonalne na istniejącym sprzęcie i przy istniejących bazach danych gry końcowej) może pomóc we wcześniejszym przycinaniu wyszukiwania. Oczywiście nie możesz zapamiętać całej funkcji bez pamięci O (n), ale możesz wybrać dużą liczbę całkowitą i zapamiętać, że wiele gier końcowych wylicza wstecz od każdego możliwego (lub nawet niełatwo udowodnić, jak sądzę) stanu końcowego.

Wiem, że to trochę nierówna sytuacja, ale muszę włożyć tutaj moje 5 centów. Komputer lub osoba może zakończyć każdą partię szachów, w której bierze udział, wygraną lub impasem.

Jednak aby to osiągnąć, musisz dokładnie znać każdy możliwy ruch i reakcję, i tak dalej, aż do każdego możliwego wyniku gry i wizualizować to lub w łatwy sposób analizować te informacje, pomyśl o jest to mapa myśli, która nieustannie się rozgałęzia.

Węzeł centralny byłby początkiem gry. Każda gałąź wychodząca z każdego węzła symbolizuje ruch, każdy inny niż jego ruchy bretheren. Przedstawienie go w tej posiadłości wymagałoby wielu zasobów, zwłaszcza jeśli robisz to na papierze. Na komputerze wymagałoby to prawdopodobnie setek terabajtów danych, ponieważ miałbyś bardzo wiele repedycyjnych ruchów, chyba że przywrócisz gałęzie.

Jednak zapamiętanie takich danych byłoby niewiarygodne, jeśli nie niemożliwe. Aby komputer rozpoznał najbardziej optymalny ruch, aby wykonać (najwyżej) 8 natychmiastowych ruchów, byłoby możliwe, ale nie do przyjęcia ... ponieważ komputer musiałby być w stanie przetworzyć wszystkie gałęzie za tym ruchem, aż do konkluzji, policz wszystkie wnioski, które doprowadzą do wygranej lub impasu, a następnie zastosuj się do tej liczby zwycięskich wniosków, aby nie przegrać, a to wymagałoby pamięci RAM zdolnej do przetwarzania danych w terabajtach lub więcej! A przy dzisiejszej technologii komputer taki wymagałby więcej niż saldo bankowe 5 najbogatszych mężczyzn i / lub kobiet na świecie!

Więc po tych wszystkich rozważaniach dało się to zrobić, jednak nikt nie mógł tego zrobić. Takie zadanie wymagałoby 30 najbystrzejszych umysłów żyjących dzisiaj, nie tylko w szachach, ale także w nauce i technologii komputerowej, a takie zadanie można było wykonać tylko z (postawmy to całkowicie w podstawowej perspektywie) ... komputer super-duper ... który nie mógłby istnieć przez co najmniej sto lat. Będzie zrobione! Po prostu nie w tym życiu.

W twoim eksperymencie myślowym są dwa błędy:

1. Jeśli twoja maszyna Turinga nie jest „ograniczona” (pamięć, szybkość, ...) nie musisz używać heurystyki, ale możesz obliczyć końcowe stany (wygrana, przegrana, remis). Aby znaleźć idealną grę, wystarczy użyć algorytmu Minimax (patrz http://en.wikipedia.org/wiki/Minimax ), aby obliczyć optymalne ruchy dla każdego gracza, co doprowadziłoby do jednej lub więcej optymalnych gier.

2. Nie ma również ograniczeń co do złożoności stosowanej heurystyki. Jeśli potrafisz obliczyć idealną grę, istnieje również sposób na wyliczenie z niej doskonałej heurystyki. W razie potrzeby jest to po prostu funkcja, która odwzorowuje pozycje szachowe w sposób „Jeśli jestem w tej sytuacji S moim najlepszym ruchem jest M”.

Jak inni już zauważyli, zakończy się to 3 możliwymi wynikami: białe mogą wymusić wygraną, czarne mogą wymusić wygraną, a jeden z nich może wymusić remis.

Wynik doskonałej gry w warcaby został już „obliczony”. Jeśli ludzkość wcześniej się nie zniszczy, pewnego dnia zostaną obliczone dla szachów, kiedy komputery rozwiną się na tyle, by mieć wystarczającą ilość pamięci i szybkości. Albo mamy komputery kwantowe ... Albo dopóki ktoś (badacz, znawca szachów, geniusz) znajdzie jakieś algorytmy, które znacznie zmniejszają złożoność gry. Oto przykład: Jaka jest suma wszystkich liczb od 1 do 1000? Możesz obliczyć 1 + 2 + 3 + 4 + 5 ... + 999 + 1000 lub po prostu obliczyć: N * (N + 1) / 2 przy N = 1000; wynik = 500500. Teraz wyobraź sobie, że nie wiesz o tym wzorze, nie wiesz o indukcji matematycznej, nie wiesz nawet, jak mnożyć lub dodawać liczby, ... Więc, możliwe, że istnieje obecnie nieznany algorytm, który ostatecznie zmniejsza złożoność tej gry i obliczenie najlepszego ruchu na obecnym komputerze zajęłoby tylko 5 minut. Może dałoby się nawet oszacować to jako człowieka za pomocą pióra i papieru, a nawet w myślach, mając trochę więcej czasu.

Szybka odpowiedź brzmi: jeśli ludzkość przetrwa wystarczająco długo, to tylko kwestia czasu!

Może to być rozwiązane, ale coś mi przeszkadza: nawet gdyby można było przejść całe drzewo, nadal nie ma sposobu, aby przewidzieć następny ruch przeciwnika. Musimy zawsze oprzeć nasz następny ruch na stanie przeciwnika i wykonać „najlepszy” dostępny ruch. Następnie na podstawie kolejnego stanu robimy to ponownie. Tak więc nasz optymalny ruch może być optymalny, jeśli przeciwnik poruszy się w określony sposób. W przypadku niektórych ruchów przeciwnika nasz ostatni ruch mógł być nieoptymalny.

Po prostu nie rozumiem, jak na każdym kroku może być „doskonały” ruch.

Aby tak się stało, dla każdego stanu [w bieżącej grze] musi istnieć ścieżka w drzewie, która prowadzi do zwycięstwa, niezależnie od następnego ruchu przeciwnika (jak w kółko i krzyżyk), a ja mam trudny Czas to wymyślić.

Matematycznie, szachy zostały rozwiązane przez algorytm Minimax , którego początki sięgają lat dwudziestych XX wieku (znaleziony przez Borela lub von Neumanna). Tak więc maszyna Turinga rzeczywiście może grać w doskonałe szachy.

Jednak złożoność obliczeniowa szachów sprawia, że ​​jest to praktycznie niewykonalne. Obecne silniki używają kilku ulepszeń i heurystyk. Dzisiejsze najlepsze silniki przewyższały najlepszych ludzi pod względem siły gry, ale ze względu na heurystykę, której używają, mogą nie działać idealnie w nieskończonym czasie (np. Kolizje hash mogą prowadzić do nieprawidłowych wyników).

Najbliższe, jakie mamy obecnie pod względem idealnej gry, to tabele końcowe . Typową techniką ich generowania jest analiza wsteczna . Obecnie wszystkie pozycje z maksymalnie sześcioma figurami zostały rozwiązane.

Tak , w matematyce szachy są klasyfikowane jako gra zdeterminowana, co oznacza, że ​​ma doskonały algorytm dla każdego pierwszego gracza, udowodniono, że jest to prawdą nawet dla nieskończonej szachownicy, więc prawdopodobnie pewnego dnia kwantowa sztuczna inteligencja znajdzie idealną strategię, i gra się skończyła

Więcej na ten temat w tym filmie: https://www.youtube.com/watch?v=PN-I6u-AxMg

Istnieją również szachy kwantowe, w których nie ma matematycznego dowodu, że jest to zdeterminowana gra http://store.steampowered.com/app/453870/Quantum_Chess/

a tam masz szczegółowy film o szachach kwantowych https://chess24.com/en/read/news/quantum-chess

Oczywiście jest tylko 10 do potęgi pięćdziesięciu możliwych kombinacji pionów na planszy. Mając to na uwadze, aby zagrać przy każdej kompilacji, musiałbyś wykonać poniżej 10 do potęgi pięćdziesięciu ruchów (w tym powtórzenia pomnożyć tę liczbę przez 3). Zatem do potęgi stu ruchów w szachach jest mniej niż dziesięć. Po prostu wybierz te, które prowadzą do mata i jesteś gotowy

64-bitowa matematyka (= szachownica) i operatory bitowe (= następne możliwe ruchy) to wszystko, czego potrzebujesz. Po prostu. Brute Force zwykle znajdzie najlepszy sposób. Oczywiście nie ma uniwersalnego algorytmu dla wszystkich pozycji. W prawdziwym życiu obliczenia są również ograniczone w czasie, limit czasu je zatrzyma. Dobry program szachowy to ciężki kod (zdany, zdublowane pionki itp.). Mały kod nie może być bardzo silny. Otwieranie i zamykanie baz danych po prostu oszczędza czas przetwarzania, niektóre wstępnie przetworzone dane. Urządzenie, mam na myśli - system operacyjny, możliwości wątków, środowisko, sprzęt definiują wymagania. Język programowania jest ważny. W każdym razie proces rozwoju jest interesujący.