Czy może istnieć idealny algorytm szachowy?

Aktualne algorytmy szachowe idą około 1 lub może 2 poziomy w dół drzewa możliwych ścieżek w zależności od ruchów gracza i ruchów przeciwnika. Powiedzmy, że mamy moc obliczeniową do opracowania algorytmu, który przewiduje wszystkie możliwe ruchy przeciwnika w grze w szachy. Algorytm, który ma wszystkie możliwe ścieżki, które przeciwnik może pokonać w danym momencie, w zależności od ruchów graczy. Czy może istnieć idealny algorytm szachowy, który nigdy nie przegra? A może algorytm, który zawsze wygrywa? Teoretycznie ktoś, kto potrafi przewidzieć wszystkie możliwe ruchy, musi być w stanie znaleźć sposób na pokonanie każdego z nich lub po prostu wybrać inną ścieżkę, jeśli określony doprowadzi go do porażki .....

edytuj - Czym naprawdę jest moje pytanie. Powiedzmy, że mamy moc obliczeniową dla idealnego algorytmu, który może grać optymalnie. Co dzieje się, gdy przeciwnik gra z tym samym optymalnym algorytmem? Dotyczy to również wszystkich gier 2-osobowych ze skończoną liczbą (bardzo dużych lub nie) ruchów. Czy może istnieć optymalny algorytm, który zawsze wygrywa?

