Crea una IA perfecta para el juego 15

8

En el juego 15, dos jugadores se turnan para seleccionar números del 1 al 9 (sin elegir ningún número que cualquiera de los jugadores ya haya seleccionado). Un jugador gana si tiene tres números que suman 15. Si todos los números han sido seleccionados y ninguna combinación de ninguno suma 15, el juego es un empate.

Su tarea es construir una función que tome el estado de un juego de 15 (representado en cualquier forma que desee) y devuelva qué número mover a continuación, que actuará como una IA para jugar el juego con otro jugador. Puede suponer que la posición es legal (ningún jugador tiene más de un número más que el otro jugador, y ningún jugador ya tiene tres números que sumen 15).

La IA debe ser perfecta, es decir, si se le da una posición ganadora, debe forzar una victoria, y si se le da una posición no perdedora (una posición donde su oponente no tiene una estrategia ganadora), no debe permitir su oponente para darle una posición perdedora (que es posible, ya que 15 es un juego resuelto).

El código más corto gana.

(nota: aceptaré la respuesta más corta actualmente y la cambiaré si aparece una respuesta más corta).

Joe Z.
fuente
¿Entiendo correctamente que se nos permite perder si llegamos a una posición ganadora en la que nuestra IA no podría haberse metido?
John Dvorak
Si, eso es correcto. Si a la IA se le presenta un estado del juego que no puede ganar ni empatar (por ejemplo, una trampa doble), entonces se le permite perder. Sin embargo, la IA nunca debe permitir que el juego entre en dicho estado perdedor desde un tablero vacío.
Joe Z.
¿Asumo correctamente que la IA es siempre la primera en jugar?
John Dvorak
1
hmm ... parece que estamos autorizados a empatar incluso si podemos forzar una victoria. ¿Es eso cierto?
John Dvorak
2
Ja Acabo de aprender sobre este juego, y lo primero que hice cuando llegué a casa fue publicarlo aquí. Por desgracia, me han golpeado.
stand

Respuestas:

6

GolfScript ( 129 86 81 85 75 caracteres)

{:C[{.`{1$-\{+15\-}+%}:T+/}/10,1>C~+-:^{.{^T&}+C/,2<*T}/5^{1&}$][]*^&0=}:N;

Formato de entrada esperado: [[int int ...][int int ...]]donde la primera lista son mis números y la segunda lista son los números de mi oponente. Para pruebas interactivas, agregue ~Nal final del script y proporcione una cadena en ese formato: por ejemplo

$ golfscript.rb 15.gs <<<"[[5][2 8]]"
9
$ golfscript.rb 15.gs <<<"[[2][5 8]]"
6

Heurística:

  1. Si puedo ganar este turno, hazlo
  2. Si el oponente ganara el próximo turno, bloquee
  3. Si puedo forzar al oponente a un cuadrado que les impide crear una bifurcación, hazlo
  4. 5 es el único número que puede contribuir a ganar de 4 maneras, así que cógelo si está disponible.
  5. Favorecer los pares sobre las probabilidades

Marco de prueba:

{:Set;[1 5 9 1 6 8 2 4 9 2 5 8 2 6 7 3 4 8 3 5 7 4 5 6]3/{.Set&=},!!}:isWin;
{
    # Mine His
    .isWin{
        "Lost "@`@`++puts
    }{
        # If there are available moves, it's my move.
        # If I won before my move, I've still won after it.
        1$1$+,9<!!{
            # my move
            1$1$[\\]N 2$\+
            # Mine His Mine'
            .isWin!{
                # his move
                10,1>2$2$+-{
                    2$\+1$\
                    # Mine His Mine' Mine' His'
                    fullTest
                    # Mine His Mine'
                }/
            }*;
        }*;;
    }if
}:fullTest;
# I move first
'[][]fullTest'puts [][]fullTest
# He moves first
'[][1]fullTest'puts [][1]fullTest
'[][2]fullTest'puts [][2]fullTest
'[][5]fullTest'puts [][5]fullTest
Peter Taylor
fuente
¿Puede ejecutar esta entrada para mí? [5][3](Debería devolver 4 u 8).
Joe Z.
9- Pero parece que has cambiado las reglas.
Peter Taylor
Además, ¿por qué solo 4o 8?
Peter Taylor
Oh, espera, no importa, estaba equivocado. Cualquier cosa excepto 7debe funcionar, por lo que 9es aceptable.
Joe Z.
Además, no quise cambiar las reglas; es solo que los había expresado mal la primera vez.
Joe Z.
4

Rubí, 330 315 341 caracteres

def m i
$_=i.join
l='159258357456168249267348'.scan /(.)(.)(.)/
return 1 if /^5(28|46|64|82)$/
return 4 if /^[258]{3}$/
return 2 if /^[456]{3}$/
i.each{|i|l.map{|l|return l if(l-=i).size==1&&!/[#{l=l[0]}]/}}
.map{|i|l.map{|m|l.map{|l|return (l&m)[0] if(z=l-i|m-i).size==3&&l!=m&&!/[#{z.join}]/}}}
"524681379".chars{|z|return z if !/#{z}/}
end

Retendré los detalles por ahora, pero digamos que se basa en el algoritmo óptimo para un problema similar que también se ha resuelto y cuyo algoritmo óptimo funciona igual de bien aquí. Se han hecho suposiciones: esto elegirá movimientos malos en situaciones que no pueden ser producidas por este algoritmo jugando contra otro jugador, solo por dos jugadores uno contra el otro.

Entrada: una matriz de dos matrices de cadenas de un dígito. Cada conjunto representa los valores tomados por un jugador: el primero es la IA, el segundo es el oponente.

Salida: ya sea un número o una cadena de un solo dígito. Son semánticamente equivalentes. La normalización de cadenas costaría 8 caracteres.

Tres personajes más pueden salvarse si asumimos que el orden de los números dados por la persona que llama - cambiar la expresión regular en la L5 a /^285$/o /^258$/dependiendo del orden producido a partir del juego (opponent)5-(ai)2-(opponent)8.

John Dvorak
fuente
Parece que tiene un ahorro fácil en las últimas tres líneas simplemente moviéndose 5al inicio de su orden de preferencia.
Peter Taylor
@ah, sí, gracias. Tuve otro paso intermedio que eliminé (con una carcasa especial en la parte superior) y olvidé fusionar los pasos circundantes. Lo editaré cuando llegue a casa (a menos que sea voluntario antes).
John Dvorak
1

GolfScript ( 90 85 84 caracteres)

{.~.,3/*..2%.@^++3*3/{~++15=},,*10,1>2$~+-@`{([2$+]+v[0=~)\]}+%[1,]or$0=+}:v{1=}+:N;

Esto toma un enfoque completamente diferente, pero es potencialmente susceptible a optimizaciones para vencer al heurístico. Aquí hacemos un análisis completo del árbol del juego, increíblemente lento. (No, lo digo en serio. Lleva varias horas ejecutar la prueba completa, principalmente debido a `{...}+que agrega el estado actual al siguiente ciclo de movimiento). Tenga en cuenta que la parte difícil es identificar un estado ganador (un tercio del código, en la actualidad).

Hay algunos trucos feos en las secciones no recursivas. En particular, cuando la posición se identifica como perdedora, tomamos nuestras posiciones como la [value move]matriz, confiando en que el movimiento sea irrelevante y el valor sea distinto de cero.

Peter Taylor
fuente