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


109

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


1
+1: doskonały temat. Uważam jednak, że powinno to zostać uwzględnione na wiki, o czym świadczy różnorodność i ilość odpowiedzi.
IAbstract

1
„myślisz, że wskazałem coś, co nie zostało jeszcze w zadowalający sposób udowodnione”? Na co wskazałeś, co nie zostało formalnie udowodnione?
S.Lott,

2
Ack! jak może być 20 różnych odpowiedzi na tak czarno-białe pytanie! (gra słów nie przeznaczona).
Peter Recore

5
Ja również jestem zdumiony liczbą ludzi, którzy publikują swoje spekulatywne odpowiedzi nieświadomi, że odpowiedź została w rzeczywistości określona matematycznie - odpowiedź w tym sensie, że udowodniono, że szachy mają rozwiązanie - po prostu nie jest praktyczne, aby to obliczyć.
DJClayworth

3
Przypomina mi żart o idealnym komputerze do gry w szachy. Grając na biało, myśli i myśli i myśli, a potem… rezygnuje!

Odpowiedzi:


104

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


22
Wszystkie końcówki zawierające 6 lub mniej elementów zostały wyliczone i rozwiązane. Zobacz tablebase i bitbase tutaj: en.wikipedia.org/wiki/Tablebase . Na przykład istnieje gra końcowa KQNKRBN, w której do wymuszenia mata potrzeba 517 ruchów! Ale całkowita liczba gier w szachy wynosi około (10 ^ (10 ^ 50)).
HTTP 410

2
Skrypt do wygrywania to jedno. Wyczerpująco wyliczone to co innego. Tak czy inaczej, informacja jest doskonała - wszystko jest znane - gra jest z definicji deterministyczna.
S.Lott,

11
@RoadWarrior: nie zgadzam się. Losowo dotyczy pogody. Bóg rzuca kośćmi. Losowość nie dotyczy szachów - z definicji. Szachy zawierają pełne informacje. Pogoda ma efekty kwantowe - nie może być kompletna.
S.Lott,

3
To, co utrudnia prognozowanie pogody, to chaotyczne czynniki nieliniowe, a nie efekty kwantowe. Mając wystarczającą moc obliczeniową i wiedzę, moglibyśmy teoretycznie stworzyć „poprawną” prognozę pogody.
HTTP 410

3
@monojohnny: Zasady zabraniają trzech powtórzeń tej samej pozycji. Szachy są po prostu skończone. Jest duży, ale ograniczony.
S.Lott

72

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.


2
+1, To naprawdę świetny sposób na wyjaśnienie tego. Nie mogę uwierzyć, że nigdy o tym nie pomyślałem!
Zifre

2
Dlaczego czarny nie mając doskonałej strategii oznacza, że ​​biały ma doskonałą strategię? A co z obaj graczami, którzy nie mają idealnej strategii? Gdyby twoje sugestie były prawdziwe, czy nie byłoby to prawdą w przypadku każdej gry na 2 graczy, co oznacza, że ​​każda gra ma idealną strategię?
John M Naglick

8
@john: Ponieważ szachy mają doskonałe informacje i nie zawierają elementów losowych (w przeciwieństwie do wielu, wielu innych gier 2-osobowych), jedynym sposobem na istnienie idealnej strategii dla czarnych jest to, że białe mogą wymusić wygraną pomimo jakiejkolwiek próby czarny - innymi słowy, jeśli istnieje idealna strategia dla białych.
Dave Sherohman

2
Właściwie ta logika nie zawsze się sprawdza, ale czy jest prawdą w tym przypadku.
BlueRaja - Danny Pflughoeft

4
@john "po co tyle dyskusji tutaj" - ponieważ niektórzy ludzie nie znają odpowiedzi, ale i tak piszą tutaj.
DJClayworth

30

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.


6
„[Y] ou nie niedługo” to trochę za mało. Oprócz limitu oczekiwanego czasu trwania wszechświata, masz problem z przechowywaniem - liczba stanów w szachach znacznie przekracza 500 miliardów warcabów; w rzeczywistości przekracza liczbę cząstek we wszechświecie.
Michael Dorfman

30
„[…] faktycznie przekracza liczbę cząstek we wszechświecie”. Dopóki nie przekracza liczby stanów cząstek we wszechświecie, wciąż jest nadzieja ;-)
Carsten

1
co się dzieje, gdy program, który zawsze zmusza przeciwnika do przegrania, gra przeciwko sobie ????
John Demetriou

1
@BCS hmm, a co, jeśli istnieje przewidywanie, w którym jeśli gram jako drugi gracz, a drugi używa tej samej heurystyki co ja, zastosuj tę heurystykę, aby wygrać i jeśli pierwszy gracz ma podobną heurystykę ???? ?
John Demetriou

