¿Qué consejos generales tienes para crear un bot para participar en un desafío de King of the Hill? ¿Qué estrategias utilizas para pasar de considerar el desafío a crear tu bot? ¿Qué estructuras de datos le resultan más útiles?

Por favor, publique un consejo por respuesta.

Encontrar los equilibrios de Nash

Este es un concepto muy importante cuando el KOTH involucra un conjunto relativamente simple de decisiones, involucra solo a unos pocos jugadores (típicamente 2) y es determinista. Un equilibrio de Nash describe una posición de "estancamiento": si los dos jugadores han decidido sus dos estrategias, entonces los dos jugadores están efectivamente encerrados en esas posiciones: cualquier jugador que cambie su estrategia simplemente crea vulnerabilidades adicionales.

Ejemplos de juegos donde los equilibrios de Nash son importantes son:

• Piedra-Papel-Tijera (-Lizard-Spock), en el que una estrategia "inmejorable" es un juego aleatorio
• Morra , que tiene un "espectro" de equilibrios. Peter Taylor escribió un buen ejemplo en su respuesta aquí .
• Prisoner's Dilemma, un juego cooperativo notable por tener un estancamiento de "todos pierden"

¿Cómo encontrar un equilibrio?

Encontrar un equilibrio en realidad es bastante simple para la mayoría de los juegos simples, y a menudo es bastante intuitivo. Se pueden encontrar muchos detalles sobre los diversos métodos en Internet. El concepto básico, que normalmente es aplicable, es crear una lista de posibles estrategias que los dos jugadores puedan usar (las opciones proporcionadas por el juego). Si una estrategia está "dominada" por otra, entonces esa estrategia puede eliminarse de la lista y el proceso se repite. Por "dominación" quiero decir que si la estrategia A siempre da un resultado igual o mejor que la estrategia B, contra todas las estrategias restantes del oponente, entonces la estrategia B puede eliminarse de la lista.

Ejemplo: piedra, papel, tijera

RPS tiene algo llamado equilibrio "mixto", lo que significa que hay una distribución involucrada. En lugar de jugar el mismo movimiento repetidamente (lo que conducirá a una derrota rápida), el equilibrio es jugar 1/3 de piedra, 1/3 de papel y 1/3 de tijera en una distribución aleatoria. Si juego al azar, no hay nada que mi oponente pueda hacer para obtener una ventaja sobre mí, punto. Si mi oponente elige no jugar al azar, eso solo crea una vulnerabilidad de su parte.

Los juegos con equilibrio mixto son probablemente los más comunes en PPCG, ya que pueden tomar muchas formas (el único juego interesante que se me ocurre con un equilibrio puro es el dilema del prisionero). Debo señalar que el equilibrio mixto no tiene que ser uniformemente aleatorio , simplemente algo más que jugar el mismo movimiento cada vez.

Usando esta información

El equilibrio de Nash de un juego a menudo representa la "línea de base" desde la cual debes intentar operar. En RPS, jugar aleatoriamente garantiza un punto final alrededor del medio del paquete. Para pasar a la cima, debes comenzar a identificar las debilidades de otros jugadores.

Para hacer esto, debes mantenerte en el equilibrio cuando no estés seguro de las debilidades del oponente. Una vez que esas debilidades han sido identificadas (has detectado que tu oponente no está en equilibrio), entonces necesitas salir suavemente del equilibrio para aprovechar a tu oponente. Esta acción, a su vez, crea debilidades por tu parte. Luego debes detectar cuándo tu oponente está cambiando su estrategia, para que luego puedas detener el ataque y reanudar el juego aleatorio.

Detección de variación del equilibrio

Esto es bastante difícil, y no soy un experto. Las variaciones pueden venir en muchas formas:

• Favorecer algunas opciones por encima / por debajo de otras sin ninguna razón, como un jugador RPS que juega rock dos veces más que las tijeras, o uno que evita jugar papel. Algunas estadísticas relativamente simples pueden detectar esto.
• Basando un movimiento actual de movimientos pasados, en un patrón predecible. Esto incluye copy-cats, bots "late lo que supera tu último movimiento" o bots "ciclismo". Esto requiere una lógica adicional para detectar, ya que la distribución general del movimiento se puede distribuir uniformemente, aunque los movimientos no sean aleatorios. Debes intentar tomar el registro de movimientos y encontrar correlaciones como "el movimiento que hice hace 2 turnos y el movimiento que hizo mi oponente ahora" y "el movimiento que hizo hace 1 turno y el movimiento que hizo ahora", etc.
• Bots cuya distribución de movimientos se basa en la tuya. La vulnerabilidad en estos bots a menudo no se crea (en una cantidad medible) hasta después de que usted haya variado de una distribución aleatoria. En general, su propio bot cae en esta categoría.

Sea específico sobre los requisitos para ejecutar su bot

Los bots se pueden escribir en una variedad de idiomas (y versiones de esos idiomas), por lo que ayuda a todos cuando:

1. Pruébelo en el entorno que especifica el OP (o lo más cerca posible).
2. Pruébelo en una variedad de otros entornos si es posible (para ayudar a otros que quieran ejecutarlo).
3. Sea específico sobre el idioma y la versión que usa, y explique cómo ejecutar su bot.

Como beneficio adicional: si está utilizando un lenguaje menos conocido, haga un enlace donde las personas puedan descargar el binario / fuente para ejecutarlo.

Si se basa en equipo, trabaje junto con su equipo

Si bien generalmente puedes escribir un bot que funcione solo para completar tareas para ayudar a tu equipo, hay una ventaja mucho mayor cuando coordinas tanto dentro como fuera del juego. Un excelente ejemplo de esto se puede ver en Red vs. Blue - Pixel Team Battlebots .

Durante el desarrollo, los equipos pudieron conversar y discutir cómo coordinar sus bots para que funcionen mejor que solos. Si bien técnicamente es el mismo bot, SphiNotPi3000 fue escrito para trabajar en conjunto con otro de sí mismo, y fue capaz de moverse de una manera que explica las debilidades que habría enfrentado si fuera solo. El resultado final fue que pudieron dominar casi por completo el campo de batalla, incluso cuando solo eran ellos dos contra todo el otro equipo .

Entonces, fuera del juego, planifique y coordine con sus compañeros de equipo sobre qué estrategias cubrir. ¿Quizás alguien tiene un bot que escanea el mapa en diagonal? Haga que el suyo escanee horizontalmente (solo un ejemplo). Dentro del juego, si el desafío permite la comunicación del equipo, aprovéchalo. En el juego Battlebots, por ejemplo, puedes enviar un mensaje a tus compañeros de equipo sobre la posición de los bots fuera de su campo de visión, y luego alentarlos a escribir sus bots de una manera compatible para hacer uso de esas señales.

Usa una meta estrategia

Para casi todas las estrategias inteligentes hay otra estrategia que la supera: por ejemplo, tu oponente podría usar exactamente el mismo razonamiento que tú para anticipar tu próximo movimiento y luego contrarrestarlo. Ahora puede intentar adivinar nuevamente a su oponente, pero es difícil saber cuándo detenerse .

Otro problema es que una estrategia que es buena para adivinar un oponente inteligente podría estar lejos de ser óptima contra oponentes más simples.

¿Cómo puedes resolver esto? ¡Dejas que tu bot decida sobre la marcha qué estrategia usar!

Para esto, comienzas con darle a tu bot un repertorio de diferentes estrategias. Luego, antes de cada movimiento, tu bot observa el historial registrado del juego hasta el momento y evalúa cómo les habría ido a estas diferentes estrategias. Luego muestra la que habría tenido más éxito.

Incluir estrategias que sean fuertes en primer lugar ayudará a darle a su bot buenas opciones para elegir. Pero también debes incluir los realmente simples, porque a menudo funcionan mejor contra oponentes tontos.

Puede considerar sesgar algunas estrategias, ya sea para evitar el sobreajuste (por ejemplo, tratar de superar un patrón en el que el oponente simplemente actúa al azar) o favorecer ciertas estrategias al principio cuando aún no hay mucha información.

Por supuesto, este enfoque solo funcionará para ciertos tipos de desafíos del rey de la colina. Me fue muy bien en un partido de Rock-Paper-Scissors-Lizard-Spock . En otros juegos puede ser casi imposible evaluar cómo le habría ido a una determinada estrategia si no se hubiera jugado realmente.

Una forma extrema de este meta enfoque (que raya en hacer trampa) sería incluir el comportamiento conocido de todos los demás bots en su propio bot, de modo que pueda anticipar perfectamente sus movimientos.