The Easter Egg Hunt on the Hill

Question

Easter Egg Hunt

Bot find egg before bunny find egg. Bot happy.

Overview

This is a king-of-the-hill challenge in honor of Easter and the Easter egg hunting tradition!

Your bot has a vision of two spaces in every direction, including diagonals, creating a 5x5 square around you that you can see. It is looking for eggs, and whoever finds the most eggs wins!

The Board

The board will consist of os, which are Easter eggs, #s, which are walls, *s, which are other players, and s, which are empty spaces.

• It will be a square with edge length (number of entries) * 3.
• It will be surrounded by walls.
• Inside of the walls will be an assortment of randomly placed, straight line walls of #, which will have a random length between 2 and 10 inclusive. There will be (number of entries) * 3 of them.
• The eggs will then be placed randomly. There will be (number of entries) * 4 of them, and they will only be generated on blank () squares.
• There must be at least 7 entires for the board generating process to work properly.

Here is a JSFiddle that will generate a random board for you to test with. Here's an example, with (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#
#                   #
#####################

After the board is generated, each player is placed on a random square (empty space).

Input

You will take six lines of input. The first five lines are your field of vision (spaces out of bounds of the board will be represented by X, and the middle space will always be *, you), and the sixth line will be empty (at first).

Output

You will output three lines. First, the direction that you want to move in:

1  2  3
8 YOU 4
7  6  5

