Easter Egg Hunt

O bot encontra o ovo antes que o coelho encontre o ovo. Bot feliz.

Visão geral

Este é um desafio do tipo rei da colina em homenagem à Páscoa e à tradição de caça aos ovos de Páscoa!

Seu bot tem uma visão de dois espaços em todas as direções, incluindo diagonais, criando um quadrado 5x5 ao seu redor que você pode ver. Está à procura de ovos e quem encontrar mais ovos ganha!

O quadro

O tabuleiro será composto por os, que são ovos de Páscoa, #s, que são paredes, *s, que são outros jogadores e s, que são espaços vazios.

• Será um quadrado com o comprimento da aresta (number of entries) * 3.
• Será cercado por muros.
• Dentro das paredes, haverá uma variedade de paredes de linhas retas, colocadas aleatoriamente #, que terão um comprimento aleatório entre 2 e 10, inclusive. Haverá (number of entries) * 3deles.
• Os ovos serão colocados aleatoriamente. Haverá um (number of entries) * 4deles, e eles serão gerados apenas em quadrados em branco ( ).
• Deve haver pelo menos sete entradas para que o processo de geração da placa funcione corretamente.

Aqui está um JSFiddle que irá gerar um quadro aleatório para você testar. Aqui está um exemplo, com (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#
#                   #
#####################

Depois que o tabuleiro é gerado, cada jogador é colocado em um quadrado aleatório (espaço vazio).

Entrada

Você receberá seis linhas de entrada. As cinco primeiras linhas são o seu campo de visão (os espaços fora dos limites do quadro serão representados por X, e o espaço do meio será sempre *você) e a sexta linha estará vazia (no início).

Resultado

Você produzirá três linhas. Primeiro, a direção que você deseja mover:

1  2  3
8 YOU 4
7  6  5

(9 é um no-op se você não quiser se mover), segundo, um Attack, Cozter ou outro N(isso será explicado em profundidade em breve), e a linha thrid terá qualquer comprimento de até 1024 Esta será a memória do seu bot. Você pode usá-lo para o que quiser ou deixá-lo em branco. Essa memória será a sexta linha de entrada do seu programa na próxima execução.

Todas as outras linhas de saída são ignoradas e, se houver apenas uma linha, a segunda será assumida em branco.

Movendo

O processo a seguir é usado para determinar para onde você se mudou:

• Se, quando você se move, você acaba em um espaço vazio ( ), seu player é colocado nesse espaço.
• Se você parar em uma parede ( #), sua jogada é ignorada e você perde a sua vez.
• Se você acabar em um ovo ( o) ou em um jogador ( *), essas informações serão armazenadas e serão usadas depois que todos tiverem se mudado.

Depois que todos se mudam, as ambiguidades são resolvidas.

Se houver dois jogadores que desembarcaram no mesmo espaço, ocorre uma luta! É aqui que o A/ C/ Nentra para jogar. Atack supera tudo N(ataque normal), tato Nsupera Conça (você não pode contrariar nada), e Conça supera Attack (contra-ataque). O jogador que vence esta luta permanece na praça, e o jogador que perde volta para a praça original em que começou. Em caso de empate, os dois jogadores voltam para onde estavam.

Se um jogador perdedor ou empatado voltar para onde estava e houver outro jogador lá, não haverá luta e o outro jogador também voltará ao seu espaço original. Se este espaço tem um outro jogador, que jogador vai voltar, e isso continua até que todos os jogadores estão em diferentes espaços.

Se houver três ou mais jogadores em um espaço, todos eles voltarão às suas posições originais.

Se algum jogador ainda estiver de pé em um ovo ...

• Se o jogador escolher A, o ovo é destruído.
• Se o jogador escolher C, nada acontecerá e o jogador voltará ao seu espaço original.
• Se o jogador escolheu N, ele pega o ovo! A pontuação do jogador é incrementada em um e o ovo é removido.

línguas

Você pode usar qualquer idioma disponível gratuitamente no Windows, OSX e Linux, para garantir a equidade entre cada participante. Se o código não puder ser executado livremente, mas puder ser compilado ou empacotado em um formato que seja, inclua esse formato na sua resposta também. Idealmente, se você pode compilar seu código em uma linguagem mais comum (por exemplo, CoffeeScript -> JavaScript), faça-o.

Pontuação

Sua pontuação será o número médio de ovos coletados em dez execuções. Uma corrida termina quando todos os ovos são coletados ou quando os (number of entries * 25)turnos passam. Assegurarei manualmente que é possível alcançar todos os ovos para cada mapa (gerando mapas continuamente até que todos os ovos estejam acessíveis).

Placar

Um placar será adicionado quando todas as seguintes condições forem atendidas:

• Pelo menos sete entradas válidas com uma pontuação positiva ou nula (não reduzida) foram enviadas
• Pelo menos 48 horas se passaram desde a criação deste desafio (UTC 14:23)

As regras não serão alteradas durante o período anterior à competição, exceto para esclarecer onde uma regra não é clara. Depois que o placar for colocado, o programa de testes também será publicado aqui para que você possa testar suas entradas. O código de teste para isso ainda está em andamento, mas é reproduzível e funciona. Aqui está o repositório do GitHub.

Cart'o'Gophers

Aqui está outra submissão - e esta realmente pretende ser competitiva. Mais uma vez, está em Ruby. Então corra com ele ruby cartogophers.rb. Isso levou muito mais tempo do que o esperado ...

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}"

Este bot lembra o que viu antes e tenta construir um mapa maior a cada turno. Em seguida, ele usa uma pesquisa abrangente do ovo mais próximo e segue nessa direção. Se não houver um ovo que possa ser alcançado no mapa atual, o bot dirige-se para a borda aberta mais próxima do mapa (para expandir o mapa rapidamente em uma direção em que ele ainda possa se mover).

Este bot ainda não tem conceito de outros bots e também não tem estratégia de combate. Como não encontrei uma maneira confiável de determinar se minha mudança foi bem-sucedida, isso pode causar alguns problemas. Simplesmente sempre presumo que a mudança tenha sido bem-sucedida - por isso, se não fossem novos patches, eles serão carregados no mapa nos lugares errados, o que pode ou não ser prejudicial à busca de caminhos.

O bot usa a memória para armazenar o mapa e sua nova posição no mapa (assumindo que a movimentação será bem-sucedida). O mapa é armazenado sem quebras de linha, compactado e codificado com base64 (junto com o número de linhas do mapa, para que as quebras de linha possam ser reinseridas). Essa compactação reduz o tamanho para cerca de um terço do mapa não compactado; portanto, com uma sombra acima de 1000 bytes, eu poderia armazenar um mapa de cerca de 3000 células, o que corresponde aproximadamente à exploração completa de um mapa com 18 bots. Enquanto não houver um número tão grande de envios, não acho que possa me dar ao trabalho de encontrar uma solução para esse caso.

Depois de alguns testes realizados contra 5 se dumbbot1 naivebot(minha outra submissão), ele teve um desempenho muito ruim (como 1 ou 2 ovos) ou superou os outros por uma margem considerável (7 a 9 ovos). Posso pensar em uma melhor estratégia de luta e como posso determinar se realmente me mudei ou não. Ambos podem melhorar um pouco a pontuação.

Ah, e se você está se perguntando o nome do bot, deve ler The Order of The Stick ( último painel deste quadrinho ).

EDIT: Houve alguns bugs na detecção das bordas do mapa descoberto. Agora que eu os corrigi, esse bot sempre recebe pontuações de 205 contra dumbbot1 naivebot. É mais assim! Se você adicionar $stderr.puts mapao meu bot agora, poderá realmente ver como ele sistematicamente descobre o mapa e coleta todos os ovos enquanto isso. Também decidi escolher, em Avez de Nnão pisar em um ovo, reduzir a probabilidade de voltar à célula original do bot (que em parte estraga o mapa).

(Ele não funciona tão bem contra 6 naivebots, especialmente porque é muito possível acabar em um "impasse" com outro bot quando os dois querem repetidamente pegar um ovo e escolher N. Preciso pensar nisso ... )

Java Bunny

Este coelho ainda não terminou de crescer (ainda pretendo fazer alterações), mas é um ponto de partida por enquanto. Ele procura o ovo mais próximo e vai em sua direção. Ainda não há detecção de parede ou fora dos limites. Ele irá pegar o ovo em que pousar, mas, caso contrário, tentará avançar e atacar qualquer outra coisa. Se não houver ovos próximos, ele começará a seguir o coelho mais próximo. Eles podem saber algo que ele não sabe. Caso contrário, ele apenas escolherá uma direção aleatória para caminhar. E ele é bastante esquecido (sem uso da variável de memória).

Planos para o futuro:

• Tomar decisões com base em muros / fora dos limites
• Escolha caminhos com uma finalidade, em vez de aleatoriamente
• Use a memória para determinar a direção que eu estava indo antes

Atualização 1 Meu coelho seguirá outros coelhos se ele não vir um ovo. Também refatorou o código "encontrar o ovo mais próximo" em seu próprio método.

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 (em Ruby)

Aqui está um bot muito simplista para fazer o ovo rolar (queremos chegar rapidamente a esses 7 envios, certo?). Meu Ruby não é muito idiomático, portanto esse código pode fazer com que os rubiistas adequados se encolham de dor. Leia por sua conta e risco.

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}
"

Corra com ruby naivebot.rb.

Estou simplesmente codificando alguns casos em que um ovo é visível e não é obstruído por uma parede. Nem sequer escolhe o ovo mais próximo, mas escolhe o primeiro movimento que faz sentido. Se nenhum ovo for encontrado, o bot fará um movimento aleatório. Ele desconsidera todos os outros jogadores e nunca ataca ou faz contadores.

WallFolower

(trocadilho deliberado) em Python 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)))

Move para um ovo se houver um ovo à vista, mas apenas se estiver mais próximo desse ovo do que outro robô. Se houver um empate à distância, vale a pena de qualquer maneira. Caso contrário, segue uma parede LH (atualmente não está bem implementada).

Ainda precisa trabalhar na parede, mas eu vou postar aqui de qualquer maneira.