Jakie masz ogólne wskazówki na temat tworzenia bota, aby wziąć udział w wyzwaniu King of the Hill? Jakich strategii używasz, od przejścia wyzwania do stworzenia swojego bota? Jakie struktury danych są najbardziej przydatne?

Proszę zamieścić jedną wskazówkę na odpowiedź.

Znalezienie równowagi Nasha

Jest to bardzo ważna koncepcja, gdy KOTH obejmuje stosunkowo prosty zestaw decyzji, angażuje tylko kilku graczy (zazwyczaj 2) i jest deterministyczny. Równowaga Nasha opisuje pozycję „blokady”: jeśli dwaj gracze zdecydowali się na dwie strategie, wówczas dwaj gracze są skutecznie zablokowani na tych pozycjach: każdy z graczy zmieniający strategię po prostu stwarza dodatkowe podatności.

Przykłady gier, w których ważna jest równowaga Nasha:

• Rock-Paper-Scissors (-Lizard-Spock), w którym strategia „nie do pobicia” to gra losowa
• Morra , która ma „spektrum” równowagi. Peter Taylor napisał dobry przykład w swojej odpowiedzi tutaj .
• Dylemat Więźnia, gra kooperacyjna godna uwagi z powodu impasu „wszyscy przegrywają”

Jak znaleźć równowagę

Znalezienie równowagi jest w rzeczywistości dość proste w przypadku większości prostych gier i często jest dość intuicyjne. Ton szczegółów na temat różnych metod można znaleźć w internecie. Podstawową koncepcją, która zwykle ma zastosowanie, jest stworzenie listy możliwych strategii, z których mogą korzystać dwaj gracze (opcje dostępne w grze). Jeśli jedna strategia jest „zdominowana” przez inną, wówczas strategia ta może zostać usunięta z listy, a proces się powtarza. Przez „dominację” rozumiem, że jeśli strategia A zawsze daje wynik równy lub lepszy niż strategia B, w porównaniu ze wszystkimi pozostałymi strategiami przeciwnika, strategia B może zostać usunięta z listy.

Przykład: kamień-papier-nożyce

RPS ma coś, co nazywa się równowagą „mieszaną”, co oznacza, że ​​w grę wchodzi rozkład . Zamiast powtarzać ten sam ruch (co doprowadzi do szybkiej porażki), równowaga polega na graniu w 1/3 kamienia, 1/3 papieru i 1/3 nożyczek w losowym rozkładzie. Jeśli gram losowo, nic nie może zrobić mój przeciwnik, aby uzyskać przewagę, kropka. Jeśli mój przeciwnik zdecyduje się nie grać losowo, stwarza to tylko jego podatność.

Gry o mieszanej równowadze są prawdopodobnie najbardziej popularne na PPCG, ponieważ mogą przybierać różne formy ( jedyną interesującą grą, o której mogę myśleć z czystą równowagą, jest dylemat więźnia). Powinienem zauważyć, że mieszana równowaga nie musi być jednolicie losowa , po prostu coś innego niż wykonywanie tego samego ruchu za każdym razem.

Korzystanie z tych informacji

Równowaga Nasha w grze często reprezentuje „linię bazową”, od której powinieneś spróbować działać. W RPS losowa gra gwarantuje końcowe miejsce pośrodku paczki. Aby przejść na szczyt, musisz zacząć identyfikować słabości innych graczy.

Aby to zrobić, powinieneś trzymać się równowagi, gdy nie jesteś pewien słabości przeciwnika. Po zidentyfikowaniu tych słabości (gdy wykryjesz, że twój przeciwnik nie jest w równowadze), musisz delikatnie wyjść z równowagi, aby skorzystać z możliwości przeciwnika. To działanie z kolei tworzy słabości z twojej strony. Następnie musisz wykryć, kiedy przeciwnik zmienia strategię, abyś mógł następnie zatrzymać atak i wznowić losową grę.

Wykrywanie odchyleń od równowagi

To jest dość trudne i nie jestem ekspertem. Wariacje mogą przybierać różne formy:

• Preferowanie niektórych opcji powyżej / poniżej innych bez powodu, takich jak odtwarzacz RPS, który gra kamień dwa razy częściej niż nożyce lub ten, który unika gry w papier. Niektóre stosunkowo proste statystyki mogą to wykryć.
• Bazowanie na bieżącym ruchu w stosunku do poprzednich ruchów, według pewnego przewidywalnego wzoru. Obejmuje to kopiowanie kotów, „bije to, co bije Twoje ostatnie ruchy” lub boty „na rowerze”. Wymaga to dodatkowej logiki do wykrycia, ponieważ ogólny rozkład ruchów może być równomiernie rozłożony, nawet jeśli ruchy nie są losowe. Powinieneś spróbować zapisać rejestr ruchów i znaleźć korelacje, takie jak „ruch, który wykonałem 2 tury temu i ruch, który mój przeciwnik wykonał teraz” i „ruch, który wykonał 1 turę temu, i ruch, który wykonał teraz” itp.
• Boty, których rozkład ruchów jest oparty na twoim. Luka w tych botów często nie jest tworzony (w wymiernej ilości), aż po masz się zmieniać z rozkładu losowego. Generalnie twój własny bot należy do tej kategorii.

Określ szczegółowo wymagania dotyczące uruchamiania bota

Boty mogą być pisane w różnych językach (i ich wersjach), więc pomaga wszystkim, gdy:

1. Przetestuj w środowisku określonym przez OP (lub tak blisko, jak to możliwe).
2. Jeśli to możliwe, przetestuj go w wielu innych środowiskach (aby pomóc innym, którzy chcą go uruchomić).
3. Określ konkretnie język i wersję, której używasz, i wyjaśnij, jak uruchomić bota.

Jako bonus: jeśli używasz mniej znanego języka, zrób link do miejsca, w którym ludzie mogą pobrać plik binarny / źródło, aby go uruchomić.

Jeśli pracujesz w zespole, współpracuj ze swoim zespołem

Chociaż zwykle możesz napisać bota, który działa solo, aby wykonać zadania, aby pomóc zespołowi, jest o wiele większa korzyść, gdy koordynujesz zarówno w grze, jak i poza nią. Doskonały przykład tego można zobaczyć w grze Red vs. Blue - Pixel Team Battlebots .

Podczas opracowywania zespoły mogły rozmawiać i dyskutować o tym, jak koordynować swoje boty, aby funkcjonowały lepiej niż same. Choć technicznie ten sam bot, SphiNotPi3000 został napisany do pracy w tandemie z innym samym sobą i był w stanie poruszać się w sposób, który tłumaczyłby słabości, z którymi by się spotkał, gdyby był sam. Rezultatem końcowym było to, że byli w stanie niemal całkowicie zdominować pole bitwy, nawet gdy byli to tylko dwaj przeciw całej drużynie .

Więc poza grą planuj i koordynuj z kolegami z zespołu, jakie strategie zastosować. Może ktoś ma bota, który skanuje mapę po przekątnej? Niech twój skanuje poziomo (tylko przykład). Jeśli wyzwanie pozwala na komunikację w zespole, skorzystaj z niego. Na przykład w grze bojowej możesz wysłać wiadomość do kolegów z drużyny o pozycji botów poza ich polem widzenia, a następnie zachęcić ich do napisania botów w kompatybilny sposób, aby wykorzystać te sygnały.

Użyj meta strategii

Dla prawie każdej sprytnej strategii istnieje inna strategia, która ją pokonuje: na przykład twój przeciwnik może zastosować dokładnie to samo rozumowanie, co ty, aby przewidzieć następny ruch, a następnie przeciwdziałać mu. Teraz możesz spróbować ponownie odgadnąć przeciwnika, ale trudno jest wiedzieć, kiedy przestać .

Innym problemem jest to, że strategia, która dobrze sprawdza się w odgadywaniu sprytnego przeciwnika, może być daleka od optymalnej w przypadku prostszych przeciwników.

Jak możesz to rozwiązać? Pozwalasz botowi na bieżąco decydować, jakiej strategii użyć!

W tym celu zacznij od podania botowi repertuaru różnych strategii. Następnie, przed każdym ruchem, twój bot sprawdza dotychczasową historię gry i ocenia, jak radziłyby sobie te różne strategie. Następnie pokazuje ten, który byłby najbardziej udany.

Uwzględnienie przede wszystkim strategii, które są silne, pomoże Twojemu botowi mieć dobre możliwości wyboru. Ale powinieneś również uwzględnić naprawdę proste, ponieważ często działają lepiej przeciwko głupim przeciwnikom.

Możesz rozważyć nastawienie na niektóre strategie, aby uniknąć przeregulowania (np. Próbując pokonać wzór, w którym przeciwnik po prostu działa losowo) lub faworyzować określone strategie na początku, gdy nie ma jeszcze zbyt wielu informacji.

Oczywiście takie podejście będzie działać tylko w przypadku niektórych rodzajów wyzwań związanych z królem wzgórza. Naprawdę dobrze mi poszło w meczu Rock-Paper-Scissors-Lizard-Spock . W innych grach ocena, jak radziłaby sobie pewna strategia, nie byłaby prawie niemożliwa.

Ekstremalną formą tego meta podejścia (graniczącego z oszustwem) byłoby włączenie znanego zachowania wszystkich innych botów do własnego bota, tak aby mógł on doskonale przewidzieć ich ruchy.