(9 is a no-op if you don't want to move), second, one of Attack, Counter, or Nothing (this will be explained in depth soon), and the thrid line will be any string of length up to 1024. This will be your bot's memory. You may use it for whatever you would like, or you may leave it blank. This memory will then be the sixth line of input to your program on the next run.

All further lines of output are ignored, and if there is only one line, the second is assumed to be blank.

Moving

The following process is used to determine where you moved:

• If, when you move, you end up in an empty space (), your player is placed into that space.
• If you end up in a wall (#), your move is ignored and you lose your turn.
• If you end up in an egg (o) or on a player (*), this information is stored and will be used after everybody has moved.

After everybody has moved, ambiguities are resolved.

If there are two players that have landed on the same space, a fight occurs! This is where the A/C/N comes in to play. Attack beats Nothing (normal attack), Nothing beats Counter (you can't counter nothing), and Counter beats Attack (counterattack). The player who wins this fight stays on their square, and the player who loses goes back to the original square that they started on. In the event of a tie, both players go back to where they were.

If a losing or tied player goes back to where they were and there is another player there, there is no fight and the other player will also revert to its original space. If this space has another player, that player goes back, and this continues until all players are in different spaces.

If there are three or more players on one space, they all revert back to their original positions.

If any player is still standing on an egg...

• If the player chose A, the egg is destroyed.
• If the player chose C, nothing happens and the player reverts to its original space.
• If the player chose N, the player picks up the egg! The player's score is incremented by one and the egg is removed.

Languages

You may use any language that is freely available on Windows, OSX, and Linux, to ensure fairness among each contestant. If the code is not freely runnable but can be compiled or packaged into a format that is, please include this format in your answer as well. Ideally, if you can compile your code into a more common language (i.e. CoffeeScript -> JavaScript), please do so.

Scoring

Your score will be the average number of eggs you collect out of ten runs. A run ends when all eggs are collected or when (number of entries * 25) turns have passed. I will manually make sure that it is possible to reach all eggs for each map (by continually generating maps until all eggs are reachable).

Scoreboard

A scoreboard will be added when all of the following conditions are met:

• At least seven valid entries with a positive or zero score (not downvoted) have been submitted
• At least 48 hours has passed since the creation of this challenge (UTC 14:23)

The rules will not change during this pre-contest period, except to add clarification where a rule was unclear. Once the scoreboard is put up, the testing program will also be posted here so that you can test your entries. The testing code for this is still work-in-progress, but it's playable and it works. Here's the GitHub repo.

Answer 1

Cart'o'Gophers

Here is another submission - and this one is actually meant to be competitive. Again, it's in Ruby. So run it with ruby cartogophers.rb. This took a lot longer than expected...

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

This bot remembers what it has seen before and tries to construct a larger map at each turn. It then uses a breadth-first search for the nearest egg and heads that way. If there is no egg that can be reached on the current map, the bot heads for the nearest open edge of its map (so as to expand the map quickly in a direction it can still move).

This bot has no concept of other bots yet and no fighting strategy either. Since I haven't found a reliable way to determine if my move has been successful, this can cause some problems. I simply always assume that the move has been successful - so if it wasn't new patches will be loaded into the map in the wrong places, which may or may not be harmful to pathfinding.

The bot uses the memory to store the map and its new position on the map (assuming the move will be successful). The map is stored without line breaks, zipped and base64 encoded (along with the number of rows of the map, so that the line breaks can be reinserted). This compression brings the size down to about a third of the uncompressed map, so having a shade over 1000 bytes, I could store a map of about 3000 cells, which roughly corresponds to fully exploring a map with 18 bots. As long as there are nowhere near that many submissions, I don't think I can be bothered to figure out a fix for that case.

After a few test runs against 5 dumbbots and 1 naivebot (my other submission), it either performed really badly (like 1 or 2 eggs) or outperformed the others by a considerable margin (7 to 9 eggs). I may think about a better fighting strategy and how I can determine if I actually moved or not. Both might be able to improve the score somewhat.

Oh and if you're wondering about the name of the bot, you should read The Order of The Stick (last panel on this comic).

EDIT: There were a few bugs with detecting the edges of the discovered map. Now that I've fixed them this bot always gets scores of about 20 against 5 dumbbots and 1 naivebot. That's more like it! If you add $stderr.puts map to my bot now, you can really see how he systematically uncovers the map and collects all eggs in the meantime. I've also decided to choose A instead of N whenever not stepping onto an egg, to reduce the probability of moving back to the bot's original cell (which partly screws up the map).

(It doesn't perform quite as well against 6 naivebots, especially since it's very possible to end up in a "deadlock" with another bot when they both repeatedly want to grab an egg and choose N. I need to think about that...)

Answer 2

Java Bunny

This bunny hasn't finished growing up yet (I still plan to make changes), but it's a starting point for right now. He looks for the closest egg and goes towards it. There isn't wall detection or out-of-bounds detection (yet). He'll go to pick up the egg he lands on, but otherwise he'll try to push he way around and attack anything else. If there are no nearby eggs, he'll start following the nearest bunny. They might know something that he doesn't. Otherwise, he'll just pick a random direction to walk. And he's pretty forgetful (no use of the memory variable).

Plans moving forward:

• Make decisions based on walls/out-of-bounds
• Pick paths with a purpose, rather than randomly
• Use the memory to determine the direction I was going before

Update 1 My bunny will follow other bunnies if he doesn't see an egg. Also refactored the "find nearest egg" code into it's own method.

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];

    }

}

Answer 3

NaiveBot (in Ruby)

Here is a very simplistic bot to get the egg rolling (we want to hit those 7 submissions quick, right?). My Ruby isn't very idiomatic so this code may make proper rubyists cringe in pain. Read at your own risk.

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

Run with ruby naivebot.rb.

I'm simply hardcoding a few cases, where an egg is visible and not obstructed by a wall. It doesn't even go for the closest egg, but picks the first move that makes sense. If no such egg is found, the bot makes a random move. It disregards all other players and never attacks or counters.

Answer 4

WallFolower

(deliberate pun) in 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)))

Moves to an egg if there is an egg in sight, but only if it is closer to that egg than another robot. If there is a tie in distance, it goes for it anyways. Otherwise, does a LH wall follow (not currently well implemented).

Still needs work on the wall follow, but I'll post this here anyways.