Frozen
Here is an active version
Advanced Heuristics for Artificial Intelligence
The computer plays worse of its colleague from the 11th hour. It is necessary to do something with it. Let’s try other heuristics for the computer player.
Idea
To begin with, a small couple of functions that count the number of enemy chips in neighboring cells.
;; count enemy neighbors
(defun slow-get-neighbors-pattern (cell)
(remove-if #'null
(list
(when (> (mod cell *board-width*) 0)
(1- cell))
(when (>= cell *board-width*)
(- cell *board-width*))
(when (< (mod cell *board-width*) (1- *board-width*))
(1+ cell))
(when (< (floor cell *board-width*) (1- *board-height*))
(+ cell *board-width*))
(when (and (> (mod cell *board-width*) 0)
(>= cell *board-width*))
(- cell *board-width* 1))
(when (and (< (floor cell *board-width*) (1- *board-height*))
(>= cell *board-width*))
(- cell *board-width* -1))
(when (and (> (mod cell *board-width*) 0)
(< (floor cell *board-width*) (1- *board-height*)))
(+ cell *board-width* -1))
(when (and (< (mod cell *board-width*) (1- *board-width*))
(< (floor cell *board-width*) (1- *board-height*)))
(+ cell *board-width* 1)))))
(defun count-enemy-neighbors (board cell player)
(let
((pat (slow-get-neighbors-pattern cell))
(enemy (change-player player)))
(* *enemy-weight*
(reduce (lambda (acc x) (if (cell-playerp board x (change-player player))
(1+ acc)
acc)) pat :initial-value 0))))
The process of experimenting with heuristics became much easier when I added several constants that set the relative weights of different heuristics. In particular, victory or loss have a huge weights.
(defparameter *enemy-weight* 4)
(defparameter *player-weight* 5)
(defparameter *win-weight* (* 9 (max *enemy-weight* *player-weight*)))
(defparameter *ai-win* *win-weight*)
(defparameter *draw* 0)
(defparameter *human-win* (- *win-weight*))
Here how the position is now scored with the help of new weighting factors:
;; count longest line
(defun score-position (tree move)
(let ((cnt (count-player-cells
(game-node-board tree)
move
(last-player tree)))
(enemy (count-enemy-neighbors
(game-node-board tree)
move
(last-player tree))))
(+ enemy (* *player-weight* (if (last-playerp tree *ai-player*)
cnt
(- cnt))))))
The essence of the new heuristics: in addition to calculating promising lines from its chips, AI tries to make a move to have as many opponent chips in its neighbors as it can. ``Enclosing’’ opponent’s chips AI thereby reduces its ability to build lines.
Win 
The new AI was able to defeat the monster from the 11th hour! Here is the final position The next move, the AI will put the light chip in the cursor position. Full log of the battle between computers.
