¿Cuál es el algoritmo del programa de backgammon independiente?
El backgammon es un juego muy querido por el público, tiene reglas simples, muchos cambios y es muy interesante y recreativo. Aquí diseñamos e implementamos un programa de backgammon para el juego hombre-máquina, utilizando el método del árbol de juego y aplicando los principios de poda y árboles máximo-mínimo para buscar y encontrar la mejor posición de movimiento. Presenta la estructura de datos, las reglas de puntuación, los métodos de valoración de victorias y derrotas 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 tablero, la situación actual del tablero se expresa en forma de lista enlazada, con el propósito de permitir al usuario realizar operaciones como arrepentirse del movimiento y retroceder.
CList StepList
La representación de la estructura Paso es:
struct Step
{
int m ; //m, n representa dos valores de coordenadas
int n;
char side; //side representa el lado inferior
}; /p>
Guarde la situación actual del disco en forma de matriz.
El propósito es utilizar al mostrar la situación actual del disco:
char FiveArea[FIVE_MAX_LINE][ FIVE_MAX_LINE];
Entre ellos, FIVE_MAX_LINE representa el número máximo de líneas en el disco.
Al mismo tiempo, debido a la necesidad de considerar la eficiencia del tiempo y el espacio durante el proceso de búsqueda recursiva, solo se encuentran unos pocos discos que son relativamente buenos para la situación actual en lugar de todas las posiciones posibles. aquí la variable CountList se utiliza para representar la colección de todos los nuevos objetos de situación del disco que se pueden seleccionar en la búsqueda actual:
CList CountList
Entre ellos, la clase CBoardSituiton es:
class CBoardSituation
{
CList StepList; //Lista de cada paso
char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]; /p>
struct Step machineStep; //El paso dado por la máquina
double value; //La puntuación obtenida por este estado del disco
}
2. Reglas de puntuación
Para puntuar la importancia de un movimiento, la situación actual del ajedrez debe considerarse desde seis posiciones, a saber: -, ?, /, \, //, \\
De hecho, es necesario considerar la disposición de las piezas formadas por un determinado grupo en estas seis posiciones. La puntuación de la situación actual después de colocar la pieza en un lugar donde aún no hay pieza es principalmente para. Ilustre la importancia de la pieza en este lugar. Se establece una regla simple para expresar la puntuación de la pieza de ajedrez actual que mira hacia el lado de la máquina.
Las reglas básicas son las siguientes:
Para determinar si puede llegar a 5, si es una máquina se le darán 100.000 puntos, si es un humano se le darán 100.000 puntos. recibirás -100,000 puntos
Determina si puede ser Survival 4 o Double Death 4 o Dead 4 Live 3. Si es el lado de la máquina, dará 10,000 puntos. dará -10,000 puntos;
Juzga si se ha convertido en Double Live 3, si es el lado de la máquina, dará 5000 puntos, si es el lado humano, dará -5000 puntos;
Juzga si es vida o muerte 3, vive 3, si es el lado de la máquina dará 1000 puntos, si es el lado humano dará 1000 puntos -1000 puntos
p>Para determinar si puede sobrevivir 4, si es una máquina, dará 500 puntos, si es un humano, dará -500 puntos.
Para determinar si puede; sobrevive 3, si es el lado de la máquina, se le darán 200 puntos, si es el lado humano, se le dará -200 puntos
Para determinar si se ha vuelto activo-activo 2, si es el lado de la máquina, se le darán 100 puntos, si es el lado humano, se le darán - 100 puntos.
Para determinar si puede ser un 3 de vida o muerte, si; es una máquina, se le darán 50 puntos, si es un humano, se le darán -50 puntos.
Para determinar si puede ser un 2 de vida y muerte, si es así; del lado de la máquina, se le darán 10 puntos, si es el lado humano, se le dará -10 puntos
Juzga si puede sobrevivir a 2, si es del lado de la máquina, se le dará; dados 5 puntos, si es el lado humano, se le darán -5 puntos.
Para determinar si puede sobrevivir o morir, se le darán 3 puntos si es una máquina, y -3 puntos; se dará si es un humano.
De hecho, la situación actual se compara en el orden de las reglas anteriores. Si se cumple una determinada regla, la situación se califica y se guarda, y luego se sale de la coincidencia de reglas. Tenga en cuenta que las reglas aquí son un resumen basado en las reglas generales del juego de ajedrez. Durante la operación real, los usuarios pueden agregar reglas y modificar el mecanismo de puntuación.
3. Juicio del resultado
De hecho, el resultado se determina en función de la situación del último movimiento. De hecho, es necesario juzgar desde cuatro posiciones, la horizontal, la vertical y dos líneas con un ángulo de 45 grados y un ángulo de 135 grados respectivamente, con la piedra como punto de partida. El propósito es ver si es el último lugar. de la piedra en estas cuatro direcciones constituye cinco líneas consecutivas de ajedrez, si es así, significa que la partida ha sido ganada o perdida. Consulte el siguiente diagrama para obtener más detalles:
4. Descripción de la implementación del algoritmo de búsqueda
Tenga en cuenta que la variable currentBoardSituation en el algoritmo principal a continuación representa la última situación del disco de la máquina actual, y CountList representa la última situación del disco. el primero Una colección de mejores discos entre los que los subnodos de capa pueden elegir. El algoritmo principal es el siguiente:
void MainDealFunction()
{
value=-MAXINT //Asignar valor al nodo raíz inicial
CalSeveralGoodPlace(currentBoardSituation, CountList);
// Esta función es comparar en función de la situación actual del tablero para obtener varias situaciones mejores del tablero que se pueden considerar. La comparación de puntajes se puede seleccionar en función de. situación de puntuación real Los discos más altos, es decir, el algoritmo codicioso se utiliza al seleccionar los nodos de primer nivel para encontrar directamente los que tienen puntuaciones relativamente altas para formar los nodos de primer nivel. y evitar el desbordamiento de la pila.
pos=CountList.GetHeadPosition();
CBoardSituation* pBoard;
for(i=0;ivalue=Buscar(pBoard, min, valor, 0 );
Value=Select(value, pBoard-gt; value, max);
// Tome el valor mayor y el valor de pBoard-gt y asígnelo al nodo raíz.
p>}
for(i=0;ivalue)
//Encuentra el tablero con la puntuación más alta
{
currentBoardSituation=pBoard;
PlayerMode=min; //El tablero actual se cambia a humano
Break
}
}
La función de búsqueda se expresa de la siguiente manera: De hecho, el algoritmo central es un proceso de poda, en el que los cuatro parámetros relevantes en este proceso de búsqueda son: (1) El juego de ajedrez actual situación; (2) El movimiento actual puede ser una máquina (max) o una persona (min) (3) El valor del nodo padre oldValue (4) La profundidad de búsqueda actual
doble; Buscar (CBoardSituation&
tablero, modo int, doble valor antiguo, profundidad int)
{
CList m_DeepList
if(profundidadvalorantiguo) )== VERDADERO)
{
if(modo==max)
valor=select(valor, buscar(sucesor
Tablero, min, valor, profundidad+1), max);
else
amp nb
sp;
Tablero, máximo, valor, profundidad+1), mín
}
valor de retorno
}
else
{
if ( objetivo(tablero)lt; gt; 0)
//Aquí objetivo(tablero)lt; 0 significa que se puede determinar el ganador
return goal(board);
else
return evlation(board);
}
p>
Tenga en cuenta que la función objetivo (tablero) aquí se utiliza para determinar si el tablero actual se puede dividir en ganadores y perdedores, mientras que evlation(board) Se utiliza para puntuar 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 apropiado del nodo según la situación del PlayerMode, es decir, si es la máquina o el usuario.
doble selección(doble a, doble b, modo int)
{
if(agt; b && mode==max)? && mode==min)
regresar a
else
regresar b
}
cinco; , Resumen
Bajo el sistema operativo Windows, este programa de backgammon hombre-máquina se implementó utilizando VC++. En comparación con muchos programas nacionales que solo usan reglas o recursividad simple sin poda, es mejor que 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 ajedrez y Go, etc.).