HEX ---Human vs. Computer

A. Third Edition

In <The Matrix>, Morpheus said to Neo that there was a big difference between knowing the path and walking through the path.

It seems fitting this scenario. To test a solution is always much easier than finding the solution. 

Alright, here we go to walk the path!

B.The problem

-------------------------------------------------------------------------------
; Hex game playing program
;
; Authors: Milly Cow and Maud Vachon   ; <=== your names

; This program always wins             ; <=== other useful comments

(load "board")

(define ...)                           ; <=== other definitions you need

; implement the following function to make a "move" for a player:
(define (move board color)             ; board: see "board.scm",
   ...                                 ; color: #t=red, #f=blue,
)                                      ; <return> #t: win, #f: no win (continue)
--------------------------------------------------------------------------------

The difficult part is shortest path finder, as for human vs. AI interface, it is really a trivial job. And the professor is

so busy that he even doesn't bother to design such a simple interface. Probably he just searches on internet and happens to

find such a game. However, without the feature of competition against each other, the game AI is really unable to justify.

1. Approach Algorithm:

 1.1  The shortest path procedure:

a)      The approach of our program is to reduce branching factor in search as many as possible. Therefore we spend great efforts in implementing a very complicated heuristic function to give guides to our search tree. This function is very expensive as it is quite complicated. However, we think it is still worth calling it so many times because it usually will only return no more than four coordinates. (typical case is one or two.)

b)      The idea of this function is to calculate the minimum steps needed for one player to achieve goal. Or in other words, how can we find a shortest path such that red player can construct his pieces to connect top to bottom or blue player to connect left to right? Note that the shortest path can be more than one and starting from different group of same color may have different value of shortest path. The shortest path of one player is equally important for his opponent. Therefore instead of searching the union of shortest path of two players, we decide to search only the intersection of shortest path of two players because these places not only increase players winning group but also block his opponent's winning group.

c)      The implementation of "shortest path" has a time complexity of N². First we scan every place on board. There are two cases. If empty place or pieces of opponent's color, the length of shortest path is regarded as infinite. If player's piece is reached, we search shortest path by a series of expanded circles which has current piece as center. Also we use an internal board to record the distance for each coordinate. During each round searching, there are three cases. If empty place encountered, write current radius plus one to that coordinate. If opponent's color piece encountered, write infinite to that coordinate. If player's piece encountered, write previous radius to that coordinate. After finishing one round of searching, increase radius by one to search a larger circle until the expanded circle covers no place on board any more. After all places on board have been written with a distance, we search those smallest numbers on winning border of board. In red player case, they are both top and bottom sides, and in case of blue player they are left and right sides. From the set of smallest distance number, we construct the shortest path by searching grids of decreasing distance numbers. If it decrease with exact one, add that coordinate into shortest path. If it has exact same distance number but it has player's color piece, also add it into shortest path. The first scan is a linear scan of every grid of board, and the second search is also linear because it just searches in circles. And in the worst case, every place of board might be done with this kind of search. Therefore the algorithms has a time complexity of N².

d)      A more detailed analysis about "shortest path" algorithms shows that it is similar to Dijkstra algorithms which needs to update neighbor distance whenever a new distance is created. And this function can even be used to check if a winner is created when shortest path return 0 distance. Another optimizing method is that all connected pieces has same length of shortest path.

e) However, after the first testing, I found the branching factor is still very high. Then I deliberately select those points which are adjacent to current nodes. Therefore the play is proceeded more like human, at least like some of us.

1.2  The minmax procedure

a)      We define our heuristic value as the difference of length of shortest path between blue and red player. Therefore red player is the max because he wants the difference to be as big as possible. And blue player is the min player.

b)      We write two versions of minmax procedure, one has alpha-beta prune, and the other has not. By doing this we actually are able to compare performance difference between purely DFS and alpha-beta-prune. It seems the difference in average is more than 25%.

c)      However, our complicated heuristic function prevents us from searching deeper than level four.

1.3  The human vs. AI procedure

a)       As we observed, no matter how good algorithms it might be, computer against computer will usually ends up balanced play. And sometimes, it is hard to distinguish this balanced play from some naive heuristic. So, we designed a little interface to enable human vs. AI.

b)      To play it, loads the file "humanplay.scm" and run function (humanplay board). At the prompt, key in coordinate by one capital letter and one lower case letter with no space in between. The first indicates the row number and the second indicates the column number. As we are running out of time, there is no error checking in this interface so that no mistakes is tolerated.

1.4   The display board procedure

a)        As hex game is very difficult to imagine unless a beautiful display function is implemented, we implemented a nice display function to mimic the real hex game.

b)        In order for input for human vs. AI, letter coordinates are added.

D.The major functions

My friend asks me how to play it and it is quite a hard question for my bad memory because I almost totally forget what I have learned. Bit 

by bit, my memory recovers and in case I lose them in future let me write down:

1. computer mode (AI vs. AI):

At prompt of "gambit", type

(load "board.scm)

(play board)

2. Human mode (Human vs. AI):

At prompt of "gambit", type

(load "humanplay.scm)

(humanplay board)

E.Further improvement

When a Scheme program is more than five hundred lines or more, it is much difficult to debug. 

F.File listing

1. shortestpath.scm

2. board.scm (given by professor)

3. displayboard.scm (by Alejandro)

4. moveboard.scm

5. alpha-beta.scm

6. humanplay.scm

file name: shortestpath.scm

(load "board.scm")
(load "displayboard.scm")
(define n_infinite 1000)
;(define n_currentLength n_infinite)

(define n_row0	(vector 'E 'E 'E 'E 'E 'E 'E 'E 'E 'E 'E))
(define n_row1	(vector 'E 'E 'E 'E 'E 'R 'B 'E 'E 'E 'E))
(define n_row2	(vector 'E 'E 'E 'E 'E 'R 'B 'E 'E 'E 'E))
(define n_row3	(vector 'E 'E 'E 'E 'E 'R 'B 'E 'E 'E 'E))
(define n_row4	(vector 'E 'E 'E 'E 'E 'R 'B 'E 'E 'E 'E))
(define n_row5	(vector 'E 'E 'E 'E 'E 'R 'E 'E 'E 'E 'E))
(define n_row6	(vector 'E 'E 'E 'E 'R 'B 'E 'E 'E 'E 'E))
(define n_row7	(vector 'E 'E 'E 'E 'R 'B 'E 'E 'E 'E 'E))
(define n_row8	(vector 'E 'E 'E 'B 'R 'E 'E 'E 'E 'E 'E))
(define n_row9	(vector 'E 'E 'E 'B 'R 'E 'E 'E 'E 'E 'E))
(define n_row10	(vector 'E 'E 'E 'B 'R 'E 'E 'E 'E 'E 'E))

(define n_board	(vector n_row0 n_row1 n_row2 n_row3 n_row4 n_row5 n_row6 n_row7 n_row8 n_row9 n_row10))
(define n_board 
'#(#(E E E E E E E E E E E)
   #(E E E E E E E E E E E)
   #(E E E E E E E E E E E)
   #(E E E E E E E E E E E)
   #(E E E E E E E E E E E)
   #(E E E E E R E E E E E)
   #(E E E E E E E E E E E)
   #(E E E E E B E E E E E)
   #(E E E E E E E E E E E)
   #(E E E E E E E E E E E)
   #(E E E E E E E E E E E)))

(define n_flagBoard (make-vector board-size))

(define n_createFlagBoard 
	(lambda ()
		(let loop ((r 0)(c 0)(v (make-vector board-size)))
			(if (< r board-size)
				(begin
					(if (= c board-size)
						(begin
							(vector-set! n_flagBoard r v)
							(set! r (+ r 1))
							(set! c 0)
							(set! v (make-vector board-size))
						)
					)
					(vector-set! v c #f)
					(loop r (+ c 1) v)
				)
			)
		)
	)
)

(define n_myboard (make-vector board-size))

(define n_dodisplayboard
	(lambda (ls)		
		(if (not (null? ls))
			(begin 
				(pp (vector->list (car ls)))
				;(pp "\n")
				(n_dodisplayboard (cdr ls))
			)
		)
	)
)
	

(define n_displayboard
	(lambda (v)
		(n_dodisplayboard (vector->list v))
	)
)

;(define n_vectorset
;	(lambda (vv r c value)
;		(vector-set! (eval 'quote(vector-ref vv r)) c value)
;	)
;)		
	
(define n_vectorRefGet
	(lambda (vv r c)
		(vector-ref (vector-ref vv r) c)
	)
)
(define n_vectorRefSet
	(lambda (vv r c value)
		(vector-set! (vector-ref vv r) c value)
	)
)

(define n_doListGet
	(lambda (ls index)
		(if (= index 0)
			(car ls)
			(n_doListGet (cdr ls)(- index 1))
		)
	)
)

(define n_doVectorGet
	(lambda (v index)
		(n_doListGet (vector->list v) index)
	)
)

(define n_vectorget
	(lambda (vv r c)
		(n_doVectorGet (n_doVectorGet  vv r) c)
	)
)

(define n_doListSet
	(lambda (ls index value)
		(if (= index 0)
			(cons value (cdr ls))
			(cons (car ls)(n_doListSet (cdr ls)(- index 1) value))
		)
	)
)

(define n_doVectorSet
	(lambda (v index value)
		(list->vector (n_doListSet (vector->list v) index value))
	)
)


(define n_vectorset
	(lambda (vv r c value)
		(n_doVectorSet vv r (n_doVectorSet (n_doVectorGet vv r) c value))
	)
)

(define n_doVectorCopy
	(lambda (v)
		(list->vector (n_doListCopy (vector->list v)))
	)
)

(define n_doListCopy
	(lambda (ls)
		(if (null? ls)
			'()
			(cons (car ls)(n_doListCopy (cdr ls)))
		)
	)
)

(define n_vectorCopyHelper
	(lambda (ls)
		(if (null? ls)
			'()
			(cons (n_doVectorCopy (car ls)) (n_vectorCopyHelper (cdr ls)))
		)
	)
)

(define n_vectorCopy
	(lambda (vv)
		(list->vector (n_vectorCopyHelper (vector->list vv)))
	)
)	 


;(define n_vectorget
;	(lambda (vv r c)
;		(vector-ref (vector-ref vv r) c)
;	)
;)

;(define n_vectorset
;	(lambda (vv r c value)
;		(vector-set! (vector-ref vv r) c value)
;	)
;)


(define n_sameColor
	(lambda (board color row col)
		(or (and color (eq? (n_vectorget board row col) 'R))
		    (and (not color)(eq? (n_vectorget board row col) 'B))
		)
	)
)

(define n_otherColor
	(lambda (board color row col)
		(or (and color (eq? (n_vectorget board row col) 'B))
		    (and (not color)(eq? (n_vectorget board row col) 'R))
		)
	)
)

(define n_emptyColor
	(lambda (board color row col)
		(eq? (n_vectorget board row col) 'E)
	)
)

(define n_addPath
	(lambda (row col path)
		(cons (cons row col) path)
	)
)

(define n_inPath
	(lambda (row col path)
		(if (null? path)
			#f
			(if (and (= row (car (car path)))(= col (cdr (car path))))
				#t
				(n_inPath row col (cdr path))
			)
		)
	)
)

(define n_addUnique
	(lambda (x ls)
		(if (null? ls)
			(list x)
			(if (equal? x (car ls))
				ls
				(cons (car ls)(n_addUnique x (cdr ls)))
			)
		)
	)
)

(define n_mergePath
	(lambda (ls1 ls2)
		(if (null? ls1)
			ls2
			(n_mergePath (cdr ls1) (n_addUnique (car ls1) ls2))
		)
	)
)

(define n_findMin
	(lambda (temp ls)
		(begin (pp(list "n_findmin temp=" temp "ls=" ls))
		(if (null? ls)
			temp
			(if (< (car (car ls))(car temp))
				(n_findMin (car ls)(cdr ls))
				(if (= (car temp)(car (car ls)))
					(n_findMin (cons (car temp) (n_mergePath (cdr temp)(cdr (car ls)))) (cdr ls))
					(n_findMin temp (cdr ls))
				)
			)
		))
	)
)

(define n_filterList
	(lambda (board color ls)
		(if (null? ls)
			'()
			(if (n_sameColor board color (car (car ls)) (cdr (car ls)))
				(n_filterList board color (cdr ls))
				(cons (car ls)(n_filterList board color (cdr ls)))
				
			)
		)		
	)
)

;(define n_doVectorCopy
;	(lambda (ls)
;		(if (null? ls)
;			'()
;			(cons (car ls)(n_doVectorCopy (cdr ls)))
;		)
;	)
;)


;(define n_vectorCopy
;	(lambda (vv)
;		(list->vector (n_doVectorCopy (vector->list vv)))
;	)
;)

;*****************************ALEX'S EDIT
;(define n_vectorCopy
;	(lambda (vv)
;		(define ls (eval (list 'quote (vector->list vv))))
;		(list->vector m)	
;	)
;)

(define n_inBoard
	(lambda (row col)
		(and (>= row 0)(>= col 0)(< row board-size)(< col board-size))
	)
)

(define n_doPaintPath
	(lambda (path myboard)
		(if (not (null? path))
			(let ((row (car (car path)))(col (cdr (car path))))
				(n_doPaintPath (cdr path) (n_vectorset myboard row col '*))
			)
			myboard
		)
	)
)

(define n_paintPath
	(lambda (path)
		(n_doPaintPath  path n_board)
	)
)
	
(define n_testElement
	(lambda (x ls)
		(if (null? ls)
			#f
			(if (equal? x (car ls))
				#t
				(n_testElement x (cdr ls))
			)
		)
	)
)

(define n_testList
	(lambda (ls1 ls2)
		(if (null? ls1)
			'()
			(if (n_testElement (car ls1) ls2)
				(cons (car ls1) (n_testList (cdr ls1) ls2))
				(n_testList (cdr ls1) ls2)
			)
		)
	)
)

(define n_unionPath
	(lambda (ls1 ls2)
		(let ((result (n_testList ls1 ls2)))
			(if (null? result)
				(append ls1 ls2)
				result
			)
		)
	)
)	
				
(define n_hasBothColorNeighbour
	(lambda (board color row col)
		(let f ((path (n_allNeighbours row col)))
			(if (null? path)
				#f
				(if (not (n_emptyColor board color (car (car path))(cdr (car path))))
					#t
					(f (cdr path))
				)
			)
		)
	)
)

;;testing conditions
(define n_doHasConnection
	(lambda (board color row col ls)
		(if (or (not (n_sameColor board color row col)) (n_inPath row col ls))
			#f
			(if (n_vectorRefGet n_flagBoard row col)
				#t
				(n_hasConnection board color row col ls)
			)
		)
	)
)
			

(define n_hasConnection
	(lambda (board color row col ls)
		(let loop ((path (n_allNeighbours row col)))
			(if (null? path)
				#f; which means no connection
				(let ((r (car (car path)))(c (cdr (car path))))
					(if (n_doHasConnection board color r c (n_addUnique (cons row col) ls))
						#t
						(loop (cdr path))
					)
				)
			)
		)
	)
)		
		


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;       above this line are all general utility functions                                 ;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; first we need to search entire board and pinpoint the group of color
;; then we compare among groups to find the shortest path
;; the following are big board search and comparison
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; this is the entry point
; do while loop for each position on board
; scan all position and generate shortest path for each position
; compare and take the shortest
(define ShortestPath
	(lambda (board color)
		(n_createFlagBoard)
		(let f ((row 0)(col 0)(length n_infinite)(retList '()))
			(if (= row board-size)
				(cons length (n_filterList board color retList))
				(let ((newList (n_findPath board color row col length retList)))
					(n_vectorRefSet n_flagBoard row col #t)
					(if (< col (- board-size 1))
						(f row (+ col 1) (car newList)(cdr newList))
						(f (+ row 1) 0 (car newList)(cdr newList))
					)
				)
			)
		)
	)
)


; first search if it starts with a matching color
; two situations:
; if same color, begin searching for shortest, and MUST copy board for parameter
; if other color or empty, just return
(define n_findPath
	(lambda (board color row col length retList)
		(if (and (n_sameColor board color row col)(not(n_hasConnection board color row col '())))
		;(if (n_sameColor board color row col);;only for testing optimizing
			(begin				
				(let ((result (n_doFindPath board color row col)))	
					(if (< (car result) length)
						(begin
							;(set! n_currentLength (car result))
							result   ;return new
						)
						(if (= (car result) length)
							(cons length (n_mergePath (cdr result) retList)) ; add new
							(cons length retList) ; return old 
						)
					)
				)
			)
			(cons length retList);simply return as no matching
		)
	)
)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; the following is detail how to find one shortest path for one particular
;;; starting point, provided it is same color. for one group of nodes, we 
;;; might waste time for repeating, but I don't see any better way
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; it searches in a series of circles which have row col as center and 
;; radius is distance which increases one by each time
;; it returns by calling n_findShortestWrapper which will retrieve information
;; from myboard and generate path list
(define n_doFindPath 
	(lambda (board color row col)
		(set! n_myboard (n_vectorCopy board)) ;(n_vectorCopy board))
		(let f ((distance 0))   ;(myboard n_myboard))			
			(let ((path (n_generateList row col distance)))
				(if (null? path)
					; this is the return which means you need to generate the path from charted board
					(n_findShortestWrapper board color row col n_myboard) ;;debugging
					;n_myboard ;;debugging
					(begin
						(if (= distance 0)
							(set! n_myboard (n_vectorset n_myboard row col 0))
							(n_updateBoard board color path)											
						)
						;(pp (list "n_doFindPath board=" board "myboard=" n_myboard))
						(f (+ distance 1))
					)
				)				
			)
		)	
	)
)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; first job is to generate the charted board by searching its neighbour and retrieve the
;; smallest distance, if current node is same color, teleport; if current is empty color,
;; walk by plus one; if current node is other color, ignore
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define n_updateBoard 
	(lambda (board color path)
		(begin ;(pp(list "n_updateBoard board=" board "myboard=" myboard))
		(if (not (null? path))			
			(let ((row (car (car path)))(col (cdr (car path))))	
				(if (n_sameColor board color row col) 
					(set! n_myboard (n_vectorset n_myboard row col (n_shortestNeighbour n_myboard row col )))
				)
				(if (n_emptyColor board color row col)
					(set! n_myboard (n_vectorset n_myboard row col (+ 1 (n_shortestNeighbour n_myboard row col))))
				)		
				(if (not (n_otherColor board color row col))				
					; it is possible you need to update your neighbour
					(n_updateNeighbour board color row col)						
					
				)				
				(n_updateBoard board color (cdr path))
			)
		))
	)
)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; self-explained: other-color nodes returns infinite
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define n_shortestNeighbour
	(lambda (myboard row col)
		(let f ((path (n_allNeighbours row col))(result n_infinite))
			(if (null? path)
				result
				(begin
					(set! result (min result (n_getNeighbourValue n_myboard (car (car path))(cdr (car path)))))
					(f (cdr path) result)
				)
			)	
		)
	)
)
	
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; the reason for updating neighbour is exactly like Dijkstra algorithms
;; you might need to adjust old value when you discover new value
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define n_updateNeighbour
	(lambda (board color row col)
		(let f ((ls (n_allNeighbours row col))(value (n_vectorget n_myboard row col)))
			(if (not (null? ls))
				(begin
					(let ((r (car (car ls)))(c (cdr (car ls))))
						; the fist case is the same color different value
						(if (and (n_sameColor board color row col)(n_sameColor board color r c)
							(integer? (n_vectorget n_myboard r c))(> (n_vectorget n_myboard r c) value))
								(set! n_myboard (n_vectorset n_myboard r c value))
						)
						; the second case is that no neighbour can be bigger more than 1
						(if (and (not (n_otherColor board color r c)) (integer? (n_vectorget n_myboard r c))
								(> (n_vectorget n_myboard r c)(+ value 1)))
							(set! n_myboard (n_vectorset n_myboard r c (+ value 1)))
						)
						(f (cdr ls) value)
					)
				)
			)
		)
	)
)
				

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; this is the second big job, that is, after you created the charted board, how do you
;; generate shortest path from this board? 
;; first you find the sets of smallest distance at both borders (up-down for red, left-right
;; for blue) , then you backtrack path starting from these nodes.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; n_findshortest only retrieves set of positions of smallest distance
; at border, it passes this list as starting point for n_doFindShortest
(define n_findShortestWrapper
	(lambda (board color row col myboard)
		(let ((path (n_findShortest board color row col myboard)))
			(let f ((ls (cdr path))(length (car path))(result '()))
				(if (null? ls)
					(cons length result)
					(begin
						(set! result (n_doFindShortest board color myboard result (car (car ls))(cdr (car ls)) ) )
						(f (cdr ls) length result)
					)
				)
			)
		)
	)
)



; collect all smallest length from border
; this is a function to retrieve shortest path from charted board----myboard
; which has been full of distance from started "row col".
; it searches all TWO borders to find the "set" of positions of smallest distances
; 			
(define n_findShortest 
	(lambda (board color row col myboard)
		(let f ((firstrow 0)(firstcol 0)(secondrow (- board-size 1))(secondcol (- board-size 1))
				(firstresult '())(secondresult '())(firstlength n_infinite)(secondlength n_infinite))
			(if (or (and color (= firstcol board-size)) (and (not color)(= firstrow board-size)))
				(cons (+ firstlength secondlength)(n_mergePath firstresult secondresult))
				;;else 
				(begin ;(pp (list "n_findShortest firstrow=" firstrow "firstcol=" firstcol "firstlength=" firstlength))
				(let ((result0 (n_getNeighbourValue myboard firstrow firstcol))
						(result1 (n_getNeighbourValue myboard secondrow secondcol)))
					(if (< result0 firstlength)
						(begin
							(set! firstresult (list (cons firstrow firstcol)))
							(set! firstlength result0)
						)
						(if (= result0 firstlength)
							(set! firstresult (n_addPath firstrow firstcol firstresult))
						)
					)
					(if (< result1 secondlength)
						(begin
							(set! secondresult (list (cons secondrow secondcol)))
							(set! secondlength result1)
						)
						(if (= result1 secondlength)
							(set! secondresult (n_addPath secondrow secondcol secondresult))
						)
					)
					(if color
						(f firstrow (+ firstcol 1) secondrow (- secondcol 1) firstresult secondresult firstlength secondlength)
						(f (+ firstrow 1) firstcol (- secondrow 1) secondcol firstresult secondresult firstlength secondlength)
					)
				))
			)
		
		)
	)
)

;; recursively add neighbour nodes into path by either of two conditions:
;; 1. neighbour with same distance
;; 2. neighbour with distance of exact less one provided either neighbour or the node itself is
;;		the color it is searching for
;;  and it returns the path
(define n_doFindShortest
	(lambda (board color myboard oldPath row col)	
		;(begin ;(pp(list "n_doFindShortest oldpath=" oldPath ))
		(let f ((ls (n_allNeighbours row col))(path (n_addPath row col oldPath)))
			(if (not (null? ls))
				(let ((r (car (car ls)))(c (cdr (car ls))))
					(if (and 
							;; cannot be the one you already searched
							(not (n_inPath r c path)) 
							(or 
								;;there are two cases:
								;;first it must be exact same distance
								(and 
									(integer? (n_vectorget myboard r c))
									(integer? (n_vectorget myboard row col))
									(= (- (n_vectorget myboard row col) 1)(n_vectorget myboard r c))
								)
								;;second case is that you have exact less one distance
								;; but either neighbor or itself must be the same color of player
								(and  
									(or (n_sameColor board color r c)
										(n_sameColor board color row col)
									)
									(integer? (n_vectorget myboard row col))
									(integer? (n_vectorget myboard r c))
									(=  (n_vectorget myboard row col) (n_vectorget myboard r c)) 
								)														
							)
						)
						;(pp (list board color myboard path r c))
						;(pp (n_doFindShortest board color myboard path r c))						
						(set! path (n_doFindShortest board color myboard path r c))						
					)
					(f (cdr ls) path)
				)
				; if no more neighbour can be generated
				path
			)
		);)					
	)
) 


;;clockwise counting
(define n_checkAndAddPath 
	(lambda (row col distance count result)
		(if (n_inBoard (+ row distance) (- col count))		
			(set! result (n_addPath (+ row distance) (- col count) result))
		)
		(if (n_inBoard (- row distance)(+ col count))
			(set! result (n_addPath (- row distance)(+ col count) result))
		)
		(if (n_inBoard (- (+ row distance) count)(- col distance))
			(set! result (n_addPath (- (+ row distance) count) (- col distance) result))
		)
		(if (n_inBoard (+ (- row distance) count) (+ col distance))
			(set! result (n_addPath (+ (- row distance) count) (+ col distance) result))
		)
		(if (n_inBoard (+ row count) (- (+ col distance) count))
			(set! result (n_addPath (+ row count) (- (+ col distance) count) result))
		)
		(if (n_inBoard (- row count) (+ (- col distance) count))
			(set! result (n_addPath (- row count) (+ (- col distance) count) result))
		)
		result
	)
)


(define n_generateList
	(lambda (row col distance)
		(if (= distance 0)
			(list (cons row col))
			(let f ((count 0)(result '()))
				(if (= count distance)
					result
					(begin
						(set! result (n_checkAndAddPath row col distance count result))
						(f (+ count 1) result)
					)
				)
			)
		)
	)
)

(define n_getNeighbourValue
	(lambda (myboard row col)
		(if (n_inBoard row col)
			(let ((result (n_vectorget myboard row col)))
				(if (integer? result)
					result
					n_infinite
				)
			)
			n_infinite
		)
	)
)

(define n_allNeighbours
	(lambda (row col)
		(n_generateList row col 1)
	)
)

;(define n_allNeighbours
;	(lambda (row col)
;		(let ((result '()))
;			(if (n_inBoard row (+ col 1))
;				(set! result (n_addPath row (+ col 1) result))
;			)
;			(if (n_inBoard row (- col 1))
;				(set! result (n_addPath row (- col 1) result))
;			)
;			(if (n_inBoard (+ row 1) col)
;				(set! result (n_addPath (+ row 1) col result))
;			)
;			(if (n_inBoard (- row 1) col)
;				(set! result (n_addPath (- row 1) col result))
;			)
;
;			(if (n_inBoard (- row 1) (+ col 1))
;				(set! result (n_addPath (- row 1) (+ col 1) result))
;			)
;
;			(if (n_inBoard (+ row 1) (- col 1))
;				(set! result (n_addPath (+ row 1) (- col 1) result))
;			)
;			result
;		)
;	)
;)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; The following is another major function of how to choose branching factors
;; after union of shortest path from both color, we give priority to those points of
;; overlapped ones. And after that, we choose those who can connect the same color points
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define n_doChooseBranching
	(lambda (board color ls)
		(if (null? ls)
			'()
			(let ((row (car (car ls)))(col (cdr (car ls))))
				(if (n_hasBothColorNeighbour board color row col)
					(cons (car ls)(n_doChooseBranching board color (cdr ls)))
					(n_doChooseBranching board color (cdr ls))
				)
			)
		)
	)
)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; function to union two path
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define n_testElement
	(lambda (x ls)
		(if (null? ls)
			#f
			(if (equal? x (car ls))
				#t
				(n_testElement x (cdr ls))
			)
		)
	)
)

(define n_testList
	(lambda (ls1 ls2)
		(if (null? ls1)
			'()
			(if (n_testElement (car ls1) ls2)
				(cons (car ls1) (n_testList (cdr ls1) ls2))
				(n_testList (cdr ls1) ls2)
			)
		)
	)
)

(define n_unionPath
	(lambda (ls1 ls2)
		(let ((result (n_testList ls1 ls2)))
			(if (null? result)
				(append ls1 ls2)
				result
			)
		)
	)
)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; legacy of codes, maybe it is useful in distant future
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define n_propogate
	(lambda (board color row col length path isUpLeft)
		(let (
			(result0 (n_doFindPath board color row (+ col 1) length path isUpLeft))
			(result1 (n_doFindPath board color row (- col 1) length path isUpLeft))
			(result2 (n_doFindPath board color (+ row 1) col length path isUpLeft))
			(result3 (n_doFindPath board color (- row 1) col length path isUpLeft))
			(result4 (n_doFindPath board color (- row 1) (- col 1) length path isUpLeft))
			(result5 (n_doFindPath board color (+ row 1) (+ col 1) length path isUpLeft))
			(temp (list n_infinite))
			)
				(n_findMin temp (list result0 result1 result2 result3 result4 result5))
		)
	)
)

; there are four situations:
; 2 : the same color, which means you can teleport to it without cost
; 1 : found it , the correct border reached
; 0 : not yet, but can go on which means the node is empty
; -1 : dead end, either it is visited before or even longer route than other route
; -2: or out of board
(define n_checkCondition
	(lambda (board color row col length path isUpLeft)
		(cond
			((and color isUpLeft (= row 0)) 1)
			((and color (not isUpLeft)(= row (- board-size 1))) 1)
			((and (not color) isUpLeft (= col 0)) 1)
			((and (not color)(not isUpLeft)(= col (- board-size 1))) 1)
						
			((or (< row 0)(< col 0)(= row board-size)(= col board-size))  -2)
			((> length n_currentLength) -1) ; already longer than previous			
			((n_inPath row col path) -1)
			((n_otherColor board color row col) -1)			
			((n_sameColor board color row col) 2)
			(else 0) ; empty
		)
	)
)




file name: board.scm (provided by professor and probably obtained somewhere in internet, at least I suspect)

; Hex board game definitions & functions
; COMP 472/6721 - Introduction to AI
; Project 2
;

; a hex board is of size NxN
(define board-size 11)

; each hexagon on the board is either empty, marked red, or marked blue
; we represent these as Scheme symbols 'R, 'B, and 'E
(define blue 'B)
(define red 'R)
(define empty 'E)

; a board is a vector of size N of vectors of size N,
; each element in the NxN matrix is initialized to "empty"
; board[0] gives you the top row, and board[0][0] its leftmost column
(define board (do ((board (make-vector board-size))
		   (i 0 (+ i 1)))
		  ((= i board-size) board)
		(vector-set! board i (make-vector board-size empty))))

; play a game until one side wins
(define (play board)
    (let loop ((player #t))         ; red starts
	  (begin (pp (list "loop begins player=" player))
      ;(if (not (time (move board player)))
	  (if (not (move board player))

	  (loop (not player))))
	  )
)



;------------------------------------------------
; make a move - implement this in a file hex.scm!
;
; "board" is of size NxN as define above,
;         changed by this function to add a move
;
; "player" is boolean, #t for red and #f for blue
;
; <return> value of this function is a boolean,
;          #t for win (current player wins),
;          #f for no win (game continues)
;
;(define (move board player)
;  ...
;)
;------------------------------------------------

			 
file name: displayboard.scm
			
	

;Author: Alejandro Endo

;Date: 22 November 2005

;Parameters:

;<brd> board

;<row> It has to be 0

;It may not work with certain fonts since the arrangement depends on that. It looks fine in Dr Scheme and in my version of SSH which i use to telnet to concordia

(load "board.scm")



(define (a_BoardDisplay brd) 
(display "     ")
(assignCoordinates1 brd 0)

  (display "      /")

  (a_displayBoard brd 0)

  (display #\newline)

  ) ;just a wrapper



(define (a_displayBoard brd row)

  (if (>= row (vector-length brd)) (a_displayTop (vector-ref brd 0) 1 0) ;last

      (begin

	;(a_addSpaces row)

        (a_displayTop (vector-ref brd row) row 0)

        (display #\newline)

        
(a_addSpaces (+ (+ row row) 1))

(display " <")
(display (integer->char (+ row 65)))
(display ">")

;        (a_addSpaces (+ (+ row row) 1))

        

        (a_displayMiddle (vector-ref brd row) row 0)

        (display #\newline)

        (a_addSpaces (+ (+ row row) 1))

        (display "    ")

        

        (a_displayBoard brd (+ row 1))

        )

      )

  )





(define (a_displayTop vec row pos)

  ;(if (and (eq? (vector-length vec) pos) (eq? (modulo row 2) 0)) (display"/"))



        (if (eq? (vector-length vec) pos) (display" \\"))

  (if (and (eq? row 0) (eq? pos 0)) (set! pos 1))

  (if (< pos (vector-length vec))

            (begin 

              ;(if (and (eq? (modulo row 2) 1) (eq? pos 0)) (display " \\"))

              

              (display " \\ /")

              (a_displayTop vec row (+ pos 1))

              

              )

            

            )

        

      

  )





(define (a_displayMiddle vec row pos)
  (define symbol 0)

  (if (eq? (vector-length vec) pos) (display "|"))

  (if (< pos (vector-length vec)) 

      (begin 

        ;(if (eq? (modulo row 2) 1) (display " "))

        (display "| ")
	(set! symbol (vector-ref vec pos) )

        ;(display (vector-ref vec pos) )
	(if (eq? symbol 'E)
		(display ".")
		(display symbol))

        (display " ")

        (a_displayMiddle vec 0 (+ pos 1))

        )

      )

  )

(define (a_addSpaces num)

  (if (> num 0) 

      (begin

        (display " ")

        (a_addSpaces (- num 1))

        )

      )

  )

(define (assignCoordinates1 brd level)
(if (< level (vector-length brd))
(begin
(display " <")
(display (integer->char (+ level 97)))
(display ">")
(assignCoordinates1 brd (+ level 1))
)
(display #\newline)
)
)

file name: moveboard.scm

(load "board.scm")
(load "ShortestPath.scm")
(load "alpha-beta.scm")
;(load "alex.scm")
(load "displayboard.scm")



(define CoordList '())
(define n_firstMove #t)
(define n_secondMove #t)
(define n_firstMoveCoord '(5 . 5))

(define n_secondMoveCoord '(7 . 5))

(define FirstMove 
	(lambda (board player)		
		(MoveBoard board player n_firstMoveCoord)			
		(DisplayBoard board)
		#f
	)
)

(define SecondMove 
	(lambda (board player)		
		(MoveBoard board player n_secondMoveCoord)			
		(DisplayBoard board)
		#f
	)
)

;(define MinMax
;	(lambda (board color)
;		(l_alpha-beta MaxDepth board color DefaultAlphaValue DefaultBetaValue #t)
;	)
;)
;(define n_currentDepth 0)


(define DisplayBoard 
	(lambda (board)
		(a_BoardDisplay board) 
	)
)

(define MoveBoard
	(lambda (board color coord)
		(if color
			(vector-set! (vector-ref board (car coord)) (cdr coord) 'R)
			(vector-set! (vector-ref board (car coord)) (cdr coord) 'B)
		)
	)
)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; function to decide if there is a winner
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define Judge
	(lambda (board color)
		(= (car (ShortestPath board color)) 0)
	)
)

(define DisplayResult
	(lambda (board winner)
		(if winner
			(pp "Red is winning!")
			(pp "Blue is winning!")
		)
		;(DisplayBoard board)
		(let loop ((ls CoordList)(color #t))
			(if (not (null? ls))
				(begin
					(if color 
						(pp (list "Red" (car (car ls)) (cdr (car ls))) )
						(pp (list "Blue" (car (car ls)) (cdr (car ls))) )
					)
					(loop (cdr ls)(not color))
				)
			)
		)
	)
)


(define move
	(lambda (board player)
		(if n_firstMove
			(begin
				(set! n_firstMove #f)
				(set! CoordList (append CoordList (list n_firstMoveCoord)))
				(FirstMove board player)
			)
			;;else
			(if n_secondMove
				(begin
					(set! n_secondMove #f)
					(set! CoordList (append CoordList (list n_secondMoveCoord)))
					(SecondMove board player)
				)			
				
				;; else
				(begin
					;(pp (list "before minmax " board))
					;(DisplayBoard board)
					(let ((step (MinMax board player)))
						(set! CoordList (append CoordList (list step)))
						(MoveBoard board player step)
						(DisplayBoard board)
						(if (Judge board player)
							(begin
								(DisplayResult board player)
								#t
							)
							#f
						)
					)
				)
			)
		)
	)
)

					

file name: alpha-beta.scm

(load "ShortestPath.scm")

(define MaxDepth 3)
(define DefaultAlphaValue -999)
(define DefaultBetaValue  999)

(define MaxAlphaValue 999)
(define MinBetaValue  -999)

(define DoMove
	(lambda (board color coord)
		(if color
			(n_vectorset board (car coord)(cdr coord) 'R)
			(n_vectorset board (car coord)(cdr coord) 'B)
		)
	)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;first choose the overlapped in n_union
;;; then we try to find connected
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define ChooseBranching
	(lambda (board color)
		(let ((path (n_unionPath (cdr (ShortestPath board #t))(cdr (ShortestPath board #f)))))
			(let ((result (n_doChooseBranching board color path)))
				(if (null? result)
					path
					result
				)
			)
		)
	)
)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  This is the major function of Heuristic
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define Heuristic
	(lambda (board)
		(- (car (ShortestPath board #f)) (car (ShortestPath board #t)))
	)
)

;(define n_doGetMinMax
;	(lambda (color numlst)
;		(let ((result 0))
;			(if color
;				(set! result DefaultAlphaValue)
;				(set! result DefaultBetaValue)
;			)
;			(let loop ((ls numlst))
;				(if (null? ls)
;					(begin ;(pp (list "n_doGetMinMax=" result "color=" color))						
;						result
;					)
;					(begin
;						(if color 
;							(set! result (max (car ls) result))
;							(set! result (min (car ls) result))
;						)
;						(loop (cdr ls))
;					)
;				)
;			)
;		)
;	)
;)



;(define n_getMinMaxValue
;	(lambda (board color depth)
;		(lambda (coord)			
;			(let ((path (ChooseBranching board color)))
;				(begin ;(pp (list "n_getMinMaxValue color=" color "depth=" depth "coord=" coord  "path=" path))
;				(cond
;					((and color (null? path)) DefaultBetaValue); red is winning
;					((and (not color)(null? path)) DefaultAlphaValue) ; blue is winning
;					((= depth MaxDepth) (Heuristic board))
;					(else
;						(n_doGetMinMax color 
;							(map (n_getMinMaxValue (DoMove board color coord) (not color)(+ depth 1)) path)))						
;				))
;			)
;		)
;	)
;)

(define n_getMinMaxValue
	(lambda (board color alpha beta coord depth)				
		(let ((path (ChooseBranching board color)))
			;(begin ;(pp (list "n_getMinMaxValue color=" color "depth=" depth "coord=" coord  "path=" path))
			(cond
				((and color (null? path)) DefaultBetaValue); red is winning
				((and (not color)(null? path)) DefaultAlphaValue) ; blue is winning
				((= depth MaxDepth) (Heuristic board))
				(else
					(begin
						(let ((result 0))
							(if color
								(set! result DefaultAlphaValue)
								(set! result DefaultBetaValue)
							)
							(let loop ((ls path))
								(if (null? ls)
									result
									(let ((value (n_getMinMaxValue (DoMove board color coord) (not color)
												alpha beta (car ls) (+ depth 1)) ))
										(cond
											((and color (> value beta)) value)
											((and (not color)(< value alpha)) value)
											((and color (> value alpha)) 
												(begin
													;(set! alpha value)
													(set! result value)
													(loop (cdr ls))
												)
											)
											((and (not color) (< value beta))
												(begin
													;(set! beta value)
													(set! result value)
													(loop (cdr ls))
												)
											)
											(else (loop (cdr ls)))
										)
									)
								)
							)
						)
					)
				)
			)
		)
	)
)

			


(define MinMax
	(lambda (board color)
		(let ((minmaxValue 0)(result '())(path (ChooseBranching board color)))	
			(set! result (car path))					
			(let loop ((ls path))
				(if color 
					(set! minmaxValue DefaultAlphaValue)
					(set! minmaxValue DefaultBetaValue)
				)						
				(begin ;(pp (list "loop continue with path=" path))
				(if (null? ls)					
					result
					(let ((value (n_getMinMaxValue board color DefaultAlphaValue DefaultBetaValue (car ls) 0) ))
						;(pp (list "for coord=" (car ls) "color=" color "value=" value "minmaxValue=" minmaxValue))
						(if (or (and color (> value minmaxValue))
								(and (not color) (< value minmaxValue)))
							(set! result (car ls))
						)
						(loop (cdr ls))
					)
				))
			)
		)
	)
)
			
					
					

file name: humanplay.scm
				

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Human vs. AI interface
;; author: qingzhe huang
;; date: Nov. 29, 2005
;; usage: load this file and run (humanplay board)
;;		  at prompt, key in coordinate with row of capital letter, column of lower case letter
;;		  e.g.  "Fg" will be translated as (5 . 6), no space is allowed in between
;;        My program would not check or tolerate any mistakes of coordinate
;;        
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(load "DisplayBoard.scm")
(load "moveboard.scm")

(define RowBase (char->integer #\A))
(define ColBase (char->integer #\a))




(define read-coord
	(lambda()
		(let ((pr (read-pair)))
			(cons (- (char->integer (car pr)) RowBase) (- (char->integer (cdr pr)) ColBase))
		)
	)
)


(define read-pair
	(lambda ()
		(read-char) ; ignore the first newline
		(cons (read-char) (read-char))	
	)
)

(define (humanplay board)
	(let loop ((player #t))         ; red starts	
		(begin 
			(pp (list "loop begins player=" player))
			(display "key in coordinate with row in capital letter and column in lower letter and no space in between")
			(display #\newline)
			(display ">")
			(let ((coord (read-coord)))
				(MoveBoard board player coord)
				(set! CoordList (append CoordList (list coord)))
			)
			(DisplayBoard board)
			(if (not (Judge board player))
				(if (not (humanmove board (not player)))
					(loop  player)
					(DisplayResult board (not player))
				)
				(DisplayResult board player)
			)
		)
	)
)
				
(define humanmove
	(lambda (board player)	
		(if n_firstMove
			(begin
				(set! n_firstMove #f)
				(if (not (eq? (n_vectorget board (car n_firstMoveCoord) (cdr n_firstMoveCoord)) 'E))
					(set! n_firstMoveCoord (cons (+ (car n_firstMoveCoord) 2) (cdr n_firstMoveCoord)))
				)
				(set! CoordList (append CoordList (list n_firstMoveCoord)))
				(FirstMove board player)
			)
			(begin
				(pp (list "play continues the player is" player))
				(let ((step (MinMax board player)))
					(set! CoordList (append CoordList (list step)))
					(MoveBoard board player step)
					(DisplayBoard board)
					(if (Judge board player)
						(begin
							(DisplayResult board player)
							#t
						)
						#f
					)
				)
			)
		)
	)
)

The result is like following :

......

("play continues the player is" #f)
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | . | . | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | . | . | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | . | . | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | . | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("loop begins player=" #t)
key in coordinate with row in capital letter and column in lower letter and no s
pace in between
>De
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | . | . | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | . | . | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | . | . | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("play continues the player is" #f)
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | . | . | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | . | . | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | . | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("loop begins player=" #t)
key in coordinate with row in capital letter and column in lower letter and no s
pace in between
>Ce
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | . | . | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | . | . | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | R | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("play continues the player is" #f)
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | . | . | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | . | B | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | R | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("loop begins player=" #t)
key in coordinate with row in capital letter and column in lower letter and no s
pace in between
>Be
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | . | . | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | R | B | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | R | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("play continues the player is" #f)
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | . | B | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | R | B | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | R | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("loop begins player=" #t)
key in coordinate with row in capital letter and column in lower letter and no s
pace in between
>Ae
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | R | B | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | R | B | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | R | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | . | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("play continues the player is" #f)
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | R | B | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | R | B | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | R | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | B | . | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
("loop begins player=" #t)
key in coordinate with row in capital letter and column in lower letter and no s
pace in between
>Ke
      <a> <b> <c> <d> <e> <f> <g> <h> <i> <j> <k>
      / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
  <A>| . | . | . | . | R | B | . | . | . | . | B |
      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
    <B>| . | . | . | . | R | B | . | . | . | B | . |
        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
      <C>| . | . | . | . | R | B | . | . | B | . | . |
          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
        <D>| . | . | . | . | R | B | . | B | . | . | . |
            \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
          <E>| . | . | . | . | R | . | B | R | . | . | . |
              \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
            <F>| . | . | . | . | R | B | R | B | . | . | . |
                \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
              <G>| . | . | . | . | R | R | . | R | . | . | . |
                  \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                <H>| . | . | . | . | B | R | . | . | . | . | . |
                    \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                  <I>| . | . | . | . | B | R | . | . | . | . | . |
                      \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                    <J>| . | . | . | . | R | . | . | . | . | . | . |
                        \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
                      <K>| . | . | . | B | R | . | . | . | . | . | . |
                          \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
"Red is winning!"
("Red" 6 7)
("Blue" 5 5)
("Red" 6 5)
("Blue" 5 7)
("Red" 5 6)
("Blue" 7 4)
("Red" 7 5)
("Blue" 8 4)
("Red" 8 5)
("Blue" 4 6)
("Red" 9 4)
("Blue" 3 7)
("Red" 4 7)
("Blue" 2 8)
("Red" 6 4)
("Blue" 1 9)
("Red" 5 4)
("Blue" 0 10)
("Red" 4 4)
("Blue" 3 5)
("Red" 3 4)
("Blue" 2 5)
("Red" 2 4)
("Blue" 1 5)
("Red" 1 4)
("Blue" 0 5)
("Red" 0 4)
("Blue" 10 3)
("Red" 10 4)
>