Algoritmo para el juego de Chomp

Question

Estoy escribiendo un programa para el juego de Chomp. Puedes leer la descripción del juego en Wikipedia, sin embargo, lo describiré brevemente de todos modos.

Jugamos en una barra de chocolate de Dimension NXM, es decir, la barra está dividida en cuadrados NXM. En cada turno, el jugador actual elige un cuadrado y come todo lo que está debajo y a la derecha del cuadrado elegido. Entonces, por ejemplo, el siguiente es un primer movimiento válido:

El objetivo es obligar a tu oponente a comer la última pieza de chocolate (está envenenado).

Con respecto a la parte AI, utilicé un algoritmo Minimax con truncamiento de profundidad. Sin embargo, no puedo encontrar una función de evaluación de posición adecuada. El resultado es que, con mi función de evaluación, es bastante fácil para un jugador humano ganar contra mi programa.

Puede alguien:

• Sugerir una buena función de evaluación de posición o
• proporcionar alguna referencia útil o
• ¿Sugerir un algoritmo alternativo?

Answer 1

¿Qué tan grandes son tus tableros?

Si tus tableros son bastante pequeños, entonces puedes resolver el juego exactamente con programación dinámica. En Python:

n,m = 6,6
init = frozenset((x,y) for x in range(n) for y in range(m))

def moves(board):
    return [frozenset([(x,y) for (x,y) in board if x < px or y < py]) for (px,py) in board]

@memoize
def wins(board):
    if not board: return True
    return any(not wins(move) for move in moves(board))

La función gana (placa) calcula si la placa es una posición ganadora. La representación del tablero es un conjunto de tuplas (x, y) que indica si la pieza (x, y) todavía está en el tablero. La función mueve la lista de calculaciones de tableros accesibles en un solo movimiento.

La lógica detrás de la función WINS funciona así. Si el tablero está vacío en nuestro movimiento, el otro jugador debe haber comido la última pieza, por lo que ganamos. Si el tablero no está vacío, entonces podemos ganar si hay any Mover podemos hacer de tal manera que la posición resultante sea una posición perdedora (es decir, no ganar, es decir not wins(move)), porque entonces llevamos al otro jugador a una posición perdedora.

También necesitará la función de ayuda para el ayudante que almacena en caché los resultados:

def memoize(f):
    cache = dict()
    def memof(x):
        try: return cache[x]
        except:
            cache[x] = f(x)
            return cache[x]
    return memof

Al almacenar en caché solo calculamos quién es el ganador de una posición determinada una vez, incluso si esta posición es accesible de múltiples maneras. Por ejemplo, se puede obtener la posición de una sola fila de chocolate si el primer jugador come todas las filas restantes en su primer movimiento, pero también se puede obtener a través de muchas otras series de movimientos. Sería un desperdicio calcular quién gana en la placa de una sola fila una y otra vez, por lo que almacenamos el resultado. Esto mejora el rendimiento asintótico de algo como O((n*m)^(n+m)) a O((n+m)!/(n!m!)), una gran mejora, aunque todavía lenta para tableros grandes.

Y aquí hay una función de impresión de depuración para conveniencia:

def show(board):
    for x in range(n):
        print '|' + ''.join('x ' if (x,y) in board else '  ' for y in range(m))

Este código sigue siendo bastante lento porque el código no está optimizado de ninguna manera (y esto es Python ...). Si lo escribe en C o Java de manera eficiente, probablemente pueda mejorar el rendimiento de más de 100 veces. Debería poder manejar fácilmente las tablas de 10x10, y probablemente pueda manejar hasta 15x15 tablas. También debe usar una representación de tablero diferente, por ejemplo, una tabla de bits. Tal vez incluso podría acelerarlo 1000X si utiliza múltiples procesadores.

Aquí hay una derivación de Minimax

Comenzaremos con Minax:

def minimax(board, depth):
  if depth > maxdepth: return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move, depth-1))
    return alpha

Podemos eliminar la verificación de profundidad para hacer una búsqueda completa:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move))
    return alpha

Debido a que el juego terminó, Heuristic regresará -1 o 1, dependiendo de qué jugador ganó. Si representamos -1 como falso y 1 como verdadero, entonces max(a,b) convertirse en a or b, y -a convertirse en not a:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not minimax(move)
    return alpha

Puedes ver que esto es equivalente a:

def minimax(board):
  if not board: return True
  return any([not minimax(move) for move in moves(board)])

Si en su lugar habíamos comenzado con Minimax con poda Alpha-Beta:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -beta, -alpha))
      if alpha >= beta: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

La búsqueda comienza con alfa = -1 y beta = 1. Tan pronto como el alfa se convierte en 1, el bucle se rompe. Por lo tanto, podemos suponer que Alpha se queda -1 y Beta se mantiene 1 en las llamadas recursivas. Entonces el código es equivalente a esto:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -1, 1))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

Por lo tanto, podemos simplemente eliminar los parámetros, ya que siempre se pasan como los mismos valores:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board)

Podemos volver a hacer el cambio de -1 y 1 a los booleanos:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not alphabeta(move))
      if alpha: break
    return alpha

Por lo tanto, puede ver que esto es equivalente a usar cualquiera con un generador que detenga la iteración tan pronto como haya encontrado un valor verdadero en lugar de calcular siempre toda la lista de niños:

def alphabeta(board):
  if not board: return True
  return any(not alphabeta(move) for move in moves(board))

Tenga en cuenta que aquí tenemos any(not alphabeta(move) for move in moves(board)) en vez de any([not minimax(move) for move in moves(board)]). Esto acelera la búsqueda en aproximadamente un factor de 10 para tableros de tamaño razonable. No porque la primera forma sea más rápida, sino porque nos permite omitir todo el resto del bucle, incluidas las llamadas recursivas tan pronto como hemos encontrado un valor que es cierto.

Así que ahí lo tienes, la función de victorias fue solo una búsqueda de alfabeta disfrazada. El siguiente truco que usamos para las victorias es memorizarlo. En la programación de juegos, esto se llamaría usando "tablas de transposición". Por lo tanto, la función WINS está haciendo una búsqueda de alfabeta con tablas de transposición. Por supuesto, es más simple escribir este algoritmo directamente en lugar de pasar por esta derivación;)

Answer 2

No creo que sea posible una buena función de evaluación de posición, porque a diferencia de los juegos como el ajedrez, no hay 'progreso' antes de ganar o perder. El artículo de Wikipedia sugiere que una solución exhaustiva es práctica para las computadoras modernas, y creo que encontrará que este es el caso, dado una memoización y optimización adecuadas.

Un juego relacionado que puede encontrar de interés es Nim.