Lab Rat Race: un ejercicio en algoritmos genéticos

113

Este es el desafío quincenal # 3. Tema: Algoritmos Genéticos

Este desafío es un poco un experimento. Queríamos ver qué podíamos hacer, a nivel de desafío, con algoritmos genéticos. Puede que no todo sea óptimo, pero hicimos todo lo posible para que fuera accesible. Si esto funciona, quién sabe lo que podríamos ver en el futuro. ¿Quizás un genético Rey de la colina?

¡La especificación es bastante larga! Hemos tratado de separar la especificación en The Basics, lo mínimo que necesita saber para comenzar a jugar con el marco y enviar una respuesta, y The Gory Details, la especificación completa, con todos los detalles sobre el controlador, según los cuales usted podría escribir el tuyo
Si tiene alguna pregunta, ¡no dude en unirse a nosotros en el chat!

Eres investigador en psicología del comportamiento. Es viernes por la noche y usted y sus colegas deciden divertirse y usar sus ratas de laboratorio para una pequeña carrera de ratas. De hecho, antes de que nos apeguemos demasiado a ellos, llamémosles especímenes .

Has configurado una pequeña pista de carreras para los especímenes, y para hacerlo más interesante, has puesto algunas paredes, trampas y teletransportadores en la pista. Ahora, tus especímenes siguen siendo ratas ... no tienen idea de qué es una trampa o un teletransportador. Todo lo que ven es algunas cosas en diferentes colores. Tampoco tienen ningún tipo de memoria: todo lo que pueden hacer es tomar decisiones basadas en su entorno actual. Supongo que la selección natural seleccionará los especímenes que saben cómo evitar una trampa de los que no lo hacen (esta carrera llevará un tiempo ...). ¡Que empiecen los juegos!

Imagen de ejemplo de tablero en uso

† 84,465 especímenes fueron dañados en la realización de este desafío.

Los basicos

Este es un juego para un solo jugador (usted y sus colegas no querían mezclar las poblaciones, por lo que cada uno construyó su propia pista de carreras). La pista de carreras es una cuadrícula rectangular, 15 celdas de alto y 50 celdas de ancho. Comienza con 15 muestras en celdas aleatorias (no necesariamente distintas) en el borde izquierdo (donde x = 0 ). Sus muestras deben tratar de alcanzar la meta que es cualquier celda en x ≥ 49 y 0 ≤ y ≤ 14 (las muestras pueden sobrepasar la pista a la derecha). Cada vez que esto sucede, obtienes un punto. También comienzas el juego con 1 punto. Debes intentar maximizar tus puntos después de 10,000 turnos.

Varias muestras pueden ocupar la misma celda y no interactuarán.

En cada turno, cada espécimen ve una cuadrícula de 5x5 de su entorno (consigo mismo en el centro). Cada celda de esa cuadrícula contendrá un color -1para 15. -1representa celdas que están fuera de los límites. Su espécimen muere si se sale de los límites. En cuanto a los otros colores, representan celdas vacías, trampas, paredes y teletransportadores. Pero su espécimen no sabe qué color representa qué y usted tampoco. Sin embargo, hay algunas limitaciones:

  • 8 colores representarán celdas vacías.
  • 4 colores representarán un teletransportador. Un teletransportador enviará el espécimen a cierta celda dentro de su vecindario 9x9. Este desplazamiento será el mismo para todos los teletransportadores del mismo color.
  • 2 colores representarán las paredes. Entrar en una pared es lo mismo que quedarse quieto.
  • 2 colores representarán una trampa. Una trampa indica que una de las 9 celdas en su vecindad inmediata es letal (no necesariamente la celda de trampa en sí). Este desplazamiento será el mismo para todas las trampas del mismo color.

Ahora, sobre esa selección natural ... cada espécimen tiene un genoma, que es un número con 100 bits. Se crearán nuevos especímenes cruzando dos especímenes existentes y luego mutando ligeramente el genoma. Cuanto más exitoso es un espécimen, mayor es la posibilidad de reproducción.

Así que aquí está tu tarea: escribirás una sola función, que recibe como entrada la cuadrícula de colores de 5x5 que ve un espécimen, así como su genoma. Su función devolverá un movimiento (Δx, Δy) para la muestra, donde Δx y Δy serán cada uno de ellos {-1, 0, 1}. No debe persistir ningún dato entre llamadas a funciones. Esto incluye el uso de sus propios generadores de números aleatorios. Su función se proporcionará con un RNG sembrado que puede usar libremente como desee.

La puntuación de su envío será la media geométrica del número de puntos en 50 pistas aleatorias. Hemos encontrado que este puntaje está sujeto a un poco de variación. Por lo tanto, estos puntajes serán preliminares . Una vez que este desafío desaparezca, se anunciará una fecha límite. Al final de la fecha límite, se elegirán 100 tableros al azar, y todas las presentaciones se volverán a calificar en estos 100 tableros. Siéntase libre de poner un puntaje estimado en su respuesta, pero nosotros calificaremos cada envío para asegurarnos de que nadie haga trampa.

Hemos proporcionado programas de controlador en un puñado de idiomas. Actualmente, puede escribir su envío en Python (2 o 3), Ruby , C ++ , C # o Java . El controlador genera los tableros, ejecuta el juego y proporciona un marco para el algoritmo genético. Todo lo que tiene que hacer es proporcionar la función de movimiento.

Espera, ¿qué hago exactamente con el genoma?

¡El desafío es resolver eso!

Como los especímenes no tienen memoria, todo lo que tienes en un turno dado es una cuadrícula de colores 5x5 que no significa nada para ti. Entonces tendrás que usar el genoma para alcanzar la meta. La idea general es que use partes del genoma para almacenar información sobre los colores o el diseño de la cuadrícula, y su bot basa sus decisiones en la información adicional almacenada en el genoma.

Ahora, por supuesto, no puedes almacenar nada allí manualmente. Entonces, la información real almacenada allí inicialmente será completamente aleatoria. Pero el algoritmo genético pronto seleccionará aquellos especímenes cuyo genoma contenga la información correcta y eliminará aquellos que tengan la información incorrecta. Su objetivo es encontrar un mapeo de los bits del genoma y su campo de visión a un movimiento, lo que le permite encontrar un camino hacia la meta rápidamente y que evoluciona constantemente hacia una estrategia ganadora.

Esto debería ser suficiente información para comenzar. Si lo desea, puede omitir la siguiente sección y seleccionar su controlador de elección de la lista de controladores en la parte inferior (que también contiene información sobre cómo usar ese controlador en particular).

Sigue leyendo si quieres todo ...

Los detalles sangrientos

Esta especificación está completa. Todos los controladores tienen que implementar estas reglas.

Toda aleatoriedad utiliza una distribución uniforme, a menos que se indique lo contrario.

Generación de pistas:

  • La pista es una cuadrícula rectangular, X = 53 celdas de ancho e Y = 15 celdas de alto. Las celdas con x ≥ 49 son celdas objetivo (donde x está basado en cero).
  • Cada celda tiene un solo color y puede o no ser letal : las celdas no son letales a menos que se especifique por uno de los tipos de celdas a continuación.
  • Hay 16 colores de celda diferentes, etiquetados de 0a 15, cuyo significado cambiará de un juego a otro. Además, -1representa celdas que están fuera de los límites: estas son letales .
  • Elige 8 colores al azar . Estas serán celdas vacías (que no tienen efecto).
  • Elige 4 colores más al azar . Estos son teletransportadores. Para dos de estos colores, elija un desplazamiento distinto de cero en la vecindad 9x9 (de (-4, -4) a (4,4) excepto (0,0)). Para los otros dos colores, invierta esos desplazamientos. Si un espécimen pisa un teletransportador, ese desplazamiento lo mueve inmediatamente.
  • Elige 2 colores más al azar . Estas son trampas. Para cada uno de estos colores, elija un desplazamiento en el vecindario 3x3 (de (-1, -1) a (1,1)). Una trampa indica que la celda en ese desplazamiento es letal . Nota: La celda trampa no es necesariamente letal.
  • Los 2 colores restantes son paredes, que impiden el movimiento. Intentar pasar a una celda de pared convertirá el movimiento en quedarse quieto. Las células de la pared son letales .
  • Para cada celda sin objetivo de la cuadrícula, elija un color aleatorio. Para cada celda objetivo, elija un color vacío aleatorio .
  • Para cada celda en el borde izquierdo de la pista, determine si se puede alcanzar el objetivo dentro de los 100 turnos (de acuerdo con las reglas de orden de turno a continuación). Si es así, esta celda es una celda inicial admisible . Si hay menos de 10 celdas iniciales, descarte la pista y genere una nueva.
  • Cree 15 especímenes, cada uno con un genoma aleatorio y edad 0 . Coloque cada muestra en una celda inicial aleatoria.

Orden de giro:

  1. Se realizarán los siguientes pasos, en orden, para cada muestra. Las muestras no interactúan ni se ven, y pueden ocupar la misma celda.
    1. Si la edad del espécimen es de 100 años , muere. De lo contrario, incremente su antigüedad en 1.
    2. Al espécimen se le da su campo de visión, una cuadrícula de colores de 5x5, centrada en el espécimen, y devuelve un movimiento en su vecindario de 3x3. Los movimientos fuera de este rango harán que el controlador termine.
    3. Si la celda objetivo es un muro, entonces el movimiento se cambia a (0,0).
    4. Si la celda objetivo es un teletransportador, la muestra se mueve por el desplazamiento del teletransportador. Nota: Este paso se realiza una vez , no de forma iterativa.
    5. Si la celda actualmente ocupada por la muestra (potencialmente después de usar un teletransportador) es letal, la muestra muere. Este es el único momento en que mueren las muestras (aparte del paso 1.1. Anterior). En particular, un nuevo espécimen que se genera en una célula letal no morirá de inmediato, pero tiene la oportunidad de salir de la célula peligrosa primero.
    6. Si el espécimen ocupa una celda objetivo, anote un punto, mueva el espécimen a una celda inicial aleatoria y restablezca su edad a 0.
  2. Si quedan menos de dos especímenes en el tablero, el juego termina.
  3. Crea 10 nuevos especímenes con edad 0 . Cada genoma está determinado (individualmente) por las siguientes reglas de reproducción. Coloque cada muestra en una celda inicial aleatoria.

Cría:

  • Cuando se crea un nuevo espécimen, elija dos padres distintos al azar, con un sesgo hacia los especímenes que han progresado más hacia la derecha. La probabilidad de que se elija un espécimen es proporcional a su puntaje actual de aptitud . El puntaje de aptitud física de un espécimen es

    1 + x + 50 * número de veces que alcanzó la meta

    donde x es el índice horizontal basado en 0. Las muestras creadas en el mismo turno no se pueden elegir como padres.

  • De los dos padres, elija uno aleatorio para tomar el primer bit del genoma.

  • Ahora, a medida que camina por el genoma, cambie de padres con una probabilidad de 0.05 y continúe tomando fragmentos del padre resultante.
  • Muta el genoma completamente ensamblado: para cada bit, voltéalo con probabilidad 0.01 .

Puntuación:

  • Un juego dura 10,000 turnos.
  • Los jugadores comienzan el juego con 1 punto (para permitir el uso de la media geométrica).
  • Cada vez que un espécimen alcanza la meta, el jugador anota un punto.
  • Por ahora, la presentación de cada jugador se ejecutará durante 50 juegos, cada uno con una pista aleatoria diferente.
  • El enfoque anterior da como resultado más varianza de la que es deseable. Una vez que este desafío desaparezca, se anunciará una fecha límite. Al final de la fecha límite, se elegirán 100 tableros al azar, y todas las presentaciones se volverán a calificar en estos 100 tableros.
  • El puntaje general de un jugador es la media geométrica de los puntajes de estos juegos individuales.

Los controladores

Puede elegir cualquiera de los siguientes controladores (ya que son funcionalmente equivalentes). Los hemos probado todos, pero si detecta un error, desea mejorar el código o el rendimiento, o agregar una característica como salida gráfica, envíe un problema o envíe una solicitud de extracción en GitHub. ¡También puedes agregar un nuevo controlador en otro idioma!

Haga clic en el nombre del idioma de cada controlador para acceder al directorio correcto en GitHub, que contiene README.mdinstrucciones de uso exactas.

Si no está familiarizado con git y / o GitHub, puede descargar todo el repositorio como un ZIP desde la página principal (vea el botón en la barra lateral).

Pitón

  • Más a fondo probado. Esta es nuestra implementación de referencia.
  • ¡Funciona con Python 2.6+ y Python 3.2+!
  • Es muy lento. Recomendamos ejecutarlo con PyPy para una aceleración sustancial.
  • Admite salida gráfica usando pygameo tkinter.

Rubí

  • Probado con Ruby 2.0.0. Debería funcionar con versiones más nuevas.
  • También es bastante lento, pero Ruby puede ser conveniente para crear prototipos de una idea para una presentación.

C ++

  • Requiere C ++ 11.
  • Opcionalmente admite subprocesos múltiples.
  • De lejos, el controlador más rápido del grupo.

C#

  • Utiliza LINQ, por lo que requiere .NET 3.5.
  • Bastante lento.

Java

  • No particularmente lento. No particularmente rápido.

Tabla de clasificación preliminar

Todos los puntajes son preliminares. Sin embargo, si algo está simplemente mal o desactualizado, avíseme. Nuestro envío de ejemplo está en la lista para comparación, pero no en contienda.

  Score   | # Games | User               | Language   | Bot           
===================================================================================
2914.13   |   2000  | kuroi neko         | C++        | Hard Believers
1817.05097|   1000  | TheBestOne         | Java       | Running Star
1009.72   |   2000  | kuroi neko         | C++        | Blind faith
 782.18   |   2000  | MT0                | C++        | Cautious Specimens
 428.38   |         | user2487951        | Python     | NeighborsOfNeighbors
 145.35   |   2000  | Wouter ibens       | C++        | Triple Score
 133.2    |         | Anton              | C++        | StarPlayer
 122.92   |         | Dominik Müller     | Python     | SkyWalker
  89.90   |         | aschmack           | C++        | LookAheadPlayer
  74.7    |         | bitpwner           | C++        | ColorFarSeeker
  70.98   |   2000  | Ceribia            | C++        | WallGuesser
  50.35   |         | feersum            | C++        | Run-Bonus Player
  35.85   |         | Zgarb              | C++        | Pathfinder
 (34.45)  |   5000  | Martin Büttner     | <all>      | ColorScorePlayer
   9.77   |         | DenDenDo           | C++        | SlowAndSteady
   3.7    |         | flawr              | Java       | IAmARobotPlayer
   1.9    |         | trichoplax         | Python     | Bishop
   1.04   |   2000  | fluffy             | C++        | Gray-Color Lookahead

Créditos

Este desafío fue un gran esfuerzo de colaboración:

  • Nathan Merril: Escribió controladores de Python y Java. Convirtió el concepto de desafío de un rey de la colina en una carrera de ratas.
  • trichoplax: Playtesting . Trabajó en el controlador Python.
  • feersum: escribió el controlador C ++.
  • VisualMelon: escribió el controlador C #.
  • Martin Büttner: Concepto. Escribió el controlador Ruby. Pruebas de juego. Trabajó en el controlador Python.
  • T Abraham: Pruebas de juego. Probé Python y revisé el controlador C # y C ++.

Todos los usuarios anteriores (y probablemente un par más que olvidé) han contribuido al diseño general del desafío.

Actualización del controlador C ++

Si está utilizando C ++ con Visual Studio y subprocesos múltiples, debería obtener la última actualización debido a un error con su generación de generador de números aleatorios que permite la producción de tableros duplicados.

Martin Ender
fuente
3
¿No podría alguien hacer un algoritmo genético genético para encontrar el algoritmo genético óptimo para este problema?
mbomb007
1
@ anon3202 Bueno, eso, por supuesto, le daría más información sobre el diseño de la pista, ya que podría evaluar dónde se encuentra. Esencialmente, queríamos mantener la interfaz para bots simple y convertirla en un problema puramente local, donde necesitará el genoma para saber qué solución local es más beneficiosa para su progreso global.
Martin Ender
1
@matovitch Consulte la sección 5 de la sección Orden de giro de los Detalles 'In particular, a new specimen which spawns on a lethal cell will not die immediately, but has a chance to move off the dangerous cell first.'
sangrientos
1
Modifiqué el código de C ++ para mostrar la media de muestra, stddev, stderr y el intervalo de conf del 99% (antes de su registro / exp "geométrico") e hice un descubrimiento sorprendente. La respuesta de "Fe ciega" tenía "Media muestral de 116529 + - 2.78337e + 010 (99%) stddev = 7.77951e + 010" después de 50 carreras ". Caer el intervalo de confianza al 50% no mejora notablemente las cosas. Sin embargo, la media geométrica fue más estable: "Media de 159.458 + - 117262 (99%) stddev = 32.6237" (Antes de su actualización de 800 puntajes)
Mooing Duck
1
Hice algunos experimentos con la tasa de mutación, y creo que el desafío sería más interesante (y los controladores funcionarían mucho más rápido) si la probabilidad aumentara de .01 a .0227, lo que le da a un ADN solo un 10% de posibilidades de pasar mutación sin cambios en lugar de 37% con el valor actual. Esto evita explosiones de población ridículas (lo que a su vez ahorra mucho tiempo de cálculo) y evita muchas fallas debido a la diversidad insuficiente. Los puntajes individuales son más bajos, pero dado que más carreras producen ganadores, el promedio mundial tiende a aumentar.

Respuestas:

37

La fe ciega - C ++ - parece anotar por encima de 800 (!) En 2000 carreras

Genoma de codificación de colores con una misteriosa respuesta de pista y un disuasivo eficaz para golpear la pared

#include "./gamelogic.cpp"

#define NUM_COLORS 16

// color meanings for our rats
typedef enum { good, bad, trap } colorType_t;
struct colorInfo_t {
    colorType_t type;
    coord_t offset; // trap relative location
    colorInfo_t() : type(good) {} // our rats are born optimists
};

// all 8 possible neighbours, carefully ordered
coord_t moves_up  [] = { { 1, 0 }, { 1,  1 }, { 1, -1 }, { 0,  1 }, { 0, -1 }, { -1, 0 }, { -1,  1 }, { -1, -1 } };  // toward the goal, going up   first
coord_t moves_down[] = { { 1, 0 }, { 1, -1 }, { 1,  1 }, { 0, -1 }, { 0,  1 }, { -1, 0 }, { -1, -1 }, { -1,  1 } };  // toward the goal, going down first

// map of the surroundings
struct map_t {
    static const size_t size = 5;
    static const int max = size / 2;
    static const int min = -max;
    colorType_t map[size*size];
    colorType_t & operator() (int x, int y) { return map[(x + max)*size + y + max]; }
    colorType_t & operator() (coord_t pos) { return operator()(pos.x, pos.y); }
    bool is_inside(int x, int y) { return abs(x) <= max && abs(y) <= max; }
    bool is_inside(coord_t pos) { return is_inside(pos.x,pos.y); }
};

// trap mapping info
struct trap_t {
    coord_t detector;
    colorInfo_t color;
    trap_t(int x, int y, colorInfo_t & color) : color(color) { detector.x = x; detector.y = y; }
    trap_t() {}
};

coord_t blindFaith(dna_t d, view_t v)
{
    colorInfo_t color[NUM_COLORS]; // color informations

    // decode colors
    for (size_t c = 0; c != 16; c++)
    {
        size_t base = c * 4;
        if (d[base])
        {
            color[c].type = d[base+1] ? good : bad;
        }
        else // decode trap location
        {
            color[c].type = trap;
            int offset = d[base+1] + 2 * d[base+2] + 4 * d[base+3];
            color[c].offset = moves_up[offset]; // the order is irrelevant as long as all 8 neighbours are listed
        }
    }

    // build a map of the surrounding cells
    map_t map;
    unsigned signature = 0;
    int i = 0;
    for (int x = map.min; x <= map.max; x++)
    for (int y = map.min; y <= map.max; y++)
    {
        int c = v(x, y);
        map(x, y) = (c == -1) ? bad : color[c].type;
        if (c != -1) signature ^= v(x, y) << ((i++) % 28);
    }

    // map traps
    for (int x = map.min; x <= map.max; x++)
    for (int y = map.min; y <= map.max; y++)
    {
        if (map(x, y) != trap) continue;
        const colorInfo_t & trap = color[v(x, y)];
        int bad_x = x + trap.offset.x;
        int bad_y = y + trap.offset.y;
        if (!map.is_inside(bad_x, bad_y)) continue;
        map(bad_x, bad_y) = bad;
        map(x, y) = good;
    }

    // pick a vertical direction according to surroundings signature
    int go_up = d[64 + signature % (DNA_BITS - 64)];

    // try to move to a good cell nearer the goal
    for (const coord_t &move : go_up ? moves_up : moves_down) if (map(move.x, move.y) == good) return move;

    // try not to increase fitness of this intellectually impaired specimen
    return{ -1, 0 };
}

int main() {
    time_t start = time(NULL);
    double score = runsimulation(blindFaith);
    slog << "Geometric mean score: " << score << " in " << time(NULL) - start << " seconds";
}

Resultados de muestra:

Scores: 15 4113306 190703 1 1 44629 118172 43594 63023 2 4 1 1 205027 1 455951 4194047 1 5 279 1 3863570 616483 17797 42584 1 37442 1 37 1 432545 5 94335 1 1 187036 1 4233379 1561445 1 1 1 1 35246 1 150154 1 1 1 1 90141 6 1 1 1 26849 1 161903 4 123972 1 55 988 7042063 694 4711342 90514 3726251 2 1 383389 1 593029 12088 1 149779 69144 21218 290963 17829 1072904 368771 84 872958 30456 133784 4843896 1 2 37 381780 14 540066 3046713 12 5 1 92181 5174 1 156292 13 1 1 29940 66678 125975 52714 1 5 3 1 101267 69003 1 1 10231 143110 282328 4 71750 324545 25 1 22 102414 1 3884626 4 28202 64057 1 1 1 1 70707 4078970 1623071 5047 1 1 549040 1 1 66 3520283 1 6035495 1 79773 1 1 1 218408 1 1 15 33 589875 310455 112274 1 1 4 1 3716220 14 180123 1 2 12785 113116 12 2 1 59286 822912 2244520 1840950 147151 1255115 1 49 2 182262 109717 2 9 1049697 59297 1 11 64568 1 57093 52588 63990 331081 54110 1 1 1537 3 38043 1514692 360087 1 260395 19557 3583536 1 4 152302 2636569 12 1 105991 374793 14 3934727 1 2 182614 1 1675472 121949 11 5 283271 207686 175468 1 1 173240 1 138778 1 1 59964 3290382 1 4 1757946 1 23520 1 2 94 1 124577 497071 1749760 39238 1 301144 3 1 2871836 1 1 10486 1 11 8 1 111421 11 1807900 1 587479 1 42725 116006 3 1 6 5441895 1 1 22 52465 952 1 18 1 1 46878 2 1 1 1994 4 593858 123513 4692516 820868 4247357 1 1 2 1 2 8770 2 1 95371 4897243 2 22741 1 1 1 1 325142 6 33650 4 51 102993 1 182664 1 4040608 18153 2045673 462339 1 1 617575 2 2551800 3 7760 1 108012 76167 143362 1148457 1 53460 1 71503 1 1 1 1 81482 3208 62286 69 139 1 3503941 1 253624 101903 3081954 80123 84701 9 16 1 1070688 71604 613064 2076 15009 9 1 1 1 199731 1 2 1 63132 1 1843855 27808 1 3569689 273144 1 460524 2703719 22443 10876 51242 1 6972678 4591939 1 140506 43981 45076 2 1 91301 5 1 1874615 1758284 608 13 1 96545 75161 1 618144 4 2056133 1 1 2 57401 1394307 6 188116 83545 1 41883 1 1 467189 371722 1 1122993 1 17912 159499 1 5 3355398 33 1 2 246304 1 2 168349 1 50292 12 141492 2723076 3 1 6 3060433 223360 171472 106409 1 2 1 102729 8814 1 285154 1 11 1 65 930 2 689644 3271116 1 5 4 60 77447 1 1 1477538 256023 100403 2480335 1 39888 1 1 70052 66090 1 250 1 2 8 115371 1523106 1424 168148 1 1 1 42938 17 1 364285 185080 1 1 36 4903764 13 51987 1106 276212 67460 1 251257 2 6867732 1 1 1890073 1 1 8 5 2118932 210 0 3792346 5209168 1 1 1 1 51 1 4621148 1 37 337073 3506096 1 1 1 1 458964 2 16 52930 1 15375 267685 1 1 1259646 14930 3248678 527105 1 103 24 1 3252685 6009 1 1 176340 3971529 121 1722808 1 31483 194232 2314706 95952 3625407 3 216755 56 1 8 1 1 1 1 885 229 9056 172027 31516 2526805 1 76076 1589061 1 1 8 90812 1 21 72036 1681271 2 212431 1581814 85993 79967 4 7 514708 1070070 1 71698 1 23478 15882 94453 1 27382 495493 277308 12127 91928 248593 1 1 1 26540 1709344 2119856 1 1 48867 107017 251374 64041 15924 15 87474 8 1 23 9 48 1 1 1 51793 2 61029 84803 15 689851 1 1 873503 10 140084 420034 87087 82223 1 163273 12 1 5 570463 19 26665 1 170311 1 39983 1 475306 1 2 36417 746105 11 141345 1 3 1 30 3 1 1 1 1 1312289 408117 1 42210 273871 561592 1 1 1 1 4448568 48448 7 378508 1 351858 278331 1 79515 1169309 3670107 14711 4686395 1156554 33 2528441 24537 76 335390 63545 122108 76675 21929 34 1 861361 83000 417781 1 90487 1 1 85116 7 2 1 60129 647991 79 1 2755780 726845 244217 50007 187212 1 3674051 286071 44068 3 307427 26973 1 26059 1957457 230783 58102 545318 1 4 172542 168365 1 89402 1 4 1 1 1 1 2 3 16 62935 5643183 117961 109942 85762 5 117376 118883 1 61 23893 122536 70185 1 64252 208409 179269 55381 1579240 3434491 1 4964284 3356245 3 21 2197119 346542 44340 59976 772220 5590844 199721 90858 63785 125989 57219 129737 81836 1 3671 16810 1 4151040 1 15 40108 1 443679 3224921 2 27498 2 3 146529 169409 19 1 1 1 1 41627 1 3 2722438 1 2013730 1 1649406 1 1 6943 125772 58652 1 1 1 2413522 1 2 48 36067 253807 2 146464 1 248 07 3359223 139896 395985 65241 43988 594638 69033 275085 1 17973 1 1 1 594835 1 1 4468341 3496274 222854 94769 55 161056 36185 8793 277592 3 1 6746 1 138151 66 37365 1 2729315 1 3 57091 22408 249875 246514 85058 1 20 5463152 1 3 1 45293 1 70488 2792458 461 441 951926 2236205 2 171980 1 1 48 3893009 1 458077 1 268203 1 70005 7 19299 1 278978 1 45286 26 2 1883506 274393 342679 1 1 913722 911600 12688 1 1 115020 1249307 1529878 53426 1 226862 3721440 23537 86033 397433 1 1 1 161423 96343 94496 1 1 1 2 1 111576 1 4039782 1 1 1 5742393 3569 46072 1 1 2 1 1 85335 219988 1 78871 115876 43405 1 300835 1 166684 53134 1 3 111487 6 3 3 77 1 115971 3 205782 10 1932578 356857 43258 47998 1 27648 127096 573939 32650 523906 45193 1 2 128992 1 10144 1 257941 1 19841 5077836 14670 5 3 6 1 1 21 14651 2906084 37942 45032 9 304192 3035905 6214026 2 177952 1 51338 1 65594 46426 553875 2676479 245774 95881 3 216364 3064811 1198509 223982 3 6 1 533254 1 590363 264940 68346 127284 1 7 1 1 4617874 5 45400 1 1 3097950 360274 1 3 1 8421 14 469681 418563 3 1 6 1 1 575766 405239 11 2631108 152667 1 1 1 467383 1 1 775499 1 157998 2 1 143351 92021 1 1 1173046 3636579 1 70635 162303 1 1534876 834682 2 1 1 11981 346908 245124 607794 17 1570641 126995 13 57050 1 2 33731 29739 1 1 35460 1 33716 168190 214704 1 443156 701674 2636870 108081 1604895 1 1 11 115901 23 571891 360680 1 1 35 1 2036975 1 1 2555536 4742615 5 360553 287044 1 1814255 7 59632 1 216 41546 1 540920 353424 2625301 223744 1 1 1 15717 3 429871 1 4 2329632 18 11 1 2 4 1 3905 5 1 1 1 2 5431442 1 859628 1 3 338378 15236 13764 1 3384362 1 15 65293 24 619599 152620 2 189921 35854 16647 7 2 404790 360096 1 2 189459 1097768 191610 1 1 470254 1 12 2 330299 364219 2365542 312023 2273374 2 10527 1 115453 1 2 3845592 52388 913449 1 14695 1 44 37352 90302 1 1 1 233577 51639 3474983 44010 1650727 31 2 2 1 8 7 1 3 5 25603 17799 45630 758457 1 4571839 37 4 3 2 1 1 1351271 196673 12 2880765 263886 2926173 1 2 1 241502 5 6 1 278576 9 7 290722 42749 143391 82753 21771 57887 1 1 60400 1766903 1 296392 1 5 2861787 125560 1 9 199218 1 1 308226 517598 2246753 12 1168981 3 98447 1 488613 9 842865 202108 10 1 238493 1 1523706 5383982 29435 1 1 207071 1 8 4 125742 70531 253135 72207 124291 23364 184376 2 40034 9569353 194109 102854 2 3247153 58313 85995 1 598 63 1 2676692 10 3573233 1 36651 118016 2486962 65456 46760 1 5813 723 178120 2 153305 1 1 2 1 2354413 3 1 17126 132953 437123 299778 3070490 1 6490 403704 2261 511439 1 39 33410 173045 1 1 120970 641346 132042 1 44906 1 33940 132124 467702 45472 9 44 1 1 1 107008 1 46635 1 121431 130760 1 7 3 1 56251 1299306 3 1 1 1 15 2147678 215169 1374943 1 332995 231089 269310 1 7816944 1 1 1 46 134426 1 1 1 2 76112 1 1 30438 299927 25 139373 76048 278757 71 3474997 1 294046 1 3126554 2518019 2 1 6 1 3054393 1 1 1 2 525 96 419528 1 1 154718 233 207879 26 1 6 57436 3 5944942 1 1 318198 147536 1 22 420557 1 1 120938 1 1 167412 4082969 73299 1 11 3557361 1 4 330028 269051 1 2569546 2 1 1 4 1 1 377412 1 1 1 213800 58131 1422177 54 109617 117751 12432 3830664 419046 3 6821 741 919 1 22335 1 1 15069 80694 488809 2389 2308679 145548 51411 115786 110984 107713 1 12 6 1 5 8365 1 2001874 210250 4674015 14 1 1204101 314354 89066 1 1 2438200 68350 1 1575329 5593838 2743787 151670 57 16 5948210 597158 128060 189160 23628 1 1 15 4171774 1 8206 4157492 1 2 315607 1618680 24736 18520 4787225 33842 134431 1 1 1 1 1 1115809 17759 1 33016 123117 1 77322 169633 219091 1 321593 57231 135536 175401 4 1 435702 1 253132 100707 114547 1 119324 6382967 1472898 3 72567 1707408 177958 26 208719 1 27083 74 12 576410 19375 177069 4 3 1 31 507048 2 1 1 2 1 2 1 40 7 99892 95202 60649 241396 232370 1 136579 70649 1 2877 280695 13603 102860 404583 29717 112769 1 54089 1 97579 40819 2 868629 64848 2 63432 5 1 1888426 99623 2 1 7911 53646 3047637 1 2 3 152910 1 3244662 105187 1 1 1 1 8966 200347 1 1 22 302654 6 17 1 10 328150 55259 1016 117291 2 1 224524 23846 74645 1 1 1 1 1 3117394 10847 33976 144613 4 201584 1 1 26959 3 4410588 27019 6 66749 55935 23 4126812 4089989 99959 1 1 1 1 55490 1 4275599 13652 33967 2 8126062 337093 320653 128015 4 1 7729132 1 10594 116651 20990 3046630 1 353731 132989 2066431 4 80 15575 147430 1 621461 3100943 2306122 5 33439 407945 25634 1 2911806 32511 2174235 298281 15159 54125 1 2 3063577 2205013 1 407984 1 319713 1 22171 1 2763843 1 2607606 1 100015 3096036 1 55905 1 1 635265 2890760 1 1 1 1 35854 1 352022 2652014 1 2 274366 1 4 1 602980 4 83828 602270 2816 2 59116 25340 1 11 1 5162051 34 8 218372 1186732 142966 1 1 170557 503302 1 84924 5 1 1350329 1 1 1 130273 78055 902762 1 8581 5 1 3635882 1 1 1 224255 44044 61250 2 438453 8 1 2729357 28 1 17658 82640 1 31809 10 1 33 1 1 45495 5798 5000217 40018 588787 67269 1 12 83512 2798339 1 609271 1 3 1 7 67912 189808 3388775 60961 81311 1167 24939 433791 405306 85934 1 1170651 2 1 66 552579 122985 515363 2188340 1 1 1 3807012 1502582 4 13 149593 1 1 2108196 3 34279 24613 1282047 27 1 2 1 1 584435 27487 1 1 5 33278 1 1 1202843 1 1 1 6 3649820 3100 2 266150 13 164117 10 53163 3295075 1 1 1 1 77890 1 286220 90823 18866 3139039 481826 1 3994676 23 116901 132290 6 3927 84948 1 1 1 1 256310 1 11 8 1 102002 8392 887732 98483 444991 1 1 49408 409967 1158979 1 1 1 81469 189764 3960930 296231 64258 1 1 176030 4 1 2 1 486856 1 1135146 31 2 13112 227077 31
Geometric mean score: 831.185 in 14820 seconds

Basado en la prueba involuntariamente larga de feersum, creo que 2000 carreras son suficientes para producir un resultado aceptablemente estable.
Como mi controlador modificado muestra la media geométrica actual después de cada ejecución, confirme visualmente que la variación en las últimas 50 ejecuciones fue relativamente pequeña (+ - 10 puntos).

Lo que hace que estos bichos funcionen

En lugar de dar prioridades iguales a cada color, considero estos valores posibles:

  1. bien -> la rata cree que puede ir a salvo allí
  2. mal -> la rata no irá allí
  3. trampa -> la rata considerará que la posición de la trampa es mala y que la celda indica que la trampa es buena .
    Aunque soy demasiado vago para cambiarle el nombre, esto es más bien un "detector de peligro" que indica la ubicación (supuesta) de una trampa real, una pared, un teletransportador esperando enviar al vagabundo desprevenido a un lugar desagradable o incluso la entrada de un muerto -fin. En resumen, un lugar donde una rata sabia preferiría no ir.

Los genes buenos o malos solo requieren 2 bits para almacenar (por ejemplo 11y 10), pero las trampas requieren 4 bits ( 0tttdonde tttrepresenta una de las 8 posibles ubicaciones "peligrosas").

Para mantener cada gen consistente (es decir, que conserva su significado después sido mezclados en un genoma completamente diferente, que requiere que cada gen de codificación por colores para estar en una ubicación fija), todos los valores se codifican en 4 bits (por lo bueno se codifica como 11xxy mala como 10xx), para un total de 16 * 4 = 64 bits.

Los 36 bits restantes se usan como "anti-wall-bangers" (más sobre eso más adelante). Los 25 colores circundantes se combinan en un índice de estos 36 bits. Cada bit indica una dirección vertical preferida (arriba o abajo), que se utiliza cuando hay una posible elección entre dos celdas.

La estrategia es la siguiente:

  • decodifique cada color de acuerdo con el genoma (o informe directo del controlador para células "malas" fuera de la pista)
  • construir un mapa de los alrededores inmediatos (3x3 celdas, 8 posibles vecinos)
  • calcular una firma de los alrededores (un hash de los 25 colores, excepto las celdas fuera de pista)
  • Elija una dirección vertical preferida de la firma (entre 36 cubos hash)
  • trate de moverse hacia un vecino insinuado como "bueno", comenzando con los más cercanos a la meta y yendo primero en la dirección vertical preferida
  • Si no se puede encontrar un vecino "bueno", intente mover una celda hacia atrás (por lo tanto, posiblemente sea víctima de un desafortunado accidente y evite aumentar el estado físico en cualquier caso)

Roedores, he aquí los enemigos de tu clase.

el temido muro bucle de teletransportación

Lo peor que le puede pasar a una población es no haber producido ningún ganador todavía, pero muchas ratas se pegaron contra una pared o dentro de un bucle infinito de teletransportación lo suficientemente cerca del objetivo para tener una oportunidad dominante de ser seleccionado para la cría .
A diferencia de las ratas que son aplastadas en una trampa o teletransportadas a las paredes, estos roedores solo serán asesinados por la vejez.
No tienen una ventaja competitiva sobre sus primos atascados en 3 células desde el principio, pero tendrán tiempo suficiente para reproducirse generación tras generación de cretinas hasta que su genoma se vuelva dominante, dañando así la diversidad genética sin ninguna buena razón.

Para mitigar este fenómeno, la idea es hacer que los descendientes de estas ratas malas y malas tengan más probabilidades de evitar seguir los pasos de su ascendencia.
La indicación de dirección vertical es de solo 1 bit de largo (básicamente diciendo "intente subir o bajar primero en este entorno"), y es probable que bastantes bits tengan un efecto en el camino seguido, por lo que las mutaciones y / o cruces deberían tener un Impacto significativo.
Muchas de las crías tendrán un comportamiento diferente y no terminarán golpeándose la cabeza contra la misma pared (entre los cadáveres de sus ancestros hambrientos).
Lo importante aquí es que esta indicación no es el factor dominante en el comportamiento de la rata. La interpretación del color seguirá prevaleciendo en la mayoría de los casos (la opción arriba / abajo solo importará si de hecho hay dos "buenas"y lo que la rata ve como un color inofensivo no es un teletransportador esperando para lanzarlo a la pared).

¿Por qué (parece) funcionar?

Todavía no sé exactamente por qué.

El golpe de suerte absoluto que sigue siendo un misterio sin resolver es la lógica de mapeo de trampas. Es sin duda la piedra angular del éxito, pero funciona de manera misteriosa.

Con la codificación utilizada, un genoma aleatorio producirá 25% de identificadores de color "buenos", 25% "malos" y 50% "trampa".
los identificadores de "trampa" a su vez producirán estimaciones "buenas" y "malas" en correlación con el entorno 5x5.
Como resultado, una rata en un lugar determinado "verá" el mundo como una mezcla de colores estables y contextuales "ir / no ir".

Como parece indicar el mecanismo anti-golpes bastante exitoso, el peor tipo de elemento en la pista es el muro temido (y su primo el bucle de teletransportación, pero supongo que estos son mucho menos comunes).

La conclusión es que un programa exitoso debe, sobre todo, lograr evolucionar ratas capaces de detectar posiciones que conduzcan a una inanición lenta sin alcanzar la meta.

Incluso sin "adivinar" los dos colores que representan las paredes, los colores de la "trampa" parecen contribuir a evitar la pared al permitir que una rata evite algunos obstáculos no porque "vio" las paredes, sino porque la estimación de la "trampa" descartó estos células de pared particulares en estos entornos particulares.

Aunque la rata intenta moverse hacia la meta (lo que podría llevar a pensar que los indicadores de trampa más "útiles" son los que indican un peligro en el frente), creo que todas las direcciones de la trampa tienen aproximadamente la misma influencia: una trampa que indica "peligro detrás" "2 celdas ubicadas frente a una rata tienen la misma influencia que una que indica" peligro por delante "cuando la rata se encuentra justo encima de ella.

Desafortunadamente, por qué esta mezcla tiene la propiedad de hacer que el genoma converja tan exitosamente está más allá de mis matemáticas.

Me siento más cómodo con el disuasivo para golpear la pared. Esto funcionó según lo planeado, aunque muy por encima de mis expectativas (el puntaje se multiplicó básicamente por cuatro).

Pirateé el controlador fuertemente para mostrar algunos datos. Aquí hay un par de carreras:

Turns:2499 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^v^^^v^vv^^v^^^ Max fitness: 790 Specimens: 1217 Score: 2800
Turns:4999 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^v^^^v^vv^^v^^^ Max fitness: 5217 Specimens: 15857 Score: 685986
Turns:7499 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^vvvvv^^v^v^^^^ Max fitness: 9785 Specimens: 31053 Score: 2695045
Turns:9999 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^vvvvv^^v^v^^^^ Max fitness: 14377 Specimens: 46384 Score: 6033904
Scored 6035495 in game 146 current mean 466.875

Aquí apareció una raza de súper rata temprano (la pista probablemente permitió correr en línea recta y alguna rata afortunada en las primeras generaciones tenía el ADN correcto para aprovecharla). El número de especímenes al final es aproximadamente la mitad del máximo teórico de unas 100.000 ratas, lo que significa que casi la mitad de las criaturas adquirieron la capacidad de sobrevivir a esta pista en particular indefinidamente (!).
Por supuesto, la puntuación resultante es simplemente obscena, por cierto, al igual que el tiempo de cálculo.

Turns:2499 best rat B  T0 G  B  T7 B  G  B  T6 T0 T3 B  G  G  G  T4 ^v^^^^^v^^v^v^^^^^^^^v^v^v^^vvv^v^^^ Max fitness: 18 Specimens: 772 Score: 1
Turns:4999 best rat T7 G  G  G  G  T7 G  B  T6 T0 T3 T5 G  G  B  T4 ^vvvvvvv^^^vvv^^v^v^^^^^^^^^^^^^v^^^ Max fitness: 26 Specimens: 856 Score: 1
Turns:7499 best rat G  T0 G  T3 G  T0 G  B  T6 T0 T2 B  T4 G  B  T4 ^^v^vvv^^^vv^^v^vvv^v^^vvvv^^^^^^^^^ Max fitness: 55 Specimens: 836 Score: 5
Turns:9999 best rat T6 T0 G  T5 B  T1 G  B  T6 T0 T3 B  T4 G  B  T4 ^^vv^^^^vv^^v^v^^v^^vvv^vv^vvv^^v^^v Max fitness: 590 Specimens: 1223 Score: 10478
Scored 10486 in game 258 current mean 628.564

Aquí podemos ver el refinamiento del genoma en el trabajo. El linaje entre los dos últimos genomas aparece claramente. Las buenas y malas evaluaciones son las más significativas. Las indicaciones de la trampa parecen oscilar hasta que se estabilizan en una trampa "útil" o mutan en buenas o malas .

Parece que los genes de color tienen algunas características útiles:

  • tienen un significado autónomo
    (un color específico debe ser manejado de una manera específica)
    Cada codificación de color puede ser arrojada a un genoma completamente diferente sin cambiar drásticamente el comportamiento, a menos que el color sea realmente decisivo (típicamente una pared o un teletransportador que conduce a un bucle infinito).
    Este es menos el caso con una codificación de prioridad básica, ya que el color más prioritario es la única información utilizada para decidir dónde moverse. Aquí todos los colores "buenos" son iguales, por lo que un color dado agregado a la lista "buena" tendrá menos impacto.
  • son relativamente resistentes a las mutaciones,
    la codificación buena / mala tiene solo 2 bits significativos de 4, y la ubicación de la trampa puede cambiarse la mayor parte del tiempo sin alterar significativamente el comportamiento de la rata.
  • son pequeños (4 bits), por lo que la probabilidad de ser destruido por un crossover es muy baja.
  • las mutaciones producen cambios significativos o inofensivos
    Un gen que muta a "bueno" tendrá poco efecto (si, por ejemplo, corresponde a una célula vacía, podría permitir encontrar un camino nuevo y más corto, pero eso también podría llevar a la rata directamente a una trampa), o una dramática (si el color representa una pared, es muy probable que la nueva rata se atasque en algún lugar).
    Un gen que cambia a "trampa" privará a la rata de un color esencial o no tendrá un efecto notable.
    Una mutación de una ubicación de trampa solo importará si de hecho hay una trampa (o algo dañino) por delante, lo que tiene una probabilidad relativamente pequeña (diría algo así como 1/3).

Por último, supongo que los últimos 36 bits contribuyen no solo a evitar que las ratas se atasquen, sino también a propagar las ratas de manera más uniforme en la pista, preservando así la diversidad genética hasta que emerge un genoma ganador y se vuelve dominante a través de la parte de codificación de colores.

Más trabajo

Debo decir que encuentro estos pequeños bichos fascinantes.
Gracias nuevamente a todos los contribuyentes a este excelente desafío.

Estoy pensando en cortar aún más el controlador para mostrar datos más significativos, como la ascendencia de una rata exitosa.

También me gustaría mucho ver a estas ratas en acción, pero este lenguaje C ++ b ** ch hace que crear, y mucho menos animar, imágenes (entre muchas otras cosas) sea una tarea desordenada.

Al final, me gustaría producir al menos una explicación del sistema de trampa y posiblemente mejorarlo.

Hack de controlador

Si alguien está interesado, puedo publicar las modificaciones que hice en el controlador.
Son sucios y baratos, pero hacen el trabajo.

No soy un experto en GitHub, por lo que tendría que pasar por una simple publicación.

Comunidad
fuente
16
Obtuve un puntaje de 208.14 con 10,000 juegos. Intenté probarlo por 1000, pero nunca me di cuenta de que había escrito un 0 adicional, por lo que me llevó más de 7 horas.
fiesta
LOL gracias de todos modos. En comparación con mis dos 1000 ejecuciones, parece que unas 2000 ejecuciones podrían producir un resultado estable en ese momento.
¿Qué ^^v^vvv^^^vv^^v^vvv^v^^vvvv^^^^^^^^^significas? El resto lo puedo adivinar, pero ¿estoy teniendo problemas con esa parte?
Mooing Duck
Estaba contemplando hacer un controlador de "depuración" por separado, que ejecuta una rata a la vez, y cada vez que se genera una nueva rata, muestra el ADN de los padres y el niño (a través de alguna función personalizable). Eso haría mucho más fácil examinar cómo funciona la rata.
Mooing Duck
2
eso representa los 36 bits indicadores "arriba / abajo", pero en estos ejemplos el ADN ganador ya se ha vuelto dominante, por lo que no varían mucho.
18

Duros creyentes - C ++ - (teletransportadores mejorados): 10.000+ para 2000 carreras

(esta es una evolución de la fe ciega , por lo que es posible que desee escalar otro muro de texto antes de este)

#ifndef NDEBUG
#define NDEBUG
#include "./gamelogic.cpp"
#endif // NDEBUG
#include <cassert>

#define NUM_COLORS 16
#define BITS_OFFSET  3
#define BITS_TYPE    2
#define BITS_SUBTYPE 2
#define BITS_COLOR (BITS_TYPE+BITS_OFFSET)

// how our rats see the world
typedef unsigned char enumSupport_t;
typedef unsigned char trapOffset_t;
typedef enum : enumSupport_t {
    danger,   // code      trap detector
    beam,     // code      safe teleporter
    empty,    // code      empty
    block,    // code      wall, pit or teleporter
    trap,     // computed  detected trap
    pit,      // read      off-board cell
} colorType_t;

// color type encoding (4 first bits of a color gene)
// the order is critical. A single block/empty inversion can cost 2000 points or more
const colorType_t type_decoder[16] = {
    /*00xx-*/
    danger,
    empty,
    beam,
    block,
    /*01xx-*/
    beam,
    danger,
    empty,
    block,
    /*10xx-*/
    empty,
    beam,
    block,
    danger,
    /*11xx-*/
    block,
    empty,
    danger,
    beam,
};

// all 8 possible neighbours, carefully ordered
typedef coord_t neighborhood_t[8];
neighborhood_t moves_up =   { { 1, 0 }, { 1,  1 }, { 1, -1 }, { 0,  1 }, { 0, -1 }, { -1, 0 }, { -1,  1 }, { -1, -1 } };  // toward the goal, going up   first
neighborhood_t moves_down = { { 1, 0 }, { 1, -1 }, { 1,  1 }, { 0, -1 }, { 0,  1 }, { -1, 0 }, { -1, -1 }, { -1,  1 } };  // toward the goal, going down first

// using C++ as a macro-assembler to speedup DNA reading
/*
Would work like a charm *if* a well-paid scatterbrain at Microsoft had not defined
std::bitset::operator[] as

bool operator[](size_t _Pos) const
{   // subscript nonmutable sequence
return (test(_Pos));
}

Bounds checking on operator[] violates the spec and defeats the optimization.
Not only does it an unwanted check; it also prevents inlining and thus generates
two levels of function calls where none are necessary.
The fix is trivial, but how long will it take for Microsoft to implement it, if
the bug ever makes it through their thick layer of tech support bullshit artists?
Just one of the many reasons why STL appears not to live up to the dreams of
Mr Stroustrup & friends...
*/
template<size_t BITS> int DNA_read(dna_t dna, size_t base)
{
    const size_t offset = BITS - 1;
    return (dna[base + offset] << offset) | DNA_read<offset>(dna, base);
}
template<> int DNA_read<0>(dna_t, size_t) { return 0; }

// color gene
struct colorGene_t {
    colorType_t  type;
    trapOffset_t offset;  // trap relative location
    colorGene_t() : type(empty) {} // our rats are born optimists
};

// decoded DNA
class dnaInfo_t {
private:
    const dna_t & dna;
    static const size_t
        direction_start = NUM_COLORS*(BITS_TYPE + BITS_OFFSET),
        direction_size = DNA_BITS - direction_start;

public:
    colorGene_t color[NUM_COLORS];
    int         up_down; // anti-wall-banger

    // decode constant informations during construction
    dnaInfo_t(const dna_t & d) : dna(d)
    {
        for (size_t c = 0; c != NUM_COLORS; c++)
        {
            unsigned raw = DNA_read<BITS_COLOR>(d, c * BITS_COLOR);
            color[c].type = type_decoder[raw >> 1];
            if      (color[c].type == danger) color[c].offset = raw & 7;
            else if (color[c].type == beam  ) color[c].offset = raw & 3;
        }
    }

    // update with surroundings signatures
    void update(size_t signature)
    {
        // anti-blocker
        up_down = (direction_size > 0) ? dna[direction_start + signature % direction_size] : 0;
    }
};

// map of the surroundings
class map_t {
    struct cell_t {
        coord_t pos;
        int     color;
    };

    static const size_t size = 5;
    static const int max = size / 2;
    static const int min = -max;

    size_t local_signature[size*size]; // 8 neighbours signatures for teleporters
    cell_t track_cell[size*size]; // on-track cells
    size_t cell_num;
    colorType_t map[size*size];
    size_t raw_index(int x, int y) { size_t res = x * size + y + max + max * size; assert(res < size*size); return res; }
    size_t raw_index(coord_t pos) { return raw_index(pos.x, pos.y); }

    bool is_inside(int x, int y) { return abs(x) <= max && abs(y) <= max; }

public:
    size_t compute_signatures(view_t v, dnaInfo_t genome)
    {
        cell_num = 0;
        size_t signature = 0;
        memset (local_signature, 0, sizeof(local_signature));
        int i = 0;
        for (int x = min; x <= max; x++)
        for (int y = min; y <= max; y++)
        {
            int c = v(x, y);
            if (c == -1)
            {
                (*this)(x, y) = pit; continue;
            }
            track_cell[cell_num++] = { { x, y }, c };
            signature ^= c << (4 * (i++ & 1));

            if (genome.color[c].type == beam)
            {
                int in = 0;
                for (coord_t n : moves_up)
                {
                    coord_t pn = {x+n.x,y+n.y};
                    if (!is_inside(pn)) continue;
                    int cn = v(pn.x, pn.y);
//                    if (cn == -1) continue;
                    local_signature[raw_index(pn.x,pn.y)] ^= cn << (4 * (in++ & 1));
                }
            }
        }
        return signature;
    }

    void build(dnaInfo_t genome)
    {
        coord_t traps[size*size];
        size_t t_num = 0;

        // plot color meanings
        for (size_t c = 0; c != cell_num; c++)
        {
            const cell_t& cell = track_cell[c];
            const colorGene_t& color = genome.color[cell.color];
            (*this)(cell.pos) = (color.type == beam && (local_signature[raw_index(cell.pos.x,cell.pos.y)] % 4) == color.offset)
                    ? block
                    : color.type;

            // build a list of trap locations
            if (color.type == danger)
            {
                coord_t location = cell.pos + moves_up[color.offset];
                if (is_inside(location)) traps[t_num++] = location;
            }
        }

        // plot trap locations
        while (t_num) (*this)(traps[--t_num]) = trap;
    }

    // quick & dirty pathing
    struct candidate_t {
        coord_t pos;
        candidate_t * parent;
        candidate_t() {} // default constructor does not waste time in initializations
        candidate_t(int) : parent(nullptr) { pos.x = pos.y = 0; } // ...this is ugly...
        candidate_t(coord_t pos, candidate_t * parent) : pos(pos), parent(parent) {} // ...but so much fun...
    };

    coord_t path(const neighborhood_t & moves)
    {
        candidate_t pool[size*size]; // private allocation for express garbage collection...
        size_t alloc;

        candidate_t * border[size*size]; // fixed-size FIFO 
        size_t head, tail;

        std::bitset<size*size>closed;

        // breadth first search. A* would be a huge overkill for 25 cells, and BFS is already slow enough.
        alloc = head = tail = 0;
        closed = 0;
        closed[raw_index(candidate_t(0).pos)] = 1;
        border[tail++] = new (&pool[alloc++]) candidate_t(0);
        while (tail > head)
        {
            candidate_t & candidate = *(border[head++]); // FIFO pop
            for (const coord_t move : moves)
            {
                coord_t new_pos = candidate.pos + move;
                if (is_inside(new_pos))
                {
                    size_t signature = raw_index(new_pos);
                    if (closed[signature]) continue;
                    closed[signature] = 1;
                    if ((*this)(new_pos) > empty) continue;
                    if (new_pos.x == 2) goto found_exit; // a path to some location 2 cells forward
                    assert(alloc < size*size);
                    assert(tail < size*size);
                    border[tail++] = new(&pool[alloc++]) candidate_t(new_pos, &candidate); // allocation & FIFO push
                    continue;
                }
                // a path out of the 5x5 grid, though not 2 cells forward
            found_exit:
                if (candidate.parent == nullptr) return move;
                candidate_t * origin;
                for (origin = &candidate; origin->parent->parent != nullptr; origin = origin->parent) {}
                return origin->pos;
            }
        }

        // no escape
        return moves[1]; // one cell forward, either up or down
    }

    colorType_t & operator() (int x, int y) { return map[raw_index(x, y)]; }
    colorType_t & operator() (coord_t pos) { return operator()(pos.x, pos.y); }
    bool is_inside(coord_t pos) { return is_inside(pos.x, pos.y); }
};

