Czy może istnieć idealny algorytm szachowy?

15

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

algorithms turing-machines

— John Demetriou
źródło

1

zobacz także, jaka jest złożoność obliczeniowa rozwiązywania szachów, tcs.se

— vzn 12.12

To pytanie opiera się na kilku nieporozumieniach. Po pierwsze, komputery szachowe wyglądają znacznie dalej niż jedna lub dwie warstwy naprzód: nawet pięć lat temu na zwykłym laptopie całkiem zwyczajne programy szachowe wyglądały na 15-16 warstw na przyszłość, a ponad 25 na krytycznych liniach. Po drugie, nie można osiągnąć definicji „doskonałego” jako „zawsze wygrywającego”, jak pokazano w odpowiedziach. Po trzecie, silniki szachowe nie „przewidują” ruchów: obliczają i wykonują ruchy, które są dobre przeciwko wszelkim możliwym reakcjom.

— David Richerby,

13

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ć.

— Kyle Jones
źródło

3

Może to być na przykład algorytm, który pozwala pierwszemu graczowi wygrać. Oznaczałoby to, że gra jako pierwsza ma przewagę. A może optymalny algorytm pozwala tylko drugiemu graczowi wygrać. Dałoby to drugiemu graczowi przewagę. Trzecią możliwością jest algorytm, który pozwala jednemu z graczy zawsze wymusić remis, ale nie gwarantuje wygranej (ponieważ jak chce OP, to dzieje się na przykład, jeśli obaj gracze grają w tę samą strategię wygranej , jeśli nie ma przewagi w grze na pierwszym lub drugim).

— Realz Slaw,

3

@Realz Cóż, tak, jeśli zmienisz definicję „optymalnego algorytmu”, możesz udowodnić, co chcesz. Użyłem definicji, o którą pytający nas poprosił.

— Kyle Jones,

Oto odpowiedź, którą próbowałem wydostać się z ludzi. Nie może istnieć algorytm, który zawsze wygrywa, ponieważ jest to gra dla 2 graczy, więc nie ma możliwości, aby algorytm mógł działać, ponieważ obaj gracze mogą mieć ten sam algorytm, więc po prostu co najmniej jeden z nich musi wygrać (przegrać lub zremisować) . Zadałem mojemu nauczycielowi to samo pytanie i zajęło nam wiele czasu, aby dojść do tego wniosku

— John Demetriou,

3

@JohnDemetriou Problem polega na tym, że taki wniosek jest błędny . Szachy nie są grą symetryczną ze względu na przewagę pierwszego gracza - jest całkiem możliwe, że istnieje optymalny algorytm, który pozwala Białym grać i wygrywać, ale Czarne nie mogą używać tego algorytmu z tego prostego powodu, że nie jest Biała!

— Steven Stadnicki,

Jest również możliwe, należy zauważyć, że pierwsze podejście nie jest tak naprawdę zaletą i że istnieje algorytm, który zawsze pozwala Blackowi wygrać z najlepszą grą białych - ale od razu powinno być oczywiste, że nie ma algorytmu, który mógłby zawsze pozwala wygrać, czy czarny czy biały. Dlatego ludzie mówią o „najlepszym możliwym wyniku”, ponieważ „zwycięstwo z obu stron” jest banalnie niemożliwe.

— Steven Stadnicki

23

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.

— Yuval Filmus
źródło

tak, rzeczywiście, ale próbowałem odpowiedzieć na każdą odpowiedź innym pytaniem, co się stanie, gdy obaj gracze będą grać z optymalnym algorytmem ???? co się stanie, jeśli gracz znajdzie sposób na pokonanie optymalnego algorytmu?

— John Demetriou,

11

@JohnDemetriou Gdy obaj gracze będą grać optymalnie, osiągniesz pewien wynik. Ten wynik nazywa się wartością gry. Jeśli szachy są białą wygraną, oznacza to, że nic czarnego nie byłoby w stanie pokonać białego gracza grającego optymalnie. Biały faktycznie ma ogromną książkę (lub jest w stanie wykonać ruch z takiej książki obliczeniowo), która zawiera idealny licznik dla każdego ruchu, jaki czarny może wykonać w każdej możliwej sytuacji, która rozwija się od początku gry. BTW, chillax na znakach zapytania. Wystarczy jedno zdanie.

— rrenaud,

Przepraszam za znaki zapytania. Tak po prostu piszę w ogóle. Co jeśli szachy są najbardziej optymalną wygraną. Jeśli biały i czarny mają tę samą książkę i te same liczniki? Co się wtedy stanie?

