To dwutygodniowe wyzwanie nr 3. Temat: Algorytmy genetyczne
To wyzwanie jest trochę eksperymentem. Chcieliśmy zobaczyć, co możemy zrobić, pod kątem wyzwań, za pomocą algorytmów genetycznych. Nie wszystko może być optymalne, ale staraliśmy się, aby było to dostępne. Jeśli to się powiedzie, kto wie, co możemy zobaczyć w przyszłości. Może genetyczny król wzgórza?
Specyfikacja jest dość długa! Próbowaliśmy podzielić specyfikację na Podstawy - absolutne minimum, które musisz wiedzieć, aby zacząć grać z frameworkiem i przesłać odpowiedź - oraz The Gory Details - pełną specyfikację ze wszystkimi szczegółami na temat kontrolera, na podstawie których mógłbym napisać własny.
Jeśli masz jakiekolwiek pytania, dołącz do nas na czacie!
Jesteś badaczem psychologii behawioralnej. Jest piątek wieczorem, a ty i twoi koledzy decydujecie się zabawić i wykorzystać swoje szczury laboratoryjne do małego wyścigu szczurów. W rzeczywistości, zanim przywiążemy się do nich zbyt emocjonalnie, nazwijmy je okazami .
Przygotowałeś mały tor wyścigowy dla okazów, a żeby był bardziej interesujący, umieściłeś na nim kilka ścian, pułapek i teleporterów. Teraz twoje okazy są nadal szczurami ... nie mają pojęcia, czym jest pułapka lub teleporter. Widzą tylko niektóre rzeczy w różnych kolorach. Nie mają też żadnej pamięci - wszystko, co mogą zrobić, to podejmować decyzje w oparciu o ich obecne otoczenie. Myślę, że dobór naturalny wyodrębni okazy, które potrafią uniknąć pułapki od tych, które tego nie robią (ten wyścig zajmie trochę czasu ...). Niech rozpocznie się gra! †
† 94 465 okazów zostało poszkodowanych przy podejmowaniu tego wyzwania.
Podstawy
Jest to gra dla jednego gracza (ty i twoi koledzy nie chcieliście mieszać populacji, więc każdy zbudował własny tor wyścigowy). Tor wyścigowy jest prostokątną siatką o wysokości 15 komórek i szerokości 50 komórek. Zaczynasz z 15 okazami na losowych (niekoniecznie odrębnych) komórkach na lewej krawędzi (gdzie x = 0 ). Próbki powinny próbować osiągnąć cel, którym jest dowolna komórka przy x ≥ 49 i 0 ≤ y ≤ 14 (okazy mogą przekroczyć ścieżkę w prawo). Za każdym razem, gdy tak się dzieje, dostajesz punkt. Grę rozpoczynasz również z 1 punktem. Powinieneś spróbować zmaksymalizować swoje punkty po 10 000 tur.
Wiele próbek może zajmować tę samą komórkę i nie będzie oddziaływać.
Na każdym kroku każdy okaz widzi siatkę 5x5 swojego otoczenia (z samym sobą na środku). Każda komórka tej siatki będzie zawierała kolor -1
do 15
. -1
reprezentuje komórki, które są poza granicami. Twój okaz umrze, jeśli wyjdzie poza granice. Jeśli chodzi o inne kolory, reprezentują puste komórki, pułapki, ściany i teleportery. Ale twój okaz nie wie, który kolor reprezentuje to, co ty, i ty też. Istnieją jednak pewne ograniczenia:
- 8 kolorów będzie reprezentować puste komórki.
- 4 kolory będą reprezentować teleporter. Teleporter wyśle próbkę do określonej komórki w jej sąsiedztwie 9x9. To przesunięcie będzie takie samo dla wszystkich teleporterów tego samego koloru.
- 2 kolory będą reprezentować ściany. Poruszanie się w ścianie jest tym samym, co stanie w bezruchu.
- 2 kolory będą stanowić pułapkę. Pułapka wskazuje, że jedna z 9 komórek w jej bezpośrednim sąsiedztwie jest śmiertelna (niekoniecznie sama komórka pułapki). To przesunięcie będzie takie samo dla wszystkich pułapek tego samego koloru.
O tej naturalnej selekcji ... każdy okaz ma genom, który jest liczbą 100 bitów. Nowe okazy zostaną utworzone przez krzyżowanie dwóch istniejących okazów, a następnie nieznaczną mutację genomu. Im bardziej udany okaz, tym większa szansa na jego rozmnażanie.
Oto twoje zadanie: napiszesz jedną funkcję, która otrzymuje jako dane wejściowe siatkę kolorów 5x5, którą widzi próbka, a także jej genom. Twoja funkcja zwróci ruch (Δx, yy) dla próbki, gdzie Δx i Δy będą jednym z nich {-1, 0, 1}
. Nie wolno utrwalać żadnych danych między wywołaniami funkcji. Obejmuje to używanie własnych generatorów liczb losowych. Twoja funkcja otrzyma rozstawiony RNG, z którego możesz dowolnie korzystać.
Wynik Twojego zgłoszenia będzie średnią geometryczną liczby punktów na 50 losowych ścieżkach. Stwierdziliśmy, że wynik ten jest dość zróżnicowany. Dlatego te wyniki będą wstępne . Kiedy to wyzwanie dobiegnie końca, zostanie ogłoszony termin. Po upływie terminu 100 losowo wybieranych jest 100 plansz, a wszystkie zgłoszenia zostaną zapisane na tych 100 planszach. Możesz wpisać szacunkowy wynik w odpowiedzi, ale sami ocenimy każde zgłoszenie, aby nikt nie oszukiwał.
Udostępniliśmy programy kontrolera w kilku językach. Obecnie możesz napisać swoje zgłoszenie w języku Python (2 lub 3), Ruby , C ++ , C # lub Java . Kontroler generuje plansze, uruchamia grę i zapewnia ramy dla algorytmu genetycznego. Wszystko, co musisz zrobić, to zapewnić funkcję ruchu.
Czekaj, więc co dokładnie robię z genomem?
Wyzwanie polega na zrozumieniu tego!
Ponieważ okazy nie mają pamięci, wszystko, co masz w danej turze, to siatka kolorów 5x5, które nic dla ciebie nie znaczą. Musisz więc użyć genomu, aby osiągnąć cel. Ogólna idea polega na tym, że używasz części genomu do przechowywania informacji o kolorach lub układzie siatki, a twój bot opiera swoje decyzje na dodatkowych informacjach przechowywanych w genomie.
Teraz oczywiście nie można ręcznie niczego tam przechowywać. Tak więc przechowywane tam rzeczywiste informacje będą początkowo całkowicie losowe. Ale algorytm genetyczny wkrótce wybierze te okazy, których genom zawiera właściwą informację, jednocześnie zabijając te, które mają niewłaściwą informację. Twoim celem jest znalezienie mapowania z fragmentów genomu i pola widzenia na ruch, który pozwala szybko znaleźć ścieżkę do celu i który konsekwentnie ewoluuje do zwycięskiej strategii.
To powinno wystarczyć do rozpoczęcia pracy. Jeśli chcesz, możesz pominąć następną sekcję i wybrać kontroler z listy kontrolerów u dołu (która zawiera również informacje o tym, jak używać tego konkretnego kontrolera).
Czytaj dalej, jeśli chcesz wszystko ...
Krwawe szczegóły
Ta specyfikacja jest kompletna. Wszyscy administratorzy muszą wdrożyć te reguły.
Wszelka losowość wykorzystuje rozkład równomierny, chyba że zaznaczono inaczej.
Generowanie torów:
- Ścieżka ma prostokątną siatkę, szerokość X = 53 komórki i wysokość Y = 15 komórek. Komórki zx ≥ 49 są komórkami docelowymi (gdzie x jest zerowy).
- Każda komórka ma jeden kolor i może, ale nie musi, być śmiertelna - komórki nie są śmiertelne, chyba że określi je jeden z poniższych typów komórek.
- Istnieje 16 różnych kolorów komórek, oznaczonych od
0
do15
, których znaczenie zmieni się z gry na grę. Ponadto-1
reprezentuje komórki, które są poza granicami - są śmiertelne . - Wybierz 8 losowych kolorów . Będą to puste komórki (które nie działają).
- Wybierz 4 więcej losowych kolorów . To są teleportery. Dla dwóch z tych kolorów wybierz niezerowe przesunięcie w sąsiedztwie 9x9 (od (-4, -4) do (4,4) z wyjątkiem (0,0)). Dla pozostałych dwóch kolorów odwróć te przesunięcia. Jeżeli próbka nadepnie na teleporter, zostanie natychmiast przesunięta o to przesunięcie.
- Wybierz jeszcze 2 losowe kolory . To są pułapki. Dla każdego z tych kolorów wybierz przesunięcie w sąsiedztwie 3x3 (od (-1, -1) do (1,1)). Pułapka wskazuje, że komórka w tym przesunięciu jest śmiertelna . Uwaga: Sama komórka pułapkowa niekoniecznie jest śmiertelna.
- Do 2 Pozostałe kolory są ściany, które utrudniają ruch. Próba przejścia na komórkę ścienną zmieni ruch w nieruchomy. Same komórki ścienne są śmiertelne .
- Dla każdej komórki niebędącej celem siatki wybierz losowy kolor. Dla każdej komórki celu wybierz losowy pusty kolor.
- Dla każdej komórki na lewej krawędzi toru ustal, czy cel można osiągnąć w ciągu 100 obrotów (zgodnie z poniższymi zasadami kolejności zwrotów ). Jeśli tak, ta komórka jest dopuszczalną komórką początkową . Jeśli jest mniej niż 10 komórek początkowych, odrzuć ścieżkę i wygeneruj nową.
- Utwórz 15 okazów, każdy z losowym genomem i wieku 0 . Umieść każdą próbkę w losowej początkowej komórce.
Kolejność:
- Dla każdej próbki zostaną wykonane kolejno następujące kroki. Okazy nie wchodzą w interakcje ani nie widzą się nawzajem i mogą zajmować tę samą komórkę.
- Jeśli wiek okazu wynosi 100 , umiera. W przeciwnym razie zwiększ jego wiek o 1.
- Próbka otrzymuje swoje pole widzenia - siatkę kolorów 5x5, wyśrodkowaną na próbce - i zwraca ruch w sąsiedztwie 3x3. Przesunięcie poza ten zakres spowoduje zakończenie pracy sterownika.
- Jeśli komórką docelową jest ściana, ruch zmienia się na (0,0).
- Jeśli komórką docelową jest teleporter, próbka zostaje przesunięta o przesunięcie teleportera. Uwaga: Ten krok jest wykonywany raz , a nie iteracyjnie.
- Jeśli komórka zajmowana obecnie przez próbkę (potencjalnie po użyciu jednego teleportera) jest śmiertelna, próbka umiera. Jest to jedyny czas, w którym próbki umierają (oprócz kroku 1.1. Powyżej). W szczególności nowy okaz, który odradza się w śmiertelnej komórce, nie umrze natychmiast, ale ma szansę na pierwsze zejście z niebezpiecznej komórki.
- Jeśli próbka zajmuje komórkę celu, zdobądź punkt, przenieś próbkę do losowej komórki początkowej i zresetuj jej wiek do 0.
- Jeśli na planszy pozostały mniej niż dwa okazy, gra się kończy.
- Utwórz 10 nowych próbek w wieku 0 lat . Każdy genom jest określany (indywidualnie) na podstawie poniższych reguł hodowlanych. Umieść każdą próbkę w losowej początkowej komórce.
Hodowla:
Po utworzeniu nowego okazu wybierz losowo dwóch różnych rodziców, z nastawieniem na osobniki, które posunęły się dalej w prawo. Prawdopodobieństwo wyboru próbki jest proporcjonalne do jej aktualnej oceny kondycji . Ocena kondycji okazu wynosi
1 + x + 50 * ile razy osiągnął cel
gdzie x jest wskaźnikiem poziomym opartym na 0. Okazy utworzone w tej samej turze nie mogą być wybrane jako rodzice.
Z dwojga rodziców wybierz losowego, z którego zostanie pobrany pierwszy bit genomu.
- Teraz, gdy idziesz wzdłuż genomu, przełączaj rodziców z prawdopodobieństwem 0,05 i nadal pobieraj kawałki od wynikowego rodzica.
- Zmutuj w pełni złożony genom: dla każdego bitu odwróć go z prawdopodobieństwem 0,01 .
Punktacja:
- Jedna gra trwa 10 000 tur.
- Gracze rozpoczynają grę z 1 punktem (aby umożliwić użycie średniej geometrycznej).
- Za każdym razem, gdy okaz osiąga cel, gracz zdobywa punkt.
- Na razie zgłoszenie każdego gracza zostanie uruchomione na 50 gier, każda z inną losową ścieżką.
- Powyższe podejście powoduje większą wariancję niż jest to pożądane. Kiedy to wyzwanie dobiegnie końca, zostanie ogłoszony termin. Po upływie terminu 100 losowo wybieranych jest 100 plansz, a wszystkie zgłoszenia zostaną zapisane na tych 100 planszach.
- Ogólny wynik gracza jest średnią geometryczną wyników poszczególnych gier.
Kontrolery
Możesz wybrać jeden z następujących kontrolerów (ponieważ są one funkcjonalnie równoważne). Przetestowaliśmy je wszystkie, ale jeśli zauważysz błąd, chcesz poprawić kod lub wydajność, lub dodasz funkcję graficzną, wyślij zgłoszenie problemu lub wyślij żądanie ściągnięcia na GitHub! Możesz również dodać nowy kontroler w innym języku!
Kliknij nazwę języka dla każdego kontrolera, aby przejść do właściwego katalogu na GitHub, który zawiera README.md
dokładne instrukcje użytkowania.
Jeśli nie znasz git i / lub GitHub, możesz pobrać całe repozytorium jako plik ZIP ze strony głównej (patrz przycisk na pasku bocznym).
Pyton
- Najbardziej dokładnie przetestowany. To jest nasza referencyjna implementacja.
- Działa zarówno z Python 2.6+, jak i Python 3.2+!
- Jest bardzo wolny. Zalecamy korzystanie z PyPy w celu znacznego przyspieszenia.
- Obsługuje wyjście graficznego korzystając albo
pygame
albotkinter
.
Rubin
- Testowane z Ruby 2.0.0. Powinien działać z nowszymi wersjami.
- Jest również dość powolny, ale Ruby może być dogodny do prototypowania pomysłu na przesłanie.
C ++
- Wymaga C ++ 11.
- Opcjonalnie obsługuje wielowątkowość.
- Zdecydowanie najszybszy kontroler w grupie.
DO#
- Używa LINQ, więc wymaga .NET 3.5.
- Raczej powolny.
Jawa
- Niezbyt wolno. Niezbyt szybko.
Wstępna tablica wyników
Wszystkie wyniki są wstępne. Jeśli jednak coś jest nie tak lub nieaktualne, daj mi znać. Nasze przykładowe przesłanie jest wymienione w celach porównawczych, ale nie jest niezgodne.
Score | # Games | User | Language | Bot
===================================================================================
2914.13 | 2000 | kuroi neko | C++ | Hard Believers
1817.05097| 1000 | TheBestOne | Java | Running Star
1009.72 | 2000 | kuroi neko | C++ | Blind faith
782.18 | 2000 | MT0 | C++ | Cautious Specimens
428.38 | | user2487951 | Python | NeighborsOfNeighbors
145.35 | 2000 | Wouter ibens | C++ | Triple Score
133.2 | | Anton | C++ | StarPlayer
122.92 | | Dominik Müller | Python | SkyWalker
89.90 | | aschmack | C++ | LookAheadPlayer
74.7 | | bitpwner | C++ | ColorFarSeeker
70.98 | 2000 | Ceribia | C++ | WallGuesser
50.35 | | feersum | C++ | Run-Bonus Player
35.85 | | Zgarb | C++ | Pathfinder
(34.45) | 5000 | Martin Büttner | <all> | ColorScorePlayer
9.77 | | DenDenDo | C++ | SlowAndSteady
3.7 | | flawr | Java | IAmARobotPlayer
1.9 | | trichoplax | Python | Bishop
1.04 | 2000 | fluffy | C++ | Gray-Color Lookahead
Kredyty
To wyzwanie było ogromnym wysiłkiem polegającym na współpracy:
- Nathan Merril: Napisałem kontrolery Python i Java. Przekształcił koncepcję wyzwania z King-of-the-Hill w wyścig szczurów.
- trichoplax: Playtesting . Pracował na kontrolerze Python.
- feersum: Napisałem kontroler C ++.
- VisualMelon: Napisałem kontroler C #.
- Martin Büttner: Koncepcja. Napisałem kontroler Ruby. Testowanie Pracował na kontrolerze Python.
- T Abraham: Playtesting. Przetestowałem Python i przejrzałem kontrolery C # i C ++.
Wszyscy powyżsi użytkownicy (i pewnie jeszcze kilku zapomniałem) przyczynili się do ogólnej konstrukcji wyzwania.
Aktualizacja kontrolera C ++
Jeśli używasz C ++ z Visual Studio i wielowątkowością, powinieneś otrzymać najnowszą aktualizację z powodu błędu w ich generowaniu liczb losowych, który pozwala na tworzenie duplikatów kart.
źródło
'In particular, a new specimen which spawns on a lethal cell will not die immediately, but has a chance to move off the dangerous cell first.'
Odpowiedzi:
Ślepa wiara - C ++ - wydaje się osiągać ponad 800 (!) W 2000 rund
Genom kodujący kolory z tajemniczym sprzężeniem zwrotnym śladu i skutecznym środkiem odstraszającym uderzenia w ścianę
Przykładowe wyniki:
Na podstawie nieludzko długiego testu Feersum, uważam, że 2000 przebiegów wystarczy, aby uzyskać akceptowalnie stabilny wynik.
Ponieważ mój zmodyfikowany kontroler wyświetla bieżącą średnią geometryczną po każdym przebiegu, wizualnie potwierdziłem, że zmiana w ciągu ostatnich 50 przebiegów była stosunkowo niewielka (+ - 10 punktów).
Co sprawia, że te zwierzątka tykają
Zamiast nadawać równe priorytety każdemu kolorowi, rozważam te możliwe wartości:
Chociaż jestem zbyt leniwy, aby zmienić jego nazwę, to raczej „wykrywacz niebezpieczeństwa” wskazujący (rzekomą) lokalizację rzeczywistej pułapki, ściany, teleportera czekającego na wysłanie niczego nie podejrzewającego wędrowca w nieprzyjemne miejsce, a nawet wejścia do martwego -koniec. Krótko mówiąc, miejsce, do którego mądry szczur raczej by nie poszedł.
dobre lub złe geny przechowują tylko 2 bity (na przykład
11
i10
), ale pułapki wymagają 4 bitów (0ttt
gdziettt
reprezentuje jedną z 8 możliwych „niebezpiecznych” lokalizacji).Aby zachować spójność każdego genu (tj. Zachować jego znaczenie po zmieszaniu z całkowicie innym genomem, co wymaga, aby każdy gen kodujący kolor znajdował się w ustalonej lokalizacji), wszystkie wartości są kodowane na 4 bitach (tak dobre są kodowane jako złe,
11xx
a złe jako10xx
), w sumie 16 * 4 = 64 bity.Pozostałe 36 bitów jest używanych jako „anti-wall-banger” (więcej na ten temat później). 25 otaczających kolorów jest mieszanych w indeksie tych 36 bitów. Każdy bit wskazuje preferowany kierunek pionowy (w górę lub w dół), który jest używany, gdy istnieje możliwość wyboru między dwiema komórkami.
Strategia jest następująca:
Wy, gryzonie, patrzcie na wrogów waszych
Najgorsze, co może spotkać populację, to nie dać jeszcze zwycięzcy, ale wiele szczurów utknęło albo pod ścianą, albo w nieskończonej pętli teleportacyjnej wystarczająco blisko celu, aby mieć dominującą szansę na selekcję do hodowli .
W przeciwieństwie do szczurów zgniatanych w pułapkę lub teleportowanych do ścian, gryzonie te zostaną zabite tylko do starości.
Nie mają przewagi konkurencyjnej nad kuzynami, którzy od początku utknęli w 3 komórkach, ale będą mieli wystarczająco dużo czasu na rozmnażanie pokolenia za pokoleniem kretyn, aż ich genom stanie się dominujący, szkodząc w ten sposób różnorodności genetycznej bez uzasadnionego powodu.
Aby złagodzić to zjawisko, chodzi o to, aby potomstwo tych złych, złych szczurów unikało podążania śladami ich przodków.
Wskazanie kierunku pionowego ma tylko 1 bit (mówiąc w zasadzie „spróbuj najpierw wejść w górę lub w dół w tych okolicach”), a całkiem sporo bitów prawdopodobnie będzie miało wpływ na ścieżkę, więc mutacje i / lub zwrotnice powinny mieć Znaczący wpływ.
Wiele potomstwa będzie miało inne zachowanie i nie będzie w końcu uderzać głową w tę samą ścianę (wśród zwłok ich głodujących przodków).
Subtelność polega na tym, że to wskazanie nie jest dominującym czynnikiem w zachowaniu szczura. W większości przypadków nadal dominować będzie interpretacja kolorów (wybór góra / dół będzie miał znaczenie tylko wtedy, gdy rzeczywiście są dwa „dobre”a to, co szczur uważa za nieszkodliwy kolor, nie jest teleporterem czekającym na wrzucenie go do ściany).
Dlaczego to (wydaje się) działa?
Nadal nie wiem dokładnie dlaczego.
Absolutnym ciosem szczęścia, który pozostaje nierozwiązaną tajemnicą, jest logika mapowania pułapek. Bez wątpienia jest kamieniem węgielnym sukcesu, ale działa na swój tajemniczy sposób.
Przy stosowanym kodowaniu losowy genom wytworzy 25% „dobrych”, 25% „złych” i 50% „pułapkowych” identyfikatorów kolorów.
identyfikatory „pułapki” z kolei generują „dobre” i „złe” oszacowania w korelacji z otoczeniem 5x5.
W rezultacie szczur w danym miejscu „zobaczy” świat jako mieszankę stabilnych i kontekstowych kolorów „iść / nie iść”.
Jak się wydaje dość skuteczny mechanizm przeciwdziałający uderzeniom, najgorszym elementem na torze jest przerażająca ściana (i jej kuzyn pętla teleportacyjna, ale myślę, że są one znacznie mniej powszechne).
Wniosek jest taki, że udany program musi przede wszystkim ewoluować szczurom zdolnym do wykrycia pozycji, które doprowadzą do powolnego głodu bez osiągnięcia celu.
Nawet bez „odgadnięcia” dwóch kolorów reprezentujących ściany, kolory „pułapki” wydają się przyczyniać do unikania ścian, umożliwiając szczurowi omijanie kilku przeszkód nie dlatego, że „widział” ściany, ale dlatego, że oszacowanie „pułapki” wykluczyło te konkretne komórki ścienne w tym konkretnym otoczeniu.
Chociaż szczur próbuje zbliżyć się do celu (co może prowadzić do przekonania, że najbardziej „przydatne” wskaźniki pułapek wskazują na niebezpieczeństwo z przodu), myślę, że wszystkie kierunki pułapek mają w przybliżeniu taki sam wpływ: pułapka wskazująca „niebezpieczeństwo za sobą” „umieszczone 2 komórki przed szczurem mają taki sam wpływ, jak ten, który wskazuje„ niebezpieczeństwo przed sobą ”, gdy szczur stoi tuż nad nim.
Dlaczego ta mieszanka ma tę właściwość, że genom tak skutecznie się zbiega, jest niestety daleko poza moimi matematykami.
Czuję się lepiej z odstraszającym uderzeniem w ścianę. Po prostu zadziałało to zgodnie z planem, ale znacznie powyżej moich oczekiwań (wynik został w zasadzie pomnożony przez cztery).
Mocno zhakowałem kontroler, aby wyświetlić niektóre dane. Oto kilka przebiegów:
Tutaj wcześnie pojawiła się rasa superszczurów (tor prawdopodobnie pozwalał biegać w linii prostej, a niektórzy szczur w pierwszych pokoleniach mieli odpowiednie DNA, aby z niego skorzystać). Liczba okazów na końcu to około połowa teoretycznego maksimum około 100 000 szczurów, co oznacza, że prawie połowa zwierząt zyskała zdolność do przetrwania na tym konkretnym torze w nieskończoność (!).
Oczywiście wynik jest po prostu nieprzyzwoity - tak na marginesie - czas obliczeń.
Tutaj możemy zobaczyć udoskonalenie genomu w pracy. Linia między dwoma ostatnimi genomami jest wyraźnie widoczna. Najważniejsze są dobre i złe oceny. Te pułapki przesłanki zdają się drgać, aż do ustabilizowania albo „pożyteczne” pułapkę lub mutować w dobry lub zły .
Wygląda na to, że geny kolorów mają kilka przydatnych cech:
(konkretny kolor należy traktować w określony sposób)
Każde kodowanie kolorów można wrzucić do zupełnie innego genomu bez radykalnej zmiany zachowania - chyba że kolor rzeczywiście jest decydujący (zazwyczaj ściana lub teleporter prowadzący do nieskończonej pętli).
Jest tak mniej w przypadku podstawowego kodowania priorytetowego, ponieważ najbardziej priorytetowy kolor jest jedyną informacją używaną do decydowania, gdzie się przenieść. Tutaj wszystkie „dobre” kolory są równe, więc dany kolor dodany do listy „dobrych” będzie miał mniejszy wpływ.
dobre / złe kodowanie ma tylko 2 znaczące bity z 4, a lokalizacja pułapki może być zmieniana przez większość czasu bez znaczącej zmiany zachowania szczura.
Gen mutujący się w „dobry” albo będzie miał niewielki wpływ (jeśli na przykład odpowiada pustej komórce, może pozwolić na znalezienie nowej, krótszej ścieżki, ale może również doprowadzić szczura do pułapka) lub dramatyczna (jeśli kolor reprezentuje ścianę, nowy szczur prawdopodobnie utknie gdzieś).
Gen przechylający się do „pułapki” albo pozbawi szczura niezbędnego koloru, albo nie będzie miał zauważalnego efektu.
Mutacja lokalizacji pułapki będzie miała znaczenie tylko wtedy, gdy rzeczywiście będzie przed nią pułapka (lub coś szkodliwego), co ma względnie małe prawdopodobieństwo (powiedziałbym, że 1/3).
Wreszcie, wydaje mi się, że ostatnie 36 bitów przyczynia się nie tylko do uniknięcia utknięcia szczurów, ale także do bardziej równomiernego rozłożenia szczurów na torze, zachowując w ten sposób różnorodność genetyczną, dopóki nie powstanie zwycięski genom i stanie się dominujący poprzez część kodującą kolory.
Dalsza praca
Muszę powiedzieć, że uważam te małe stworzenia za fascynujące.
Jeszcze raz dziękuję wszystkim uczestnikom tego wspaniałego wyzwania.
Zastanawiam się, czy jeszcze bardziej zahartować kontrolera, aby wyświetlał bardziej znaczące dane, takie jak pochodzenie udanego szczura.
Bardzo chciałbym też zobaczyć te szczury w akcji, ale ten język C ++ b ** ch języka sprawia, że tworzenie - nie mówiąc już o animacji - obrazów (wśród wielu innych rzeczy) jest bałaganiarskim obowiązkiem.
Na koniec chciałbym przedstawić przynajmniej wyjaśnienie systemu pułapek i ewentualnie je ulepszyć.
Hakowanie kontrolera
Jeśli ktoś jest zainteresowany, mogę opublikować wprowadzone przeze mnie zmiany w kontrolerze.
Są brudne i tanie, ale wykonują swoją pracę.
Nie jestem zaznajomiony z GitHub, więc musiałbym przejść przez zwykły post.
źródło
^^v^vvv^^^vv^^v^vvv^v^^vvvv^^^^^^^^^
myśli? Resztę zgaduję, ale mam z tym problem?Trudni wyznawcy - C ++ - (ulepszone teleportery): 10.000+ na 2000 przebiegów
(jest to ewolucja ślepej wiary , więc możesz wspiąć się na kolejną ścianę tekstu przed tą)
Odcinek IV: Ukierunkowanie się na starcie
Wyniki
Zmieniłem na g ++ / MinGW i 3 wątki.
Kod generowany przez GNU jest ponad dwa razy szybszy niż Microsoft.
Nic dziwnego, co z ich przerażającą implementacją STL.
Teleportery
Efekt teleportacji jest wysoce zależny od pozycji. Do tej pory z przyjemnością uważałem teleporter za zawsze dobry (postrzegany jako pusta przestrzeń) lub zawsze zły (postrzegany jako ściana, aby żaden gryzoń nigdy go nie wziął).
To zbyt gruby model.
Dany teleporter może pchać szczura do przodu, aż kilka komórek od bramki, ale gdy już tam jest, ten sam teleporter może wyrzucić szczura z planszy.
Taki teleporter najprawdopodobniej zostanie rozpoznany jako przejezdny (ponieważ zwiększa sprawność szybciej niż podczas „chodzenia” do tej samej lokalizacji x), stanie się częścią dominującego genomu i zabije prawie wszystkie szczury, które ufają mu jako „zawsze bezpieczne”.
Ponieważ szczury nie mają możliwości poznania swojej pozycji X, jedynym rozwiązaniem do wykrycia tych zdradzieckich teleporterów jest decyzja, czy nadepnąć na nie w oparciu o jedyne dostępne dane kontekstowe, tj. Siatkę kolorów 5x5.
Aby to zrobić, zdefiniowałem 4 rodzaje genów kolorów:
Chodzi o to, aby spróbować odróżnić teleporter, patrząc na jego najbliższych 8 sąsiadów. Ponieważ prawdopodobieństwo posiadania 8 identycznych sąsiadów w danej lokalizacji jest bardzo niskie, powinno to pozwolić na zidentyfikowanie unikalnego wystąpienia każdego teleportera.
8 sąsiednich kolorów można łączyć w celu utworzenia lokalnego podpisu, który jest niezmienny w zależności od pozycji w labiryncie. Niestety, 8 sąsiadów jest widocznych tylko dla komórek znajdujących się w wewnętrznym kwadracie pola widzenia 3x3, więc podpisy będą niedokładne na brzegu pola widzenia.
Niemniej jednak da nam to stałą informację kontekstową w bezpośrednim sąsiedztwie, co wystarcza, aby zwiększyć prawdopodobieństwo pomyślnej nawigacji teleporterów.
geny wiązki mają zmienne pole bitowe o długości 2 bitów.
Dla danego podpisu lokalnego teleportera istnieje jedna szansa na cztery, że komórka wiązki zostanie uznana za nieprzekraczalną. Każda wartość pola wybiera jedną z tych czterech możliwości.
W rezultacie mutacja genu wiązki na tych 2 bitach przejdzie przez 4 możliwe kontekstowe znaczenia koloru.
Poza tym najważniejszymi kolorami do odgadnięcia są wciąż ściany i pułapki. Oznacza to, że powinniśmy pozwolić na wykrycie teleportera dopiero po tym, jak szczury dowiedzą się, gdzie są ściany i pułapki.
Odbywa się to poprzez jedynie rzadkie aktualizowanie lokalnych podpisów. Obecne kryterium aktualizacji podpisu lokalnego ma być w pobliżu koloru określonego jako potencjalny teleporter.
Kodowanie wykorzystuje 5 bitów na gen koloru i grupy w celu uwolnienia 3 mniej znaczących bitów w celu zakodowania wartości 0..7:
Każdy gen wiązki ma 1/4 szansy na uznanie za blok i 3/4 szansy na uznanie za puste, więc 4 wiązki reprezentują średnio 1 blok i 3 puste.
Średni odsetek reprezentowany przez losowy rozkład 16 kolorów wynosi zatem:
Ta mieszanka wydaje się dawać jak dotąd najlepsze wyniki, ale nie skończyłem jej przerabiania.
Zmienność genu
Jedno jest pewne: wartości kodu wybrane do reprezentowania typów genów mają kluczowe znaczenie. Odwrócenie dwóch wartości może kosztować 2000 punktów lub więcej.
Tu znowu powód, dla którego nie mam matematyki.
Domyślam się, że prawdopodobieństwa mutacji z jednego rodzaju na inny muszą być zrównoważone, bo inaczej, podobnie jak w macierzy Markowskiej, skumulowane prawdopodobieństwa ograniczają wartości do podzbioru o najwyższych prawdopodobieństwach przejścia.
Ścieżka na ratunek
Ścieżka znacznie zmniejszy liczbę odwiedzanych komórek, umożliwiając testowanie tylko tych, którzy najprawdopodobniej doprowadzą do celu. W ten sposób nie tylko unika się częstych ślepych zaułków, ale również znacznie częściej wykrywa się błędne kody kolorów.
W rezultacie czas konwergencji jest znacznie skrócony.
Nie pomaga to jednak w rozwiązywaniu map, w których genom nie jest w stanie uzyskać właściwej reprezentacji ścieżki.
Co zrobić z kretynami?
Po wizualnym spojrzeniu na tor zrozumiałem, dlaczego domyślna strategia, która próbuje iść naprzód, nawet gdy wydaje się, że są tylko ściany z przodu, jest naprawdę lepsza niż powstrzymywanie się.
„ściany” mogą być w rzeczywistości teleporterami, które dają tak wiele niefortunnych wyników, że genom odwzorowuje je jako przeszkody, których nigdy nie należy deptać, ale w rzadkich przypadkach szczególny przypadek tego niegrzecznego teleportera może mieć pozytywny (lub przynajmniej nie śmiertelny) efekt , więc zabranie go zamiast cofnięcia się zwiększa szanse na znalezienie drogi do zwycięstwa.
Wczesna konwergencja
Wydaje mi się, że częstość mutacji jest nieco za niska (przynajmniej dla moich gryzoni).
Obecne ustawienie 0,01 daje DNA 37% szans na przetrwanie nienaruszonego procesu mutacji. Zmiana parametru na 0,0227 obniża to prawdopodobieństwo do około 10%
Ponownie wykonałem dokładnie ten sam test (używając ustalonej sekwencji losowych nasion) z prawdopodobieństwem 10%.
Na wielu mapach poprzednie awarie okazały się (ograniczonymi) sukcesami. Z drugiej strony, ogromne eksplozje populacji były mniejsze (co miało ciekawy efekt uboczny przyśpieszania obliczeń).
Mimo że bardzo wysokie wyniki (ponad milion) były mniej powszechne, liczba udanych przebiegów była więcej niż wystarczająca, aby to zrekompensować.
Ostatecznie średnia wzrosła z 1400+ do około 2000.
Przeciwnie, ustawienie P na 5% dało średnią około 600.
Zakładam, że wskaźnik mutacji był tak wysoki, że genom zwycięskich szczurów zbyt często przekształcał się w mniej wydajne warianty.
Jak to działa?
Dzięki dodanym detektorom teleportera liczba nieudanych gier (wynik <10) znacznie spadła.
W próbie z 2000 przebiegami odnotowano tylko 1/3 awarii.
Średnia geometryczna wzrosła tylko z 2900 do 3300, ale liczba ta nie odzwierciedla poprawy.
Puste kolory są często zgadywane jako belki i niebezpieczeństwa (zwykle 2 do 5). Genom „używa” tych kolorów do blokowania ścieżek, które mogłyby wpędzić szczury w kłopoty.
Genom jest całkiem dobry w zgadywaniu pułapek (tj. Gdy szczury osiągną cel, kolory reprezentujące rzeczywiste detektory pułapek są zgadywane w około 90% przypadków).
Wykorzystuje także nowe kody wiązek dla teleporterów, choć rzadziej (prawdopodobnie dlatego, że „zdradzieckie” teleportery są mniej powszechne niż pułapki, a inne kolory wiązek / niebezpieczeństwa ewoluują, aby zablokować ścieżkę do ostatnich przypadków tych zdrajców).
Sądząc po liczbie gier, w których zwycięski genom pojawia się po 5000 lub więcej turach, sądzę, że ta nowa rasa skorzystałaby znacznie na zwiększonej częstości mutacji.
źródło
ColorScorePlayer, wstępny wynik ≈ 22
To jest bot, którego widzisz w pracy w GIF w wyzwaniu.
To był nasz bot testowy w fazie projektowania. Wykorzystuje genom do przechowywania wyniku jakości dla każdego z 16 kolorów. Następnie wykonuje ruch do przodu, który przesuwa go na kolor z najlepszym wynikiem (i nigdy nie przechodzi na
-1
). W przypadku remisu wybierany jest losowy ruch między komórkami wiążącymi.Ten odtwarzacz został przeniesiony na wszystkie języki kontrolera, więc działa on jako przykład sposobu ich użycia:
Pyton
Rubin
C ++
DO#
Jawa
Gracz zdobywa dość niekonsekwentnie. Oto 50 losowych przebiegów:
źródło
ColorFarSeeker, C ++ ≈ 74,7
To wyzwanie jest naprawdę zabawne i proste, jeśli spróbujesz.
Nie zniechęcaj się długim opisem.
Wystarczy odwiedzić GitHub i sprawdzić ... wszystko będzie znacznie wyraźniejsze! :)
Symulator C ++ jest wysoce zalecany ze względu na szybkość. Nawet po tym, jak skończyłem tłumaczyć mój program pythonowy na C ++, symulacja pythonowa wciąż się nie kończy.
To ulepszona odmiana ColorScorePlayer. Aby dobrze wykorzystać widok 5x5, rozważa przesunięcie o 2 kroki od niego za pomocą funkcji ważonej. Przesuwa się o 1 krok przed nim, zyskuje większą wagę, ponieważ mają bardziej bezpośredni wpływ na przetrwanie. Przejdź 2 kroki do przodu, aby otrzymać mniejszą wagę.
Próbuje iść do przodu, ale jeśli nie widać bezpiecznego ruchu ... to próbuje na boki ... a jeśli wszystko inne zawiedzie, przesuwa się losowo do tyłu.
Wynik:
Jest całkiem sporo jedynek ... które mogą być odrobinę przygnębiające, gdy konsola wyrzuca 1 po sobie. Jak planeta ze wszystkimi niezbędnymi do życia rzeczami, ale bez oznak zaawansowanej cywilizacji szczurów ...
Potem okazjonalny skok. :)
Hmm ... najwyraźniej miałem szczęście z pierwszą partią biegów, otrzymując geometrię 300+. Wyniki naprawdę bardzo się wahają. Ale w każdym razie, przy większej liczbie uruchomień symulatora, jest on prawdopodobnie bliższy 74.. (Dzięki za pomoc w symulacji i jego niesamowity szybki program)
źródło
Bishop - Python, wstępny wynik 1,901
Biskup zawsze porusza się po przekątnej, więc połowa planszy jest niedostępna podczas danej wędrówki w poprzek planszy, ale oznacza to mniej potencjalnych ruchów do zakodowania, więc każdy pojedynczy fragment genomu może reprezentować ruch (Biskup nigdy się nie wycofuje). Który bit, do którego należy się odwoływać, jest ustalany na podstawie bloku kwadratów 3x3 przed (po prawej stronie) próbką. Najlepszym ruchem w danej sytuacji jest tylko jedna bitowa mutacja.
Ten bot najpierw szybko się uczy, ale potem często uderza w sufit, zanim dotrze do mety, prawdopodobnie w przypadku wystąpienia jednego z dwóch następujących problemów:
Kod
Pomimo tych ograniczeń, w rzadkich przypadkach Biskup ma się dobrze, a poszczególne osobniki wypełniają kilka okrążeń planszy każdy. Myślałem, że na danym okrążeniu okaz może poruszać się tylko o połowę planszy (co odpowiada tylko czarnym kwadratom lub tylko białym kwadratom na szachownicy). Jednak, jak zauważył Martin Büttner, teleporter może przenieść okaz z czarnego kwadratu na biały kwadrat lub odwrotnie, więc na większości desek nie będą one ograniczone.
(Istnieją dwie pary dopasowanych typów teleporterów i każda z nich ma prawdopodobieństwo 0,5 przesunięcia, które przesuwa próbkę do drugiej połowy czarnych i białych kwadratów. Zatem prawdopodobieństwo, że tablica będzie miała tylko teleportery ograniczające próbkę do jednego połowa planszy na jedno okrążenie to tylko 0,25).
Wyniki pokazują, że okazjonalne triumfy są przeplatane długimi okresami nieosiągnięcia mety:
źródło
Run-bonus player: średnia geometryczna 50,35 (test w 5000 gier)
Ten bot ocenia kwadraty według indywidualnych kolorów na podstawie 6-bitowej sekcji DNA, takiej jak gracz oceniający kolory, ale z innym systemem liczbowym. Bot ten był motywowany myślą, że jeden z bitów zmienia wartość wyniku o 32, a inny tylko o 1. Przypisuje wartość n (n + 1) / 2 do serii n kolejnych 1 bitów. Dodatkowo dodaje mechanizm losowy, aby uniknąć utknięcia. Wykona losowy ruch do przodu z szansą 1 na 30.
Dla porównania, gracz z wynikiem kolorowym zdobył 30 do 35 punktów w kilku testach na 1000 gier. Co ciekawe, maksymalny wynik gracza z kolorem mieścił się w przedziale 3-5 milionów, podczas gdy maksymalny bonus run wynosił tylko 200 tys. Premia do uruchomienia korzysta z logarytmicznego systemu punktacji, uzyskując bardziej niezerowy wynik.
Uruchomienie 5000 gier zajęło około 20 minut z 6 wątkami na kontrolerze C ++.
źródło
StarPlayer | C ++ | Wynik: 162 (na podstawie przebiegu 500 gier)
Ten gracz próbuje użyć A *, aby znaleźć najlepszą drogę do przodu. Przypisuje wagi w taki sam sposób, jak ColorScorePlayer i próbuje znaleźć ścieżkę do prawej krawędzi widoku. Wdrożenie nie jest najładniejsze, jakie kiedykolwiek zrobiłem, ale przynajmniej nie jest zbyt wolne.
Przykładowe wyniki:
źródło
WallGuesser - Zdobył 113,266 w teście 1000 gier
Kodowanie
Zrobiłem naprawdę proste kodowanie 6-bitowe / kolorowe. Aby zdekodować kolor [n]
Rozprowadzając bity koloru w genomie, zwiększam szansę, że bity od obojga rodziców zostaną użyte dla każdego koloru.
Ruch
Korzystam z (na pewno niezbyt wydajnego) wyszukiwania opartego na *, aby wyszukać ścieżkę o najniższym koszcie do dowolnego kwadratu z prawej krawędzi. Jeśli kolor zostanie odwzorowany na „zablokowany”, wyszukiwanie nigdy go nie wprowadzi. Jeśli wyszukiwanie nie może znaleźć ścieżki, zakłada, że ten szczur nie jest zdolny do rozmnażania i próbuje go zakończyć, przesuwając jednego w lewo.
Zmniejszenie liczby niezdolnych szczurów
Ponieważ mój genom skutecznie zgaduje, które kwadraty są ścianami lub teleporterami do tyłu, szczury, które nie mają odgadnięć (żadnych kolorów, które odwzorowują na zablokowane), nie są bardzo sprawne. Aby spróbować usunąć te szczury, jeśli żaden kolor nie zostanie oznaczony jako zablokowany, KAŻDY kolor zostanie oznaczony jako zablokowany, a szczur zawsze przesunie się o jeden w lewo.
DO ZROBIENIA
Obecnie w zachowaniu nie ma losowości, więc szczury łatwo mogą utknąć.
źródło
g++ -std=c++11 .\wallguesser.cpp -O2 -o .\wallguesser.exe
. Dostaję dużo błędów, ale pierwszy to.\wallguesser.cpp:47:19: error: 'dna_t' has no member named 'at' if (d.at(i) == true){
at
aby[]
to naprawić.FITTEST - średni wynik geometryczny: ~ 922 (2 tys. Przebiegów)
Moje podejście polega na:
Przetestowałem ponad 2000 zestawów parametrów z tymi samymi 50 nasionami. Wybrano najbardziej obiecujące zestawy, które oceniono za pomocą 250 identycznych nasion, a te z najwyższą rangą stanowiły wkład do następnej rundy testu. Udało mi się stworzyć algorytm genetyczny, aby znaleźć optymalny algorytm genetyczny dla tego problemu, zgodnie z sugestią użytkownika mbomb007 .
Pożądane zachowanie:
Metody przechowywania danych:
Chcemy, aby gatunek nauczył się różnych rzeczy, przystosował do swojego środowiska, stał się najsilniejszy. Nieuchronnie działa to tylko wtedy, gdy nauka może być w jakiś sposób przechowywana. Uczenie zostanie „zapisane” w 100 bitach DNA. To dziwny sposób przechowywania, ponieważ nie możemy zmienić wartości naszego DNA. Więc założyć, że DNA już przechowuje informacje o złych i dobrych ruchów. Jeśli dla określonego gatunku przechowywana jest poprawna informacja w jego DNA, przejdzie on szybko do przodu i stworzy wiele nowych gatunków z jego DNA.
Odkryłem, że średnia geometryczna wyniku jest wrażliwa na sposób przechowywania informacji. Załóżmy, że czytamy pierwsze 4 bity ze 100 bitów DNA i chcemy zapisać to jako zmienną całkowitą. Możemy to zrobić na kilka sposobów:
dnarange
, przykład:1011
4 bity zamieniają się w „1x2 ^ 3 + 0x2 ^ 2 + 1x2 ^ 1 + 1x2 ^ 0 = 15. Możliwe wartości (dla 4 bitów): [0, 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]dnaStreakRange
funkcji (zdefiniowanej poniżej), przykład: stanie się 4bity 10111x1 + 0x1 + 1x1+ 1x2 = 4
. Możliwe wartości (dla 4 bitów): [0, 1, 2, 3, 6, 10]dnaCountRange
funkcji (zdefiniowanej poniżej), przykład: stanie się 4bity 10111x1 + 0x1 + 1x1 + 1x1 = 3
. Możliwe wartości (dla 4 bitów): [0, 1, 2, 3, 4]Różnice między metodami przechowywania są następujące:
Priorytetyzuj rozwiązania.
Gdy ColorScorePlayer zidentyfikuje dwa ruchy do przodu z identycznymi wynikami, dokonuje się arbitralnego wyboru. IMHO, nigdy nie należy używać funkcji
v.rng.rint()
funkcji losowych . Zamiast tego powinieneś wykorzystać tę szansę na uzyskanie równych wyników jako haka do oceny rozwiązań dla efektów drugiego rzędu.Efekt pierwszego rzędu otrzymuje najwyższy priorytet. Jeśli osiągnięte zostaną równe wyniki, pierwszeństwo ma rozwiązanie z priorytetem 2 i tak dalej. Dostosowując parametry rozwiązania, możesz wpłynąć na prawdopodobieństwo wystąpienia równych wyników i w ten sposób zmienić wagę rozwiązań o priorytecie 1 i priorytecie 2.
Realizacja pożądanego zachowania
Dowiedz się, które kolory są bezpieczne:
threshold = 63/3=21
, gdzie 63 to maksymalny wynik dla 6 bitów, a 33% = 1/3 (można to zobaczyć na powyższym wykresie).Jeśli żadne dobre ruchy nie są dostępne, przesuń się w pionie lub w tył:
weightMove
zmienną.Zobacz, co jest poza:
x2
iy2
pętle), która opcja jest najlepsza (poprzezmainSubScore
zmienną). Najbardziej odpowiednia kolumna w tym polu 3x3 prowadzi.Zidentyfikuj pułapki:
Zbadałem DNA gatunku o najwyższym wyniku, gdy dowolna gra zakończyła się przechowywaniem bitsum4 (więc ocena koloru ma zakres [0,4]):
Z tego można wywnioskować, że mury i teleporty uzyskują prawidłowy wynik. Pułapki nie są identyfikowane, ponieważ zależą od kierunku i koloru pochodzenia, podczas gdy punktacja odbywa się na podstawie koloru miejsca docelowego. Dlatego istnieje potrzeba przechowywania również danych dotyczących koloru pochodzenia, więc
v(0,0)
. W idealnym świecie chcielibyśmy przechowywać informacje dla 16 kolorów x 8 kierunków x 3 bity = 384 bity.Niestety dostępnych jest tylko 100 bitów i nie możemy tego wszystkiego użyć, ponieważ potrzebujemy również trochę pamięci na wyjaśnione powyżej rozwiązanie. Dlatego wykonamy 4 kolorowe kosze:
oraz 4 pojemniki kierunku ruchu
Gdy wynik dziesiętny wynosi 4 lub więcej (100,101,110,111), zakłada się, że pułapka jest powiązana z tą komórką, w wyniku czego ruch ten nie zostanie wybrany, gdy pojawią się równe wyniki. Zatem identyfikacja pułapki jest efektem drugiego rzędu, a „zobacz, co jest poza” będzie rozwiązaniem trzeciego priorytetu.
Błędne założenie dotyczące ściany jest wielokrotnie duplikowane przez noworodków:
Niektóre gatunki niepoprawnie zakładają, że ściany są dobre i starają się do nich cały czas się poruszać, dlatego utkną przed ścianami. Mogą również utknąć w nieskończonej pętli teleporterów. Efekt jest taki sam w obu przypadkach.
Głównym problemem jest to, że po kilkuset iteracjach niektóre geny stają się bardzo dominujące . Jeśli są to „właściwe” geny, możesz uzyskać bardzo wysokie wyniki (> 1 milion punktów). Jeśli są one błędne, utkniesz, ponieważ potrzebujesz różnorodności, aby znaleźć „właściwe” geny.
Walenie kretynów: Rozwiązanie 1: odwrócenie kolorów
Pierwszym rozwiązaniem, które wypróbowałem, była próba wykorzystania części nieużywanej pamięci, która wciąż jest bardzo zróżnicowana. Załóżmy, że przydzielono 84 bity do pamięci kolorów i pamięci wyszukiwania pułapek. Pozostałe 16 bitów będzie bardzo zróżnicowanych. Możemy wypełnić 2 zmienne dziesiętne8, które mają wartości w przedziale [0,255] i są one jednorodne, co oznacza, że każda wartość ma szansę 1/256. Zmienne zostaną wywołane
inInverse
iinReverse
.Jeśli
inInverse
wynosi 255 (szansa 1/256), wówczas odwrócimy interpretację wyników kolorów . Tak więc ściana, którą kretyn uważa za bezpieczny ze względu na wysoki wynik, otrzyma niski wynik, a zatem stanie się złym ruchem. Wadą jest to, że wpłynie to również na geny „praw”, więc uzyskamy mniej bardzo wysokich wyników. PonadtoinInverse
gatunek ten będzie musiał się rozmnażać, a jego dzieci również otrzymają części dominującego DNA. Najważniejsze jest to, że przywraca różnorodność.Jeśli
inReverse
wynosi 255 (szansa 1/256), wówczas odwrócimy kolejność pozycji przechowywania wyników kolorów . Więc zanim kolor 0 był zapisywany w bitach 0-3. Teraz kolor 15 zostanie zapisany w tej pozycji. Różnica winInverse
podejściu polega na tym, żeinReverse
cofną pracę wykonaną do tej pory. Wróciliśmy do punktu wyjścia. Stworzyliśmy gatunek, który ma podobne geny, jak w momencie rozpoczęcia gry (z wyjątkiem pamięci znalezienia pułapki)Poprzez optymalizację badane jest, czy jest mądry, aby używać
inInverse
iinReverse
w tym samym czasie. Po zakończeniu optymalizacji wynik nie wzrósł. Problem polega na tym, że mamy bardziej zróżnicowaną populację genów, ale wpływa to również na „właściwe DNA”. Potrzebujemy innego rozwiązania.Morons walczy: Rozwiązanie 2: kod skrótu
Gatunek ma 15 możliwych pozycji początkowych i obecnie istnieje zbyt duża szansa, że pójdzie dokładnie tą samą ścieżką, jeśli zacznie od tej samej pozycji początkowej. Jeśli jest kretynem, który kocha mury, utknie na tej samej ścianie w kółko. Jeśli na szczęście uda mu się dotrzeć do dalekiej ściany, zacznie dominować w puli DNA przy swoich błędnych założeniach. Potrzebujemy, aby jego potomstwo podążyło nieco inną ścieżką (ponieważ dla niego i tak jest już za późno) i nie utknie na dalekiej ścianie, ale na ścianie w pobliżu . Można to osiągnąć, wprowadzając kod skrótu .
Hashcode powinny mieć cel do jednoznacznej identyfikacji i oznakowania aktualną pozycję na planszy. Celem nie jest ustalenie pozycji (x, y), ale udzielenie odpowiedzi na pytania, czy moi przodkowie byli już w tej lokalizacji?
Załóżmy, że masz przed sobą całą planszę i utworzysz jpg każdego możliwego kwadratu 5 na 5 komórek. Otrzymasz (53-5) x (15-5) = 380 zdjęć. Dajmy tym obrazkom numery od 1 do 380. Nasz kod skrótu powinien być postrzegany jako taki identyfikator, z tą różnicą, że nie działa od 1 do 330, ale brakuje IDS, więc np. 563, 3424, 9424, 21245 itp.
Liczby pierwsze
17
i31
są tam, aby zapobiec zniknięciu informacji dodanych na początku pętli. Później więcej o tym, jak zintegrować nasz hashcode z resztą programu.Pozwala zastąpić mechanizm subcoringowy „patrz, co jest poza” innym mechanizmem subcoringowym. Kiedy dwie lub trzy komórki mają takie same wyniki główne, będzie 50% szans na wybranie górnej, 50% szans na wybranie dolnych komórek i 0% szans na wybranie środkowej. Szansa nie zostanie określona przez generator losowy, ale przez bity z pamięci , ponieważ w ten sposób upewniamy się, że w tej samej sytuacji dokonuje się tego samego wyboru.
W idealnym świecie (gdzie mamy nieskończoną ilość pamięci) obliczylibyśmy unikalny kod skrótu dla naszej obecnej sytuacji, np. 25881, i udaliśmy się do miejsca pamięci 25881 i przeczytaliśmy tam, czy powinniśmy wybrać górną lub dolną komórkę (gdy tam jest równym wynikiem). W ten sposób znaleźlibyśmy się w dokładnie takiej samej sytuacji (kiedy np. Po raz drugi podróżujemy po tablicy i zaczynamy w tej samej pozycji) podejmujemy te same decyzje. Ponieważ nie mamy nieskończonej pamięci, zastosujemy modulo wielkości dostępnej pamięci do kodu mieszającego . Obecny hashcode jest dobry w tym sensie, że rozkład po operacji modulo jest jednorodny.
Kiedy potomstwo podróżuje po tej samej planszy z nieznacznie zmienionym DNA, w większości przypadków (> 99%) podejmuje dokładnie taką samą decyzję. Ale im bardziej się zbliża, tym większa szansa, że jego ścieżka będzie inna niż jego przodkowie. Zatem szansa, że utknie na tej odległej ścianie jest niewielka. Utknął na tej samej pobliskiej ścianie, co jego przodek, jest stosunkowo duży, ale nie jest tak źle, ponieważ nie będzie generował dużo potomstwa. Bez metody hashcode szansa utknięcia na pobliskiej i odległej ścianie jest prawie taka sama
Optymalizacja
Po optymalizacji stwierdzono, że tablica identyfikacji pułapki nie jest potrzebna i wystarczają 2 bity na kolor. Pozostała część pamięci 100-2x16 = 68 bitów służy do przechowywania kodu skrótu. Wygląda na to, że mechanizm kodu skrótu jest w stanie uniknąć pułapek.
Zoptymalizowałem dla 15 parametrów. Ten kod zawierał najlepszy zestaw poprawionych parametrów (jak dotąd):
To mój pierwszy program w C ++. Jak większość z was ma teraz doświadczenie w analizie gnomów. Chcę podziękować organizatorom, ponieważ bardzo podobała mi się praca nad tym.
Jeśli masz jakieś uwagi, zostaw komentarz poniżej. Przepraszamy za długie teksty.
źródło
Pathfinder, C ++, wstępny wynik 35,8504 (50 rund)
Całkowity remont! Przeniesiłem mój algorytm do C ++ i trochę go poprawiłem, ale wynik wciąż nie jest zbyt wysoki, prawdopodobnie dlatego, że szczury wciąż walą głową w ściany. Mam dość próbowania tego poprawić, więc na razie pozwolę.
Wyjaśnienie
Ogólną ideą jest sklasyfikowanie każdego koloru jako pułapkę lub nie, a następnie przypisanie kierunków pułapek i ciężarów do pułapek bez pułapek i próba podążenia ścieżką minimalnej masy do prawej granicy siatki wizji.
W pierwszych 80 bitach genomu każdy kolor jest klasyfikowany za pomocą 5 bitów
abcde
. Jeśliab = 01
kolor jest pułapką icde
koduje jego kierunek (osiem możliwości). Jeśliab ≠ 01
kolor nie jest pułapką, a jego waga toa + b + 2*(c + d + e)
.Następnie inicjalizujemy siatkę 3x7, która reprezentuje pole widzenia szczura po jego prawej stronie, wypełnione „nieznanymi” kolorami. Bity 80-84 kodują wagę nieznanych komórek podobnie jak kolory bez pułapek, a bity 85-89 kodują wspólną wagę pułapek. Wypełniamy siatkę ciężarkami, obliczamy najkrótsze ścieżki i dodajemy dodatkowy ciężar (zakodowany w bitach 90-95) do komórek bezpośrednio powyżej i poniżej szczura, aby zniechęcić do omijania kroków. Bity 95–99 kodują wagę bramkową. Jeśli minimalna waga ścieżki jest poniżej, szczur prawdopodobnie utknął gdzieś i kontynuuje ruch losowo (ale nigdy nie wraca). W przeciwnym razie podąża ścieżką minimalnego ciężaru. Z małym prawdopodobieństwem w zależności od masy zapobiegającej bocznicu, szczur wybiera zamiast tego ścieżkę masy od drugiej do minimalnej. Ma to na celu zapobieganie przywieraniu do ścian (ale wydaje się, że obecnie nie działa zbyt dobrze).
źródło
LookAheadPlayer C ++ ≈ 89,904
Moją pierwotną myślą było poszukiwanie 4 bitów, które pasują do koloru, którego szukałem, i użycie kilku następnych bitów jako wyniku. To był okropny pomysł, prawdopodobnie z powodu mutacji.
Pomyślałem więc o sposobach ochrony przed mutacjami i zwrotnicami, co przypomniało mi o pracy, jaką wykonałem przy dekodowaniu kodu QR. W kodach QR dane są dzielone na bloki i paski, aby uniknąć błędów powodujących zniszczenie zbyt dużej części danej części danych.
Dlatego, podobnie jak ColorScorePlayer, pocięłam DNA na 16 części i wykorzystuję je jako wynik. Jednak wyniki są rozłożone tak, że poszczególne bity każdego wyniku nie są sąsiadujące. Następnie sumuję wynik zarówno aktualnych możliwych ruchów, jak i kolejnych potencjalnych ruchów i wybieram najlepszy ruch do wykonania.
Uwaga: zostało to zakodowane / przetestowane na MinGW. Nie można go skompilować z optymalizacjami ani z wielowątkowością. Nie mam faktycznej instalacji Linuksa ani programu Visual Studio, aby użyć kompilatora, w którym będą działać. Będę testować to szybko jutro rano, ale daj mi znać, jeśli napotkasz jakieś problemy.
źródło
SlowAndSteady C ++ (wynik 9,7)
Nie możemy polegać na interpretacji fragmentów genomu jako liczb, ponieważ pojedyncze odwrócenie bitów może mieć radykalnie różne efekty w zależności od jego pozycji. Dlatego po prostu używam 16 6-bitowych segmentów i oceniam je według liczby
1
s. Początkowo111111
było dobre i000000
złe, i chociaż nie ma to znaczenia na dłuższą metę (po pełnym rozwinięciu genomu) w początkowej konfiguracji DNA większość segmentów ma 2-4, więc przełączyłem się na używanie9 - (#1 - 3)^2
do punktacji, to pozwala na znacznie większą swobodę ruchu w pierwszych rundach i szybszą ewolucję.Teraz patrzę tylko na 7 najbliższych sąsiadów, dodam odchylenie kierunku do wyniku koloru i poruszam się losowo w jednym z najwyższych kierunków.
Chociaż sam wynik nie jest bardzo wysoki, moje stworki osiągają linię mety i zdobywają> 1 w 3/4 przypadków.
I próbka punktacji na 100 tablicach
Średni wynik geometryczny: 9,76557
źródło
WeightChooser | C # | Wyniki: 220,8262 w 1520 grach
Oblicza wagę możliwego następnego ruchu (niebieski) na podstawie średniej masy możliwych następnych ruchów (żółty)
źródło
SZCZURY W AKCJI (nie odpowiedź, ale narzędzie graficzne dla botów C ++)
Od początku tego wyzwania miałem trudności z ustaleniem, co naprawdę stoją szczurom na torze.
W końcu zhakowałem kontroler i napisałem boczne narzędzie, aby uzyskać graficzną reprezentację ścieżki.
W końcu zrobiłem więcej hackowania i dodałem wizualizację możliwych ścieżek DNA danego szczura.
Mapa jest bardzo zagracona i wymaga trochę przyzwyczajenia się, ale zrozumiałem, jak działają moje boty.
Oto przykład:
Prawdopodobnie będziesz musiał powiększyć, aby zobaczyć cokolwiek, więc oto tylko pierwsza połowa:
Najpierw spójrzmy na ścieżki szczura. Istnieje jedna ścieżka dla każdej możliwej lokalizacji początkowej (zwykle 15, czasem nieco mniej). Zwykle łączą się, idealnie prowadząc do pojedynczego miejsca zwycięstwa.
Ścieżki są reprezentowane przez duże proste strzałki. Kolor opisuje wynik:
W tym przykładzie mamy 12 zwycięskich pozycji początkowych, jedną prowadzącą do nieskończonej pętli i dwie do wyczerpującej śmierci (jak się wydaje, teleportowana w pułapkę).
Nieciągłości ścieżki wynikają z teleportacji, którą można śledzić za pomocą odpowiednich zakrzywionych strzałek.
Teraz kolorowe symbole. Reprezentują znaczenie 16 kolorów (szare przedstawiają to, co widzi szczur).
puste kolory są ... no cóż ... puste.
Teleportery mają wychodzące strzałki wskazujące miejsce docelowe.
Detektory pułapek mają również strzałki wskazujące pułapkę, która jest przedstawiona jako czerwone kółko.
W jednym z 9 przypadków pułapka znajduje się w tej samej komórce co jej detektor, w którym to przypadku zobaczysz mały oktogon na czerwonym kółku.
W tym przykładzie jest tak w przypadku jasnożółtej pułapki.
Możesz również zobaczyć fioletowe detektory pułapek skierowane w dół do wskazanej pułapki.
Zauważ, że czasami czerwone koło pułapki będzie ukryte pod ścianą. Oba są śmiertelne, więc wynik jest taki sam w przypadku teleportacji.
Zauważ też, że pułapka może znajdować się na teleporterze, w którym to przypadku teleporter ma pierwszeństwo (tzn. Szczur jest teleportowany przed wpadnięciem w pułapkę, w efekcie neutralizując pułapkę).
Wreszcie, szare symbole reprezentują to, co widzą moje szczury (tj. Znaczenie, jakie ich genom przypisuje kolorom).
Zasadniczo wszystkie komórki siedzące na szarym kwadracie są uważane przez szczura za ściany.
Wielkie X reprezentują komórki uważane za pułapki, a odpowiadające im oktogony wskazują wykrywacz, który je zgłosił.
W tym przykładzie obie ściany są oznaczone jako takie, podobnie jak jasnożółta pułapka (wskazująca rzeczywiście śmiertelną komórkę, więc przedstawienie jej jako ściany jest prawidłowe).
Fioletowy detektor pułapki został zidentyfikowany jako taki (znajduje się na szarym oktogonie), ale lokalizacja pułapki jest niepoprawna (widać, że niektóre czerwone kółka nie mają pod nimi krzyży).
Z 4 teleporterów 2 są uważane za ściany (turkusowe i jasnobrązowe), a 2 jako puste komórki (czerwonawe i żółtawe).
Kilka pustych komórek jest uważanych za detektory pułapek lub ściany. Patrząc uważnie, widać, że te „wadliwe detektory” rzeczywiście zabraniają wejścia do komórek, które wpędzałyby szczura w kłopoty, więc nawet jeśli nie pasują do rzeczywistych kolorów, mają określony cel.
Kod
Cóż, to bałagan, ale działa całkiem dobrze.
Widząc z kodu gracza, dodałem tylko jeden interfejs: funkcję śledzenia używaną do zgłaszania znaczenia danego DNA. W moim przypadku użyłem 3 typów (ściana, wykrywacz pułapek i pusty), ale możesz zasadniczo generować wszystko, co jest związane z kolorem (lub wcale, jeśli nie chcesz grafiki związanej z genomem).
Zhakowałem kontroler, aby wygenerować ogromny ciąg znaków zestawiający opis toru i kolorów z „suchym przebiegiem” DNA szczura ze wszystkich możliwych lokalizacji.
Oznacza to, że wyniki będą naprawdę znaczące tylko wtedy, gdy bot nie użyje losowych wartości. W przeciwnym razie wyświetlane ścieżki będą reprezentować tylko jeden możliwy wynik.
Na koniec wszystkie te ślady są umieszczane w dużym pliku tekstowym, który jest następnie odczytywany przez narzędzie PHP, które generuje dane wyjściowe grafiki.
W bieżącej wersji robię migawkę za każdym razem, gdy szczur umiera po osiągnięciu nowej maksymalnej sprawności (która pokazuje całkiem dobrze progresywne udoskonalanie genomu bez wymagania zbyt wielu migawek), a także ostatnią migawkę na końcu gry (która pokazuje najbardziej udane DNA).
Jeśli ktoś jest zainteresowany, mogę opublikować kod.
Oczywiście działa to tylko dla botów C ++ i będziesz musiał napisać funkcję śledzenia i ewentualnie zmodyfikować kod PHP, jeśli chcesz wyświetlić dane specyficzne dla genomu (szare cyfry w moim przypadku).
Nawet bez informacji specyficznych dla DNA możesz bardzo łatwo zobaczyć ścieżki, którymi podąża twoje DNA na danej mapie.
Dlaczego wynik pośredni?
Przede wszystkim C ++ nie ma przyzwoitej przenośnej biblioteki graficznej, o której można mówić, szczególnie w przypadku MSVC. Nawet jeśli kompilacje Win32 są zwykle dostępne, często przychodzą one na później, a liczba potrzebnych bibliotek zewnętrznych, pakietów i innych potrzebnych uniksów sprawia, że pisanie szybkiej i prostej aplikacji graficznej jest strasznym bólem w części ciała, którego nie pozwala przyzwoitość ja od nazywania.
Rozważyłem użycie Qt (o jedynym środowisku, które sprawia, że przenośne GUI / projektowanie graficzne w C ++ jest prostym i nawet przyjemnym zadaniem, IMHO - prawdopodobnie dlatego, że dodaje system przesyłania wiadomości à la Objective C, którego C ++ bardzo brakuje i robi niesamowitą robotę ograniczania pamięci zarządzanie do najmniejszego minimum), ale wyglądało to na przesadne wykonanie zadania (i każdy, kto chce skorzystać z kodu, musiałby zainstalować duży SDK - chyba nie warte wysiłku).
Nawet przy założeniu przenośnej biblioteki nie ma potrzeby mówić o szybkości (jedna sekunda, aby wygenerować obraz jest w dużej mierze wystarczająca), a dzięki przysłowiowej sztywności i nieodłącznemu bałaganowi C ++ z pewnością nie jest najlepszym narzędziem do tego zadania.
Co więcej, posiadanie pośredniego tekstu wyjściowego zapewnia dużą elastyczność. Gdy już tam są dane, możesz je wykorzystać do innych celów (na przykład analizując wydajność botów).
Dlaczego PHP
Uważam, że język jest niezwykle prosty i elastyczny, bardzo wygodny do tworzenia prototypów. Uczyniłem go moim językiem domowym dla wyzwań kodu, które nie wymagają ekstremalnych osiągów.
Jest to okropny język do gry w golfa, ale golf i tak nigdy nie był moją filiżanką herbaty.
Podejrzewam, że Python lub Ruby byłyby równie przyjemne w użyciu do tego samego celu, ale nigdy nie miałem okazji z nimi zrobić poważnej pracy, a ostatnio pracowałem na stronach internetowych, więc PHP jest.
Nawet jeśli nie znasz języka, modyfikacja kodu w zależności od potrzeb nie powinna być trudna. Tylko nie zapomnij o
$
s przed zmiennymi, tak jak stare dobre podstawowe dni :).źródło
SkyWalker - Python - ocenia mniej niż 231 w 50 grach
Więc najpierw kod, a potem kilka wyjaśnień. Mam nadzieję, że nic się nie zepsuło podczas kopiowania.
Niektóre wyjaśnienia
Moim zdaniem główna różnica polega na tym, że nie koduję każdego koloru. Zamiast tego próbuję zapisać liczbę ważnych kolorów. Moim zdaniem te kolory to pułapki, ściany i teleportery. Próbka nie musi znać koloru dobrej komórki. Dlatego mój genom ma następującą strukturę.
To daje w sumie 52 bitów. Używam jednak tylko pierwszego bitu z 3 decydujących teleporterów (sprawdzam, czy liczba jest większa 3). Dlatego pozostałe 2 mogą zostać usunięte, pozostawiając mi 44 używane bity.
Przy każdej turze sprawdzam każde pole mojej wizji, czy jest to zły kolor (+ poza planszą -1) i dodam go do listy pól, do których okaz nie chce się przenieść. W przypadku pułapki dodaję pole znajdujące się na zapisanym przesunięciu dla tego koloru pułapki.
Na podstawie listy tych złych pól obliczany jest następny ruch. Kolejność preferowanych pól jest następująca:
Jeśli obowiązują dwa pola kategorii, jedno jest wybierane losowo.
Wyniki
Myśli
Nie mam pojęcia, czy mam szczęście z 50 biegami, czy też w mojej strategii jest mądrość.
Moje biegi nigdy nie wydają się startować i osiągać bardzo wysokie wyniki, ale mają też tendencję do znajdowania przynajmniej kilka razy bramki
Niewielka przypadkowość jest dobra, aby nie utknąć w pułapce w pobliżu końca wyścigu
Myślę, że nietypowe kolory nigdy nie są złe. Jednak ich wystąpienia mogą być złe, gdy znajdują się na granicy pułapki. Dlatego też oznaczanie koloru jako zły, jeśli nie jest to pułapka, ściana lub zły teleporter, nie ma sensu.
Ściany są największymi wrogami
Ulepszenia
Po pierwsze, chociaż będę tęsknił za obserwowaniem, jak czarne kwadraty zbliżają się coraz bardziej do celu, konieczny jest port C ++, aby przeprowadzić więcej testów i uzyskać bardziej znaczący wynik.
Jednym z głównych problemów jest to, że jeśli przed szczurem znajdują się złe komórki (lub te, które okazują złe), łatwo poruszają się w kółko w górę iw dół. W takich przypadkach można to zatrzymać lub zmniejszyć, patrząc na 2 ruchy do przodu, i zapobiec przeniesieniu się na pole, na którym po prostu cofnie się.
Często zajmuje dużo czasu, zanim szczur z dobrymi genami osiąga cel i zaczyna rozprzestrzeniać geny. Może potrzebuję strategii, aby zwiększyć różnorodność w tych przypadkach.
Ponieważ teleportery są trudne do obliczenia, może powinienem podzielić populację na tych, którzy są ryzykowni i zawsze biorą dobre teleportery oraz tych, którzy są bardziej zaniepokojeni i biorą je tylko wtedy, gdy nie ma innego wyboru.
Powinienem jakoś wykorzystać drugą połowę mojego genomu.
źródło
self.bit_chunk(16, 4)
iself.bit_chunk(20, 4)
masz zarówno wartość0010
, że skutecznie przechowujesz informacje tylko o jednej z dwóch pułapek.itervalues
navalues
.Python, NeighboursOfNeighbors, wynik = 259,84395 w ponad 100 grach
To jest odmiana w ColorScorePlayer. Co 6 bitów przechowuje wynik jakości dla kwadratu. Gdy bot wykonuje ruch, ocenia każdy z 3 kwadratów do przodu - przekątnej w górę, do przodu i przekątnej w dół. Wynik to jakość kwadratu plus połowa średniej jakości kolejnych 3 kwadratów. To daje botowi pewne spojrzenie w przyszłość, nie przytłaczając jakości pierwszego kwadratu. Algorytm jest podobny do LookAheadPlayer, którego nie widziałem przed napisaniem tego rozwiązania.
źródło
else None
sięelse 0
w stosunku do poprzedniego wiersza, aby obliczyć swój wynik. Mam nadzieję, że nie zmieni to twojej logiki (nie wprowadziłem żadnych zmian w twoim kodzie tutaj na SE poza dodaniem zagubionego wcięcia).ROUS (gryzonie o nietypowym rozmiarze), Java, wynik = 0
To powoduje, że otoczenie decyduje, dokąd pójść.
Ponieważ kontroler Java nie działa, nie mam na to punktów. Zajedzie to bardzo daleko, jeśli znajdzie kilka teleporterów, aby mu pomóc.To ma tendencję do wyginięcia i awarii sterownika raz na jakiś czas. Wynika to prawdopodobnie z faktu, że jego naturalnym środowiskiem jest Bagno Ognia.źródło
Szary kolor Lookahead (C ++, ~ 1,35)
Ten średnio nie radzi sobie zbyt dobrze, ale w rzadkich przypadkach działa znakomicie. Niestety, jesteśmy oceniani na podstawie średniej geometrycznej (1,35), a nie na podstawie maksymalnej oceny (20077).
Algorytm działa po prostu za pomocą 4-bitowych szarych kodów, aby zamapować wynik każdego koloru gdzieś od -2 do 2 (z odchyleniem w kierunku zakresu [-1..1]) i oblicza wynik każdego kafelka każdego ruchu i jego kolejnych ruchów . Używa również 2-bitowego szarego kodu, aby określić mnożnik dla samego kafelka, a także współczynnik przesunięcia w przypadku przejścia w prawo. (Szare kody są znacznie mniej podatne na duże skoki z powodu mutacji, chociaż tak naprawdę nie robią żadnych korzyści dla krzyżowania środkowego punktu kodowego ...)
Nie robi też absolutnie nic, by próbować specjalnie obchodzić się z pułapkami, i podejrzewam, że może to być upadek (chociaż nie dodałem żadnych instrumentów do kontrolera, aby przetestować tę teorię).
Dla każdego możliwego ruchu określa wynik, a spośród wszystkich ruchów o najwyższym wyniku wybiera losowo.
W moim ostatnim biegu uzyskałem wyniki: 1 1 1 1 1 1 1 46 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20077 1 1 1 2 1 1 1 1 1
Chciałbym móc zdobyć więcej z 20077 i mniej z 1. :)
źródło
C ++, TripleScore, wynik: 100 ~ 400
Po pierwsze, mój wynik różni się znacznie w wielu biegach (głównie z powodu liczby 1).
Rdzeń oblicza wynik 5 kierunków: w górę, w dół, do przodu w górę, do przodu i do przodu w dół. Najpierw oblicza się wynik w górę i w dół, a następnie porównuje wyniki z wartością pozostania na miejscu. Jeśli pozostanie na miejscu jest lepsze niż poruszanie się w górę lub w dół, kierunki te nie zostaną wybrane (więc musi iść do przodu). Ma to zapobiec odbijaniu się (w górę, w dół, w górę, w dół, ...) między 2 punktami.
Teraz punktowane są 3 inne kierunki: do przodu, do przodu i do przodu w dół. Ze wszystkich badanych kierunków zachowane są te z najwyższym wynikiem, a 1 z nich wybierany jest losowo.
Punktacja kierunku: TripleScore oblicza wynik ruchu na podstawie 3 wyników cząstkowych:
Podobnie jak w przypadku innych odpowiedzi, wynik zależy w dużej mierze od liczby zwróconych wyników 1.
źródło
Ruby - ProbabilisticScorePlayer
Ten wysoce niedeterministyczny szczur oblicza prawdopodobieństwo przejścia na przestrzeń przez jej sąsiedztwo. Pierwsze 16 miejsc w genomie reprezentuje 16 kolorów. 1 w gnieździe oznacza, że kolor jest dobry na nadepnięcie, 0 oznacza zły. Następne 16 to samo dla pola przed celem i tak dalej.
Główną zaletą podejścia probabilistycznego jest to, że utknięcie za ścianą jest prawie niemożliwe. Wadą jest to, że prawie nigdy nie dostaniesz prawie idealnego szczura.
źródło
c
wartość początkową? Wydaje się, że nie jest zdefiniowany, gdy używasz go w pierwszymif
.coords
nie jest listą, używasz&&
zamiastand
i zapomniałeś nawiasów, a nawet po naprawieniu tego wszystkiego nie ograniczasz wartości RNG, więc otrzymujesz pusty kierunek. Czy ten pseudo-kod, czy coś, co ma być uruchamiane z jakimś dialektem Ruby?Java, RunningStar, wynik = 1817.050970291959 w ponad 1000 gier
Ten bot wykorzystuje kodowanie kolorów Run-Bonus techniką StarPlayer .
Aktualizacja: Naprawiono kontroler Java.
źródło
Skok do przodu, Python 2
Niezbyt przełomowy, ale to moja jedyna próba, która wykonała się dobrze.
Zasadniczo koduje cztery kolory (każdy 4 bity), których należy unikać w genomie. Następnie przechodzi do koloru, którego nie ma na tej liście. Jeśli wszystkie kolory są złe, nadal przeskakuje w nieznane.
źródło
Java - IAmARobotPlayer - Ocena 3,7
Właśnie stworzyłem tego robota-szczura do porównania z innym (jak dotąd niezbyt interesującym) programem, który stworzyłem. Nie osiąga ogólnie dobrych wyników, ale jeśli gdzieś zdobędzie punkty, zdobędzie wiele szczurów. Chodzi o to, że będzie patrzeć tylko na trzy komórki przed sobą, każda komórka jest dobra lub zła. To daje liczbę binarną. Następnie sprawdzi tę liczbę w swoim genomie, weźmie trzy kolejne bity, również skonwertuje je na liczbę i podejmie działanie zapisane pod tym numerem. Więc działa zawsze tak samo, gdy napotyka tę samą sytuację.
Wynik:
źródło
Cautious Specimens - C ++ - ocenia około 2030 na 200 przebiegów
Wykorzystuje część barwną (16 x 4 bity) DNA kodującego Blind Faith, ale pozostawia resztę (36 bitów) DNA całkowicie niewykorzystaną.
Kodowanie koloru to:
Gdzie X oznacza nieużywane bity. Biorąc pod uwagę, że tylko 2 z 16 kolorów to pułapki, które wykorzystają wszystkie 4 ich bity (i tylko jeśli pułapka jest przesunięta, co będzie miało miejsce 8 z 9 razy), wówczas zwykle będzie 64 nieużywanych bitów - teoria jest taka, że mutacje, które wpływają na którykolwiek z tych nieużywanych bitów, nie zrujnują genomu, a stabilność jest lepsza niż jakiekolwiek wymyślne rozwiązania, które mogłyby wykorzystać te pozostałe bity.
Próbki wykorzystują to następnie do zaplanowania bezpiecznej trasy w obrębie siatki 7x7 wyśrodkowanej na sobie (5x5 ich widzenie pozwala plus 1 kwadrat z każdej strony, aby umożliwić przesunięcie pułapek), priorytetem jest przesunięcie największej odległości do przodu po 3 ruchach.
Początkowo zacząłem budować w kilku kontrolach, aby upewnić się, że fakt, że kolor, na którym aktualnie stoi okaz, nie jest śmiertelny, odpowiada genomowi i oznacza wszelkie błędne kolory jako kwadraty BEZPIECZNEGO bezpieczeństwa (i ich sąsiednie kwadraty) - ale to dodało znaczące komplikacja zapewniająca niewielki zysk w porównaniu do oznaczania tych kwadratów jako BEZPIECZNYCH i zabijania kilku dodatkowych okazów. Wrócę do tego, jeśli będę miał czas.
Przykładowe wyniki:
Maksymalny wynik podczas testowania: 8 150 817 zapisanych próbek.
źródło