1
mówię, że jeśli istnieje idealny algorytm i obaj gracze go mają, będzie nieskończona liczba prawdopodobieństw, że algorytm może się zmienić, aby był doskonały
John Demetriou

15

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.


Kto więc miał ochotę zlekceważyć moją odpowiedź? Czy jest w tym coś złego? Chcesz stanąć na czele?
ypnos

@ypnos, w ogóle nie zagłosowałem na twoją odpowiedź. Właśnie skomentowałem, aby powiedzieć, że nie pozwól, aby przypadkowi negatywni wyborcy cię nie zepsuli.
Zyskałeś

1
Kilka powodów do odrzucenia. 1) Wiadomo, że istnieje algorytm rozwiązywania gry, po prostu algorytm jest niepraktyczny do obliczania przy użyciu jakiejkolwiek możliwej technologii. 2) Rozwiązanie gry NIE oznacza, że ​​istnieje bezpieczna strategia. Kółko i krzyżyk jest rozwiązany, ale nie ma strategii dla drugiego gracza, która pozwoli uniknąć przegranej.
DJClayworth

2
„To nie jest kwestia komputerów, ale tylko gry w szachy”. Cóż, informatyka tak naprawdę nie dotyczy komputerów. Są tylko narzędziem. Informatyka działa bez komputerów.
Janus Troelsen

1
Jest to właściwie pytanie o komputery, ponieważ pytanie brzmi, czy może istnieć Maszyna Turinga (= komputer), która rozwiązuje szachy.
SDwarfs

14

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


3
No chodź. Musisz inaczej myśleć o problemie. Nie myśl o liczbie gier, ponieważ transpozycje i algorytmy alfa-beta i takie zmniejszają to ogromnie. Pomyśl o pozycjach na szachownicy (10 ^ 60) lub kombinacjach szachów (100 milionów). W przypadku obliczeń kwantowych to trywialne.
lkessler

2
Alfa-beta w tym kontekście (rozwiązywanie szachów) wymagałaby doskonałej funkcji oceny. Podobnie jest z pozycjami na planszy i kombinacjami pionków. Nie mamy doskonałej funkcji oceny, więc obliczenia kwantowe nam nie pomagają.
HTTP 410

1
Za każdym razem, gdy myślę, że coś jest „trywialne” i jestem pewien, że nikt tego nie zrobił, jestem też pewien, że przynajmniej raz się pomyliłem.
Dean J

2
@lkessler: Stanowiska w zarządzie nie mówią wszystkiego. Przynajmniej część historii gry jest niezbędna do wykonania roszady lub bicia w przelocie lub remisu z powodu braku bicia lub ruchu pionkiem, a cała historia do remisu przez powtórzenie. Co więcej, ponieważ ostatnio godnym uwagi wynikiem badań dla komputera kwantowego był współczynnik 15, powiedziałbym, że w tej chwili nic nie jest trywialne w obliczeniach kwantowych.
David Thornley

2
Dla porównania, jeśli możesz wygenerować wszystkie możliwe pozycje szachowe, możesz w trywialny sposób brutalnie wymusić dowolny szyfr z kluczem 128-bitowym, ponieważ 10 ^ 46 to około 2 ^ 152 lub 2 ^ 153. Istnieją doskonałe powody, by sądzić, że jest to niemożliwe przed śmiercią Wszechświata.
David Thornley

9

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.


8

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


9
„Czy wiesz, że sprzedaż płyt disco wzrosła o 400% w roku kończącym się w 1976 roku? Jeśli te trendy się utrzymają… AAY!” - Disco Stu
Jeremy Friesner

2
Prawo Moore'a - moc obliczeniowa podwaja się co 18 miesięcy - prawdopodobnie zawiedzie około 2015 roku. W przeciwnym razie projekt procesora komputera będzie musiał być radykalnie inny. Zatem rok 2080 nie jest realistycznym celem.
Philip Smith,

3
@Philip: Prędkości taktowania procesorów komputerów stacjonarnych wzrosły tylko nieznacznie od 2003 r., A ulepszenia od tego czasu dotyczyły głównie zwiększonej pamięci podręcznej i wielu rdzeni. Ponieważ procesor 3 GHz ma jeden cykl zegara w czasie, w którym światło porusza się o 4 cale / 10 cm, nie można oczekiwać, że szybkość zegara będzie rosła w nieskończoność. Co więcej, równoległość jest zazwyczaj trudna. Przewidywanie wykładniczego wzrostu przez pięćdziesiąt lat, kiedy zaczęło się psuć siedem lat temu, nie wydaje się być bezpiecznym zakładem.
David Thornley

1
@David - to wszystko prawda. Ale mija się z celem. Jeśli zmniejszysz o połowę komponenty chipa, elektrony wykonają dwa razy więcej przy tej samej częstotliwości zegara. To właśnie napędza prawo Moore'a.
Philip Smith