std::string trace_DNA(const dna_t d, bool graphics = false)
{
    std::ostringstream res;
    dnaInfo_t genome(d);
    for (size_t c = 0; c != NUM_COLORS; c++)
    {
        if (graphics)
        {
            res << "tbew--"[genome.color[c].type];
            if (genome.color[c].type == danger) res << ' ' << moves_up[genome.color[c].offset].x << ' ' << moves_up[genome.color[c].offset].y;
            if (genome.color[c].type == beam) res << ' ' << genome.color[c].offset << " 0";
            if (c != NUM_COLORS - 1) res << ',';
        }
        else switch (genome.color[c].type)
        {
        case danger: res << "01234567"[genome.color[c].offset]; break;
        case beam  : res <<     "ABCD"[genome.color[c].offset]; break;
        default: res << "!*-#X@"[genome.color[c].type]; break;
        }
    }
    return res.str();
}

coord_t hardBelievers(dna_t d, view_t v)
{
    dnaInfo_t genome(d); // decoded DNA
    map_t     map;       // the surroundings seen by this particular rodent

    // update genome with local context
    genome.update(map.compute_signatures(v, genome));

    // build a map of the surrounding cells
    map.build(genome);

    // move as far to the right as possible, in the contextually preffered direction
    return map.path(genome.up_down ? moves_up : moves_down);
}

int main() {
    time_t start = time(NULL);
    double score = runsimulation(hardBelievers, trace_DNA);
    slog << "Geometric mean score: " << score << " in " << time(NULL) - start << " seconds";
}

Episodio IV: orientarse en la red

Resultados

Scores: 309371 997080 1488635 1 19 45832 9 94637 2893543 210750 742386 1677242 206614 111809 1 1738598 1 1 342984 2868939 190484 3354458 568267 280796 1 1 1 679704 2858998 1 409584 3823 200724 1 973317 849609 3141119 1 1987305 1 1 57105 245412 1223244 2 1603915 2784761 9 12 1 1839136 1 298951 2 14 138989 501726 1365264 308185 707440 22 772719 17342 63461 3142044 19899 3 409837 48074 3549774 138770 32833 1 1 1184121 67473 310905 1996452 4201 1701954 2799895 2041559 218816 174 433010 51036 1731159 1871641 1 23 2877765 1 127305 27875 626814 142177 2101427 167548 2328741 4 8433 2674119 2990146 466684 1 2 8 83193 388542 2350563 1 1140807 100543 1313548 31949 73117 73300 121364 1899620 1280524 1 10726 12852 7 2165 1 3 44728 2 122725 41 2 1902290 3 1 8581 70598 1148129 429767 1 112335 1931563 521942 3513722 1 2400069 1 3331469 141319 220942 205616 57033 63515 34 6 1419147 1983123 1057929 1 599948 2730727 2438494 5586 268312 1728955 1183258 95241 1537803 11 13 1157309 1750630 1 1 2690947 101211 3463501 1 258589 101615 212924 137664 19624 251591 509429 510302 1878788 1 4045925 1 21598 459159 118663 7 3606309 3 13016 17765 640403 1 72841 695439 1 135297 2380810 1 43 31516 14 1442940 1001957 95903 194951 1 238773 773431 1 1 975692 2 4990979 52016 3261784 2 413095 12 3 420624 7905 60087 760051 2702333 2572405 1 1717432 1 12 3040935 1 1 31787 60114 513777 1 3270813 9639 581868 127091 270 164228 274393 1275008 261419 597715 138913 28923 13059 1848733 2895136 7754 14 1 107592 1 3557771 2067538 147790 112677 119004 1 13791082842974 249727 838699 4067558 6 470799 695141 1 3 1 1276069 23691 831013 5 165142 1236901 1 187522 2599203 1 67179 81345 44111 2909946 94752 7 406018 991024 4 1 3 573689 6 748463 2166290 33865 670769 322844 5657 1131171 1990155 5 4536811 1785704 3226501 2030929 25987 3055355 192547 1761201 433330 27235 2 312244 13203 756723 81459 12 1 1 54142 307858 2 25657 30507 1920292 3945574 1 191775 3748702 3348794 4188197 366019 1540980 3638591 1 1840852 1 26151 2888481 112861 8 11 2 1 27231 1 74 106853 3 173389 2390495 25 1 83116 3238625 75443 1 1 2125260 1 49626 1 6 312084 159735 358268 54351 367201 2868856 5779 172554 119016 141728 3 1 6 9 1 1504011 1 168968 1868493 1 5 1 244563 2 2887999 3144375 1598674 1 1578910 45313 176469 30969 8 127652 1911075 9 1300092 224328 168752 8 1619669 292559 9090 2040459 705819 1852774 10 139217 16 1221670 355060 339599 3 2184244 2546028 1 1 11 70958 242187 1 80737 1 190246 3 1 1 577711 150064 1 1047154 3851461 92399 224270 612237 1 3 3330053 1 1 1192533 615756 267923 144724 2 1 150018 4621881 1 6 299247 115996 2 10 6 185495 76351 465554 178786 1802565 257101 56 2491615 1 24547 1 1203267 32 5741149 541203 11393 1 368082 540534 16167 113481 2004136 13045 17 1 12 333803 14 1955075 1 4 38034 1286203 2382725 26777 1 180312 1 87161 4773392 1244024 1146401 3 80598 2983715 1 63741 1 1 2561436 16 1 1 1807854 1239680 200398 2 46153 1400933 11 5058787 8787 1 98841 89162 1106459 112566 1 4138891 2858906 101835 81375 539485 6587808 1 5359988 1 1 869106 443452 120748 436156 2 2 3944932 1 1875599 2 3081185 733911 447824 1 1 23187 3082414 33 3 1 1 2053904 410824 104571 885952 1946162 2 294773 364169 1 101310 2166548 1177524 2192461 12 4 3457016 90975 2356374 573234 53746 187527 7837 1441335 458407 52139 3387239 2030900 38 1648216 215105 212589 8278 1201586 244282 1 1 1897515 3957343 46 1 134481 1 1 2041785 3 1 37593 163173 1565457 3 1026885 1 34530 4655639 2 18 1940645 1550444 593209 1 2270700 706918 1 1 610113 9 1287883 3 1472134 1998685 1916822 1 296017 2 1 1737607 4155665 1510560 553342 56130 14436 13240604 4025888 1 4253261 174177 2043316 504151 2370989 420666 155232 1 219327 3752236 130062 571247 24 1 29015 31392 1020196 3 1117502 460873 7 1 228 8 133656 1 147008 1 93471 1 1 1 513410 4834094 1 14 1875636 182714 1504903 95263 4418053 1 357853 1135536 3698641 3 239316 4237884 131730 3878724 2158931 55650 1906785 1 26372 32 99217 1645677 379838 1 450352 7329657 112909 1 897980 2114198 308917 126215 1 53839 539997 238036 2 2270000 5 2388928 1668820 519153 58227 347528 1 1 2339954 10 5 2031341 54 2341529 2189774 112731 1 21918 748662 2068921 2 2232504 2923457 97740 3858 16604 398940 388755 1875003 667810 53633 315866 839868 1 7 1 14238 185 4 14 1 2 178947 1965719 398323 120849 48 1397222 961772 34124 2 160652 1 252629 246554 14529 1 299866 135255 490837 2863773 8 10 2 1906405 57 9782 118940 870003 255097 6 4187677 50965 3354376 17611 1804789 183601 158748 1539773 116107 77684 34738 2862836 1 2081903 727739 50328 2740070 17 923524 18 3089706 3144082 1 20 205247 347420 2076952 3725220 39270 2 15 49329 422629 5 1693818 2570558 2146654 1 5 129085 653766 47438 102243 389910 59715 21769 1246783 361571 4 120502 255235 1314165 3 3 5 2902624 76351 3117137 174413 2546645 14534 166054 1013583 1 1 2 9 3027288 3173742 338261 94929 1071263 4659804 1 506576 42798 4 984508 1 4 4 1 18541 7 1 269761 188905 2 1 92011 147031 677955 27484 1291675 2420682 99970 57943 1 4081062 1 250953 704904 4 349180 4273479 30528 2092508 2352781 3700946 1 77799 328993 3684623 3930179 1250080 1975798 54981 1621677 91664 1355832 1084049 721612 56950 197563 246868 5031 1 924076 1328694 58562 1 457662 2445958 1345169 957845 1056809 2485300 1687907 199029 3 9474 86928 1 2419980 3585265 570673 1 1514184 437383 1596697 29709 199606 126031 2 1541777 1 3 2090249 2402438 15 19 1423959 28 37852 4 1652596 1 405512 52 3 1948029 1 2 376 1155902 3 631665 3741991 57673 284026 424787 1 11569 5 1200313 1 20 2360854 1 119994 3889143 673424 797763 1 1 144306 1007659 1231874 75607 1 15 66187 8763 21366 146277 2684501 4458542 162223 3 1 5 94232 3036009 401312 19775 510737 3305062 58905 125783 274094 3089988 118483 1 106213 1 1289180 127905 30 528859 2 1215596 1955900 30 2236528 218643 1 2396631 1598175 1148688 452064 1 1840394 198540 1 1307187 107463 341396 2684981 9602 536871 1 148107 4068 4918434 1 2430254 2066144 88915 3585780 6464 259394 3098337 49601 42 79205 925658 1 2513666 26817 2738302 1 28 345735 5086930 361294 505662 386194 1103890 2653001 412247 4074274 2217918 1 519433 1338570 4289317 140138 18 2519983 168656 4546204 8 1 76545 511580 979214 9318 210013 50508 40 152908 17969 922507 1 7 32 1 388579 1 49886 13319 1066048 4663 27883 38419 1418098 2538216 1 778734 3556791 490764 666880 22746 5666164 4 20 1806284 21142 1 527906 2 12417 182224 49536 105029 206917 2427623 294247 1405136 321480 354137 84225 50 128073 1391176 352835 26074 91159 34229 237942 1 1519676 1 2428669 272681 148689 528951 560736 1 3548197 3833513 1438699 286613 1 1290904 47145 3456135 249648 277045 1012397 271073 1 6 149276 94843 11 177134 32336 2772732 7 22 37065 1 105299 76735 44 2211334 511942 30639 522056 5162 1899842 74 1 1448039 1 88817 21 1027532 555416 1 364383 1335609 167332 283252 49564 220972 1006800 3108886 801258 265596 61651 1 2413276 252747 416606 960925 54 311956 267135 3871698 22581 8978 2 10 1966155 3123429 28 46409 1 18433963725323 1769396 114766 49071 1 1 4228762 3483932 1139490 602592 2700468 770273 3 1 1 212087 281247 27093 156094 286299 1204001 18374 1 330780 1 1 25384 906728 99334 1250819 2161201 34 1027892 1 33449 2 129787 52246 94872 1536841 23470 1 1700323 1 1 3785351 1 95315 1014155 56570 22586 66842 7 156840 48752 1 3143722 1 1168309 2 4 101423 385892 42868 2893851 7 1783109 217499 24 460497 2003214 180135 3503010 131137 2 5240 1621601 2754811 11198 1 1 1105643 1 1671021 3 139611 18268 107229 44582 2211034 1 2880152747163 231008 262504 1 257760 1 1 52992 804418 2 2 4811272 1772250 3 1796530 1918647 1 1934549 1 100550 3448657 1681262 3 604526 320865 1901079 556908 2794800 2472000 637735 123663 1 3213187 118199 2553610 1 1750628 2563806 1 1670872 1 999609 50200 654831 1 164612 2865759 1841739 9 3744159 1331395 3202501 1 7 1 1 239868 1 1 581984 112413 401 1 29656 359367 74532 27226 51752 2583 1 645443 1559731 1 114195 1 85473 229474 111353 1 1521653 1 2568733 444398 2593568 18546 1 158085 1211147 1020006 23407 42514941388799 158442 1 1660358 5 34874 1594789 1551270 386464 502417 32280 170606 1954278 72486 3406066 11 52896 345631 4010742 33307 1951926 1441325 1886066 1 3 402778 3089364 351 28028 4301364 1 431569 5 3054030 375986 404966 1 449317 1230292 1 7 763949 1 2 3197443 1537806 335317 2 1 161263 1 1959902 1664530 139136 447570 1 1 50 158825 222939 1842131 11252 1680094 1017889 71 144808 1 53679 1 41278 1226724 1 1 2 10 2 1 112451 42133 1406662 1 112593 2 2832116 1544488 3579017 3029492 2752014 6 255091 731329 540861 1 426725 440330 212602 202358 173553 4 1189793 11031 84073 2084554 3963 1473295 1 642570 1 1423688 34509 75056 163273 490193 3200250 451777 157797 4156542 2386299 2794795 2735308 1332758 1193296 1131014 1001570 414257 4415511 4 3 1 3499595 536583 16731 93839 92382 1 45890 1 17695 8 867246 18 1607123 3197052 5 40009 1 329895 3497309 2416600 2316390 11 118179 2166659 2 136426 76762 2 14 2 3632525 214889 6 3900942 270409 230143 120414 417489 16706 1563597 31418 2 73 468763 88585 428274 3537347 2 1 491461 2806485 1 7 2950804 115684 4 1 429002 85771 2480 285541 186486 1 1 2430862 6 9 4 1833423 17143 353689 2568741 408890 2929237 208679 2198380 1 2501053 1933666 180843 1 1 2569886 1 17035 3449472 71357 246257 217898 1 47601 589824 401679 362878 13178 34464 1076419 1 554417 1 21248 2136449 1068 23029 8 766649 4 302879 274751 19 1 390259 1899931 233910 1392272 184492 2 2752059 55813 1 6 64674 205205 595508 1714309 582492 4821971 63973 1708726 189200 4548446 479425 2866037 1 1 1 2139319 1 1 3 1572621 2086152 2341038 1 619612 1 78942 772466 18932 1404368 936790 2263929 230200 3009227 251065 835010 88225 642856 824193 5559048 1 36348 2338046 481447 108132 2728223 3539009 1 197164 181408 171634 2172263 2317332 1598340 1318829 1746303 7 59657 1 1415452 122924 915828 1063890 40339 430186 4 2165185 2250922 704568 85138 4417453 255 326360 33541 3 49759 72127 912537 599665 1 29169 168741 349838 996835 1548193 2 28449 803521 4 2 2 3359043 3243259 1 491574 1675000 186105 3203018 11 39127 959876 334480 873131 70262 137080 1076591 1 2155613 74804 893022 2473922 1 1 269835 5 2407308 3 55200 905207 1 1 1245609 65934 7 1372126 530582 1383562 1 1 2718341 1 3947638 4 76837 412551 11 1 1 1208080 3024670 277 46485 1 9 562183 46 2985858 3379885 67816 1896527 1 105478 2035453 3026415 1 189256 2992616 2098002 1099666 775250 5913 13 406948 166773 1 322250 41919 480047 64950 17435 2147428 2336270 3330243 352709 86029 1398723 106236 312951 1 408211 252689 847088 2 17 34088 13128 187366 2 1559482 2349010 1651122 2371088 401005 1715445 1 29483921 1464444 50228 2365851 1651636 768715 226704 23677 83501 1 252623 444628 34 3640316 3602127 45369 1 1 1978261 1 3019189 1 25411 2177552 192839 191146 293712 3840622 182598 4069200 175757 1 2250458 4 1 7 2740824 2753005 1 2836428 1 12 19 2 1788326 3302198122211 3386546 1176663 20847 28 1194294 794665 2630378 13624 722012 2273872 1549353 1 3 1735700 1668388 416 970581 258382 295427 1 121571 3193610 3764806 1 368985 20436 89411 3 16130 2 241879 1 2996216 136958 2382095 510146 1762872 1372194 4215387 346915 4423 1 904153 2004500 248495 836598 3529163 27 2547535 1424181 1885308 1 1056747 289743 176929 2299073 170473 1 1 839941 12382 51457 608526 1684239 4843522 34550 929855 2767014 2979286 1 340808 184830 131077 57298 63854 381689 201998 1715328 118687 69190 123466 1 2 69392 159797 382756 1513430 2506318 457 1
Geometric mean score: 10983.8 in 31214 seconds

Cambié a g ++ / MinGW y 3 hilos.
El código generado por GNU es más del doble de rápido que el de Microsoft.
No es de extrañar, ¿qué pasa con su terrible implementación de STL?

Teletransportadores

El efecto de teletransportador depende en gran medida de la posición. Hasta ahora, estaba feliz de considerar un teletransportador como siempre bueno (visto como un espacio vacío) o siempre malo (visto como una pared para que ningún roedor lo tomara).

Este es un modelo demasiado grueso.
Un teletransportador determinado puede impulsar a una rata hacia adelante hasta unas pocas celdas de la meta, pero una vez allí, el mismo teletransportador puede arrojar a la rata fuera del tablero.
Es muy probable que este teletransportador sea reconocido como aceptable (ya que aumenta la aptitud física más rápido que cuando "camina" hacia la misma ubicación x), se convierte en parte del genoma dominante y mata a casi todas las ratas que confían en él como "siempre seguro".
Dado que las ratas no tienen forma de conocer su posición X, la única solución para detectar estos teletransportadores traicioneros es decidir si pisarlos en función de los únicos datos contextuales disponibles, es decir, la cuadrícula de color 5x5.

Para hacerlo, definí 4 tipos de genes de color:

  • detector de trampa de peligro
  • vacío transitable en cualquier lugar de la pista
  • bloque prohibido en cualquier parte de la pista
  • viga vista como vacía o bloque según el entorno

La idea es tratar de distinguir un teletransportador mirando a sus 8 vecinos inmediatos. Dado que la probabilidad de tener 8 vecinos idénticos en una ubicación dada es muy baja, eso debería permitir identificar una instancia única de cada teletransportador.

Los 8 colores vecinos se pueden combinar para formar una firma local, que es invariable según la posición en el laberinto. Desafortunadamente, los 8 vecinos solo son visibles para las células ubicadas dentro del cuadrado interno del campo de visión 3x3, por lo que las firmas serán inexactas en el borde del campo de visión.
Sin embargo, esto nos dará una información contextual constante en el vecindario inmediato, que es suficiente para aumentar la probabilidad de navegar teletransportadores con éxito.

Los genes del haz tienen un campo variable de 2 bits.
Para una firma local de teletransportador dada, hay una posibilidad entre cuatro de que la celda de haz se considere intransitable. Cada valor del campo selecciona una de estas cuatro posibilidades.
Como resultado, una mutación del gen del haz en estos 2 bits recorrerá 4 posibles significaciones contextuales del color.

Además, los colores más importantes para adivinar todavía son paredes y trampas. Esto significa que deberíamos permitir la detección de teletransportadores solo después de que las ratas supieran dónde están las paredes y las trampas.

Esto se lleva a cabo actualizando las firmas locales solo con moderación. El criterio actual para actualizar una firma local es estar en la vinculación de un color identificado como un posible teletransportador.

La codificación utiliza 5 bits por gen de color y tipos de grupos para liberar los 3 bits menos significativos para codificar un valor 0..7:

  • 4 peligro
  • 4 vacíos
  • 4 bloque
  • 4 haz

Cada gen de haz tiene 1/4 de probabilidad de ser considerado como un bloque y 3/4 de posibilidades de ser considerado vacío, por lo que 4 haces representan en promedio 1 bloque y 3 vacíos.

La proporción promedio representada por una distribución aleatoria de 16 colores es así:

  • 4 peligro
  • 7 vacío
  • 5 bloque

Esta mezcla parece dar los mejores resultados hasta ahora, pero no he terminado de ajustarla.

Mutabilidad genética

Una cosa es segura: los valores de código elegidos para representar los tipos de genes son críticos. Invertir dos valores puede costar 2000 puntos o más.

Aquí, nuevamente, la razón por la cual está más allá de mis matemáticas.

Supongo que las probabilidades de mutación de un tipo a otro deben ser equilibradas, o de lo contrario, como en una matriz de Markow, las probabilidades acumulativas tienden a restringir los valores al subconjunto que tiene las mayores probabilidades de transición entrante.

Camino al rescate

La ruta reducirá drásticamente la cantidad de celdas visitadas, lo que permite probar solo las que tienen más probabilidades de llegar a la meta. Por lo tanto, no solo se evitan algunos callejones sin salida frecuentes, sino que también es mucho más probable que se descubran códigos de color incorrectos antes.
Como resultado, el tiempo de convergencia disminuye fuertemente.

Sin embargo, esto no ayuda a resolver los mapas donde el genoma no puede producir una representación adecuada de la pista.

¿Qué hacer con los imbéciles?

Después de mirar visualmente la pista, entendí por qué una estrategia predeterminada que trata de avanzar incluso cuando parece que no hay más que paredes al frente es realmente mejor que contenerse.
Los "muros" pueden ser en realidad teletransportadores que producen tantos resultados desafortunados que el genoma los mapea como obstáculos que nunca deben pisarse, pero en raras ocasiones una instancia particular de este travieso teletransportador puede tener un efecto positivo (o al menos no letal) , así que tomarlo en lugar de retroceder aumenta las posibilidades de encontrar un camino hacia la victoria.

Convergencia temprana

Me parece que la tasa de mutación es un poco demasiado baja (al menos para mis roedores).

La configuración actual de 0.01 le da al ADN un 37% de posibilidades de sobrevivir al proceso de mutación intacto. Cambiar el parámetro a 0.0227 reduce esta probabilidad a aproximadamente 10%

La fórmula misteriosa es la mutación P 1 bit = 1-P genoma completo intacto 1/100 , siendo 100 la longitud de bits del genoma.

Por ejemplo, para un 10% de probabilidad, P 1 bit de mutación = 1 - 0.1 1/100 = 0.0277
Para un 5% de probabilidad, P = 1 - 0.05 1/100 = 0.0295 Al invertir
la fórmula, encontramos que 0.01 da un 37% de posibilidades de ser sin cambios por mutación.

Volví a ejecutar exactamente la misma prueba (usando una secuencia fija de semillas aleatorias) con una probabilidad del 10%.
En muchos mapas, las fallas anteriores se convirtieron en éxitos (limitados). Por otro lado, las enormes explosiones de población fueron menores (lo que tuvo el interesante efecto secundario de acelerar mucho el cálculo).
A pesar de que los puntajes muy altos (más de un millón) fueron menos comunes, el número de carreras más exitosas fue más que suficiente para compensar.
Al final, la media aumentó de 1400+ a aproximadamente 2000.

Establecer P al 5%, por el contrario, produjo una media de aproximadamente 600.
Supongo que la tasa de mutación fue tan alta que el genoma de las ratas ganadoras se convirtió con demasiada frecuencia en variantes menos eficientes.

Como funciona este

Con los detectores de teletransportador agregados, el número de juegos fallidos (puntaje <10) disminuyó significativamente.
En una prueba de 2000 ejecuciones, solo hubo 1/3 de fallas.
La media geométrica solo aumentó de 2900 a 3300, pero este número no refleja la mejora.

Los colores vacíos se adivinan con frecuencia como vigas y peligros (generalmente de 2 a 5). El genoma "usa" estos colores para bloquear caminos que podrían causar problemas a las ratas.

El genoma es bastante bueno para adivinar trampas (es decir, una vez que las ratas pueden alcanzar la meta, los colores que representan detectores de trampas reales se adivinan aproximadamente el 90% del tiempo).
También hace uso de los nuevos códigos de haz para los teletransportadores, aunque más raramente (probablemente porque los teletransportadores "traicioneros" son menos comunes que las trampas, y otros colores de haz / peligro evolucionan para bloquear el camino a las últimas instancias de estos traidores).

A juzgar por la cantidad de juegos en los que emerge un genoma ganador después de 5000 turnos o más, creo que esta nueva raza se beneficiaría enormemente de una mayor tasa de mutación.

Comunidad
fuente
Como hay un número par de trampas, vacíos, paredes y teletransportes, solo necesita 3 bits para almacenar las proporciones con precisión (incluso si considera trampas == paredes). Además, ¿consideró / descartó la idea de usar bits de compensación de trampa no utilizados en el anti-wallbanging? Dado que el objetivo es no heredar de los padres, en realidad podría usar todos los bits en el anti-wallbanging. No hay razón para que sean únicos, no creo.
Mooing Duck
1
@MooingDuck Probé su idea de reutilizar bits de desplazamiento, pero falló. Como temía, reutilizar una información para dos propósitos diferentes no parece funcionar. Supongamos, por ejemplo, que los bits de desplazamiento de un color dado son necesarios para que un genoma elija la dirección vertical adecuada en una ruta dada, este color ya no puede representar una trampa significativa sin destruir la ruta que depende de los mismos datos. También traté de usar 6 bits, pero como temía también los 4 golpes restantes contra la pared eran muy escasos.
1
Es bueno saberlo, pero sugerí dos ideas allí, una era usar todos los bits (reutilizar algunos), y la otra era usar los bits de compensación de trampa no utilizados para paredes / vacío. ¿Intentaste ambos? (Entiendo totalmente que si no quieres intentarlo, difícilmente debes hacerlo si no quieres)
Mooing Duck
1
Intenté ambos, y ambos fallaron. Las compensaciones de trampa son importantes incluso cuando un gen no las usa, porque este gen todavía puede mutar de nuevo a un color de trampa, en cuyo caso el desplazamiento de trampa probablemente habrá mutado a cualquier bit de contexto que sea más rentable, y perdió su significado como compensación . Ahora volverá a mutar al valor de compensación rentable y destruirá los caminos de las ratas que dependían de él como indicadores contextuales. Creo que vi el caso de tal oscilación con mi herramienta gráfica, pero no es fácil exhibir una instancia clara de este problema.
16

ColorScorePlayer, puntaje preliminar ≈ 22

Este es el bot que ves en el trabajo en el GIF en el desafío.

Este fue nuestro robot de prueba durante toda la fase de desarrollo. Utiliza el genoma para almacenar una puntuación de calidad para cada uno de los 16 colores. Luego realiza el movimiento hacia adelante que lo mueve al color con la mejor puntuación (y nunca se mueve hacia -1). En caso de empate, se elige un movimiento aleatorio entre las celdas de unión.

Hemos trasladado este reproductor a todos los idiomas del controlador, por lo que actúa como ejemplo de cómo usarlos:

Pitón

class ColorScorePlayer(Player):
    def __init__(self):
        Player.__init__(self)
        self.coords = [Coordinate( 1, 0),
                       Coordinate( 1,-1),
                       Coordinate( 1, 1)]
        self.n_moves = len(self.coords)

    def turn(self):
        max_score = max([self.bit_chunk(6*self.vision_at(c.x, c.y), 6) for c in self.coords if self.vision_at(c.x, c.y)>=0])
        restricted_coords = [c for c in self.coords if self.vision_at(c.x, c.y)>=0 and self.bit_chunk(6*self.vision_at(c.x,c.y), 6) == max_score]

        return random.choice(restricted_coords)

Rubí

class ColorScorePlayer < Player
    def initialize(rng)
        super(rng)
        @coords = [Vector2D.new( 1,-1),
                   Vector2D.new( 1, 0),
                   Vector2D.new( 1, 1)]
    end

    def vision_at(vec2d)
        @vision[vec2d.x+2][vec2d.y+2]
    end

    def turn
        max_score = @coords.map { |c|
            color = vision_at(c)
            color < 0 ? -1 : bit_chunk(6*color, 6)
        }.max

        restricted_coords = @coords.select { |c|
            color = vision_at(c)
            color >= 0 && bit_chunk(6*color, 6) == max_score
        }

        restricted_coords.sample(random: @rng)
    end
