Muy buenas, les saluda Miguel y para hoy les traigo este artículo.
… Y terminar de implementar el algoritmo minimax
En este artículo, terminaremos de implementar el algoritmo minimax para jugar el juego 2048, y luego usaremos esta implementación para jugar automáticamente una versión web de este juego que se puede encontrar en esta página de Github.
Para eso, primero crearemos el GameDriver
class que actuará como intermediario entre nuestra implementación de minimax y el juego que se encuentra en esta página web. los GameDriver
la clase es responsable de interactuar con el juego. Necesitaremos 2 operaciones para manejar: obtener datos sobre el estado actual del juego y realizar uno de los movimientos: arriba, abajo, izquierda, derecha. Estas 2 operaciones se implementan en los siguientes métodos:
.getGrid()
– esto obtendrá los datos del estado del juego y los devolverá como unGrid
objeto..move()
– esto tomará como parámetro un código de dirección de movimiento y emulará una pulsación de la tecla de flecha correspondiente.
Los códigos de dirección de movimiento que elegimos en nuestra implementación son:
- 0 = Arriba
- 1 = Abajo
- 2 = Izquierda
- 3 = Derecha
Para la implementación de este GameDriver
class, usaremos Selenium, que es una buena biblioteca para hacer este tipo de cosas: interactuar con un navegador web.
Ahora, comenzamos con la importación de algunas cosas. De la biblioteca de Selenium, necesitamos webdriver y Keys, que se utilizarán para crear una instancia de controlador para su navegador web deseado, respectivamente, para usar las teclas de flecha. También importamos el tamaño máximo de un tipo int como MAX_INT
y el time
paquete; veremos después de un tiempo para qué los necesitamos.
from selenium import webdriver from selenium.webdriver.common.keys import Keysfrom sys import maxsize as MAX_INT import time
A continuación, creamos el método de instanciación para el GameDriver
clase. Almacenamos la URL de la página del juego, creamos una instancia del controlador de Chrome y abrimos la URL del juego. Luego, necesitamos almacenar una referencia al elemento del cuerpo de la página para poder enviar los comandos de las teclas de flecha más tarde. También almacenamos un diccionario que asigna los códigos de dirección de movimiento a las teclas de flecha correspondientes.
def __init__(self): self.url = 'https://hczhcz.github.io/2048/20ez/' self.driver = webdriver.Chrome() self.driver.get(self.url) self.body = self.driver.find_element_by_tag_name('body') self.moves = { 0: Keys.ARROW_UP, 1: Keys.ARROW_DOWN, 2: Keys.ARROW_LEFT, 3: Keys.ARROW_RIGHT }
El método .getGrid()
extrae datos sobre el estado del juego y devuelve un Grid
objeto. Almacenamos los datos como una matriz y los pasamos a Grid
‘s constructor al regresar. En primer lugar, la matriz se inicializa con ceros y luego la actualizamos a medida que encontramos los mosaicos en la página.
Después de inspeccionar un poco la página del juego en Chrome Developer Tools (CTRL + SHIFT + I), llegué a la conclusión de que:
- Los mosaicos se pueden identificar por el nombre de clase «mosaico».
- La posición (número de fila y columna) de cada mosaico en la cuadrícula se puede extraer de un nombre de clase de la forma «mosaico-posición-columna–fila”Que se encuentra en el atributo de clase de cada mosaico.
- El número de mosaico es el valor máximo que se puede extraer de un nombre de clase de la forma «mosaico-num”Que se encuentra en el atributo de clase de cada mosaico.
A continuación se muestra el código que implementa las ideas anteriores:
def getGrid(self) -> Grid: matrix = [[0 for i in range(4)] for j in range(4)] tiles = self.driver.find_elements_by_class_name('tile') for tile in tiles: cls = tile.get_attribute('class') col, row = cls.split('tile-position-')[1].split(' ')[0].split('-') col, row = int(col)-1, int(row)-1 num = int(cls.split('tile tile-')[1].split(' ')[0]) if num > matrix[row][col]: matrix[row][col] = num return Grid(matrix)
El método .move()
siguiente envía la señal de la tecla de flecha apropiada al elemento del cuerpo para que se realice un movimiento en la dirección indicada por el parámetro que toma. Entonces, usamos time.sleep(0.1)
hacer una pausa de 0,1 segundos después de que se envía la señal de movimiento para que la página tenga tiempo de actualizarse.
def move(self, moveCode): self.body.send_keys(self.moves[moveCode]) time.sleep(0.1)
A continuación se muestra el código completo del GameDriver
clase:
from selenium import webdriver from selenium.webdriver.common.keys import Keys from sys import maxsize as MAX_INT import time class GameDriver: def __init__(self): self.url = 'https://hczhcz.github.io/2048/20ez/' self.driver = webdriver.Chrome() self.driver.get(self.url) self.body = self.driver.find_element_by_tag_name('body') self.moves = { 0: Keys.ARROW_UP, 1: Keys.ARROW_DOWN, 2: Keys.ARROW_LEFT, 3: Keys.ARROW_RIGHT } def getGrid(self) -> Grid: matrix = [[0 for i in range(4)] for j in range(4)] tiles = self.driver.find_elements_by_class_name('tile') for tile in tiles: cls = tile.get_attribute('class') col, row = cls.split('tile-position-')[1].split(' ')[0].split('-') col, row = int(col)-1, int(row)-1 num = int(cls.split('tile tile-')[1].split(' ')[0]) if num > matrix[row][col]: matrix[row][col] = num return Grid(matrix) def move(self, moveCode): self.body.send_keys(self.moves[moveCode]) time.sleep(0.1)
Ahora es el momento de implementar el algoritmo minimax que consta de 3 funciones: maximize()
, minimize()
y getBestMove()
. Si no está familiarizado con el algoritmo minimax, puede consultar este artículo para asegurarse de que comprende lo que está sucediendo aquí.
La maximize()
función toma como parámetros: state
que es un objeto Grid, a
y b
que son el alfa y el beta de la poda α-β, y d
es la profundidad máxima permitida. Esta función devuelve una tupla de la forma (maxChild, maxUtility)
, dónde maxChild
son los hijos del objeto de estado actual (en el árbol del algoritmo minimax) que maximiza la utilidad, y maxUtility
es el valor de utilidad de maxChild
estado del juego.
maxUtility
La variable tendrá la máxima utilidad de un nodo encontrado hasta ahora. Al comienzo de la función, no conocemos ningún valor de utilidad, por lo que consideramos que el máximo hasta ahora es un número menor que cualquier valor que pueda tener un valor de utilidad. Elegí -1.
Luego, comprobamos si el estado actual es un nodo terminal o si alcanzamos la profundidad máxima. Si es así, devolvemos None como el maxChild
y evaluar la utilidad del estado actual; de lo contrario, continuaremos iterando sobre todos los hijos del estado actual. En cada iteración hacemos una copia del estado actual del juego y hacemos un movimiento en uno de los movimientos disponibles; los child
La variable en el bucle for es un código de dirección de movimiento que se utiliza para realizar este movimiento.
Después dejamos que Min haga su movimiento a través del minimize()
función y recuperar de esta función la utilidad del estado hijo de la iteración actual. Esta es la utilidad que obtendríamos si decidiéramos hacer el movimiento que lleva al hijo actual en el ciclo. Si esta utilidad es mayor que nuestra anterior maxUtility
, luego actualizamos el maxChild
y maxUtility
en consecuencia. Después de esto, hacemos 2 verificaciones más de acuerdo con el algoritmo de poda α-β, de modo que saltemos rutas en el árbol del juego que sabemos de antemano que no nos darán la mejor jugada.
La función minimize()
es similar a maximize()
pero ahora estamos en la piel del jugador Min e intentamos elegir el movimiento que minimice la utilidad.
La getBestMove()
llamadas a funciones maximize()
y devuelve el código de la jugada que tenemos que realizar para maximizar nuestra puntuación / utilidad.
A continuación se muestra el código de nuestra implementación minimax:
def maximize(state: Grid, a: int, b: int, d: int) -> Tuple[Grid, int]: (maxChild, maxUtility) = (None, -1) if d == 0 or state.isTerminal(who="max"): return (None, state.utility()) d -= 1 for child in state.getChildren(who = "max"): grid = Grid(matrix=state.getMatrix()) grid.move(child) (_, utility) = minimize(grid, a, b, d) if utility > maxUtility: (maxChild, maxUtility) = (grid, utility) if maxUtility >= b: break if maxUtility > a: a = maxUtility return (maxChild, maxUtility) def minimize(state: Grid, a: int, b: int, d: int) -> Tuple[Grid, int]: (minChild, minUtility) = (None, MAX_INT) if d == 0 or state.isTerminal(who="min"): return (None, state.utility()) d -= 1 for child in state.getChildren(who = "min"): grid = Grid(matrix=state.getMatrix()) grid.placeTile(child[0], child[1], child[2]) (_, utility) = maximize(grid, a, b, d) if utility < minUtility: (minChild, minUtility) = (grid, utility) if minUtility <= a: break if minUtility < b: b = minUtility return (minChild, minUtility) def getBestMove(grid: Grid, depth: int = 5): (child, _) = maximize(Grid(matrix=grid.getMatrix()), -1, MAX_INT, depth) return grid.getMoveTo(child)
Ahora es el momento de crear el ciclo de juego en el que repetimos, hasta que el juego termina, las siguientes 3 cosas: obtener los datos del juego, usar minimax para establecer cuál es la mejor jugada y, de hecho, hacer esta jugada.
gameDriver = GameDriver() moves_str = ['UP', 'DOWN', 'LEFT', 'RIGHT'] moves_count = 1 while True: grid = gameDriver.getGrid() if grid.isGameOver(): print("Unfortunately, I lost the game.") break moveCode = getBestMove(grid, 5) print(f'Move #{moves_count}: {moves_str[moveCode]}') gameDriver.move(moveCode) moves_count += 1
Cuando ejecutamos este bucle de juego, deberíamos tener en nuestras pantallas un juego 2048
Puedes encontrar el código completo de este proyecto en Github.
Espero que este artículo te haya resultado interesante y gracias por leerlo
Añadir comentario