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)))