3
@Philip: Zmniejszenie o połowę nie może oczywiście trwać wiecznie. Atom krzemu ma około ćwierć nanometra średnicy, a produkcja chipów spadła już do dziesiątek nanometrów. Co więcej, na poziomach kwantowych cząstki podlegają regułom statystycznym, a nie absolutnym, więc konieczne jest poruszanie się po wystarczającej liczbie elektronów naraz, aby przywołać prawo dużych liczb. Jak dotąd prawo Moore'a znajdowało się gdzieś pomiędzy prawem a samospełniającą się przepowiednią, ale wkrótce się to skończy.
David Thornley,

7

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 :)


4
Technicznie rzecz biorąc, zasada pięćdziesięciu ruchów, jak powtórzenie w trzech ruchach (co również ogranicza rzeczy - istnieje skończona liczba możliwych pozycji, więc pomnożenie tej liczby przez trzy daje nam górną granicę) nie powoduje remisu. Raczej daje każdemu graczowi możliwość odebrania remisu. Zwykle zrobi to przegrany gracz, ale nie jest to wymagane. Dlatego gra jest całkowicie legalna: 1. Sc3 Sc6 2. Sb1 Sb8 3. Sc3 Sc6 4. Sb1 Sb8, powtarzane w nieskończoność. I jeśli się nie mylę, nie można obalić, że nie jest to wynikiem dwóch doskonałych algorytmów grających jako biały i czarny.
Lenoxus

6

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.


5

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.


1
Można to zrobić, ale czy można to zrobić na komputerze, który prawdopodobnie kiedykolwiek zobaczymy?
BCS

1
Prawdopodobnie nie za naszego życia. Wszystkie naprawdę interesujące badania w tej dziedzinie są przeprowadzane w grze Go. :)
Bill the Lizard

Większość sześciolatków IIRC może być dowolnym komputerem w Go.
BCS

2
@BCS: Już nie. Najlepsze programy Go pokonują teraz graczy na poziomie dan (profesjonalnych).
Bill the Lizard

1
@BlueRaja: To było w 2008 roku. Nie wiem, jaki jest obecny rekord, ale MoGo pokonał zawodowców 6 i 7 kamieniami na 19x19. ireport.cnn.com/docs/DOC-214010
Bill the Lizard,

5

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.


Tak pokonujesz dzisiejsze komputery w szachy. Jutro będzie lepiej. Zgadzam się jednak z Tobą, że Blondie24 jest fascynujące.
Bill the Lizard

Zagłosowano ponownie. Ten post nie zasługuje na ocenę negatywną.
Cybis

Niestety problem z grą w szachy jest zbyt duży, aby uczenie maszynowe mogło działać. Nigdy nie mogliby dostać programu do nauki szachów, aby nawet grać nowatorsko bez błędów. Heurystyka jest lepsza. Ale Brute Force było jeszcze lepsze. Uczenie maszynowe nauczyło się tylko na błędach w szachach.
lkessler

Programy szachowe nie popełniają krótkoterminowych błędów, a najlepsze programy grają lepiej niż mistrzowie świata. Myślę, że najnowsza wersja 64-bitowej Rybki jest oceniana jako 3200 ELO
Alex

5

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.



4
Technicznie jest to kombinatoryczna teoria gier.
Anaphory

5

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


5

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!


3

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.


Posiadanie niedoskonałych przeciwników nie jest prawdziwym problemem. To po prostu sprawia, że ​​idealny gracz wygrywa / remisuje (niezależnie od tego, jaki jest doskonały wynik) w mniejszej liczbie ruchów. Optymalny ruch w każdej pozycji jest zawsze lepszy lub równy innym możliwym ruchom (z definicji). Tak więc suboptymalne ruchy pozwalają przeciwnikowi osiągnąć optymalny stan końcowy (wygrana / remis) wcześniej lub nawet pozwalają wymusić lepszy wynik. Na przykład, jeśli czarne zawsze przegrywają, jeśli białe grają idealnie, możliwe jest, że czarne wygrywają, jeśli białe zagrają tylko jeden nieoptymalny ruch. Ale tak, powinno to nieco zwiększyć złożoność analizy.
SDwarfs

@Stefan - niedoskonali przeciwnicy to ogromny problem, jeśli zależy Ci na optymalnej grze. W szczególności możesz wyobrazić sobie sytuacje, w których faktycznie lepiej byłoby zagrać ruch przegrywający (tj. Ruch, w którym doskonały przeciwnik zdecydowanie by cię pokonał), jeśli wiesz, że prawdopodobieństwo popełnienia błędu przez przeciwnika jest wystarczająco wysokie.
mikera

