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

03.07.2009 - Paweł Pająk
TrudnośćTrudność

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

Odpowiedź

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 $ N $-strategią, jeżeli grając nią przechodzimy do nowej ery mając $ N $ 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ą $ N $-strategie dla różnych $ N $ i rozgrywki Age Of Empires.

 

Ponieważ dla większych $ N $ 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ć $ N $-strategię dla wszystkich sensownych $ N $ i wybrać najlepszą z nich. Co to znaczy, że $ N $ jest sensowne? Wróćmy do naszego przykładu. Zauważmy, że grając $ N $-strategią dla $ N\textgreater500 $ 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 $ N $, ale zamiast tego przeanalizujmy sytuację jeszcze raz.

5
Twoja ocena: Brak Ocena: 5 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com