CODEWITHSUNDEEP
algorithmtreeracketminimax
Majora320
Majora320

Reputation: 1351

Minimax algorithm not working as expected

I am building an AI for a game of tick-tack-toe, using the stub given in the Realm of Racket book as a basis. So far, everything has gone well. However, when I try to run my minimax function on the root of the tree, it returns a list of the lowest possible values you can get by running it (With either player as the predicate).
Here is a code dump of the function:

(define (minimax tree player depth)
  (define (generate-score tree player depth)
    (define won (winner (ttt-tree-board tree)))
    (if (<= depth 0) 0
        (+ (cond 
             [(equal? won player) 1]
             [(false? won) 0]
             [else -1])
           (apply +
                  (for/list ([t (ttt-tree-moves tree)])
                    (generate-score (second t) player (sub1 depth)))))))
  (for/list ([t (ttt-tree-moves tree)])
    (generate-score (second t) player depth)))

This is only my minimax function, because none of the others (except for winner) need to be displayed. Here is winner:

(define (winner board)
  (or
   (ormap (lambda (row) (if (all-equal? row) (first row) #f)) board) ; Horizontal
   (ormap (lambda (i) (if ; Vertical
                       (all-equal? (map (lambda (j) (list-ref (list-ref board j) i)) (stream->list (in-range (length board)))))
                       (list-ref (first board) i) #f))
          (stream->list (in-range (length board))))
   (if ; Diagonal
    (all-equal? (map (lambda (i) (list-ref (list-ref board i) i)) (stream->list (in-range (length board)))))
    (first (first board)) #f)

   (if ; Diagonal cont.
    (all-equal? (map (lambda (i) (list-ref (reverse (list-ref board i)) i)) (stream->list (in-range (length board)))))
    (last (first board)) #f)))

(It is a bit sloppy, so if anyone has an idea to make it shorter, tell me your suggestion)
ttt-tree structures follow this pattern:

(ttt-tree board moves)

In which board is a 2D array corresponding to the tick-tack-toe board (with the form '((X - O) (O X -) (- X O))), and moves is a list of possible moves that can be made from that node, each of which is a list with two elements: the position that changed, and a ttt-tree which forms the next node. So (second t) refers to the next node, if t is (list-ref (ttt-tree-moves #<ttt-tree>) x)

My original thought was that there may be some error in the cond, but I'm using equal? not eq?, so I don't see how that would be a problem. The other possibility is that I'm defining winner wrong, but I have tested it many times so I don't know what could go wrong. Please help!

Upvotes: 0

Views: 160

Answers (1)

Majora320
Majora320

Reputation: 1351

It turns out that the problem was that in my winner function, I never checked if the winner was "-", the empty tile. Therefore that would trigger in most cases, activating the else clause and resulting in a score of -1.

Upvotes: 1

Related Questions