moim zdaniem optymalna gra oznacza osiągnięcie możliwie najlepszego wyniku przy zerowym ryzyku. Twój przeciwnik jest prawdopodobnie „słaby”, ale kiedy zagrasz ten przegrywający ruch , może niestety przez przypadek zagrać dobry ruch. Dbanie o nieoptymalnych przeciwników ma znaczenie tylko wtedy, gdy istnieje tylko wybór między przegranymi ruchami, w których jeden z nich ma większe szanse na błąd (nieoptymalnej gry) przeciwnika, prowadząc w rzeczywistości do remisu lub wygranej.
SDwarfs

1
To nie jest zwykła definicja optymalności w teorii gier. Optymalny zwykle oznacza maksymalizację oczekiwanego wyniku. W takim przypadku optymalny gracz zaakceptuje pewne ryzyko, pod warunkiem, że uzyska średnio lepszy wynik .
mikera

W takim razie masz całkowitą rację!
SDwarfs

2

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.


Właściwie cytat jest właściwy. Programy analizują wszystkie możliwe ruchy obu stron na bieżącej pozycji i używają heurystyki, aby znaleźć dobry ruch, który poprowadzi grę w kierunku korzystnym dla komputera.
Bill the Lizard,

1
Nie, nie patrzą na wszystkie możliwe ruchy. Używają heurystyki ruchu zerowego, aby przyciąć drzewo.
Alex

2

„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ż


1
Będąc całkiem przyzwoitym szachistą i po dogłębnym przestudiowaniu problemu przez lata, jestem na 99,9% pewien, że idealna strategia szachowa dla obu graczy kończy się remisem (tak samo, jak zostało udowodnione w warcabach). Istnieją również dowody na to, że wraz ze wzrostem siły gracza rośnie odsetek remisów.
mikera


2

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.


1

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.


1
Twój m = 5898. Zasady szachowe FIDE określają, że musisz przesunąć pionka lub wziąć figurę (coś, co nieodwracalnie zmienia grę) co najmniej co 50 posunięć (zwane zasadą 50 ruchów) lub jeden z graczy może ubiegać się o remis. Obliczono, że najdłuższa możliwa gra to 5898 ruchów, jeśli obaj gracze współpracują i jak najszybciej zgłaszają remis. Kontynuacja gry nie ma sensu, jeśli obaj gracze mogą ubiegać się o remis. Jeśli gracz zauważy, że przegrywa, może zażądać remisu, dając ten sam wynik. Zobacz: chess.com/blog/kurtgodden/the-longest-possible-chess-game
SDwarfs

1
Uwaga: m = 5898 to liczba „ruchów”. Maksymalna liczba pół ruchów to (118-3) * 100 + 3 * 99 = 11797. Dowód można znaleźć tutaj (po niemiecku!): De.wikipedia.org/wiki/50-Z%C3%BCge-Regel# Schachmathematik
SDwarfs

1

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.


1

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!


0

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


5
Idealny ruch jest wybierany przez strategię „minmax”: jest to ruch, który maksymalizuje twój minimalny możliwy wynik (biorąc pod uwagę wszystkie możliwe ruchy, które może wykonać przeciwnik). Inaczej mówiąc, zakłada, że ​​przeciwnik również gra doskonale.
Nick Johnson

Jest to jednak interesująca kwestia. Czy może dojść do sytuacji, w której reakcja na najlepszy możliwy ruch postawiłaby Cię w niekorzystnej sytuacji, jeśli przeciwnik nie wykona najlepszego możliwego ruchu? Jakie ma to konsekwencje?
Nona Urbiz

Nie jestem matematykiem i niezbyt dobrym szachistą; Założyłem też, że w teorii (jeśli znane jest całe drzewo gry), odpowiedź brzmi „tak”. Jednak teraz, kiedy wspomniałeś o tym problemie [o wyborze innego gracza], czy to oznacza, że ​​system jest potencjalnie nieprzewidywalny? Czy w grze występuje środek, w którym drugi gracz może wymusić niekorzystną sytuację? Czy to trochę przypomina fakt, że Perceptron (sieć neuronowa) może nauczyć się „OR” i „AND”, ale nigdy nie może uchwycić „XOR”? Czy szachy są przykładem systemu „chaotycznego”? FWIW, IMHO Myślę, że w tym momencie odpowiedź brzmi „nie wiem”.
monojohnny

@Nona Z definicji ten ruch byłby najlepszym ruchem. Nie ma takiego założenia.
piccolbo,

@piccolbo: Lepszy jeden z najlepszych ruchów. W szachach są pozycje, na których wiele ruchów daje ten sam wynik (wygrana, remis lub przegrana w tej samej liczbie posunięć).
SDwarfs

0

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.


-1

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


-2

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


-3

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.