;----------------------------------------------------
;		Cassie Reynolds
; 		Ben Sauskojus
;		CS 436
; 		Program 4: Gomoku
;		Due: 12/7/2007 
;		Black Player
;-----------------------------------------------------
; Uses pattern matching to determine the best move to
; make in the game of gomoku.
;------------------------------------------------------


(defconstant whitePositiveInfinity 1e10)	; Positive Infinity
(defconstant whiteNegativeInfinity -1e10)	; Negative Infinity


(defconstant WHITE_BRANCHING_FACTOR 3)	;The size of the array that holds the best moves; Also the branching factor	
(defconstant WHITE_DEPTH_LIMIT 5)		;The depth limit for our search


; Constants used to identify patterns in the board and the point value associated with them
(defconstant 1INAROW 2)				; One stone in a row 
(defconstant 1INAROW_SINGLE_BLOCK 1)		; One stone with a block on either side 
(defconstant 1INAROW_DOUBLE_BLOCK 0)		; One stone with a block on both sides

(defconstant 2INAROW 5)				; Two stones in a row
(defconstant 2INAROW_SINGLE_BLOCK 4)		; Two stones with a block on either side
(defconstant 2INAROW_DOUBLE_BLOCK 0)		; Two stones with a block on both sides

(defconstant 3INAROW 20)			; Three stones is a row
(defconstant 3INAROW_SINGLE_BLOCK 15)		; Three stones with a block on either side
(defconstant 3INAROW_DOUBLE_BLOCK 0)		; Three stones with a block on both sides

(defconstant 4INAROW 70)			; Four stones in a row (40)
(defconstant 4INAROW_SINGLE_BLOCK 65)		; Four stones with a block on either side (30)
(defconstant 4INAROW_DOUBLE_BLOCK 0)		; Four stones with a block on both sides

(defconstant 5INAROW 200)			; Five stones in a row 

; Patterns that have empty spaces between stones (E - empty; S - Stone)
(defconstant 32SPLIT 5)			; A pattern that looks like this S E S
(defconstant 43SPLIT 18)		; A pattern that looks like this S S E S
(defconstant 42SPLIT 4)			; A pattern that looks like this S E E S
(defconstant 54SPLIT 70)		; A pattern that looks like this S S S E S (40)
(defconstant 53SPLIT 12)		; A pattern that looks like this S S E E S
(defconstant 52SPLIT 3)			; a pattern that looks like this S E E E S

; A structure that models a coordinate pair
(defstruct whiteCoord
	x
	y
)

; A structure that is used in minimax to return the
; value of a specific move
(defstruct whiteCoordVal
	coord
	value
)

; A structure that models the range of a pattern
(defstruct whiteRange
	x1		;Begining Coord
	y1

	x2		;Ending Coord
	y2

	x-inc		;How to increment from x1 to x2
	y-inc		;How to increment from y1 to y2

	stoneNumber	;The number of stones in a pattern
	color		;The color of the stones in the pattern
	blockNumber	;1 - if the other player blocks the pattern on the increasing side
			;2 - if the other player blocks the pattern on the decreasing side
			;3 - if the other player blocks the pattern on both sides 
	
	len		;The length of the patten including empty spaces between stones
			;Helps to distinguish between straight and split patterns quickly
)


; A 2D array that maps the pattern values for the offense
(defvar *whiteOffenseMap* (make-array `(,*size* ,*size*) :initial-element 0))
; A 2D array that maps the pattern values for the defense
(defvar *whiteDefenseMap* (make-array `(,*size* ,*size*) :initial-element 0))


; The last move our player made
(defvar whiteOurLastMove nil)
; The last move the other player made
(defvar whiteTheirLastMove nil)




;-----------------------------------------------------
; whiteEvaluatePatterns
;----------------------------------------------------
; infMap:		The influence map to evaluate patterns on
; rangeList:		The list of patterns
; reverseValues:	If we need to reverse the values on the patterns
;-----------------------------------------------------
; This function takes an influence map and evaluates
; the patterns that were identified. It maps the
; values associated with the pattern on to the map.
; Also if a map was used during minimax and a move
; needs to be reversed then the reverseValues parameter
; is sent in to help reverse the map to the way it 
; was before the move was made.
;------------------------------------------------------
(defun whiteEvaluatePatterns (infMap rangeList &optional(reverseValues))
	(let
		(
			patternValue		;The value of the pattern
			xincrement		;How to increment x	
			yincrement		;How to increment y
			ypos			;The x coord
			xpos			;The y coord
		)
		
		(dolist (pattern rangeList)

			(setf patternValue (whiteGetPatternValue pattern))
			
			
			(cond
				((= (whiteRange-len pattern) (whiteRange-stoneNumber pattern))
				
					;Solid Pattern
					(dotimes (i 1)
						
						; Sets the Map Values
						(setf xincrement (* (+ 1 i) (whiteRange-x-inc pattern)))
						(setf yincrement (* (+ 1 i) (whiteRange-y-inc pattern)))
						
						; Sets the increasing side
						(cond
							((not (equal (logand (whiteRange-blockNumber pattern) #b01) 1))			
								(setf xpos (+ xincrement (whiteRange-x1 pattern)))
								(setf ypos (+ yincrement (whiteRange-y1 pattern)))
								
								;;We need to check for stones here. An error will occur if we try to add patternValue to a stone. 
								(if (and (whiteInBoard xpos ypos) (numberp (aref infMap xpos ypos)))
									(if (equal reverseValues t)
										(setf (aref infMap xpos ypos) (- (aref infMap xpos ypos) patternValue))
										(setf (aref infMap xpos ypos) (+ patternValue (aref infMap xpos ypos)))
									)
								)
								
							)
						)
						
						; Sets the decreasing side
						(cond
							((not (equal (logand (whiteRange-blockNumber pattern) #b10) 2))				
								(setf xpos (+ (* -1 xincrement) (whiteRange-x2 pattern)))
								(setf ypos (+ (* -1 yincrement) (whiteRange-y2 pattern)))
								
								;;We need to check for stones here. An error will occur if we try to add patternValue to a stone. 
								(if (and (whiteInBoard xpos ypos) (numberp (aref infMap xpos ypos)))
									(if (equal reverseValues t)
										(setf (aref infMap xpos ypos) (- (aref infMap xpos ypos) patternValue))
										(setf (aref infMap xpos ypos) (+ patternValue (aref infMap xpos ypos)))
									)
								)
							)
						)
					)
					;End of dotimes - Paranthesis are off
					
				)
				(t
					;Split Patterns
					(setf xpos (whiteRange-x1 pattern))
					(setf ypos (whiteRange-y1 pattern))

					(dotimes (i (whiteRange-len pattern))
						(cond
							((and (whiteInBoard xpos ypos) (numberp (aref infMap xpos ypos)))
								(if (equal reverseValues t)
									(setf (aref infMap xpos ypos) (- (aref infMap xpos ypos) patternValue))
									(setf (aref infMap xpos ypos) (+ patternValue (aref infMap xpos ypos)))
								)
							)
						)
	
						(setf xpos (- xpos (whiteRange-x-inc pattern) ))
						(setf ypos (- ypos (whiteRange-y-inc pattern) ))
						
					)
				)
			)

			(if (= patternValue 5INAROW)
				;Write a signal on the influenceMap that a 5INAROW was found
				
				(if (equal reverseValues t)
					(setf (aref infMap 0 0) (first (aref infMap 0 0)))
					(setf (aref infMap 0 0) (list (aref infMap 0 0) 'X))
				)
			)
			
		)
	)
)

;-----------------------------------------------------
; whiteGetPatternValue
;----------------------------------------------------
; range:	The pattern whose value we need to obtain
;-----------------------------------------------------
; This function takes a pattern and then returns the 
; value associated with that pattern.
;------------------------------------------------------
(defun whiteGetPatternValue (range)		

	(cond 
		((= (whiteRange-len range) (whiteRange-stoneNumber range))
		
			(case (whiteRange-stoneNumber range)
				(1
					(case (whiteRange-blockNumber range)
						(0
							1INAROW
						)
						(1
							1INAROW_SINGLE_BLOCK
						)
						(2
							1INAROW_SINGLE_BLOCK
						)
						(3
							1INAROW_DOUBLE_BLOCK
						)
					)
				)
				(2 
					(case (whiteRange-blockNumber range)
						(0
							2INAROW
						)
						
						(1
							2INAROW_SINGLE_BLOCK
						)
						(2
							2INAROW_SINGLE_BLOCK
						)
						(3
							2INAROW_DOUBLE_BLOCK
						)
					)
				)
				(3 
					(case (whiteRange-blockNumber range)
						(0
							3INAROW
						)
						(1
							3INAROW_SINGLE_BLOCK
						)
						(2
							3INAROW_SINGLE_BLOCK
						)
						(3
							3INAROW_DOUBLE_BLOCK
						)
					)
				)
				(4
					(case (whiteRange-blockNumber range)
						(0
							4INAROW
						)
						(1
							4INAROW_SINGLE_BLOCK
						) 
						(2
							4INAROW_SINGLE_BLOCK
						)
						(3
							4INAROW_DOUBLE_BLOCK
						)
					)
				)
				(5
					5INAROW
				)
			)
		)
		(t
				
			(case (whiteRange-len range)
				(3
					32SPLIT
				)
				(4
					(case (whiteRange-stoneNumber range)
						(2
							42SPLIT
						)
						(3
							43SPLIT
						)
					)
				)
				(5
					(case (whiteRange-stoneNumber range)
						(2
							52SPLIT
						)
						(3
							53SPLIT
						)
						(4
							54SPLIT
						)
					)
				)
			)
		)
	)
)

;-----------------------------------------------------
; whitePatternSearch
;----------------------------------------------------
; x:			The x coordinate of the move just made
; y:			The y coordinate of the move just made
; infMap:		The influence map to search for patterns on
; color:		The color of the player who made the move
;-----------------------------------------------------
; This function looks for patterns along all the lines
; of the move that was just made (horizontal, vertical,
; diagonal).
;------------------------------------------------------
(defun whitePatternSearch (x y infMap color)
		(whitePatternFindLine x y 0 1 infMap color 
		(whitePatternFindLine x y 1 0 infMap color 
		(whitePatternFindLine x y 1 1 infMap color 
		(whitePatternFindLine x y -1 1 infMap color))))
)

;-----------------------------------------------------
; whitePatternFindLine
;----------------------------------------------------
; x:			The x coordinate of the move just made
; y:			The y coordinate of the move just made
; x-inc:		The way to increment the x coordinate
; y-inc:		The way to increment the y coordinate
; infMap:		The influence map to search for patterns on
; color:		The color of the player who made the move
; currentRangeList:	The patterns we have found thus far
;-----------------------------------------------------
; This function looks for patterns along a certain
; line (horizontal, vertical, diagonal). 
;------------------------------------------------------
(defun whitePatternFindLine(x y x-inc y-inc infMap color &optional(currentRangeList))			
	(let
		(			
			(movingLeft t)		; Tells us to move to the left (increasing side)
			(movingRight t)		; Tells us to move to the right	(decreasing side)
				
			newRange		; The newly found pattern
			newRange2		; If a pattern needs to be split in two this variable is used
						; for the second pattern
		)

		; Creates new range
		(setf newRange (make-whiteRange :x1 x :x2 x :y1 y :y2 y :x-inc x-inc :y-inc y-inc :stoneNumber 1 :color color :blockNumber 0 :len 1))
		
		

		; Performed up to five away from the move both directions
		(dotimes (i 5)		
		
			(if (eq i 0)		
				(setf i 1)
			)
			
			(cond 
				((equal movingLeft t)
	
					; Moves along the increasing side
					(setf movingLeft (whiteGetPatternChar x y x-inc y-inc i 1 infMap color newRange))
				)
			)		
			
			(cond 
				((equal movingRight t)

					; Moves along the decreasing side
					(setf movingRight (whiteGetPatternChar x y x-inc y-inc i -1 infMap color newRange))
				)
			)
		
			
		)


		; Calculate the length of the pattern
		(setf (whiteRange-len newRange) (+ 1 (max (abs (- (whiteRange-x1 newRange) (whiteRange-x2 newRange))) (abs (- (whiteRange-y1 newRange) (whiteRange-y2 newRange))))))

		; Adds pattern to the list
		(cond
			 ((>= (whiteRange-len newRange) 6)
				
				

				; There  are two patterns using the origin stone
				; Split the newRange into two different patterns
				(setf newRange2 (make-whiteRange :x1 (whiteRange-x1 newRange) :y1 (whiteRange-y1 newRange) :x2 x :y2 y :x-inc x-inc :y-inc y-inc :stoneNumber 1 :color color :blockNumber 0 :len 1))
				(setf (whiteRange-len newRange2) (+ 1 (max (abs (- (whiteRange-x1 newRange2) (whiteRange-x2 newRange2))) (abs (- (whiteRange-y1 newRange2) (whiteRange-y2 newRange2))))))
				(whiteStoneCount newRange2 infMap)	
				
				(setf (whiteRange-x1 newRange) x)
				(setf (whiteRange-y1 newRange) y)
				(setf (whiteRange-len newRange) (+ 1 (max (abs (- (whiteRange-x1 newRange) (whiteRange-x2 newRange))) (abs (- (whiteRange-y1 newRange) (whiteRange-y2 newRange))))))
				(whiteStoneCount newRange infMap)

				(setf currentRangeList (cons newRange currentRangeList))
				(setf currentRangeList (cons newRange2 currentRangeList))
				
				currentRangeList						
			)
			(t
			
				
				(setf currentRangeList (cons newRange currentRangeList))
				currentRangeList
			)
		)
	)
)

;-----------------------------------------------------
; whiteStoneCount
;----------------------------------------------------
; range:		The pattern
; infMap:		The influence map to search for patterns on
;-----------------------------------------------------
; This function counts the number of stones in the range/pattern.
; Used only if a pattern needs to be split into two patterns. 
;------------------------------------------------------
(defun whiteStoneCount (range infMap)					
	(let
		(
			posX		; The x coord
			posY		; The y coord
		)
		
		(setf (whiteRange-stoneNumber range) 1)

		(dotimes (i (- (whiteRange-len range) 1))		
		
			(setf posX (+ (* (whiteRange-x-inc range) i) (whiteRange-x2 range)))
			(setf posY (+ (* (whiteRange-y-inc range) i) (whiteRange-y2 range)))
			
			(if (equal (aref infMap posX posY) (whiteRange-color range))
				(setf (whiteRange-stoneNumber range) (+ 1 (whiteRange-stoneNumber range)))
			)
			
		)
	)
)

;-----------------------------------------------------
; whiteGetPatternChar
;----------------------------------------------------
; x:			The x coordinate of the move just made
; y:			The y coordinate of the move just made
; x-inc:		The way to increment the x coordinate
; y-inc:		The way to increment the y coordinate
; i:			How far the x y is from the origin
; direction:		The direction in way the incrementing is occuring
; infMap:		The influence map to search for patterns on
; color:		The color of the player who made the move
;-----------------------------------------------------
; Gets all the characteristics. Gets the number of stones
; in the pattern, the starting coordinates of the pattern,
; the ending coordinates of the pattern and the block number.
;------------------------------------------------------
(defun whiteGetPatternChar (x y x-inc y-inc i direction infMap color range)
	(let
		(
			posX		; The x coord
			posY		; The y coord
			(result t)	; If we go off the board or hit an opposing stone
					; it is set to false
		)

		(cond 
			((= direction 1)
				(setf posX (+ (* x-inc i) x))
				(setf posY (+ (* y-inc i) y))
			)
			(t
				(setf posX (+ (* -1 x-inc i) x))			
				(setf posY (+ (* -1 y-inc i) y))
			
			)
		)

		(if (whiteInBoard posX posY)
			(cond 
				((equal (aref infMap posX posY) color)		
					

					; Gets the number of stones in the pattern
					(setf (whiteRange-stoneNumber range) (+ 1 (whiteRange-stoneNumber range)))
					
					; Gets the starting and ending coordinates of the pattern
					(cond 
						((= direction 1)
							(setf (whiteRange-x1 range) posX)
							(setf (whiteRange-y1 range) posY)
						)
						(t						
							(setf (whiteRange-x2 range) posX)
							(setf (whiteRange-y2 range) posY)
						)
					)
					
				)
				; Gets the block number of the pattern
				((not (numberp (aref infMap posX posY)))

					(if (= direction 1)
						(setf (whiteRange-blockNumber range) (logior #b01 (whiteRange-blockNumber range)))
						(setf (whiteRange-blockNumber range) (logior #b10 (whiteRange-blockNumber range)))
					)
					
					(setf result nil)
				)
			)
		)
		
		result
	)
)


;-----------------------------------------------------
; whiteInBoard
;----------------------------------------------------
; x:			The x coordinate of the move
; y:			The y coordinate of the move
;-----------------------------------------------------
; Checks to see if the move is in the board.
;------------------------------------------------------
(defun whiteInBoard (x y)
	(if (and (< x *size*) (>= x 0))
		(if (and (< y *size*) (>= y  0))
			t
		)
	)
)

;-----------------------------------------------------
; whiteGetBestMoves
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
;-----------------------------------------------------
; This function gets the branching factor number of
; best moves. This function is used for minimax.
;------------------------------------------------------
(defun whiteGetBestMoves(offMap defMap)
	(let
		(
			max		; The max value between the defmap and offmap
			min		; The smallest value in the bestMovesArray
			minLocation	; The location of the smallest value in the bestMovesArray

			;First column coords, second column offmap value, third column defmap value
			(bestMovesArray (make-array `(,WHITE_BRANCHING_FACTOR 3))) ;Stores the best moves
			
			(count 0)	; Used to determine when the array is initially filled
			x		; The x coord of a move
			y		; The y coord of a move
			coord		; A coordinate for a move
			spotValue	; The value of the slot in the array
		)
		(dotimes (i *size*)
			(dotimes (j *size*)
				(cond
					((numberp (aref offMap i j))

						(cond
							; Fills the best moves array 
							((< count WHITE_BRANCHING_FACTOR)
								(if (> (aref defMap i j) (aref offMap i j))
									(setf max (aref defMap i j))
									(setf max (aref offMap i j))	
								)
								(setf (aref bestMovesArray count 0) (make-whiteCoord :x i :y j))
								(setf (aref bestMovesArray count 1) max)
								(setf count (+ 1 count))
							) 
							(t
								; When the best moves array is full it removes
								; the coord with the smallest max value and replaces it
								(setf min (aref bestMovesArray 0 1))
								(dotimes (k WHITE_BRANCHING_FACTOR)
									
									(setf spotValue (aref bestMovesArray k 1))

									(cond
										((<= spotValue min)
										 	(setf min spotValue)
											(setf minLocation k)
										) 
									)
								)
								(cond
								
									((or (> (aref defMap i j) min) (>= (aref offMap i j) min))
	
										(if (> (aref defMap i j) (aref offMap i j))
											(setf max (aref defMap i j))
											(setf max (aref offMap i j))	
										)

										(setf (aref bestMovesArray minLocation 0) (make-whiteCoord :x i :y j))
										(setf (aref bestMovesArray minLocation 1) max)
										
									)	
								)
							)
						)
						
						
					)
				)
			)
		)
		
		; Sets the array to contain the defmap and offmap values in the correct columns in the array
		(dotimes (i WHITE_BRANCHING_FACTOR)
			(cond
				((not (equal (aref bestMovesArray i 0) nil))
					(setf coord (aref bestMovesArray i 0))					
					(setf x (whiteCoord-x coord))
					(setf y (whiteCoord-y coord))
					(setf (aref bestMovesArray i 1 ) (aref offMap x y))
					(setf (aref bestMovesArray i 2 ) (aref defMap x y))
				)
			)
		)
		
		bestMovesArray
		
	)
)

;-----------------------------------------------------
; whiteFullBoardDif
;----------------------------------------------------
; board:		The board
; infMap:		A influence map
;-----------------------------------------------------
; This function helps us identify where the opponent
; put their stone. 
;------------------------------------------------------
(defun whiteFullBoardDiff (board infMap)
	(let
		(
			newStone	; The new stone placed by the opponent
		)

		(dotimes (i *size*)
			(dotimes (j *size*)
				(cond 
					((or (equal (aref board i j) *black*) (equal (aref board i j) *white*))

						(if (not (equal (aref infMap i j) (aref board i j)))
							(setf newStone (make-whiteCoord :x i :y j))
						)
					)
				)
			)
		)
		
		newStone
	)
)

;-----------------------------------------------------
; white-get-move
;----------------------------------------------------
; board:		The board
;-----------------------------------------------------
; This function determines which move our player will make.
;------------------------------------------------------
(defun white-get-move (board)
	(let
		(

			tempCoord	; A temporary var to hold the hardwired move
			lastMove	; The opponents last move
			nextMove	; Our next move
			ranges		; The patterns
		)

		
		(cond
			; Hardwired first move
			((null whiteOurLastMove)
				(setf tempCoord (round (/ *size* 2)))
				(if (eq *empty* (aref board tempCoord tempCoord))
					(setf nextMove (make-whiteCoord :x tempCoord :y tempCoord))
					(setf nextMove (make-whiteCoord :x (+ 1 tempCoord) :y (+ 1 tempCoord)))	
				)
			)
			(t
				;Search whole map for the opponents last move
				(setf lastMove (whiteFullBoardDiff board *whiteOffenseMap*))
				(setf whiteTheirLastMove lastMove)
				
				;Updates the maps with the opponent's move
				(setf (aref *whiteDefenseMap* (whiteCoord-x lastMove) (whiteCoord-Y lastMove)) *black*)
				(setf (aref *whiteOffenseMap* (whiteCoord-x lastMove) (whiteCoord-Y lastMove)) *black*)
				
				(setf ranges (whitePatternSearch (whiteCoord-x lastMove) (whiteCoord-Y lastMove) *whiteOffenseMap* *black*))
				
				(whiteEvaluatePatterns *whiteDefenseMap* ranges)

				;Choose our move
				(setf nextMove (whiteMiniMax *whiteOffenseMap* *whiteDefenseMap* *white*))
			)
		)
					
			
		; Creates a list to store ranges
		(setf ranges (list))
		

		;Update the influence maps again for our move
		
		(setf (aref *whiteDefenseMap* (whiteCoord-x nextMove) (whiteCoord-Y nextMove)) *white*)
		(setf (aref *whiteOffenseMap* (whiteCoord-x nextMove) (whiteCoord-Y nextMove)) *white*)
		

		; Finds patterns
		(setf ranges (whitePatternSearch (whiteCoord-x nextMove) (whiteCoord-Y nextMove) *whiteOffenseMap* *white*))
		

		; Evaluates patterns
		(whiteEvaluatePatterns *whiteOffenseMap* ranges)
		

		; Sends back our move
		(setf whiteOurLastMove nextMove)
		
		; Returns our move as a list
		(list (whiteCoord-x nextMove) (whiteCoord-Y nextMove))	

	)	
)


;-----------------------------------------------------
; whiteMiniMax
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
; color:			The color of the player 
;-----------------------------------------------------
; This function uses minimax and alpha-beta pruning to
; determine our best move to make.
;------------------------------------------------------
(defun whiteMiniMax (offMap defMap color)
	(let
		(
			v		; The value and the coordinate of the best move to make
		)
		

		
		(setf v (whiteMax-value offMap defMap color 0 (make-whiteCoordVal :value whiteNegativeInfinity) (make-whiteCoordVal :value whitePositiveInfinity)))
		
		;Return coord with value v
		(whiteCoordVal-coord v)
	)
)

;-----------------------------------------------------
; whiteMax-value
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
; color:			The color of the player 
; depth:		The depth that we are searching to
; alpha:		The value of the best alternative for max	
; beta:			The value of the best alternative for min
;-----------------------------------------------------
; This function is part of minimax and determines the best
; move for our player to make.
;------------------------------------------------------
(defun whiteMax-value (offMap defMap color depth alpha beta)
	(let
		(
			v		; The value and the coordinate of the best move to make
			tempCoordVal	; Temporary CoordVal variable
			ranges		; The patterns found
			moves		; The best moves that were generated by getBestMoves
		)
		

		
		(cond
			; Checks terminal test
			; Returns utility of the board
			((whiteTerminal offMap defMap depth)		
				(setf v (make-whiteCoordVal :value (whiteUtility offMap defMap color)))	;;return utility of the board
			)
		
			; If the terminal function didn't evaluate to true
			(t
				(setf v (make-whiteCoordVal :value whiteNegativeInfinity))
				
				(setf moves (whiteGetBestMoves offMap defMap)) ;Get our move list
			
				(if (null (aref moves 0 0))
					(return-from whiteMax-value (make-whiteCoordVal :value (whiteUtility offMap defMap color)))
				)
				
				;For Each Child
				(dotimes(i WHITE_BRANCHING_FACTOR)
				
					(if (null (aref moves i 0))
						(return-from whiteMax-value v)
					)
				
	
					(setf ranges (whiteCreateSuccessor offMap defmap color (aref moves i 0)))	;;Modifys infMaps
	
					;Get the advantage of this move
					(setf tempCoordVal (whiteMin-value offMap defMap color (+ 1 depth) alpha beta))
					
					
					
					;If this move is better than our current best store it's coordinates and value
					(cond
						((> (whiteCoordVal-value tempCoordVal) (whiteCoordVal-value v))
							(setf (whiteCoordVal-value v) (whiteCoordVal-value tempCoordVal))		
							;ensure this copies values and is not a "by reference"
							(setf (whiteCoordVal-coord v) (aref moves i 0))
						)
					)
					
					; Removes the move that we add to our influence maps previously
					(whiteReverseSuccessor offMap defMap color (aref moves i 0) (aref moves i 1) (aref moves i 2) ranges)
					

					

					(if (>= (whiteCoordVal-value v) (whiteCoordVal-value beta))
						(return-from whiteMax-value v)
					)
					
					(if (> (whiteCoordVal-value alpha) (whiteCoordVal-value v))
						(setf alpha v)
					)

				)
			)
		)
		
		v
	)
)

;-----------------------------------------------------
; whiteMin-value
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
; color:			The color of the player 
; depth:		The depth that we are searching to
; alpha:		The value of the best alternative for max	
; beta:			The value of the best alternative for min
;-----------------------------------------------------
; This function is part of minimax and determines the best
; move for the opponent to make.
;------------------------------------------------------
(defun whiteMin-value (offMap defMap color depth  alpha beta)
	(let
		(
			v		; The value and the coordinate of the best move to make
			tempCoordVal	; Temporary CoordVal variable
			ranges		; The patterns found
			moves		; The best moves that were generated by getBestMoves
		)
		

		
		(cond
			; Checks terminal test
			; Returns utility of the board
			((whiteTerminal offMap defMap depth)		
			
				(setf v (make-whiteCoordVal :value (whiteUtility offMap defMap color)))		;;return utility of the board
			)

			; If the terminal function didn't evaluate to true
			(t
				(setf v (make-whiteCoordVal :value whitePositiveInfinity))
				
		
				(setf moves (whiteGetBestMoves defMap offMap)) ;Get our move list	

				(if (null (aref moves 0 0))
					(return-from whiteMin-value (make-whiteCoordVal :value (whiteUtility offMap defMap color)))
				)				
								
				;For Each Child
				(dotimes(i WHITE_BRANCHING_FACTOR)
					
					(if (null (aref moves i 0))
						(return-from whiteMin-value v)
					)
					
					;;Modifys infMaps and returns the ranges found 
					(setf ranges (whiteCreateSuccessor offMap defmap (whiteOppColor color) (aref moves i 0)))	
					

					
					;Get the advantage of this move
					(setf tempCoordVal (whiteMax-value offMap defMap color (+ 1 depth) alpha beta))
					
					;If this move is better than our current best store it's coordinates and value
					(cond
						((< (whiteCoordVal-value tempCoordVal) (whiteCoordVal-value v))
							;ensure this copies values and is not a "by reference"
							(setf (whiteCoordVal-value v) (whiteCoordVal-value tempCoordVal))		
							(setf (whiteCoordVal-coord v) (aref moves i 0))
						)
						
					)
					
					; Removes the move that we add to our influence maps previously
					(whiteReverseSuccessor defMap offMap (whiteOppColor color) (aref moves i 0) (aref moves i 1) (aref moves i 2) ranges)
					

					(if (<= (whiteCoordVal-value v) (whiteCoordVal-value alpha))
						(return-from whiteMin-value v)
					)
					
					(if (< (whiteCoordVal-value beta) (whiteCoordVal-value v))
						(setf beta v)
					)
					
					
				)
			)
		)
		
		v
	)
)

;-----------------------------------------------------
; whiteOppColor
;----------------------------------------------------
; color:		The color of the player 
;-----------------------------------------------------
; This function takes in a color and returns the opposite
; color.
;------------------------------------------------------
(defun whiteOppColor (color)
	(if (equal color *black*)
		*white*
		*black*
	)
)


;-----------------------------------------------------
; whiteCreateSuccessor
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
; color:		The color of the player 
; move:			The move
;-----------------------------------------------------
; This function creates the succesors for move passed in.
; It returns all the patterns that result from the move
;------------------------------------------------------
(defun whiteCreateSuccessor (offMap defMap color move)
	(let
		(
			ranges		; The patterns made by the move
		)	
		
		; Place stone on influence maps
		(setf (aref offMap (whiteCoord-x move) (whiteCoord-y move)) color)
		(setf (aref defMap (whiteCoord-x move) (whiteCoord-y move)) color)
		
		;Find patterns from move
		(setf ranges (whitePatternSearch (whiteCoord-x move) (whiteCoord-y move) offMap color))	;The map fed to patternSearch is only for reference (i.e. it doesn't matter which goes in)
			
		;Evaluate patterns
		(if (equal color *white*)								
			(whiteEvaluatePatterns *whiteOffenseMap* ranges)	
			(whiteEvaluatePatterns *whiteDefenseMap* ranges)
		)
		
		
		;return ranges
		ranges
	)
)

;-----------------------------------------------------
; whiteReverseSuccessor
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
; color:		The color of the player 
; move:			The move to be reversed
; moveValueOff:		The original value of the move on the offensive map
; moveValueDef:		The original value of the move on the defensive map
; ranges:		The patterns that were created by the move
;-----------------------------------------------------
; This function is used to remove a move from the maps
; and set the maps back to their original values before
; the move was map
;------------------------------------------------------
(defun whiteReverseSuccessor (offMap defMap color move moveValueOff moveValueDef ranges)

	;reverse influense patterns from that stone
	(if (equal color *white*)								
		(whiteEvaluatePatterns *whiteOffenseMap* ranges t)	
		(whiteEvaluatePatterns *whiteDefenseMap* ranges t)
	)
	
	;replace stone on both maps with moveValue
	(setf (aref offMap (whiteCoord-x move) (whiteCoord-y move)) moveValueOff)
	(setf (aref defMap (whiteCoord-x move) (whiteCoord-y move)) moveValueDef)
)

;-----------------------------------------------------
; whiteTerminal
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
; depth:		The depth that we are searching to
;-----------------------------------------------------
; This function is part of minimax and determines if
; the search is finished.
;------------------------------------------------------
(defun whiteTerminal (offMap defMap depth)
	(let 
		(
			(result nil)		; If the search is over or not
		)
		
		; Checks if the depth limit was reached
		(if (> depth WHITE_DEPTH_LIMIT)
			(setf result t)
		)
		
		; Checks if their is a winner (we won)
		(if (listp (aref offMap 0 0))	;Check for a list in [0,0]. If one exists then the owner of the influencemap has 5 in 							a row
			(setf result t)
		)
		
		; Checks if their is a winner (opponent won)
		(if (listp (aref defMap 0 0))
			(setf result t)
		)
	
		result
	)
)

;-----------------------------------------------------
; whiteUtility
;----------------------------------------------------
; offMap:		The offensive influence map
; defMap:		The defensive influence map
; color:		The color of the player 
;-----------------------------------------------------
; This function is part of minimax and determines the 
; utility of the game based on the influence maps.
;------------------------------------------------------
(defun whiteUtility (offMap defMap color)
	(let
		(
			resultVal		; The total value of the board
			moves			; The best moves
			(offensiveTotal 0)	; The offensive total
			(defensiveTotal 0)	; The defensive total
			
		)
			

		; Find the greatest pattern value on the board (5INAROW being greatest)
		(cond
			((listp (aref offMap 0 0))
				(setf resultVal 5INAROW)
			)
			((listp (aref defMap 0 0))
				(setf resultVal (* -1 5INAROW))
			)
			(t	

				;Call getBestMoves
				(if (equal color *white*)	
					(setf moves (whiteGetBestMoves offMap defMap))
					(setf moves (whiteGetBestMoves defMap offMap))
				)
				
				(dotimes(i WHITE_BRANCHING_FACTOR)
				
					(if (null (aref moves i 0))
						(return-from whiteUtility (- offensiveTotal defensiveTotal))
					)

					;Utility = offensiveValue - defensiveValue
					(if (> (aref moves i 1) (aref moves i 2))	;if offensive value is greater than defensive value
						(setf offensiveTotal (+ offensiveTotal (aref moves i 1)))
						(setf defensiveTotal (+ defensiveTotal (aref moves i 2)))	
					)
					
					
				)
				
				(setf resultVal (- offensiveTotal defensiveTotal))
			)
		)
		resultVal
	)
)