stephanet

Un neurone est une fonction extrêmement simple qui prend un certain nombre de paramètres et retourne soit 0 (ou -1) soit 1 selon la valeur des arguments qui lui sont passés. Il multiplie chacun de ces argument par une valeur, additionne le tout et rajoute une constante. Si le résultat de cette opération est positive, alors il retourne 1, si elle est négative, il retourne -1.

L’intérêt de ce neurone, c’est qu’il est capable d’apprendre, c’est à dire que si on lui montre un jeu de données avec le résultat attendu, il va régler de lui même les constantes à utiliser pour sa petite opération et essayer de trouver une valeur idéale pour retourner la bonne réponse.

Ça vous intéresse, je vous suggère la lecture de la page Wikipedia et de faire vos propres recherches : https://en.wikipedia.org/wiki/Perceptron

Mon implémentation est sans doute très naïve et je suis certain qu’il existe une tonne de librairies qui le font beaucoup mieux que moi. Mais l’objectif ici est de comprendre le rouage de la chose, comment cela fonctionne. Une fois cela compris, il est certain que se tourner vers une librairie, complète, testée et optimisée est tout à fait recommandable pour faire un vrai projet en prod.

(setf data '(
	     (20 2000 1)
	     (40 1000 -1)
	     (30 3000 1)
	     (30 1000 -1)
	     (20 3000 1)
	     (40 2000 -1)
	     (40 4000 1)
	     (20 2000 -1)
	     (30 4000 1)
	     (20 4000 1)
	     (40 3000 -1)))


(defvar w '(1 1 1))

(defun magic (w x y)
  (if (> (+ (first w) (* (second w) x) (* (third w) y)) 0)
      1
      -1))


(dolist (l data)
  (format t "-----~%")
  (format t "~A~%" l)
  (let ((c (magic w (first l) (second l)))
	(alpha 0.00001))
    (format t "G/S=> ~A/~A~%" c (third l))
    
    (setf (first w)
	  (+ (first w) (*
			1
			alpha
			(- (third l) c))))
    (setf (second w)
	  (+ (second w) (*
			 (first l)
			 alpha
			 (- (third l) c ))))
    (setf (third w)
	  (+ (third w) (*
			(second l)
			alpha
			(- (third l) c))))
    (format t "~A~%" w)))
  
  
	     
      

Je n’ai pas la moindre idée de comment se nomme ce jeu en Français, il s’agit de cette grille de trois sur trois ou l’on rentre des X et des O. Le premier à avoir aligné trois caractères identique a gagné la partie.

Dans ma course à la compréhension de l’Intelligence artificielle, j’ai donc décidé de m’attaquer `a ce jeu et d’implanter l’algorithme Minimax en Common Lisp.

L’ordinateur n’est pas imbattable, en fait, il suffit d’un peu de stratégie pour gagner, mais il tient quand même la partie. Je pense qu’il faudrait pondérer les coups en fonction du nombre de coups avant de gagner pour améliorer le système. Mais qu’à cela ne tienne, l’ordinateur connait les règles, il essaye de gagner et essaye de faire perdre son adversaire.

Le principle consiste tout simplement à visualiser par avance toutes les parties possibles pour chaque coup et de jouer en priorité ceux qui lui permettent d’arriver à la victoire.

Le code ci-dessous:

#!/opt/homebrew/bin/sbcl --script


(defmacro t-equal (p a b c)
  `(and
    (equal ,p ,a)
    (equal ,a ,b)
    (equal ,a ,c)))

(defun arrived (player state)
  (or
   (t-equal player (nth 0 state) (nth 1 state) (nth 2 state))
   (t-equal player (nth 3 state) (nth 4 state) (nth 5 state))
   (t-equal player (nth 6 state) (nth 7 state) (nth 8 state))
   (t-equal player (nth 0 state) (nth 4 state) (nth 8 state))
   (t-equal player (nth 2 state) (nth 4 state) (nth 6 state))
   (t-equal player (nth 0 state) (nth 3 state) (nth 6 state))
   (t-equal player (nth 1 state) (nth 4 state) (nth 7 state))
   (t-equal player (nth 2 state) (nth 5 state) (nth 8 state))))

(defun actions (state player)
  (let ((ret ()))
    (dotimes (i 9)
      (when (null (nth i state))
	(let ((node (copy-list state)))
	  (setf (nth i node) player)
	  (push node ret))))
    ret))

(defun display-board (state)
  (format t "--~%~%~A|~A|~A~%-----~%~A|~A|~A~%-----~%~A|~A|~A~%"
	  (or (nth 0 state) " ")
	  (or (nth 1 state) " ")
	  (or (nth 2 state) " ")
	  (or (nth 3 state) " ")
	  (or (nth 4 state) " ")
	  (or (nth 5 state) " ")
	  (or (nth 6 state) " ")
	  (or (nth 7 state) " ")
	  (or (nth 8 state) " ")))

(defun other-player (player)
  (if (equal player 1)
      2
      1))

(defun utility (state)
  (when (arrived 1 state)
    (return-from utility -1))
  (when (arrived 2 state)
    (return-from utility 1))
  0)

(defun arrived? (state)
  (or
   (arrived 1 state)
   (arrived 2 state)))

(defun max-value (state)
  (when (arrived? state)
    (return-from max-value (utility state)))
  (let ((actions (actions state 2))
	(l '(-99999999999)))
    (dolist (action actions)
      (push (min-value action) l))
    (reduce #'max l)))

(defun min-value (state)
  (when (arrived? state)
    (return-from min-value (utility state)))
  (let ((actions (actions state 1))
	(l '(9999999999)))
    (dolist (action actions)
      (push (max-value action) l))
    (reduce #'min l)))



(defun ask-user (state)
  (display-board state)
  (format t "From 0 to 8, where do you play ?~%")
  (let ((input (read)))
    (setf (nth input state) 1))
  state)

(defvar state '(nil nil nil nil nil nil nil nil nil))

(loop
  (when (arrived? state)
    (display-board state)
    (format t "Computer wins~%")
    (return))
  (setf state (ask-user state))
  (when (arrived? state)
    (display-board state)
    (format t "User wins~%")
    (return))
  
  (let ((actions (actions state 2))
	(temporary-state nil)
	(v -9999))
    (dolist (action actions)
      (let ((w (min-value action)))
	(when (> w v)
	  (display-board action)
	  (format t "Got ~A~%" w)
	  (setf v w)
	  (setf temporary-state action))))
    (setf state temporary-state)))