Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: b36fe569ca
Fetching contributors…

Cannot retrieve contributors at this time

119 lines (100 sloc) 3.512 kb
#! /usr/bin/env racket
#lang racket
(require rackunit)
(struct
state (location)
#:transparent)
(define terminal-states
(map state '(e f g h i j k l m)))
(define (terminal? s)
(member s terminal-states))
(check-not-false (terminal? (state 'e)))
(check-false (terminal? (state 'a)))
(define (utility s)
(cond
[(equal? s (state 'e)) 3]
[(equal? s (state 'f)) 12]
[(equal? s (state 'g)) 8]
[(equal? s (state 'h)) 2]
[(equal? s (state 'i)) 3]
[(equal? s (state 'j)) 9]
[(equal? s (state 'k)) 14]
[(equal? s (state 'l)) 1]
[(equal? s (state 'm)) 8]))
(define (successors s)
(cond
[(equal? s (state 'a))
(map state '(b c d))]
[(equal? s (state 'b))
(map state '(e f g))]
[(equal? s (state 'c))
(map state '(h i j))]
[(equal? s (state 'd))
(map state '(k l m))]))
(define (naive-maximum-value s)
;iterate over all the successors and figure out the values of each of those
(apply max (map value (successors s))))
(define (naive-minimum-value s)
;iterate over all the successors and figure out the values of each of those
(apply min (map value (successors s))))
(define (maximizing? s)
(equal? s (state 'a)))
(define (minimizing? s)
(member s (map state '(b c d))))
(define (11-review-question)
(printf "what's the value of states a b c and d in the tree described?\n")
(printf "~v\n" (map value (map state '(a b c d)))))
(define (cutoff? s depth)
#f)
; depth gets increased as we go along
; alpha is best-value-for-max is lower-bound
; beta is best-value-for-min is upper-bound
; initial call is (value s0 0 -inf.0 +inf.0)
(define (value s [depth +inf.0] [lower-bound -inf.0] [upper-bound +inf.0])
(cond
[(cutoff? s depth) (evaluate s)]
[(terminal? s) (utility s)]
[(maximizing? s) (maximum-value s depth lower-bound upper-bound)]
[(minimizing? s) (minimum-value s depth lower-bound upper-bound)]
[(chance? s) (expected-value s depth lower-bound upper-bound)]
[else (error s "unable to determine what kind of state this is.")]))
; lower-bound = alpha
; upper-bound = beta
(define (maximum-value s depth lower-bound upper-bound)
(let-values
([(maximum-value new-lower-bound within-upper-bound?)
(for/fold ([maximum-so-far -inf.0]
[new-lower-bound lower-bound]
[within-upper-bound? #t])
([successor (successors s)]
#:when within-upper-bound?)
(let ([successor-value
(value successor (add1 depth) new-lower-bound upper-bound)])
(values (max maximum-so-far successor-value)
(max new-lower-bound successor-value)
(< successor-value upper-bound))))])
maximum-value))
; lower-bound = alpha
; upper-bound = beta
(define (minimum-value s depth lower-bound upper-bound)
(let-values
([(minimum-value new-upper-bound within-lower-bound?)
(for/fold
([minimum-so-far +inf.0]
[new-upper-bound upper-bound]
[within-lower-bound? #t])
([successor (successors s)]
#:when within-lower-bound?)
(let ([successor-value
(value successor (add1 depth) lower-bound new-upper-bound)])
(values
(min minimum-so-far successor-value)
(min new-upper-bound successor-value)
(< lower-bound successor-value))))])
minimum-value))
(define (expected-value s)
0)
(define (chance? s)
#f)
(define (evaluate s)
0)
Jump to Line
Something went wrong with that request. Please try again.