Pytanie:
Czy ktoś próbował scharakteryzować szachy matematycznie?
postoronnim
2019-12-10 02:02:49 UTC
view on stackexchange narkive permalink

Od lat bycia studentem, badaczem i praktykiem szachów czuję, że ma kompletność i elegancję, które można znaleźć w matematycznych dowodach i teoriach. Tak więc wydaje się naturalne, że wyobrażenie sobie, że powinno być możliwe opisanie szachów w kategoriach matematycznych. Rozumiem przez to elegancki opis, jak zwarty zestaw formuł lub dowód, że szachy należą do takiej a takiej dziedziny matematyki. Intuicyjnie wydaje się, że powinien pasować do teorii grup. Czy ktoś wie, jakie próby podjęto w tym zakresie? Chciałbym konkretnie wykluczyć silniki, sieci neuronowe itp. Z dyskusji, ponieważ pomimo oczywistego sukcesu w zwiększaniu jakości gry, próby te nie stanowią teoretycznego dowodu.

Gdybyśmy mieli coś zbliżonego do matematycznego dowodu na temat szachów, czy nie sądzisz, że partia zostałaby rozwiązana? Gdyby istniał pełny opis gry, analogicznie do pełnego opisu grupy, bylibyśmy w stanie stworzyć znacznie lepsze silniki niż te oparte wyłącznie na heurystyce.
@ NoseKnowsWszystko wiem, że gra nie została rozwiązana. Moje pytanie dotyczy prób tego.
@Rewan Demontay To zdecydowanie coś. Ciekawi mnie jednak kompletne rozwiązanie, a przynajmniej próby. Mam tylko przeczucie, że szachy lub ich elementy, takie jak figury i pozycje, mające symetrie, takie jak grupy w teorii grup, mogą być potencjalnie zaklasyfikowane jako zbiór tych grup. Co więcej, będąc kompletną teorią grup, co oznacza, że ​​zawiera ona dowolny obiekt matematyczny, można odkryć niektóre wcześniej niewidziane właściwości szachów.
Wygląda bardziej jak teoria grafów, z (skierowanymi) strzałkami wskazującymi, które pozycje można osiągnąć jednym ruchem z innej pozycji. Nie sądzę, aby istniał jakikolwiek związek między teorią grup a szachami; mają zupełnie inne cechy (na przykład akcje w szachach są na ogół nieodwracalne).
Czy nikt nie wspomniał jeszcze o [stronie wikipedii na ten temat] (https://en.wikipedia.org/wiki/Solving_chess)?
@NoseKnowsAll: „sformułowanie matematyczne” jest dalekie od „matematycznego dowodu”. Jest wiele rzeczy, o których matematycy mówią szczegółowo bez posiadania dowodów.
Widziałeś wielomian wieży?
Pięć odpowiedzi:
#1
+30
Laska
2019-12-10 13:38:13 UTC
view on stackexchange narkive permalink

Istnieje wiele różnych aspektów szachów, które można sformalizować matematycznie. Przynajmniej od XIX wieku szachy były eksploatowane jako źródło innowacji matematycznych. Mówiąc więc o matematycznej charakterystyce szachów, nie jest to pojedynczy model, o którym mówimy, który obejmuje każdą cechę, ale raczej szereg modeli, w których moc każdego jest paradoksalnie odpuszczenie jakiegoś aspektu szachów, który nie jest istotny dla tej analizy.

Być może najwcześniejszym sukcesem (nie licząc :-) ziaren ryżu na szachownicy) był Twierdzenie Zermelo (tak przez jednego z twórców teorii zbiorów ZF), które stwierdza, że ​​w szachach „albo białe mogą wymusić wygraną, albo czarne mogą wymusić wygraną, albo obie strony mogą wymusić przynajmniej remis”.

Teoria gier kombinatorycznych (opracowana przez wybitnych matematyków Johna H. Conwaya, Elwyn Berlekamp i Richarda Guya) została z powodzeniem zastosowana w szachach. Jednak kilka założeń tej teorii jest sprzecznych z jej ogólnym zastosowaniem do szachów. Jednym z nich jest to, że wygrana w CGT ma miejsce wyłącznie wtedy, gdy przeciwnik nie może się poruszyć, co nie rozwiązuje problemu impasu. Po drugie, istnieje pojęcie „pociągającego za sobą posunięcie” (np. Czek), w którym jeśli jedna osoba gra, to drugi gracz musi odpowiedzieć, a nie pierwszy gracz ponownie. Ale Noam Elkies uzyskał pewne nietrywialne wyniki w końcówkach szachów, obliczając ich wartość CGT - odniesienia podane na jego stronie szachowej http://www.math.harvard.edu/~elkies/chess.html : „O liczbach i końcówkach” i „Wyższe nimbers [sic] w grach pionowych na dużych szachownicach”.

