El programa era mas fácil de lo que lo había hecho antes. Me complique demasiado, en realidad había que dividir el tablero en lineas, y el ordenador debería buscar las lineas que van cumpliendo con el objetivo, e ir completándolas. Hay ocho lineas posibles, 3 verticales, 3 horizontales y las dos diagonales. El orden de la búsqueda de la posición en blanco para cada linea puede ser al azar. También debe impedir que el humano complete sus lineas. Las versiones anteriores consultaban todas las posibilidades con el tablero completo de nueve entradas. La versión 4 era mas de lo mismo, por eso ni me moleste en publicarla. El problema con las versiones anteriores era que consumían demasiados recursos, para 3 entradas, por ejemplo, un barrido costaría solo unos pocos segundos, pero con nueve el tiempo de computo aumenta exponencialmente. La solución para un problema complejo es dividirlo en pequeñas partes e ir resolviéndolo, es decir generalizar. Aquí tendré en cuenta solo lineas de tres entradas, para ir luego tomándolas del tablero de nueve y seleccionar que linea conviene modificar. Una vez modificada una línea, se averigua su posición en el tablero. Para eso se usan listas con claves, que son las lineas-n. Cada linea-n de esta lista tiene dos claves :lin y :pos. :lin me da la linea del tablero, por ejemplo (N X O) y pos me dice cual linea es dentro del *tablero*.
Las posiciones del *tablero* son:
0 1 2 ----> :pos 0
3 4 5 ----> :pos 1
6 7 8 ----> :pos 2
Las primeras tres horizontales desde arriba hacia abajo son las lineas-n con :pos 0,1 y 2; las que siguen son las verticales desde izquierda a derecha, que son las lineas cuya :pos son 3,4 y 5. Restan las diagonales. Entonces la primera diagonal formada por las posiciones 0,4,8 es la linea-n con :pos 6. Por último nos queda, la diagonal formada por las posiciones 2,4,6 es la linea-n con :pos 7.
Con la linea modificada y la posición, basta copiar este valor en las posiciones del tablero.
Visto de esta manera, el tiempo de computo tiende a cero :-D
Todavía hay que probar que no pierda el juego, y ver si se puede arreglar eso, es decir, probar el modo de jugar del programa.
Bueno aquí dejo el programa tal como quedó actualmente:
(setf *tablero* '(n n n n n n n n n))
;--------------------------------------------------------------------------------
;Para una linea
(defun agrega-x (linea pos)
;Devuelve una linea con la 'x colocada
(setf (nth pos linea) 'x)
linea)
(defun busca-n (linea)
;Devuelve la posicion de un espacio en blanco para una linea
(setf pos nil)
(setf ordenamientos '((0 1 2) (0 2 1)
(1 0 2) (1 2 0)
(2 0 1) (2 1 0)))
(setf orden (nth (random 6) ordenamientos))
(if (equal (nth (first orden) linea) 'n)
(setf pos (first orden))
(if (equal (nth (second orden) linea) 'n)
(setf pos (second orden))
(if (equal (nth (third orden) linea) 'n)
(setf pos (third orden)))))
pos)
;---------------------------------------------------------------------------
; Obtener las lineas del tablero
(defun obtener(tablero)
;Obtiene las ocho lineas posibles 0 1 2
;linea 0 1 2 son horizontales 3 4 5
;lineas 3 4 5 verticales 6 7 8
;linea 6 diagonal \
;linea 7 diagonal /
(setf linea-0 (list :lin (list (nth 0 tablero) (nth 1 tablero) (nth 2 tablero)) :pos 0))
(setf linea-1 (list :lin (list (nth 3 tablero) (nth 4 tablero) (nth 5 tablero)) :pos 1))
(setf linea-2 (list :lin (list (nth 6 tablero) (nth 7 tablero) (nth 8 tablero)) :pos 2))
(setf linea-3 (list :lin (list (nth 0 tablero) (nth 3 tablero) (nth 6 tablero)) :pos 3))
(setf linea-4 (list :lin (list (nth 1 tablero) (nth 4 tablero) (nth 7 tablero)) :pos 4))
(setf linea-5 (list :lin (list (nth 2 tablero) (nth 5 tablero) (nth 8 tablero)) :pos 5))
(setf linea-6 (list :lin (list (nth 0 tablero) (nth 4 tablero) (nth 8 tablero)) :pos 6))
(setf linea-7 (list :lin (list (nth 2 tablero) (nth 4 tablero) (nth 6 tablero)) :pos 7))
(setf lineas-n (list linea-0 linea-1 linea-2 linea-3 linea-4 linea-5 linea-6 linea-7))
lineas-n)
;----------------------------------------------------------------------------------
;Seleccionar las lineas mas importantes
(defun seleccionar(lineas-n)
(setf seleccion nil)
(setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'x) 2)) lineas-n));obtiene las lineas-n con dos 'x
(if (equal seleccion nil)
(setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'o) 2)) lineas-n));obtiene las lineas-n con dos 'o
(if (equal seleccion nil)
(setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'x) 1)) lineas-n));obtiene las lineas-n con una 'x
(if (equal seleccion nil)
(setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'o) 1)) lineas-n)))));obtiene las lineas-n con una 'o
(if (equal seleccion nil)
(setf seleccion lineas-n)) ;si no encontro nada < 1 no hay jugadas aun, el tablero es todo 'n
seleccion)
(defun cuenta (linea var)
;Cuenta la cantidad de veces que esta una variable ('x o 'o) en la linea
(setf cuenta 0)
(when (equal (nth 0 linea) var) (incf cuenta))
(when (equal (nth 1 linea) var) (incf cuenta))
(when (equal (nth 2 linea) var) (incf cuenta))
cuenta)
(defun quita-completos (lineas-n)
(setf lineas-n (remove-if #'(lambda (linea-n) (= (cuenta (getf linea-n :lin) 'n) 0)) lineas-n));quita las lineas-n si no tienen espacios en blanco
lineas-n)
;---------------------------------------------------------------------------------------------
(defun gana (jugador);jugador es 'x y 'o. Verifica si un jugador gana
(setf lineas-n (obtener *tablero*));las lineas-n tienen claves
(setf respuesta nil)
(when (some #'(lambda (linea-n) (= (cuenta (getf linea-n :lin) jugador) 3)) lineas-n)
(setf respuesta T))
respuesta)
;;;;--------------------------------------------------------------------------------------------------------------
;;;; Una jugada del ordenador -----------------------------------------------------------------------------------
;;;;--------------------------------------------------------------------------------------------------------------
(defun una-jugada-ordenador ()
(setf pos-tablero nil) ;posicion absoluta de *tablero*
(setf lineas-n (obtener *tablero*));las lineas-n tienen claves
(setf lineas-n (quita-completos lineas-n)); quita las lineas que ya estan completas.
(when (not (equal lineas-n nil))
(progn
(setf seleccion (seleccionar lineas-n))
(setf linea-n (nth (random (length seleccion)) seleccion)) ;toma una linea-n al azar de seleccion
(setf linea (getf linea-n :lin));linea seleccionada
(setf posicion (getf linea-n :pos));tipo de linea seleccionada - | / \
(setf pos-x (busca-n linea));busca una posicion en blanco
(agrega-x linea pos-x) ;coloca la 'x
;Coloca la linea correspondiente en el tablero 0 1 2
;linea 0 1 2 son horizontales 3 4 5
;lineas 3 4 5 verticales 6 7 8
;linea 6 diagonal \
;linea 7 diagonal /
;pos-x es la posicion dentro de una linea y pos-tablero es la posicion absoluta dentro de *tablero*
(cond
((= posicion 0)
(cond
((= pos-x 0) (setf pos-tablero 0))
((= pos-x 1) (setf pos-tablero 1))
((= pos-x 2) (setf pos-tablero 2))))
((= posicion 1)
(cond
((= pos-x 0) (setf pos-tablero 3))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 5))))
((= posicion 2)
(cond
((= pos-x 0) (setf pos-tablero 6))
((= pos-x 1) (setf pos-tablero 7))
((= pos-x 2) (setf pos-tablero 8))))
((= posicion 3)
(cond
((= pos-x 0) (setf pos-tablero 0))
((= pos-x 1) (setf pos-tablero 3))
((= pos-x 2) (setf pos-tablero 6))))
((= posicion 4)
(cond
((= pos-x 0) (setf pos-tablero 1))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 7))))
((= posicion 5)
(cond
((= pos-x 0) (setf pos-tablero 2))
((= pos-x 1) (setf pos-tablero 5))
((= pos-x 2) (setf pos-tablero 8))))
((= posicion 6)
(cond
((= pos-x 0) (setf pos-tablero 0))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 8))))
((= posicion 7)
(cond
((= pos-x 0) (setf pos-tablero 2))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 6)))))
(setf (nth pos-tablero *tablero*) (nth pos-x linea)))) ;Coloca la ficha en *tablero*
pos-tablero) ;Devuelve la posicion absoluta de tablero, donde se coloco la ficha
Ok. :-) y dejo el link del programa completo con interfaz gráfica: tic-tac-toe-5.lisp
Para recordar como se ejecutan estos programas con ltk:
1 1) Tener tcl/tk instalado en tu sistema operativo.
Si tenes alguna distribución linux, hay que instalar primero los paquetes tcl8.5 y tk8.5, podes hacerlo desde el gestor de paquetes. Voy a mostrar la instalación en ubuntu:
Abre una terminal y logueate como administrador:
> sudo su
Instala los paquetes con apt-get, o con algun gestor de paquetes.
> apt-get install tcl8.5
> apt-get install tk8.5
Si tu sistema operativo es Windows puedes descargar e instalar la última versión de ActiveTcl desde: https://www.activestate.com/activetcl/downloads
Asegurate de tener el sistema operativo actualizado, prueba ejecutar c:\ActiveTcl\bin\wish.exe y te aparecerá una ventana vacía. Si da error debes actualizar Universal C Runtime: https://support.microsoft.com/es-ar/help/2999226/update-for-universal-c-runtime-in-windows
2) Tener el archivo ltk.lisp.
Se puede descargar desde: http://beta.quicklisp.org/archive/ltk/2011-07-30/ltk-0.96.tgz
O desde mi cuenta de box: https://www.box.com/s/e2d42ef29fd4d3c34150
3
3) Cargar el programa ltk.lisp y tic-tac-toe-5.lisp en la consola de lisp.
(load "/ruta/ltk.lisp") ;en mi caso hago: (load "c:/users/renepc/documents/mis-programas-lisp/ltk.lisp")
(load "/ruta/tic-tac-toe.lisp") ;en mi caso hago: (load "c:/users/renepc/documents/mis-programas-lisp/tic-tac-toe-5.lisp")
4) Ejecutar el main dentro del paquete:
(tic-tac-toe:main)
También se puede crear un archivo arranca-ttt5.lisp por ejemplo, que carge el ltk.lisp, el programa tic-tac-toe-5.lisp y ejecute (tic-tac-toe:main), para no tener que hacer tantos pasos.
También se puede crear un archivo arranca-ttt5.lisp por ejemplo, que carge el ltk.lisp, el programa tic-tac-toe-5.lisp y ejecute (tic-tac-toe:main), para no tener que hacer tantos pasos.
No hay comentarios:
Publicar un comentario