co się stanie, gdy zastosujemy najnowocześniejsze technologie do odwiecznej gry w szachy? A co się dzieje, gdy znudzony geek z nadwyżką mocy obliczeniowej przeprowadza własne dziwne domowe eksperymenty na grze?
w tym roku inżynier oprogramowania z Pensylwanii, który nazywa siebie Tom Murphy VII, postanowił stworzyć śmiesznie złe algorytmy gry w szachy, używając wszystkiego, od uczenia maszynowego i sieci neuronowych po darmową liczbę cykli procesora-a następnie przeciwstawił złe algorytmy sobie nawzajem, aby stworzyć ” turniej głupców.”
” to mój pomysł na zabawę… ” Murphy mówi w humorystycznym filmie opisującym eksperymenty.
pierwsze ruchy
W 2007 obronił doktorat z informatyki. w Carnegie Mellon — w tym samym roku uczniowie zaczęli organizować doroczną konferencję SIGBOVIK w Prima Aprilis. Sponsorowany przez „Association for Computational Heresy”, był rodzajem satyrycznej grupy zainteresowań, poświęconej fikcyjnemu badaczowi o imieniu” Harry Quizmaster Bovik”, i zawierał wezwanie do głupich artykułów na tematy takie jak ” sztuczna głupota.”
przez ostatnie 11 lat Murphy był starszym inżynierem oprogramowania w Google (w jego biurach w Pittsburghu). Ale w tym roku postanowił wrócić ponownie na konferencję Prima Aprilis – i znowu, przyczynił się do żartobliwych badań własnych.
Murphy chwali się z dumą, że niektóre z jego wcześniejszych prezentacji dotyczyły śmiesznych badań, które były „nie do odróżnienia od „prawdziwych” badań (na przykład pierwszy poziom Super Mario Bros. jest łatwy z uporządkowaniem leksykograficznym, a Podróże w czasie mają około 20 cytowań w „prawdziwych” badaniach akademickich).
ale to był rok, w którym Murphy zwrócił uwagę na Szachy.
niech rozpocznie się gra
w początkowej grze Murphy ’ ego ludzie mają zawiązane oczy, zmuszając ich do pamiętania, gdzie są figury. Ale jaki jest odpowiednik dla komputera? Mówienie, gdzie znajdują się części, ale nie Jakie są części (lub nawet jakiego koloru)…
oczywiście komputer nie byłby wyposażony w ruchy prowadzące do pozycji. Nawet nie wiedział, czyja to kolej. Tak, istnieje możliwość, że król komputera jest w check — w którym momencie prawie każdy ruch jest nielegalny z wyjątkiem ruchu, który prowadzi króla do bezpieczeństwa. Ale aby to obejść, Tom stworzył program, który generuje listę możliwych ruchów, uszeregowanych według preferencji — z których zostanie wybrany pierwszy legalny ruch.
„lubię grać przeciwko niemu, bo nie jest zbyt dobry” – mówi Murphy w filmie. „Ale naturalne pytanie brzmi: jak to nie jest bardzo dobre?”Testowanie go z programami do gry w szachy dowodzi, że tak, przegrywa z wielką regularnością – tak jak za każdym razem.”
następnie postanowił zbudować inne złe algorytmy gry w szachy, aby mógł porównać ich względną wydajność…
jeden z nich preferował umieszczanie swoich figur na białych kwadratach, gdy gra biały, i na czarnych kwadratach, gdy gra czarny. (Jego przeciwnik? Algorytm, który wolał umieszczać swoje kawałki na przeciwstawnie kolorowych kwadratach.) W końcu obaj grali dość źle. „Mają preferencje, ale tak naprawdę nie ma to nic wspólnego z wygrywaniem.”W rzeczywistości oba są nieco gorsze od algorytmu, który wybiera swoje ruchy losowo.
jeśli uważasz, że mój skomplikowany 42-minutowy film o 30 dziwnych algorytmach szachowych rywalizujących w turnieju głupców, aby ocenić mój program, który gra w szachy, nie wiedząc, jakie figury są na planszy, jest nudny, to dlatego, że nie rozumiesz sztuki:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) lipiec 15, 2019
istnieją również dwa algorytmy, które nazwał „Huddle” i „Swarm” – w których jeden zautomatyzowany gracz szuka ruchów trzymających swoje figury blisko własnego króla, podczas gdy drugi szuka ruchów umieszczających swoje figury blisko króla przeciwnika. Czasami prowadzi to do tego, że król Huddle jest zmuszony podążać za własnymi pionkami na całej planszy, przy czym przynajmniej w kilku przypadkach jego pionek przypadkowo awansował na potężniejsze pionki i nieumyślnie sprawdzał przeciwnika.
ale częściej działa to w drugą stronę. „Jeśli masz preferencje, aby zaatakować przeciwnika, masz zamiar przypadkowo go mat czasami.”W filmie Murphy ujawnia, że wśród złych algorytmów szachowych, ten jest zaskakująco nie tak zły. „’Rój’ jest w rzeczywistości znacznie lepszy niż ’ losowy ruch.'”
i jeszcze jedna udana strategia to algorytm, który priorytetyzuje cztery konkretne rodzaje ruchu (w tej kolejności): SZACH MAT, check, capture a piece, lub push into its oponent ’ s territory.
ale są też inne straszne pomysły — jak algorytm, który stara się odbić kawałki przeciwnika lub przenieść wszystkie jego kawałki na drugą stronę planszy. Jeden algorytm po prostu wybiera, który ruch jest pierwszy w kolejności alfabetycznej.
i jest jeszcze inny algorytm, w którym każdy ruch jest wybierany z listy możliwych ruchów – z wyborami dyktowanymi arbitralnie cyframi pi…
przetrwanie w szachach
ale ostatecznie jego najbardziej rozbudowany algorytm zaczął się od pytania: która pojedyncza szachownica najprawdopodobniej „przetrwa” – pozostanie na planszy do końca gry i wyjdzie zwycięsko ze wszystkimi innymi szachownicami? Sumiennie badając odpowiedź, Murphy złożył wizytę na stronie free / libre chess LiChess.org (który obecnie widzi ponad milion gier dziennie). Oferuje również gry do pobrania-więc Murphy pobrał wszystkie 506,000,416 z nich.
podsumował wyniki w pracy „Survival in Chessland”, która wyjaśnia jego metodologię. Murphy pobrał wszystkie Kompletne gry, które mieli do listopada 2018 roku-chociaż kolejne 200 milionów stało się najwyraźniej dostępne w ciągu ośmiu miesięcy od tego czasu. Nawet jego listopadowe zdobycze reprezentowały aż 875 GB partii szachowych,” więc przetwarzanie ich wymagało trochę wydajności i równoległości”, mówi Murphy w filmie.
” na szczęście mam komputer z obsceniczną liczbą rdzeni i naprawdę nadmierną pamięcią RAM, więc musisz użyć tego do czegoś.”
Er, jak nieprzyzwoicie? W e-mailu opisuje swój „darmowy” system domowy, 32-rdzeniowy AMD ThreadRipper 2990wx. Uruchamianie wielowątkowych programów C++ przez kilka godzin wystarczyło, aby schrupać cały zestaw danych. „Myślę, że ludzie nie doceniają tego, co można zrobić wydajnie za pomocą jednej maszyny!”
„praca jest dość prosta: Analizuję PGN (który opisuje grę), następnie wykonuję ruchy w grze, śledząc losy każdego elementu, a następnie sumuję liczby dla każdego losu…”
„zasadniczo napisałem cały kod od zera, ponieważ jest to bardziej zabawne niż doprowadzenie kodu innych ludzi do działania. :)”
Analiza „przeżywalności” Murphy ’ ego stworzyła naprawdę piękne wizualizacje danych, pokazujące prawdopodobieństwo przeżycia każdej figury szachowej na każdym z 64 pól (z kolorami wskazującymi prawdopodobieństwo znalezienia się na tym polu na końcu gry.)
doprowadziło to do powstania bardziej złych algorytmów gry w szachy. Po pierwsze, jest taki, który po prostu przesuwa kawałki do tych kwadratów, gdzie są statystycznie bardziej narażone na przetrwanie. Lub po prostu do kwadratów, na których najprawdopodobniej znajdują się na końcu gry. A inne algorytmy robią dokładnie odwrotnie-przenoszą elementy do kwadratów, gdzie są najmniej prawdopodobne, aby przetrwać (lub skończyć). Dwa algorytmy obliczają, który kwadrat ma najwyższy współczynnik przetrwania (w porównaniu do współczynnika przechwytywania) dla elementu na każdym kwadracie, przy czym jeden algorytm szuka najwyższego współczynnika sprzyjającego przetrwaniu — a algorytm „fatalistyczny” szuka najniższego takiego współczynnika.
” co dziwne, ma największe szanse na wygraną tych strategii.”
i wreszcie postanowił porównać je wszystkie z silnikiem szachowym Stockfish na kilku poziomach (w tym specjalny algorytm, w którym jest zmuszony do zagrania swojego najmniej obiecującego ruchu). „Patrząc na wyniki, nic dziwnego, że jest to ogólnie najgorsza strategia i udaje jej się przegrać z prawie wszystkimi.”
ale pamiętacie oryginalny algorytm Toma „z zawiązanymi oczami”, który nie wiedział, który kawałek zajmuje kwadrat (ani nawet jego kolor)? Postanowił ją rozszerzyć o sieć neuronową, która wykonywała uczenie maszynowe-wykorzystując miliardy pozycji dostępnych w grach od LiChess.org. Teraz był w stanie prawidłowo przewidzieć rzeczywiste kawałki w każdej pozycji ze 100% dokładnością … około jednej piątej czasu. A nawet jeśli jest źle, to tylko błędnie odgadnięte średnio 3,22 sztuk dla każdej pozycji.
i to staje się punktem wyjścia dla jeszcze bardziej dzikich obliczeń. W pewnym momencie dedukuje, że wszystkie gry w ich bazie danych ostatecznie przechodzą przez 21 553 382 902 unikalne pozycje. Z 204GB można je przechowywać wszystkie-wraz z następnym ruchem-ale jest jeszcze inna ciekawa statystyka. Aż 76% pozycji miało miejsce dokładnie raz. „Zajmują więc dużo miejsca i nie są zbyt użyteczne do grania, ponieważ raczej nie zobaczę ich więcej.”Wyrzucając te jednorazowe pozycje, każda inna możliwa pozycja gry może być przechowywana z około 500 MB pamięci. Można to łatwo przekształcić w algorytm, który odtwarza najbardziej popularny ruch dla każdej napotkanej pozycji (podczas zamiany w losowym ruchu, jeśli okaże się uwięziony w unikalnej pozycji).
ale jest jeden prosty trik na pokonanie go. „Jak tylko wykonam trochę dziwny ruch, to po prostu zaczyna grać losowo. A potem jest to bardzo łatwe do pokonania.”
eksperyment końcowy obejmuje różne „rozcieńczenia” silnika Stockfish — w którym jego preferowany ruch jest zastępowany losowo wybranym ruchem x procent czasu.”
„właściwie możemy ocenić, jak dobry jest teraz gracz, porównując go bezpośrednio do konkretnego rozcieńczenia Stockfish…”
po tym, jak wszystkie skomplikowane algorytmy gry w szachy Murphy ’ ego zostały sumiennie Przetestowane, podsumował wyniki w jednym masywnym stole i triumfalnie zakończył swój film, ogłaszając, że jest w końcu gotowy do innych zainteresowań.
„teraz jest następny projekt, który uczy tego psa grać w szachy.”
- co się dzieje, gdy uczenie maszynowe prowadzi ludzkość do odpowiedzi, których nie rozumiemy?
- poznaj Sophie, robota do produkcji makaronu.
- po 15 latach naukowcy odkrywają sztuczne ramię, które może czuć.