¿Cuáles son algunos juegos con heurística bastante simple para evaluar las posiciones?

Question

le estoy enseñando a un niño de programación, y estoy introduciendo algunos conceptos básicos de la inteligencia artificial en el momento. Para empezar vamos a implementar un juego de tres en raya que busca todo el árbol de juego y, como tal, juega perfectamente. Una vez que terminamos, quiero aplicar los mismos conceptos a un juego que tiene demasiadas posiciones para evaluar cada una, por lo que debemos implementar una heurística para evaluar las posiciones intermedias.

Lo mejor que se me ocurrió fue Dots and Boxes. Tiene la ventaja de que puedo establecer el tamaño del tablero arbitrariamente grande para evitar que busque todo el árbol, y puedo hacer que una función de puntuación muy básica sea el número de mis cuadros menos el número de casillas de oponente. Desafortunadamente, esto significa que durante la mayor parte del comienzo del juego cada posición se evaluará de manera equivalente con una puntuación de 0, ya que se requieren bastantes movimientos antes de que los jugadores comiencen a hacer cajas.

¿Alguien tiene alguna idea mejor para juegos? (¿O una mejor función de puntuación para puntos y cuadros)?

Answer 1

¿Qué tal Reversi? Tiene un espacio de heurística bastante bueno basado en el número de piezas, el número de piezas de borde y el número de piezas de esquina.

Answer 2

¿Qué le parece comenzar su juego de Puntos y Cajas con líneas al azar ya agregadas? Esto puede llevarte a la acción rápidamente. Solo necesita asegurarse de no iniciar el juego con ningún recuadro.

Answer 3

Otra opción de juego podría ser Reversi aka Othello.

Una heurística ingenua sería simplemente contar el número de fichas ganado por cada movimiento válido y elegir el más grande. Desde allí, puedes factorizar la posición de la tabla y minimizar de manera vulnerable al oponente.

Answer 4

Tome un vistazo a Go.

• Bastante simple para niños en tablas muy pequeñas.
• Complejidad escalas infinitamente.
• tiene un montón de papeles disponibles, algoritmos y programas para utilizar ya sea como una escala o base. Se mencionó reversi, que es una variante simplificada del Go:

actualización. Podría ser una mejor opción.

Answer 5

Un juego que puede considerar es Connect Four. Juego simple con reglas simples pero más complicado que Tic-Tac-Toe.

Answer 6

Four in a line lo suficientemente duro, pero es bastante fácil para llegar a una función de evaluación de trabajo fácil, por ejemplo, (la distancia a cuatro de mi línea más larga - distancia a cuatro de línea más larga de mi oponente)

Answer 7

¿Qué tal Mancala? Solo hay 6 posibles movimientos en cada turno, y es fácil calcular el puntaje resultante para cada uno, pero es importante considerar la respuesta del oponente, y el árbol del juego se agranda bastante rápido.

Answer 8

Gomoku es un juego simple y divertido para escribir AI.

Answer 9

Damas le permitirá enseñar a varios métodos. Búsqueda simple, búsqueda exhaustiva de las decisiones del mejor de los casos, las diferencias entre las ganancias a corto y a largo plazo, y algo en lo que podrían continuar trabajando después de aprender lo que desea enseñarles.

Personalmente creo que el último bit es el más crítico: hay puntos naturales en el desarrollo de la IA que son buenos para detenerse, ver si se puede superar y luego profundizar en los mecanismos de IA más profundos. Mantiene a su estudiante interesado sin sentirse terriblemente frustrado, y les da más que hacer por sí mismos si quieren continuar el proyecto.

Answer 10

Rubik's Infinity 's bastante divertido, es un poco como Conecta Cuatro, pero sutilmente diferente. Evaluar una posición es bastante fácil.

Arreglé un guión de Perl para reproducirlo hace un tiempo, y en realidad tuve que reducir el número de movimientos por delante, o me golpeaba cada vez, generalmente con tácticas bastante sorprendentes.

Answer 11

En lo que respecta a una mejor heurística de puntos y cajas, sugiero mirar guías de estrategia en línea para el juego. El first result en Google para "estrategia de puntos y casillas" es bastante útil.

Saber utilizar la regla de la cadena separa a un jugador bueno de una buena. Saber cuándo funcionará la regla de la cadena en su contra es lo que separa a los mejores jugadores de los buenos.

Answer 12

me gusta mucho Conecta Cuatro. Muy fácil de programar usando un algoritmo Minimax. Una buena función de evaluación podría ser:

eval_score = 0 
for all possible rows/lines/diagonals of length 4 on the board: 
    if (#player_pieces = 0) // possible to connect four here? 
     if (#computer_pieces = 4) 
      eval_score = 10000 
      break for loop 
     else 
      eval_score = eval_score + #computer_pieces 
      (less pieces to go -> higher score) 
     end if 
    else if (#player_pieces = 4) 
     eval_score = -10000 
     break for loop 
    end if 
end for 

Para mejorar el programa puede agregar:

1. Si el equipo se mueve primero, jugar en la columna central (esto ha sido demostrado ser óptimo)
2. poda alfa-beta
3. Mover pedidos
4. Zobrist Hashes