Yellow Rabbit

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

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

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

23 Dec 2015 • 8 мин. читать • Comments •

Игра Трилобит на Lisp: совершенствуем AI

Итак противник уже играет круче меня, но это не достижение, меня все обыгрывают. Будем улучшать искусственный разум.

Чуточку умнее

Итак, AI действует разумно только когда видит чью-нибудь победу через ближайшие *ai-level* ходов, иначе просто выбирает первый же ход. Попробуем следующую эвристику:

Отсюда наилучшая позиция — это позиция, где длина линии из фишек нашего цвета равна *win-len*.

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

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

;; count longest line
(defun score-position (tree move)
  (let ((cnt (count-player-cells 
               (game-node-board tree) 
               move 
               (change-player (game-node-player tree)))))
    (if (eql *ai-player* (game-node-player tree))
      (- cnt)
      cnt)))

Небольшие изменения в старых функциях оценки ходов:

  1. чтобы подсчитать длину линии, получившуюся в результате последнего хода, нужно этот ход знать;
  2. собственно подсчёт длины линии.
(defun rate-position (tree move)    ; // 1
  (let ((moves (game-node-moves tree)))
        (if (not (lazy-null 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*)
            (score-position tree move))))) ; // 2

(defun get-ratings (tree)
  (mapcar (lambda (move)
            (rate-position (cadr move) (car move))) ; // 1
          (take-all (game-node-moves tree))))

Листинг игры

current player = The Evil AI
........
........
........
........
........
........
........
abcdefgh
current player = Human
........
........
........
........
........
........
A.......
abcdefgh
choose your move:
1. a
2. b
3. c
4. d
5. e
6. f
7. g
8. h
2

current player = The Evil AI
........
........
........
........
........
........
AH......
abcdefgh
current player = Human
........
........
........
........
........
A.......
AH......
abcdefgh
choose your move:
1. a
2. b
3. c
4. d
5. e
6. f
7. g
8. h
1

current player = The Evil AI
........
........
........
........
H.......
A.......
AH......
abcdefgh
current player = Human
........
........
........
........
H.......
AA......
AH......
abcdefgh
choose your move:
1. a
2. b
3. c
4. d
5. e
6. f
7. g
8. h
2

current player = The Evil AI
........
........
........
........
HH......
AA......
AH......
abcdefgh
current player = Human
........
........
........
A.......
HH......
AA......
AH......
abcdefgh
choose your move:
1. a
2. b
3. c
4. d
5. e
6. f
7. g
8. h
3

current player = The Evil AI
........
........
........
A.......
HH......
AA......
AHH.....
abcdefgh
current player = Human
........
........
A.......
A.......
HH......
AA......
AHH.....
abcdefgh
choose your move:
1. a
2. b
3. c
4. d
5. e
6. f
7. g
8. h
3

current player = The Evil AI
........
........
A.......
A.......
HH......
AAH.....
AHH.....
abcdefgh
current player = Human
........
A.......
A.......
A.......
HH......
AAH.....
AHH.....
abcdefgh
choose your move:
1. a
2. b
3. c
4. d
5. e
6. f
7. g
8. h
1

current player = The Evil AI
H.......
A.......
A.......
A.......
HH......
AAH.....
AHH.....
abcdefgh
current player = Human
H.......
A.......
A.......
A.......
HH......
AAH.....
AHHA....
abcdefgh
choose your move:
1. b
2. c
3. d
4. e
5. f
6. g
7. h
2

current player = The Evil AI
H.......
A.......
A.......
A.......
HHH.....
AAH.....
AHHA....
abcdefgh
current player = Human
H.......
A.......
A.......
A.A.....
HHH.....
AAH.....
AHHA....
abcdefgh
choose your move:
1. c
2. b
3. d
4. e
5. f
6. g
7. h
3

current player = The Evil AI
H.......
A.......
A.......
A.A.....
HHH.....
AAHH....
AHHA....
abcdefgh
current player = Human
H.......
A.......
A.......
A.A.....
HHHA....
AAHH....
AHHA....
abcdefgh
choose your move:
1. c
2. b
3. d
4. e
5. f
6. g
7. h
4

current player = The Evil AI
H.......
A.......
A.......
A.A.....
HHHA....
AAHH....
AHHAH...
abcdefgh
current player = Human
H.......
A.......
A.......
AAA.....
HHHA....
AAHH....
AHHAH...
abcdefgh
choose your move:
1. b
2. c
3. d
4. e
5. f
6. g
7. h
1

current player = The Evil AI
H.......
A.......
AH......
AAA.....
HHHA....
AAHH....
AHHAH...
abcdefgh
current player = Human
H.......
A.......
AH......
AAAA....
HHHA....
AAHH....
AHHAH...
abcdefgh
The winner is The Evil AI
*

Я проиграл :frowning: