Age of Empires - wyścig chłopów

Dobrze jest rozwiązywać zadania, które mają związek z rzeczywistością. Problemy grafowe przekładają się na projektowanie układów scalonych, szukanie wzorców w tekście na genetykę i tak dalej. W tym artykule nie będziemy tego robić. Zajmiemy się jednak czymś równie ważnym - problemem jak dobrze zacząć potyczkę w Age of Empires.

Sytuacja jest następująca: jesteś władcą małego plemienia. Do swojej dyspozycji oddanych masz kilku chłopów. Każdy z nich w pojedynczej turze (tura może być na przykład 1 sekundą) zbiera jednostkę jedzenia. Po każdej turze możesz zatrudnić dodatkowych chłopów - kosztuje Cię to ustaloną ilość jednostek jedzenia za każdego nowego pracownika. Twoim zadaniem jest w jak najmniejszej ilości tur przejść do nowej ery. Stanie się to, kiedy uzbierasz wystarczająco dużo jednostek jedzenia.

Przykładowo, dla Age of Empires najczęściej zaczynamy grę z 3 chłopami, dodatkowy pracownik kosztuje 50 jednostek jedzenia, a do nowej ery konieczne jest zebranie 500 jednostek jedzenia. Na pierwszy rzut oka nie bardzo widać, jak grać. Jeżeli nie będziemy zatrudniać nowych pracowników chomikując jedzenie w spichlerzu, możemy zbyt długo czekać na nową erę. Z drugiej strony, kiedyś trzeba przestać inwestować i dać chłopom popracować w spokoju.

Zacznijmy od przykładu analizując jedną z moich rozgrywek w Age Of Empires(*).

Zaczynam grę z 3 chłopami. Zatrudnię jeszcze 3 chłopów i poczekam na nową erę.

6 chłopów dzielnie pracuje.

Hmm, trochę to za wolno idzie. Zatrudnię jeszcze 2 chłopów.

Zebraliśmy ponad 500 jednostek jedzenia. 8 chłopów dało jakoś radę.

(*) Ze względu na lepszą jakość, screeny zostały wykonane podczas gry w Age of Empires 3.

Nie jest to niestety najlepsza rozgrywka. Czy wiesz dlaczego? Spróbuj zmodyfikować powyższą strategię, tak żeby zakończyć grę z 8 chłopami, ale szybciej przejść do nowej ery.

Wskazówka

W chwili, kiedy postanowiłem zatrudnić 2 chłopów na screenie 3 wiedziałem już, że mogłem zagrać lepiej.

Odpowiedź

Od momentu gry, przedstawionego na screenie 2, do sytuacji ze screenu 3 upłynęło ponad 40 tur (sprawdź różnicę w liczbie jednostek jedzenia). W tym czasie mógłbym już zatrudnić siódmego i ósmego chłopa, pozwalając im dłużej pracować. W rezultacie szybciej zebrałbym wymagane 500 jednostek jedzenia.

Dokonaliśmy pierwszej obserwacji. Nie opłaca się odwlekać zatrudniania chłopów - jeżeli mamy to uczynić, zróbmy to jak najszybciej. Czemu tak jest? Zauważmy, że pracownik zatrudniony kilka tur wcześniej pracuje dla nas dłużej. Pozwoli nam to zebrać więcej jednostek jedzenia niż w pierwotnej strategii, w której chłop został najęty w późniejszym czasie.

Pokazaliśmy właśnie, że możemy ograniczyć się tylko do jednego rodzaju strategii. Są to strategie, w których do pewnego momentu zatrudniamy chłopów tak szybko jak jest to możliwe, a następnie nie robimy już nic czekając na nową erę. Takie strategie nazwijmy dobrymi strategiami. Dobrą strategię nazywamy -strategią, jeżeli grając nią przechodzimy do nowej ery mając chłopów.

Chcąc grać 4-strategią, musimy poczekać 17 tur, żeby 3 chłopów zebrało 51 jednostek jedzenia. Następnie, płacąc 50 jednostek, zatrudniamy czwartego pracownika. W trakcie kolejnych 125 tur chłopi zbierają 500 jednostek. Po 142 turach kończymy rozgrywkę mając 501 jednostek jedzenia. Innym przykładem jest strategia przedstawiona na screenach, która po wspomnianej modyfikacji staje się 8-strategią.

Zobaczmy jakie wyniki dają -strategie dla różnych i rozgrywki Age Of Empires.

Ponieważ dla większych wyniki są coraz gorsze, najlepsza jest 9 lub 10-strategia ( czyli trzeba zatrudnić dodatkowych 6 lub 7 chłopów ). Co więcej, udało nam się pokazać, że nie da się grać lepiej i przejść do nowej ery szybciej niż w 117 tur gry.

W tym momencie moglibyśmy skończyć. Umiemy już znajdować optymalną strategię dla dowolnych danych - wystarczy zasymulować -strategię dla wszystkich sensownych i wybrać najlepszą z nich. Co to znaczy, że jest sensowne? Wróćmy do naszego przykładu. Zauważmy, że grając -strategią dla równie dobrze moglibyśmy grać 500-strategią. Czemu? Odpowiedź jest prosta: po zatrudnieniu 500-tego chłopa mamy pewność, że gra zakończy się w następnej turze. Nie ma zatem potrzeby najmować więcej pracowników. Z tej obserwacji wynika, że na pewno nie opłaca się sprawdzać strategii, w których najmujemy więcej chłopów niż liczba jednostek jedzenia gwarantująca nam przejście do nowej ery. Pewnie można byłoby bardziej ograniczyć zbiór kandydatów na sensowne , ale zamiast tego przeanalizujmy sytuację jeszcze raz.