0Pricing
Competitive Programming Academy · Lekcja

Stany wygrywające i przegrywające w grach

Rozumowanie o zwycięzcy przy optymalnej grze

Stany wygrywające i przegrywające w grach to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Dwóch graczy, doskonała gra

W grze kombinatorycznej dwóch graczy wykonuje ruchy naprzemiennie, obaj grają optymalnie, a gracz, który nie może wykonać ruchu, przegrywa. Zadanie polega jedynie na przewidzeniu zwycięzcy. 🎯

Każda pozycja ma etykietę

Każda pozycja w grze jest stanem. Całe zadanie polega na oznaczeniu każdego stanu jako wygranego albo przegranego dla gracza, który ma wykonać ruch.

Znaczenie stanu wygranego

Stan jest wygrany, jeśli gracz wykonujący ruch ma przynajmniej jeden ruch prowadzący do stanu przegranego przeciwnika.

Znaczenie stanu przegranego

Stan jest przegrany, gdy każdy wykonany ruch przekazuje przeciwnikowi stan wygrany. Nie ma dobrego wyboru.

Przypadek bazowy

Pozycja, w której nie można wykonać żadnego ruchu, jest przypadkiem bazowym. Gracz, który na nią trafia, już przegrał, więc należy oznaczyć ją jako przegraną.

Budowanie od dołu

Należy zacząć od przypadków bazowych i przechodzić na zewnątrz. Etykieta każdego nowego stanu zależy wyłącznie od stanów, do których prowadzą jego ruchy.

Wystarczy jeden dobry ruch

Aby wygrać, wystarczy wykonać jeden ruch prowadzący do stanu przegranego przeciwnika. Znalezienie dowolnej drogi wyjścia wystarczy.

Mały przykład

Z kupki można zabierać 1 albo 2 kamienie, a wygrywa osoba, która zabierze ostatni. Przy 0 kamieniach gracz wykonujący ruch przegrywa, więc jest to stan przegrany.

Kodowanie sprawdzania zwycięstwa

Ta rekurencja oznacza stan, próbując każdego ruchu i wywołując rekurencję dla wyniku. ⚙️

def win(n):
    if n == 0:
        return False
    return any(not win(n - k) for k in (1, 2))

Zapamiętywanie wyników dla szybkości

Stany powtarzają się w różnych gałęziach, więc należy zapisać każdy wynik w pamięci podręcznej. Proste memo zmienia wykładniczy nakład pracy w czas liniowy.

from functools import lru_cache
@lru_cache(None)
def win(n):
    return n != 0 and any(not win(n - k) for k in (1, 2))

Symetria to skrót

Jeśli pozycja jest idealnie symetryczna, drugi gracz może często odwzorowywać ruchy przeciwnika i wygrać. Warto wypatrywać tej strategii lustrzanej.

Szybkie sprawdzenie

Przed Państwem znajduje się pewien stan. Kiedy jest on dla Państwa stanem przegranym?

Podsumowanie

Można już oznaczać stany: wygrana ma jeden ruch prowadzący do przegranej przeciwnika, a przegrana nie ma żadnego. Należy budować rozwiązanie od przypadków bazowych i zapamiętywać wyniki. 🧠

Często zadawane pytania

Czy lekcja „Stany wygrywające i przegrywające w grach” jest bezpłatna?

Tak — pełny tekst „Stany wygrywające i przegrywające w grach” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Stany wygrywające i przegrywające w grach”?

Rozumowanie o zwycięzcy przy optymalnej grze Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?

Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Stany wygrywające i przegrywające w grach”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?

Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Stany wygrywające i przegrywające w grach
  2. Nim i liczba Grundy’ego
  3. Spotkanie pośrodku
  4. Szybkie debugowanie: testy obciążeniowe i triage
← Powrót do Competitive Programming Academy