Hola todos,
El otro día mi hijo pidió jugar la versión en papel cuadriculado de "Battleship". Cada persona tenía 5 "barcos" de 5, 4, 3, 3 y 2 unidades de largo (y una unidad de ancho). Los "barcos" se colocaron en una cuadrícula de 10 por 10 en el espacio XY; cada "barco" tenía un conjunto único de coordenadas (x, y). Por ejemplo, una de las 3 unidades "barcos" podría tener las coordenadas (3,4), (4,4) y (5,4). No más de un "barco" puede ocupar la misma coordenada (x,y). Los "barcos" solo pueden correr vertical u horizontalmente; no se permite un diseño diagonal.
Luego nos turnamos para llamar a pares de coordenadas (x, y) para ver quién tenía un impacto directo en el "barco" de otra persona. Cada uno de nosotros solo tenía 16 turnos para intentar golpear (o hundir) tantos "barcos" de la otra persona. Mientras atravesábamos esto, pensé que debe haber un mejor enfoque para maximizar las posibilidades de golpear (y / o hundir) el "barco" de otra persona que simplemente llamar coordenadas al azar. Por supuesto, no llamarías una coordenada (x, y) que ya hayas usado, ya que sabrías si golpeaste un "barco" o no.
Al principio, pensé que tal vez la plataforma de diseño personalizado sería el camino correcto a seguir, pero si crea un diseño donde Y es "Acertar" (0/1 para no/sí), y X1 = x y X2 = coordenadas y (numérico discreto de 10 niveles), la plataforma generará un diseño en el que solo utiliza los niveles alto y bajo para cada X e Y. Por cierto, los términos del modelo son solo x, y y el término cruzado x*y. Entonces, desafortunadamente, el diseño personalizado no funciona.
La plataforma Full Factorial DOE no funcionará porque quiere hacer 100 corridas (10x10 Factorial), y solo tenemos 16 corridas (intentos) cada uno.
La plataforma RSM DOE solo funciona en los niveles alto/bajo, e ingresando 1 y 10 para los niveles bajo/alto. Las opciones de diseño de CCD realmente no llenan el espacio de la cuadrícula de 10 por 10 donde se colocarían los "barcos", demasiados recorridos centrales para cubrir el espacio de la cuadrícula.
La única otra plataforma que sería aplicable para esto sería Space Filling Design. Usando la misma configuración baja/alta, 1/10 para xey y "Hit" como respuesta (esto sería binario, 0/1 para no/sí), puedo obtener una tabla DOE con emparejamientos (x,y) que llenan el espacio de la cuadrícula. No estoy seguro de cuál sería la mejor opción para los métodos de diseño de relleno de espacio, FFF o Uniform, o Latin Hypercube, etc.
Creo que lo más importante es que el DOE es fijo, no es "adaptable" en el sentido de que, según el resultado de la primera ejecución, ¿cómo se modificaría el DOE para tener en cuenta la información conocida? Usando las coordenadas del barco de 3 unidades de arriba, digamos que mi primera carrera es llamar a las coordenadas (3,4) y obtengo un acierto. Sabiendo que el diseño de los "barcos" es horizontal o vertical, mi próxima llamada no sería seguir el DOE en absoluto, sino llamar (3,5), (3,3), (2,4) , o (4,4): aumentaría x o y en una unidad y vería cuál es el resultado. Y así sucesivamente hasta hundir el barco o pasar a la siguiente coordenada de inicio posible.
Me gustaría encontrar un método más científico para generar un DOE adaptativo que pueda optimizar las 16 ejecuciones para generar "aciertos". Salir de un DOE estático no hará eso porque después de cada ejecución, se "agota" una coordenada, y aprendo si es un éxito o no. Cada ejecución informa a la ejecución subsiguiente n+1. Que yo sepa, no existe un DOE que pueda manejar algo como esto, pero tampoco soy un experto en este campo.
¿Es la selección aleatoria de un punto de partida lo mejor que se puede hacer en "Battleship"? No lo creo, pero estoy teniendo dificultades para descubrir cómo tener un DOE adaptativo que básicamente tenga declaraciones "si/entonces" para optimizar el uso de mis 16 intentos mientras toma en cuenta la información de el paso anterior Sería genial tener un DOE "adaptable" que optimizaría sus elecciones para cada carrera a fin de maximizar sus posibilidades de ganar en 16 intentos.
¡Gracias por la discusión!,
SD
PD: al buscar JMP y "Battleship", encontré esto correo por @Jordan_Hiller que muestra cómo se puede usar JMP para jugar diferentes juegos, y @brady_brady escribió el código JSL para jugar realmente "Battleship". ¡Muy genial! ¡Estará descargando ese JSL pronto!
Hola @Jordan_Hiller ,
Gracias por el enlace al blog, me gustó el artículo.
En general, entiendo el concepto detrás de cómo calcularon la probabilidad de que un barco esté en un cuadrado determinado: esto sería diferente para cada tipo de barco. Sin embargo, dado que el estado de probabilidad del tablero cambiaría después de cada ronda de juego, la elección de la siguiente casilla para disparar cambia, lo que para mí no es más que un diseño de relleno de espacio optimizado que tiene en cuenta los aciertos/errores/ tamaño del barco y número de pasadas restantes.
El cartel del blog pudo generar un algoritmo que puede con el juego en 34 movimientos, que es exactamente el doble del número de casillas ocupadas por los barcos. Presumiblemente, sería posible generar una ruta de decisión óptima que podría acercar a 17 el número requerido de movimientos para ganar. Tal vez no exactamente 17, pero muy cerca.
Ciertamente, un enfoque de ML/AI puede construir un algoritmo para ganar el juego, pero estoy de acuerdo, eso es excesivo y no es lo que realmente busco. Estoy más interesado en tal vez una combinación de lo que hizo la persona del blog y utilizar un DOE. Claramente, la función de densidad de probabilidad para el tablero de juego es fundamental para tomar decisiones. Pero, ¿podría uno modificar eso de un cálculo puramente de probabilidad a uno que se basa en un relleno de espacio optimizado, casi como alimentar la función de probabilidad de la placa como una función de "ponderación" para el DOE, de modo que el DOE generaría los aciertos más probables? Me parece que generar primero el conteo de visitas más alto y luego enfocarse en el hundimiento conduciría a una victoria más rápida en comparación con cómo lo hizo el blogger, que consistía en enfocarse en hundir un barco primero antes de pasar al modo de búsqueda.
De todos modos, lo encontré interesante para considerar y pensar, ¡y aparentemente otros también lo han hecho!
¡Gracias!,
SD
¡Divertida idea, Diedrich!
Aquí hay una publicación de blog antigua sobre este tema, alguien descubrió cómo calcular la probabilidad de que un barco esté en cada casilla de la cuadrícula para cualquier estado del juego. https://www.datagenetics.com/blog/december32011/ Después de eso, ni siquiera necesita un modelo, solo puede elegir el cuadrado más probable. También hay algunos proyectos de aprendizaje automático, ¡pero eso parece excesivo!
Jordán
