Gra w zmianę Berlekampa

Gra przełączania Berlekampa to gra matematyczna zaproponowana przez amerykańskiego matematyka Elwyna Berlekampa . Została również nazwana grą przełączania Gale-Berlekamp , ​​na cześć Davida Gale'a , który niezależnie odkrył tę samą grę, lub grą niezrównoważonych świateł . Obejmuje system żarówek sterowanych dwoma rzędami przełączników, przy czym jeden gracz próbuje włączyć wiele żarówek, a drugi stara się wyłączyć jak najwięcej żarówek. Można go użyć do zademonstrowania koncepcji promienia pokrycia w teorii kodowania .

Zasady

Sprzęt do gry składa się z pomieszczenia zawierającego prostokątny układ żarówek o wymiarach $i$ niektórych liczb b $displaystyle$$\ b$ . Bank $jednej$ stronie pokoju kontroluje każdą żarówkę z osobna Odwrócenie jednego z tych przełączników zmienia żarówkę z wyłączonej na włączoną lub z włączonej na wyłączoną, w zależności od jej poprzedniego stanu. Po drugiej stronie pokoju znajduje się kolejny rząd $przełączników$ po jednym dla każdego rzędu lub kolumny Za każdym razem, gdy którykolwiek z tych przełączników zostanie obrócony, każda kontrolowana przez niego żarówka w rzędzie lub kolumnie zmienia się z wyłączonej na włączoną lub z włączonej na wyłączoną, w zależności od poprzedniego stanu. Podczas przełączania więcej niż jednego przełącznika kolejność przełączania przełączników nie ma wpływu na wynik: te same żarówki będą świecić na końcu sekwencji przerzucania, bez względu na kolejność ich przełączania.

Gra toczy się w dwóch rundach. W pierwszej rundzie pierwszy gracz używa przełączników sterujących poszczególnymi światłami, aby dowolnie włączać i wyłączać światła. W drugiej rundzie drugi gracz używa przełączników sterujących rzędami lub kolumnami świateł, zmieniając układ świateł ustawiony przez pierwszego gracza na inny (ewentualnie pozostawiając go bez zmian). Celem pierwszego gracza jest zaświecenie jak największej liczby świateł na koniec gry, a celem drugiego gracza jest zapalenie jak najmniejszej liczby świateł. Dlatego pierwszy gracz powinien wybrać taki układ świateł, dla którego drugi gracz nie może wyłączyć wielu świateł.

Historia

Berlekamp pracował w Bell Labs w Murray Hill $w stanie$ Jersey od 1966 do roku. Tam skonstruował fizyczną instancję tej gry dla przypadku w pokoju wspólnym Wydziału Matematyki David Gale również wynalazł tę grę niezależnie, jakiś czas przed 1971 rokiem.

Wczesne badania nad powiązanymi problemami obejmowały publikacje Andrew M. Gleasona ( 1960 ), $którego$ komputerowe można interpretować jako pytanie o jak dobrze drugi gracz może sobie poradzić z pierwszym gracza, który gra losowo, oraz JW Moona i Leo Mosera ( 1966 ), którzy teoretycznie odnoszą się do pytania Gleasona, pokazując, że dla prawie wszystkich wyborów pierwszego gracza, w granicach dużych rozmiarów planszy, optymalna wartość gry jest bliska ${\ Displaystyle {\ tfrac {1} {2}} n ^ {2}}$ .

Analiza

Matematycznie można opisać światła włączone przez ruch pierwszego gracza jako zbiór $a$ najmniejszą liczbę świateł, które można osiągnąć dzięki najlepszej grze dla drugiego gracza, jako liczbę ${ \displaystyle f(S)}$ . Najlepszą grą $displaystyle f (S)}$ pierwszego gracza jest wybranie zestawu , który maksymalizuje $\$ . Dlatego też największą liczbę świateł, które można osiągnąć dzięki najlepszej grze dla pierwszego gracza, można opisać jako liczbę ${\ textstyle R_ {a, b} = \ max _ { S}f(S)}$ . Poza pytaniem, jak dobrze grać w pojedynczą grę, szerszym pytaniem, które było przedmiotem badań matematycznych, jest ogólnie scharakteryzowanie wartości funkcji ${\ displaystyle R_ {a, b}}$ za $a}$$displaystyle$ i , aby określić jego zachowanie jako funkcję lub obliczyć jego wartość dla jak największej liczby kombinacji za $displaystyle a}$ i ${\ displaystyle b}$ .

Przypadek kwadratowej $równoważnik$ został rozwiązany dla $12}$ . Dodatkowo, $displaystyle n$ granice dla zostały znalezione dla $leq 20}$ \ Te liczby to:

Rozwiązania dla ${\ displaystyle n \ razy n}$

