;----------------------------------------------------
;		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 blackPositiveInfinity 1e10)	; Positive Infinity
(defconstant blackNegativeInfinity -1e10)	; Negative Infinity


(defconstant BLACK_BRANCHING_FACTOR 3)	;The size of the array that holds the best moves; Also the branching factor	
(defconstant BLACK_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 blackCoord
	x
	y
)

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

; A structure that models the range of a pattern
(defstruct blackRange
	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 *blackOffenseMap* (make-array `(,*size* ,*size*) :initial-element 0))
; A 2D array that maps the pattern values for the defense
(defvar *blackDefenseMap* (make-array `(,*size* ,*size*) :initial-element 0))


; The last move our player made
(defvar blackOurLastMove nil)
; The last move the other player made
(defvar blackTheirLastMove nil)




;-----------------------------------------------------
; blackEvaluatePatterns
;----------------------------------------------------
; 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 blackEvaluatePatterns (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 (blackGetPatternValue pattern))

			
			(cond
				((= (blackRange-len pattern) (blackRange-stoneNumber pattern))
				
					;Solid Pattern
					(dotimes (i 1)
						
	
						; Sets the Map Values
						(setf xincrement (* (+ 1 i) (blackRange-x-inc pattern)))
						(setf yincrement (* (+ 1 i) (blackRange-y-inc pattern)))
						
						; Sets the increasing side
						(cond
							((not (equal (logand (blackRange-blockNumber pattern) #b01) 1))			
								(setf xpos (+ xincrement (blackRange-x1 pattern)))
								(setf ypos (+ yincrement (blackRange-y1 pattern)))
								
								;;We need to check for stones here. An error will occur if we try to add patternValue to a stone. 
								(if (and (blackInBoard 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 (blackRange-blockNumber pattern) #b10) 2))				
								(setf xpos (+ (* -1 xincrement) (blackRange-x2 pattern)))
								(setf ypos (+ (* -1 yincrement) (blackRange-y2 pattern)))
								
								;;We need to check for stones here. An error will occur if we try to add patternValue to a stone. 
								(if (and (blackInBoard 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 (blackRange-x1 pattern))
					(setf ypos (blackRange-y1 pattern))

					(dotimes (i (blackRange-len pattern))
						(cond
							((and (blackInBoard 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 (blackRange-x-inc pattern) ))
						(setf ypos (- ypos (blackRange-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))
				)
			)
			
		)
	)
)

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



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

;-----------------------------------------------------
; blackPatternSearch
;----------------------------------------------------
; 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 blackPatternSearch (x y infMap color)
		(blackPatternFindLine x y 0 1 infMap color 
		(blackPatternFindLine x y 1 0 infMap color 
		(blackPatternFindLine x y 1 1 infMap color 
		(blackPatternFindLine x y -1 1 infMap color))))
)

;-----------------------------------------------------
; blackPatternFindLine
;----------------------------------------------------
; 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 blackPatternFindLine(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-blackRange :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 (blackGetPatternChar x y x-inc y-inc i 1 infMap color newRange))
				)
			)		
			
			(cond 
				((equal movingRight t)

					; Moves along the decreasing side
					(setf movingRight (blackGetPatternChar x y x-inc y-inc i -1 infMap color newRange))
				)
			)
		
			
		)
		
		;;Calculate distance between (x1,y1) and (x2,y2) to help identify split patterns		


	
		; Calculate the length of the pattern
		(setf (blackRange-len newRange) (+ 1 (max (abs (- (blackRange-x1 newRange) (blackRange-x2 newRange))) (abs (- (blackRange-y1 newRange) (blackRange-y2 newRange))))))
		
	
		; Adds pattern to the list
		(cond
			 ((>= (blackRange-len newRange) 6)
				
				
		
				; There  are two patterns using the origin stone
				; Split the newRange into two different patterns
				(setf newRange2 (make-blackRange :x1 (blackRange-x1 newRange) :y1 (blackRange-y1 newRange) :x2 x :y2 y :x-inc x-inc :y-inc y-inc :stoneNumber 1 :color color :blockNumber 0 :len 1))
				(setf (blackRange-len newRange2) (+ 1 (max (abs (- (blackRange-x1 newRange2) (blackRange-x2 newRange2))) (abs (- (blackRange-y1 newRange2) (blackRange-y2 newRange2))))))
				(blackStoneCount newRange2 infMap)	
				
				(setf (blackRange-x1 newRange) x)
				(setf (blackRange-y1 newRange) y)
				(setf (blackRange-len newRange) (+ 1 (max (abs (- (blackRange-x1 newRange) (blackRange-x2 newRange))) (abs (- (blackRange-y1 newRange) (blackRange-y2 newRange))))))
				(blackStoneCount newRange infMap)

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

;-----------------------------------------------------
; blackStoneCount
;----------------------------------------------------
; 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 blackStoneCount (range infMap)					
	(let
		(
			posX		; The x coord
			posY		; The y coord
		)
		
		(setf (blackRange-stoneNumber range) 1)

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

;-----------------------------------------------------
; blackGetPatternChar
;----------------------------------------------------
; 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 blackGetPatternChar (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 (blackInBoard posX posY)
			(cond 
				((equal (aref infMap posX posY) color)		
					

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

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


;-----------------------------------------------------
; blackInBoard
;----------------------------------------------------
; 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 blackInBoard (x y)
	(if (and (< x *size*) (>= x 0))
		(if (and (< y *size*) (>= y  0))
			t
		)
	)
)

;-----------------------------------------------------
; blackGetBestMoves
;----------------------------------------------------
; 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 blackGetBestMoves(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 `(,BLACK_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 BLACK_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-blackCoord :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 BLACK_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-blackCoord :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 BLACK_BRANCHING_FACTOR)
			(cond
				((not (equal (aref bestMovesArray i 0) nil))
					(setf coord (aref bestMovesArray i 0))					
					(setf x (blackCoord-x coord))
					(setf y (blackCoord-y coord))
					(setf (aref bestMovesArray i 1 ) (aref offMap x y))
					(setf (aref bestMovesArray i 2 ) (aref defMap x y))
				)
			)
		)
		
		bestMovesArray
		
	)
)

;-----------------------------------------------------
; blackFullBoardDif
;----------------------------------------------------
; board:		The board
; infMap:		A influence map
;-----------------------------------------------------
; This function helps us identify where the opponent
; put their stone. 
;------------------------------------------------------
(defun blackFullBoardDiff (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-blackCoord :x i :y j))
						)
					)
				)
			)
		)
		
		newStone
	)
)

;-----------------------------------------------------
; black-get-move
;----------------------------------------------------
; board:		The board
;-----------------------------------------------------
; This function determines which move our player will make.
;------------------------------------------------------
(defun black-get-move (board)
	(let
		(
			tempX		; A temporary var to hold an x coord
			tempY		; A temporary var to hold a y coord
			lastMove	; The opponents last move
			nextMove	; Our next move
			ranges		; The patterns
		)
		
		
		;Search whole map for the opponents last move
		(if (null lastMove)	
			(setf lastMove (blackFullBoardDiff board *blackOffenseMap*))
		)
		
		(setf blackTheirLastMove lastMove)
	
		
		; Checks to see if they made a move and if so updates the influence maps
		(cond
			((not (null lastMove))
		
				(setf (aref *blackDefenseMap* (blackCoord-x lastMove) (blackCoord-Y lastMove)) *white*)
				(setf (aref *blackOffenseMap* (blackCoord-x lastMove) (blackCoord-Y lastMove)) *white*)
				
				(setf ranges (blackPatternSearch (blackCoord-x lastMove) (blackCoord-Y lastMove) *blackOffenseMap* *white*))
				
				(blackEvaluatePatterns *blackDefenseMap* ranges)
			)
		)
		
		
		
		; Test if this is our first move. If so it moves based
		; on the opponents move. Otherwise it uses minimax to determine
		; our first move.
		(cond
			((null blackOurLastMove)
					(setf tempX (blackCoord-x lastMove))
					(setf tempY (blackCoord-y lastMove))
				(cond
					((blackInBoard (+ tempX 1)  tempY)

						(setf nextMove (make-blackCoord :x (+ tempX 1)  :y tempY))
					)
					((blackInBoard tempX  (+ tempY 1))
						(setf nextMove (make-blackCoord :x tempX  :y (+ tempY 1)))
					)
					((blackInBoard tempX  (- tempY 1))
						(setf nextMove (make-blackCoord :x tempX  :y (- tempY 1)))
					)
					((blackInBoard (- tempX 1)  tempY)
						(setf nextMove (make-blackCoord :x (- tempX 1)  :y tempY))
					)
					
				)

			)
			(t
			
				;Choose our move
				(setf nextMove (blackMiniMax *blackOffenseMap* *blackDefenseMap* *black*))

			)
		)
			
			
		; Creates a list to store ranges
		(setf ranges (list))
		

		;Update the influence maps again for our move
		(setf (aref *blackDefenseMap* (blackCoord-x nextMove) (blackCoord-Y nextMove)) *black*)
		(setf (aref *blackOffenseMap* (blackCoord-x nextMove) (blackCoord-Y nextMove)) *black*)
		

		; Finds patterns
		(setf ranges (blackPatternSearch (blackCoord-x nextMove) (blackCoord-Y nextMove) *blackOffenseMap* *black*))

		; Evaluates patterns
		(blackEvaluatePatterns *blackOffenseMap* ranges)
		
		; Sends back our move
		(setf blackOurLastMove nextMove)
		
		; Returns our move as a list
		(list (blackCoord-x nextMove) (blackCoord-Y nextMove))	

	)	
)


;-----------------------------------------------------
; blackMiniMax
;----------------------------------------------------
; 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 blackMiniMax (offMap defMap color)
	(let
		(
			v		; The value and the coordinate of the best move to make
		)
		
		
		(setf v (blackMax-value offMap defMap color 0 (make-blackCoordVal :value blackNegativeInfinity) (make-blackCoordVal :value blackPositiveInfinity)))
		
		;Return coord with value v
		(blackCoordVal-coord v)
	)
)

;-----------------------------------------------------
; blackMax-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 blackMax-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
			((blackTerminal offMap defMap depth)		
				(setf v (make-blackCoordVal :value (blackUtility offMap defMap color)))	;;return utility of the board
			)
		
			; If the terminal function didn't evaluate to true
			(t
				(setf v (make-blackCoordVal :value blackNegativeInfinity))
				

				(setf moves (blackGetBestMoves offMap defMap)) ;Get our move list
			
				(if (null (aref moves 0 0))
					(return-from blackMax-value (make-blackCoordVal :value (blackUtility offMap defMap color)))
				)
				
				;For Each Child
				(dotimes(i BLACK_BRANCHING_FACTOR)
				
					(if (null (aref moves i 0))
						(return-from blackMax-value v)
					)
				

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

					

					(if (>= (blackCoordVal-value v) (blackCoordVal-value beta))
						(return-from blackMax-value v)
					)
					
					(if (> (blackCoordVal-value alpha) (blackCoordVal-value v))
						(setf alpha v)
					)

				)
			)
		)
		
		v
	)
)

;-----------------------------------------------------
; blackMin-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 blackMin-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
			((blackTerminal offMap defMap depth)		

				(setf v (make-blackCoordVal :value (blackUtility offMap defMap color)))		;;return utility of the board
			)

			; If the terminal function didn't evaluate to true
			(t
				(setf v (make-blackCoordVal :value blackPositiveInfinity))
				

				(setf moves (blackGetBestMoves defMap offMap)) ;Get our move list
				
				(if (null (aref moves 0 0))
					(return-from blackMin-value (make-blackCoordVal :value (blackUtility offMap defMap color)))
				)


				
				;For Each Child
				(dotimes(i BLACK_BRANCHING_FACTOR)
					
					(if (null (aref moves i 0))
						(return-from blackMin-value v)
					)
					
	
					(setf ranges (blackCreateSuccessor offMap defmap (blackOppColor color) (aref moves i 0)))	;;Modifys infMaps and returns the ranges found 

					
					;Get the advantage of this move
					(setf tempCoordVal (blackMax-value offMap defMap color (+ 1 depth) alpha beta))
					
					;If this move is better than our current best store it's coordinates and value
					(cond
						((< (blackCoordVal-value tempCoordVal) (blackCoordVal-value v))
							;ensure this copies values and is not a "by reference"
							(setf (blackCoordVal-value v) (blackCoordVal-value tempCoordVal))		
							(setf (blackCoordVal-coord v) (aref moves i 0))
						)
						
					)

					; Removes the move that we add to our influence maps previously
					(blackReverseSuccessor defMap offMap (blackOppColor color) (aref moves i 0) (aref moves i 1) (aref moves i 2) ranges)
					

					(if (<= (blackCoordVal-value v) (blackCoordVal-value alpha))
						(return-from blackMin-value v)
					)
					
					(if (< (blackCoordVal-value beta) (blackCoordVal-value v))
						(setf beta v)
					)
					
					
				)
			)
		)
		
		v
	)
)

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


;-----------------------------------------------------
; blackCreateSuccessor
;----------------------------------------------------
; 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 blackCreateSuccessor (offMap defMap color move)
	(let
		(
			ranges		; The patterns made by the move
		)	
		
		; Place stone on influence maps
		(setf (aref offMap (blackCoord-x move) (blackCoord-y move)) color)
		(setf (aref defMap (blackCoord-x move) (blackCoord-y move)) color)
		
		;Find patterns from move
		(setf ranges (blackPatternSearch (blackCoord-x move) (blackCoord-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 *black*)								
			(blackEvaluatePatterns *blackOffenseMap* ranges)	
			(blackEvaluatePatterns *blackDefenseMap* ranges)
		)
		
		
		;return ranges
		ranges
	)
)

;-----------------------------------------------------
; blackReverseSuccessor
;----------------------------------------------------
; 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 blackReverseSuccessor (offMap defMap color move moveValueOff moveValueDef ranges)

	;reverse influense patterns from that stone
	(if (equal color *black*)								
		(blackEvaluatePatterns *blackOffenseMap* ranges t)	
		(blackEvaluatePatterns *blackDefenseMap* ranges t)
	)
	
	;replace stone on both maps with moveValue
	(setf (aref offMap (blackCoord-x move) (blackCoord-y move)) moveValueOff)
	(setf (aref defMap (blackCoord-x move) (blackCoord-y move)) moveValueDef)
)

;-----------------------------------------------------
; blackTerminal
;----------------------------------------------------
; 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 blackTerminal (offMap defMap depth)
	(let 
		(
			(result nil)		; If the search is over or not
		)
		
		; Checks if the depth limit was reached
		(if (> depth BLACK_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
	)
)

;-----------------------------------------------------
; blackUtility
;----------------------------------------------------
; 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 blackUtility (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 *black*)	
					(setf moves (blackGetBestMoves offMap defMap))
					(setf moves (blackGetBestMoves defMap offMap))
				)
				
				(dotimes(i BLACK_BRANCHING_FACTOR)
				
					(if (null (aref moves i 0))
						(return-from blackUtility (- 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
	)
)