end

C ++

coord_t colorScorePlayer(dna_t d, view_t v) {
    const int chunklen = DNA_BITS / N_COLORS;
    int ymax[3], nmax, smax = -1;
    for(int y = -1; y <= 1; y++) {
        if(v(1, y) == OUT_OF_BOUNDS) continue;
        int score = dnarange(d, v(1, y)*chunklen, chunklen);
        if(score > smax) {
            smax = score;
            nmax = 0;
        }
        if(score == smax) ymax[nmax++] = y;
    }
    return {1, ymax[v.rng.rint(nmax)]};
}

C#

public static void ColorScorePlayer(GameLogic.IView v, GameLogic.IGenome g, Random rnd, out int ox, out int oy)
{
    ox = 0;
    oy = 0;

    var max_score = cspcoords.Where(c => v[c.x, c.y] > -1).Select(c => g.cutOutInt(6 * v[c.x, c.y], 6)).Max();
    var restrictedCoords = cspcoords.Where(c => v[c.x, c.y] > -1 && g.cutOutInt(6 * v[c.x, c.y], 6) == max_score).ToArray();

    Coord res = restrictedCoords[rnd.Next(restrictedCoords.Length)];

    ox = res.x;
    oy = res.y; 
}

Java

package game.players;

import java.awt.*;
import java.util.Map;

public class ColorScorePlayer extends Player{
    private static final Point[] possibleMoves = {new Point(1, 0), new Point(1, -1), new Point(1, 1)};

    @Override
    public Point takeTurn(String genome, Map<Point, Integer> vision) {
        int chunkLength = genome.length()/16;
        int maxSum = -1;
        Point maxSumMove = possibleMoves[0];
        for (Point move: possibleMoves){
            if (vision.get(move) == -1){
                continue;
            }
            int initialPoint = chunkLength*vision.get(move);
            int sum = 0;
            for (int i = initialPoint; i < initialPoint + chunkLength; i++){
                sum = (sum<<1)+Integer.parseInt(genome.charAt(i)+"");
            }
            if (sum > maxSum){
                maxSum = sum;
                maxSumMove = move;
            }
        }
        return maxSumMove;
    }
}

El jugador anota con bastante inconsistencia. Aquí hay 50 carreras aleatorias:

Scores: 1 1 1132581 3 43542 1 15 67 57 1 11 8 623162 1 1 1 134347 93198 6 1 2 1 1 245 3 1 1 27 1 31495 65897 9 5 1 2 20 2 117715 1 1 1 20 64616 5 38 1 2 1 2 12
Martin Ender
fuente
12

ColorFarSeeker, C ++ ≈ 74.7

Este desafío es realmente muy divertido y simple si lo intentas.

No te dejes desanimar por la larga descripción.
Simplemente visite el GitHub y vea las cosas ... ¡todo será mucho más claro! :)

El simulador C ++ es muy recomendable por su velocidad. Incluso después de haber terminado de traducir mi programa de Python a C ++, la simulación de Python todavía no se ha detenido.

Esta es una variante mejorada de ColorScorePlayer. Para hacer un buen uso de su vista de 5x5, considera movimientos de 2 pasos con una función ponderada. Los movimientos de 1 paso por delante tienen un mayor peso, ya que tienen un efecto más inmediato en la supervivencia. Mover 2 pasos hacia adelante se les da menor peso.

Intenta avanzar, pero si no se ve ningún movimiento seguro ... luego intenta de lado ... y si todo lo demás falla, retrocede al azar.

coord_t colorFarSeeker(dna_t d, view_t v) {
#define s(w,x,y) (v(x,y)>-1?((b+dnarange(d,l+m+n*v(x,y),n))*w):0)
#define max2(a,b) (((a)>(b))?(a):(b))
#define max3(a,b,c) (max2(a,max2(b,c)))
#define push(vec,maxScore,score,x,y) if(score==maxScore&&v(x,y)>-1)vec.push_back({x,y});
#define tryReturn() if(vec.size()){return vec[v.rng.rint((int)vec.size())];}vec.clear();

    // Some constants to tweak
    int k = 4;
    int l = 3;
    int m = dnarange(d, 0, l);
    int n = 4;
    int b = dnarange(d, l, k) + 10;

    std::vector<coord_t> vec;

    // Looks forward for good moves...
    int upRightScore = s(1,0,-2) + s(1,1,-2) + s(1,2,-2) + s(5,1,-1);
    int forwardScore = s(1,2,-1) + s(1,2,0) + s(1,2,1) + s(5,1,0);
    int downRightScore = s(1,0,2) + s(1,1,2) + s(1,2,2) + s(5,1,1);
    int maxForwardScore = max3(upRightScore,forwardScore,downRightScore);
    push(vec,maxForwardScore,upRightScore,1,-1);
    push(vec,maxForwardScore,forwardScore,1,0);
    push(vec,maxForwardScore,downRightScore,1,1);
    tryReturn();

    // Looks sideways for good moves...
    int upScore = s(1,-1,-2) + s(1,0,-2) + s(1,1,-2) + s(5,0,-1);
    int downScore = s(1,-1,2) + s(1,0,2) + s(1,1,2) + s(5,0,1);
    int maxSideScore = max2(upScore,downScore);
    push(vec,maxSideScore,upScore,0,-1);
    push(vec,maxSideScore,downScore,0,1);
    tryReturn();

    // If all else fails, move backwards randomly.
    // I have tried considering the scores of backmoves,
    // but it seems worse than just randomly moving backwards. 
    vec.push_back({-1,-1});
    vec.push_back({-1,0});
    vec.push_back({-1,1});
    return vec[v.rng.rint((int)vec.size())];

}

Puntuación:

Hay bastantes 1's ... que pueden ser un poco deprimentes cuando ves que la consola arroja 1 uno detrás del otro. Como un planeta con todas las necesidades para la vida, pero sin signos de civilizaciones de ratas avanzadas ...
Luego, espigas ocasionales. :)

Hmm ... aparentemente tuve la suerte de mi primer lote de carreras, obteniendo un geométrico de más de 300. Las puntuaciones realmente fluctúan bastante. Pero de todos modos, con más ejecuciones del simulador, probablemente esté más cerca de ≈ 74. (Thx feersum por ayudarme a simular y su programa ultrarrápido)

Puntajes de mis carreras: 6 6 53 1 5 101223 89684 17 2 303418 4 85730 24752 1 1 1 3482515 39752 1 59259 47530 13 554321 1 563794 1 1770329 1 57376 1 123870 4 1 1 79092 69931 594057 1 69664 59 1 6 37857 1733138 55616 2 1 51704 1 254006 4 24749 1 117987 49591 220151 26 4292194 23 57616 72 67 1 4 308039 1 1 103 89258 1 286032 1 5 3 1 5 114851 46 143712 5 15 9 80 7425 1 1 7 1 108379 70122 97238 1 1 5 2 23 104794 1 10476 59245 1 204 1 1 12 1 29641 1 314894 18785 13 1 3 1 1 1 2 526001 1 1 1 27559 29285 3 3 128708 70386 30 2 2 1 208531 331 1 2 1 61 114993 1 15 51997 1 2 1 146191 1 31 4 3 1 161422 207 1 64 1 1 1 68594 145434 87763 150187 169 185518 1 1 1 1 24208 2570 1 1 537 1 1 462284 1 2 55 1 1 1 214365 1 40147 2 213952 1 29 3 1 2144435 5 4502444 72111 1 1 1 1 1 774547

Vectorizado
fuente
1
Obtuve una media geométrica de 74.7 con 1000 juegos, buen trabajo.
fiesta
8

Obispo - Python, puntaje preliminar 1.901

El Obispo siempre se mueve en diagonal, por lo que la mitad del tablero es inaccesible en una caminata dada a través del tablero, pero esto significa menos movimientos potenciales para codificar, por lo que cada parte individual del genoma puede representar un movimiento (el Obispo nunca se retira). A qué bit referirse se decide en función del bloque de cuadrados 3x3 delante (a la derecha) de la muestra. El mejor movimiento para una situación dada es solo una mutación de distancia.

Al principio, este bot aprende rápidamente, pero luego a menudo alcanza un techo antes de llegar al final, presumiblemente donde ocurre uno de los siguientes dos problemas:

  • Dos o más partes del tablero se asignan al mismo bit pero requieren movimientos diferentes.
  • Algunos tableros no son transitables utilizando solo movimientos diagonales.

Código

class BishopPlayer(Player):
    def __init__(self):
        Player.__init__(self)
        self.coords = [Coordinate(1,-1),
                       Coordinate(1, 1),
                       ]
        self.inputs = [(x,y) for x in (0,1,2) for y in (-1,0,1)]

    def turn(self):
        # Move away from out of bounds areas
        if self.vision_at(0,-1) == -1:
            return self.coords[1]
        if self.vision_at(0,1) == -1:
            return self.coords[0]

        # Move right, and either up or down based on one bit of the genome
        bit_to_use = sum(self.vision_at(self.inputs[i][0],
                                        self.inputs[i][1]
                                        ) * (16 ** i) for i in range(9)
                         ) % 100
        return self.coords[self.bit_at(bit_to_use)]

A pesar de estas limitaciones, en raras ocasiones el Obispo lo hace bien, con especímenes individuales que completan varias vueltas del tablero cada uno. Pensé que en una vuelta dada, un espécimen solo puede moverse en la mitad del tablero (equivalente a solo los cuadrados negros o solo los cuadrados blancos en un tablero de ajedrez). Sin embargo, como señaló Martin Büttner, un teletransportador puede mover una muestra de un cuadrado negro a un cuadrado blanco o viceversa, por lo que en la mayoría de los tableros no estarán restringidos.

(Hay dos pares de tipos de teletransportadores coincidentes y cada uno tiene una probabilidad de 0.5 de tener un desplazamiento que mueve un espécimen a la otra mitad de los cuadrados en blanco y negro. Entonces, la probabilidad de que un tablero tenga solo teletransportadores que restrinjan el espécimen a uno la mitad del tablero por vuelta es solo 0.25.)

Los puntajes muestran que los triunfos ocasionales se entremezclan con largos períodos de falta del final:

Puntuaciones: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 2 1 1 1 1 1 6 1 8 1 10 15 1 1 12544 1 2 1 1 1 1 3 7554 1 1 1 1 1

trichoplax
fuente
8

Jugador de bonificación de carrera: media geométrica 50.35 (prueba de 5000 juegos)

Este bot puntúa cuadrados por sus colores individuales basados ​​en una sección de ADN de 6 bits como el jugador de puntuación de color, pero con un sistema de números diferente. Este bot fue motivado por la idea de que es bastante arbitrario que uno de los bits cambie el valor de la puntuación en 32, mientras que otro lo hace solo en 1. Asigna el valor n (n + 1) / 2 a una serie de n 1 bits consecutivos. Además, agrega un mecanismo de aleatorización en un intento de evitar quedarse atascado. Hará un movimiento aleatorio hacia adelante con una probabilidad de 1 en 30.

A modo de comparación, el jugador con puntaje de color obtuvo 30 a 35 en un par de pruebas de 1000 juegos. Curiosamente, el puntaje máximo del jugador con puntaje de color estaba en el rango de 3-5 millones, mientras que el máximo de bonificación de carrera fue de solo 200 mil. Run-bonus se beneficia del sistema de puntuación promedio logarítmico al obtener un puntaje distinto de cero de manera más consistente.

Ejecutar 5000 juegos tomó aproximadamente 20 minutos con 6 hilos en el controlador C ++.

coord_t runbonus(dna_t d, view_t v) {
    int ymax[3], nmax, smax = -1;
    if(!v.rng.rint(30)) {
        int y;
        while(!~v(1, y = v.rng.rint(-1, 1)));
        return {1, y};
    }
    for(int y = -1; y <= 1; y++) {
        if(v(1, y) == OUT_OF_BOUNDS) continue;
        int score = 0;
        int streak = 0;
        for(int i = 0; i < 6; i++) {
            if(d[6*v(1,y) + i])
                score += ++streak;
            else
                streak = 0;
        }
        if(score > smax) {
            smax = score;
            nmax = 0;
        }
        if(score == smax) ymax[nmax++] = y;
    }
    return {1, ymax[v.rng.rint(nmax)]};
}
Feersum
fuente
solo por curiosidad, ¿cuánto tiempo tomó la prueba de 5000 pistas? Mis ratas necesitan más de una hora para completar 1000 pistas, por lo que tendría que dejar que la computadora funcione toda la noche para reproducir su caso de prueba.
@kuroineko La respuesta a su pregunta ya estaba en mi respuesta.
fiesta
Ups, lo siento. Probaré su código en mi PC para ver qué papel juega el hardware en la diferencia de velocidad. Y tal vez intente usar gcc en lugar de MSVC. Noté un aumento del rendimiento del 30% sobre MSVC en un par de otros bits de código de computación pesada.
Su código se ejecutó en un poco más de 20 minutos para 1000 pistas en mi [email protected] con 4 hilos. El puntaje fue de aproximadamente 56 . Parece que mi PC es 5 veces más lenta que la suya y mi código sería aproximadamente 6 veces más lento en una máquina determinada (pero tener una mejor puntuación mecánicamente implica un mayor tiempo de cálculo). Como estoy demasiado arruinado para comprar una nueva PC, es hora de un poco de optimización ...
8

StarPlayer | C ++ | Puntuación: 162 (basado en 500 carreras ejecutadas)

Este jugador intenta usar A * para encontrar la mejor manera de avanzar. Asigna pesos de la misma manera que ColorScorePlayer e intenta encontrar el camino hacia el borde derecho de la vista. La implementación no es la más bonita que he hecho, pero al menos no es demasiado lenta.

#include <utility>

#define IDX(a,b) a[VIEW_DIST + b.x][VIEW_DIST + b.y]

std::pair<coord_t,int> planAhead(int weights[N_COLORS], view_t &v, coord_t target) {
    bool open[VIEW_DIST*2+1][VIEW_DIST*2+1] = {false};
    bool closed[VIEW_DIST*2+1][VIEW_DIST*2+1] = {false};
    int f_score[VIEW_DIST*2+1][VIEW_DIST*2+1] = {0};
    int g_score[VIEW_DIST*2+1][VIEW_DIST*2+1] = {0};
    coord_t came_from[VIEW_DIST*2+1][VIEW_DIST*2+1] = {{0,0}};
    open[VIEW_DIST][VIEW_DIST] = true;
    g_score[VIEW_DIST][VIEW_DIST] = v.rng.rint(5);
    f_score[VIEW_DIST][VIEW_DIST] = (abs(target.x) + abs(target.y)) * 10;
    for (;;) {
        coord_t current{VIEW_DIST+1,0};
        for (int x = 0; x < (VIEW_DIST*2+1); x++)
            for (int y = 0; y < (VIEW_DIST*2+1); y++)
                if (open[x][y] && (current.x > VIEW_DIST || f_score[x][y] < IDX(f_score,current)))
                    current = {x - VIEW_DIST, y - VIEW_DIST};
        if (current.x > VIEW_DIST)
            return {{1,0}, 1000000};
        if (current.x == target.x && current.y == target.y)
            break;
        IDX(open,current) = false;
        IDX(closed,current) = true;
        for (int dx = -1; dx <= 1; dx++) for (int dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0)
                continue;
            coord_t tentative{current.x + dx, current.y + dy};
            if (abs(tentative.x) > VIEW_DIST || abs(tentative.y) > VIEW_DIST)
                continue;
            if (IDX(closed,tentative))
                continue;
            auto color = v(tentative.x, tentative.y);
            if (color == OUT_OF_BOUNDS)
                continue;
            auto tentative_g = IDX(g_score,current) + weights[color];
            if (!IDX(open,tentative) || tentative_g < IDX(g_score,tentative)) {
                IDX(came_from,tentative) = current;
                auto distance = abs(tentative.x - target.x) + abs(tentative.y - target.y);
                IDX(f_score,tentative) = tentative_g + distance * 10;
                IDX(g_score,tentative) = tentative_g;
                IDX(open,tentative) = true;
            }
        }
    }
    auto prev = target, current = target;
    while (current.x != 0 || current.y != 0)
        prev = current, current = IDX(came_from,current);
    return {prev, IDX(g_score,target)};
}

coord_t starPlayer(dna_t d, view_t v) {
    const int chunklen = DNA_BITS / N_COLORS;
    int weights[N_COLORS];
    for (int i = 0; i < N_COLORS; i++)
        weights[i] = dnarange(d, i*chunklen, chunklen);
    std::pair<coord_t,int> choice{{1,0}, 1000000};
    for (int y = -VIEW_DIST; y <= VIEW_DIST; y++) {
        auto plan = planAhead(weights, v, {VIEW_DIST, y});
        if (plan.second < choice.second)
            choice = plan;
    }
    return choice.first;
}

Puntajes de muestra:

4 92078 1 10 1 1 3 2 2862314 5 24925 1 3 2 126502 1 24 1097182 39 1 1 1 47728 227625 137944 15 1 30061 1 1 1 3171790 19646 10 345866 1 1 1 829756 425 6699 22 8 1 1 6 6 104889 125608 1

Anton
fuente
1
En 1000 juegos obtuve un puntaje de 133.2, bueno.
feersum
7

WallGuesser: obtuvo 113.266 en una prueba de 1000 juegos

Codificación

Hice una codificación de 6 bits / color realmente simple. Para decodificar el color [n]

  • Suma cada noveno bit del genoma hasta 96
  • Si el puntaje de la suma es> = 4, entonces diga que este cuadrado está bloqueado
  • Si el puntaje de suma es <= 4, entonces su puntaje final es 2 ^ de su puntaje de suma

Al difundir los bits para un color en todo el genoma, estoy aumentando la posibilidad de que se usen bits de ambos padres para cada color.

Movimiento

Utilizo una búsqueda basada en A * (estoy seguro de que no es muy eficiente) para buscar la ruta de menor costo a cualquiera de los cuadrados del borde derecho. Si un color se asigna a "bloqueado", la búsqueda nunca lo ingresará. Si la búsqueda no puede encontrar una ruta, se supone que esta rata no está en condiciones de reproducirse e intenta terminar moviéndola hacia la izquierda.

Reducir el número de ratas no aptas

Dado que mi genoma está adivinando efectivamente qué cuadrados son teletransportadores de pared o hacia atrás, las ratas que no tienen adivinanzas (no hay colores que se mapeen como bloqueados) no son muy adecuadas. Para tratar de eliminar estas ratas si ningún color se marcaría como bloqueado, CADA color se marcará como bloqueado y la rata siempre se moverá una hacia la izquierda.

QUE HACER

Actualmente no hay aleatoriedad en el comportamiento, por lo que es fácil que las ratas se atasquen.

#include "./gamelogic.cpp"

#include <algorithm>
#include <set>
#include <map>
#include <climits>

bool operator< (const coord_t &a, const coord_t &b){
    if(a.x != b.x){ return a.x < b.x; }
    else if (a.y != b.y){ return a.y < b.y; }
    else{ return false; }
}

bool operator== (const coord_t &a, const coord_t &b){
    return (a.x == b.x) && (a.y == b.y);
}

int coordDistance(const coord_t &a, const coord_t &b){
    int xDif = abs(a.x - b.x);
    int yDif = abs(a.y - b.y);
    return xDif > yDif ? xDif : yDif;
}

int coordMinSetDistance(const coord_t &a, const std::set<coord_t> &ends){
    int min = INT_MAX;
    for (auto i : ends){
        int cur = coordDistance(a, i);
        if (cur < min){
            min = cur;
        }
    }
    return min;
}


class ColorMap{
public:
    view_t *v;
    int colors[16] = {};
    const int Blocked = -1;

    ColorMap(dna_t &d, view_t *v){
        this->v = v;

        //Decode the genome
        for (int i = 0; i <= (16*6); i++){
            if (d.at(i) == true){
                colors[i % 16]++;
            }
        }

        //Encode the result
        bool guessedWalls = false;
        for (int i = 0; i < 16; i++){
            if (colors[i] >= 4){
                colors[i] = Blocked;
                guessedWalls = true;
            }
            else{
                colors[i] = pow(2, colors[i]);
            }
        }

        if (guessedWalls == false){
            for (auto i : colors){
                i = Blocked;
            }
        }
    }

    int operator() (coord_t pos){
        if (abs(pos.x) > VIEW_DIST || abs(pos.y) > VIEW_DIST){
            return Blocked;
        }

        int value = (*v)(pos.x, pos.y);
        if (value == OUT_OF_BOUNDS){
            return Blocked;
        }
        else{
            return colors[value];
        }
    }

    void print(){
        int lower = -1 * VIEW_DIST;
        int upper = VIEW_DIST;
        for (int y = lower; y <= upper; y++){
            for (int x = lower; x <= upper; x++){
                std::cout << std::setw(3) << this->operator()({ x, y });
            }
            std::cout << std::endl;
        }
    }
};

class node{
public:
    coord_t pos;
    coord_t cameFrom;
    int gScore;
    int minDistance;

    node(coord_t pos, coord_t cameFrom, int gScore, int minDistance){
        this->pos = pos;
        this->cameFrom = cameFrom;
        this->gScore = gScore;
        this->minDistance = minDistance;
    }

    int fScore() const{ return gScore + minDistance; };

    bool operator< (const node &rhs) const{ return fScore() < rhs.fScore(); }
};

class EditablePriorityQueue{
private:
    //This is reversed so smallest are on top
    struct lesser{
        bool operator()(node *a, node *b) const{
            return (*b) < (*a);
        }
    };

    std::vector<node*> queue; // Use heap functions to maintain the priority queue ourself
    std::map<coord_t, node*> members;

public:
    EditablePriorityQueue(){};

    ~EditablePriorityQueue(){
        for (auto &m : members){
            delete m.second;
        }
    }

    bool empty(){ return members.empty(); }

    node *top(){
        auto top = this->queue.front();
        std::pop_heap(queue.begin(), queue.end(), lesser());
        queue.pop_back();
        members.erase(top->pos);
        return top;
    }

    void set(coord_t target, coord_t cameFrom, int gScore, int minDistance){
        auto targetLocation = members.find(target);

        //If the target isn't a member add it
        if (targetLocation == members.end()){
            auto *newNode = new node(target, cameFrom, gScore, minDistance);
            queue.push_back(newNode);
            std::push_heap(queue.begin(), queue.end(), lesser());
            members[target] = newNode;
        }
        //The target must be updated
        else{
            auto currentNode = targetLocation->second;
            if (currentNode->gScore > gScore){
                currentNode->gScore = gScore;
                currentNode->cameFrom = cameFrom;
                std::make_heap(queue.begin(), queue.end()); //More efficient way to do this?
            }
        }
    }
};

std::pair<coord_t, int> pathCost(ColorMap &m, coord_t start, const std::set<coord_t> &ends){
    EditablePriorityQueue openSet;
    std::set<coord_t> closedSet;
    std::map<coord_t, coord_t> cameFrom;

    openSet.set(start, start, 0, coordMinSetDistance(start, ends));
    while (openSet.empty() == false){
        auto current = openSet.top();
        closedSet.insert(current->pos);
        cameFrom[current->pos] = current->cameFrom;

        //Check if we're done
        if (ends.count(current->pos) != 0){
            //Recover the path
            coord_t path = current->pos;
            int finalScore = current->gScore;
            delete current;
            while (!(cameFrom[path] == start)){
                path = cameFrom[path];
            }

            return{ path, finalScore };
        }               

        //Examine current's neighbours
        for (int x = -1; x <= 1; x++) for (int y = -1; y <= 1; y++){
            coord_t neighbour = { current->pos.x + x, current->pos.y + y };

            if (x == 0 && y == 0){ continue; }

            closedSet.count(neighbour);
            if (closedSet.count(neighbour) != 0){ continue; }

            int neighbourScore = m(neighbour);
            if (neighbourScore == m.Blocked){ continue; }

            int tentativeScore = current->gScore + neighbourScore;
            openSet.set(neighbour, current->pos, tentativeScore, coordMinSetDistance(neighbour, ends));

        }
        delete current;
    }

    return{ { -1, 0 }, INT_MAX }; //Try to end it
}

coord_t myPlayer(dna_t d, view_t v) {
    auto ourMap = ColorMap(d, &v);

    std::set<coord_t> edges;
    for (coord_t edge = { VIEW_DIST, -1 * VIEW_DIST }; edge.y <= VIEW_DIST; edge.y++){
        edges.insert(edge);
    }

    //Move to the neighbor closest to a square on the right
    auto result = pathCost(ourMap, { 0, 0 }, edges);
    auto minMove = result.first;

    return minMove;
}