— John Demetriou,

1

@JohnDemetriou „Optymalny” oznacza „najlepszy z możliwych”. Jeśli matematycznymi konsekwencjami reguł szachowych jest to, że najlepsza czerń, jaką można zrobić wbrew optymalnej bieli, to losowanie (lub nawet może opóźnić zwycięstwo bieli tak długo, jak to możliwe), to optymalny algorytm dla czerni jest tym, który to osiąga, i jest w stanie wygrać z większością nieoptymalnych przeciwników.

— Ben,

1

@JohnDemetriou Możliwe, że istnieje algorytm, który zawsze wygrywa jako biały ; oczywiście ten algorytm nie zawsze mógł wygrać jako Czarny z powodów, które zostały już przedstawione (ponieważ grałby przeciwko sobie). Możliwe jest nawet, że okaże się, że czarne „wygrane” szachy zostały doskonale zagrane i że istnieje algorytm gwarantujący wygraną dla czarnych przeciwko dowolnej opozycji. Jeśli masz na myśli „algorytm, który zawsze wygrywa z obu stron”, sugeruję użycie tej terminologii; „optymalny” ma już dobrze zdefiniowane znaczenie.

— Steven Stadnicki,

8

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!

— sjmeverett
źródło

6

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

— Piotr
źródło

1

Rzeczywiście bardzo interesujący artykuł!

— Paresh,

To nie jest optymalny algorytm. Pytam, czy kiedykolwiek może istnieć optymalny algorytm (jeśli mamy moc obliczeniową)

— John Demetriou,

1

Racja, a biorąc pod uwagę twoją definicję „optymalnego algorytmu” jako algorytmu, który zawsze wygrywa, taki algorytm nie może istnieć dla obu graczy, czarno-białych. Oprócz większego (ale skończonego) drzewa gry, pod tym względem nie ma nic specjalnego w szachach w porównaniu do innych gier, takich jak na przykład Hex, dla których rozwiązanie jest już znane: jeśli pierwszy gracz stosuje optymalną (znaną) strategię gry w Hex , wtedy pierwszy gracz zawsze wygrywa, bez względu na algorytm używany przez drugiego gracza.

— Piotra,

Artykuł w sprawie King Gambit okazał się mistyfikacją. Zauważ, że artykuł zaczyna się „31 marca autor programu Rybka, Vasik Rajlich i jego rodzina przeprowadzili się z Warszawy do Polski w nowym mieszkaniu w Budapeszcie na Węgrzech. Następnego dnia, pomimo zgiełku przenoszenia pudeł i ustawienia w górę połączenia telefoniczne i internetowe Vas, uprzejmie zgodził się na następujący wywiad "- innymi słowy, było to 1 kwietnia ...

— Joe K

-1

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 .

— Geek Luke
źródło

Chociaż inne odpowiedzi nie odnoszą się wprost do minimax, niektóre odnoszą się do linków, które ostatecznie prowadzą do nich lub przycinania alfa-beta, algorytmu do wydajniejszego wdrożenia minimax. Co dodaje ta odpowiedź, której jeszcze nie powiedziano?

— Dyskretna jaszczurka

-3

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

— vzn
źródło

teoretycznie moje pytanie zaczęło się, powiedzmy, że mamy moc obliczeniową, łączymy połowę komputerów świata, aby pracować jako klaster dla białych, a drugą dla czarnych ....

— John Demetriou

1

koleś, działa nawet wtedy, gdy podłączysz każdy superkomputer, który teraz istnieje lub kiedykolwiek istnieje. twoje pytanie sprowadza się zatem do teorii „jeśli teoria była fałszywa ...” (w tym z fizyki) w gruncie rzeczy mówi oczywiście, że nie można obliczyć (daleko) większej liczby ścieżek niż atomów we wszechświecie, teraz czy kiedykolwiek w przyszłości ,

— vzn 12.12.12

3

prawda, ale pytanie zaczyna się od POWIEDZMY, ŻE MAMY MOC KOMPUTEROWĄ, czy można to zrobić? to jest rzeczywiste pytanie, jeśli mamy moc, czy może istnieć algorytm?

— John Demetriou,

+1 za stwierdzenie, że fizycznie niemożliwe jest uzyskanie mocy obliczeniowej niezbędnej do dokładnego rozwiązania szachów. Ponadto nie wiem, dlaczego wszystkie -1 z tą odpowiedzią, myślę, że jest sprawiedliwe i zapewnia dobry wgląd w inne odpowiedzi.

— Alejandro Piad