-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathminimax-multiplayer-v2.lisp
129 lines (98 loc) · 6.47 KB
/
minimax-multiplayer-v2.lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
;Algorimo de decision minimax extendido para aplicarlo a multiples jugadores. Renombrado como decision-maxn.
;Para hacer uso del algoritmo se supone que ha sido cargada, previamente, la implementacion de la especificacin del juego sobre
; el que se va aplicar el algoritmo. En toda especificacion de cualquier juego se representara cada jugador por un numero, de manera que,
; sea mas sencillo identificarlo y obtener su puntuacion correspondiente en el vector de puntuciones devuelto por la funcion de evaluacion estatica.
;
; Dicha implementación debe incluir las siguientes variables globales:
; - *minimo-valor*
; - *maximo-valor*
; - *maxima-suma*
; + movimientos (estado turno)
; + es-estado-final(estado)
; + evaluacion-estatica(estado turno)
; + construye-nodo(estado turno)
; + estado(nodo)
; + turno(nodo)
;ESTE CODIGO CORRESPONDE A LA VERSION 2 DE MINIMAX-MULTIPLAYER, A LA QUE SE LE APLICA PODA INMEDIATA Y PODA SUPERFICIAL
;La PODA INMEDIATA consiste en que si un movimiento supone la maxima puntuacion *maximo-valor* para un jugador, entonces,
; no es neceserio evaluar el resto de nodos, pues es imposible que vaya a mejorar dicha puntuacion.
;La PODA SUPERFICIAL sigue la regla (*maxima-suma* - y <= x) siendo 'x' el maximo valor hasta el momento del nodo padre e y el maximo valor
; hasta el momento del nodo hijo correspondiente a ese padre. La variable global *maxima-suma* es el valor maximo que puede alcanzar la suma de
; las puntuaciones de todos los jugadores en un estado concreto del juego.
;
;El objetivo de la poda superficial es la comparacion de la puntuacion maxima en ese instante entre el nodo padre (jugador que mueve antes) y
; el nodo hijo (jugador que mueve a continuacion) de manera que, si se cumple la regla anterior, el jugador correspondiente al nodo padre no va
; a escoger el movimiento hacia ese nodo hijo luego no tiene sentido seguir evaluando nodos sucesores de ese hijo.
;
;Ademas, la poda superficial depende del tipo de puntuaciones que tenga el juego. Segun lo expuesto en el recurso R4, si en el juego no se cumple
; la desigualdad (maxima-suma < 2 * maximo-valor) no se lleva a cabo la poda superficial y solo podría hacer por tanto, poda inmediata. Esto se debe
; a la dependencia entre las puntuaciones entre jugadores. Es decir, en un juego en el que los puntos que consigue el jugador son puntos que pierden
; los otros jugadores, existe una relacion que cumple la condicion anterior. Mientras que en juego en los que los puntos que consigue un jugador no
; suponen puntos perdidos para otros, no existe una dependencia entre puntuaciones de los jugadores y por tanto no se cumple la condicion mencionada.
;
;Por otro lado, la poda inmediata se trata de un caso particular de la poda superficial, por lo que la implementacion de la poda superficial
; incluye la posibilidad de poda inmediata en su caso. Esto es asi porque, en el caso de que el valor del nodo hijo consiga la maxima puntuacion,
; el resto de nodos seran podados como si de una poda inmediata se tratara, pues siempre se cumplira la condicion de la poda superficial.
;
;R4. Sturtevant, N., Korf, R.: On Pruning Techniques for Multi-Player Games. In: AAAI 2000, pp. 201-207 (2000).
(defun decision-maxn (actual)
"devuelve el nodo sucesor correspondiente al movimiento mejor valorado para el jugador que lo invoca"
(let ((max-val *minimo-valor*)
(jugador (turno actual))
(max-nodo nil))
(loop for nodo in (sucesores actual)
do (let ((puntuacion (valor-maxn nodo max-val)))
(if (>= (puntuacion-jugador puntuacion jugador) max-val)
(progn (setf max-val (puntuacion-jugador puntuacion jugador))
(setf max-nodo nodo))))
if (= max-val *maximo-valor*) do (loop-finish)) ;Poda inmediata.
;En este punto solo tiene sentido la poda inmediata pues el nodo actual no tiene antecesor.
max-nodo)
)
(defun valor-maxn (nodo cota-puntos) ;cota-puntos indica la puntuacion maxima, en ese momento,
; para el padre del nodo pasado como parametro,
; posibilitando la poda superficial en su caso.
"devuelve la puntuacion del nodo sucesor mejor valorado para el jugador del nodo actual"
(if (or (es-estado-final (estado nodo)) (not (sucesores nodo)))
(evaluacion-estatica (estado nodo) (turno nodo))
(maximiza-puntuacion (sucesores nodo) (turno nodo) cota-puntos))
)
(defun maximiza-puntuacion (sucesores jugador cota-puntos)
"devuelve la puntuacion maxima de entre las puntuaciones de los nodos sucesores, para el jugador pasado como parametro"
(let ((max-val *minimo-valor*)
(max-puntuacion nil))
(loop for nodo in sucesores
do (let ((puntuacion (valor-maxn nodo max-val)))
(if (>= (puntuacion-jugador puntuacion jugador) max-val)
(progn (setf max-val (puntuacion-jugador puntuacion jugador))
(setf max-puntuacion puntuacion))))
if (<= (- *maxima-suma* max-val) cota-puntos) do (loop-finish)) ;Poda superficial (incluye poda inmediata en su caso)
max-puntuacion)
)
(defun sucesores (nodo)
"obtiene la lista de sucesores del nodo dado, a partir de los posibles movimientos del jugador al que le toca mover"
(loop for movimiento in (movimientos (estado nodo) (turno nodo))
if (not (equal (sucesor nodo movimiento) 'no-aplicable))
collect (sucesor nodo movimiento) into lista-sucesores
;Si no puede aplicar ningun movimiento y el estado no es final debe pasar el turno, por tanto el sucesor es el mismo estado actual.
finally (if (and (eq lista-sucesores nil) (not (es-estado-final (estado nodo))))
(return (list (construye-nodo (estado nodo) (siguiente-turno (turno nodo)))))
(return lista-sucesores)))
)
(defun sucesor (nodo movimiento)
"obtiene el sucesor de un estado para un nodo y un movimiento del juego dado"
(let ((estado-sucesor (aplica-movimiento movimiento (estado nodo))))
(if (equal estado-sucesor 'no-aplicable)
'no-aplicable
(construye-nodo estado-sucesor (siguiente-turno (turno nodo)))))
)
;Funciones auxiliares
(defun puntuacion-jugador (puntuacion jugador)
"a partir del vector de puntuacion, que contiene un valor por cada puntuacion de cada jugador,
devuelve la puntuacion correspondiente al jugador especificado"
(nth (1- jugador) puntuacion)
)
(defun siguiente-turno (turno-actual)
"devuelve el identificador del jugador al que le toca mover en el siguiente turno"
(if (eq turno-actual *numero-jugadores*) 1 (1+ turno-actual))
)