Definicja osobista: Optymalny algorytm to idealny algorytm, który zawsze wygrywa ... (nie taki, który nigdy nie przegrywa, ale taki, który zawsze wygrywa

Twoje pytanie jest podobne do starego kasztana: „Co się stanie, gdy nieodparta siła spotka nieruchomy przedmiot?” Problem tkwi w samym pytaniu: dwa opisane podmioty nie mogą istnieć w tym samym logicznie spójnym wszechświecie. Twój optymalny algorytm, algorytm, który zawsze wygrywa, nie może być używany przez obie strony w grze, w której jedna strona musi wygrać, a druga musi z definicji przegrać. Zatem twój optymalny algorytm, jak zdefiniowano, nie może istnieć.

Po pierwsze, uważam, że algorytmy szachowe wyglądają na więcej niż 2 warstwy, chociaż nie uwzględniają wszystkich różnych możliwości; przycinanie drzewa wyszukiwania jest bardzo ważne, aby uniknąć kombinatorycznej eksplozji w liczbie możliwych ruchów.

W przypadku gry takiej jak szachy istnieją trzy możliwości identyfikacji zwycięzcy: albo gracz 1 ma strategię wygraną, albo gracz 2 ma strategię wygraną, lub obaj gracze dobierają w optymalnej grze. Nie wiadomo, co ma miejsce w przypadku gry w szachy. Ponieważ jednak szachy są grą skończoną, istnieje algorytm komputerowy składający się z bardzo dużego stołu, który optymalnie gra w szachy.

Oczywiście taki algorytm nie byłby praktyczny. Jednak w przypadku niektórych prostszych gier została ustalona „wartość” gry (która wygrywa, o ile ją wygrywa) i opracowano optymalny algorytm. Taka gra jest znana jako gra rozwiązana .

Przedmiotem matematycznym, który zajmuje się (tak zwanymi) grami kombinatorycznymi, jest teoria gier kombinatorycznych . Matematycy opracowali metodę rekurencyjną do określania wartości gry na podstawie jej wykresu, który obejmuje wszystkie dozwolone pozycje i ruchy. Opis tego algorytmu powinien być w stanie znaleźć we wpisie w Wikipedii lub w notatkach na ten temat.

Przede wszystkim dobre algorytmy szachowe wyglądają na więcej niż 1 lub 2 poziomy. Zamiast naiwnego wyszukiwania drzewa, wykonują przycinanie alfa-beta, aby zawęzić liczbę opcji do rozważenia. Zauważ, że w otwarciu i grach końcowych używana jest duża baza ruchów, ponieważ ma lepszą wydajność niż wyszukiwanie drzewa, które jest używane w środku gry.

Na pytanie: wierzę, że pytasz: „Czy szachy można rozwiązać ?”. Jest hipotetycznie, chociaż opinie różnią się, czy ten wynik będzie możliwy do osiągnięcia w najbliższym czasie. Warcaby zostały rozwiązane na przykład w 2007 roku, ale ma znacznie mniej pozycji (wokół pierwiastka kwadratowego liczby w szachach). Aby uzyskać więcej informacji, zobacz artykuł w Wikipedii .

Nawiasem mówiąc, obecne najlepsze szachowe SI prawie zawsze pokonują lub dobierają z mistrzami świata; więc chociaż nie są obecnie idealne, algorytmy są co najmniej całkiem dobre!

Zasadniczo szachy są rozwiązywalne jak każda inna gra. Jak wskazały inne odpowiedzi, nie należy się jednak spodziewać w najbliższym czasie.

Edycja: w komentarzach zaznaczono, że [1] to mistyfikacja, więc pomiń resztę tej odpowiedzi.

To powiedziawszy, nastąpiły pewne ostatnie zmiany w tym kierunku. [1] twierdzi, że wykazał, że otwarcie szachowe zwane King's Gambit zostało rozwiązane : jest tylko jeden ruch, który pociąga dla Białych, podczas gdy wszystkie inne ruchy otwierające prowadzą do zwycięstwa dla Czarnych. Zauważ, że [1] nie zbadał drzewa gry na pełnej głębokości, ale tylko twierdzi, że wyniki te mają duże prawdopodobieństwo.

[1] http://chessbase.com/newsdetail.asp?newsid=8047

To, czy zawsze można wygrać w szachy, zależy od zasad gry. Istnieje jednak technika / algorytm o nazwie Minimax (szczegółowe informacje można znaleźć na stronie https://en.wikipedia.org/wiki/Minimax ). Algorytm polega na próbie przewidzenia, który gracz ma przewagę w różnych scenariuszach z funkcją rekurencyjną. Oto jasne wyjaśnienie, jak to działa w prostszej grze: Kółko i krzyżyk https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-alameterm13 .

doda kolejną odpowiedź, która podkreśla ogromną przestrzeń stanu, niezupełnie konceptualizowaną w pytaniu lub wskazaną w innych odpowiedziach. musi się nie zgadzać z twoim założeniem:

Powiedzmy, że mamy moc obliczeniową do opracowania algorytmu, który przewiduje wszystkie możliwe ruchy przeciwnika w grze w szachy.

zobacz informacje na temat artykułu Shannons z 1950 r., „Programowanie komputera do gry w szachy”, który wprowadził dziedzinę komputerowego grania w szachy / algorytmów i którego analiza jest zasadniczo niezmieniona i nadal brzmi (nawet przez późniejszą rewolucję komputerową i prawo Mooresa ). szacuje liczbę ruchów. jest absolutnie astronomiczny. w zakresie „nigdy w obrębie wyobrażalnego sprzętu, nawet z rewolucyjnymi nieprzewidzianymi postępami”.

jest to udokumentowany fakt psychologiczny [3], prawdopodobnie jeden z wielu uprzedzeń psychologicznych [2], że ludzie mają problemy ze zrozumieniem liczb tej wielkości. patrz także myślenie alternatywne [4], podczas gdy superkomputery obliczają ogromne problemy, jego kontrowersyjnie nie mieści się w zasięgu żadnego superkomputera, który jest obecnie budowany lub który mógłby zostać kiedykolwiek zbudowany. (i wielu miłośników szachów twierdzi, że ta „kombinatoryczna eksplozja” możliwości ruchów / pozycji jest nieodłącznym aspektem „smaku” gier, który wydaje się celowo zaprojektowany w tysiącletniej grze).

dlatego szachy różnią się zasadniczo od niektórych gier, które mają mniejsze „możliwe do rozwiązania” przestrzenie państwowe [które są przedmiotem badań w dziedzinie informatyki i teorii gier itp.] i pod pewnymi kluczowymi względami nie mogą być ocenione w tych ramach.

$10^{123}$$4×10^{79}$$10^{81}$

teraz jednak można sobie wyobrazić (ale mało prawdopodobne), że mogą istnieć teoretyczne spostrzeżenia na temat gry, które można wykorzystać do znacznego przycięcia przestrzeni wyszukiwania. zdarzyło się to od 1950 r., ale tak naprawdę w żaden przełomowy sposób.

Zobacz też

[1] jaka jest złożoność obliczeniowa rozwiązywania szachów, tcs.se

[2] ludzkie uprzedzenia w ocenie i podejmowaniu decyzji

[3] Studenci psychologii publikują badania nad konceptualizacją liczb

[4] alternatywne myślenie