; ; Here are two (simple) sample evaluation functions and two games that ; I played with each (the first with it only searching to depth 2, the ; second to depth 4). ; ; You can see that even very simple evaluation functions can play a ; game and... well... not lose immediately. ; ; I expect that you'll come up with an evaluation function much more ; sophisticated than these. Yours should handily win a game against ; either of these or similar simple evaluation functions. ; ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Evaluation function 1 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Here is a very simple evaluation procedure. Actually, it's hardly ; an evaluation procedure at all --- if no one won the game, the value ; is 0. Still, this can use the power of the (alpha-beta) minimax ; search to look ahead. It can avoid losing games within its look ; ahead, but if it loses beyond that horizon, it won't know which move ; to make. ; (define (c4-eval-1 board current-player max-player) (let ((winner (c4-end? board))) (cond ((equal? winner max-player) 1000) ((equal? winner (other-player max-player)) -1000) ((equal? winner 'draw) 0) (else 0)))) ;Value: c4-eval-1 ;;;;;;;;;;;;;;;; ; I've added some commentary to the two games below ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; only searching to depth 2 for this first game!!! ; (define r (create-c4-player c4-eval-1 2)) ;Value: r (play-c4 human-player r) +---------------+ 6| | 5| | 4| | 3| | 2| | 1| | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; all moves look equal to it, so it just chooses 1 +---------------+ 6| | 5| | 4| | 3| | 2| | 1| O X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| | 2| X | 1| O X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; again because all moves look equal to it since ; it neither wins nor loses in the next two ; moves +---------------+ 6| | 5| | 4| | 3| | 2| O X | 1| O X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| X | 2| O X | 1| O X | +---------------+ 1 2 3 4 5 6 7 O plays in column 4. ; here it can see that if it doesn't play in ; column 4, then on X's next move, X can win, ; and that's bad for O +---------------+ 6| | 5| | 4| O | 3| X | 2| O X | 1| O X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 5 X plays in column 5. +---------------+ 6| | 5| | 4| O | 3| X | 2| O X | 1| O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; again because it neither wins nor loses in the ; next 2 moves +---------------+ 6| | 5| | 4| O | 3| O X | 2| O X | 1| O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 1 X plays in column 1. +---------------+ 6| | 5| | 4| X O | 3| O X | 2| O X | 1| O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; it does not see the "open three in a row at ; both ends" which is coming because that does ; not lead to a win or loss in the next 2 moves +---------------+ 6| | 5| O | 4| X O | 3| O X | 2| O X | 1| O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 3 X plays in column 3. +---------------+ 6| | 5| O | 4| X O | 3| O X | 2| O X | 1| O X X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; now, it doesn't matter where O plays because ; it will lose to X on the next move +---------------+ 6| O | 5| O | 4| X O | 3| O X | 2| O X | 1| O X X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 6 X plays in column 6. +---------------+ 6| O | 5| O | 4| X O | 3| O X | 2| O X | 1| O X X X X | +---------------+ 1 2 3 4 5 6 7 Player X wins in 13 moves! ;Value 9: (x 13) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; searching to depth 4 for this game ; (define s (create-c4-player c4-eval-1 4)) ;Value: s (play-c4 human-player s) +---------------+ 6| | 5| | 4| | 3| | 2| | 1| | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| O X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 5 X plays in column 5. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 3. ; it can now see that X wins in 4 moves if this ; "open two at both ends" is not blocked +---------------+ 6| | 5| | 4| | 3| | 2| | 1| O O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 6 X plays in column 6. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| O O X X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 7. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 5 X plays in column 5. +---------------+ 6| | 5| | 4| | 3| | 2| X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; all moves look the same because no one wins in 4 moves +---------------+ 6| | 5| | 4| | 3| | 2| O X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| | 2| O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. +---------------+ 6| | 5| | 4| | 3| O | 2| O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 1 X plays in column 1. +---------------+ 6| | 5| | 4| X | 3| O | 2| O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 O plays in column 3. ; I now have a forced win, but it's more than 4 ; moves ahead. +---------------+ 6| | 5| | 4| X | 3| O | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 3 X plays in column 3. ; actually, this was not the right move +---------------+ 6| | 5| | 4| X | 3| O X | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 O plays in column 3. ; because if X plays 4, then O cannot block at ; both 3 and 4. O at 4 is a better move, but ; from this evaluation function's perspective, ; moving at either 3 or 4 blocks the X at 4 ; forced win. However, I still have a forced ; win that is more than 4 moves ahead. +---------------+ 6| | 5| | 4| X O | 3| O X | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| X O | 3| O X X | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 O plays in column 4. +---------------+ 6| | 5| | 4| X O O | 3| O X X | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 5 X plays in column 5. +---------------+ 6| | 5| | 4| X O O | 3| O X X X | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; because O loses either way (if O plays 5, then ; X plays 6 and can win with either 6 or 7) +---------------+ 6| | 5| O | 4| X O O | 3| O X X X | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 5 X plays in column 5. +---------------+ 6| | 5| O | 4| X O O X | 3| O X X X | 2| O O X X | 1| O O X X X O | +---------------+ 1 2 3 4 5 6 7 Player X wins in 19 moves! ;Value 10: (x 19) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Evaluation function 2 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Here is a slightly more complicated evaluation function. It knows ; that open columns are good for it and bad for the opponent to have. ; ; If the board is not a win or a draw, then we tally up: ; ; * for MAX: 1 point for every "open column of two" and 2 points for ; every "open column of three" ; ; * for MIN: -1 point for every "open column of two" and -2 points for ; every "open column of three" ; (define (c4-eval-2 board current-player max-player) (let ((winner (c4-end? board))) (cond ((equal? winner max-player) 1000) ((equal? winner (other-player max-player)) -1000) ((equal? winner 'draw) 0) (else (let ((max-c (open-columns board max-player)) (min-c (open-columns board (other-player max-player)))) (apply + (append (map * '(1 2) max-c) (map * '(-1 -2) min-c)))))))) ;Value: c4-eval-2 ;;;;;;;;;;;;;;;; ; again, two games with commentary ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; search to depth 2 (define t (create-c4-player c4-eval-2 2)) ;Value: t (play-c4 human-player t) +---------------+ 6| | 5| | 4| | 3| | 2| | 1| | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| X | +---------------+ 1 2 3 4 5 6 7 O plays in column 4. ; because otherwise X could get an open 2 on X's ; next move +---------------+ 6| | 5| | 4| | 3| | 2| O | 1| X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 5 X plays in column 5. +---------------+ 6| | 5| | 4| | 3| | 2| O | 1| X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 4. ; still doesn't see that an open row of 2 will ; win because it's more than 2 moves ahead. ; Instead, it sees that it can get a column of 2. +---------------+ 6| | 5| | 4| | 3| O | 2| O | 1| X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 3 X plays in column 3. +---------------+ 6| | 5| | 4| | 3| O | 2| O | 1| X X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. +---------------+ 6| | 5| | 4| | 3| O | 2| O | 1| O X X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 2 X plays in column 2. +---------------+ 6| | 5| | 4| | 3| O | 2| O | 1| O X X X X | +---------------+ 1 2 3 4 5 6 7 Player X wins in 7 moves! ;Value 11: (x 7) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; now search to depth 4 (define u (create-c4-player c4-eval-2 4)) ;Value: u (play-c4 human-player u) +---------------+ 6| | 5| | 4| | 3| | 2| | 1| | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| | 2| | 1| X | +---------------+ 1 2 3 4 5 6 7 O plays in column 4. +---------------+ 6| | 5| | 4| | 3| | 2| O | 1| X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 5 X plays in column 5. +---------------+ 6| | 5| | 4| | 3| | 2| O | 1| X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 3. ; it's able to see than an unblocked both-end ; open row of 2 wins within the next 4 moves, ; so it blocks. +---------------+ 6| | 5| | 4| | 3| | 2| O | 1| O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 3 X plays in column 3. +---------------+ 6| | 5| | 4| | 3| | 2| X O | 1| O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; all moves look the same. even if O played 4, ; then X plays 4, O can play 3 or 5 (blocking a ; possible open column of 2), but then X takes ; the other. Net result --- X has one more ; open column of two than O does. Therefore, ; all moves look the same, and O plays 1. +---------------+ 6| | 5| | 4| | 3| | 2| X O | 1| O O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 2 X plays in column 2. +---------------+ 6| | 5| | 4| | 3| | 2| X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; in order to get that open column of 2 +---------------+ 6| | 5| | 4| | 3| | 2| O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 4 X plays in column 4. +---------------+ 6| | 5| | 4| | 3| X | 2| O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 2. ; not sure why. maybe so that X can't get an ; open column at 2 +---------------+ 6| | 5| | 4| | 3| X | 2| O O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 3 X plays in column 3. +---------------+ 6| | 5| | 4| | 3| X X | 2| O O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 2. +---------------+ 6| | 5| | 4| | 3| O X X | 2| O O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 3 X plays in column 3. +---------------+ 6| | 5| | 4| X | 3| O X X | 2| O O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 O plays in column 1. ; this is because X now has a forced win: X ; plays 6 threatening a win with 5 or 7. O ; loses no matter where it goes, so it takes ; the default move of 1. +---------------+ 6| | 5| | 4| X | 3| O O X X | 2| O O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 You are playing X Which column do you want to play in? (1-7 inclusive) Enter your move and press return (or C-x C-e in Emacs/Edwin 3 X plays in column 3. +---------------+ 6| | 5| X | 4| X | 3| O O X X | 2| O O X O | 1| O X O X X | +---------------+ 1 2 3 4 5 6 7 Player X wins in 15 moves! ;Value 12: (x 15)