Easter Egg Hunt

Bot znajdź jajko, zanim królik znajdzie jajko. Bot szczęśliwy.

Przegląd

To wyzwanie na szczycie wzgórza na cześć Wielkanocy i tradycji polowania na pisanki!

Twój bot ma wizję dwóch pól w każdym kierunku, w tym przekątnych, tworząc wokół siebie kwadrat 5x5, który możesz zobaczyć. Szuka jajek, a ten, kto znajdzie najwięcej jajek, wygrywa!

Tablica

Plansza będzie się składać z os, które są pisankami, #s, które są ścianami, *s, którzy są innymi graczami, i s, które są pustymi polami.

• Będzie to kwadrat o długości krawędzi (number of entries) * 3.
• Będzie otoczony murami.
• Wewnątrz ścian będzie znajdować się losowo rozmieszczone ściany o linii prostej #, o losowej długości od 2 do 10 włącznie. Będzie (number of entries) * 3ich.
• Jaja zostaną następnie umieszczone losowo. Będą (number of entries) * 4ich i będą generowane tylko na pustych ( ) kwadratach.
• Aby proces generowania płyty działał poprawnie, musi być co najmniej 7 wpisów.

Oto JSFiddle, który wygeneruje losową planszę do przetestowania. Oto przykład z (number of entries) = 7:

#####################
#        o         ##
#    #    o        ##
#    #o    ######  ##
######     #       ##
## o #     #       ##
##  o#   #o#    o o##
##   #o  # # o  #   #
##   # o # #    #   #
##  ##   # #  o #   #
##  #    #  o   # # #
##  # o  #   ## # # #
##  #           # # #
# o #          ## # #
# o oo         ##o  #
#o  ####### oo ##   #
#        #      #   #
#   o o o#          #
#   o ####   o     o#
#                   #
#####################

Po wygenerowaniu planszy każdy gracz kładzie się na losowym polu (puste miejsce).

Wejście

Weźmiesz sześć wierszy danych wejściowych. Pierwsze pięć linii to twoje pole widzenia (spacje poza granicami planszy będą reprezentowane przez X, a środkowa spacja zawsze będzie to *Ty), a szósta linia będzie pusta (na początku).

Wynik

Wyprowadzisz trzy linie. Po pierwsze, kierunek, w którym chcesz się poruszać:

1  2  3
8 YOU 4
7  6  5

(9 to brak Aoperacji, jeśli nie chcesz się ruszać), po drugie, jeden z ttack, Counter lub Nothing (zostanie to wyjaśnione wkrótce), a trzecia linia będzie miała dowolny ciąg długości do 1024 To będzie pamięć twojego bota. Możesz użyć go do wszystkiego, co chcesz, lub pozostawić puste. Pamięć ta będzie następnie szóstym wierszem danych wejściowych do programu przy następnym uruchomieniu.

Wszystkie dalsze wiersze danych wyjściowych są ignorowane, a jeśli jest tylko jeden wiersz, zakłada się, że drugi jest pusty.

W ruchu

Poniższy proces służy do określenia miejsca przeniesienia:

