Antecedentes

Mu Torere es un juego que es uno de los dos únicos jugados por los maoríes de Nueva Zelanda antes de la influencia europea. Esto lo convierte en un juego muy singular, ya que tiene un "criterio objetivo ganador" y reglas de juego que son diferentes de la mayoría de los otros juegos existentes.

Como se Juega:

El tablero es un octágono. Hay conexiones entre cada vértice adyacente, y hay un nodo central que está conectado a todos los vértices. En cualquier momento, ocho de los nueve nodos están ocupados por piedras. Al principio, hay cuatro piedras blancas y cuatro piedras negras que ocupan la mitad del octágono, con el nodo central vacío. El negro se mueve primero.

Cada turno, un jugador puede mover una de sus piedras a lo largo de uno de los 16 bordes de un nodo al nodo vacío. Una piedra solo se puede mover de un nodo externo al nodo central si la piedra está al lado de la piedra de un oponente.

Un jugador pierde cuando no puede hacer un movimiento legal, lo que ocurre cuando no hay un borde que conecte una piedra al nodo vacío.

Aquí hay un sitio web que explica las reglas (con un diagrama) y ofrece algunos análisis.

El reto

Su desafío es escribir el programa más corto que pueda jugar un juego perfecto de Mu Torere contra un oponente humano. Su programa debería poder mostrar y actualizar el tablero de juego, hacer movimientos y recibir movimientos de un oponente humano. Lo más importante, debe jugar un juego perfecto.

Juego perfecto?

Sí, juego perfecto. He estado haciendo un análisis del juego, y descubrí que el juego dura una cantidad infinita de tiempo si ambos jugadores lo juegan perfectamente. Esto significa que su programa nunca debería perder. Además, su programa debería ser capaz de forzar una victoria siempre que el oponente humano cometa un error que le permita forzar una victoria. En cuanto a cómo su programa encuentra el movimiento perfecto, esto depende de usted.

Detalles

Después de cada movimiento (y al comienzo del juego), su programa debe imprimir el tablero de juego. Sin embargo, si elige mostrar la placa, debe mostrar todos los nodos y estar completamente conectada (las 16 líneas de conexión deben dibujarse sin líneas cruzadas). Al comienzo, el tablero debe tener la posición inicial correcta. Una forma de lograr esto es haciendo que el tablero de juego sea un cuadrado.

w-w-w
|\|/|
b-o-w
|/|\|
b-b-b

Los dos colores son blanco y negro, u oscuro / claro. El tablero debe mostrar qué nodos están ocupados por las piezas de cada jugador, como marcarlos con una "b" o "w", y qué nodo está vacante. Se alienta a los participantes (pero no es obligatorio) a hacer que el tablero de juego sea más gráfico, en lugar de texto simple.

Su tablero de juego debe tener un sistema de numeración que le dé a cada nodo un número único. Puede elegir numerar el tablero de la forma que desee, pero debe explicarse en su respuesta o en el programa. El tablero cuadrado se puede numerar de la siguiente manera:

1-2-3
|\|/|
4-5-6
|/|\|
7-8-9

El humano es el primero en moverse. Su entrada será un solo número. Este será el número del nodo donde está actualmente la piedra movida. Si quisiera mover una piedra del nodo 4 a un nodo vacío 5, escribiré a 4. El 5 está implícito ya que es el único nodo vacío.

Suponga que el humano siempre hará un movimiento legal.

Después de que el humano hace su movimiento, se debe imprimir un tablero actualizado. Después de que su programa decida un movimiento legal, debe imprimir otro tablero actualizado y luego esperar a que el humano ingrese otro movimiento.

Su programa debe finalizar una vez que haya ganado.

Notas

Se aplican reglas de golf de código estándar, sin acceso a archivos externos, etc., etc. Además, voy a imponer un límite de tiempo flexible de 15 segundos (en una máquina razonable) para que su programa realice cada uno de sus movimientos. Como se indicó, este juego tiene la posibilidad de formar bucles infinitos, y no quiero que una búsqueda profunda profundice en un bucle infinito.

Ruby, 390 caracteres

o=->s,c{f=s=~/o/;[*0..8].select{|t|s[t]==c&&(t<1||(t+6)%8+1==f||t%8+1==f||f<1&&(s[(t+6)%8+1]!=c||s[t%8+1]!=c))}.map{|t|k=s*1;k[f]=c;k[t]=?o;k}}
v=->s,c,h{f=o[s,c];f==[]?0:h<1?1:2-f.map{|t|v[t,c>?b??b:?w,h-1]}.min}
q=->g{puts"1-2-3\n|\\|/|\n8-0-4\n|/|\\|\n7-6-5\n".tr"0-8",g;$>.flush}
q[g="obbbbwwww"]
(g.tr!?o,?b;g[gets.to_i]=?o;q[g];q[g=o[g,?w].sort_by{|q|v[q,?w,5]}[-1]])while v[g,?b,5]>0

Una implementación en ruby ​​que calcula directamente el árbol del juego (que requiere bastante código) y, por lo tanto, siempre se juega de manera óptima. Las posiciones del tablero están en espiral hacia afuera como se muestra en la siguiente figura:

1 - 2 - 3
| \ | / |
8 - 0 - 4
| / | \ |
7 - 6 - 5

bash y amigos ( 463 447 caracteres)

t(){ tr 0-8a-i $b$b
}
p(){ t<<E
0-1-2
|\|/|
3-4-5
|/|\|
6-7-8

E
}
g(){ b=`tr $x$e $e$x<<<012345678|t`
p
e=$x
}
b=bbbbowwww
e=4
m=0
p
while [ $m != 5 ]&&read x;do
g
m=0
for y in {0..8};do
s=0
S=05011234
grep -E "w.*($y$e|$e$y)"<<<${b:$y:1}30125876340142548746>/dev/null&&for p in wow.\*/ww wow.\*/w bbo.\*/b obb.\*/b www wbw .
do
((s++))
tr $y$e $e$y<<<3012587630/4e|t|grep $p>/dev/null&&break
done
s=${S:$s:1}
[ $s -gt $m ]&&m=$s x=$y
done
g
done

El humano juega como b, la computadora comow . La posición del tablero está numerada como en el documento aquí en la parte superior. Resulta que las heurísticas para jugar un juego perfecto son sorprendentemente simples.

Por otro lado, perder el camino interesante es bastante difícil. http://ideone.com/sXJPy demuestra el suicidio más corto posible contra este bot. Tenga en cuenta que el 0 adicional al final es para probar que se sale del bucle correctamente.