The Simplest Heuristic for the Machine Mind

747 words | 2015-12-23

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:

  • the best position is where the length of the line from the chips of our color is maximal;
  • the worst position is where the length of the line from the opponent’s chips is the maximum.

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:

Updated: