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

language-agnostic artificial-intelligence (12)

Estoy enseñando a un niño a programar, y estoy presentando algunos conceptos básicos de inteligencia artificial en este 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 pude pensar fue en 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 mejores ideas para juegos? (¿O una mejor función de puntuación para puntos y cuadros)?

¿Qué hay de 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.

¿Qué hay de 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.

¿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.

Con respecto a una mejor heurística para puntos y cuadros, sugiero consultar las guías de estrategias en línea para el juego. El primer resultado en Google para "estrategia de puntos y casillas" es bastante útil.

Saber cómo usar la regla de la cadena separa un jugador OK de uno bueno. Saber cuándo funcionará la regla de la cadena en su contra es lo que separa a los mejores jugadores de los buenos.

Eche un vistazo a Go.

Lo suficientemente simple para niños en tableros muy pequeños.
La complejidad se escanea infinitamente.
Tiene muchos documentos disponibles, algoritmos y programas para usar como una escala o base.

Actualización: se mencionó reversi, que es una variante simplificada de Go. Podría ser una mejor opción.

Las damas te permitirán enseñar 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 aspecto 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 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.

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

Una heurística ingenua sería simplemente contar la cantidad de fichas ganadas por cada jugada válida y elegir la más grande. Desde allí, puedes factorizar la posición de la tabla y minimizar de manera vulnerable al oponente.

Realmente me gusta Connect Four. 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:

Si la computadora se mueve primero, juegue en la columna del medio (esto se ha demostrado que es óptimo)
Poda alfa-beta
Mover ordenando
Zobrist Hashes

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

Cuatro en una línea Lo suficientemente difícil, pero lo suficientemente fácil como para llegar a una función de evaluación de trabajo fácil, por ejemplo, (distancia a cuatro de mi línea más larga - distancia a cuatro desde la línea más larga de mi oponente)

Gomoku es un juego agradable, simple y divertido para escribir AI.

Rubik''s Infinity es bastante divertido, se parece un poco a Connect Four pero sutilmente diferente. Evaluar una posición es bastante fácil.

Hice un guión de Perl para tocarlo hace un tiempo, y en realidad tuve que reducir el número de movimientos que tenía delante, o me golpeaba cada vez, generalmente con tácticas bastante sorprendentes.