Yellow Rabbit

Frozen

Here is an active version

The Simplest Heuristic for the Machine Mind

23 Dec 2015 • 9 min. read • Comments •

Trilobit Game in Lisp: Improve AI

So the enemy already plays better than me, but this is not an achievement, I’m all overplayed. We will improve the artificial mind.

A little smarter

So AI acts sensibly only when it sees someone’s victory through the nearest *ai-level* moves, otherwise it just chooses the first move. Let’s try the following heuristic:

Hence the best position is the position where the length of the line from the chips of our color is *win-len*.


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

The new function evaluates the position based on the move player made and how long the line from the chips turned out.


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

Minor changes in the old evaluation functions:

  1. To calculate the length of the line, resulting from the last move, you need to know this move;
  2. Proper calculation of the length of the line.

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

Game Log


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
*

I lost :frowning: