Programming Wars round 9: The Ants are my Friends 2.0

For all your silly time-killing forum games.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Tue Feb 11, 2014 2:51 am UTC

Challenge 9: The Ants are my Friends 2.0

This is an updated, more manageable version of challenge 5.

Please don't be intimidated by the length of this post; the game is not as hard as it may seem. If any clarifications or coding help are needed, feel welcome to ask.


You are an ant, moving in a toroidial plane of 200 by 200 units. This is like pacman: if you walk off the playfield you come back on the other side. You move in any direction, as you are able to make turns at arbitrary angles, and you can only know your position and direction relative to your own start. You walk at a fixed speed of one unit per timestep, leaving a pheromone trace behind you. You also have the option to not walk. The pheromone evaporates at a fixed rate. Between steps you are able to "smell" pheromone trails of your friend at your current position.

Games are played in pairs and start with you and your friend being placed on a pheromone-free torus. You do not know each other's relative positions and directions. Your task is to find each other as fast as you can. The game ends when the friends are within close range. Your program does one such game in a single run.

Prior to the match 100 pairs of random starting positions and -directions are prepared. Each pair of programs is tested twice on each prepared pair of starting positions, once with friend 1 starting at position 1 and once with friend 1 starting at position 2. Games time out after 10000 timesteps. The winning ant is chosen based both on the lowest number of timeouts and the lowest average number of timesteps taken to successfully find friends. Edit: the current plan is to multiply the number of timeouts with the average seek time to obtain the final score of each ant, and declare the ant with the lowest score the winner. If multiple ants have zero timeouts, the tie is broken by the lowest average seek time.

Do not discuss strategies with the other competitors. To motivate you to make your ant as general as possible, at least one mystery ant will be released by the judge. The mystery ant(s) will not be qualified to win.

In order to outsmart your competitors, you'll probably need to be (a) easier to find, (b) better at finding trails and (c) better at using trails to catch up with your friend.

Send your solution to me (Jplus) in a PM, before 5. March. We can extend the deadline if that enables more people to compete. If you have any problems please report them as soon as possible. Feel free to ask for clarifications at any time.

You are allowed to submit multiple ants. However, only one of them can be qualified to win. You can submit the other programs only for curiosity. You are free to pick your favourite ant; choose wisely.

Details:
Spoiler:
You program runs as a subprocess of the judge program. It takes a port number as its last command line argument. Your program will connect to the internet domain socket on localhost with that port number, as a client. Your program keeps running until you have found your friend or the game times out. See the program code section for examples.

Your ant starts with no knowledge about its position or direction relative to the world. You also do not receive any information about your own direction or position at any later point in time, nor do you smell your own trails; if you want to have a sense of where you are relative to your starting point, you have to keep track of it by yourself.

As has been mentioned before, the arena is a (toroidal) square of 200 by 200 units and you walk at 1 unit per timestep. Since you and your friend can make arbitrary turns, coordinates will usually not be integral numbers. The judge program will store coordinates as double-precision floats; you should do the same in order to keep rounding differences to a minimum. Double precision is the default for floats in most programming languages.

Angles are expressed in 16ths of degrees (deglets): 5760 deglets to a full circle, 1440 deglets for an orthogonal left turn, 2880 deglets for a U-turn, 4320 (or -1440) deglets for an orthogonal right turn, 1152 deglets if you want to walk in a counterclockwise pentagon, and so on. Angles are always integers.

You can smell pheromone up to a distance of 0.57 unit. In other words, there is a circle around your current position with radius 0.57 (about 1 square unit) where you will be able to detect trails. You "smell" the trails by being informed about them by the judge program.

The judge program and your ant will take turns in sending messages to each other over the socket. The judge program starts. You always receive the messages from the judge by calling recv on the socket (line-buffered or with a block buffer of 1024 bytes). You also always send a (single) reply by calling send on the socket, except when you just received the stop signal.

Messages by the judge program can take one of the following forms:
(1)

Code: Select all

smell [ ANGLE_OUT AGE PAUSE ANGLE_IN ] \n
Informs you about any trail(s) in your vicinity. ANGLE_OUT is the angle under which the trail exits your vicinity, relative to your current direction. AGE is the number of timesteps since the trail exited. PAUSE is the number of timesteps that passed between the trail entering and exiting your vicinity (as your friend may have decided to stay put, or may have visited multiple points within your vicinity before exiting). ANGLE_IN is the angle under which the trail enters your vicinity (it may be different from ANGLE_OUT if your friend made a turn). The square brackets are meant to indicate that the same pattern may appear zero to multiple times (the brackets do not actually appear in the message). If there are multiple trails they are ordered by age, with the youngest (most recent) first. In order to follow your friend you only need the first ANGLE_OUT; you may use the remaining data to learn more about your friend's behaviour and strategy. The message will never be longer than 1024 bytes (if there are more trail data available (which is unlikely) they are truncated). Example:

Code: Select all

smell 4422 56 1 4422 4422 433 10 2982\n
Two trails. The first enters slightly diagonally from your left, continues in a straight line and exits 56 timesteps ago slightly diagonally to your right. The second enters in almost the opposite of your current direction, stays around for 10 timesteps and exits 433 timesteps ago (again) slightly diagonally to your right (it probably stayed put for a while and then made an orthogonal turn to its right). In order to follow your friend, you send

Code: Select all

walk 4422\n
(see below).
(2)

Code: Select all

stop\n
Tells your program to terminate, either because you have found your friend or because the game has timed out. Your program must obey immediately, without sending any more messages: close the socket and exit with status 0.

Messages by your ant always take one of the following two forms:
(1)

Code: Select all

walk ANGLE\n
This tells the judge program that you'll turn ANGLE deglets relative to your current direction and walk one unit. Turn 0 deglets to keep walking in the same direction.
(2)

Code: Select all

stay\n
Stay where you are. This action does not change your direction.

The pheromone slowly evaporates and becomes undetectable after 500 timesteps. If, by coincidence, you walk into a trail that entered your vicinity more than 500 timesteps ago (but exited less than 500 timesteps ago, otherwise you would smell no trace at all), you can't know which direction it came from. (Edit) A similar situation arises if you walk into the spawn point of your friend. The judge program will always set ANGLE_IN to the magical value 11520 in such cases (i.e. walking into an evaporating trail end or a spawn point). It will not set ANGLE_IN to 11520 in any other case.

You and your friend take "simultaneous" turns; so first both ants are updated with the latest information, then the judge program takes in the next action of both ants.

You have found your friend if your pheromone detection circles overlap. It is also counted as a success if this happens halfway during a step.

On programming sockets: digestible Python tutorial (also useful for other languages), Python library, longwinded C and C++ tutorial, C and C++ on Windows, Haskell, Fortran.

Program code:

The judge program. Run with -h for a manual. You can run it either with Python 2 (the standard interpreter) or with PyPy.

Code: Select all

#! /usr/bin/env python2

''' (c) 2013, 2014 Jplus
    Judge program for the 9th challenge of "Programming Wars",
    a game at the xkcd forums.

    Run ./judge.py --help for instructions. '''

from __future__ import print_function, division
from multiprocessing import Process
from argparse import ArgumentParser

import argparse
import socket as sock
import random
import math
import sys
import os

# settings for the serving socket
FAMILY =    sock.AF_INET
TYPE =      sock.SOCK_STREAM
ADDRESS =   ('localhost', random.randint(50000, 60000))

# properties of the world
SIZE =          200
CIRCLE =        16 * 360
SMELL_RADIUS =  .57
DECAYTIME =     500

# other constants
TAU =       2 * math.pi
DEG2RAD =   TAU / CIRCLE
RADIX2 =    math.sqrt(2)

class Point (object):
    ''' Position or vector in the toroidal plane.

    Warning: valid points are not necessarily valid vectors. Always
    do substraction to get a valid vector before performing any of
    the other operations. '''

    def __init__ (self, x = 0, y = 0):
        self.x = x
        self.y = y

    def __repr__ (self):
        return ' '.join(map(str, (self.x, self.y)))

    @classmethod
    def from_string (cls, string):
        return cls(*(map(float, string.split())))

    def __sub__ (self, other):
        ''' Vector between points. '''
        x = self.x - other.x
        x = minabs(x, x - math.copysign(SIZE, x))
        y = self.y - other.y
        y = minabs(y, y - math.copysign(SIZE, y))
        return Point(x, y)

    def __add__ (self, other):
        ''' Vector addition. '''
        x = self.x + other.x
        x = minabs(x, x - math.copysign(SIZE, x))
        y = self.y + other.y
        y = minabs(y, y - math.copysign(SIZE, y))
        return Point(x, y)

    def __abs__ (self):
        ''' Distance between point and origin. '''
        return math.hypot(self.x, self.y)

    def __mul__ (self, other):
        ''' Inner product of two vectors. '''
        return self.x * other.x + self.y * other.y

    def __rmul__ (self, multiple):
        ''' Scalar product; invoke as `scalar` * `vector`. '''
        return Point(self.x * multiple, self.y * multiple)

    __slots__ = ('x', 'y')

def minabs (x1, x2):
    return x1 if abs(x1) < abs(x2) else x2

def linedist ((a, b), c):  # NOT general, assumes abs(a - b) == 1
    bmina = b - a
    cmina = c - a
    pitch = bmina * cmina  # length of projection of (a, c) on (a, b)
    projection = pitch * bmina
    if pitch < 0:
        return abs(cmina)
    elif pitch > 1:
        return abs(c - b)
    else:
        return abs(c - (a + projection))

class Position (Point):
    ''' Position with direction in the toroidal plane. '''

    def __init__ (self, x = 0, y = 0, angle = 0):
        Point.__init__(self, x, y)
        self.direction = angle

    def __repr__ (self):
        return "'" + ' '.join(map(str, (self.x, self.y, self.direction))) + "'"

    def __xor__ (self, angle):
        ''' New position after setting a step with turning angle `angle`.

        Guarantees positive coordinates. '''
        angle = (self.direction + angle) % CIRCLE
        radians = angle * DEG2RAD
        x = math.fmod(self.x + math.cos(radians) + SIZE, SIZE)
        y = math.fmod(self.y + math.sin(radians) + SIZE, SIZE)
        return Position(x, y, angle)

    __slots__ = 'direction'

class Grid (object):
    ''' Datastructure for storing data by position. Speed over memory. '''

    def __init__ (self, hsize, vsize):
        self._data = [None] * hsize * vsize
        self.hsize = hsize
        self.vsize = vsize

    def __getitem__ (self, key):
        ''' Retrieve all data stored at or near (range of) position(s) key.

        Returns list of data for matching cell, or a generator of such lists
        if a range is requested. '''
        x, y = key
        h = self.hsize
        ystart = int(y.start)
        ystop = int(math.ceil(y.stop))
        if y.start <= y.stop:
            r = range(ystart, ystop)
                # custom stepping not supported
            section = (self._data[(h * i):(h * (i + 1))] for i in r)
        else:
            rs = (range(ystart, self.vsize), range(0, ystop))
            section = (self._data[(h * i):(h * (i + 1))] for r in rs for i in r)
        xstart = int(x.start)
        xstop = int(math.ceil(x.stop))
        if x.start <= x.stop:
            x = slice(xstart, xstop)
            return (entry for row in section for entry in row[x] if entry)
        else:
            xs = (slice(xstart, self.hsize), slice(0, xstop))
            return (entry for row in section for x in xs for entry in row[x] if entry)
        return []

    def __setitem__ (self, key, value):
        ''' Store a value at the given Point. '''
        x, y = int(key.x), int(key.y)
        index = x + self.hsize * y
        if not self._data[index]:
            self._data[index] = []
        self._data[index] += [(key, value)]

    def __str__ (self):
        ''' Show grid contents in tabular form. '''
        s = ''
        for i in range(self.vsize):
            s += str(self._data[(i * self.hsize):((i + 1) * self.hsize)]) + '\n'
        return s

    __slots__ = ('_data', 'hsize', 'vsize')

class Ant:
    ''' Encapsulation of an ant with associated subprocess and socket. '''

    def __init__ (  self, server, command,
                    pos = Position(), log = None, name = None  ):
        self.process = Process(
            target = os.execvp,
            args = (command[0], command + [str(server.getsockname()[1])])
            )
        self.process.start()
        self.socket, self.address = server.accept()
        if name == None: name = ' '.join(command)
        self.name = name
        self.path = [pos]
        self.time = 0
        self.grid = Grid(SIZE, SIZE)
        self.grid[pos] = self.time

        if log:
            self.logfile = log
            self.log = self._nontrivial_logging_function;
            self.log(self.init_string, str(self.address[1]), pos)

    def terminate (self):
        self.socket.send('stop\n')
        self.socket.close()
        self.process.join()
        self.time += 1
        self.log(self.term_string)

    def log (self, formatstring, *data):
        pass

    def send_data (self, data):
        datastring = ' '.join(map(str, data))
        while len(datastring) > 1017:  # 1024 - 'smell' - space - endline
            del data[-4:]
            datastring = ' '.join(map(str, data))
        self.socket.send('smell ' + datastring + '\n')
        self.log(self.trans_string, datastring)

    def get_new_position (self):
        incoming = self.socket.recv(1024)
        words = incoming.split()
        self.time += 1
        if words[0] == 'walk':
            oldpos = self.path[-1]
            newpos = oldpos ^ int(words[1])
            self.log(self.moved_string, words[1], newpos)
        else:
            newpos = self.path[-1]
            self.log(self.stayed_string, newpos)
        self.path += [newpos]
        self.grid[newpos] = self.time
        return newpos

    def get_trace (self, pos):
        query_limits = (pos.x - self._query_dist, pos.x + self._query_dist,
                        pos.y - self._query_dist, pos.y + self._query_dist)
        query_limits = map(lambda x: math.fmod(x + SIZE, SIZE), query_limits)
        xlo, xhi, ylo, yhi = query_limits
        environment = self.grid[xlo:xhi, ylo:yhi]
        return self._encode_trails(pos, self._extract_trails(pos, environment))

    _query_dist = SMELL_RADIUS + 1

    init_string = '({0: 4}) {1}: connected on port {2}, initial position {3}.'
    term_string = '({0: 4}) {1}: terminated.'
    trans_string = '({0: 4}) {1}: received pheromone readings {2}.'
    moved_string = '({0: 4}) {1}: {2} degree turn and walk, new position {3}.'
    stayed_string = '({0: 4}) {1}: remained at position {2}.'

    def _nontrivial_logging_function (self, formatstring, *data):
        print(  formatstring.format(self.time, self.name, *data),
                file = self.logfile     )

    def _extract_trails (self, center, environment):
        age_filtered_data = []
        for cell in environment:
            prune = 0
            for position, time in cell:
                age = self.time - time
                if age >= DECAYTIME:
                    prune += 1
                else:
                    age_filtered_data += [(age, position)]
            del cell[0:prune]
        age_filtered_data.sort()  # each age is unique, so ordered by age
        trails = []
        hot = False
        for i in range(len(age_filtered_data) - 1):
            age, position = age_filtered_data[i]
            next_age, next_position = age_filtered_data[i + 1]
            if hot:
                if next_age - age > 1:
                    hot = False
                elif (abs(position - center) > SMELL_RADIUS):
                    if (linedist((position, next_position), center) <= SMELL_RADIUS):
                        trails += [[(age, position)]]
                    else:
                        hot = False
                else:
                    trails[-1] += [(age, position)]
            elif next_age - age == 1 and (linedist((position, next_position), center) <= SMELL_RADIUS):
                trails += [[(age, position)]]
                hot = True
        if hot and abs(position - center) <= SMELL_RADIUS:
            trails[-1] += [(age, position)]
        return trails

    def _encode_trails (self, origin, traildata):
        if not traildata:
            return []
        encoded = []
        for trail in traildata:
            angle_out = (trail[0][1].direction - origin.direction) % CIRCLE
            age = trail[0][0]
            pause = len(trail) - 1
            angle_in = (trail[-1][1].direction - origin.direction) % CIRCLE
            encoded += [int(angle_out), age, pause, int(angle_in)]
        old_age, old_pos = traildata[-1][-1]
        if old_age == DECAYTIME - 1 or old_age == self.time:
            encoded[-1] = CIRCLE * 2
        return encoded

def pairs (max):
    return [(i, j) for i in xrange(max) for j in xrange((i + 1), max)]

def main (argv):  # expects list without initial program name
    options = parse_commandline(argv)
    server = sock.socket(FAMILY, TYPE)
    server.bind(ADDRESS)
    server.listen(2)  # max no. of ants that can connect simultaneously.
                      # do not listen to more than 5 connections on a
                      # single server; use multiple servers instead.
    if options.commands or options.positions:
        multi_game(server, options)
    else:
        single_game(server, options)
    if options.log and options.log != sys.stdout:
        options.log.close()
    server.close()
    return 0

def single_game (server, options):
    if options.runonce:
        play_game (server, options)
    else:
        while True:
            play_game (server, options)
            userchoice = raw_input('Repeat? [y] > ')
            if userchoice and userchoice.startswith(('n', 'N')):
                break
            print(file = options.log)

def multi_game (server, options):
    if options.commands:
        com = [line.split() for line in options.commands.readlines()]
        options.commands.close()
    else:
        com = [ [options.name1] + options.command1,
                [options.name2] + options.command2 ]
    if options.positions:
        pos = [ Position.from_string(line) for line in
                options.positions.readlines()   ]
        options.positions.close()
    else:
        pos = [options.position2]
    numcommands = len(com)
    compairs = pairs(numcommands)
    fastgames = []
    totals = [0] * numcommands
    timeouts = [0] * numcommands
    numgames = len(compairs) * len(pos) * 2
    p1 = options.position1
    for p2 in pos:
        for i, j in compairs:
            for s1, s2 in ((p1, p2), (p2, p1)):
                result = play_game( server, options, s1, s2,
                                    com[i][0], com[i][1:],
                                    com[j][0], com[j][1:] )
                time_taken = len(result[1]) - 1
                if time_taken == options.timeout:
                    timeouts[i] += 1
                    timeouts[j] += 1
                else:
                    totals[i] += time_taken
                    totals[j] += time_taken
                speed = result[0] / time_taken
                if len(fastgames) < 10 or speed > min(fastgames)[0]:
                    fastgames += [(speed, result)]
    scores = [totals[i] / (numgames - timeouts[i]) for i in xrange(numcommands)]
    for c, s, t in zip(com, scores, timeouts):
        print(c[0], s, t, sep = '\t')
    fastgames.sort(reverse = True)
    record = open('fastgames.log', 'w')
    print(fastgames[:10], file = record)
    record.close()

def play_game ( server, options, pos1 = None, pos2 = None,
                name1 = None, com1 = None, name2 = None, com2 = None ):
    single = True
    if not pos1:
        pos1, pos2 = options.position1, options.position2
    else: single = False
    if not name1:
        name1, com1 = options.name1, options.command1
        name2, com2 = options.name2, options.command2
    else: single = False
    ant1 = Ant(server, com1, pos1, options.log, name1)
    ant2 = Ant(server, com2, pos2, options.log, name2)
    initial_distance = abs(pos1 - pos2)
    for i in xrange(options.timeout):
        ant1.send_data(ant2.get_trace(pos1))
        ant2.send_data(ant1.get_trace(pos2))
        pos1 = ant1.get_new_position()
        pos2 = ant2.get_new_position()
        dist = abs(pos1 - pos2)
        if dist < 2 * SMELL_RADIUS:
            if single: print('\nThe friends found each other at t =', i + 1)
            break
    else:
        if single: print('\nThe friends were unable to find each other!')
    ant1.terminate()
    ant2.terminate()
    if single:
        print('Final position of {0}:'.format(ant1.name), pos1)
        print('Final position of {0}:'.format(ant2.name), pos2)
        print()
    return initial_distance, ant1.path, ant2.path

def parse_commandline (argv):  # expects list without initial program name
    str2pos = lambda s: Position.from_string(s)
    parser = ArgumentParser(
        description = 'Play once or repeatedly with two ants.',
        epilog = options_epilog_string,
        formatter_class = argparse.RawDescriptionHelpFormatter
        )
    controls = parser.add_argument_group('General controls')
    controls.add_argument(
        '-o', '--runonce',
        help = 'do not offer the option to run again (see below)',
        action = 'store_true'
        )
    controls.add_argument(
        '-l', '--log',
        help = 'enable logging, set logfile to LOG (default: stdout)',
        nargs = '?', type = argparse.FileType('w'), const = sys.stdout
        )
    controls.add_argument(
        '-t', '--timeout',
        help = 'the number of timesteps after which the game times out',
        type = int, default = 10000
        )
    ant1 = parser.add_argument_group('Primary ant properties')
    ant1.add_argument(
        '-p', '--position1',
        help = 'initial position of ant 1 (default: "100 100 0")',
        metavar = 'POS1',
        type = str2pos, default = Position(100, 100, 0)
        )
    ant1.add_argument(
        '-n', '--name1',
        help = 'optional short name for ant 1'
        )
    ant1.add_argument(
        '-c', '--command1',
        help = 'a command that starts ant 1 (see below)',
        nargs = '+'
        )
    ant2 = parser.add_argument_group('Secondary ant properties')
    ant2pos = ant2.add_mutually_exclusive_group(required = True)
    ant2pos.add_argument(
        '-q', '--position2',
        help = 'initial position of ant 2',
        metavar = 'POS2',
        type = str2pos
        )
    ant2pos.add_argument(
        '-r', '--positions',
        help = 'file containing a list of initial positions',
        type = argparse.FileType('r')
        )
    ant2.add_argument(
        '-m', '--name2',
        help = 'optional short name for ant 2'
        )
    ant2com = ant2.add_mutually_exclusive_group(required = True)
    ant2com.add_argument(
        '-d', '--command2',
        help = 'a command that starts ant 2 (see below)',
        nargs = '+'
        )
    ant2com.add_argument(
        '-e', '--commands',
        help = 'file containing a list of names and commands',
        type = argparse.FileType('r')
        )
    opts = parser.parse_args(argv)
    if opts.command2 and not opts.command1:
        parser.print_usage()
        print('If you specify COMMAND2 you also have to specify COMMAND1.')
        sys.exit(1)
    return opts

options_epilog_string = '''
~~~ Detailed instructions ~~~
In the "the ants are my friends" game, two ant programs must attempt
to find each other in a toroidal plane. The sooner they find each
other, the better. A timeout is set in case the friends don't succeed.
This program is the host (parent process) and judge for the game. The
host and the ants communicate through an internet domain socket on
localhost. Ant programs must take the port number for the socket as
the last argument.

This program allows two modes of playing the game:

1. A single game. In this case at least the -c, -d and -q parameters
must be specified. By default you are offered the option to repeat the
game; specify -o to suppress this.

2. A match of multiple games. If the -r or -e parameter is specified,
all combinations of ant programs and initial positions are
systematically played. This includes POS1, which has a default value;
you should ensure that the other position(s) are at least 1.5 units
away from it. If -e is specified, -c and -n are ignored. -o
automatically applies in this mode. In the end a scores table is
produced.

Regarding the parameters:

POS1 and POS2 need to be triplets of numbers, surrounded by quotes and
delimited by spaces. The first number is the x coordinate and should
be positive. The second number is the y coordinate and should be
positive as well. The third number is the direction expressed as an
angle with the x axis; a circle is considered to have {0} deglets. In
the POSITIONS file, each line should contain one position in this
format, but WITHOUT the quotes.

By default the full command that launches an ant program will be shown
in your logs. The --name options let you provide a short handle to
keep the logs tidy. These options are ignored if -e is specified.

You need to specify the complete sequence of words that is needed to
launch each ant program (except for the final port number). This
includes the name of the interpreter if a program runs interpreted,
even if the program has a shebang line or file associaton, as well as
any additional arguments that the interpreter and the program may
take. Do not surround the commands by quotes; however, if some of the
arguments within the commands contain spaces you may surround those by
quotes. If a file of commands is given using -e, then each line should
contain one obligatory short name (without whitespace), followed by a
blank, followed by one ant command possibly including blanks.
'''.format(CIRCLE)

if __name__ == '__main__':
    sys.exit(main(sys.argv[1:]))
Edit 2014-02-13 23:34 UTC: patched a bug.
Edit 2014-02-14 10:40 UTC: a few additional patches.

Example ants. These are the submissions to the previous installment of the ants game, with some modifications to make them work with the new judge program. You are encouraged to learn from these programs and to test your own ants against them, but you are not allowed to submit ants that follow the same strategy (the mystery ant(s) will also be different). Note that any analysis of the behaviour of the friend was completely unfeasible in the previous version of the game, so none of the programs below attempts to do that.
Spoiler:
dudiobugtron's ant: doesn't move at all, also known as the "lost child strategy". Written in Python.

Code: Select all

import socket
import sys

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('localhost', int(sys.argv[-1])))

action = 'stay\n'

while True:
    rawdata = s.recv(1024)
    if rawdata.startswith('stop'):
        break
    s.send(action)
s.close()

Snark's ant: picks a random direction at the start, then keeps walking in a straight line (with an occasional pause to allow friends to catch up) until it smells a trail. It then keeps bouncing back and forth around the place where it walked into the trail. The intended behaviour was to follow the trail, but it didn't work at the time because the smell data were insanely hard to interpret in the previous version; the actual behaviour is reproduced here. Written in Python.

Code: Select all

import socket, sys, random

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('localhost', int(sys.argv[-1])))

waiting = False
target = random.randint(60,150)
current = 0
first = True
bouncing = False
move_counter = 0

while True:
    rawdata = s.recv(1024)
    listdata = rawdata.split()
    if listdata[0] == 'stop':
        break
    elif first == True:
        action = 'walk ' + str(random.randint(0,5759))
    elif bouncing == True:
        action = 'walk 2880\n'
    elif waiting == False:
        if len(listdata) == 1:
            action = 'walk 0\n'
        else:
            action = 'walk {0}\n'.format(listdata[1])
            bouncing = True
    else:
        action = 'stay\n'
    move_counter = move_counter + 1
    current = current + 1
    if current == target:
        if waiting == True:
            target = random.randint(60,150)
            waiting = False
        else:
            target = random.randint(10,30)
            waiting = True
        current = 0
    first = False
    s.send(action)
s.close()

benneh's ant: walks circles with a diameter of about 115 units, changing direction (from clockwise to counterclockwise or vice versa) at random intervals. Does not pay any attention to trails at all. Written in Haskell.

Code: Select all

