Antecedentes
En la implementación anterior del tres en raya teníamos una clase abstracta denominada TTTGamePlayer de la cual heredaban las clases TTTHumanGamePlayer y TTTRandomGamePlayer. TTTHumanGamePlayer además de heredar de TTTGamePlayer, también heredaba de KeyMatrixListener, de esta forma los eventos de los pulsadores se transforman en movimientos del jugador humano.
La clase TTTRandomGamePlayer era una clase que inicializaba una semilla aleatoria. Dentro de esta clase el método getSpot(), que es el método virtual puro de TTTGamePlayer que debe devolver el movimiento que desea realizar el jugador, devolvía en este caso una posición aleatoria de entre todas las posiciones libres que quedaban en el tablero.
Algoritmo Minimax
El algoritmo minimax es un algoritmo de decisión muy simple desarrollado a partir del Teorema Minimax de John von Neumann en 1926 (para juegos de suma cero e información perfecta). El algoritmo es muy sencillo:
- Cuando nos toque mover a nosotros, calculamos el árbol de decisión del juego.
- Los nodos hoja del árbol representarán todas las posibles formas de terminar el juego. Asignamos a cada uno de los nodos hoja del árbol un valor numérico directamente proporcional a nuestro beneficio (o inversamente proporcional al beneficio de nuestro oponente).
- Vamos ascendiendo en el árbol escogiendo, alternativamente, el mínimo o el máximo de los hijos (minimax) en función de si cada decisión debe ser tomada por mí o por mi oponente (yo busco maximizar mi beneficio y mi oponente busca minimizarlo o, lo que es lo mismo, maximizar el suyo propio), así hasta la raíz. De esta forma podemos elegir el movimiento que minimize nuestra pérdida esperada.
Con un ejemplo del 3 en raya se ve mejor. Imaginemos que somos X y que nos toca mover a nosotros:
o x x
x . . sig. mov. = x, beneficio = max(-1, -1, 0) = 0
o o .
o x x
x x . sig. mov. = o, beneficio = min(0, -1) = -1
o o .
o x x
x x o sig. mov. = x, beneficio = max(0) = 0
o o .
o x x
x x o tablas, beneficio = 0
o o x
o x x
x x . gana o, beneficio = -1
o o o
o x x
x . x sig. mov. = o, beneficio = min(1, -1) = -1
o o .
o x x
x o x sig. mov. = x, beneficio = max(1) = 1
o o .
o x x
x o x gana x, beneficio = 1
o o x
o x x
x . x gana o, beneficio = -1
o o o
o x x
x . . sig. mov = o, beneficio = min(1, 0) = 0
o o x
o x x
x o . sig. mov. = x, beneficio = max(1) = 1
o o x
o x x
x o x gana x, beneficio = 1
o o x
o x x
x . o sig. mov. = x, beneficio = max(0) = 0
o o x
o x x
x x o tablas, beneficio = 0
o o x
A partir del nodo raíz, el beneficio máximo se corresponde con el movimiento:
o x x o x x
x . . ---> x . .
o o . o o x
En este caso “beneficio” se refiere a “beneficio para X”. Como se puede ver, partiendo del estado del tablero indicado por la raíz del árbol, el mejor movimiento será el de marcar la fila 3 y la columna 3.
Hardware
El montaje lo he realizado utilizando un Arduino Leonardo, conectando la matriz de pulsadores a los puertos A0, A1, A2, D11, D12 y D13
Y la matriz de leds a los puertos D0, D1, D2, D3, D4 y D5
Si vamos a realizar el montaje para otro modelo de Arduino hay que comprobar el mapeo de los puertos en el microcontrolador y modificar la implementación de las clases MyLedMatrixManager y MyKeyMatrixManager (como se trata de una implementación en C++, no tenemos a nuestra disposición la abstracción de puertos que nos proporciona el lenguaje Arduino).
Implementación
La clase TTTMinimaxGamePlayer es la que implementa el algoritmo minimax: Al igual que las clases TTTRandomGamePlayer y TTTHumanGamePlayer, hereda de TTTGamePlayer con la diferencia de que en su método getSpot() calcula el siguiente movimiento a realizar utilizando el algoritmo de decisión minimax.
uint8_t TTTMinimaxGamePlayer::getSpot() { uint8_t ret = 0; this->minimax(*this->board, true, ret); return ret; } int8_t TTTMinimaxGamePlayer::minimax(TTTGameBoard &board, bool me, uint8_t &bestMovement) { uint8_t winner = board.getWinner(); if (board.isFinished() || (winner != 0)) { int8_t ret = 0; if (winner == this->number) ret = 1; else if (winner == this->opponentNumber) ret = -1; return ret; } else { int8_t limit = 0; if (me) limit = -10; else limit = 10; TTTGameBoard auxBoard; uint8_t numMovements = 0; for (uint8_t m = board.getFirstAvailableMovement(); m != 0; m = board.getNextAvailableMovement(), numMovements++) { auxBoard.copyFrom(board); if (me) auxBoard.set(m, this->number); else auxBoard.set(m, this->opponentNumber); uint8_t childBestMovement; int8_t v = minimax(auxBoard, !me, childBestMovement); if (me) { if (v > limit) { limit = v; bestMovement = m; } } else { if (v < limit) { limit = v; bestMovement = m; } } } return limit; } }
Se trata de una implementación recursiva y el parametro “me” indica cuando se está simulando un movimiento propio (true) o un movimiento del oponente (false). A pesar de usarse una implementación recursiva, nótese que no se realizarán más de 8 llamadas recursivas: Cada nivel es un movimiento adicional y un tablero de 3 en raya sólo tiene 9 posiciones.
A modo de visión global, el diagrama de clases queda ahora así:
En la sección soft puede descargarse el código fuente del proyecto en C++. Aquí una pequeña guía sobre cómo desarrollar en C++ para el Arduino.
[ añadir comentario ] ( 2766 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 2171 )
Calendario
