Programación dinámica para jugar 21 - Parte I
Ivan Moreno, 18 September 2018
Durante la última semana he estado trabajando en encontrar una política que permita jugar al 21. Aunque hasta ahora solo encontré resultados mixtos, cada vez que hago una modificación, el panorama mejora. Pero antes de seguir hablando de lo que falta por hacer, ¿porqué no hablar primero de la programación dinámica y de porqué estamos aprendiendo esto?
Programas que buscan
Existen muchos problemas. Muchos de ellos implican buscar algo: una función, unas reglas, una ruta. Las búsquedas se realizan en entornos de características diversas. En este curso, nos interesa buscar en entornos parcial o totalmente observables, y estocásticos.
El resultado de la búsqueda termina siendo una política: nos dice que acción deberíamos tomar en el estado en el que nos encontramos.
Procesos de decisión de Markov
Para buscar una política para algún problema, primero debemos representarlo. Entonces entran los procesos de decisión de Markov, que son excelentes para entornos estocásticos. Solo ocupamos una condición: que el proceso no tenga memoria. Formalmente, un proceso de decisión de Markov es
\[ (S, A, \rho, r, S_f) \]
Donde \(S\) es un conjunto enumerable de estados, \(A\) es un conjunto de posibles acciones, \(\rho\) es una función de probabilidad de pasar del estado \(s\) al estado \(s’\) a través de la acción \(a\), \(r\) es una función de recompensa al transicionar entre estados, y donde \(S_f\) es un subconjunto de estados que son terminales. También se usa un número \(\gamma\) entre 0 y 1 llamado factor de descuento que indica que tanto peso deben tener las recompensas futuras.
Programación dinámica
Ya tenemos un modelo de representación de nuestro problema, y ahora queremos encontrar una política. Entonces sigue usar a la programación dinámica. Los algoritmos de este campo de las matemáticas nos permiten buscar, en parte iterativa y en parte recursivamente, políticas que optimicen alguna clase de recompensa a través del uso de un proceso de decisión de Markov.
Si quieres saber más sobre programación dinámica o sobre procesos de decisión de Markov, el material recopilado por el profesor Waissman aquí es muy bueno.
Encontrando una política para el 21
Después de todo ese preámbulo, es hora de hablar sobre como resolver el juego del 21 (o Blackjack.) La implementación de todo lo necesario para encontrar esta dichosa política se encuentra en esta libreta de Jupyter. Todos los detalles sobre como funciona se lo dejo a la misma. El proyecto sigue siendo un trabajo en progreso al momento de escribir esta entrada. Dentro de poco deberían quedar mejores resultados.
Si algún enlace esta roto, o hay algún error en la información, o tienes cualquier otro comentario, por favor mándame un mensaje por GitHub o a mi correo electrónico. Ambos enlaces están en la barra lateral.