import Control.Monad.Trans (lift)
import Control.Monad.Trans.Maybe (MaybeT (MaybeT), runMaybeT)
import Data.List (stripPrefix)
import Network (PortID (PortNumber), connectTo)
import System.Environment (getArgs)
import System.IO (BufferMode (LineBuffering), Handle, hGetLine, hPutStrLn, hSetBuffering)
import System.Random (randomRIO)

main = do
   args <- getArgs
   h <- connectTo "localhost" (PortNumber . fromIntegral . read . last $ args)
   hSetBuffering h LineBuffering
   go h True

go :: Handle -> Bool -> IO ()
go h dir = do
   input <- hGetLine h
   m <- runMaybeT . process dir $ input
   maybe
      (return ())
      (\(output, dir') -> do
         hPutStrLn h output
         go h dir')
      (m)

process :: Bool -> String -> MaybeT IO (String, Bool)
process dir input = do
   MaybeT . return . stripPrefix "smell" $ input
   r <- lift $ randomRIO (0, 359) :: MaybeT IO Int
   if r == 0
      then return ("walk 2880", not dir)
      else if dir
         then return ("walk 16", dir)
         else return ("walk -16", dir)

mystery ant: walks an outward spiral with straight angle turns and 10 unit pitch (up to a limit size, at which it will pause and then start a new outward spiral from scratch). When it smells a trail, it follows it until it manages to catch up with its friend. Written in Python, as a state machine.

Code: Select all

from __future__ import division
import socket as sock
import sys
from judge import Point, CIRCLE, DECAYTIME

def main (address):
    s = sock.socket(sock.AF_INET, sock.SOCK_STREAM)
    s.connect(address)
    time = 0
    state = Spiral(time)

    while True:
        rawdata = s.recv(1024)
        if rawdata.startswith('stop'): break
        data = rawdata.split()
        action, state = state(data, time)
        if action:
            dir = action[1]
            s.send('walk {0}\n'.format(dir))
        else:
            s.send('stay\n')
        time += 1

    s.close()

class Spiral:
    def __init__ (self, start_time):
        self.corners = 0
        self.turn_dist = 10
        self.turn_time = start_time + self.turn_dist
        self.stop_time = start_time + 2100

    def __call__ (self, readings, time):
        if len(readings) > 1:
            return (True, readings[1]), Chase
        if time == self.stop_time:
            next_cycle = time + DECAYTIME - 1
            return False, Wait(next_cycle, Spiral(next_cycle))
        if time == self.turn_time:
            if self.corners % 2:
                self.turn_dist += 10
            self.turn_time += self.turn_dist
            self.corners += 1
            return (True, 1440), self
        return (True, 0), self

def Chase (readings, time):
    if len(readings) == 1:  # oops, walk a little star to find back trace
        return (True, CIRCLE // 8), Chase
    return (True, readings[1]), Chase

def Wait (trigger_time, next_state):
    def statefunc (readings, time):
        if time == trigger_time:
            return False, next_state
        return False, statefunc
    return statefunc

if __name__ == '__main__':
    main(('localhost', int(sys.argv[1])))

See the attachments for close-up examples of the walking patterns. The pictures were taken from round 5.

Performance based on 200 games per pair of ants (600 games per individual ant, 1200 games total) in the old version of the game:

Code: Select all

ant     average  timeouts
-------------------------
dudio    1032.7       346
Snark     853.8       135
benneh    318.2       193
mystery   782.9        78

Based on these results, Snark was chosen as the winner.

The mystery ant was less impressive than the results may seem to indicate, because the spawn points where (accidentally) chosen such that the mystery ant was very likely to walk into dudiobugtron's ant by coincidence. Fortunately this didn't affect the outcome of the match. In the current round the spawn points will be truly random, so this won't happen again.
Attachments
028_dist127.279220614_time459_speed0.277296776936.png
Snark and benneh
028_dist127.279220614_time459_speed0.277296776936.png (5.85 KiB) Viewed 8596 times
023_dist114.01754251_time276_speed0.413107038079.png
mystery and Snark
023_dist114.01754251_time276_speed0.413107038079.png (6.07 KiB) Viewed 8596 times
019_dist31.6227766017_time69_speed0.458301110169.png
mystery and benneh
019_dist31.6227766017_time69_speed0.458301110169.png (5.99 KiB) Viewed 8596 times
009_dist76.1577310586_time104_speed0.732285875564.png
Snark and dudiobugtron (lucky hit)
009_dist76.1577310586_time104_speed0.732285875564.png (5.4 KiB) Viewed 8596 times
Last edited by Jplus on Fri Feb 14, 2014 10:56 am UTC, edited 7 times in total.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Tue Feb 11, 2014 8:46 am UTC

The changes you've made to the messages from the judge program should make the situation considerably easier to interpret. This should be an interesting round.

I have a couple of questions, though. Firstly: can we submit our programs via spoilered posts to this thread, rather than private messages? It just seems a bit simpler, especially if we're going to be disclosing our programs at the end of the round anyway, and it gives everyone a rough idea of how everyone else is doing. And secondly: what, specifically, does this mean?
Jplus wrote:The winning ant is chosen based both on the lowest number of timeouts and the lowest average number of timesteps taken to successfully find friends.
How are the two criteria weighted?

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Tue Feb 11, 2014 11:40 am UTC

benneh wrote:The changes you've made to the messages from the judge program should make the situation considerably easier to interpret.
Yes, that was the intention. I hope all participants will now be able to implement whatever strategy they can imagine. At least everyone will be able to focus on their strategy rather than on overcoming technical difficulties.
benneh wrote:This should be an interesting round.
I sure hope so!

benneh wrote:I have a couple of questions, though. Firstly: can we submit our programs via spoilered posts to this thread, rather than private messages? It just seems a bit simpler, especially if we're going to be disclosing our programs at the end of the round anyway, and it gives everyone a rough idea of how everyone else is doing.
I'm a bit uncomfortable about that, because you can never be sure that a participant won't use the information to write the perfect friend. Of course we could make an agreement that all participants post their code within a limited date range (perhaps two days), but that would be less flexible than the PM solution. If more than two people participate (which I hope will happen), then it will be hard to find a limited date range of which everyone knows in advance that they'll be able to post their solutions.

But maybe I'm the only person with these concerns. Let the majority speak.
benneh wrote:And secondly: what, specifically, does this mean?
Jplus wrote:The winning ant is chosen based both on the lowest number of timeouts and the lowest average number of timesteps taken to successfully find friends.
How are the two criteria weighted?
I left this intentionally vague, because I think it depends on the situation. If the best ants differ little (say < 10%) in average seek time but a lot in #timeouts, I think the ant with the lowest #timeouts should win. The converse would also fly. If there is a negative correlation between #timeouts and seek time (i.e. if ants with low #timeouts tend to have long average seek time and vice versa) then I think we should calculate the timeout penalties for which each player would win, and then pick the player that would win for the greatest penalty. The latter approach is how the winner was decided in round 5. Maybe it also works for the cases where ants differ little in one respect but a lot in the other. So we could just go with that.

Do you have a particular way to choose the winner in mind?

Edit: since following traces is now almost trivially easy and nobody is allowed to stay put for the entire game (because that strategy was already taken by dudiobugtron in round 5), there might be no timeouts at all. In that case, obviously, the average seek time will be the only deciding factor.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Tue Feb 11, 2014 1:35 pm UTC

Jplus wrote:
benneh wrote:And secondly: what, specifically, does this mean?
Jplus wrote:The winning ant is chosen based both on the lowest number of timeouts and the lowest average number of timesteps taken to successfully find friends.
How are the two criteria weighted?
I left this intentionally vague, because I think it depends on the situation. If the best ants differ little (say < 10%) in average seek time but a lot in #timeouts, I think the ant with the lowest #timeouts should win. The converse would also fly. If there is a negative correlation between #timeouts and seek time (i.e. if ants with low #timeouts tend to have long average seek time and vice versa) then I think we should calculate the timeout penalties for which each player would win, and then pick the player that would win for the greatest penalty. The latter approach is how the winner was decided in round 5. Maybe it also works for the cases where ants differ little in one respect but a lot in the other. So we could just go with that.
Doesn't the latter approach just reduce to whoever has the fewest timeouts winning? (Not that I would have any problem with that.)

Jplus wrote:Do you have a particular way to choose the winner in mind?
No, it's up to you. I just thought it would be a good idea to have the judging process explicitly stated beforehand, to avoid any confusion. Plus, it gives contestants an idea of how much they should prioritise speed over reliability, or vice-versa. This was something that I grappled with in round 5; in the end, I went for simplicity (and hopefully therefore speed) over reliability, and, in hindsight, I feel that was a mistake.

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Vytron » Tue Feb 11, 2014 7:51 pm UTC

benneh wrote:can we submit our programs via spoilered posts to this thread, rather than private messages? It just seems a bit simpler, especially if we're going to be disclosing our programs at the end of the round anyway, and it gives everyone a rough idea of how everyone else is doing.


There could also be a rule that allows players to post their code in spoilered posts, but that makes it against the rules to read such spoilers by other players.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Wed Feb 12, 2014 12:16 am UTC

benneh wrote:
Jplus wrote:[...] calculate the timeout penalties for which each player would win, and then pick the player that would win for the greatest penalty. The latter approach is how the winner was decided in round 5. Maybe it also works for the cases where ants differ little in one respect but a lot in the other. So we could just go with that.
Doesn't the latter approach just reduce to whoever has the fewest timeouts winning? (Not that I would have any problem with that.)
Oops, yes, you're right. Actually this was not exactly the way in which round 5 was decided; I did calculate for which timeout penalty values each player would win, but then looked at the break-even value and decided whether that would be a reasonable penalty, or too low, or too high. So I was kind of comparing the penalty values at which each player would win to some imaginary "ideal" penalty value and then chose the player that was closest to it. We could go with a predetermined fixed penalty, for example 10x the timeout time, but although we might be able to agree about a number it will always be somewhat arbitrary, especially since there are situations possible in which a game will simply never finish.

benneh wrote:
Jplus wrote:Do you have a particular way to choose the winner in mind?
No, it's up to you. I just thought it would be a good idea to have the judging process explicitly stated beforehand, to avoid any confusion. Plus, it gives contestants an idea of how much they should prioritise speed over reliability, or vice-versa. This was something that I grappled with in round 5; in the end, I went for simplicity (and hopefully therefore speed) over reliability, and, in hindsight, I feel that was a mistake.

Thanks for pointing this out, you are absolutely right. I want people to work both on speed and reliability, because I think this makes for the most interesting solutions. I can think of two good objective metrics that take both factors into account:

1. Greatest of (#successes / mean seek time)), where #successes is the number of games in which an ant didn't time out.

Arguably, an ant with twice as many successes is twice as good, and an ant with twice the mean seek time is half as good. This formula is an exact expression of those ideas.
This approach is often taken in benchmarks, but then they would take the square root and call it the geometric mean (of the #successes and the inverse of the mean seek time).

The formula is also equivalent to (#successes2 / total seek time).

Let's see how this works for the outcome of round 5 (timeout + success = 600, i.e. the total #games per ant):

Code: Select all

ant     mean seek time  timeout  success  score
-----------------------------------------------
dudio           1032.7      346      254  0.246
Snark            853.8      135      465  0.545
benneh           318.2      193      407  1.279
mystery          782.9       78      522  0.667
So according to this metric, benneh should have won.

2. Least of (#timeouts * mean seek time).

This a variant of the previous metric, but with the assumption that twice as many successes isn't necessarily twice as good; rather, twice as many timeouts is half as good. In this way more weight is given to reliability when there are few timeouts (which is to be expected for round 9). Here's the hypothetical outcome for round 5:

Code: Select all

ant     mean seek time  timeout  success  score
--------------------------------------------------
dudio           1032.7      346      254  357314.2
Snark            853.8      135      465  115263.0
benneh           318.2      193      407   61412.6
mystery          782.9       78      522   61066.2
Again benneh would have won, but by a lesser margin this time.

Because of the greater weight of reliability at low timeout rates, I propose to use the latter metric.

Vytron wrote:
benneh wrote:can we submit our programs via spoilered posts to this thread, rather than private messages? It just seems a bit simpler, especially if we're going to be disclosing our programs at the end of the round anyway, and it gives everyone a rough idea of how everyone else is doing.

There could also be a rule that allows players to post their code in spoilered posts, but that makes it against the rules to read such spoilers by other players.

That seems obvious to me. But it doesn't offer any guarantee that people won't do it. Nobody can check that somebody isn't peeking.

To be honest, I don't really see why "participants submit their solutions in a spoilered post" is better than "participants submit their solutions in a PM and the judge publishes their solutions after the deadline has passed". Unless we actually allow peeking, and the challenge becomes to design the best ant given knowledge about other ants. But then participants who submit late have an unfair advantage. So then it should be an open challenge without a deadline and with a running top-3 or something like that. Actually I think the latter would be quite cool, but I propose to do that when round 9 has finished so we'll have a definitive winner who can start round 10.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Wed Feb 12, 2014 12:28 am UTC

Ego post, even though it's unlikely I'll have time to throw an entry together.
Image

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Vytron » Wed Feb 12, 2014 1:59 am UTC

Jplus wrote:That seems obvious to me. But it doesn't offer any guarantee that people won't do it. Nobody can check that somebody isn't peeking.


True, though, in the Mafia Subforum and several other games played on this section those kind of rules are common place and there hasn't been any accusation or suspicion of someone cheating, so players tend to add those "reading x spoilers is against the rules" in their games confident enough that no player will break those rules.

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Wed Feb 12, 2014 9:31 am UTC

Jplus wrote:2. Least of (#timeouts * mean seek time).

This a variant of the previous metric, but with the assumption that twice as many successes isn't necessarily twice as good; rather, twice as many timeouts is half as good. In this way more weight is given to reliability when there are few timeouts (which is to be expected for round 9). Here's the hypothetical outcome for round 5:

Code: Select all

ant     mean seek time  timeout  success  score
--------------------------------------------------
dudio           1032.7      346      254  357314.2
Snark            853.8      135      465  115263.0
benneh           318.2      193      407   61412.6
mystery          782.9       78      522   61066.2
Again benneh would have won, but by a lesser margin this time.

Because of the greater weight of reliability at low timeout rates, I propose to use the latter metric.
That seems reasonable to me. If multiple programs end with 0 timeouts, would the tie then be decided on their mean seek times alone?

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Wed Feb 12, 2014 10:02 pm UTC

benneh wrote:
Jplus wrote:2. Least of (#timeouts * mean seek time).

[...]

Because of the greater weight of reliability at low timeout rates, I propose to use the latter metric.
That seems reasonable to me. If multiple programs end with 0 timeouts, would the tie then be decided on their mean seek times alone?

Yes, let's do that.

(Actually I already added that to the OP.)
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Thu Feb 13, 2014 7:45 pm UTC

I'm attempting to write a simple test program, and something is happening that I don't understand. Presumably I've misunderstood part of the setup somehow, but I've no idea what.

The test program works as follows:
First, randomly choose a 'speed' v between 0 and 1.
Then, each turn:
If you cannot smell the other ant's pheromone trail, move forwards.
If you can smell the other ant's pheromone trail: follow the trail with probability v, stay put with probability (1-v).

The intended behaviour is to move straight ahead until you hit the other ant's pheromone trail, then follow the trail at an average speed of v units / turn.

In order to test the test program, I'm running some games with the following setup:
Player 1 (named "prey") has initial position (90, 100, 0).
Player 2 (named "predator") has initial position (100, 80, 1440).
So prey starts 10 units to the west of centre, heading east, and predator starts 20 units to the south of centre, heading north. Predator will reach prey's trail at the centre of the field, 10 turns behind prey, and begin the chase eastwards. But something odd happens around turn 210 when prey wraps around and reaches the centre of the field and encounters predator's pheromone trail for the first time. As far as I can tell, prey should begin to 'chase' predator eastwards; both ants should then continue to travel eastwards until their speed difference causes them to meet or they time out. But that isn't what happens. Here are the relevant lines from the log:

Code: Select all

( 209) prey: 0 degree turn and walk, new position 99.0 100.0 0.0.
( 209) predator: 0 degree turn and walk, new position 38.0 100.0 0.0.
( 209) prey: received pheromone readings .
( 209) predator: received pheromone readings 0 60 1 0.
( 210) prey: 0 degree turn and walk, new position 100.0 100.0 0.0.
( 210) predator: 0 degree turn and walk, new position 39.0 100.0 0.0.
( 210) prey: received pheromone readings 1440 188 2 1440.
( 210) predator: received pheromone readings 0 60 1 0.
( 211) prey: remained at position 100.0 100.0 0.0.
( 211) predator: 0 degree turn and walk, new position 40.0 100.0 0.0.
( 211) prey: received pheromone readings 1440 189 2 1440.
( 211) predator: received pheromone readings 0 60 1 0.
( 212) prey: 1440 degree turn and walk, new position 100.0 101.0 1440.0.
( 212) predator: remained at position 40.0 100.0 0.0.
( 212) prey: received pheromone readings .
( 212) predator: received pheromone readings 0 61 1 0.
( 213) prey: 0 degree turn and walk, new position 100.0 102.0 1440.0.
( 213) predator: 0 degree turn and walk, new position 41.0 100.0 0.0.
( 213) prey: received pheromone readings .
( 213) predator: received pheromone readings 0 61 1 0.
( 214) prey: 0 degree turn and walk, new position 100.0 103.0 1440.0.
( 214) predator: remained at position 41.0 100.0 0.0.
( 214) prey: received pheromone readings .
( 214) predator: received pheromone readings 0 62 1 0.
( 215) prey: 0 degree turn and walk, new position 100.0 104.0 1440.0.
( 215) predator: remained at position 41.0 100.0 0.0.
( 215) prey: received pheromone readings .
( 215) predator: received pheromone readings 0 63 1 0.
( 216) prey: 0 degree turn and walk, new position 100.0 105.0 1440.0.
( 216) predator: 0 degree turn and walk, new position 42.0 100.0 0.0.
( 216) prey: received pheromone readings .
( 216) predator: received pheromone readings 0 63 1 0.
On turn 210, prey reaches the centre of the field and encounters predator's pheromone trail for the first time, as expected. But the information received indicates that predator left the centre of the board heading north, not east. Prey then heads north, loses the trail, and continues wandering aimlessly northwards, instead of continuing the chase eastwards.

What's going on? Is this a bug in the judge program, or have I just misunderstood something?

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Thu Feb 13, 2014 10:56 pm UTC

I can reproduce the problem and it's certainly a bug. Expect a patch within a day. I'll edit this post if no other posts appear in the meanwhile.

Edit: I found and fixed the bug. You can obtain the fix in two ways. The first option is to replace lines 262-290 in your copy of the judge program by the lines in the code tags below. The second option is to re-copy the entire file from the opening post, which I patched.

Code: Select all

            if hot:
                if next_age - age > 1:
                    hot = False
                elif (abs(position - center) > SMELL_RADIUS):
                    if (linedist((position, next_position), center) <= SMELL_RADIUS):
                        trails += [[(age, position)]]
                    else:
                        hot = False
                else:
                    trails[-1] += [(age, position)]
            elif next_age - age == 1 and (linedist((position, next_position), center) <= SMELL_RADIUS):
                trails += [[(age, position)]]
                hot = True
        if hot and abs(position - center) <= SMELL_RADIUS:
            trails[-1] += [(age, position)]
        return trails

    def _encode_trails (self, origin, traildata):
        if not traildata:
            return []
        encoded = []
        for trail in traildata:
            angle_out = (trail[0][1].direction - origin.direction) % CIRCLE
            age = trail[0][0]
            pause = len(trail) - 1
            angle_in = (trail[-1][1].direction - origin.direction) % CIRCLE
            encoded += [int(angle_out), age, pause, int(angle_in)]
        old_age, old_pos = traildata[-1][-1]
        if old_age == DECAYTIME - 1:


While testing and editing the code it occurred to me that the judge program will happily pretend that your friend entered your vicinity in the same direction as it exited when you happen to walk into your friend's spawn point (within 500 timesteps after start). I feel this situation should be treated in the same way as walking into the "end" of the trail that is about to evaporate, i.e. by setting the ANGLE_IN to the magical value 11520. Do the participants agree?
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Fri Feb 14, 2014 8:25 am UTC

Great. The patch works fine; the test programs in the setup I mentioned above almost always find each other eventually now. Thanks for the quick response.

Jplus wrote:While testing and editing the code it occurred to me that the judge program will happily pretend that your friend entered your vicinity in the same direction as it exited when you happen to walk into your friend's spawn point (within 500 timesteps after start). I feel this situation should be treated in the same way as walking into the "end" of the trail that is about to evaporate, i.e. by setting the ANGLE_IN to the magical value 11520. Do the participants agree?
That seems like the only sensible solution to me. Essentially, that's treating it as if the ants have been standing still for a very long time prior to the beginning of the round, which seems like a reasonable way to start things off.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Fri Feb 14, 2014 10:51 am UTC

A few additional, less essential patches. These have also been applied to the code in the opening post.

Line 107: a change in the encoding of the fastgames.log file, which I needed for compatibility with my game drawing program. I have no idea why I didn't need this previously.

Code: Select all

        return "'" + ' '.join(map(str, (self.x, self.y, self.direction))) + "'"


After line 206, insert these lines to ensure that the judge program will never send messages larger than 1024 bytes:

Code: Select all

        while len(datastring) > 1017:  # 1024 - 'smell' - space - endline
            del data[-4:]
            datastring = ' '.join(map(str, data))


Change line 293 into this to have the judge program inform your ant about the spawn point in the same way as about the evaporating end of a trail:

Code: Select all

        if old_age == DECAYTIME - 1 or old_age == self.time:
Note: this is line 293 if you inserted those lines after line 206 as mentioned in the previous patch. Otherwise it will be line 290.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Fri Feb 14, 2014 5:05 pm UTC

Is your game drawing program in a state in which it could be used by other people? Being able to see what your ants are doing instead of having to trawl through log files would be very convenient for testing purposes.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Fri Feb 14, 2014 5:23 pm UTC

I think it is. Here, have at it. It depends on PyCairo. It works only for the "fastgames.log" output file of multi-game mode. Run with

Code: Select all

python drawgames.py fastgames.log


Code: Select all

#! /usr/bin/env python2

from __future__ import print_function, division
import sys

import cairo

from judge import SIZE, TAU, Point, Position

def main (filename):
    listing = open(filename)
    gamelist = eval(listing.read())
    listing.close()
    for i, game in enumerate(gamelist):
        draw_game(game, i)
    return 0

def draw_game (gamedata, queueno):
    speed, (init_dist, ant1, ant2) = gamedata
    filename = '{0:0>3}_dist{1}_time{2}_speed{3}.svg'.format(
                    queueno, init_dist, len(ant1) - 1, speed
                )
    ps = cairo.SVGSurface(filename, 4 * SIZE, 4 * SIZE)
    cr = cairo.Context(ps)
    cr.transform(cairo.Matrix(4, 0, 0, -4, 0, 4 * SIZE))
    cr.set_line_width(.25)
    cr.set_line_cap(cairo.LINE_CAP_SQUARE)
    cr.set_line_join(cairo.LINE_JOIN_ROUND)
    cr.set_source_rgb(0, .125, 1)
    draw_path(cr, ant1)
    cr.set_source_rgb(1, .25, 0)
    draw_path(cr, ant2)
    cr.show_page()

def draw_path (context, path):
    prev = Position.from_string(path[0])
    context.arc(prev.x, prev.y, .7, 0, TAU)
    context.fill()
    context.move_to(prev.x, prev.y)
    for s in path[1:]:
        curr = Position.from_string(s)
        dif = curr - prev
        if abs(curr.x - prev.x) > 1.1 or abs(curr.y - prev.y) > 1.1:
            context.line_to(prev.x + dif.x, prev.y + dif.y)
            context.stroke()
            context.move_to(curr.x - dif.x, curr.y - dif.y)
        context.line_to(curr.x, curr.y)
        prev = curr
    context.stroke()
    context.arc(curr.x, curr.y, .75, 0, TAU)
    context.stroke()

if __name__ == '__main__':
    sys.exit(main(sys.argv[1]))
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Sat Feb 15, 2014 8:53 am UTC

Thanks. That works fine, and makes things much easier.

On an unrelated note, a thought has occurred to me: once you've decided on your ant's strategy, it might be possible to submit some additional ants with strategies designed to work well with your primary ant's strategy, but poorly with any other strategy. By submitting ants like this, you would boost your primary ant's score slightly, and lower all the other ants' scores slightly. Are we allowed to do this?

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Sat Feb 15, 2014 6:49 pm UTC

benneh wrote:On an unrelated note, a thought has occurred to me: once you've decided on your ant's strategy, it might be possible to submit some additional ants with strategies designed to work well with your primary ant's strategy, but poorly with any other strategy. By submitting ants like this, you would boost your primary ant's score slightly, and lower all the other ants' scores slightly. Are we allowed to do this?

I find that a hard question. I can think of reasons to allow it but also of reasons to disallow it. Reasons to allow it would be (a) since you've now openly coined the idea, everyone can prepare for it and perhaps try to use the same trick, and (b) by introducing ants that aren't designed to work well with other ants in general, you are just giving the other players more incentive to make their ants as robust as possible. On the other hand, the primary idea behind this challenge is that you try to be the best at cooperating, and introducing secondary ants that are meant to give your primary ant an advantage at the expense of others seems like the opposite. Personally I prefer that you only submit ants which you believe might be good cooperators.

Then, there's another argument of which I'm not sure whether it's in favour or against allowing such "egocentric ant teams". If you expect the performance of your primary ant to be boosted by your custom "crippled" secondary ants, your primary ant probably relies on some of the behaviour of your secondary ants. That would mean that your primary ant isn't really general, either, so it might perform worse with ants of other players which were just designed to be robust. In other words, submitting a "team" of ants that doesn't cooperate externally, like you describe, might amount to shooting yourself in the foot.

Before making a definitive decision about this, I'd like to know the opinion of more participants. In any case, I propose that if there are N players, each player can submit at most N-2 ants (so that a single player cannot get a majority), and that all ants submitted by the same player should have unique strategies (i.e. making small variations on the same strategy just to be able to send more ants is not allowed).

If it turns out that a player has submitted more ants than allowed by the number of players, they will get free choice on which ants to retract.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby benneh » Sun Feb 16, 2014 4:07 pm UTC

For what it's worth, I'm inclined to agree that it seems against the spirit of the challenge to submit ants which have been designed to be "crippled".

User avatar
Carlington
Posts: 1588
Joined: Sun Mar 22, 2009 8:46 am UTC
Location: Sydney, Australia.

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Carlington » Mon Feb 17, 2014 7:02 am UTC

I'm not a player, but I've been watching this game since round 1. I wanted to chime in here and say that a potential way of dealing with this scenario is to allow players to submit many ants (possibly up to a limit, although that limit might just be how many ants you can write before deadline) - however, the player's score is then the average (as in, mean) of the scores of all ants submitted by the player. That way, if they submit more than one ant in a genuine effort to do well, they're likely to keep their score relatively high, but if they submit lots of "crippled", non-cooperative ants, their score could suffer.
Kewangji: Posdy zwei tosdy osdy oady. Bork bork bork, hoppity syphilis bork.

Eebster the Great: What specifically is moving faster than light in these examples?
doogly: Hands waving furiously.

Please use he/him/his pronouns when referring to me.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Mon Feb 17, 2014 1:58 pm UTC

Thanks for the comment. :)

It's a solution for the crippled ants problem. I'm not sure whether it is satisfactory for people who write multiple ants, and then suspect most of them won't score well but nonetheless wonder how they'd do against the others. In other words, whether it's curiosity-friendly. On the other hand, I guess you could just tell those people to run their own matches afterwards.

More comments are welcome.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Mon Feb 17, 2014 9:47 pm UTC

Is there are any distinction between our pheromone trail and that of our friend?
I would hate to get confused and be stuck following my own tail.
Image

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Mon Feb 17, 2014 10:37 pm UTC

Yes. You do not smell your own trail. At all.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Vytron » Mon Feb 17, 2014 11:50 pm UTC

As another person interesting in this, though unable to play, I have another idea: hold two competitions at once, in one, one only is able to send one Ant, the master one, and that's it, the best ant wins. In another, one is allowed to send multiple ants, and the best scoring one wins; players are encouraged to send ants that perform poorly but that enhance the score of the master ant, so it's some kind of ants sacrificing themselves for others.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Tue Feb 18, 2014 5:16 pm UTC

Thanks for your suggestion, Vytron.

So far we have about as many ideas as participants in the discussion. It's hard to make a decision! I guess I could just force my own preference if nobody comes with a definitive killer argument, given that I'm the judge...

Vytron wrote:As another person interesting in this, though unable to play,

What makes you unable to play? Are you sure you couldn't get something to work if you copy dudiobugtron's ant and peek in Snark's program to figure out how to make a few edits? I can even help you a little to realise your idea, if you want (not to design a strategy, mind you).
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Tue Feb 18, 2014 6:54 pm UTC

Given the likely numbers, I would suggest permitting multiple entries. Maybe you'd want to cap it at three or something.
I wouldn't worry about people entering deliberately ants to cripple other entries but enhance their own. I'm not even convinced such a thing could be made to work reliably.
It's not like this is super competitive.
Image

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Vytron » Tue Feb 18, 2014 11:22 pm UTC

Wait, what? I can just make a few edits to another player's ant and call it my own o_O - okay... let me take a look into that...

Xenomortis wrote:I wouldn't worry about people entering deliberately ants to cripple other entries but enhance their own. I'm not even convinced such a thing could be made to work reliably.


Hehe, yeah, it's just a possibility, like in the roshambo/titfortat bot competitions where once one bot receives signals from its master it goes into submissive mode. Here, I'd imagine that when the slave ants actually find another, they try to "dance" with it, if the other dances, it's the master, so they meet ASAP. If the other doesn't "dance", it's an enemy, so the slave ant avoids meeting it to greatly damage its score. The master just meets enemy ants ASAP, while trying to "dance" with them to check if they're slaves.

This should guarantee the master's victory.

The hardest part is the "dancing" part, an ant would need to recognize patterns on the pheromones of the other ant, and well, this may be impossible if the enemy ants are going to meet the slave ant running away from them faster than the time lost by the master ant trying to "dance" with enemies.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Tue Feb 18, 2014 11:40 pm UTC

Well, there are more direct ways to work out if it's your partner program that's being run. It's just that it wouldn't be easy to hide your intentions in the code.
Image

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Wed Feb 19, 2014 7:25 am UTC

Xenomortis wrote:Given the likely numbers, I would suggest permitting multiple entries. Maybe you'd want to cap it at three or something.
I wouldn't worry about people entering deliberately ants to cripple other entries but enhance their own. I'm not even convinced such a thing could be made to work reliably.
It's not like this is super competitive.

Thanks. Yes, I think I'll go this route and basically just stick with my initial plan. I'm not even going to cap the number of submissions per player. Perhaps if everyone has multiple ants each player can have two primary ants that compete for the winning position. Or maybe I'll even allow people to opt-in for a construction where they set as many primary ants as they want, on the condition that the average of those ants will be deciding for winning/not winning.

Vytron wrote:Wait, what? I can just make a few edits to another player's ant and call it my own o_O - okay... let me take a look into that...

Why yes, please do. The emphasis in this challenge is on who can figure out the best strategy, not on who is best at overcoming technical hurdles. (Of course, being good at programming is helpful if you want to implement a complicated strategy.)

Xenomortis wrote:Well, there are more direct ways to work out if it's your partner program that's being run. It's just that it wouldn't be easy to hide your intentions in the code.

You make me curious. What is such a direct way?
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Carlington
Posts: 1588
Joined: Sun Mar 22, 2009 8:46 am UTC
Location: Sydney, Australia.

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Carlington » Wed Feb 19, 2014 9:51 am UTC

Off the top of my head, wouldn't it be possible to create some sort of method in the code that returns a certain value when called, and then write your partner ants to try calling that method somehow to check whether it's the ant they're looking for? (I'm not competing, just answering your question.) Alternative ly, is it possible to "mark" the pheromone trail somehow?
Kewangji: Posdy zwei tosdy osdy oady. Bork bork bork, hoppity syphilis bork.

Eebster the Great: What specifically is moving faster than light in these examples?
doogly: Hands waving furiously.

Please use he/him/his pronouns when referring to me.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Wed Feb 19, 2014 10:16 am UTC

Carlington wrote:Off the top of my head, wouldn't it be possible to create some sort of method in the code that returns a certain value when called, and then write your partner ants to try calling that method somehow to check whether it's the ant they're looking for? (I'm not competing, just answering your question.) Alternative ly, is it possible to "mark" the pheromone trail somehow?

In any modern OS, processes are largely isolated from one another. The address space (and hence the code) are unique to the process; you can't call one processes code from a different process.
But that doesn't mean they can't communicate.

JPlus wrote:You make me curious. What is such a direct way?

And throw away my advantage? :wink:
Spoiler:
I look at the list of running processes.
Or I have my programs, in separate threads, attempt to talk to each other.
Or I use the file-system in some way.
Image

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Wed Feb 19, 2014 1:32 pm UTC

Carlington wrote:I'm not competing

Why not, actually? You seem interested.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Carlington
Posts: 1588
Joined: Sun Mar 22, 2009 8:46 am UTC
Location: Sydney, Australia.

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Carlington » Thu Feb 20, 2014 1:49 am UTC

I lack the technical skill to keep up, honestly. Also, implementing solutions to problems isn't my jam, so much. I can have a wonderful half-hour spitball session and come up with a whiteboard full of ideas and ways to solve the problem, but no clue how to actually make them happen. I'm much better at implementing little things, like writing short scripts to automate tasks I do a lot.
Kewangji: Posdy zwei tosdy osdy oady. Bork bork bork, hoppity syphilis bork.

Eebster the Great: What specifically is moving faster than light in these examples?
doogly: Hands waving furiously.

Please use he/him/his pronouns when referring to me.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Thu Feb 20, 2014 2:03 am UTC

Well, simple strategies can usually be implemented in less than 20 lines (at least if we're talking Python). Also, my offer to Vytron to help her realise her ideas apply to you as well (and to anybody else who doesn't feel competent enough to participate in the challenge on their own).

Just saying.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Vytron » Thu Feb 20, 2014 4:20 am UTC

Haha! First time being called a she despite being a he! :mrgreen:

Anyway, I guess I'd base mine on the mystery ant, since, the concept would just be to try to find the other ant and chase it and that already has code for that. The idea would be to edit this part of the code?:

Code: Select all

class Spiral:
    def __init__ (self, start_time):
        self.corners = 0
        self.turn_dist = 10
        self.turn_time = start_time + self.turn_dist
        self.stop_time = start_time + 2100

    def __call__ (self, readings, time):
        if len(readings) > 1:
            return (True, readings[1]), Chase
        if time == self.stop_time:
            next_cycle = time + DECAYTIME - 1
            return False, Wait(next_cycle, Spiral(next_cycle))
        if time == self.turn_time:
            if self.corners % 2:
                self.turn_dist += 10
            self.turn_time += self.turn_dist
            self.corners += 1
            return (True, 1440), self
        return (True, 0), self


So that the ant moves in some manner, I'm thinking something like...

Image

Which seems simple enough as I just need U turning code, waiting code, and 90-degree turning code and switch between the three, though, no idea how hard is it to implement in reality.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Thu Feb 20, 2014 11:32 am UTC

Vytron wrote:Haha! First time being called a she despite being a he! :mrgreen:

Well I read in the gamers pronouns thread that you didn't care, so I thought, let's use female ones for variation. :)

Vytron wrote:Anyway, I guess I'd base mine on the mystery ant, since, the concept would just be to try to find the other ant and chase it and that already has code for that. The idea would be to edit this part of the code?:

I'm going to reply in a PM. In general, you are encouraged to ask me for help, but I recommend that you do so in private.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Thu Feb 20, 2014 2:48 pm UTC

Since it took me a little while to work out how to get this thing to work, if you want a nice visualisation of your ant's behaviour, you can use Julian's script from the past round to generate pretty pictures.
Spoiler:

Code: Select all

#! /usr/bin/env python2

from __future__ import print_function, division
import sys

import cairo

from judge import SIZE, TAU, Point, Position

def main (filename):
    listing = open(filename)
    gamelist = eval(listing.read())
    listing.close()
    for i, game in enumerate(gamelist):
        draw_game(game, i)
    return 0

def draw_game (gamedata, queueno):
    speed, (init_dist, ant1, ant2) = gamedata
    filename = '{0:0>3}_dist{1}_time{2}_speed{3}.svg'.format(
                    queueno, init_dist, len(ant1) - 1, speed
                )
    ps = cairo.SVGSurface(filename, 4 * SIZE, 4 * SIZE)
    cr = cairo.Context(ps)
    cr.transform(cairo.Matrix(4, 0, 0, -4, 0, 4 * SIZE))
    cr.set_line_width(.25)
    cr.set_line_cap(cairo.LINE_CAP_SQUARE)
    cr.set_line_join(cairo.LINE_JOIN_ROUND)
    cr.set_source_rgb(0, .125, 1)
    draw_path(cr, ant1)
    cr.set_source_rgb(1, .25, 0)
    draw_path(cr, ant2)
    cr.show_page()

def draw_path (context, path):
    prev = Position.from_string(path[0])
    context.arc(prev.x, prev.y, .7, 0, TAU)
    context.fill()
    context.move_to(prev.x, prev.y)
    for s in path[1:]:
        curr = Position.from_string(s)
        dif = curr - prev
        if abs(curr.x - prev.x) > 1.1 or abs(curr.y - prev.y) > 1.1:
            context.line_to(prev.x + dif.x, prev.y + dif.y)
            context.stroke()
            context.move_to(curr.x - dif.x, curr.y - dif.y)
        context.line_to(curr.x, curr.y)
        prev = curr
    context.stroke()
    context.arc(curr.x, curr.y, .75, 0, TAU)
    context.stroke()

if __name__ == '__main__':
    sys.exit(main(sys.argv[1]))


To use it, you need to run a series of multiple games using judge.py.
Create a text file, e.g. poslist.txt, and write some starting positions (only need one) like this:

Code: Select all

100 100 0

Then call judge.py:

Code: Select all

judge.py -c [your program] -d [opponent program] -r poslist.txt

This'll write a file containing the data of the fastest games (or the two games played from your single starting position).
Call Julian's script given above (call it pictures.py):

Code: Select all

pictures.py fastest.log

And it'll generate SVG pictures of the recorded games.

Someone who speaks better Pythonese than me should be able to alter the scripts to do things more directly.
And ideally I'd like an animation.
Carlington wrote:I lack the technical skill to keep up, honestly. Also, implementing solutions to problems isn't my jam, so much. I can have a wonderful half-hour spitball session and come up with a whiteboard full of ideas and ways to solve the problem, but no clue how to actually make them happen. I'm much better at implementing little things, like writing short scripts to automate tasks I do a lot.

There's something very satisfying about seeing a solution at work.
And when in doubt, try returning the result of some trig function. It may not be the best solution, but the patterns are always neat.

Vytron wrote:Which seems simple enough as I just need U turning code, waiting code, and 90-degree turning code and switch between the three, though, no idea how hard is it to implement in reality.

Depending on your programming experience, either trivial or something you'll have to think carefully about.
Perfectly reasonable even with minimal programming experience however.
Image

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Thu Feb 20, 2014 9:31 pm UTC

So I initially misinterpreted ANGLE_IN and ANGLE_OUT.
As they currently stand, the information given to us seems a little strange. We have no way of knowing *where* in our little sense-circle the trail is located, or where it is exiting and entering our circle.
Simply emitting ANGLE_OUT will cause our ants to run parallel to the trail, rather than head towards it.

Wouldn't it be more sane (and intuitive) if ANGLE_IN/OUT represent the clockwise angle between our current direction and the line formed by our current position and the point at which the trail enters/exists our little circle?
Image

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Jplus » Thu Feb 20, 2014 10:11 pm UTC

Xenomortis wrote:Since it took me a little while to work out how to get this thing to work, if you want a nice visualisation of your ant's behaviour, you can use Julian's script from the past round to generate pretty pictures.
[...]
To use it, you need to run a series of multiple games using judge.py.
Create a text file, e.g. poslist.txt, and write some starting positions (only need one) like this:
[...]

Thanks for contributing a detailed manual!

Someone who speaks better Pythonese than me should be able to alter the scripts to do things more directly.
And ideally I'd like an animation.

I agree about the animation. What do you mean by "doing things more directly"?

Xenomortis wrote:So I initially misinterpreted ANGLE_IN and ANGLE_OUT.
As they currently stand, the information given to us seems a little strange. We have no way of knowing *where* in our little sense-circle the trail is located, or where it is exiting and entering our circle.
Simply emitting ANGLE_OUT will cause our ants to run parallel to the trail, rather than head towards it.

But since your sense-circle is, well, a circle, if the trail is within range in the current turn and you walk parallel to it, it will most likely also be in detection range in the next turn. For that reason it doesn't really matter where on the perimeter of your circle the trail exits. Moreover, walking parallel to the trail is the most efficient way to follow it.

Wouldn't it be more sane (and intuitive) if ANGLE_IN/OUT represent the clockwise angle between our current direction and the line formed by our current position and the point at which the trail enters/exists our little circle?

If you walk towards the spot where the trail exits your circle instead, you are likely to zig-zag along the trail, thus reducing your effective chasing speed. In the limit you can even oscillate on the spot without ever getting closer to your friend. I wouldn't find such an encoding intuitive at all.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Xenomortis
Not actually a special flower.
Posts: 1445
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Programming Wars round 9: The Ants are my Friends 2.0

Postby Xenomortis » Thu Feb 20, 2014 10:54 pm UTC

Jplus wrote:
Someone who speaks better Pythonese than me should be able to alter the scripts to do things more directly.
And ideally I'd like an animation.

I agree about the animation. What do you mean by "doing things more directly"?

Either connect or integrate the script into the judge program, or something.

JPlus wrote:
Xenomortis wrote:So I initially misinterpreted ANGLE_IN and ANGLE_OUT.
As they currently stand, the information given to us seems a little strange. We have no way of knowing *where* in our little sense-circle the trail is located, or where it is exiting and entering our circle.
Simply emitting ANGLE_OUT will cause our ants to run parallel to the trail, rather than head towards it.

But since your sense-circle is, well, a circle, if the trail is within range in the current turn and you walk parallel to it, it will most likely also be in detection range in the next turn. For that reason it doesn't really matter where on the perimeter of your circle the trail exits. Moreover, walking parallel to the trail is the most efficient way to follow it.

But you can't do anything clever. I can't "guess" where he might be going, and I cannot move closer.
And there are cases where you might step out of range, whereas that cannot happen if you take your step toward the exit point.

If the trail is toward the edge of my circle, then I'm in very real danger of stepping away from it by simply running parallel (since I might miss a turn).


JPlus wrote:
Wouldn't it be more sane (and intuitive) if ANGLE_IN/OUT represent the clockwise angle between our current direction and the line formed by our current position and the point at which the trail enters/exists our little circle?

If you walk towards the spot where the trail exits your circle instead, you are likely to zig-zag along the trail, thus reducing your effective chasing speed. In the limit you can even oscillate on the spot without ever getting closer to your friend. I wouldn't find such an encoding intuitive at all.

I cannot think of a case where you'd oscillate without getting closer.
But I could still choose to move parallel to a line segment, or attempt to move in a way that'd move me onto it.
I'd have to do some calculations and I have to have a way of deciding when to do it, but the option is there.

I just feel that the extra information enables you to do more, both in finding and being found.
On the other hand, I don't see anyone doing anything particularly complicated, least of all myself, and since it's the simple case that degrades, you might want to keep things as is.
Image


Return to “Forum Games”

Who is online

Users browsing this forum: SuperJedi224 and 46 guests