Problema de implementación de backgammon JAVA (trabajo duro)
El algoritmo específico también está disponible online:
Backgammon es un juego muy querido por el público. Sus reglas son simples y diversas, lo que lo hace muy interesante y entretenido. Este artículo diseña e implementa un programa de backgammon para emparejamiento humano-máquina, utilizando el método del árbol de juego, aplicando los principios de poda y árbol máximo-mínimo para buscar la mejor posición para el siguiente jugador. Se presentan la estructura de datos, las reglas de puntuación, el método de determinación de victoria o derrota y el proceso del algoritmo de búsqueda del programa de backgammon.
1. Estructuras de datos relacionadas
En cuanto a la representación de la situación del disco, la situación actual del disco se expresa en forma de una lista vinculada, con el propósito de permitir al usuario arrepentirse. , retirada y otras operaciones.
CLista de pasos;
La estructura de la escalera se expresa como:
Pasos estructurales
{
int m; //m, n representa dos valores de coordenadas.
int n;
char side; //side representa el siguiente nodo secundario.
};
Guarde el disco actual en forma de matriz.
El propósito es utilizar:
char CINCO área [FIVE_MAX_LINE][FIVE_MAX_LINE];
Donde FIVE_MAX_LINE representa el número máximo de líneas en la superficie del disco.
Al mismo tiempo, debido a la necesidad de considerar la efectividad del tiempo y el espacio durante el proceso de búsqueda recursiva, solo se encuentran unos pocos discos que son relativamente buenos en la situación actual en lugar de buscar todas las ubicaciones descargables. . Aquí, la variable CountList se utiliza para representar la colección de todos los nuevos objetos de estado del disco que se pueden seleccionar en la búsqueda actual:
CList CountList
La clase CBoardSituiton es:
CBoardSituation Class
{
CList lista de pasos; //Lista de cada paso
char FIVE area[FIVE _ MAX _ LINE][FIVE _ MAX _ LINE] ];
Estructura paso machineStep//El siguiente paso de la máquina
Valor doble //La puntuación obtenida por el estado de este disco
}
2. Reglas de puntuación
Para la puntuación de importancia de Xia Zi, debemos considerar el juego de ajedrez actual desde seis posiciones, a saber: -,? ,/,\,//,\\
De hecho, debemos considerar la disposición de las piezas de ajedrez formadas por una parte en estas seis posiciones. Con respecto a la puntuación de la situación actual después de que no se coloca la pieza de ajedrez, principalmente para ilustrar la importancia de la pieza de ajedrez allí, se establece una regla simple para indicar la puntuación de la superficie de ajedrez actual a la máquina.
Las reglas básicas son las siguientes:
Juzga si puedes hacer 5. Si es una máquina, dale 100.000 puntos; si es un humano, dale -100.000 puntos;
Juzga si puedes vivir 4, morir 4, morir 4, vivir 3. Si es una máquina, dará 10.000 puntos. Si es un humano, dará -10.000 puntos.
Para determinar si se ha convertido en un trabajo dual 3, si es una máquina, dará 5.000 puntos, si es un humano, dará -5000 puntos;
Para juzgar. si está vivo o muerto, si es una máquina, otorga 1000 puntos, si es un humano, otorga -1000 puntos;
Para juzgar si está vivo o muerto, no puedo tener éxito. 4. Si es una máquina dará 500 puntos, si es un humano dará -500 puntos.
Para determinar si una persona puede trabajar sola 3, si es una máquina se le darán 200 puntos, si es un humano serán -200 puntos, si es un; lado humano, se otorgarán -100 puntos;
Juzga si puede tener éxito. 3. Si es una máquina dará 50 puntos, si es un humano dará -50 puntos.
Juzga si puede funcionar en parejas 2. Si es una máquina, dale 10 puntos, si es un humano, dale -10 puntos
Juzga si puede sobrevivir 2; , si es una máquina, otorga 5 puntos, si es un humano, otorga -5 puntos;
Determina si puede tener éxito. 2. Si es el lado máquina dará 3 puntos, si es el lado humano dará -3 puntos.
De hecho, la situación actual se compara en el orden de las reglas anteriores. Si se cumple una regla, la situación se califica y se guarda, luego se cierra la coincidencia de reglas. Tenga en cuenta que las reglas aquí son un resumen de las reglas generales para jugar al ajedrez. En funcionamiento real, los usuarios pueden agregar reglas y modificar el mecanismo de puntuación.
En tercer lugar, el juicio de victoria o derrota
De hecho, la victoria o derrota se juzga en función de la situación actual del último jugador. De hecho, es necesario juzgar desde cuatro posiciones, la línea horizontal, la línea vertical y las dos líneas con un ángulo de 45 grados y un ángulo de 135 grados respectivamente, para ver si el último jugador en estas cuatro direcciones constituye cinco jugadores consecutivos. piezas de ajedrez. Si es así, significa que el juego ha sido ganado. Consulte la figura siguiente para obtener más detalles:
Cuarto, describa la implementación del algoritmo de búsqueda
Preste atención a la variable currentBoardSituation en el algoritmo central a continuación, que representa la última situación del disco del máquina actual, y CountList representa el hijo de primer nivel. Una colección de mejores discos entre los que el nodo puede elegir. El algoritmo principal es el siguiente:
void MainDealFunction()
{
valor =-MAXINT //Asigna el valor al nodo raíz inicial
; p>
CalSeveralGoodPlace(currentBoardSituation, count list);
//Esta función compara varios discos que se pueden considerar según la situación actual del disco y selecciona los discos con puntuaciones más altas según la puntuación real. , es decir, se dice que al seleccionar nodos de primer nivel, se utiliza un algoritmo codicioso para encontrar directamente los nodos de primer nivel con puntuaciones relativamente altas para mejorar la velocidad de búsqueda y evitar el desbordamiento de la pila.
pos=CountList. getheadsposition();
CBoardSituation * pBoard
for(I = 0; ivalue=Buscar(pBoard, min, value, 0);
Valor=Seleccionar (valor, pBoard->; valor, max);
//Obtener el valor y asignar el pboard->valor máximo al nodo raíz
}
<. p> for(I = 0; ivalue)//Descubre qué disco tiene la puntuación más alta
{
currentBoardSituation = pBoard
PlayerMode. = min//El subgrupo actual se cambia a un individuo
Break
}
}
Tablero, modo int. doble valor antiguo, profundidad int)
{
CList m _ DeepList
if(profundidadvalorantiguo))== TRUE)
{
if(modo==valor máximo)
Valor = seleccionar(valor, buscar(sigue
Tablero, min, valor, profundidad+1), max );
Otro
Valor = Seleccionar(valor, buscar(sigue
Tablero, máx, valor, profundidad+1), min);
}
Valor de retorno;
}
Otros
{
if(objetivo( board)& lt;& gt0)
//aquí Target (board) < & gt0 significa que se puede decidir el ganador.
Objetivo de retorno (tablero);
Otro
Traducción de retorno (tablero);
}
}
Tenga en cuenta que la función goal(board) aquí se utiliza para determinar si se gana o pierde el tablero actual, mientras que evlation(board) puntúa el tablero actual desde la perspectiva de la máquina.
La siguiente es una introducción a la función Seleccionar. El objetivo principal de esta función es devolver el valor correcto del nodo, es decir, máquina o usuario, según el PlayerMode.
Doble selección (doble a, doble b, modo int)
{
If (a & gtb & & mode = = max)(a & lt ;b && mode==min)
Devolver a;
Otro
Devolver b;
}
Resumen de verbo (abreviatura de verbo)
Bajo el sistema operativo Windows, este programa de backgammon hombre-máquina se implementa utilizando VC++. En comparación con muchos programas nacionales que solo usan reglas o recursividad simple sin poda, es superior a estos programas en términos de inteligencia y eficiencia de tiempo. Al mismo tiempo, los métodos y procesos de diseño discutidos proporcionan una referencia para que los usuarios diseñen otros juegos como el ajedrez y el Go.
Te lo envié.