Asymetryczny KOTH: Catch the Cat
AKTUALIZACJA : Pliki gist są aktualizowane (w tym nowe zgłoszenia), ponieważ plik Controller.java nie wychwytuje wyjątków (tylko błędy). Przechwytuje teraz błędy i wyjątki, a także je drukuje.
To wyzwanie składa się z dwóch wątków, to jest wątek kota, wątek łapacza można znaleźć tutaj .
Kontroler można pobrać tutaj .
Jest to asymetryczna KOTH: Każde zgłoszenie dotyczy kota lub łapacza . Istnieją gry między każdą parą każdego kota i łapacza. Koty i łapacze mają osobne rankingi.
Łapacz
Na sześciokątnej siatce jest kot. Twoim zadaniem jest złapanie go tak szybko, jak to możliwe. W każdej turze możesz postawić wiadro z wodą na jednej komórce siatki, aby kot nie mógł się tam dostać. Ale kot nie jest (może) głupi i za każdym razem, gdy umieścisz wiadro, kot przeniesie się do innej komórki siatki. Ponieważ siatka jest sześciokątna, kot może iść w 6 różnych kierunkach. Twoim celem jest otoczenie kota wiadrami z wodą, im szybciej, tym lepiej.
Kot
Wiesz, że łapacz chce cię złapać, umieszczając wokół ciebie wiadra z wodą. Oczywiście próbujesz uniknąć, ale ponieważ jesteś leniwym kotem (tak jak koty), robisz dokładnie jeden krok naraz. Oznacza to, że nie możesz pozostać w tym samym miejscu, co ty, ale musisz przenieść się do jednego z sześciu okolicznych miejsc. Ilekroć zobaczysz, że łapacz umieścił nowe wiadro z wodą, idziesz do innej celi. Oczywiście starasz się unikać tak długo, jak to możliwe.
Krata
Siatka jest sześciokątna, ale ponieważ nie mamy heksagonalnych struktur danych, bierzemy 11 x 11
kwadratową tablicę 2d i naśladujemy sześciokątne „zachowanie”, które kot może poruszać się tylko w 6 kierunkach:
Topologia jest toroidalna, co oznacza, że jeśli wejdziesz na komórkę „na zewnątrz” tablicy, zostaniesz po prostu przeniesiony do odpowiedniej komórki po drugiej stronie tablicy.
Gra
Kot zaczyna od określonej pozycji na siatce. Łapacz może wykonać pierwszy ruch, następnie kot i jego łapacz wykonują naprzemienne ruchy, dopóki kot nie zostanie złapany. Liczba kroków to wynik tej gry. Kot stara się uzyskać jak najlepszy wynik, łapacz stara się uzyskać jak najniższy wynik. Średnia suma wszystkich gier, w których uczestniczyłeś, będzie wynikiem twojego zgłoszenia. Istnieją dwa osobne rankingi, jeden dla kota, drugi dla łapaczy.
Kontroler
Dany kontroler jest napisany w Javie. Jako catcher lub cat każdy z was musi w pełni zaimplementować klasę Java (są już pewne prymitywne przykłady) i umieścić ją w players
pakiecie (i zaktualizować listę kotów / catchers w klasie Controller), ale można także napisać dodatkowe funkcje w tej klasie. Do kontrolera dołączone są dwa robocze przykłady prostych klas cat / catcher.
Pole to tablica 11 x 11
2D int
przechowująca wartości bieżących stanów komórek. Jeśli komórka jest pusta, ma wartość 0
, jeśli jest kot, ma wartość, -1
a jeśli jest wiadro, to jest 1
.
Istnieje kilka podanych funkcji, których możesz użyć: isValidMove()
/ isValidPosition()
służą do sprawdzania, czy twój ruch (kot) / pozycja (łapacz) jest prawidłowy.
Za każdym razem, gdy jest twoja kolej, twoja funkcja takeTurn()
jest wywoływana. Argument zawiera kopię bieżącej siatki i ma metody takie jak read(i,j)
czytanie komórki w (i,j)
, a także isValidMove()/ isValidPosition()
sprawdza poprawność odpowiedzi. To również zarządza zawijaniem toroidalnej topologii, co oznacza, że nawet jeśli siatka ma tylko 11 x 11, nadal możesz uzyskać dostęp do komórki (-5,13).
Metoda powinna zwrócić int
tablicę dwóch elementów, które reprezentują możliwe ruchy. Dla kotów {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}
reprezentują one względną pozycję, w której kot chce iść, a łapacze zwracają bezwzględne współrzędne miejsca, w którym chcą umieścić wiadro {i,j}
.
Jeśli Twoja metoda spowoduje nieprawidłowy ruch, zgłoszenie zostanie zdyskwalifikowane. Ruch uważa się za nieważny, jeśli w miejscu docelowym znajduje się już wiadro lub ruch jest niedozwolony / miejsce docelowe jest już zajęte (jako kot) lub jeśli jest już wiadro / kot (jako łapacz). Możesz to wcześniej sprawdzić za pomocą podanych funkcji.
Twoje zgłoszenie powinno działać dość szybko. Jeśli twoja metoda trwa dłużej niż 200 ms dla każdego kroku, zostanie również zdyskwalifikowana. (Najlepiej znacznie mniej ...)
Programy mogą przechowywać informacje między krokami.
Zgłoszenia
- Możesz przesłać dowolną liczbę zgłoszeń.
- Nie zmieniaj znacząco przesłanych już zgłoszeń.
- Proszę o każde zgłoszenie w nowej odpowiedzi.
- Każde zgłoszenie powinno mieć swoją unikalną nazwę.
- Zgłoszenie powinno składać się z kodu twojej klasy oraz opisu, który mówi nam, jak działa zgłoszenie.
- Możesz napisać wiersz
<!-- language: lang-java -->
przed kodem źródłowym, aby uzyskać automatyczne podświetlanie składni.
Punktacja
Wszystkie koty będą rywalizować ze wszystkimi łapaczami tyle samo razy. Spróbuję często aktualizować bieżące wyniki, zwycięzcy zostaną wyłonieni, gdy aktywność spadnie.
To wyzwanie jest inspirowane starą grą flash
Dzięki @PhiNotPi za testowanie i udzielenie konstruktywnej opinii.
Aktualne wyniki (100 gier na parę)
Name Score Rank Author
RandCatcher 191962 8 flawr
StupidFill 212688 9 flawr
Achilles 77214 6 The E
Agamemnon 74896 5 The E
CloseCatcher 54776 4 randomra
ForwordCatcher 93814 7 MegaTom
Dijkstra 47558 2 TheNumberOne
HexCatcher 48644 3 randomra
ChoiceCatcher 43834 1 randomra
RandCat 77490 9 flawr
StupidRightCat 81566 6 flawr
SpiralCat 93384 5 CoolGuy
StraightCat 80930 7 CoolGuy
FreeCat 106294 3 randomra
RabidCat 78616 8 cain
Dijkstra's Cat 115094 1 TheNumberOne
MaxCat 98400 4 Manu
ChoiceCat 113612 2 randomra
main.Controller
, dzwonieniegetCatchers()
i symulowanie / sabotowanie odpowiedzi łapaczy za pomocą ichtakeTurn
metod?Odpowiedzi:
FreeCat
Wybiera ruch, który zapewniłby mu możliwie najwięcej ścieżek po 3 krokach, gdyby pole nie uległo zmianie.
FreeCat vs Achilles:
źródło
Kot Dijkstry
Nauczył się i stosuje główny algorytm swojego mistrza. Zauważ, że jest on zależny od niektórych metod w swojej odpowiedniej klasie łapacza.
Dijkstra's Cat vs Hexcatcher (wymaga aktualizacji):
Jak on działa:
Próbuje znaleźć ruch, który minimalizuje rygorystyczność planszy w stosunku do siebie. Aby uzyskać więcej informacji, zobacz odpowiedni post łapacza.
Z aktualizacją:
Teraz unika dziwnych geometrycznych kształtów, które czasami tworzą wiadra z wodą.
źródło
MaxCat
Próbowałem zaimplementować algorytm Minimax. Jednak nie działa bardzo dobrze z powodu ograniczonego czasu. Edycja: Teraz używa wielowątkowości, ale (przynajmniej na moim komputerze) nie mogę ustawić głębi. W przeciwnym razie nastąpi przekroczenie limitu czasu. Przy użyciu komputera z 6 lub więcej rdzeniami przesyłanie byłoby znacznie lepsze :)
MaxCat vs Dijkstra:
źródło
Field
publiczny. Przykro mi, że nie zaktualizowałem jeszcze plików, ale omówiliśmy to wcześniej!SpiralCat
Porusza się spiralnie. To
SpiralCat vs Agamemnon:
źródło
turns[i]
sięturns[i%6]
w celu uniknięcia poza granicami (co nie powinno mieć miejsca w tym stuation).turns[i%6]
? NietakeTurn
zadzwonię, jeśli kot zostanie zablokowany, prawda?i>=6
nigdy nie powinno się zdarzyć.RabidCat
RabidCat ma hydrofobię, więc boi się wiader z wodą. Znajduje najbliższy i biegnie w przeciwnym kierunku.
RabidCat vs ForwordCatcher:
źródło
ChoiceCat
Dla każdej możliwej nowej pozycji kota sprawdzamy jego dobroć i wybieramy najlepszą. Dobroć jest funkcją dwóch najlepszych sąsiadujących komórek, które są dalej od pozycji kota niż pozycja, której wynik obliczamy. Używamy tylko dwóch komórek, ponieważ jedną można zablokować, a kot potrzebuje tylko jednej, aby uciec. Nasza funkcja preferuje dwie dość dobre komórki niż jedną wielką i jedną złą. Pozycje z segmentami mają wynik 0, a najdalsze wolne komórki mają wynik 1.
ChoiceCat wydaje się osiągać lepsze wyniki niż obecne koty.
ChoiceCat vs ChoiceCatcher:
źródło
StupidRightCat
Zostało to wykonane tylko do testowania kontrolera. Kot porusza się w prawo, gdy tylko jest to możliwe, w przeciwnym razie porusza się w losowym kierunku.
źródło
RandCat
Zostało to wykonane tylko do testowania kontrolera. Kot po prostu porusza się losowo.
źródło
StraightCat
Ten kot porusza się prosto.
Na początku wybiera losowy kierunek i porusza się w tym kierunku, dopóki nie może, w takim przypadku przesuwa kierunek zgodnie z ruchem wskazówek zegara do następnego prawidłowego kierunku i powtarza ten proces.
StraightCat vs Agamemnon:
źródło