• Jeśli podczas ruchu skończysz na pustym polu ( ), Twój gracz zostanie umieszczony na tym polu.
• Jeśli trafisz na ścianę ( #), twój ruch zostanie zignorowany i stracisz swoją kolej.
• Jeśli trafisz do jajka ( o) lub gracza ( *), informacje te zostaną zapisane i zostaną wykorzystane po przeprowadzce wszystkich osób.

Po tym, jak wszyscy się przeprowadzą, niejasności zostaną rozwiązane.

Jeśli jest dwóch graczy, którzy wylądowali na tym samym polu, następuje walka! W tym miejscu pojawia się A/ C/ N. Attack bije Nothing (normalny atak), Nothing bije Counter (nie można nic Cskontrować ), a ounter bije Attack (kontratak). Gracz, który wygra tę walkę, pozostaje na swoim polu, a gracz, który przegrywa, wraca do pierwotnego pola, na którym zaczął. W przypadku remisu obaj gracze wracają tam, gdzie byli.

Jeśli przegrywający lub remisujący gracz wróci do miejsca, w którym był, i tam jest inny gracz, nie będzie walki, a drugi gracz również powróci na swoje pierwotne pole. Jeśli na tym polu znajduje się inny gracz, ten gracz cofa się i to trwa, dopóki wszyscy gracze nie znajdą się na różnych polach.

Jeśli na jednym polu znajduje się trzech lub więcej graczy, wszyscy wracają do swoich pierwotnych pozycji.

Jeśli jakiś gracz nadal stoi na jajku ...

• Jeśli gracz wybierze A, jajko zostanie zniszczone.
• Jeśli gracz wybrał C, nic się nie dzieje i gracz powraca do pierwotnego miejsca.
• Jeśli gracz wybrał N, gracz podnosi jajko! Wynik gracza jest zwiększany o jeden, a jajko jest usuwane.

Języki

Możesz używać dowolnego języka, który jest swobodnie dostępny w systemach Windows, OSX i Linux, aby zapewnić uczciwość między uczestnikami. Jeśli kodu nie można swobodnie uruchamiać, ale można go skompilować lub spakować w formacie, który jest, proszę również podać ten format w swojej odpowiedzi. Najlepiej, jeśli możesz skompilować kod w bardziej popularnym języku (tj. CoffeeScript -> JavaScript), zrób to.

Punktacja

Twój wynik będzie średnią liczbą zebranych jaj z dziesięciu serii. Bieg kończy się, gdy wszystkie jajka zostaną zebrane lub gdy (number of entries * 25)minie kolej. Ręcznie upewnię się, że możliwe jest dotarcie do wszystkich jaj dla każdej mapy (poprzez ciągłe generowanie map, aż wszystkie jajka będą dostępne).

Tablica wyników

Tablica wyników zostanie dodana, gdy zostaną spełnione wszystkie następujące warunki:

• Zgłoszono co najmniej siedem ważnych zgłoszeń z wynikiem pozytywnym lub zerowym (nie oceniono)
• Od utworzenia tego wyzwania minęło co najmniej 48 godzin (UTC 14:23)

Zasady nie zmienią się w tym okresie przedkonkursowym, z wyjątkiem dodania wyjaśnień w przypadku niejasności reguły. Po utworzeniu tablicy wyników zostanie tutaj opublikowany program testujący, abyś mógł przetestować swoje wpisy. Kod testowy jest wciąż w toku, ale można go odtworzyć i działa. Oto repozytorium GitHub.

Cart'o'Gophers

Oto kolejne zgłoszenie - które w rzeczywistości ma być konkurencyjne. Znów jest w Ruby. Więc uruchom to ruby cartogophers.rb. Trwało to znacznie dłużej niż oczekiwano ...

require 'zlib'
require 'base64'

def encode map, coords
    zipped = Zlib::Deflate.deflate map.join
    encoded = Base64.encode64(zipped).gsub("\n",'')
    "#{coords[:x]}|#{coords[:y]}|#{map.length}|#{encoded}"
end

def decode memory
    memory =~ /^(\d+)[|](\d+)[|](\d+)[|](.*)$/
    coords = {x: $1.to_i, y: $2.to_i}
    n_rows = $3.to_i
    encoded = $4
    decoded = Base64.decode64 encoded
    unzipped = Zlib::Inflate.inflate decoded
    n_cols = unzipped.length / n_rows;
    return unzipped.scan(/.{#{n_cols}}/), coords
end

def update map, fov, coords
    if coords[:x] < 2
        map.map! { |row| '?' << row }
        coords[:x] += 1
    elsif coords[:x] >= map[0].length - 2
        map.map! { |row| row << '?' }
    end

    if coords[:y] < 2
        map.unshift '?' * map[0].length
        coords[:y] += 1
    elsif coords[:y] >= map.length - 2
        map.push '?' * map[0].length
    end

    fov.each_index do |i|
        map[coords[:y]-2+i][coords[:x]-2, 5] = fov[i]
    end

    return map, coords
end

def clean_up map
    map.each do |row|
        row.gsub!('*', ' ')
    end
end

DIRECTIONS = [
    [],
    [-1,-1],
    [ 0,-1],
    [ 1,-1],
    [ 1, 0],
    [ 1, 1],
    [ 0, 1],
    [-1, 1],
    [-1, 0],
    [ 0, 0]
]

def move_to dir, coords
    {
        x: coords[:x] + DIRECTIONS[dir][0],
        y: coords[:y] + DIRECTIONS[dir][1]
    }
end

def get map, coords
    if coords[:x] < 0 || coords[:x] >= map[0].length ||
       coords[:y] < 0 || coords[:y] >= map.length
        return '?'
    end
    map[coords[:y]][coords[:x]]
end

def set map, coords, value
    unless coords[:x] < 0 || coords[:x] >= map[0].length ||
       coords[:y] < 0 || coords[:y] >= map.length
        map[coords[:y]][coords[:x]] = value
    end
    map[coords[:y]][coords[:x]]
end

def scan_surroundings map, coords
    not_checked = [coords]
    checked = []
    cost = { coords => 0 }
    direction = { coords => 9 }
    edges = {}

    while not_checked.length > 0
        current = not_checked.pop

        checked.push current
        (-1..1).each do |i|
            (-1..1).each do |j|
                c = { x: current[:x]+i, y: current[:y]+j }
                unless not_checked.include?(c) || checked.include?(c)
                    if get(map, c) == '#'
                        checked.push c
                    elsif get(map, c) == '?'
                        checked.push c
                        edges[current] = { cost: cost[current], move: direction[current] }
                    else
                        not_checked.unshift c

                        cost[c] = cost[current] + 1
                        if direction[current] == 9 # assign initial direction
                            direction[c] = DIRECTIONS.find_index([i,j])
                        else
                            direction[c] = direction[current]
                        end

                        if get(map, c) == 'o'
                            return direction[c], if cost[c] == 1 then 'N' else 'A' end
                        end

                        edges[c] = { cost: cost[c], move: direction[c] } if c[:x] == 0 || c[:x] == map[0].length - 1 ||
                                                                            c[:y] == 0 || c[:y] == map.length - 1
                    end
                end
            end
        end
    end

    # If no egg has been found return the move to the closest edge
    nearest_edge = edges.keys.sort_by { |c| edges[c][:cost] }.first
    if edges.length > 0
        return edges[nearest_edge][:move], 'A'
    else
        # The entire map has been scanned and no more eggs are left.
        # Wait for the game to end.
        return 9, 'N'
    end
end

input = $<.read.split "\n"
fov = input[0..4]
memory = input[5]

if memory
    map, coords = decode memory
    map, coords = update(map, fov, coords)
else
    map = fov
    coords = {x: 2, y: 2}
end
clean_up map

move, attack = scan_surroundings(map, coords)

memory = encode map, move_to(move, coords)

puts "#{move}
#{attack}
#{memory}"

Ten robot pamięta to, co widział wcześniej i za każdym razem próbuje zbudować większą mapę. Następnie używa pierwszego wyszukiwania najbliższego jajka i głów w ten sposób. Jeśli na bieżącej mapie nie ma jajka, bot skieruje się do najbliższej otwartej krawędzi mapy (aby szybko rozwinąć mapę w kierunku, w którym nadal może się poruszać).

Ten bot nie ma jeszcze pojęcia o innych botach i strategii walki. Ponieważ nie znalazłem wiarygodnego sposobu na sprawdzenie, czy mój ruch się powiódł, może to powodować pewne problemy. Po prostu zawsze zakładam, że ruch się powiódł - więc jeśli nie było, nowe łaty zostaną załadowane na mapę w niewłaściwych miejscach, co może, ale nie musi być szkodliwe dla poszukiwania ścieżki.

Bot używa pamięci do przechowywania mapy i jej nowej pozycji na mapie (zakładając, że ruch się powiedzie). Mapa jest przechowywana bez podziałów linii, skompresowana i zakodowana w standardzie base64 (wraz z liczbą wierszy mapy, dzięki czemu można ponownie wstawiać podziały linii). Ta kompresja obniża rozmiar do około jednej trzeciej nieskompresowanej mapy, więc mając cień ponad 1000 bajtów, mógłbym przechowywać mapę około 3000 komórek, co z grubsza odpowiada w pełni eksploracji mapy z 18 botami. Tak długo, jak niewiele jest takich zgłoszeń, nie sądzę, żebym miał problem z ustaleniem rozwiązania tej sprawy.

Po kilku testach w stosunku do 5 dumbbots i 1 naivebot(moje inne poddanie), albo wypadło naprawdę źle (jak 1 lub 2 jajka), albo przewyższyło pozostałe o znaczny margines (7 do 9 jaj). Mogę pomyśleć o lepszej strategii walki i o tym, jak ustalić, czy rzeczywiście się przeprowadziłem, czy nie. Oba mogą nieco poprawić wynik.

Aha, a jeśli zastanawiasz się nad nazwą bota, powinieneś przeczytać The Order of The Stick ( ostatni panel tego komiksu ).

EDYCJA: Było kilka błędów w wykrywaniu krawędzi odkrytej mapy. Teraz, kiedy je naprawiłem, ten bot zawsze otrzymuje wyniki około 205 dumbbots i 1 naivebot. Tak już lepiej! Jeśli teraz dodasz $stderr.puts mapdo mojego bota, naprawdę możesz zobaczyć, jak systematycznie odkrywa mapę i tymczasem zbiera wszystkie jajka. Postanowiłem także wybrać AzamiastN nie wchodzić na jajko, aby zmniejszyć prawdopodobieństwo powrotu do oryginalnej komórki bota (co częściowo psuje mapę).

(Nie radzi sobie tak dobrze w porównaniu z 6 naivebots, zwłaszcza, że ​​bardzo możliwe jest, aby skończyć w „impasie” z innym botem, gdy obaj wielokrotnie chcą chwycić jajko i wybrać N. Muszę o tym pomyśleć ... )

Zajączek Java

Królik jeszcze nie skończył dorastać (wciąż planuję wprowadzić zmiany), ale na razie jest to punkt wyjścia. Szuka najbliższego jajka i podchodzi do niego. Nie ma jeszcze wykrywania ścian ani wykrycia poza granicami. Pójdzie po jajko, na które wyląduje, ale w przeciwnym razie spróbuje przepchnąć się i zaatakować cokolwiek innego. Jeśli w pobliżu nie będzie jaj, zacznie podążać za najbliższym króliczkiem. Mogą wiedzieć coś, czego on nie wie. W przeciwnym razie wybierze losowy kierunek. I jest całkiem zapominalski (bez użycia zmiennej pamięci).

Plany na przyszłość:

• Podejmuj decyzje na podstawie ścian / poza granicami
• Wybierz ścieżki z przeznaczeniem, a nie losowo
• Użyj pamięci, aby określić kierunek, w którym podążałem wcześniej

Aktualizacja 1 Mój króliczek będzie podążał za innymi króliczkami, jeśli nie zobaczy jajka. Zmieniono także kod „znajdź najbliższe jajko” na jego własną metodę.

import java.util.*;

public class EasterEggHunt {

    // board chars
    public static final char EGG = 'o';
    public static final char WALL = '#';
    public static final char BUNNY = '*';
    public static final char SPACE = ' ';
    public static final char OUT_OF_BOUNDS = 'X';

    // player moves
    public static final char ATTACK = 'A';
    public static final char COUNTER = 'C';
    public static final char NOTHING = 'N';

    // directions
    public static final int UPPER_LEFT = 1;
    public static final int UP = 2;
    public static final int UPPER_RIGHT = 3;
    public static final int RIGHT = 4;
    public static final int LOWER_RIGHT = 5;
    public static final int DOWN = 6;
    public static final int LOWER_LEFT = 7;
    public static final int LEFT = 8;
    public static final int STAY = 9;


    // the size of the immediate area
    // (I'll be at the center)
    public static final int VISION_RANGE = 5;

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        char[][] immediateArea = new char[VISION_RANGE][VISION_RANGE];

        for (int i = 0; i < VISION_RANGE; ++i) {
            String line = input.nextLine();
            for (int j = 0; j < VISION_RANGE; ++j) {
                immediateArea[i][j] = line.charAt(j);
            }
        }

        String memory = input.nextLine();

        int moveDirection = decideMoveDirection(immediateArea, memory);
        System.out.println(moveDirection);

        char action = decideAction(immediateArea, memory, moveDirection);
        System.out.println(action);

        // change the memory?
        System.out.println(memory);

    }

    private static int decideMoveDirection(char[][] immediateArea, String memory) {

        // if there's a nearby egg, go towards it
        int direction = nearestBoardObject(immediateArea, EGG);

        // if we didn't find an egg, look for a bunny
        // (maybe he knows where to find eggs)
        if (direction == STAY)
            direction = nearestBoardObject(immediateArea, BUNNY);

        // otherwise, pick a random direction and go
        // we want to also have the chance to stop and catch our breath
        if (direction == STAY)
            direction = new Random().nextInt(STAY + 1);

        return direction;
    }

    private static int nearestBoardObject(char[][] immediateArea, char boardObject) {

        // start at the center and go outward (pick a closer target over a farther one)
        int spacesAway = 1;
        int meX = immediateArea.length / 2;
        int meY = immediateArea[meX].length / 2;

        while (spacesAway <= immediateArea.length / 2) {

            // I like to look right, and go clockwise
            if (immediateArea[meX][meY + spacesAway] == boardObject)
                return RIGHT;
            if (immediateArea[meX + spacesAway][meY + spacesAway] == boardObject)
                return LOWER_RIGHT;
            if (immediateArea[meX + spacesAway][meY] == boardObject)
                return DOWN;
            if (immediateArea[meX + spacesAway][meY - spacesAway] == boardObject)
                return LOWER_LEFT;
            if (immediateArea[meX][meY - spacesAway] == boardObject)
                return LEFT;
            if (immediateArea[meX - spacesAway][meY - spacesAway] == boardObject)
                return UPPER_LEFT;
            if (immediateArea[meX - spacesAway][meY] == boardObject)
                return UP;
            if (immediateArea[meX - spacesAway][meY + spacesAway] == boardObject)
                return UPPER_RIGHT;

            ++spacesAway;
        }

        // if the target object isn't in the immediate area, stay put
        return STAY;

    }

    private static char decideAction(char[][] immediateArea, String memory, int moveDirection) {

        char destinationObject = getDestinationObject(immediateArea, moveDirection);

        switch (destinationObject) {

            case EGG:
                // don't break the egg
                return NOTHING;
            default:
                // get really aggressive on everything else
                // other players, walls, doesn't matter
                return ATTACK;

        }

    }

    private static char getDestinationObject(char[][] immediateArea, int moveDirection) {

        // start at my spot (middle of the board) and figure out which direction I'm going
        int targetX = immediateArea.length / 2;
        int targetY = immediateArea[targetX].length / 2;

        switch (moveDirection) {

            case RIGHT:
                ++targetY;
                break;
            case LOWER_RIGHT:
                ++targetX;
                ++targetY;
                break;
            case DOWN:
                ++targetX;
                break;
            case LOWER_LEFT:
                ++targetX;
                --targetY;
                break;
            case LEFT:
                --targetY;
                break;
            case UPPER_LEFT:
                --targetX;
                --targetY;
                break;
            case UP:
                --targetX;
                break;
            case UPPER_RIGHT:
                --targetX;
                ++targetY;
                break;
            // otherwise we aren't moving

        }

        return immediateArea[targetX][targetY];

    }

}

NaiveBot (w Ruby)

Oto bardzo uproszczony bot, który zmusza do zrzucenia jaja (chcemy szybko uzyskać 7 zgłoszeń, prawda?). Mój Ruby nie jest bardzo idiomatyczny, więc ten kod może sprawić, że właściwi rubiści zaczną drżeć z bólu. Czytaj na własne ryzyko.

input = $<.read
$data = input.split("\n")

def is_egg x, y
    $data[y+2][x+2] == 'o'
end

def is_wall x, y
    $data[y+2][x+2] == '#'
end

def is_empty x, y
    $data[y+2][x+2] == ' '
end

def is_player x, y
    $data[y+2][x+2] == '*'
end

if (is_egg(-2,-2) || is_egg(-2,-1) || is_egg(-1,-2)) && !is_wall(-1,-1) || is_egg(-1,-1)
    dir = 1
elsif is_egg(0,-2) && !is_wall(0,-1) || is_egg(0,-1)
    dir = 2
elsif (is_egg(2,-2) || is_egg(2,-1) || is_egg(1,-2)) && !is_wall(1,-1) || is_egg(1,-1)
    dir = 3
elsif is_egg(2,0) && !is_wall(1,0) || is_egg(1,0)
    dir = 4
elsif (is_egg(2,2) || is_egg(2,1) || is_egg(1,2)) && !is_wall(1,1) || is_egg(1,1)
    dir = 5
elsif is_egg(0,2) && !is_wall(0,1) || is_egg(0,1)
    dir = 6
elsif (is_egg(-2,2) || is_egg(-2,1) || is_egg(-1,2)) && !is_wall(-1,1) || is_egg(-1,1)
    dir = 7
elsif is_egg(-2,0) && !is_wall(-1,0) || is_egg(-1,0)
    dir = 8
else
    dir = rand(8) + 1
end

attack = 'N'
puts "#{dir}
#{attack}
"

Uruchom z ruby naivebot.rb.

Po prostu zapisuję kilka przypadków, w których jajko jest widoczne i nie jest zasłonięte przez ścianę. Nie chodzi nawet o najbliższe jajko, ale wybiera pierwszy ruch, który ma sens. Jeśli nie zostanie znalezione takie jajko, bot wykona losowy ruch. Pomija wszystkich innych graczy i nigdy nie atakuje ani nie kontratakuje.

WallFolower

(celowa gra słów) w Pythonie 3 :

import sys
import random

#functions I will use
dist       = lambda p1,p2: max(abs(p2[1] - p1[1]), abs(p2[0] - p1[0]))
distTo     = lambda p    : dist((2,2), p)
cmp        = lambda x,y  : (x > y) - (x < y)
sgn        = lambda x    : (-1,0,1)[(x>0)+(x>=0)]
move       = lambda p    : (sgn(p[0] - 2), sgn(p[1] - 2))
unmove     = lambda p    : (p[0] * 2 + 2, p[1] * 2 + 2)
outputmove = lambda p    : (1,2,3,8,9,4,7,6,5)[(sgn(p[0] - 2) + 1) + 3*(sgn(p[1]-2) + 1)]
def noeggfinish(move):
    print(outputmove(unmove(move)))
    print('ACN'[random.randint(0, 2)])
    print("1"+move)
    sys.exit(0)

#beginning of main body
view    = [list(l) for l in map(input, ('',)*5)] #5 line input, all at once.
memory  = input() #currently used only as last direction moved in a tuple
eggs    = []
enemies = []
for y in range(5):
    for x in range(5):
        if   view[y][x] == 'o': eggs    += [(x,y)]
        elif view[y][x] == '*': enemies += [(x,y)]

eggs.sort(key = lambda p:distTo(p)) #sort by how close to me they are.

tiedeggs = []
end = 0
for egg in eggs[:]:
    if end:break
    for enemy in enemies:
        exec({
            -1: 'eggs.remove(egg)',
             0: 'tiedeggs += egg',
             1: 'end=1'
        }[cmp(dist(enemy, egg), distTo(egg))])
        if end:break
if eggs:
    print(outputmove(eggs[0]))
    print('N')              #no attack here
    print("0"+move(eggs[0]))
    sys.exit(0)
elif tiedeggs:
    print(outputmove(tiedeggs[0]))
    print('N')              #no attack here
    print("0"+move(tiedeggs[0]))
    sys.exit(0) 
#now there are no eggs worth going for
#do a LH wall follow

lastmove = eval(memory[1:]) #used to resolve ambiguity
if lastmove[0] and lastmove[1]:
    lastmove[random.randint(0,1)] = 0 #disregard diagonal moves
if eval(memory[0]):
    exec("check=view[%n][%n]"%{(0,-1):(0,0),(1,0):(4,0),(0,1):(4,4),(-1,0):(0,4)}[lastmove])
    if check == '#':
        noeggfinish(lastmove)
    else:pass
#currently unimplemented
#move randomly
noeggfinish(tuple([(x,y) for x in [-1,0,1] for y in [-1,0,1] if (x,y) != (0,0)))

Przechodzi do jajka, jeśli w zasięgu wzroku jest jajko, ale tylko wtedy, gdy jest ono bliżej tego jajka niż inny robot. Jeśli jest remis w oddali, i tak to pasuje. W przeciwnym razie podąża ściana LH (obecnie niezbyt dobrze wdrożona).

Nadal potrzebuje pracy na ścianie, ale i tak to opublikuję.