Dobór optymalnego składu floty w grze 'Ogame'
Paweł Kalinowski
25.06.2012
Raport z projektu wykonanego na zaliczenie przedmiotu Sztuczna Inteligencja

 Searching for the optimal fleet structure in 'Ogame' - strategic game
Paweł Kalinowski
25.06.2012
The project described in this report has been completed to fulfill the requirements for the course: Artificial Intelligence
The author searched for optimal number of ships of given types for a „Ogame” game wars.
The method used is attachin constrained integer optimisaton to self-adjusted battle simulator.
Criteria were consulted with domain-experts through official forums.
The simulated function is irregular and manual analisis were generally unsuccessful.
This project is the first attempt to perform the optimization in automatic way, so get attention of the community.
Results are satisfying – the degree of improval varies, but it is always present.



Opis zadania
Celem zadania było stworzenie systemu, który poprzez odpowiedni ciąg symulacji znajdzie “optymalny” skład floty do ataku na zadany cel w grze OGame.

“OGame – internetowa gra strategiczna z rodzaju tzw. massively multiplayer online strategic game (MMOSG). [...]
Głównym zadaniem jest kontrola nad jak największą częścią wszechświata, zbieranie i handel surowcami, rozbudowywanie swojego imperium, postęp technologiczny, walka i układy z innymi graczami, oraz osiągnięcie jak najwyższego miejsca w rankingu najlepszych graczy danego universum.[...]
sfera militarna – dzieli się ona zarówno na obronę, gdzie można produkować działa lub systemy defensywne, jak i systemy ofensywne takie jak statki bojowe, kolonizacyjne, sondy szpiegowskie oraz transportowe itp. [...] Gdy gracz dysponuje flotą, może zaatakować planetę innego gracza. [...] . Jeśli gracz atakujący zdoła przełamać obronę przeciwnika, na jego statki (zależnie od ich łącznej ładowności) zabierana jest maksymalnie połowa surowców znajdujących się na planecie przeciwnika. Walki odbywają się natychmiastowo (kończą się w momencie, gdy flota dociera do docelowej planety).” @http://pl.wikipedia.org/wiki/OGame

W grze występują 22 typy jednostek, z czego 8 to statki militarne, a 1 to tanie sondy szpiegowskie , które mogą służyć jako “mięso armatnie”. Algorytm przeprowadzania bitew jest ogólnodostępny, ale skomplikowany, a przy tym zawiera element losowy. Przy założeniu braku rażącej dysproporcji sił, jedynym sposobem na oszacowanie wyniku jest przeprowadzenie symulacji całej bitwy (runda po rundzie).
Narzędzia do wykonywania symulacji są dostępne, ale żadne z nich nie oferuje interfejsu innego niż graficzny.

Z racji innowacyjności projekt wzbudził spore zainteresowanie społeczności graczy OGame z kilku krajów . Wcześniej nie istniał automatyzowalny program do symulacji, funkcja celu jest nieliniowa a przestrzeń do przeszukania ogromna.

Opis zastosowanej metody rozwiązania problemu
Kryterium optymalności to minimalizacja funkcji {koszty produkcji + straty w trakcie bitwy + zużyte paliwo} przy warunku 100% szans na wygraną.
Po utworzeniu takiej funkcji celu (wymagało to modyfikacji silnika symulacji) użyto biblioteki NOMAD, aby przeprowadzenić 9-wymiarową optymalizację funkcji z ograniczeniami. Argumentami były liczby naturalne, odpowiadające liczbie statków.

Implementacja

  1. Z programu csim wyodrębniono silnik symulacji bitew, stworzono potrzebne interfejsy wejścia/wyjścia: interfejs linii komend oraz interfejs programowy (funkcja biblioteczna dzielonej biblioteki).

  2. Korzystając z biblioteki NOMAD i stworzonej biblioteki (punkt 1.) napisano program (w C++), który wczytuje dane obrońcy i dodatkowe parametry (np dostępny budżet) i znajduje “optymalną” flotę do ataku.

  3. Skuteczność tak wyznaczonych flot badano na bazach danych flot: udostępnionej przez OmarHawk i samodzielnie ściągniętej z board.ogame.pl.

Przykład działania programu

Program działa w dwóch trybach:

* konsolowym (dane jako argumenty wywołania, wynik wypisany na standardowe wyjście)

* automatycznym (dane wczytywane z input.txt, wyniki wypisywane do output.txt)

Kod został napisany w sposób przenośny, poza Linuksem działa również na systemie Windows (kompilowany za pomocą MinGW).


Ocena wyników

Pierwsza analizowana sytuacja: dużo struktur obronnych, brak statków:

inputDefender 10 10 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8000 3500 150 100 200 80 1 1

Wartość obrony wynosi

costD:5.0e+07

Rozwiązanie uznane przez program za optymalne zostało porównane z kilkoma innymi, składającymi się jedynie z jednego typu statków.

Wyniki:

graphics1




Ich statystyki (w ostatniej kolumnie minimalizowana funkcja, we wcześniejszych składniki: +,-,+,+)

graphics2



Jak widać znalezione rozwiązanie jest lepsze wg funkcji celu i większości jej składowych, nawet od floty samych bombowców, mimo że są to okręty dedykowane do niszczenia obrony.

Druga analizowana sytuacja: potężna i zrównoważona flota

inputDefender 10 10 10 0 225 21000 10500 5250 2625 0 0 415 73 0 203 12 537 0 0 0 0 0 0 0 0

costD:8.8e+08

graphics3



graphics4


Tutaj rozwiązania zawierającego <10e6 myśliwców nie było. Zarówno gwiazdy śmierci jak i pancerniki są przeznaczone do walki z obcymi okrętami, ale jak widać odpowiednia mieszanka różnych typów jest korzystna.

Przeanalizowano więcej konfiguracji przeciwników i we wszystkich przypadkach program wskazał nieco lepsze rozwiązanie niż najlepsze z układanych przez ludzi.

Wnioski
Osiągnięte wyniki są zadowalające. Metoda sprawdziła się, oferując poprawę wyników, a przede wszystkim dużą oszczędność czasu - częstą praktyką wśród graczy jest wykonywanie kilku symulacji (każdorazowo konfigurowanych ręcznie) w celu wyboru najkorzystniejszego wariantu.

Uwagi

Autor dobrze zna i rozumie wszystkie zasady gry, ale grając skupiał się na innych aspektach - posiada jedynie ograniczoną wiedzę ekspercką z dziedziny projektowania składu flot.
W celu uzyskania tej wiedzy zwrócił się do społeczności graczy poprzez oficjalne fora: board.ogame.pl i board.ogame.org.
Wersja alfa została upubliczniona 20.06.2012, w ciągu niecałego tygodnia program (wciąż niedokończony) osiągnął ponad 150 ściągnięć, a łącznie dotyczące go tematy zanotowały ~70 wypowiedzi i ~2000 wejść.
Pod wpływem sugestii graczy zostało wprowadzone wiele zmian. Większość komentarzy dotyczyła możliwości konfiguracji i ograniczania rozmaitych wartości, a część sugestii odnosiła się do interfejsu.
Spostrzeżenie, że ignorowanie ilości spalanego paliwa jest nierealistycznym założeniem wymusiła utworzenie dodatkowego modułu odpowiedzialnego za obliczenia odległości i spalania (~50 dodatkowach linii kodu obliczeń oraz konieczność dodania dużej ilości stałych opisujących statki).

W dniu składania raportu projekt jest wciąż rozwijany, ale zmiany dotyczą głównie przystępności dla użytkowników, a obliczenia nie podlegają zmianom.

Wykorzystane narzędzia/materiały

  1. Fragmenty kodu csim 1.17; licencja GPL2 , Copyright (C) by Dmitry E. Oboukhov, strona autora już nie istnieje, ale program/kod są dostępne w repozytoriach Debiana jako ogamesim

  2. Biblioteka NOMAD (Nonsmooth Optimization by Mesh Adaptive Direct Search), licencja LGPL,
    Samodzielnie napisany w tym celu program optifleet (udostępniony publicznie w serwisie sourceforge)

  3. Silnik programu “SpeedSim”, źródło kodu odpowiedzialnego za obliczenia dotyczące paliwa/odległości

  4. Dump tabeli 'reports' bazy danych SQL programu galaxytool, otrzymany dzięki uprzejmości Omar_Hawk (autora programu) – duży zbiór danych o flotach/obronach

  5. Samodzielnie sparsowane (bash,grep,sed,wget,awk) raporty bitewne ze strony http://board.ogame.pl/board790-z-ycia-uniwers-w/board801-starcia-tytan-w-raporty-wojenne/

  6. Analizę, zrównoleglanie obliczeń i przetwarzanie danych wykonano w pakiecie R

Inne analizy dotyczące konstrukcji flot

  1. Tematy na forach board.ogame.pl oraz board.ogame.org, dające ogólną orientację w temacie

  2. http://ogame.wikia.com/wiki/Ogame_Combat_Chain stwierdza że relacja flot przypomina “Papier-Kamień-Nożyce”. Wzajemną podatność statków (wyniki bitw flot jednolitego typu i podobnej wartości) można opisać w uproszczeniu jako:
    Fighters > Destroyers > DeathStars > Battlecruisers > Battleships > Cruisers > Fighters

  3. http://web.archive.org/web/20100329141042/http://www.ogametips.com/4/fleets-and-ships---overview – autor próbuje matematycznie wyznaczyć zunifikowaną wartość bojową poszczególnych typów statków(przeskalowaną do kosztu).
    Wynik (Light Fighter/Heavy Fighter/Cruiser/Battle Ship/Bomber/Destroyer/Death Star): 3.465/3.485/3.101/3.821/2.764/3.112/3.625.
    Sugeruje to porównywalną użyteczność, ale ignoruje “Szybkie Działa”, czyli podstawę przewagi jednego typu statku nad innym.

  4. http://board.ogame.org/board703-miscellaneous/board156-archive-version-2-0/board705-help-questions-archive/377179-exact-battle-algorithm/ ; www.speedsim.net/stuff/battle_algorithm.doc – szczegóły algorytmu obliczania wyniku bitwy (symulator był używany jako “czarna skrzynka”, ale dobrze rozumieć jak działa)

graphics5