MakarovSuites
Polski
EnglishDeutschРусскийУкраїнськаFrançaisEspañolItalianoPolski
Kontakt i licencje

Math

Nim i suma binarna

Stosy kamieni, a pod nimi ich zapis binarny. Kolumna z nieparzystą liczbą jedynek płonie na czerwono; bez czerwonych kolumn ten, kto ma ruch, już przegrał. Regułę sprawdza rozwiązanie całego drzewa gry.

Nim i suma binarna — Obraz z aplikacji
Obraz z aplikacji

Co się dzieje

Bierz ile chcesz kamieni z JEDNEGO stosu; przegrywa ten, kto nie ma co wziąć. Pod stosami karta rysuje ich zapis binarny, kolumna na stos, a kolumna z nieparzystą liczbą jedynek płonie na czerwono. Reguła Boutona mówi, że pozycja jest przegrana dla ruszającego dokładnie wtedy, gdy żadna kolumna nie jest czerwona - gdy suma binarna wynosi zero. Nie trzeba w to wierzyć: każda pozycja przestrzeni stanów zostaje oznaczona rozwiązaniem gry do końca, a oznaczenia porównuje się z regułą na 729, 2197, 4096 i 7776 pozycjach, bez ani jednej rozbieżności. Żeby zostawić przeciwnikowi zero, trzeba zgasić czerwone kolumny, a może to tylko stos z jedynką na najwyższej czerwonej pozycji. Takich stosów jest nieparzyście wiele - inaczej ta pozycja nie byłaby czerwona - więc ruchów wygrywających jest jeden albo trzy i nigdy dwa: na trzech stosach 1092 pozycje mają jeden, 148 mają trzy, a dwóch nie ma żadna. Przełącz na misère, gdzie ostatni kamień przegrywa, a ta sama reguła pęka: rozwiązane drzewo zaprzecza jej dokładnie na pozycjach z pojedynczych kamieni.

Równania modułu
Równania
kopce kamieni, ruch zabiera dowolną liczbę z JEDNEGO kopca, a gracz, który nie ma co zabrać, przegrywa
reguła Boutona: pozycja jest przegrana dla gracza, który ma ruch, dokładnie wtedy, gdy suma binarna (xor) rozmiarów kopców jest równa zero
karta tego nie cytuje - oznacza KAŻDĄ pozycję, rozwiązując grę do końca, i porównuje: 729, 2197, 4096 i 7776 pozycji, zero rozbieżności
ruchy wygrywające to kopce z (h xor s) < h, a ich liczba jest ZAWSZE NIEPARZYSTA - jeden lub trzy, nigdy dwa:
dla trzech kopców do 10 rozkład jest taki: 0 ruchów w 91 pozycjach, 1 ruch w 1092, 3 ruchy w 148, a 2 ruchy w żadnej
powód nie jest przypadkiem: ruch do zera wykonuje kopiec mający jedynkę na najwyższym ustawionym bicie sumy, a takich kopców jest nieparzysta liczba, bo inaczej ten bit byłby zerem
pozycje przegrane są zliczone dokładnie: k kopców o rozmiarach 0..2^b−1 zawiera ich 2^(b(k−1)) - 64 dla trzech kopców o rozmiarach 0..7
MISERE to inna gra i ta reguła jest tam BŁĘDNA: rozwiązanie drzewa różni się od xor na dokładnie 2^k pozycjach, wszystkich złożonych z pojedynczych kamieni
reguła misere: dopóki jakiś kopiec ma więcej niż jeden kamień, gra się jak zwykle; gdy każdy kopiec ma jeden, pozycja jest przegrana dla wykonującego ruch dokładnie wtedy, gdy ich liczba jest NIEPARZYSTA
(1,1,1) jest wygrana dla wykonującego ruch w grze normalnej i przegrana w misere; (1,1) jest odwrotnie; (2,1,1) jest wygrana w obu
domyślne rozdanie 7-5-3 ma sumę binarną 1 i dokładnie trzy ruchy wygrywające: do 6-5-3, do 7-4-3 i do 7-5-2

Inne eksperymenty

Wróć do katalogu
Drzewo gry i alfa-beta — Obraz z aplikacji

Math

Drzewo gry i alfa-beta

Drzewo gry, w którym każdy blok jest tak wysoki jak jego wartość: węzeł MAX tak wysoki jak jego najwyższe dziecko, węzeł MIN tak niski jak najniższe. Minimaks czyta każdy liść; alfa-beta pomija to, co nie może zmienić odpowiedzi, a ile pomija, zależy od kolejności ruchów.

Kod Huffmana — Obraz z aplikacji

Math

Kod Huffmana

Uporządkowana kolejka częstości tworzy drzewo kodu prefiksowego. Wybierz symbol, aby prześledzić jego bity i kolejne połączenia.

Plecak: zachłanność kontra tabela — Obraz z aplikacji

Math

Plecak: zachłanność kontra tabela

Wybierz ponumerowane ładunki przy limicie masy. Porównaj z zachłannym i optimum, otwórz komórkę tabeli i wróć do optymalnego wyboru.