int main() {
    slog << "Geometric mean score: " << runsimulation(myPlayer) << std::endl;
}
Ceribia
fuente
Hm, esto no se compila para mí g++ -std=c++11 .\wallguesser.cpp -O2 -o .\wallguesser.exe. Recibo muchos errores, pero el primero es.\wallguesser.cpp:47:19: error: 'dna_t' has no member named 'at' if (d.at(i) == true){
Martin Ender
No hay problema, simplemente cambiar atpara []solucionarlo.
fiesta
7

The FITTEST - Puntuación media geométrica: ~ 922 (2K carreras)

Mi enfoque es:

  1. Descubra qué mata a la especie y defina el comportamiento deseado (funcional)
  2. Implemente el comportamiento deseado en el código (técnico)
  3. Dale una prioridad . ¿Es más importante o menos importante que otro comportamiento deseado?
  4. Optimice la puntuación media geométrica ajustando los parámetros de las soluciones.

Probé más de 2000 conjuntos de parámetros con las mismas 50 semillas. Se seleccionaron los conjuntos más prometedores y se puntuaron utilizando 250 semillas idénticas y los que obtuvieron el rango más alto fueron la entrada para la siguiente ronda de prueba. Así que logré crear un algoritmo genético para encontrar el algoritmo genético óptimo para este problema, según lo sugerido por el usuario mbomb007 .

El comportamiento deseado:

  1. La especie debe aprender qué colores son seguros y cuáles son malos.
  2. La especie debe enfocar principalmente su decisión hacia dónde moverse en función de las 3 celdas justo en frente, pero si no hay buenos movimientos disponibles, se deben considerar movimientos verticales o hacia atrás
  3. La especie también debe mirar lo que está más allá de las 8 celdas a su alrededor y usarlo en la información en la toma de decisiones.
  4. Las especies deben aprender a identificar trampas .
  5. Algunas especies suponen incorrectamente que las paredes son buenas y tratan de moverse hacia ellas todo el tiempo y, por lo tanto, se atascan frente a las paredes. Si son las especies con el puntaje más alto en ese momento, su ADN con la suposición equivocada sobre la pared se duplica muchas veces en los recién nacidos . Después de un tiempo, todas las especies están atrapadas frente a las paredes y ninguna de ellas alcanza la meta para ganar puntos. ¿Cómo detener a los imbéciles?

Métodos de almacenamiento de datos:

Queremos que la especie aprenda cosas, se adapte a su entorno, se convierta en el más apto. Inevitablemente, esto solo funciona si el aprendizaje se puede almacenar de alguna manera. El aprendizaje se 'almacenará' en los 100 bits de ADN. Es una forma extraña de almacenar, porque no podemos cambiar el valor de nuestro ADN. Por lo tanto, suponemos que el ADN ya almacena información de movimientos malos y buenos. Si para cierta especie se almacena la información correcta en su ADN, avanzará rápidamente y producirá muchas especies nuevas con su ADN.

Descubrí que la puntuación media geométrica es sensible a cómo se almacena la información. Supongamos que leemos los primeros 4 bits de los 100 bits de ADN y queremos almacenar esto en una variable entera. Podemos hacer esto de varias maneras:

  1. almacenamiento de datos decimales: mediante el uso de la función 'incorporada' dnarange, ejemplo: 4 bits 1011se convertirán en `1x2 ^ 3 + 0x2 ^ 2 + 1x2 ^ 1 + 1x2 ^ 0 = 15. Valores posibles (para 4 bits): [0, 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
  2. almacenamiento de datos de rayas: mediante el uso de la dnaStreakRangefunción (definida a continuación), ejemplo: 4 bits 1011 se convertirá 1x1 + 0x1 + 1x1+ 1x2 = 4. Valores posibles (para 4 bits): [0, 1, 2, 3, 6, 10]
int dnaStreakRange(dna_t &d, int start, int chunklen) {
    int score = 0;
    int streak = 0;
    for(int i = 0; i < chunklen; i++) {
        if(d[start + i])
            score += ++streak;
        else
            streak = 0;
    };  
    return score;
}
  1. almacenamiento de datos de bits: usando la dnaCountRangefunción (definida a continuación), por ejemplo: 4 bits 1011 se convertirá 1x1 + 0x1 + 1x1 + 1x1 = 3. Valores posibles (para 4 bits): [0, 1, 2, 3, 4]
int dnaCountRange(dna_t &d, int start, int chunklen) {
    int score = 0;
    for(int i = 0; i < chunklen; i++) {
        if(d[start + i])
            score ++;
    };  
    return score;
}

Las diferencias entre los métodos de almacenamiento son:

  • El método de almacenamiento decimal es vulnerable a un cambio de un solo bit en el ADN. Cuando el valor de la suma de bits cambia de 1011 a 0011, su valor cambia de 3 a 2, lo cual es un cambio menor.
  • El método de almacenamiento decimal es homogéneo . Cada uno de los valores posibles tiene el mismo cambio. La posibilidad de que lea el valor de 15 de un bloque de memoria de almacenamiento de 4 bits es 1/16 = 6%. El método de almacenamiento de rayas no es homogéneo . La posibilidad de que un valor de 4 bits de racha sea menor o igual que 6 es (15-3) / 16 = 81% (las 16 combinaciones excepto 0111,1110,111). Debajo de un visual que muestra la forma de la distribución. Como puede ver en la flecha azul, la probabilidad de que una racha de 4 bits sea menor o igual a 6 es del 81%: visualización de la distribución de los tipos de almacenamiento decimal, racha y suma de bits para números binarios largos de 4,5 y 6 bits

Priorizar soluciones.

Cuando ColorScorePlayer ha identificado dos movimientos hacia adelante con puntajes idénticos, se realiza una elección arbitraria. En mi humilde opinión, nunca debe utilizar la función de v.rng.rint()función aleatoria . En su lugar, debe usar esta oportunidad de puntajes iguales como un gancho para evaluar soluciones para efectos de segundo orden.

El efecto de primer orden obtiene la máxima prioridad. Si se alcanzan puntajes iguales, prevalece la solución con la prioridad 2 y así sucesivamente. Al ajustar los parámetros de una solución, puede influir en la posibilidad de que se obtengan puntajes iguales y de ese modo cambiar el peso de las soluciones de prioridad 1 y prioridad 2.

Implementación del comportamiento deseado

Aprenda qué colores son seguros:

  • El 33% de los 16 colores son malos y, por lo tanto, cuando la puntuación de un movimiento es inferior a 63/3, el movimiento no se permitirá. Por lo tanto threshold = 63/3=21, donde 63 es el puntaje máximo para 6 bits y 33% = 1/3 (puede consultarse en el gráfico anterior).

Si no hay movimientos buenos disponibles, muévase vertical o hacia atrás:

  • Cuando no se permiten movimientos hacia adelante, los movimientos verticales se compararán entre sí de la misma manera. Si tampoco se permiten movimientos verticales, se clasifican los movimientos hacia atrás. Esto se logra a través de la weightMovevariable.

Mira lo que hay más allá:

  • Cuando 2 o 3 movimientos tienen puntajes idénticos, el cuadro de 3x3 alrededor de esos movimientos determinará (a través de x2y y2bucles) cuál es la mejor opción (a través de la mainSubScorevariable). La columna más a la derecha en ese cuadro de 3x3 es líder.
coord_t adjustedColorPlayer(dna_t d, view_t v) {
    const int chunklen = 6,threshold = 63/3;
    int xBestScore=0, yBestScore=0;
    long bestScore=-1, weightMove, weightMove2, mainScore;
    for(int x = -1; x <= 1; x++) {
        if (x < 0) weightMove = 1000; // moving backward
        if (x== 0) weightMove = 10000; //moving vertical
        if (x > 0) weightMove = 100000; //moving forward
        for(int y = -1; y <= 1; y++) {
            if(v(x, y) == OUT_OF_BOUNDS || (x==0&&y==0) ) continue;
            mainScore = dnarange(d,v(x,y)*chunklen,chunklen);
            if (mainScore<threshold+1) {
                mainScore =  0; //not a suitable move because too low score
            }else{
                mainScore*= weightMove;
                // when equal score, use sub score by examining 5x5 box to rank moves
                for(int x2 = x-1; x2 <= x+1; x2++){     
                    if (x2 < x) weightMove2 = 1; // moving backward
                    if (x2== x) weightMove2 = 10; //moving vertical
                    if (x2 > x) weightMove2 = 100; //moving forward
                    for(int y2 = x-1; y2 <= y+1; y2++){     
                        if(v(x2, y2) != OUT_OF_BOUNDS){
                            long mainSubScore = dnarange(d,v(x2,y2)*chunklen,chunklen);
                            if (mainSubScore>=threshold+1) mainScore+=mainSubScore*weightMove2;
                        }
                    }
                 }
            }
            if(mainScore > bestScore) {
                bestScore = mainScore;              
                xBestScore = x;
                yBestScore = y;
            }
        }
    }
    return{xBestScore,yBestScore};
}

Puntuación: 123 (2K carreras)

Primeras 50 puntuaciones (18 juegos han anotado solo 1 punto):

1 10 1 79947 3 1 11 125 7333287 23701 310869 53744 1 2 2 2 2 1 1 57556 2 688438 60 1 2 2636261 26306 1 125369 1 1 1 61895 27 1 36 1 91100 87636 1 2 47497 53 16 1 11 222384 1 1 1

Identificar trampas:

Examiné el ADN de la especie con la puntuación más alta cuando un juego arbitrario terminó usando un almacenamiento de bitsum4 (por lo que la puntuación de color tiene un rango [0,4]):

  • puntuación 0: teletransporte hacia atrás, ambas paredes, 1x caja fuerte
  • puntuación 1: trampa hacia atrás (tan inofensiva), teletransporte hacia atrás, 1x seguro
  • puntuación 2: trampa hacia adelante (muy peligrosa), 1x seguro
  • puntuación 3: teletransporte hacia adelante, 5x seguro
  • puntuación 4: teletransporte hacia adelante, 1x seguro

De esto se puede concluir que las paredes y los teletransportes obtienen una puntuación correcta. Las trampas no se identifican ya que dependen de la dirección y del color de origen, mientras que la puntuación se realiza según el color de destino. Por lo tanto, también es necesario almacenar datos sobre el color de origen v(0,0). En un mundo ideal, nos gustaría almacenar información para 16 colores x 8 direcciones x 3 bits = 384 bits.

Desafortunadamente, solo hay 100 bits disponibles y no podemos usarlo todo, ya que también necesitamos algo de memoria para la solución explicada anteriormente. Por lo tanto, haremos 4 contenedores de colores:

  • 0: color 0 - color 3,
  • 1: color 4 - color 7,
  • 2: color 8 - color 11,
  • 3: color 12 - color 16

y 4 contenedores de dirección de movimiento

  • 0: mover vertical o hacia atrás,
  • 1: avanzar,
  • 2: avanzar,
  • 3: avanzar hacia abajo

Cuando el puntaje decimal es 4 o superior (100,101,110,111), se supone que hay una trampa asociada con esta celda, como resultado, este movimiento no se seleccionará cuando surjan puntajes iguales. Por lo tanto, la identificación de trampas es un efecto de segundo orden y el "mirar lo que está más allá" será una solución de tercera prioridad.

int dnaLookup2(dna_t &d, int start, int chunklen, int storageMethod) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    int score = 0, streak = 0;
    for(int i = start; i < start+chunklen; i++) {
        int value = d[i];
        if (storageMethod==0) {
            score = (score << 1) |value;
        }else{
            if (storageMethod==1){
                if(value) score += ++streak; else streak = 0;
            }else{
                if(value) score ++;         
            }
        }
    };  
    return score;
}

coord_t theTrapFighter(dna_t d, view_t v) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    const int colorMemStorageMethod = 1, colorMemBlockSize = 3;
    const int trapMemStorageMethod = 0, trapMemBlockSize = 3;
    const int trapMemTopThreshold = 4, nDirBins = 4, nColorBins = 4;

    int xBestScore=0, yBestScore=0;
    long bestScore=-1, weightMove, weightMove2, mainScore;
  for(int x = -1; x <= 1; x++) {
        if (x < 0) weightMove = 1000; // moving backward
        if (x== 0) weightMove = 10000; //moving vertical
        if (x > 0) weightMove = 100000; //moving forward
        for(int y = -1; y <= 1; y++) {          
            int color = v(x, y);
            if(color == OUT_OF_BOUNDS || (x==0&&y==0) ) continue;
            mainScore = dnaLookup2(d,color*colorMemBlockSize,
             colorMemBlockSize,colorMemStorageMethod);
            if (mainScore==0) {
                //not a suitable move because too low score
            }else{
                mainScore*= weightMove;
                //lookup trap likelihood
                int directionBin = 0;
                if (nDirBins==3) directionBin = x>0?y+1:-1;
                if (nDirBins==4) directionBin = x>0?y+2:0;
                // put 16 colors in nColorBins bins
                int colorBin = v(0,0)*nColorBins/N_COLORS; 
                colorBin = colorBin>(nColorBins-1)?(nColorBins-1):colorBin;
                if (directionBin >= 0 &&
                 dnaLookup2(
                   d,
                   colorMemBlockSize*16
                    +trapMemBlockSize*(nColorBins*directionBin+colorBin),
                   trapMemBlockSize,
                   trapMemStorageMethod
                 ) >=trapMemTopThreshold){
                  //suspect a trap therefore no sub score is added                  
                 }else{
                    // when equal score, use sub score by examining 5x5 box to rank moves
                    for(int x2 = x-1; x2 <= x+1; x2++){     
                        if (x2 < x) weightMove2 = 1; // moving backward
                        if (x2== x) weightMove2 = 10; //moving vertical
                        if (x2 > x) weightMove2 = 100; //moving forward
                        for(int y2 = x-1; y2 <= y+1; y2++){     
                            int color2 = v(x2, y2);
                            if(color2 != OUT_OF_BOUNDS){
                                mainScore+=weightMove2 * dnaLookup2(d,color2*colorMemBlockSize,
                                 colorMemBlockSize,colorMemStorageMethod);
                            }
                        }
                    }               
                 }
            }
            if(mainScore > bestScore) {
                bestScore = mainScore;              
                xBestScore = x;
                yBestScore = y;
            }
        }
    }
    return{xBestScore,yBestScore};
}

Puntuación: 580 (2K carreras)

Primeras 50 puntuaciones (13 juegos han marcado solo 1 punto)

28,044 14,189 1 2,265,670 2,275,942 3 122,769 109,183 401,366 61,643 205,949 47,563 138,680 1 107,199 85,666 31 2 29 1 89,519 22 100,908 14,794 1 3,198,300 21,601 14 3,405,278 1 1 1 2 74,167 1 71,242 97,331 201,080 1 1 102,9 1 255 1951,196 1 255

Supuestos erróneos sobre el muro se duplican muchas veces en recién nacidos por imbéciles:

Algunas especies suponen incorrectamente que las paredes son buenas y tratan de moverse hacia ellas todo el tiempo y, por lo tanto, se atascan frente a las paredes. También pueden quedar atrapados en bucles infinitos de teletransportadores. El efecto es el mismo en ambos casos.

El principal problema es que después de unos cientos de iteraciones, algunos genes se vuelven muy dominantes . Si estos son los genes 'correctos', puede obtener puntajes muy altos (> 1 millón de puntos). Si esto está mal, estás atrapado, ya que necesitas la diversidad para encontrar los genes 'correctos'.

Peleas de imbéciles: Solución 1: inversión de color

La primera solución que probé fue un esfuerzo por utilizar una parte de la memoria no utilizada que todavía es muy diversa. Supongamos que ha asignado 84 bits a su memoria de color y atrape la memoria de búsqueda. Los 16 bits restantes serán muy diversos. Podemos llenar 2 variables decimal8 que tienen valores en el intervalo [0,255] y son homogéneas, lo que significa que cada valor tiene una probabilidad de 1/256. Las variables se llamarán inInversey inReverse.

Si inInversees igual a 255 (una probabilidad de 1/256), invertiremos la interpretación de las puntuaciones de color . Por lo tanto, el muro que el imbécil supone que es seguro debido a su alto puntaje, obtendrá un puntaje bajo y, por lo tanto, se convertirá en un mal movimiento. La desventaja es que esto también afectará a los genes de 'derechos', por lo que tendremos puntuaciones menos altas. Además, esta inInverseespecie tendrá que reproducirse y sus hijos también obtendrán partes del ADN dominante. La parte más importante es que recupera la diversidad.

Si inReversees igual a 255 (una probabilidad de 1/256), invertiremos el orden de las posiciones de almacenamiento de las puntuaciones de color . Entonces, antes del color 0 se almacenaba en los bits 0-3. Ahora el color 15 se almacenará en esa posición. La diferencia con el inInverseenfoque es que inReversedeshacerá el trabajo realizado hasta ahora. Estamos de vuelta en el punto de partida. Hemos creado una especie que tiene genes similares a cuando comenzó el juego (a excepción de la trampa para encontrar memoria)

A través de la optimización, se prueba si es aconsejable utilizar inInversey inReverseal mismo tiempo. Después de la optimización, se concluyó que la puntuación no aumentó. El problema es que tenemos una población de gen más diversa, pero esto también afecta el 'ADN correcto'. Necesitamos otra solución.

Peleas de imbéciles: Solución 2: código hash

La especie tiene 15 posiciones iniciales posibles y actualmente hay una posibilidad demasiado grande de que siga exactamente el mismo camino si comienza en la misma posición inicial. Si es un imbécil que ama las paredes, se quedará atrapado en la misma pared una y otra vez. Si por suerte logra llegar a un muro más adelante, comenzará a dominar el conjunto de ADN con sus suposiciones equivocadas. Lo que necesitamos es que su descendencia siga un camino ligeramente diferente (ya que para él es demasiado tarde de todos modos), y no se quedará atrapado en el muro más adelante, sino en un muro más cercano . Esto se puede lograr mediante la introducción de un código hash .

Un código hash debe tener el propósito de identificar y etiquetar de manera única la posición actual en el tablero. El propósito no es averiguar cuál es la posición (x, y), sino responder las preguntas que han tenido mis antepasados ​​en este lugar.

Supongamos que tendría el tablero completo frente a usted y haría un jpg de cada cuadrado posible de 5 por 5 celdas. Terminarías con (53-5) x (15-5) = 380 imágenes. Démosle a esas imágenes números del 1 al 380. Nuestro código hash debe verse como una ID, con esa diferencia de que no se ejecuta del 1 al 330, pero le faltan IDS, por ejemplo, 563, 3424, 9424, 21245, etc.

unsigned long hashCode=17;
for(int x = -2; x <= 2; x++) {
    for(int y = -2; y <= 2; y++) {
        int color = v(x, y)+2;
        hashCode = hashCode*31+color;
    }
}       

Los números primos 17y 31están ahí para evitar que la información agregada al principio en el ciclo desaparezca. Más adelante sobre cómo integrar nuestro hashcode en el resto del programa.

Vamos a reemplazar el mecanismo de grabación de "mirar lo que está más allá" con otro mecanismo de grabación. Cuando dos o tres celdas tienen puntajes principales iguales, habrá un 50% de posibilidades de que se escoja el superior, un 50% de posibilidades de que se elijan las celdas inferiores y un 0% de posibilidades de que se escoja el medio. La posibilidad no estará determinada por el generador aleatorio, sino por bits de la memoria , ya que de esa manera nos aseguramos de que en la misma situación se haga la misma elección.

En un mundo ideal (donde tenemos una cantidad infinita de memoria), calcularíamos un código hash único para nuestra situación actual, por ejemplo, 25881, iríamos a la ubicación de memoria 25881 y leeríamos allí si debemos elegir la celda superior o inferior (cuando hay es un puntaje igual) De esa manera, estaríamos exactamente en la misma situación (cuando, por ejemplo, viajamos por el tablero por segunda vez y comenzamos en la misma posición), tomaremos las mismas decisiones. Como no tenemos memoria infinita, aplicaremos un módulo del tamaño de la memoria disponible al código hash . El hashcode actual es bueno en el sentido de que la distribución después de la operación del módulo es homogénea.

Cuando la descendencia viaja por el mismo tablero con ADN ligeramente modificado, en la mayoría de los casos (> 99%) tomará exactamente la misma decisión. Pero cuanto más se acerca, mayor es la posibilidad de que su camino sea diferente de sus antepasados. Por lo tanto, la posibilidad de que se quede atrapado en este muro muy por delante es pequeña. Mientras se atasca en la misma pared cercana que su antepasado es relativamente grande, pero esto no es tan malo, ya que no generará mucha descendencia. Sin el enfoque de código hash , la posibilidad de quedar atrapado en la pared cercana y lejana es casi la misma.

Mejoramiento

Después de la optimización, se concluyó que la tabla de identificación de trampas no es necesaria y que 2 bits por color son suficientes. El resto de la memoria 100-2x16 = 68 bits se usa para almacenar el código hash. Parece que el mecanismo del código hash puede evitar trampas.

He optimizado para 15 parámetros. Este código incluye el mejor conjunto de parámetros modificados (hasta ahora):

int dnaLookup(dna_t &d, int start, int chunklen, int storageMethod,int inInverse) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    int score = 0;
    int streak = 0;
    for(int i = start; i < start+chunklen; i++) {
        int value = d[i];
        if (inInverse) value = (1-d[i]);            
        if (storageMethod==0) {
            score = (score << 1) |value;
        }else{
            if (storageMethod==1){
                if(value) score += ++streak; else streak = 0;
            }else{
                if(value) score ++;         
            }
        }
    };  
    return score;
}

coord_t theFittest(dna_t d, view_t v) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    const int colorMemStorageMethod = 2, colorMemBlockSize = 2, colorMemZeroThreshold = 0;
    const int useTrapMem = 0, trapMemStorageMethod = -1, trapMemBlockSize = -1;
    const int trapMemTopThreshold = -1, nDirBins = -1, nColorBins = -1;
    const int reorderMemStorageMethod = -1, reorderMemReverseThreshold = -1;
    const int reorderMemInverseThreshold = -1;
    // Definition of hashPrority: -1: no hash, 0:hash when 'look beyond' scores equal,
    // 1: hash replaces 'look beyond', 2: hash replaces 'trap finder' and 'look beyond'
    // 3: hash replaces everything ('color finder', 'trap finder' and 'look beyond')
    const int hashPrority = 2;
    int inReverse = reorderMemReverseThreshold != -1 && 
     (dnaLookup(d,92,8,reorderMemStorageMethod,0) >= reorderMemReverseThreshold);
    int inInverse = reorderMemInverseThreshold != -1 && 
     (dnaLookup(d,84,8,reorderMemStorageMethod,0) >= reorderMemInverseThreshold);
    int trapMemStart=N_COLORS*colorMemBlockSize;
    unsigned long hashCode=17;
    int moveUp=0;
    if (hashPrority>0){
        for(int x = -2; x <= 2; x++) {
            for(int y = -2; y <= 2; y++) {
                int color = v(x, y)+2;
                hashCode = hashCode*31+color;
            }
        }       
        unsigned long hashMemStart=N_COLORS*colorMemBlockSize;
        if (useTrapMem==1 && hashPrority<=1) hashMemStart+=nDirBins*nColorBins*trapMemBlockSize;
        if (hashPrority==3) hashMemStart=0;
        int hashMemPos = hashCode % (DNA_BITS-hashMemStart);
        moveUp = dnaLookup(d,hashMemStart+hashMemPos,1,0,inInverse);
    }

    int xBestScore=0, yBestScore=0;
    long bestScore=-1, weightMove, weightMove2, mainScore;
    for(int x = -1; x <= 1; x++) {
        if (x < 0) weightMove = 1000; // moving backward
        if (x== 0) weightMove = 10000; //moving vertical
        if (x > 0) weightMove = 100000; //moving forward
        for(int y = -1; y <= 1; y++) {          
            int color = v(x, y);
            if (inReverse) color = 15-v(x, y);
            if(color == OUT_OF_BOUNDS || (x==0&&y==0) ) continue;
            //when MoveUp=1 -> give move with highest y most points (hashScore=highest)
            //when MoveUp=0 -> give move with lowest y most points (hashScore=lowest)
            int hashScore = (y+2)*(2*moveUp-1)+4; 
            mainScore = dnaLookup(
              d,
              color*colorMemBlockSize,
              colorMemBlockSize,
              colorMemStorageMethod,
              inInverse
             );
            if (mainScore<colorMemZeroThreshold+1) {
                mainScore =  0; //not a suitable move because too low score
            }else{
                mainScore*= weightMove;
                //lookup trap likelihood
                int directionBin = 0;
                if (nDirBins==3) directionBin = x>0?y+1:-1;
                if (nDirBins==4) directionBin = x>0?y+2:0;
                // put 16 colors in nColorBins bins
                int colorBin = v(0,0)*nColorBins/N_COLORS; 
                if (inReverse) colorBin = (15-v(0,0))*nColorBins/N_COLORS; 
                colorBin = colorBin>(nColorBins-1)?(nColorBins-1):colorBin;
                if (useTrapMem && directionBin >= 0 &&
                 dnaLookup(
                   d,
                   trapMemStart+trapMemBlockSize*(nColorBins*directionBin+colorBin),
                   trapMemBlockSize,
                   trapMemStorageMethod,
                   0
                 )>=trapMemTopThreshold){
                  //suspect a trap therefore no sub score is added                  
                 }else{
                    if (hashPrority>=1){
                        mainScore+=hashScore;
                    } else{
                        // when equal score, use sub score by examining 5x5 box to rank moves
                        for(int x2 = x-1; x2 <= x+1; x2++){     
                            if (x2 < x) weightMove2 = 1; // moving backward
                            if (x2== x) weightMove2 = 10; //moving vertical
                            if (x2 > x) weightMove2 = 100; //moving forward
                            for(int y2 = x-1; y2 <= y+1; y2++){     
                                int color2 = v(x2, y2);
                                if (inReverse) color2 = 15-v(x2, y2);
                                if(color2 != OUT_OF_BOUNDS){
                                    long mainSubScore = dnaLookup(
                                      d,
                                      color2*colorMemBlockSize,
                                      colorMemBlockSize,
                                      colorMemStorageMethod,
                                      inInverse
                                    );
                                    if (mainSubScore>=colorMemZeroThreshold+1){
                                        mainScore+=mainSubScore*weightMove2;
                                    }
                                }
                            }
                        }
                    }               
                 }
            }
            if (hashPrority==2 || (useTrapMem<=0 && hashPrority>=1)) mainScore+=hashScore*10;
            if (hashPrority==3) mainScore=hashScore*weightMove;         

            if(mainScore > bestScore) {
                bestScore = mainScore;              
                xBestScore = x;
                yBestScore = y;
            }
        }
    }
    return{xBestScore,yBestScore};
}   

Puntuación: 922 (2K carreras)

Primeras 50 puntuaciones (9 juegos han marcado solo 1 punto):

112,747 3 1 1,876,965 8 57 214,921 218,707 2,512,937 114,389 336,941 1 6,915 2 219,471 74,289 31 116 133,162 1 5 633,066 166,473 515,204 1 86,744 17,360 2 190,697 1 6 122 126,399 399,045 1 4,172,168 1 169,119 4,990 77,432 5672,168 1 169,119 4,990 77,432 236

Este es mi primer programa C ++. Como la mayoría de ustedes ahora tengo experiencia en análisis de gnomos. Quiero agradecer a los organizadores, ya que realmente disfruté trabajando en esto.

Si tiene algún comentario, deje un comentario a continuación. Disculpas por los largos textos.

Ruut
fuente
Su análisis de trampa me parece bastante interesante.
¿Intentó con otra función hash, como por ejemplo grabar los 25 valores de color vistos como palabras de 12.5 16 bits y tomar un módulo? No estoy convencido de que la congruencia de números primos proporcione una mejor homogeneidad, pero no soy un gran matemático.
Además, ¿consideró agregar un algoritmo de ruta? Parece ser un gran factor de mejora independientemente del genoma, ya que limitará los movimientos a los que prueban la capacidad del genoma solo a lo largo de caminos que tienen muchas más probabilidades de conducir a una posición ganadora.
Kuroi, gracias por sus comentarios. No probé el xoring, ya que no estoy tan familiarizado con las operaciones binarias en c ++. Supongo que te refieres a 12.5 palabras de 8 bits? ¿Estás usando xoring?
Ruut
Puede consultar mi código de "creyentes duros" para ver qué tipo de función hash uso. Básicamente, omito las celdas fuera de la pista y considero los colores en la pista como partes de orden superior e inferior de una palabra de 16 bits. Todas estas palabras se acumulan con XOR en un registro que luego se divide por el tamaño de la tabla hash. Siempre que el valor máximo de hash (65535) sea mucho mayor que el tamaño de la tabla (<100), el módulo tiene un buen poder de propagación. Lo probé en un amplio conjunto de cuadrículas generadas aleatoriamente y parece tener una buena homogeneidad.
6

Pathfinder, C ++, puntaje preliminar 35.8504 (50 rondas)

¡Una revisión completa! Porté mi algoritmo a C ++ y lo ajusté un poco, pero el puntaje aún no es muy alto, probablemente porque las ratas siguen golpeando sus cabezas contra las paredes. Estoy cansado de tratar de mejorar esto, así que lo dejaré por ahora.


int dnarange(dna_t &d, int start, int len) {
    int res = 0;
    for(int i = start; i < start+len; i++) {
        res = (res << 1) | d[i];
    }
    return res;
}

int dnasum(dna_t &d, int start, int len) {
    int res = 0;
    for(int i = start; i < start+len; i++) {
        res += d[i];
    }
    return res;
}

int dnaweight(dna_t &d, int start) {
    return d[start] + d[start+1] + 2*d[start+2] + 2*d[start+3] + 3*d[start+4];
}

int trap_d [16] = {1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1}; //immutable
int nhood [10] = {1,0,1,1,1,-1,0,1,0,-1}; //immutable

coord_t pathfinder(dna_t d, view_t v) {
  int is_trap[16] = {0};
  int pos_or_weight[16] = {0};
  int u_weight = dnaweight(d, 80);
  for (int i = 0; i < 16; i++) {
    int status = dnarange(d, 5*i, 2);
    if (status == 1) {
      is_trap[i] = 1;
      pos_or_weight[i] = dnarange(d, 5*i + 2, 3);
    } else {
      pos_or_weight[i] = dnaweight(d, 5*i);
    }
  }
  int w_area[7][4] = {0};
  for (int j = 0; j < 7; j++) {
    w_area[j][3] = u_weight;
  }
  for (int i = 0; i < 3; i++) {
    w_area[0][i] = u_weight;
    w_area[6][i] = u_weight;
  }
  int d_coeff = dnaweight(d, 85);
  for (int i = 0; i < 3; i++) {
    for (int j = 1; j < 6; j++) {
      int p_or_w, color = v(i, j-3);
      if (color != OUT_OF_BOUNDS) {
    p_or_w = pos_or_weight[color];
      } else {
    p_or_w = 1000;
      }
      if (color != OUT_OF_BOUNDS && is_trap[color] && i+trap_d[2*p_or_w] >= 0) {
    w_area[j + trap_d[2*p_or_w + 1]][i + trap_d[2*p_or_w]] += d_coeff;
      } else {
    w_area[j][i] += p_or_w;
      }
    }
  }
  for (int i = 3; i >= 0; i--) {
    for (int j = 0; j < 7; j++) {
      int min_w = 1000;
      for (int k = std::max(0, j-1); k <= std::min(6, j+1); k++) {
    min_w = std::min(min_w, w_area[k][i + 1]);
      }
      w_area[j][i] += min_w;
    }
  }
  int speed = dnasum(d, 90, 5);
  w_area[2][0] += 2 + speed;
  w_area[4][0] += 2 + speed;
  int goal = dnaweight(d, 95);
  int min_w = 10000;
  int sec_w = 10000;
  int min_x, min_y, sec_x, sec_y, w;
  for (int i = 0; i < 5; i++) {
    w = w_area[nhood[2*i + 1] + 3][nhood[2*i]];
    if (w < min_w) {
      sec_w = min_w;
      sec_x = min_x;
      sec_y = min_y;
      min_w = w;
      min_x = nhood[2*i];
      min_y = nhood[2*i + 1];
    } else if (w < sec_w) {
      sec_w = w;
      sec_x = nhood[2*i];
      sec_y = nhood[2*i + 1];
    }
  }
  if (min_w > goal) {
    int r = v.rng.rint(5);
    return {nhood[2*r], nhood[2*r+1]};
  } else if (sec_w <= goal && v.rng.rint(100) < 2*speed) {
    return {sec_x, sec_y};
  }
  return {min_x, min_y};
}

Explicación

La idea general es clasificar cada color como una trampa o no, luego asignar direcciones a las trampas y pesos a las no trampas, e intentar seguir la ruta de peso mínimo hasta el borde derecho de la cuadrícula de visión.

En los primeros 80 bits del genoma, cada color se clasifica utilizando 5 bits abcde. Si ab = 01, el color es una trampa y cdecodifica su dirección (ocho posibilidades). Si ab ≠ 01, el color no es una trampa, y su peso sí a + b + 2*(c + d + e).

A continuación, inicializamos una cuadrícula de 3x7, que representa el campo de visión de la rata a su derecha, rellenada con colores "desconocidos". Los bits 80-84 codifican el peso de las celdas desconocidas de manera similar a los colores sin trampa, y los bits 85-89 codifican un peso común para las trampas. Llenamos la cuadrícula con los pesos, calculamos las rutas más cortas y agregamos un poco de peso adicional (codificado en los bits 90-95) a las celdas directamente encima y debajo de la rata para desalentar el paso lateral. Los bits 95-99 codifican un peso objetivo. Si el peso mínimo de un camino está debajo de él, la rata probablemente esté atrapada en algún lugar y proceda a moverse al azar (pero nunca retrocede). De lo contrario, sigue la ruta de peso mínimo. Con una pequeña probabilidad dependiendo del peso que evita el paso lateral, la rata elige la ruta de peso del segundo al mínimo. Esto es para evitar quedarse atascado en las paredes (pero parece que no funciona muy bien en este momento).

Zgarb
fuente
Ejecuté su implementación en mi computadora. Tomó algunas horas. Obtiene un puntaje promedio de 7.848433940863856 puntos. pastebin.com/d50GcwnK
Jakube
@Jakube Muchas gracias! Eso es mucho peor de lo que esperaba, pero ahora que miro el código nuevamente, veo varios errores y otras rarezas. Intentaré portar esto a C ++ más tarde para poder analizarlo yo mismo.
Zgarb
5

LookAheadPlayer C ++ ≈ 89.904

Mi idea original era buscar 4 bits que coincidieran con el color que estaba buscando, y usar los siguientes bits como puntaje. Esto resultó ser una idea terrible, probablemente debido a mutaciones.

Así que pensé en formas de protección contra mutaciones y cruces, y me recordó sobre el trabajo que he realizado en la decodificación de códigos QR. En los códigos QR, los datos se dividen en bloques y se cortan para evitar que los errores destruyan demasiada parte de los datos.

Por lo tanto, al igual que ColorScorePlayer, corté el ADN en 16 fragmentos y los utilicé como la puntuación dada. Sin embargo, las puntuaciones están divididas de manera que los bits individuales de cada puntuación no sean adyacentes. Luego sumo el puntaje de los movimientos posibles actuales y los próximos movimientos potenciales y elijo el mejor movimiento para hacer.

Nota: esto fue codificado / probado en MinGW. No se compilaría con optimizaciones o con subprocesos múltiples. No tengo una instalación real de Linux o Visual Studio a mano para usar un compilador donde estos funcionen. Lo probaré rápidamente mañana por la mañana, pero avíseme si tiene algún problema.

// get striped color score, 6 bits per color. should be
// resistant to getting erased by a crossover
void mapColorsBitwise(dna_t &d, int* color_array) {
    for (int i=0; i<N_COLORS; i++) {
        int score = 0;
        for (int j=0; j<6; j++) {
            score = (score<<1) | d[ j*N_COLORS + i ];
        }
        color_array[i] = score;
    }
}

// label for the lookup tables
enum direction_lut {
    UP_RIGHT=0, RIGHT, DOWN_RIGHT
};

// movement coord_t's to correspond to a direction
static const coord_t direction_lut[3] = {
    { 1, -1 }, { 1, 0 }, { 1, 1 }
};

// indexes into the arrays to denote what should be summed
// for each direction.
static const int sum_lut[3][6] = {
    { 3, 4, 8, 8, 9, 14 }, { 9, 13, 13, 14, 14, 19 },
    { 14, 18, 18, 19, 23, 24 }
};

coord_t lookAheadPlayer(dna_t d, view_t v) {
    int scoreArray[25] = { 0 };
    int colorScores[N_COLORS] = { };

    // Get color mapping for this iteration
    mapColorsBitwise(d, colorScores);

    for (int y=-2; y<=2; y++) {
        for (int x=0; x<=2; x++) {
            // Get the scores for our whole field of view
            color_t color = v(x,y);
            if (color != OUT_OF_BOUNDS)
                scoreArray[ (x+2)+((y+2)*5) ] += colorScores[color];
        }
    }

    // get the best move by summing all of the array indices for a particular
    // direction
    int best = RIGHT;
    int bestScore = 0;
    for (int dir=UP_RIGHT; dir<=DOWN_RIGHT; dir++) {
        if (v(direction_lut[dir].x, direction_lut[dir].y) == OUT_OF_BOUNDS)
            continue;

        int score = 0;
        for (int i=0; i<6; i++) {
            score += scoreArray[ sum_lut[dir][i] ];
        }

        if (score > bestScore) {
            bestScore = score;
            best = dir;
        }
    }

    return direction_lut[best];
}
Aschmack
fuente
5

SlowAndSteady C ++ (puntaje 9.7)

No podemos confiar en interpretar fragmentos del genoma como números porque un solo cambio de bit puede tener efectos radicalmente diferentes dependiendo de su posición. Es por eso que simplemente uso 16 segmentos de 6 bits y los califico en el número de 1s. Inicialmente 111111era bueno y 000000malo, y aunque no importa a largo plazo (una vez que el genoma está completamente evolucionado) en la configuración inicial del ADN, la mayoría de los segmentos tienen de 2 a 4, así que cambié a usar 9 - (#1 - 3)^2para puntuación, esto permite mucha más libertad de movimiento en las primeras rondas y una evolución más rápida.

En este momento solo miro a los 7 vecinos más cercanos, agrego un sesgo de dirección a la puntuación de color y me muevo en una de las direcciones más altas al azar.

Aunque el puntaje en sí no es muy alto, mis bichos alcanzan la línea de meta y obtienen un puntaje> 1 en 3/4 de los casos.

coord_t SlowAndSteadyPlayer(dna_t d, view_t v) {
    const int chunklen = 6;
    int color_scores[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    for(int i=0; i<16; i++){ //count ones
        for(int j=0; j<chunklen; j++){
            color_scores[i] += d[i*chunklen + j];
        }
    }

    int moves[7][2] = {
        {-1,1}, {0,1}, {1,1},
                       {1,0},
        {-1,-1},{1,-1},{-1,-1}
    };
    int movescores[7];
    int smax = -1;
    int nmax = 0;
    int best_moves[7];
    for(int m=0; m<7; m++){ //compute the score for each move
        int temp_color = v(moves[m][0], moves[m][1]);
        if(temp_color == OUT_OF_BOUNDS){
            movescores[m] = 0;
            continue;
        }
        int dir_bias[3] = {1,3,6};
        int temp_score = 9-(color_scores[temp_color]-3)*(color_scores[temp_color]-3) + dir_bias[moves[m][0]+1];
        movescores[m] = temp_score;

        if(temp_score > smax) {
            smax = temp_score;
            nmax = 0;
        }
        if(temp_score == smax) best_moves[nmax++] = m;
    }

    int best_chosen = v.rng.rint(nmax);
    return {moves[best_moves[best_chosen]][0], moves[best_moves[best_chosen]][1]};
}

Y una muestra de puntuación en 100 tableros

Scores: 5 4 13028 1 1 101 2 24 1 21 1 4 2 44 1 1 24 8 2 5 1 13 10 71 2 19528 6 1 69 74587 1 1 3 138 8 4 1 1 17 23 1 2 2 50 7 7 710 6 231 1 4 3 263 4 1 6 7 20 24 11 1 25 1 63 14 1 2 2 1 27 9 7 1 7 31 20 2 17 8 176 3 1 10 13 3 142 1 9 768 64 6837 49 1 9 3 15 32 10 42 8

Puntuación media geométrica: 9.76557

DenDenDo
fuente
¿La puntuación que menciona para un tablero utiliza la tasa de mutación estándar o su valor ajustado?
trichoplax
"mis bichos alcanzan la línea de meta y marcan> 1 en 3/4 de los casos" Deseo que la métrica de puntuación recompense esto
Sparr el
5

WeightChooser | C # | Puntajes: 220.8262 en 1520 juegos

Calcula el peso para el posible próximo movimiento (azul) en función del peso promedio de los posibles movimientos seguidos (amarillo)

using ppcggacscontroller;
using System.Linq;
using System;

public class WeightChooser
{
    public static ppcggacscontroller.Program.Coord[] cspcoords = new[] {
            new Program.Coord(1, -1),
            new Program.Coord(1, 0),
            new Program.Coord(1, 1),
        };

    const int dnaBits = 4;

    public static void move(GameLogic.IView v, GameLogic.IGenome g, Random rnd, out int ox, out int oy)
    {
        var gcrds = cspcoords.Where(c => viewVal(v, c) > -1)
            .OrderByDescending(p => getBitsSet(g, viewVal(v, p)))
            .ThenByDescending(gt => weight(v, g, gt));

        Program.Coord nextMove = gcrds.First();
        ox = nextMove.x;
        oy = nextMove.y;
    }

    private static uint getBitsSet(GameLogic.IGenome g, int vVal)
    {
        uint i = g.cutOutInt(dnaBits * vVal, dnaBits);
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

    private static int viewVal(GameLogic.IView v, Program.Coord c)
    {
        return v[c.x, c.y];
    }

    private static double weight(GameLogic.IView v, GameLogic.IGenome g, Program.Coord toGo)
    {
        double w = 0;

        int y = (toGo.y + v.yd) - 1;
        int i = 0;
        for (; i <= 2; i++)
        {
            int field = v[toGo.x + 1, (y + i) - v.yd];
            if (field > -1)
                w += getBitsSet(g, field);
        }

        return w / i;
    }
}

Scores: 32, 56103, 1361, 3351446, 33027, 23618, 22481, 1172713, 1, 3, 1, 1, 1, 2 88584, 106357, 1, 1232, 1, 1651280, 16690, 1, 1, 23732, 207554, 53, 69424, 1, 1,  79361, 1, 1, 51813, 229624, 25099, 2, 1, 234239, 362531, 1, 1, 19, 7295, 1, 7, 2, 196672, 1654208, 73453, 1, 23082, 1, 8, 5, 1685018, 4, 20, 1, 1, 1, 1, 1, 144 671, 122309, 10, 94752, 100895, 1, 54787, 54315, 252911, 79277, 1159, 241927, 94 347, 1, 318372, 37793, 1, 1, 1345310, 18934, 169700, 1, 1, 3, 186740, 83018, 121 758, 1, 358, 1935741, 88, 1, 1, 1, 1, 7, 21, 51144, 2, 1, 267638, 1, 1, 3, 1, 1,  1, 1, 674080, 47211, 8879, 7, 222766, 67214, 2, 89, 21038, 178463, 92846, 3, 14 0836, 1, 1, 111927, 1, 92165, 1, 192394, 1, 1, 2563722, 1, 42648, 1, 16, 1, 1, 2 85665, 1, 212653, 1, 4, 20513, 3, 135118, 13161, 2, 57, 78355, 3, 3, 44674, 8, 1 , 226472, 1, 1, 31588, 19619, 1, 2931870, 60814, 1, 1, 33867, 60740, 20558, 1, 1 5, 3, 5, 1, 1, 1, 60737, 450636, 468362, 1, 1, 347193, 91248, 551642, 1, 427215,  1, 57859, 17, 15, 66577, 24192, 1, 63560, 6568, 40279, 68216, 23098, 180732, 1,  1, 3041253, 1, 253488, 60535, 1, 1, 150838, 7361, 72855, 290699, 104644, 1, 763 01, 378, 1, 89220, 1, 262257, 2, 2, 1, 117, 105478, 33, 1, 65210, 1, 117588, 1, 1, 24320, 12, 3714568, 81152, 1, 1, 10125, 2, 1, 22, 1, 45201, 1, 1, 10518, 1, 1 , 1, 1, 34, 210021, 1, 1, 1, 65641, 6, 72, 1, 7, 2, 161578, 1, 1, 38378, 1, 4113 741, 1, 34450, 244212, 127660, 1, 256885, 46, 2, 1, 1, 103532, 1, 503965, 114774 , 52450, 124165, 73476, 50250, 1, 3, 3755352, 24928, 1, 1, 51, 11, 1, 210580, 1,  62375, 1, 1, 92745, 341232, 167675, 86, 242, 293710, 454841, 1, 49840, 4456758,  121378, 145323, 74904, 5048, 25459, 1, 57, 116999, 1, 1, 76074, 111447, 95706, 1, 1, 52631, 166756, 2159474, 161216, 1, 2, 3, 11904, 1, 22050, 6, 1, 1, 1, 41, 48908, 6, 80878, 28125, 28, 160516, 1, 4, 1, 8, 1, 1, 7, 362724, 1, 397193, 1, 2 5, 1, 59926, 3, 74548, 2320284, 470189, 1, 108, 1, 1, 16, 1, 496013, 1, 1, 1, 1,  107758, 1, 284144, 146728, 1, 70769, 94215, 1, 1, 9961, 97300, 7, 1, 76263, 1, 27, 294046, 40, 8, 2, 1, 57796, 2, 79800, 1043488, 470547, 1, 1, 1, 6, 69666, 8,  1, 1, 344011, 205325, 3963186, 1141527, 61598, 446029, 1, 1, 1, 1, 625247, 1877 92, 136391, 1, 72519, 1, 141168, 412, 98491, 103995, 297052, 1, 1, 1, 1, 3, 17, 9, 62899, 5, 47810, 254, 26789, 2, 1, 1, 3, 10361, 19615, 40430, 17288, 3, 71831 , 41374, 1, 91317, 409526, 1, 184305, 1, 192552, 3, 3587674, 39, 13, 134500, 41,  42, 672, 559835, 9, 39004, 51452, 1, 1, 12293, 11544, 265766, 8590, 1, 8632, 1,  1, 61849, 35155, 1, 74798, 72773, 1, 89, 37, 4, 4405882, 1, 99, 44397, 5, 4, 6,  1, 1, 1, 515818, 78383, 20, 127829, 1824801, 157, 1, 1, 268561, 19, 2, 230922, 1, 103, 98146, 5029789, 304324, 1, 5, 60516, 1, 139, 28982, 7, 20755, 187083, 1,  1, 143811, 37697, 1, 1, 269819, 83, 1, 202860, 13793, 16438, 113432, 1, 1, 2, 5 134384, 29, 84135, 39035, 2, 125, 1, 30, 129771, 41982, 13548, 61, 1, 2, 1, 82, 102, 2, 105581, 210399, 291204, 3012324, 1, 84763, 1, 1, 442067, 2, 1, 1, 1, 116 , 1, 3, 3, 56, 208807, 1, 2, 1, 14, 29, 31286, 1, 1, 162358, 28856, 46898, 1, 16 2698, 1, 1, 1, 65, 1, 1, 234566, 6, 1, 1, 128, 124, 2167692, 181946, 29, 1, 1, 1 , 1, 17, 162550, 179588, 4, 226480, 28, 1, 158512, 35084, 1, 26160, 17566, 1, 81 826, 2, 33, 1, 1, 11, 1, 230113, 1, 1, 1, 24405, 17, 1, 2, 1, 162365, 2, 1, 1, 8 5225, 1, 15016, 51509, 1, 5, 1, 93, 13, 59, 24548, 1, 3, 2, 2, 1, 64424, 1, 1, 4 , 1, 1, 1, 2, 267115, 139478, 52653, 96225, 1, 1, 35768, 3, 1, 1, 3280017, 8, 80 014, 43095, 112102, 1, 1, 1, 79594, 5, 1, 1, 4, 455714, 19, 15, 1, 233760, 55850 5, 2, 2, 1, 63672, 1, 3732951, 1, 135858, 134256, 452456, 151573, 79057, 638215,  88820, 1, 1, 76517, 13, 314006, 5, 1, 17704, 1, 79589, 1, 18371, 530793, 59020,  1, 1, 1, 4, 1, 1, 1, 71735, 1, 1, 1, 1, 1, 37894, 1, 2, 24054, 1, 8, 26471, 34,  1, 48033, 5, 3, 1, 25, 101, 1, 1, 5, 1, 1, 1, 97521, 1, 682817, 286486, 5, 1472 4, 1, 7805226, 6, 1, 1, 1, 7, 2, 1, 1, 1, 25, 233330, 1, 20899, 3417337, 92793, 23, 80821, 1, 1, 115948, 264191, 3, 79809, 1, 2, 59531, 2, 1, 1, 28684, 97, 1, 2 69433, 98769, 1, 76608, 138124, 1, 1, 325554, 122567, 1, 1, 3, 689604, 4, 85823,  66911, 138091, 169416, 21430, 1, 2, 486654, 108446, 93072, 1, 67907, 4, 1, 1, 5 2260, 67867, 210496, 25157, 1, 1, 1, 5477, 2, 2, 11907, 106, 48404, 1, 1, 1, 787 11, 190304, 112025, 1, 9313, 143055, 40189, 315537, 157581, 70714, 6, 180600, 38 594, 103658, 59444, 7, 31575, 1, 1, 581388, 370430, 1, 114446, 1, 1, 2, 3968, 1,  1, 1, 1, 1, 4523411, 1, 1, 270442, 1, 59, 235631, 3, 110196, 9, 1, 93724, 1, 22 917, 1, 6, 1, 2350266, 1, 1, 20, 4686858, 31, 1, 240180, 10, 470592, 3, 61051, 1 45372, 2831, 64052, 10, 120652, 255971, 479239, 1, 387659, 1, 1, 1, 378379, 7, 3 3218, 55914, 1, 1, 1667456, 6, 2, 74428, 3, 2, 1, 121582, 121274, 19651, 59899, 1, 11, 406670, 137835, 100269, 2, 164361, 98762, 44311, 25817, 178053, 31576, 1,  8, 2539307, 121430, 1, 41001, 1, 4, 1, 116258, 91101, 1, 126857, 1, 8, 49503, 1 , 489979, 12, 500332, 1, 52, 4, 8786, 4, 4878652, 12354, 27480, 89115, 87560, 11 793, 5, 1, 4702325, 301188, 1, 1, 1, 1, 1, 416520, 49357, 230103, 24497, 1, 3, 2 , 57366, 183021, 1, 1, 1, 1, 1, 2, 2, 2546229, 1, 2, 38665, 1, 6903, 1, 89519, 9 5119, 64879, 1, 1, 160380, 474336, 3107, 1, 7, 29099, 28667, 3, 196933, 35979, 1 2924, 7, 1, 99885, 6, 1, 1, 1, 7, 1, 1, 1, 1, 65727, 1, 1, 1, 1, 2108110, 3, 107 811, 23818, 701905, 1, 156034, 32, 1, 29, 143548, 1, 67665, 4612762, 1, 3, 20, 1 , 1, 9, 28543, 1, 1, 1, 30978, 9, 1, 19504, 79412, 15375, 763265, 1, 352373, 193 045, 1, 4570217, 9, 1, 6, 29180, 90030, 1, 1, 1, 1, 1, 93, 1, 100889, 1, 1, 37, 15, 17, 1, 81184, 1, 2, 272831, 1, 137, 1, 9, 42874, 679183, 1, 350027, 12, 1, 2 , 1, 26408, 1, 11182, 1, 30, 139590, 7, 3, 1, 1, 34729, 1, 2, 1, 1, 50343, 66873 , 3891, 1, 148952, 1, 1, 22322, 104176, 1, 3, 20549, 140266, 37827, 30504, 17, 6 8588, 120195, 1, 123353, 2, 64301, 11, 1, 109867, 4, 1, 1, 1, 28671, 1, 50963, 5 4584, 1, 1, 1, 33, 1, 381918, 1, 265823, 4771840, 155179, 314, 134086, 1, 1, 30,  1, 2, 1102665, 18, 132243, 3861, 1, 1, 208906, 60112, 1, 1, 1, 31273, 551, 3490 0, 2, 43606, 1, 1, 1, 1, 5, 2, 88342, 2, 1, 19, 3, 1, 1, 1, 1, 28507, 1, 491467,  1, 1, 22, 1, 1, 1, 1, 9345, 9, 18, 84343, 1, 2, 1, 18, 36816, 1, 1, 513028, 287 88, 5037383, 721932, 170292, 108942, 539115, 1, 575676, 20, 1, 31698, 99797, 205 21, 380986, 1, 1, 14, 2, 1, 201100, 30, 1, 119484, 1, 1, 1, 1, 2214252, 3, 4, 18 179, 9, 4, 542150, 1, 6, 157, 3182099, 4, 1, 1, 6140, 3339847, 498283, 52523, 1,  1, 1, 1, 1, 202054, 263324, 1, 6, 2, 1, 2, 72357, 12, 5, 66, 4, 7368, 1, 30706,  61936, 3945270, 138991, 1, 68247, 1, 1, 30482, 35326, 1, 1, 9, 1, 148, 1, 46985 , 1, 4325093, 1, 1, 2880384, 65173, 1, 56581, 179178, 372369, 56187, 3, 12, 8, 4 00743, 3, 28658, 1, 1, 9, 1, 4, 2, 34357, 1, 42596, 68840, 2, 62638, 158027, 617 34, 71263, 1, 1, 9, 1, 6830309, 3, 1, 1, 157253, 129837, 9, 5008187, 48499, 5981 3, 1, 40320, 233893, 5, 1383, 7732178, 16, 1, 13, 5686145, 84554, 1, 79442, 1, 1 , 256812, 127818, 31, 226113, 1, 4, 1, 1, 4506163, 1, 4, 1, 40176, 19107, 205, 2 7, 1, 448999, 1, 1, 2750, 62723, 1, 12, 1, 1, 79881, 1, 48, 13, 4, 1, 28765, 1, 33, 291330, 30817, 2, 1, 1, 1, 4170949, 16, 1, 1, 118781, 10473, 520797, 1, 8, 1 , 80215, 1, 21759, 5143209, 79141, 40229, 1, 17403, 71680, 1115694, 1, 1, 1, 10,  1, 77149, 382712, 1, 11, 84891, 47633, 1, 2, 39037, 1, 213148, 1607280, 127674,  1, 333207, 1, 78901, 1, 16203, 87580, 1, 1565571, 537902, 53000, 15, 1, 2, 1, 2 13127, 1, 338634, 2469990, 469479, 9519, 51083, 1, 42082, 33179, 1, 1, 32444, 3,  1, 201642, 99724, 377, 1, 2, 1, 36919, 1, 322707, 2, 164765, 82516, 1, 5274643,  1, 36421, 1, 8, 1, 117856, 1, 1, 493342, 1, 36289, 7, 1, 62, 2, 1, 38533, 1, 68 , 45754, 9, 102015, 312941, 1, 99 
Final score is 220.826222910756
Alexander Herold
fuente
5

RATAS EN ACCIÓN (no es una respuesta, sino una herramienta gráfica para bots de C ++)

Desde el comienzo de este desafío, tuve dificultades para descubrir a qué se enfrentaban realmente las ratas en la pista.
Al final, pirateé el controlador y escribí una herramienta lateral para obtener una representación gráfica de una pista.
Eventualmente hice algo más de pirateo y agregué una visualización de los posibles caminos del ADN de una rata dada.

El mapa está extremadamente abarrotado y requiere un poco de tiempo para acostumbrarse, pero me pareció bastante útil comprender cómo funcionaban mis bots.

Aquí hay un ejemplo:

pista de muestra

Probablemente necesitará hacer zoom para ver algo, así que aquí está solo la primera mitad:

media pista (sin juego de palabras)

Al principio, veamos los caminos de la rata. Hay una ruta para cada posible ubicación de inicio (generalmente 15, a veces un poco menos). Por lo general, tienden a fusionarse, lo que idealmente conduce a un solo lugar de victoria.

Los caminos están representados por grandes flechas rectas. El color describe el resultado:

  • verde: ganar
  • amarillo: bucle infinito
  • marrón: golpes en la pared
  • rojo: desafortunado accidente

En el ejemplo, tenemos 12 posiciones de inicio ganadoras, una que lleva a un bucle infinito y dos a una muerte agotadora (como parece ser teletransportado).

Las discontinuidades de la ruta se deben a teletransportaciones, que puede seguir con las flechas curvas correspondientes.

Ahora para los símbolos de colores. Representan el significado de los 16 colores (los grises representan lo que ve una rata).

  • pared: cuadrado
  • teletransportador: 4 estrellas ramificadas
  • detector de trampa: pequeño octogon

los colores vacíos están ... bueno ... vacíos.

Los teletransportadores tienen flechas salientes que apuntan a su destino.

Los detectores de trampa también tienen flechas que indican la trampa, que se representa como un círculo rojo.
En un caso de 9, la trampa se encuentra en la misma celda que su detector, en cuyo caso verá el pequeño octógono en la parte superior del círculo rojo.

Es el caso de la trampa de color amarillo pálido en este ejemplo.
También puede ver los detectores de trampa de color malva apuntando hacia su trampa indicada.

Tenga en cuenta que a veces el círculo rojo de una trampa estará oculto debajo de una pared. Ambos son letales, por lo que el resultado es el mismo en caso de teletransportación.
Observe también que una trampa podría estar ubicada en un teletransportador, en cuyo caso el teletransportador tiene prioridad (es decir, la rata se teletransporta antes de caer en la trampa, en efecto neutralizando la trampa).

Por último, los símbolos grises representan lo que ven mis ratas (es decir, el significado de sus atributos genómicos para los colores).

  • pared: cuadrado
  • detector de trampa: octogon
  • trampa: X

Básicamente, todas las celdas que se sientan en un cuadrado gris son consideradas paredes por la rata.
Las X grandes representan células consideradas trampas, con los octógonos correspondientes que indican el detector que las reportó.

En este ejemplo, ambas paredes se identifican como tales, al igual que la trampa de color amarillo pálido (indicando de hecho una celda mortal, por lo que representarla como una pared es correcta).
El detector de trampa de color malva se ha identificado como tal (se encuentra en un octógono gris), pero la ubicación de la trampa es incorrecta (puede ver que algunos círculos rojos no tienen cruces debajo de ellos).

De 4 teletransportadores, 2 se consideran paredes (turquesa y tostado) y 2 como celdas vacías (rojizas y amarillentas).

Algunas celdas vacías se consideran detectores de trampa o paredes. Si observa de cerca, puede ver que estos "detectores defectuosos" de hecho están prohibiendo la entrada a las celdas que podrían causar problemas a la rata, por lo que a pesar de que no coinciden con los colores reales, tienen un propósito definido.

El código

Bueno, es un desastre, pero funciona bastante bien.

Visto desde el código del jugador, solo agregué una interfaz: una función de rastreo utilizada para informar el significado de un ADN dado. En mi caso, utilicé 3 tipos (pared, detector de trampa y vacío), pero básicamente puede generar cualquier cosa relacionada con el color (o nada en absoluto si no desea gráficos relacionados con el genoma).

Pirateé el controlador para generar una gran cadena de caracteres que coteja la descripción de la pista y los colores con una "prueba en seco" del ADN de la rata desde todas las ubicaciones posibles.

Significa que los resultados serán realmente significativos solo si el bot no usa valores aleatorios. De lo contrario, las rutas que se muestran solo representarán un resultado posible.

Por último, todos estos rastros se colocan en un archivo de texto grande que luego es leído por una utilidad PHP que produce la salida gráfica.

En la versión actual, tomo una instantánea cada vez que una rata muere después de haber alcanzado un nuevo estado físico máximo (que muestra bastante bien el refinamiento progresivo del genoma sin requerir demasiadas instantáneas) y una instantánea final al final del juego (que muestra El ADN más exitoso).

Si alguien está interesado, puedo publicar el código.

Claramente, esto funciona solo para los bots de C ++, y necesitará escribir una función de rastreo y posiblemente modificar el código PHP si desea mostrar algunos datos específicos del genoma (las cifras grises en mi caso).
Incluso sin información específica de ADN, puede ver los caminos seguidos por su ADN en un mapa dado con muy poco esfuerzo.

¿Por qué una salida intermedia?

En primer lugar, C ++ no tiene una biblioteca gráfica portátil decente para hablar, especialmente cuando se usa MSVC. Incluso si las compilaciones de Win32 generalmente están disponibles, a menudo vienen como una ocurrencia tardía, y la cantidad de bibliotecas externas, paquetes y otras sutilezas similares a Unix necesarias hacen que escribir una aplicación gráfica rápida y simple sea un dolor terrible en una parte del cuerpo que la decencia impide yo de nombrar.

Pensé en usar Qt (casi el único entorno que hace que el desarrollo gráfico / GUI portátil en C ++ sea una tarea simple e incluso placentera, en mi humilde opinión, probablemente porque agrega un sistema de mensajería al objetivo C que C ++ carece y hace un trabajo increíble de limitar la memoria administración al mínimo posible), pero esto parecía una exageración para la tarea en cuestión (y cualquiera que quiera usar el código tendría que instalar el SDK grande, supongo que no vale la pena el esfuerzo).

Incluso suponiendo una biblioteca portátil, no hay requisitos de velocidad para hablar (un segundo más o menos para producir una imagen es en gran medida suficiente), y con su rigidez proverbial y desorden inherente, C ++ ciertamente no es la mejor herramienta para el trabajo.

Además, tener una salida de texto intermedia agrega mucha flexibilidad. Una vez que los datos están allí, puede usarlos para otros fines (analizando el rendimiento de los bots, por ejemplo).

¿Por qué PHP?

El lenguaje me parece extremadamente simple y adaptable, muy conveniente para la creación de prototipos. Lo convertí en mi lenguaje favorito para desafíos de código que no requieren desempeños extremos.
Sin embargo, es un lenguaje terrible para el golf, pero el golf nunca fue mi taza de té de todos modos.

Supongo que Python o Ruby serían igual de agradables de usar con el mismo propósito, pero nunca tuve la oportunidad de hacer un trabajo serio con ellos, y últimamente estaba trabajando en sitios web, así que PHP lo es.

Incluso si no conoce el idioma, no debería ser demasiado difícil modificar el código para satisfacer sus necesidades. Simplemente no olvides la $s antes de las variables, al igual que los buenos viejos días básicos :).


fuente
1
¿Podrías compartir tu herramienta? No veo ni código ni un enlace en su respuesta.
Franky
5

SkyWalker - Python - anota menos de 231 en 50 juegos

Entonces codifique primero y luego algunas explicaciones. Espero que nada se haya roto al copiar.

class SkyWalker(Player):
    def __init__(self):
        Player.__init__(self)
        self.coords = [#Coordinate(-1,-1),
                       #Coordinate( 0,-1),
                       Coordinate( 1, 0),
                       Coordinate( 1,-1),
                       #Coordinate(-1, 0),
                       #Coordinate( 0, 0),
                       #Coordinate(-1, 1),
                       #Coordinate( 0, 1),
                       Coordinate( 1, 1)]

        self.n_moves = len(self.coords)

    def visionToMove(self, x, y):
        x = x - 2
        y = y - 2

        return (x, y)

    def trapToMove(self, x, y, offx, offy):
        x = x - 2 + (offx % 3) - 1
        y = y - 2 + (offy % 3) - 1
        return (x, y)

    def isNeighbour(self, x1, y1, x2, y2):
        if (x1 == x2) or (x1+1 == x2) or (x2+1 == x1):
            if (y1 == y2) or (y1+1 == y2) or (y2+1 == y1):
                return True
        return False

    def calcMove(self, donots, never, up):
        forwards = {(1, 0): 0, (1, 1): 0, (1, -1): 0, (0, 1): 10, (0, -1): 10}

        for key in forwards:
            if key in never:
                forwards[key] = 100
            for x in donots:
                if (key[0] == x[0]) and (key[1] == x[1]):
                    forwards[key] = 20

        min_value = min(forwards.itervalues())
        min_keys = [k for k in forwards if forwards[k] == min_value]

        return random.choice(min_keys)

    def turn(self):
        trap1 = self.bit_chunk(0, 4)
        trap1_offsetx = self.bit_chunk(4, 2)
        trap1_offsety = self.bit_chunk(6, 2)
        trap2 = self.bit_chunk(8, 4)
        trap2_offsetx = self.bit_chunk(12, 2)
        trap2_offsety = self.bit_chunk(14, 2)
        wall1 = self.bit_chunk(16, 4)
        wall2 = self.bit_chunk(20, 4)
        tel1 = self.bit_chunk(24, 4)
        tel1_good = self.bit_chunk(28, 3)
        tel2 = self.bit_chunk(31, 4)
        tel2_good = self.bit_chunk(35, 3)
        tel3 = self.bit_chunk(38, 4)
        tel3_good = self.bit_chunk(42, 3)
        tel4 = self.bit_chunk(45, 4)
        tel4_good = self.bit_chunk(49, 3)
        up = self.bit_at(100)

        donots = []
        never = []

        for y in range(0, 5):
            for x in range(0, 5):
                c = self.vision[y][x]
                if (c == -1):
                    never += self.visionToMove(x, y),
                elif (c == trap1):
                    donots += self.trapToMove(x, y, trap1_offsetx, trap1_offsety),
                elif (c == trap2):
                    donots += self.trapToMove(x, y, trap2_offsetx, trap2_offsety),
                elif (c == wall1):
                    donots += self.visionToMove(x, y),
                elif (c == wall2):
                    donots += self.visionToMove(x, y),
                elif (c == tel1):
                    if (tel1_good > 3):
                        donots += self.visionToMove(x, y),
                elif (c == tel2):
                    if (tel2_good > 3):
                        donots += self.visionToMove(x, y),
                elif (c == tel3):
                    if (tel3_good > 3):
                        donots += self.visionToMove(x, y),
                elif (c == tel4):
                    if (tel4_good > 3):
                        donots += self.visionToMove(x, y),

        coord = self.calcMove(donots, never, up)

        return Coordinate(coord[0], coord[1])

Alguna explicación

En mi opinión, la principal diferencia es que no codifico todos los colores. En cambio, trato de guardar la cantidad de colores que son importantes. En mi opinión, esos colores son las trampas, paredes y teletransportadores. El espécimen no necesita saber el color de una buena célula. Por lo tanto, mi genoma está estructurado de la siguiente manera.

  • 2 x 8 bits para trampas, los primeros 4 bits son el número de color, los otros 4 son el desplazamiento
  • 2 x 4 bits para paredes, solo el color
  • 4 x 7 bits para teletransportadores, nuevamente 4 bits para el color, 3 para decidir bueno o malo

Esto hace un total de 52 bits utilizados. Sin embargo, utilizo solo el primer bit de los 3 decisores teletransportadores (verifico si el número es mayor 3). Por lo tanto, los otros 2 podrían eliminarse, dejándome en 44 bits utilizados.

En cada turno verifico cada campo de mi visión si es uno de los colores malos (+ fuera del tablero -1) y lo agrego a una lista de campos a los que el espécimen no quiere moverse. En el caso de una trampa, agrego el campo que está en el desplazamiento guardado para ese color de trampa.

Según la lista de esos campos defectuosos, se calcula el siguiente movimiento. El orden de los campos preferidos es:

  1. adelante
  2. arriba o abajo
  3. al revés arriba o abajo
  4. hacia atrás

Si dos campos de una categoría son aplicables, uno se elige al azar.

Resultados

Individual scores: [192, 53116, 5, 1649, 49, 2737, 35, 5836, 3, 10173, 4604, 22456, 21331, 445, 419, 2, 1, 90, 25842, 2, 712, 4, 1, 14, 35159, 13, 5938, 670, 78, 455, 45, 18, 6, 20095, 1784, 2, 11, 307853, 58171, 348, 2, 4, 190, 7, 29392, 15, 1158, 24549, 7409, 1]
On average, your bot got 231.34522696 points

Pensamientos

  • No tengo idea, si tuve suerte con las 50 carreras o si realmente hay algo de sabiduría en mi estrategia.

  • Mis carreras nunca parecen despegar y obtener puntajes súper altos, pero también tienden a encontrar al menos algunas veces el objetivo

  • Una pequeña aleatoriedad es buena para no quedar atrapado en una trampa en algún lugar cerca del final de la carrera.

  • Creo que los colores no especiales nunca son malos. Sin embargo, las instancias de ellos pueden ser malas, cuando están en el desplazamiento de una trampa. Por lo tanto, etiquetar un color como malo si no es trampa, pared o teletransportador incorrecto no tiene sentido.

  • Las paredes son los mayores enemigos.

Mejoras

Primero, aunque extrañaré ver los cuadrados negros acercándose cada vez más a la meta, es necesario un puerto C ++ para realizar más pruebas y obtener un resultado más significativo.

Uno de los principales problemas es que si hay células malas (o aquellas que el espécimen piensa mal) frente a la rata, fácilmente comienza a moverse hacia arriba y hacia abajo en círculos. Esto podría detenerse o reducirse mirando 2 movimientos hacia adelante en esos casos y evitar que se mueva a un campo donde simplemente retroceda nuevamente.

A menudo, lleva bastante tiempo hasta que una rata con buenos genes llega a la meta y comienza a propagar sus genes. Tal vez necesito alguna estrategia para aumentar la diversidad en esos casos.

Dado que los teletransportadores son difíciles de calcular, tal vez debería dividir la población entre aquellos que son riesgosos y siempre tomar buenos teletransportadores y aquellos que están más preocupados y solo tomarlos si no hay otra opción.

Debería usar la segunda mitad de mi genoma de alguna manera.

Dominik Müller
fuente
También trato de almacenar colores, pero al final concluí que no funciona porque obtendrás dobles. Por ejemplo, si self.bit_chunk(16, 4)y self.bit_chunk(20, 4)tiene el valor 0010, efectivamente solo ha almacenado información sobre una de las dos trampas.
Ruut
Necesitaba agregar sangría a una línea para que esto se ejecute; supongo que se perdió durante la copia y el pegado. Lo he agregado a su código aquí ahora también.
trichoplax 01 de
Para cualquier otra persona que desee ejecutar esto: se ejecuta en python 2, y se puede ejecutar en python 3 cambiando la aparición individual de itervaluesa values.
trichoplax 01 de
Obtuve los siguientes resultados: [6155, 133, 21, 12194, 8824, 3, 3171, 112, 111425, 3026, 1303, 9130, 2680, 212, 28, 753, 2923, 1, 1, 4140, 107, 1256 , 90, 11, 104, 1538, 63, 917, 8, 1, 709, 11, 304, 212, 2, 43, 5, 4, 206, 8259, 75, 28, 7, 1, 11, 5, 1 , 1244, 1398, 13] Media geométrica 122.9220309940335
trichoplax
Parece que tendríamos que ejecutar más de 50 juegos para obtener un puntaje confiable.
trichoplax 01 de
3

Python, NeighboursOfNeighbours, Puntuación = 259.84395 más de 100 juegos

Esta es una variación de ColorScorePlayer. Cada 6 bits almacena un puntaje de calidad para un cuadrado. Cuando el bot está haciendo un movimiento, puntúa cada uno de los 3 cuadrados hacia adelante: diagonal hacia arriba, hacia adelante y diagonal hacia abajo. El puntaje es la calidad del cuadrado más la mitad de la calidad promedio de los siguientes 3 cuadrados. Esto le da al bot un poco de anticipación, sin abrumar la calidad del primer cuadro. El algoritmo es similar a LookAheadPlayer, que no vi antes de escribir esta solución.

class NeighborsOfNeighbors(Player):
  def __init__(self):
    Player.__init__(self)
    self.coords = [ Coordinate( 1, 0),
                    Coordinate( 1,-1),
                    Coordinate( 1, 1)
                    ]

  def turn(self):
    scores=[self.score(c.x,c.y)+0.5*self.adjacentScore(c.x,c.y) if self.vision_at(c.x,c.y)>-1 else None for c in self.coords ]
    max_score = max(scores)
    return random.choice( [c for s,c in zip(scores,self.coords) if s==max_score] )

  def adjacentScore(self,x,y):
    adjacent = [(x+1,y)]
    if self.vision_at(x,y+1)>-1:
      adjacent+=[(x+1,y+1)]
    if self.vision_at(x,y-1)>-1:
      adjacent+=[(x+1,y-1)]
    adjscores=[self.score(a,b) for a,b in adjacent]
    return sum(adjscores)/float(len(adjscores))

  def score(self,x,y):
    return -1 if self.vision_at(x,y) == -1 else self.bit_chunk(6*self.vision_at(x,y),6)
usuario2487951
fuente
Faltaba una sangría en una línea. Supongo que se perdió al pegar. Lo agregué.
trichoplax
Al ejecutarse en Python 3, se quejó de comparar None al calcular max (puntuaciones). Así que cambié else Nonea else 0la línea anterior para calcular su puntaje. Espero que eso deje su lógica sin cambios (no he realizado cambios en su código aquí en SE, aparte de agregar la sangría perdida).
trichoplax 01 de
En Python 3 obtuve los siguientes puntajes para esta respuesta: [1, 13085, 360102, 1, 73713, 1, 189, 1, 1, 193613, 34, 195718, 199, 8, 1, 1, 60006, 66453, 2, 2, 53, 425206, 1, 4, 1, 1, 16, 153556, 1, 18134, 35655, 1, 4211684, 2, 1, 26451, 8, 1, 724635, 69242, 38469, 796553, 111340, 1, 25, 40017, 76064, 66478, 209365, 3925393]
trichoplax
Una media geométrica de 428.3750848244933
trichoplax 01 de
2

ROUS (Roedor de tamaño inusual), Java, Puntuación = 0

Esto mezcla los alrededores para decidir a dónde ir. Debido a que el controlador Java no funciona, no tengo puntajes para esto. Esto solo llegará muy lejos si encuentra algunos teletransportadores para ayudarlo.Esto tiende a extinguirse y bloquea el controlador de vez en cuando. Esto probablemente se deba al hecho de que su entorno natural es el Pantano de Fuego.

import java.awt.*;
import java.util.Map;

public class ROUS extends Player{

    private static final int NUMBER_OF_GENES = 33;
    private static final int GENE_SIZE = 3;
    private static final Point[] coords = new Point[]{
        new Point(-1, -1),
        new Point(-1, 0),
        new Point(-1, 1),
        new Point(0, -1),
        new Point(0, 1),
        new Point(1, -1),
        new Point(1, 0),
        new Point(1, 1)
    };

    public Point takeTurn(String dna, Map<Point, Integer> vision){
        Point[] table = decode(dna);
        int hash = hash(vision);
        return table[hash];
    }

    private int hash(Map<Point, Integer> surroundings) {
        return Math.abs(surroundings.hashCode()) % NUMBER_OF_GENES;
    }

    private Point[] decode(String dna) {
        Point[] result = new Point[NUMBER_OF_GENES];

        for (int i = 0; i < NUMBER_OF_GENES; i++){
            int p = Integer.parseInt(dna.substring(i * GENE_SIZE, (i + 1) * GENE_SIZE), 2);
            int x;
            int y;

            result[i] = coords[p];
        }
        return result;
    }
}
El numero uno
fuente
1
El controlador Java está funcionando ahora.
Martin Ender
3
Al principio pensé que estabas rindiendo homenaje a la antigua Rusia, pero como parece que fue a Rob Reiner.
El puntaje mínimo posible es 1
trichoplax
@trichoplax ...
TheNumberOne
Ah, ya veo, ¿entonces eso sucede con la frecuencia suficiente para que no puedas llegar al final de una carrera?
trichoplax
2

Lookahead de color gris (C ++, ~ 1.35)

A este no le está yendo muy bien en promedio, pero en raras ocasiones se desempeña de manera brillante. Desafortunadamente, se nos califica en promedio geométrico (1.35) y no en puntaje máximo (20077).

Este algoritmo funciona simplemente usando códigos grises de 4 bits para asignar el puntaje de cada color en algún lugar de -2 a 2 (con un sesgo hacia el rango [-1..1]), y calcula el puntaje de la casilla de cada movimiento y sus próximos movimientos . También utiliza un código gris de 2 bits para determinar el multiplicador para el mosaico en sí, así como el factor de polarización para moverse hacia la derecha. (Los códigos grises son mucho menos susceptibles a grandes saltos debido a mutaciones, aunque en realidad no hacen ningún favor para el cruce de punto de código medio ...)

Tampoco hace absolutamente nada para tratar de manejar trampas especialmente, y sospecho que podría ser la caída (aunque no he agregado ninguna instrumentación al controlador para probar esta teoría).

Para cada movimiento posible, determina un puntaje y, de entre todos los movimientos con el puntaje más alto, elige al azar.

coord_t colorTileRanker(dna_t d, view_t v) {
    const int COLOR_OFFSET = 0; // scores for each color (4 bits each)
    const int SELF_MUL_OFFSET = 96; // 2 bits for self-color multiplier
    const int MOVE_MUL_OFFSET = 98; // 2 bits for move-forward multiplier

    static const int gray2[4] = {0, 1, 3, 2};
    static const int gray3[8] = {0, 1, 3, 2, 7, 6, 4, 5};

    // bias factor table
    const int factorTable[4] = {0, 1, 2, 1};

    const int selfMul = factorTable[gray2[dnaRange(d, SELF_MUL_OFFSET, 2)]]*2 + 9;
    const int moveMul = factorTable[gray2[dnaRange(d, MOVE_MUL_OFFSET, 2)]] + 1;

    // scoring table for the color scores
    static const int scoreValue[8] = {0, 1, 2, 3, 4, 3, 2, 1};

    std::vector<coord_t> bestMoves;
    int bestScore = 0;

    for (int x = -1; x <= 1; x++) {
        for (int y = -1; y <= -1; y++) {
            const int color = v(x, y);
            if ((x || y) && (color >= 0)) {
                int score = 0;

                // score for the square itself
                score += selfMul*(scoreValue[gray3[dnaRange(d, COLOR_OFFSET + color*3, 3)]] - 2);

                // score for making forward progress;
                score += moveMul*(x + 1);

                // score for the resulting square's surrounding tiles
                for (int a = -1; a <= 1; a++) {
                    for (int b = -1; b <= 1; b++) {
                        const int color2 = v(x + a, y + b);
                        if (color2 >= 0) {
                            score += scoreValue[gray3[dnaRange(d, COLOR_OFFSET + color2*3, 3)]] - 2;
                        }
                    }
                }

                if (score > bestScore) {
                    bestMoves.clear();
                    bestScore = score;
                }
                if (score >= bestScore) {
                    bestMoves.push_back({x, y});
                }
            }
        }
    }

    if (bestMoves.empty()) {
        return {v.rng.rint(2), v.rng.rint(3) - 1};
    }
    return bestMoves[v.rng.rint(bestMoves.size())];
}

En mi carrera más reciente, obtuve puntajes: 1 1 1 1 1 1 1 46 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20077 1 1 1 2 1 1 1 1 1

Ojalá pudiera obtener más de los 20077 y menos de los 1. :)

mullido
fuente
1
¡Usar código gris es una idea grayt! ;)
matovitch
1
+1 para códigos grises. Sin embargo, un genoma completamente resistente a las mutaciones dañará bastante la diversidad. Y por cierto, un puntaje de 20,000 ni siquiera está cerca del máximo que puedes lograr. Si alguna rata desarrolla la capacidad de correr la pista desde cualquier posible lugar de inicio, se vuelve inmortal y adquiere una gran puntuación de aptitud. Su genoma domina rápidamente, lo que lleva a una población de hasta casi 50 000 ratas y una puntuación de unos pocos millones.
2

C ++, TripleScore, Puntuación: 100 ~ 400

En primer lugar, mi puntaje varía mucho en varias ejecuciones (principalmente debido al número de 1).

El núcleo calcula la puntuación de 5 direcciones: arriba, abajo, adelante-arriba, adelante y adelante-abajo. Primero se calcula la puntuación de arriba y abajo, que los resultados se comparan con el valor de permanecer en el lugar. Si permanecer en el lugar es mejor que moverse hacia arriba o hacia abajo, no se elegirán estas direcciones (por lo tanto, debe avanzar). Esto es para evitar rebotes (arriba, abajo, arriba, abajo, ...) entre 2 puntos.

Ahora se puntúan las otras 3 direcciones: hacia arriba, hacia adelante y hacia abajo. De todas las direcciones investigadas, se mantienen las que tienen la puntuación más alta y 1 de ellas se elige al azar.

Puntuación de una dirección: TripleScore calcula la puntuación de un movimiento utilizando 3 subpuntos:

  • La puntuación del color del destino (depende del ADN, como en colorScorePlayer)
  • El puntaje de avanzar (depende del ADN)
  • El puntaje máximo de avanzar desde el destino (multiplicado por un factor almacenado en el ADN)

Al igual que con otras respuestas, el puntaje depende en gran medida del número de puntajes 1 que se devuelven.

#define CHUNKSIZE 5 //We have 20 values so 5 bits/value
#define MAXVALUE 32 //2^CHUNKSIZE
#define AVGVALUE MAXVALUE/2

#define DNASEGMENT(dna, i) dnarange(dna, i*CHUNKSIZE, CHUNKSIZE)
#define DNA_COLOR 0
#define DNA_FORWARD 16
#define DNA_LOOKAHEAD 17

//Get the score for a specific move
int calcscore(dna_t dna, view_t view, int x, int y, bool final){
  if (view(x,y) == OUT_OF_BOUNDS){
    //We cant go there
    return -MAXVALUE;
  }
  //The score of the color
  int s = DNASEGMENT(dna, DNA_COLOR+view(x,y))-AVGVALUE;
  //The score of going forward
  s += x*DNASEGMENT(dna, DNA_FORWARD);

  //Get the children or not
  if (!final){
    int max=-MAXVALUE;
    int v;
    //Get the maximum score of the children
    for (int i=-1; i<2; ++i){
        v = calcscore(dna, view, x+1, y+i, true);
        if (v>max){
            max=v;
        }
    }
    //Apply dna factor to the childs score
    s += (max * DNASEGMENT(dna, DNA_LOOKAHEAD))/AVGVALUE;
  }
  return s;
}

coord_t TripleScore(dna_t dna, view_t view) {
  int maxscore = -100;
  int score;
  coord_t choices[5]; //Maximum 5 possible movements
  int maxchoices = 0;
  int zeroscore = calcscore(dna, view, 0, 0, false);

  //Go over all possible moves and keep a list of the highest scores
  for (int x=0; x<2; ++x){
    for (int y=-1; y<2; ++y){
        if (x | y){
            score = calcscore(dna, view, x, y, false);
            if (score > maxscore){
                maxscore = score;
                choices[0] = {x, y};
                maxchoices = 1;
            }else if (score == maxscore){
                choices[maxchoices++] = {x, y};
            }
        }
    }
    if (!x && maxscore <= zeroscore){
        //I will NOT bounce!
        maxscore = -100;
    }
  }

  return choices[view.rng.rint(maxchoices)];
}
Ibens Wouter
fuente
2

Ruby - ProbabilisticScorePlayer

class ProbabilisticScorePlayer < Player
    Here = Vector2D.new( 0, 0)
    Forward = Vector2D.new( 1, 0)
    Right = Vector2D.new( 0, 1)
    Left = Vector2D.new( 0,-1)

    def vision_at(vec2d)
        v = @vision[vec2d.x+2][vec2d.y+2]
        v==-1?nil:v
    end

    def turn
        coords = [Forward]
        [Here,Forward].each{|x|
            [Here,Right,Left].each{|y|
                c = x+y
                if x!=y && vision_at c > -1
                  coords.push c if bit_at(vision_at c)==1
                  coords.push c if bit_at(vision_at(c+Forward)+16)==1
                  coords.push c if bit_at(vision_at(c+Right)+32)==1
                  coords.push c if bit_at(vision_at(c+Left)+48)==1
                  coords.push c if bit_at(vision_at(c+Forward+Right)+64)==1
                  coords.push c if bit_at(vision_at(c+Forward+Left)+80)==1
                end
            }
        }
        coords.sample(random: @rng)
    end
end

Esta rata altamente no determinista calcula la probabilidad de ir a un espacio por su vecindario. Las primeras 16 ranuras en el genoma representan los 16 colores. 1 en una ranura significa que el color es bueno para pisar, 0 significa malo. Los siguientes 16 sostienen lo mismo para el espacio frente a su objetivo, y así sucesivamente.

La principal ventaja del enfoque probabilístico es que es casi imposible quedarse atrapado detrás de una pared por mucho tiempo. La desventaja es que casi nunca obtendrás una rata casi perfecta.

MegaTom
fuente
+1 por originalidad. ¿Qué tipo de puntaje obtuviste?
Nunca lo probé todavía ...
MegaTom
¿Olvidaste dar cun valor inicial? No parece estar definido cuando lo usas en el primero if.
Martin Ender
@ MartinBüttner sí, lo olvidé. Lo arreglaré ahora.
MegaTom
No conozco bien a Ruby, pero su código no se ejecuta en Ruby2.1.5. coordsno es una lista, se usa en &&lugar de andparéntesis y se olvidó, e incluso después de arreglar todo esto, no está limitando los valores RNG, por lo que obtiene una dirección vacía. ¿Es este pseudocódigo o algo destinado a ejecutarse con algún tipo de dialecto de Ruby?
2

Java, RunningStar, Puntuación = 1817.050970291959 más de 1000 juegos

Este bot utiliza la codificación de colores de Run-Bonus con la técnica de StarPlayer .

Actualización: controlador java fijo.

Scores: 6, 81533, 1648026, 14, 5, 38841, 1, 76023, 115162, 3355130, 65759, 59, 4, 235023, 1, 1, 1, 3, 2, 1, 1, 14, 50, 1, 306429, 68, 3, 35140, 2, 1, 196719, 162703, 1, 1, 50, 78233, 5, 5, 5209, 1, 2, 60237, 1, 14, 19710, 1528620, 79680, 33441, 58, 1, 4, 45, 105227, 11, 4, 40797, 2, 22594, 9, 2192458, 1954, 294950, 2793185, 4, 1, 1, 112900, 30864, 23839, 19330, 134178, 107920, 5, 122894, 1, 1, 2721770, 8, 175694, 25235, 1, 3109568, 4, 11529, 1, 8766, 319753, 5949, 1, 1856027, 19752, 3, 99071, 67, 198153, 18, 332175, 8, 1524511, 1, 159124, 1, 1917181, 2, 1, 10, 276248, 1, 15, 1, 52, 1159005, 43251, 1, 536150, 75864, 509655, 1126347, 250730, 1548383, 17, 194687, 27301, 2, 1, 207930, 621863, 6065, 443547, 1, 6, 1, 1, 1, 1, 556555, 436634, 25394, 2, 61335, 98076, 1, 190958, 2, 18, 67981, 3, 8, 119447, 1, 1, 1, 19, 28803, 23, 33, 60281, 613151, 1, 65, 20341, 799766, 476273, 105018, 357868, 3, 92325, 2062793, 18, 72097, 30229, 1, 1, 3, 610392, 1, 202149, 887122, 56571, 1, 77788, 61580, 4, 72535, 381846, 148682, 26676, 1, 210, 3556343, 212550, 650316, 33491, 180366, 1, 295685, 46255, 43295, 1006367, 63606, 1, 1, 1, 1, 3094617, 21, 10, 3, 1, 1, 14730, 1585801, 102, 2, 410353, 1570, 1, 17423, 1, 1849366, 5, 1, 357670, 1, 1, 1, 1, 89936, 349048, 15, 7, 6, 2, 121654, 1852897, 19, 1, 103275, 1, 1, 771797, 23, 19, 6700, 1, 135844, 2966847, 3, 2356708, 101515, 1, 17, 1, 996641, 22, 16, 657783, 171744, 9604, 1, 1335166, 1739537, 2365309, 1, 3378711, 11332, 3980, 182951, 609339, 8, 10, 1746504, 61895, 386319, 24216, 331130, 12193, 1, 284, 1, 2, 50369, 38, 8, 1, 1238898, 177435, 124552, 22370, 1418184, 20132, 6, 2, 730842, 1, 1341094, 141638, 534983, 1551260, 31508, 96196, 434312, 3012, 715155, 1, 276172, 214255, 1, 208948, 4, 1631942, 512293, 37, 64474, 1342713, 1, 132634, 13, 2, 61876, 1081704, 160301, 2, 488156, 2414109, 1809831, 5, 74904, 6, 11, 5, 1, 79856, 96, 35421, 229858, 238507, 3838897, 18, 44, 1, 1659126, 9, 33708, 12, 1, 758381, 162742, 256046, 3, 15, 142673, 70953, 58559, 6, 2, 1, 984066, 290404, 1072226, 66415, 4465, 924279, 48133, 319765, 519401, 1, 1, 1201037, 418362, 17022, 68, 213072, 37, 1039025, 1, 2, 6, 4, 45769, 1, 5, 1061838, 54614, 21436, 7149, 1, 1, 1, 35950, 2199045, 1, 379742, 3, 2008330, 238692, 181, 7, 140483, 92278, 214409, 5179081, 1, 1, 334436, 2, 107481, 1142028, 1, 31146, 225284, 1, 14533, 4, 3963305, 173084, 102, 1, 4732, 14, 1, 25, 11032, 224336, 2, 131110, 175764, 81, 5630317, 1, 42, 1, 89532, 621825, 2291593, 210421, 8, 44281, 4, 303126, 2895661, 2672876, 3, 436915, 21025, 1, 4, 49227, 1, 39, 3, 1, 103531, 256423, 2, 1600922, 15, 1, 2, 58933, 1114987, 1, 4, 3, 1, 1544880, 285673, 240, 2, 128, 214387, 3, 1327822, 558121, 5, 2718, 4, 1258135, 7, 37418, 2729691, 1, 346813, 385282, 2, 35674, 513070, 13, 1930635, 117343, 1929415, 52822, 203219, 1, 52407, 1, 1, 1, 3, 2, 37121, 175148, 136893, 2510439, 2140016, 437281, 53089, 40647, 37663, 2579170, 83294, 1597164, 206059, 1, 9, 75843, 773677, 50188, 12, 1, 1067679, 105216, 2452993, 1813467, 3279553, 280025, 121774, 62, 5, 113, 182135, 1, 16, 71853, 4, 557139, 37803, 228249, 6, 32420, 8, 410034, 73889, 1, 2, 96706, 48515, 1, 3, 1314561, 137, 966719, 692314, 80040, 85147, 75291, 1, 1, 30, 38119, 182723, 42267, 3836110, 22, 986685, 2, 37, 1, 3, 26, 43389, 2679689, 1, 1, 57365, 1, 2662599, 2, 72055, 1, 141247, 1, 1, 1122312, 1, 1080672, 4, 266211, 1, 34163, 1490610, 256341, 1, 627753, 32110, 1, 42468, 1, 10746, 1, 9, 1, 46, 1714133, 5, 117, 1, 104340, 218338, 151958, 122407, 211637, 223307, 57018, 74768, 582232, 2, 621279, 4, 1, 11, 196094, 1839877, 167117, 8, 42991, 2199269, 124676, 1, 1, 1, 5, 1, 1, 698083, 1, 76361, 1564154, 67345, 1398411, 9, 11, 105726, 1197879, 1, 2, 62740, 39, 2, 397236, 17057, 267647, 13, 57509, 22954, 1, 12, 747361, 4325650, 21425, 2160603, 144738, 1, 204054, 3113425, 6, 3019210, 30, 3359, 1, 89117, 489245, 1, 218068, 1, 1, 14718, 222722, 1, 1, 216041, 72252, 279874, 183, 89224, 170218, 1549362, 2, 1, 953626, 32, 130355, 30460, 121028, 20, 159273, 5, 2, 30, 1, 76215, 1654742, 2326439, 1, 53836, 1, 6, 4, 72327, 9, 285883, 1, 908254, 698872, 47779, 3, 2293485, 265788, 3766, 1, 1, 83151, 36431, 307577, 256891, 29, 1, 1, 1093544, 145213, 5, 2, 581319, 2911699, 1, 213061, 1359700, 2, 1, 343110, 1, 157592, 1708730, 1, 22703, 32075, 1, 1, 87720, 159221, 2313143, 10, 2266815, 2106917, 1345560, 3146014, 4, 551632, 1066905, 550313, 4069794, 1, 1406178, 38981, 1, 3, 1, 3039372, 241545, 35, 63325, 85804, 1365794, 2, 2143204, 48, 1, 99, 3225633, 7, 4074564, 1023899, 3209940, 2054326, 70880, 2, 1, 284192, 1944519, 84682, 2, 867681, 90022, 378115, 1, 15, 602743, 1337444, 131, 1, 229, 161445, 3, 2, 5591616, 195977, 92415, 637936, 142928, 1, 2310569, 923, 1, 230288, 1300519, 398529, 2233, 100261, 4323269, 81362, 37300, 1, 233775, 32277, 434139, 323797, 19214, 782633, 2881473, 1, 1, 9, 337016, 1, 515612, 44637, 17, 1, 25, 67758, 1737819, 16454, 30613, 692963, 62216, 222062, 344596, 3, 33782, 19, 180441, 23552, 20462, 70740, 10298, 109691, 1, 1729427, 33714, 1770930, 1, 1, 1, 1, 290766, 136688, 688231, 3250223, 30703, 1985963, 527128, 3, 226340, 195576, 30, 1, 3, 1, 793085, 5527, 5, 1, 2188429, 1327399, 5, 6192537, 1445186, 2478313, 2, 16892, 3, 1, 1, 15, 12, 1361157, 4, 1241684, 1, 45008, 1, 505095, 4037314, 14, 8, 1, 16740, 69906, 45, 1, 240949, 3975533, 212705, 2617552, 278884, 1, 24966, 958059, 231886, 22929, 4052071, 51259, 67791, 78739, 1, 165787, 67, 518191, 86923, 437, 1271004, 135941, 244766, 1, 1, 1, 1152745, 1, 3, 406365, 3847357, 476636, 135097, 304368, 8, 1578276, 1, 1, 375, 1, 1, 1298206, 1860743, 2, 35311, 834516, 421428, 2, 66629, 1, 309845, 398756, 33, 907277, 384475, 2267460, 1, 269300, 124525, 34399, 93584, 362186, 811260, 426109, 1, 1009323, 109986, 122181, 1, 1, 3626487, 11452, 1092410, 57233, 6, 2009226, 1, 83333, 4, 1338631, 79114, 2140249, 51813, 1118986, 43514, 1529365, 1, 101, 1, 1,
package game.players;

import java.awt.Point;
import java.util.*;

public class RunningStar extends Player{

    @Override
    public Point takeTurn(String genome, Map<Point, Integer> vision) {
        Map<Integer, Integer> squareCosts = decode(genome);
        Path path = astar(vision, squareCosts);
        return path.get(1);
    }

    private Path astar(Map<Point, Integer> vision, Map<Integer, Integer> squareCosts) {
        Set<Path> closed = new HashSet<>();
        PriorityQueue<Path> open = new PriorityQueue<>();
        open.add(new Path(new Point(0, 0), 0));
        while (!open.isEmpty()){
            Path best = open.remove();
            if (best.head().x == 2 || (best.head().x > 0 && (best.head().y == 2 || best.head().y == -2))){
                return best;
            }
            for (Path path : pathsAround(best, vision, squareCosts)){
                if (!closed.contains(path) && !open.contains(path)){
                    open.add(path);
                }
            }
            closed.add(best);
        }

        Path p = new Path(new Point(0,0), 0);
        return p.add(new Point((int)(random.nextDouble() * 3 - 1), (int)(random.nextDouble() * 3 - 1)), 0);
    }

    private List<Path> pathsAround(Path path, Map<Point, Integer> vision, Map<Integer, Integer> costs) {
        Point head = path.head();
        List<Path> results = new ArrayList<>();
        for (int i = -1; i <= 1; i++){
            for (int j = -1; j <= 1; j++){
                if (i == 0 && j == 0){
                    continue;
                }
                Point p = new Point(head.x + i, head.y + j);
                if (!vision.containsKey(p) || vision.get(p) == -1){
                    continue;
                }
                results.add(path.add(p, costs.get(vision.get(p))));
            }
        }
        return results;
    }

    private Map<Integer, Integer> decode(String genome) {
        int chunkLength = genome.length()/16;
        Map<Integer, Integer> costs = new HashMap<>();
        for (int i = 0; i < 16; i++){
            int runSize = 0;
            int cost = 0;
            for (int j = i * chunkLength; j < (i + 1) * chunkLength; j++){
                switch (genome.charAt(j)){
                    case '0':
                        runSize = 0;
                        break;
                    case '1':
                        cost += ++runSize;
                }
            }
            costs.put(i, cost);
        }
        return costs;
    }

    private class Path implements Comparable<Path>{

        Point head;
        Path parent;
        int length;
        int totalCost;

        private Path(){}

        public Path(Point point, int cost) {
            length = 1;
            totalCost = cost;
            head = point;
            parent = null;
        }

        public Point get(int index) {
            if (index >= length || index < 0){
                throw new IllegalArgumentException(index + "");
            }
            if (index == length - 1){
                return head;
            }
            return parent.get(index);
        }

        public Point head() {
            return head;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Path path = (Path) o;

            if (!head.equals(path.head)) return false;

            return true;
        }

        @Override
        public int hashCode() {
            return head.hashCode();
        }

        @Override
        public int compareTo(Path o) {
            return totalCost - o.totalCost;

        }

        public Path add(Point point, int cost) {
            Path p = new Path();
            p.head = point;
            p.totalCost = totalCost + cost;
            p.length = length + 1;
            p.parent = this;
            return p;
        }
    }
}
El numero uno
fuente
2

LeapForward, Python 2

No es particularmente innovador, pero es mi único intento que funcionó bien.

class LeapForward(Player):
  def __init__(self):
    Player.__init__(self)
    self.coords = [Coordinate( 1, 0),
                   Coordinate( 1,-1),
                   Coordinate( 1, 1)]
    self.n_moves = len(self.coords)

  def turn(self):
    notOKColors = [self.bit_chunk(4*n,4) for n in range(4,8)]
    notOKMap = [Coordinate(x-2,y-2) for x in range(0,5) for y in range(0,5) if self.vision[y][x] not in notOKColors]
    goTo = [c for c in self.coords if c in notOKMap]
    if not goTo:
      goTo = [Coordinate(1,0)]
    return random.choice(goTo)

Básicamente, codifica cuatro colores (cada uno de 4 bits) para evitar, en el genoma. Luego pasa a un color que no está en esa lista. Si todos los colores son malos, todavía salta hacia lo desconocido.

plannapus
fuente
Probablemente debería haberlo llamado "RedQueen" :)
plannapus
1

Java - IAmARobotPlayer - Puntuación 3.7

Acabo de crear esta rata robot para compararla con otro programa (no muy interesante hasta ahora) que hice. En general, no obtiene un buen puntaje, pero si anota en algún lugar, obtendrá muchas ratas a través de él. La idea es que solo mirará las tres celdas frente a ella, cada celda es buena o mala. Esto le da un número binario. Luego buscará este número en su genoma, tomará los tres bits consecutivos, también los convertirá en un número y tomará la acción que se almacena bajo este número. Por lo tanto, actúa siempre igual cuando se encuentra con la misma situación.

package game.players;
import java.awt.*;
import java.util.Map;
public class IAmARobotPlayer extends Player{
    private static final Point[] possibleMoves = {new Point(1,-1), new Point(1,0), new Point(1,1), new Point(0,-1), new Point(0,1), new Point(1,-1), new Point(1,0), new Point(1,1)};
    private int isGood(int pos,Map<Point,Integer> vision, char[] genomeChar){
        int value = vision.get(new Point(1,pos));
        if(value ==-1){
            return 0;
        } else {
            return genomeChar[84+value]-'0';
        }
    }

    @Override
    public Point takeTurn(String genome, Map<Point, Integer> vision) {

        char[] genomeChar = genome.toCharArray();
        int situation = 4*isGood(1,vision,genomeChar)+2*isGood(0,vision,genomeChar)+1*isGood(-1,vision,genomeChar);
        int reaction = 4*(genomeChar[3*situation+0]-'0')+2*(genomeChar[3*situation+1]-'0')+1*(genomeChar[3*situation+2]-'0');
        return possibleMoves[reaction];

    }
}

Resultado:

Individual scores: 1, 1, 332, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47560, 15457, 1, 
Your final score is 3.7100115087136234
falla
fuente
1

Especímenes cautelosos - C ++ - puntajes de aproximadamente 2030 en 200 ejecuciones

Utiliza la parte de color (16x4 bits) de la codificación de ADN de Blind Faith pero deja el resto (36 bits) del ADN completamente sin usar.

La codificación de un color es:

  • 10XX - para cuadrados seguros;
  • 11XX - para cuadrados letales; y
  • 0000 a 0111 - para los 8 tipos de cuadrados de trampa.

Donde X indica bits no utilizados. Dado que solo 2 de 16 colores son trampas que usarán los 4 bits (y solo si la trampa está compensada, que será el caso 8 de 9 veces), normalmente habrá 64 bits no utilizados - la teoría es que las mutaciones que afectan a cualquiera de estos bits no utilizados no van a destruir el genoma y la estabilidad es mejor que cualquier solución elegante que pueda usar esos bits restantes.

Los especímenes luego usan esto para planificar una ruta segura dentro de una cuadrícula de 7x7 centrada en sí mismos (el 5x5 que su visión permite más 1 cuadrado en cada lado para permitir trampas de desplazamiento) priorizando mover la mayor distancia hacia adelante después de 3 movimientos.

Inicialmente comencé a realizar algunas comprobaciones para asegurarme de que el hecho de que el color en el que se encuentra el espécimen no sea letal se corresponda con el genoma y marque cualquier color erróneo como cuadrados de seguridad INSEGURO (y sus cuadrados adyacentes), sin embargo, agregó una cantidad significativa complicación para ganar poco o nada en comparación con marcar esos cuadrados como SEGUROS y matar algunos especímenes adicionales. Volveré a esto si tengo tiempo.

#include <initializer_list>
#include <vector>

enum class D { SAFE, LETHAL,TRAP_N, TRAP_NE, TRAP_E, TRAP_SE, TRAP_S, TRAP_SW, TRAP_W, TRAP_NW, UNSURE };
enum class X { SAFE, LETHAL, UNSURE };

inline void checkLocation( color_t color, D (&dna)[16], D check )
{
    if ( color != OUT_OF_BOUNDS && dna[color] == check )
        dna[color] = D::UNSURE;
}

inline void updateMapLocation( X (&map)[7][7], unsigned int x, unsigned int y, const X& safety ){
    if (        ( safety == X::LETHAL && map[x][y] != X::LETHAL )
            || ( safety == X::UNSURE && map[x][y] == X::SAFE ) )
        map[x][y] = safety;
}

inline unsigned int isSafePath( X (&map)[7][7], coord_t p )
{
    return map[p.x][p.y] == X::SAFE ? 1 : 0;
}
inline unsigned int isSafePath(X (&map)[7][7],coord_t p,coord_t q,coord_t r){
    if ( isSafePath( map,p ) )
        if ( isSafePath( map, q ) )
            return isSafePath( map, r );
    return 0;
}

inline unsigned int isSafeEast( X (&map)[7][7], coord_t p )
{
    if ( !isSafePath( map, p ) )
        return 0;
    if ( p.x == 6 )
        return 1;
    return isSafeEast(map,{p.x+1,p.y-1})
            +isSafeEast(map,{p.x+1,p.y+0})
            +isSafeEast(map,{p.x+1,p.y+1});
}

template<typename T> inline T max(T a,T b){return a>=b?a:b;}
template<typename T, typename... A> inline T max(T a,T b,A... c){return max(max(a,b),c...); }

coord_t cautiousSpecimins( dna_t d, view_t v ) {
    X map[7][7] = { { X::SAFE } };
    D dna[16] = { D::UNSURE };
    for ( color_t i = 0; i < 16; i++ )
    {
        if ( d[4*i] == 1 )
        {
            dna[i] = d[4*i + 1] == 1 ? D::LETHAL : D::SAFE;
        }
        else
        {
            switch ( dnarange( d, 4*i + 1, 3 ) )
            {
                case 0: dna[i] = D::TRAP_N; break;
                case 1: dna[i] = D::TRAP_NE; break;
                case 2: dna[i] = D::TRAP_E; break;
                case 3: dna[i] = D::TRAP_SE; break;
                case 4: dna[i] = D::TRAP_S; break;
                case 5: dna[i] = D::TRAP_SW; break;
                case 6: dna[i] = D::TRAP_W; break;
                case 7: dna[i] = D::TRAP_NW; break;
                default: dna[i] = D::UNSURE; break;
            }
        }
    }
    if ( v(-1, 0) != OUT_OF_BOUNDS )
        checkLocation( v( 0, 0), dna, D::LETHAL );

    if ( v(-1, 0) != OUT_OF_BOUNDS )
        for ( unsigned int y = 0; y < 7; ++ y )
            map[2][y] = X::LETHAL;

    if ( v(-2, 0) != OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 2; ++x )
            for ( unsigned int y = 0; y < 7; ++ y )
                map[x][y] = X::LETHAL;

    if ( v( 0, 1) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
                map[x][4] = X::LETHAL;

    if ( v( 0, 2) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
            for ( unsigned int y = 5; y < 7; ++ y )
                map[x][y] = X::LETHAL;

    if ( v( 0,-1) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
                map[x][2] = X::LETHAL;

    if ( v( 0,-2) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
            for ( unsigned int y = 0; y < 2; ++ y )
                map[x][y] = X::LETHAL;

    checkLocation( v( 1, 1), dna, D::TRAP_SW );
    checkLocation( v( 1, 0), dna, D::TRAP_W  );
    checkLocation( v( 1,-1), dna, D::TRAP_NW );
    checkLocation( v( 0,-1), dna, D::TRAP_N  );
    checkLocation( v(-1,-1), dna, D::TRAP_NE );
    checkLocation( v(-1, 0), dna, D::TRAP_E  );
    checkLocation( v(-1, 1), dna, D::TRAP_SE );
    checkLocation( v( 0, 1), dna, D::TRAP_S  );

    for ( int x = 1; x <= 5; ++x )
    {
        for ( int y = 1; y <= 5; ++y )
        {
            switch( dna[v(x-3,y-3)] )
            {
                case D::LETHAL : updateMapLocation( map, x+0, y+0, X::LETHAL ); break;
                case D::TRAP_N : updateMapLocation( map, x+0, y+1, X::LETHAL ); break;
                case D::TRAP_NE: updateMapLocation( map, x+1, y+1, X::LETHAL ); break;
                case D::TRAP_E : updateMapLocation( map, x+1, y+0, X::LETHAL ); break;
                case D::TRAP_SE: updateMapLocation( map, x+1, y-1, X::LETHAL ); break;
                case D::TRAP_S : updateMapLocation( map, x+0, y-1, X::LETHAL ); break;
                case D::TRAP_SW: updateMapLocation( map, x-1, y-1, X::LETHAL ); break;
                case D::TRAP_W : updateMapLocation( map, x-1, y+0, X::LETHAL ); break;
                case D::TRAP_NW: updateMapLocation( map, x-1, y+1, X::LETHAL ); break;
//              case D::UNSURE : updateMapLocation( map, x+0, y+0, X::SAFE );
//                               updateMapLocation( map, x+0, y+1, X::UNSURE );
//                               updateMapLocation( map, x+1, y+1, X::UNSURE );
//                               updateMapLocation( map, x+1, y+0, X::UNSURE );
//                               updateMapLocation( map, x+1, y-1, X::UNSURE );
//                               updateMapLocation( map, x+0, y-1, X::UNSURE );
//                               updateMapLocation( map, x-1, y-1, X::UNSURE );
//                               updateMapLocation( map, x-1, y+0, X::UNSURE );
//                               updateMapLocation( map, x-1, y+1, X::UNSURE );
//                               break;
                default        : break;
            }           
        }
    }

    unsigned int north = isSafeEast(map,{4,4});
    unsigned int east  = isSafeEast(map,{4,3});
    unsigned int south = isSafeEast(map,{4,2});
    unsigned int mx    = max( north, east, south );
    unsigned int sz;
    std::vector<coord_t> dir;
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+1,+1} );
        if ( east  == mx ) dir.push_back( {+1,+0} );
        if ( south == mx ) dir.push_back( {+1,-1} );

        return dir[v.rng.rint(dir.size())];
    }


    north = isSafePath(map,{4,4},{5,5},{5,6})
            + isSafePath(map,{4,4},{4,5},{5,6});
    south = isSafePath(map,{4,2},{5,1},{5,0})
            + isSafePath(map,{4,2},{4,1},{5,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+1,+1} );
        if ( south == mx ) dir.push_back( {+1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{3,4},{4,5},{5,6});
    south = isSafePath(map,{3,2},{4,1},{5,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+0,+1} );
        if ( south == mx ) dir.push_back( {+0,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = 2*isSafePath(map,{4,4},{4,5},{4,6})
            + 1*isSafePath(map,{4,4},{3,5},{4,6});
    south = 2*isSafePath(map,{4,2},{4,1},{4,0})
            + 1*isSafePath(map,{4,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+1,+1} );
        if ( south == mx ) dir.push_back( {+1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{3,4},{4,5},{4,6})
            + isSafePath(map,{3,4},{3,5},{4,6});
    south = isSafePath(map,{3,2},{4,1},{4,0})
            + isSafePath(map,{3,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+0,+1} );
        if ( south == mx ) dir.push_back( {+0,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{2,4},{3,5},{4,6});
    south = isSafePath(map,{2,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {-1,+1} );
        if ( south == mx ) dir.push_back( {-1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{3,4},{3,5},{3,6})
            + isSafePath(map,{3,4},{2,5},{3,6});
    south = isSafePath(map,{3,2},{3,1},{3,0})
            + isSafePath(map,{3,2},{2,1},{3,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+0,+1} );
        if ( south == mx ) dir.push_back( {+0,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{2,4},{3,5},{4,6});
    south = isSafePath(map,{2,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {-1,+1} );
        if ( south == mx ) dir.push_back( {-1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    return {-1,-1};
}

Puntajes de muestra:

Scores: 421155 2 129418 71891 90635 1 211 1111987 29745 7 2200750 41793 50500 45 2012072 2 485698 1 110061 1554720 210308 249336 2 1 262110 17 3 19 1719139 23859 45118 3182784 318 2 1 15572 14 2822954 18 11 2 3 15954 1331392 2296280 135015 1 360826 1 692367 4 244775 4814645 3749144 3 1 660000 1 11 3688002 3920202 3428464 123053 1 243520 86 9 6 289576 195966 549120 220918 9 1 43 71046 5213 118177 150678 54639 3 200839 1 3 6 1978584 1514393 119502 1 1 137695 184889 337956 1 1 441405 133902 991 1 4137428 1 1427115 3340977 1 2 1 55559 11 1 94886 30270 1 6 3 69394 264780 6877 47758 128568 1 116672 130539 163747 96253 1 2654354 1 141 58212 1613661 27 9504 1 2474022 843890 1 59 3110814 2353731 150296 313748 2590241 6 5970407 1434171 2 334715 141277 1 56810 2964306 51544 61973 715590 1 106 900384 50948 2 34652 108096 391006 1 2969764 47625 1 24 30481 44 8 1 18 2094036 106461 3080432 75 620651 16 71730 282145 275031 17 1 8 15 121731 18 2 1 1 495868 3252390 6 1 63712 7 3733149 13380 1 1
Geometric mean score: 2030.17

Puntuación máxima durante la prueba: 8.150.817 muestras guardadas.

MT0
fuente
Ahora lo hiciste ... Quería guardar la ruta para más tarde, pero no podía dejar a tus cautelosos roedores sin respuesta :) Como parece, la ruta funciona aún mejor con una codificación más eficiente. Su idea de extender el área de ruta a 7x7 también parece prometedora. Veré si puedo usar eso.
Actualmente estoy haciendo 2000 carreras para esto ... después de las primeras 900, la media parece estar estableciéndose alrededor de 600, que está bastante lejos de 2000. ¿Te importaría volver a ejecutarla también para ver si el 2000 fue solo una casualidad?
Martin Ender