Yellow Rabbit

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

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

Трилобит: система игровых правил и AI

14 Dec 2015 • 7 мин. читать • Comments •

Игра Трилобит на Lisp: Правила и AI

Игра, описанная ранее и которая почти ожила пока ещё не разумна. Попробуем добавить в неё немного интеллекта

Движок игровых правил

Поскольку мы можем просчитать все комбинации (пока что для крошечной доски), то движок правил будет представлять из себя просто древовидную структуру данных1.

Дерево движка игровых правил для игры Трилобит


;; game rules engine is a tree which elements are lists
(defstruct (game-node (:type list))
  player  ; *human-player* or *ai-player*
  board   ; current board situation
  failp   ; is it a fail?
  moves)  ; nil or list of lists (move cell . game-tree).
Поле Тип Назначение
player число игрок, который сейчас будет ходить
board массив доска
failp флажок текущий игрок проиграл
moves список элементов ( ячейка . узел) ячейка, куда делает ход текущий игрок и узел дерева

Движок правил будет проверять допустимость ходов для человека, обеспечивать необходимыми данными искусственный интеллект и обнаруживать победу/поражение. Листьями дерева движка являются узлы с установленным флажком поражения или пустым списком возможных ходов, последнее означает ничью.

Итак создаём дерево движка правил, это делается одной рекурсивной функцией, и она прекрасно справляется с крошечной доской 3х3, однако очень быстро исчерпывает стек и ломается на больших досках.


;; new tree
(defun game-tree (board player move)
  (let ((fail (if (eql -1 move)
                nil
                (test-for-win board move
                              (change-player player)))))
         (make-game-node
           :player player
           :board board
           :failp fail
           :moves 
             (if fail
               '()
               (mapcar (lambda (move)
                            (list move
                                  (game-tree (board-add-move board move player)
                                             (change-player
                                               player)
                                             move)))
                   (possible-moves board))))))

Параметр move у этой функции означает клетку, куда был сделан ход, который привёл к этой ситуации на доске. Если move равен -1, то это значит, что предыдущего хода не было - это самая начальная комбинация и не нужно проверять не проиграл ли кто-нибудь. Первым делом проверяем не проиграл ли кто, в этом случае это листовая комбинация на доске и дальше комбинации не строим. Иначе строим узлы дерева для всех возможных ходов на данной доске.

AI

Искусственный интеллект будет незамысловатой реализаций алгоритма minimax. Суть его заключается в том, что при прогнозировании развития игровой ситуации AI ведёт себя следующем образом:

Другими словами AI рассчитывает, что человек будет действовать наихудшим для AI образом. Оценки, здесь ничья лучше чем проигрыш, но хуже чем победа:


(defparameter *ai-win*     1)
(defparameter *draw*       0)
(defparameter *human-win* -1)

Следующие две функции реализуют этот алгоритм.


(defun rate-position (tree)
  (let ((moves (game-node-moves tree)))
        (if moves
          (apply (if (eq *ai-player* (game-node-player tree))
                   #'max
                   #'min)
                 (get-ratings tree))
          (if (game-node-failp tree)
            (if (eql *ai-player* (game-node-player tree))
              *human-win*
              *ai-win*)
            *draw*))))

(defun get-ratings (tree)
  (mapcar (lambda (move)
            (rate-position (cadr move)))
          (game-node-moves tree)))

Проверим как работает подсчёт оценок для ходов. Создадим пустую доску, где первым будет ходить AI, запомним её для удобства в переменной *game* и посмотрим как он оценивает свои возможные ходы:


* (defvar *game* (game-tree (new-board) *ai-player* -1))

*GAME*
* (game-node-board *game*) ; посмотрим на доску

#(0 0 0 0 0 0 0 0 0)
* (get-ratings *game*)  ; посмотрим оценки

(0 0 0)

Похоже что компьютеру всё равно куда ходить - все ходы оцениваются как ведущие к ничьей. Посмотрим, что будет, если мы сымитируем выбор AI первого хода. Для этого извлечём второй элемент первого хода (cadar список-ходов) и запомним его в переменной *first-move*:


* (defvar *first-move* (cadar (game-node-moves *game*)))

*FIRST-MOVE*

Проверим оценки ситуации:


* (game-node-board *first-move*)

#(0 0 0 0 0 0 1 0 0)
* (get-ratings *first-move*)

(1 1 0)

О! Компьютер увидел для себя два возможных пути к победе! Вряд ли у него получится ими воспользоваться, поскольку сейчас ход человека, и он наверняка выберет последний ход, который ведёт к возможной ничье. Окончательно оформляем действия компьютера как функцию:


; ai
(defun handle-computer (tree)
  (let ((ratings (get-ratings tree)))
      (cadr (nth (position (apply #'max ratings) ratings) (game-node-moves tree)))))

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


* (defvar *game* (game-tree (new-board) *ai-player* -1))

*GAME*
* (game-node-board (handle-computer *game*))

#(0 0 0 0 0 0 1 0 0)

  1. Сделано с помощью маленькой программки для Graphviz. ↩