; The alpha-beta minimax that you are writing will be customized to
; play Connect 4 only in that you are hardcoding the "c4-children" and
; "c4-end?" procedures.  However, for debugging your alpha-beta
; minimax, Connect 4 is not so great because it has a branching factor
; of 7 for at least the first four moves.
;
; However, you can redefine these procedures to implement some other
; game tree.
;
; This file contains procedures for implementing the game tree that
; you used for Problem 1.  These procedures replace the Connect 4
; procedures in connect4.scm and a4code.com, so you must load this
; file afterwards in order to redefine them.
;
; The move at each depth is an integer between 1 and the branching
; factor at that depth (inclusive).  The tree from problem 1 has a
; branching factor of 3 at depth 0 and a branching factor of 2 at the
; other depths.
;
; There is a procedure "c4-eval" which will take a state at depth 4
; and return the value using the Problem 1 game tree.
;
; For example, the state (2 1 1 2) means taking the middle branch at
; depth 0, the left branches and depth 1 and 2, and the right branch
; at depth 3.  The value of the resulting depth 4 state is:
;
;    (c4-eval '(2 1 1 2) 'X 'X)
;    ;Value: -2
;
; Note that these procedures take the same arguments as their depth 4
; counterparts, even though the "player" arguments aren't used.
;
; This code has been written generally enough that you can try other
; game trees.  You can change the branching factors and leaf-node
; values.  Just make sure you specify enough leaf-node values for the
; whole tree!
; 
; When you want to go back to working on Connect 4, you'll have to
; load connect4.scm and a4code.com again.
; 

(define branching-factors '(3 2 2 2))

(define leaf-values '(6 7 6 0 3 2 -8 6 9 -2 6 -4 -7 6 8 -7 -2 -5 -8 -6
			3 -2 -5 0))
(define c4-start '())

(define (c4-end? state)
  (= (length state) 
     (length branching-factors)))

(define (c4-children state player)
  (if (c4-end? state)
      (error (string-append "ERROR: can't generate children past depth "
			    (number->string (length branching-factors))
			    " for state:")
	     state))
  (map (lambda (i)
	 (append state (list i)))
       (integers:j-k 1 (list-ref branching-factors (length state)))))

(define (c4-eval state current-player max-player)
  (if (not (= (length state) (length branching-factors)))
      (error "ERROR: can't evaluate the partial state" state))
  (list-ref leaf-values
	    (apply + (map (lambda (f s)
			    (* f (- s 1)))
			  (calc-skip branching-factors)
			  state))))

; your code is probably using this somewhere...
(define (get-move state1 state2)
  (car (last-pair state2)))

; redefine this procedure just in case
(define (print-board state)
  (print state "\n"))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; utility function to generate a list of consecutive integers
(define (integers:j-k j k)
  (if (> j k)
      '()
      (cons j (integers:j-k (+ j 1) k))))

; calculate the number of leaf nodes to skip in "leaf-values" when
; incrementing the move at each depth in the tree.  In other words,
; how many leaf nodes are in a subtree for a node at each depth:
; (d1-subtree-nodes d2-subtree-nodes ...).  This is used in
; calculating the position in "leaf-values" to find the evaluation
; function value.
(define (calc-skip b-factors)
  (define (cs bf n result)
    (if (= (length bf) 1)
	result
	(let ((nn (* n (car bf))))
	  (cs (cdr bf) nn (cons nn result)))))
  (cs (reverse b-factors) 1 '(1)))