Matematyk z Harvardu rozwiązał epicki problem szachowy sprzed 150 lat

Matematyk z Harvardu rozwiązał epicki problem szachowy sprzed 150 lat

Z jednej strony szachy wydają się prostą grą: 64 pojedyncze czarne lub białe kwadraty, 16 pionów na stronę i dwóch przeciwników dążących do podboju.

Kop jednak trochę głębiej, a gra przedstawia niezwykle złożone możliwości, stawiając przed teoretykami szachów i matematykami wyzwania, które mogą pozostać nierozwiązane przez dziesięciolecia, a nawet stulecia.

W lipcu 2021 r. jedno z tych wyzwań zostało ostatecznie rozwiązane — przynajmniej do pewnego stopnia. Miał to na myśli matematyk Michael Simkin z Uniwersytetu Harvarda w Massachusetts problem z n-królowymi Wprawiało to w zakłopotanie ekspertów, odkąd wymyślono to po raz pierwszy w latach 40. XIX wieku.

Jeśli znasz swoje własne szachy, wiesz, że hetman jest najpotężniejszą figurą na szachownicy, zdolną do poruszania się o dowolną liczbę pól w dowolnym kierunku. Problem n-matek zadaje następujące pytanie: przy danej liczbie hetmanów (n), ile jest możliwych aranżacji, w których królowe są na tyle daleko od siebie, że żadna z nich nie może zabrać żadnej z pozostałych hetmanów?

Dla ośmiu hetmanów na standardowej planszy 8×8 odpowiedź to 92, chociaż większość tych hetmanów jest rotowanych lub odwróconych tylko przez 12 podstawowych rozwiązań.

A co z 1000 królowych na planszy o wymiarach 1000 x 1000 kwadratów? A może milion królowej? Przybliżone rozwiązanie problemu Simkina to (0,143 n)n Liczba matek pomnożona przez 0,143 do potęgi n.

To, z czym ci pozostało, nie jest dokładną odpowiedzią, ale jest tak blisko, jak to tylko możliwe. W przypadku miliona królowych liczba ta pojawia się po niej jako liczba składająca się z pięciu milionów cyfr – więc nie będziemy jej tutaj odtwarzać.

Prawie pięć lat zajęło Simkinowi wymyślenie równania, przy użyciu różnych metod i technik oraz kilku przeszkód na drodze do rozwiązania. W końcu matematyk był w stanie obliczyć dolne i górne granice możliwych rozwiązań przy użyciu różnych metod i stwierdził, że są one prawie identyczne.

READ  Microsoft Surface Pro 9 wymaga żmudnego balansowania • Rejestr

„Gdybyś mi powiedział, że chcę, abyś umieścił swoje hetmany w taki a taki sposób na szachownicy, byłbym w stanie przeanalizować algorytm i powiedzieć, ile rozwiązań pasuje do tego ograniczenia” Simkin mówi.

„Z formalnego punktu widzenia sprowadza to problem do problemu optymalizacji”.

Na początku Simkin i jego kolega Zur Luria pracowali w Szwajcarskim Federalnym Instytucie Technologii w Zurychu współpracować Na odmianie problemu n-królowych znanej jako problem cykliczny lub modułowy. Na tej figurze przekątne owijają się wokół planszy, więc hetman może odsunąć się po przekątnej od prawej krawędzi planszy i pojawić się na przykład po lewej stronie.

Daje to symetrię każdej hetmana do ataku, ale nie tak działa normalna szachownica: hetman w rogu szachownicy nie ma tylu kątów ataku, jak ten w środku.

W końcu mąż Przestań pracować nad problemem pętli (Chociaż opublikowali pewne wyniki), Simkin ostatecznie zaadaptował niektóre owoce tej pracy do swojego ostatecznego rozwiązania.

Badania wykazały, że w miarę jak plansze stają się większe i liczba hetmanów wzrasta, badania wykazały, że w większości dozwolonych konfiguracji hetmany mają tendencję do gromadzenia się wzdłuż boków planszy, z mniejszą liczbą hetmanów pośrodku, gdzie są atakowane. Ta wiedza pozwala na bardziej wyważone podejście.

Teoretycznie bardziej dokładna odpowiedź na zagadkę n-królowej powinna być możliwa – ale Simkin zbliżył nas do siebie niż kiedykolwiek i chętnie przekazuje wyzwanie komuś innemu do dalszych badań.

„Myślę, że osobiście przezwyciężyłem problem n-królowych przez jakiś czas, nie dlatego, że nie mam z tym nic wspólnego, ale po prostu dlatego, że marzyłem o szachach i jestem gotowy, aby kontynuować moje życie” Simkin mówi.

Rozwiązanie papierowe Simkin dostępne na serwerze prepress arXiv.

Halsey Andrews

„Lekarz gier. Fanatyk zombie. Studio muzyczne. Kawiarni ninja. Miłośnik telewizji. Miły fanatyk alkoholik.

Rekomendowane artykuły

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *