Crea un programa determinista para jugar n d tic-tac-toe con los otros concursantes.
Su programa debería funcionar cuando n
(ancho) y d
(número de dimensión) están en estos rangos:
n∈[3,∞)∩ℕ ie a natural number greater than 2
d∈[2,∞)∩ℕ ie a natural number greater than 1
n = 3; d = 2
(3 2 es decir, 3 por 3):
[][][]
[][][]
[][][]
n = 3; d = 3
(3 3 es decir, 3 por 3 por 3):
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
n = 6; d = 2
(6 2 es decir, 6 por 6):
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
Y así.
Entrada:
La entrada será a STDIN. La primera línea de entrada será dos números, n
y d
en la forma n,d
.
Después de esto habrá una línea que consiste en coordenadas que especifican los movimientos que se han realizado. Coordenadas se mostrarán en el formulario: 1,1;2,2;3,3
. La esquina superior izquierda es el origen (0,0 para 2D). En el caso general, esta lista será como 1,2,...,1,4;4,0,...,6,0;...
donde el primer número representa izquierda-derecha-ness, el segundo arriba-abajo-ness, el tercero a la 3ra dimensión, etc. Tenga en cuenta que la primera coordenada es X
el primer giro, el segundo es O
el primer turno ...
Si este es el primer movimiento, la entrada será un número seguido de 1 línea en blanco.
Por coherencia, la entrada siempre terminará con una nueva línea. Entrada de muestra (\ n es nueva línea):
10,10\n0,0,0,0,0,0,0,0,0,0;0,2,3,4,5,6,7,8,9,0;0,1,2,3,4,5,6,7,8,9\n
Para el primer movimiento:
10,10\n\n
¿Dónde \n
está el personaje de nueva línea?
Salida:
Imprima el movimiento que desea realizar en el mismo formato que la entrada (una lista separada por comas). Un movimiento no válido (es decir, uno que ya se ha realizado) dará como resultado una pérdida para el juego.
Nota: Puede usar un generador de números aleatorios, siempre que lo siembre con un valor tal que cada ejecución sea idéntica en las mismas condiciones. En otras palabras, el programa debe ser determinista.
Nota: solo se permiten movimientos válidos.
Juegos ganadores (si ha jugado suficientes tic tac toe multidimensionales, esto es lo mismo).
Para que haya una victoria, un jugador debe tener todos los cuadrados adyacentes a lo largo de una línea. Es decir, ese jugador debe tener n
movimientos en una línea para ser un ganador.
Adyacente:
- cada azulejo es un punto; por ejemplo (0,0,0,0,0) es un punto en
d=5
- las fichas adyacentes son fichas, de modo que ambos son puntos en la misma unidad d-cubo. En otras palabras, la distancia de Chebyshev entre las fichas es 1.
- en otras palabras, si un punto
p
es adyacente a un puntoq
, entonces cada coordenada enp
s coordenada correspondienteq
difiere de ella en no más de uno. Además, al menos en el par de coordenadas difiere exactamente en uno.
Líneas:
- Las líneas están definidas por vectores y un mosaico. Una línea es cada mosaico golpeado por la ecuación:
p0 + t
<
some vector with the same number of coordinates as p0>
Simulación y condiciones ganadoras:
Indique en su respuesta si está listo para calificar. Es decir, indique claramente si su respuesta está hecha o no.
Si su respuesta está marcada como terminada, no se calificará hasta al menos 24 horas después de la última edición del código.
Los programas deben funcionar sin conexión. Si se descubre que un programa está haciendo trampa, recibirá automáticamente una puntuación de
-1
, y no se puntuará más. (¿Cómo terminaría alguien con sus programas haciendo trampa?)Si su programa produce resultados no válidos, se cuenta inmediatamente como una pérdida para el juego.
Si su programa no produce resultados después de 1 minuto, se cuenta inmediatamente como una pérdida para el juego. Si es necesario, optimice la velocidad. No quiero tener que esperar una hora para probar un programa de otro.
Cada programa se ejecutará contra los otros programas dos veces para cada uno
n
en el rango[3,6]
y cada unod
en el rango[2,5]
, una vez comoX
y una vez comoO
. Esta es una ronda.Por cada juego que gana un programa, llega
+3
a su puntaje. Si el programa empató (1 victoria y 1 derrota en una sola ronda o empates para ambos juegos), entonces se pone+1
. Si el programa se pierde, entonces se obtiene+0
(es decir, sin cambios).El programa con la puntuación más alta gana. En caso de empate, gana el programa con el menor número de juegos perdidos (fuera de los concursantes empatados).
Nota: Dependiendo de la cantidad de respuestas, es posible que necesite ayuda para ejecutar las pruebas.
¡Buena suerte! ¡Y que las simulaciones corran siempre a tu favor!
fuente
Respuestas:
Python 3
Esto es simplemente un ai aleatorio. Selecciona aleatoriamente un movimiento fuera de los movimientos que todavía están disponibles.
fuente
Python 2.7
Esta es una presentación de trabajo en progreso que estoy proporcionando para dar un esqueleto / inspiración a otros respondedores. Funciona enumerando todas las líneas ganadoras posibles, luego aplicando un poco de heurística para calificar esa línea de acuerdo con lo valiosa que sea. Actualmente, la heurística está en blanco (trabajos súper secretos). También he agregado el manejo de errores de victoria y choque.
Notas sobre el problema
¿Cuántas líneas ganadoras hay? Considere el caso unidimensional; Hay 2 vértices, 1 borde y 1 línea. En 2 dimensiones, tenemos 4 vértices unidos por 2 líneas y 4 bordes unidos por 2 * n líneas. En 3 dimensiones, tenemos 8 vértices unidos por 4 líneas, 12 bordes unidos por 6 * n líneas y 6 caras unidas por
3*n^2
líneas.En general, llamemos a un vértice una faceta 0, una arista una faceta, etc. Luego
N(i)
denotemos el número de facetas i,d
el número de dimensiones yn
la longitud del lado. Entonces el número de líneas ganadoras es0.5*sum(N(i)*n^i,i=0..d-1)
.Según wikipedia,
N(i)=2^(d-i)*d!/(i!*(n-1)!)
la fórmula final es:sum(2^(d-i-1) n^i d! / (i! * (n-i)!),i=0..d-1)
que wolfram | alpha no le gusta mucho. Esto se hace muy grande rápidamente, así que no espero que mi programa tenga un tiempo de ejecución manejable para d> 8.
Algunos resultados (perdón por el formato:
I / O
Por el momento, la entrada debe ingresarse como:
tictactoe.py <ret> n,d <ret> move;move <ret>
- observe las múltiples líneas y no la final;
.El resultado se ve
(x_1,x_2,x_3...)
, por ejemplo:tictactoe.py <ret> 6,5 <ret> <ret>
=>0, 0, 0, 0, 0
tictactoe.py <ret> 6,5 <ret> 0,0,0,0,0;0,0,0,0,5 <ret>
=>0, 0, 0, 5, 0
Editar: para E / S, lógica agregada. Creo que esto ya está listo para marcar
Tenga en cuenta que este comentario fue inicialmente un marcador de posición que eliminé y eliminé.
fuente
Python 2
La mayor parte del código es exactamente el mismo que la IA aleatoria de Quincunx . En lugar de seleccionar un movimiento al azar, elige el primer movimiento disponible lexicográficamente (es decir (0,0, ... 0), luego (0,0, ... 1), luego (0,0, ... 2) , etc.)
Esta es una estrategia bastante basura, pero casi siempre es mejor que jugar al azar.
fuente