Yellow Rabbit

Старая версия

Здесь находится настоящий сайт

Продвинутая эвристика для искусственного интеллекта

26 Dec 2015 • 4 мин. читать • Comments •

Игра Трилобит на Lisp: новая эвристика

Компьютер играет хуже своего собрата из 11th hour. С этим надо что-то делать. Попробуем другие эвристики для компьютерного игрока.

Идея

Для начала небольшая парочка функций, которые подсчитывают количество фишек противника в соседних клетках.


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

Процесс экспериментирования с эвристиками стал гораздо легче, когда я ввел несколько констант, которые задавали относительные веса разных эвристик. В частности победа или поражения имеют просто огромный вес.


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

А вот как теперь оценивается позиция с помощью новых весовых коэффициентов:


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

Суть новой эвристики: кроме подсчёта перспективных линий из своих фишек AI старается сделать ход так, чтобы иметь в соседях как можно больше фишек противника. ``Облепливая’’ фишки противника AI тем самым снижает его возможности строить линии.

Победа :trophy:

Новый AI смог победить монстра из 11-го часа! Вот финальная позиция Следующим ходом лисповский AI поставит светлую фишку в позицию курсора. Полный лог сражения между компьютерами.