Wspomniałeś o teorii grup - co ciekawe, zestaw gier kombinatorycznych w składzie tworzy grupę abelową! Szczerze mówiąc, dwie wyżej wymienione przeszkody uniemożliwiają szachom takie zachowanie.

Wokół szachownicy wykonano ogromną ilość kombinatorycznej pracy. Vaclav Kotesovec opublikował w Internecie 800-stronicową książkę just na temat nieatakujących figur szachowych (uogólniając masowo problem 8 dam). Link znajduje się pod adresem http://www.kotesovec.cz/. Jest to związane z magicznymi kwadratami, projektowaniem eksperymentalnym itp.

Istnieje również, zaczynając w Finlandii z Eero Bonsdorffem, długi rodowód problemów szachowych z wyliczaniem ścieżek, liczący liczbę sposobów, w jakie można osiągnąć pozycję . Często wiąże się to z analizą Standard Young Tableaux, które stanowią również podstawę teorii reprezentacji grup symetrycznych. Często spotykane są tu liczby Fibonacciego, katalońskie i Eulera, a także inne kombinatoryjne tożsamości, których urzeczywistnienie kryje się w genialnych szachowych kompozycjach. Zobacz https://pdb.dieschwalbe.de/search.jsp i wpisz g = 'mathematics' w polu wyszukiwania.

Problem z trasą rycerza jest również znany z pomocy popchnąć badanie grafów Hamiltona, a zwłaszcza wyzwanie polegające na policzeniu liczby takich obiektów. Zobacz https://www.mayhematics.com/t/t.htm.

Teoria obliczeń pyta również o to, czy szachy są zdeterminowane. Chodzi o to, aby układać zestawy elementów w znacznie większe plansze, aby spróbować wykonać maszyny odpowiadające maszynom Turinga. To prowadzi nas do tematu granic obliczeń, w którym chciałbym zwrócić uwagę na to, że jeśli teoria matematyczna całkowicie charakteryzuje szachy, to nie powinniśmy być bardziej w stanie z nią dyskutować, niż sami gramy w szachy. To może pozwolić nam uciec przed niektórymi językowymi wyzwaniami obecnego prawa (np. Czy pionki mogą być zorientowane).

Myślę, że matematyczny opis tego, jak konwencje szachowe konsekwentnie stosuje się do problemów szachowych, w tym szachów z bajki, ma również wartość badawczą. Guus Rol ma bardzo ambitny program, który redukuje każdą turę do „mikro-faz” i twierdzi, że jest w stanie z dużą dokładnością określić, jak bajkowe warunki oddziałują na siebie w złożonych sytuacjach „retroaktywnych”, w których konieczna jest zarówno logika wstecz, jak i do przodu. Nie wiem, czy kiedykolwiek dokończy swoją teorię.

Osobiście chciałbym zobaczyć skromniejszą teorię, która traktuje każdy ruch jako atomową i chociaż nie obejmuje tak dobrze bajkowych szachów, na najmniej może obejmować działające wstecz aspekty konwencji problemowych, takich jak roszada i ep Nawet to nie zostało jeszcze zrobione.

Fizyk matematyczny Roger Penrose opublikował stanowisko szachowe około 2 lata temu, które miało na celu udowodnienie jego długo utrzymywanego stanowiska, że ​​istnieje zasadniczo inny rodzaj rozumowania prezentowany przez ludzi niż sztuczna inteligencja ugruntowana w „funkcjach obliczeniowych” może zademonstrować. Zobacz https://en.chessbase.com/post/a-chess-problem-holds-the-key-to-human-consciousness

Mimo że teoria losowości wykresy, a analiza Monte Carlo została z powodzeniem zastosowana w silnikach, zwłaszcza najnowszej generacji, nie sądzę, że to dyskwalifikuje ją jako teorię matematyczną.

Istnieje również podejście algebry liniowej do liczenie ruchów i pozycji. „Jeśli szachy są wykresem, jaka jest jego maksymalna wartość własna?” to bardzo realne i interesujące pytanie. Zobacz witrynę Francois Labelle pod adresem http://wismuth.com/chess/statistics-games.html

Algebra liniowa może być z powodzeniem stosowana do innych pytań związanych z szachami, np. na ile jest sposobów, aby wieża przemieściła się z a1 na h8 dokładnie w n ruchach? A co z królem?

Od wielu lat Noam Elkies & Richard Stanley współpracuje nad książką o szachach i matematyce. Nie wiem, kiedy to się wreszcie pojawi, ani czy zrezygnowali z tego. Ale „Matematyczny rycerz” podany na stronie szachowej Noama, do której linkował wcześniej, może daje przedsmak tej książki. Richard Stanley jest jednym z czołowych liderów w dziedzinie kombinatoryki: patrz http://www-math.mit.edu/~rstan/chess/queue.pdf i artykuł urodzinowy Noama https: / /arxiv.org/pdf/math/0508645.pdf

Istnieje również książka „Mathematics and Chess” autorstwa Miodraga S. Petkovicia, ale nie znam jej zawartości.

Niektóre z tych pomysłów są wymienione na stronie Wikipedii: https://en.wikipedia.org/wiki/Category:Mathematical_chess_problems oraz bardziej szczegółowa strona https : //en.wikipedia.org/wiki/Mathematical_chess_problem.

Jeśli ktoś ma inne przykłady szachów i matematyki, wspomnij o nich w komentarzach, a spróbuję uwzględnić je w tej odpowiedzi . Jeśli ktoś ma linki ilustrujące tematy, o których wspominam, dodaj je, dziękuję.

Wreszcie: math.stackexchange.com ma 62 strony szachowych wpisów!?!

Szukałem tych matematycznych i kombinatorycznych analiz teorii gier, które naprawdę skupiają się na szachach (a które nie skupiają się na grach kombinatorycznych w ogóle) przez kilka lat. Nie znalazłem wielu wyników. Czy znasz jakieś konkretne książki / artykuły na ten temat?
Cześć anionie, najlepsze są dwie kartki z końcówek Noama Elkiesa - dodałem link do jego strony szachowej, która zawiera szczegółowe informacje.
#2
+8
Mason
2019-12-10 11:09:39 UTC
view on stackexchange narkive permalink

Oto kilka punktów początkowych w czytaniu o teorii gier, która jest matematycznym narzędziem, które byłoby najbardziej odpowiednie do formułowania twierdzeń dotyczących szachów.

To jest lekka historia wczesna teoria gier. Szachy to „doskonała gra informacyjna” i jest kilka interesujących rzeczy, które można powiedzieć o tej kategorii gier. Zobacz na przykład to. Czytałbym też o Claude Shannon. liczba Shannona wyznacza ograniczenie w drzewie złożoności gry. W przypadku standardowych szachów mamy trudną łamigłówkę, ale możesz zrobić mniejsze warianty i rozwiązać te mniejsze partie. Oto przykład tego. Autorzy twierdzą, że rozwiązali mniejszą odmianę szachów 5x5.

#3
+3
yobamamama
2019-12-10 04:09:53 UTC
view on stackexchange narkive permalink

Niezupełnie. Przynajmniej nie poważni matematycy.

Jest to nieco omówione w teorii gier, ale inne podejścia, takie jak teoria grup, nie wydają się pasować; chociaż można znaleźć nieliniowy opis typu wyższego wymiaru.

Algebra, która obejmuje grupy, a także topologię, wydaje się być niedostępna, ale być może pasowałaby do analizy, gdyby ktoś chciał ją wypróbować. Ale to byłby zaawansowany matematyk, który byłby bardziej skłonny do podjęcia lepszego problemu, który doprowadziłby do doktoratu i nauczania zawodu.

Dzięki za wgląd. Jeśli taka próba się powiedzie, powinna wzbudzić duże uznanie. Pomyśl tylko, ilu ludzi zmagało się do tej pory z rozwiązaniem tego problemu.
@postoronnim - Byłoby warte uznania. Nie jestem pewien, ilu wykwalifikowanych ludzi na poważnie próbowało rozwiązać ten problem.
[Noam Elkies] (http://www.math.harvard.edu/~elkies/chess.html) przychodzi na myśl.
#4
+3
orlp
2019-12-10 20:15:53 UTC
view on stackexchange narkive permalink

Nie chciałbym tego mówić, ale mówiąc matematycznie w szachy, gdy gramy, są one bardzo nudne. Jest to doskonała gra informacyjna, bez determinizmu, dla dwóch graczy na zmianę. Oznacza to, że szachy to albo wygrana białych, wygrana czarnych, albo remis. Optymalna strategia szachowa jest banalna i znana: minimaks. Jeśli chodzi o matematykę, szachy są rozwiązane.

@emory - bo faktycznie _wykonanie_ optymalnej strategii jest obliczeniowo niewykonalne? (z powodu wybuchu kombinatorycznego)
@emery - może mylisz sposób wykonywania matematyki ze sposobem wykonywania innych prac? Pomyśl: Inżynier, fizyk i matematyk pracują, gdy przed ich biurami wybucha mały pożar. Fizyk przeprowadza kilka szybkich obliczeń i używa ich tylko tyle, aby ugasić pożar. Matematyk widzi pożar, spogląda w stronę gaśnicy i mówi: „istnieje rozwiązanie!” następnie wraca do swojego biura.
@emory Nie rozumiesz. Dzięki minimaxowi nie tylko wiemy * co robić * (czyli zdobyć więcej punktów w koszykówce czy zadać mata przeciwnika w szachach), ale także wiemy * jak dokładnie to zrobić *. Po prostu wiemy, że jeśli przed każdym możliwym ruchem w szachy zagramy wszystkie możliwe kombinacje rozwoju gry, a następnie wybierzemy najlepszą, stosujemy ** najlepszą możliwą ** strategię. To jest algorytm minimax w pigułce. I to bardzo różni się od twojego przykładu koszykówki.
@Firzen,, ale jeśli nie przejmujesz się takimi rzeczami, to tak, szachy są rozwiązane.
@emory * „Jeśli dobrze pamiętam, taki komputer byłby wielokrotnie większy od naszego Układu Słonecznego i działałby wiele milionów ludzkich istnień. Czy nie jest tak, że taka maszyna byłaby tak masywna, że ​​utworzyłaby czarną dziurę i wyniki jego obliczeń nie mogły uciec od horyzontu zdarzeń. ”* Nie byłbym tego taki pewien. Zresztą… budowa komputerów to raczej dyscyplina fizyczna. Być może nie mamy * wydajnego * najlepszego algorytmu szachowego, ale mamy przynajmniej kilka. Tak więc, jak wspomniano powyżej, matematycznie szachy są rozwiązywane.
@emory Nie, minimax w ogóle nie wymaga dużej ilości pamięci. Twój telefon komórkowy ma moc obliczeniową, aby optymalnie rozwiązywać szachy - wymaga to po prostu długiego, długiego, długiego czasu. I nawet gdybyś potrzebował ogromnego komputera aż do śmierci wszechświata na gorąco, matematyka to nie problem.
Ponadto, biorąc pod uwagę przycinanie alfa beta, dobrą heurystykę ruchu i tabelę transpozycji, wystarczy spojrzeć na około 10 ^ 30 różnych pozycji. To tylko około 2 ^ 100, co jest trudne do wykonania, ale wcale nie jest trudne. Jest mniej więcej na poziomie złamania 256-bitowego szyfrowania.
#5
-3
David Richerby
2019-12-11 02:56:47 UTC
view on stackexchange narkive permalink

Szachy nie są przedmiotem zainteresowania matematyków. Matematycy przejmują się problemami, które są w jakiś sposób nieskończone: albo nieskończonymi przedmiotami, albo skończonymi obiektami, których przykładów jest nieskończenie wiele. Szachy są całkowicie ograniczone. Jest tylko jedna szachy, korzysta z skończonej szachownicy, istnieje nieskończenie wiele możliwych pozycji. Jeśli w szachy gra się racjonalnie (i nie możemy mieć nadziei na scharakteryzowanie ich bez tego założenia), to gry mają skończoną długość. „Racjonalne” oznacza w zasadzie, że którykolwiek z graczy zażąda remisu, gdy tylko będzie miał do tego prawo, a to oznacza, że ​​w grach jest mniej niż około 5900 posunięć, co oznacza, że ​​jest ich skończenie wiele. Matematyk mógłby studiować liczby pierwsze, ale nie będzie studiował pojedynczej liczby 1827368429.

Dla matematyka „rozwiązywanie szachów” to tylko obliczenia, a matematycy nie są zainteresowani obliczeniami. Fakt, że jest to kalkulacja ważna z kulturowego punktu widzenia, może zachęcić kogoś do podjęcia próby, ale trudno wyobrazić sobie, by ktokolwiek miał czas na zrobienie czegoś tak skomplikowanego. Jest to coś, co wymagałoby dziesięcioleci pełnoetatowej pracy, a gdyby ci się nie udało, w zasadzie nie miałbyś nic.

Duża matematyka nie ma problemu ze skończonymi rzeczami, jest mnóstwo przykładów, jeśli się rozejrzysz. Pytanie nie dotyczy obliczeń ani obliczeń, chodzi o nadanie szachom teoretycznych podstaw w dziedzinie matematyki.
@postoronnim Przykłady, takie jak co? Podałem wam podstawę teoretyczną: to pojedynczy obiekt skończony.
Skończone przestrzenie prawdopodobieństwa, macierze, modele, grafy skończone, lista jest długa.
@postoronnim Jest ich nieskończenie wiele. Jest tylko jedna szachy. Tak jak istnieje nieskończenie wiele liczb pierwszych (z których każda jest skończona), ale tylko jedna 1827368429. Są tysiące matematyków, którzy badają liczby pierwsze, a żaden nie studiuje 1827368429 w izolacji.
„Matematycy [tylko] przejmują się problemami, które są w jakiś sposób nieskończone”. Przepraszam, ale opierając się na moim doświadczeniu w matematyce, jest to albo całkowicie błędne, albo strasznie błędne. Proponuję wyjaśnić swój punkt.
@YiFan Wyjaśniłem to w części zdania, którego nie zacytowałeś ... Jeśli jest strasznie błędne, podaj mi listę przykładów matematyków badających pojedynczy obiekt skończony.
Stanislav Ulam opisał siebie jako: „czysty matematyk, który upadł tak nisko, że jego najnowsza praca faktycznie zawierała liczby z przecinkiem”
@DavidRicherby `Jeśli w szachy gra się racjonalnie (i nie możemy mieć nadziei na scharakteryzowanie ich bez tego założenia), to gry mają skończoną długość`. Myślę, że możemy osłabić to założenie w oparciu o zasadę: `` Każdy gracz może zadeklarować remis, jeśli wykonano 50 ruchów szachowych (50 białych i 50 czarnych), a żaden ruch pionkiem lub bierka nie został zbity. '' Jeśli to zmodyfikujemy reguła od „może zadeklarować” do „musi zadeklarować” wtedy gracze mogą być nieracjonalni i gra nadal będzie skończona.
O. W takim razie jestem pewien, że źle odczytałem twoje pismo.
Powszechne jest umieszczanie obiektu skończonego w wygodnym uogólnieniu i badanie tego. Kiedy teoretycy gier twierdzą o złożoności obliczeniowej takiej gry, jak szachy, go, warcaby itp. Mówią o grze rozgrywanej na planszy n na n.
@Mason Racja. Ale te analizy asymptotycznych wymagań dotyczących zasobów przy rozwiązywaniu szachów na szachownicy n-po-n nic nam nie mówią o szachach na szachownicy 8 na 8, o to właśnie chodzi w tym pytaniu.
Masz rację, rzucając mi wyzwanie, bym znalazł podstawowy element mojej krytyki: pozwól mi odpowiedzieć w może dziwny sposób. Matematykę można sformułować w ten sposób (trochę / tylko czasami). Wybieramy założenia, których chcemy, ponieważ budują one typ struktur, które chcemy ... Jeśli założymy, że PO pyta o „(A) Tylko szachy w swojej standardowej formie” i „(B) matematycy nie są zainteresowani w obliczeniach ”. Wtedy odpowiedź, którą napiszemy, powinna być typu, który napisałeś. Ale przyjęcie tych założeń nie wydaje się być pytaniem, na które chcę odpowiedzieć.
Wiem, że to może dziwna krytyka, ale kiedy czytam twoje pismo, wydaje mi się, że przyjmujesz pewne założenia / ograniczenia, których OP niekoniecznie umieścił w ich pytaniu. Dlaczego więc nie zakładamy, że PO zadał istotne pytanie, które mogłoby mieć „Tak! Ale naturalnym posunięciem matematycznym byłoby zbadanie uogólnienia…” - odpowiedź. W przeciwieństwie do odpowiedzi „Nie. Ponieważ wydaje się, że nie rozumiesz tego typu rzeczy…”. Jeden wydaje się bardziej zachęcający.
@Mason To rozsądna krytyka. Nie wydaje mi się, żebym naprawdę dodawał ograniczenia, ale raczej odpowiadam na zadane pytanie. Sugerujesz uogólnienie pytania, aby uzyskać bardziej interesującą odpowiedź, z którą się zgadzam, i jest to również całkowicie rozsądne podejście.
Doceniam, że poświęciłeś czas na przeczytanie krytyki. I szanuję pragnienie, aby odpowiedzieć dokładnie na to, o co zostało zapytane, zamiast robić zbyt wiele nieuzasadnionych domysłów, do czego zmierzają.


To pytanie i odpowiedź zostało automatycznie przetłumaczone z języka angielskiego.Oryginalna treść jest dostępna na stackexchange, za co dziękujemy za licencję cc by-sa 4.0, w ramach której jest rozpowszechniana.
Loading...