${\ displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\ Displaystyle R_ {n, n}}$	0	1	2	4	7	11	16	22	27	35	43	54	≥ 60	≥ 71	≥ 83	≥ 96	≥ 107	≥ 122	≥ 139	≥ 148

Asymptotycznie liczby te rosną jako ${\ Displaystyle {\ tfrac {n ^ {2}} {2}} - \ Theta (n ^ {3/2})}$ .

Złożoność obliczeniowa

Ponieważ istnieje wykładniczo wiele opcji, dla których należy przełączyć przełączniki, wyczerpujące poszukiwanie optymalnego wyboru nie jest możliwe w przypadku dużych , co $.$ pytanie, jak dobrze gracze o ograniczonej mocy obliczeniowej mogą grać w tę grę

Pierwszy gracz może spowodować, że oczekiwana wartość gry będzie równa ${\ Displaystyle {\ tfrac {n ^ {2}} {2}} -O (n ^ {3/2}) }$ grając losowo. Podobnie drugi gracz może uzyskać wartość, której oczekiwana odległość od wynosi ${\ Displaystyle {\ tfrac {n ^ {2}} {2}}}$ Ω $\ Displaystyle \ Omega (n ^ {3/2})}$ grając losowo; ta wartość może być większa lub mniejsza niż , $jest$ jest większa, drugi gracz może przełączyć wszystkie przełączniki rzędów, aby uzyskać wartość, mniejszy o taką samą kwotę. Ta losowa strategia dla drugiego gracza może być uczyniona nielosową przy użyciu metody prawdopodobieństw warunkowych , dając algorytm czasu wielomianowego , który uzyskuje te same gwarancje wartości rozwiązania. Inna derandomizacja daje algorytm równoległy w klasie złożoności NC .

Znalezienie optymalnego wyboru dla drugiego gracza w grze, gdy pierwszy gracz wybrał żarówki do zapalenia, jest problemem NP-trudnym . Istnieje jednak schemat aproksymacji czasu wielomianowego $dla$ gry $1+ \ varepsilon) }$ + razy minimalna możliwa liczba zapalonych żarówek dla dowolnego $,$ czasie $+2^{O(1/\varepsilon^{2})}}$${\ Displaystyle O (n ^ {2}$ .

Połączenie z teorią kodowania

Gra przełączająca Berlekampa może być wykorzystana w teorii kodowania jako demonstracja promienia pokrycia pewnego binarnego kodu liniowego . Binarny kod liniowy o długości $n$${$ jest zdefiniowany jako ${\ displaystyle n}$ liniowa podprzestrzeń -wymiarowej przestrzeni wektorowej $\ displaystyle n}$${ \ displaystyle \ mathbb {F} _ {2} ^ {n}}$ nad polem skończonym z dwoma elementami , ${\ displaystyle \ mathbb {F} _ {2}}$ . Elementy podprzestrzeni nazywane są słowami kodowymi, a promień pokrycia to najmniejsza liczba taka, że ​​każdy punkt mieści się w obrębie ${ \ displaystyle \ mathbb {F} _ {2} ^ {$$}}$ Odległość Hamminga słowa kodowego ${\ displaystyle r} .$

Niech $\ Displaystyle n = ab}$ i re $\ Displaystyle d = a + b-1}$ . Dla $\ Displaystyle a \ razy b$ parametrów przestrzeń wektorowa $b$ wszystkie możliwe wzory zapalonych żarówek w } żarówki, z operacją dodawania wektorów, która łączy dwa wzory, zapalając żarówki, które pojawiają się dokładnie w jednym z dwóch wzorów ( operacja różnicy symetrycznej na zestawach zapalonych żarówek). Można zdefiniować liniową podprzestrzeń składającą się ze wszystkich wzorów, które drugi gracz może całkowicie wyłączyć, lub równoważnie ze wszystkich wzorów, które drugi gracz mógłby stworzyć, zaczynając od całkowicie wyłączonej planszy. Chociaż drugi gracz ma ${$ drugiego banku przełączników, ta podprzestrzeń ma $a + b- 1}}$$elementy$ , nadając mu wymiar drugiego gracza nie ma wpływu na wzór zapalonych

Wtedy ${\ Displaystyle R_ {a, b}}$ jest promieniem pokrycia tego kodu. Zestaw zapalonych żarówek wybranych przez pierwszego $^ {n}}$ , daje punkt _ jak najdalej od liniowej podprzestrzeni. Zestaw żarówek, których stan jest zmieniany przez drugiego gracza, z najlepszą grą, daje najbliższy punkt w liniowej podprzestrzeni. Zestaw żarówek, które pozostają zapalone po tych wyborach, to te, których liczba określa odległość Hamminga między tymi dwoma punktami.

Zobacz też

• Lights Out (gra) , inna łamigłówka polegająca na wyłączaniu żarówek za pomocą przełączników sterujących wieloma żarówkami