/*
 * Implementation of noughts and crosses (tic-tac-toe) in Fril.
 * This code can be used as a stand-alone package (in Fril) or as part of an embedded
 * system in Java, with Java handling the display and user interaction.
 *
 *	Author T. P. Martin (c) 2000
 *
 * 
 * To use as a stand-alone system
 * load this file into Fril
 * run the goal
 * go 2     % to let the computer go first
 * go 1     % or go <anything-except-2> for the human to go first
 *
 * In the stand-alone system, a simple grid is drawn as below
 *
 *     0| 1 |2
 *     --------
 *     3| 4 |5
 *     --------
 *     6| 7 |8
 *
 * and squares are taken by typing the number in response to the prompt;
 * the numbers are substituted by 'x' or 'o' until the game is won, lost or drawn.
 * There is little error checking and the algorithm is not infallible.
 * The board is passed to Fril as a list of lists e.g. ((0 x 2) (3 o 5) (x o 8))
 * indicating that the top centre square (1) has been occupied by 'x', etc.
 * Human is assumed to play 'x' and computer is 'o' - this is hard coded into
 * the predicates "final", "opp_move" and "play" below.
 */


((go 2) (play comp ((0 1 2)(3 4 5)(6 7 8))))
((go X) (play opp ((0 1 2)(3 4 5)(6 7 8))))

((play _  BOARD) (final BOARD VERDICT) (p '>>>>>' VERDICT '<<<<<')(pp)(!))	  % check for win/draw/lose

((play opp BOARD) (opp_move BOARD NEXT)  (play comp NEXT))		% human's turn - get move and continue
((play comp BOARD)												% computer's turn - calculate move and continue
    (move BOARD MOVE) 
	(board_subst o MOVE BOARD NEXT)
	(!)
	(pp (computer occupied square MOVE)) 
	(play opp NEXT))

/* get human move - print out current board and get a number, try
 * to substitute an 'x' for the number. If board_subst fails, 
 * print a message and do it all again
 */
 
((opp_move BOARD NEWB)
        (print_board BOARD)
        (read_move MOVE)
        (board_subst x MOVE BOARD NEWB)
        (!))
((opp_move BOARD NEWB) (p  invalid move) (pp) (opp_move BOARD NEWB))

		
((read_move MOVE)(p Please input any number from the board above) (p  >) (p) (r MOVE))

((print_board (LAST)) (!) (print_row LAST) (pp))
((print_board (ROW|REST)) (print_row ROW) (pp '--------') (print_board REST))

((print_row (A B C)) (p A '|' B '|' C)(pp))

/* board_subst substitutes the symbol SYM for the number NUM in
 * the board represented by the 3rd argument, yielding a new
 * board in the 4th argument
 */
 
((board_subst SYM NUM (ROW|REST) (NEW|REST))
        (row_subst SYM NUM ROW NEW)
        (!))
((board_subst SYM NUM (ROW|REST) (ROW|NEW))
        (board_subst SYM NUM REST NEW))

((row_subst SYM NUM (NUM|REST) (SYM|REST)) (!))
((row_subst SYM NUM (ANY|REST) (ANY|NEW)) (row_subst SYM NUM REST NEW))


/*------------------------------------------------------
 *
 * embedded code - for just making moves - is below.
 * "move" and "final" are called from Java
 *
 *------------------------------------------------------*/
 
 /* line is used to extract the symbols in a line. The first
  * argument is a variable, instantiated on success to a list
  * of three symbols (taken from o, x, number)
  * First 3 clauses extract rows, then 2 diagonals and finally 3 columns
  */
 
((line X (X _ _)))
((line X (_ X _)))
((line X (_ _ X)))
((line (T M B) ((T _ _) (_ M _) (_ _ B))))
((line (T M B) ((_ _ T) (_ M _) (B _ _))))
((line (T M B) ((T _ _) (M _ _) (B _ _))))
((line (T M B) ((_ T _) (_ M _) (_ B _))))
((line (T M B) ((_ _ T) (_ _ M) (_ _ B))))

/* 
 * 1st argument N is initially a variable, 2nd argument is a board ((...) (...) (...))
 * N is instantiated on success to a number (representing a space) in the board
 */

((space N (ROW|BOARD)) (member N ROW) (num N) )
((space N (_|REST)) (space N REST))

((member N (N|_)))
((member N (_|T)) (member N T))


((delete_member X (X|R) R))
((delete_member X (A|R) (A|T)) (delete_member X R T))


/* 
 * "contains" is used to check whether specified symbols are present in a line (list of 3 x/o/number symbols)
 * The first argument is list of up to three symbols drawn from <o, x, blank>
 * The second argument is initially a variable, instantiated on success to the corresponding board symbols.
 * The third argument is three board symbols representing a line.
 *
 * For example if the third argument contains (3 x 5) and the first argument is (blank blank) then
 * the second argument will be isntantiated to (3 5) on successful completion
 */
 
((contains () () LINE))
((contains (blank|T) (NUM|R) LINE) (delete_member NUM LINE NEWLINE) (num NUM) (!) (contains T R NEWLINE))
((contains (H|T) BLANKS LINE) (delete_member H LINE NEWLINE) (contains T BLANKS NEWLINE))


/* 
 * "final" checks whether the game is finished and if so, returns a verdict in the second argument
 */
 
((final BOARD human) (line (x x x) BOARD) (!))
((final BOARD computer) (line (o o o) BOARD) (!))
((final BOARD draw) (negg space N BOARD))

/*
 * "move" is given a current state-of-play in the first argument and returns the
 * selected position in the second argument.
 * The algorithm for selecting a position is
 * (i) is there a square that would lead to a win by completing a row
 * (ii) is there a square that would prevent a defeat by blocking the opponent's o-o-blank
 * (iii) are there two lines o-blank-blank with a common blank square - choose the common square
 * (iv) is there a line with two blanks and an 'o' - choose the first blank
 * (v) choose any square according to the order of the "preferred" clauses below
 */
 
((move OLD MOVE) (pp (rule 1)) (line LINE OLD) (contains (o o blank) (MOVE) LINE) )
((move OLD MOVE) (pp (rule 2)) (line LINE OLD) (contains (x x blank) (MOVE) LINE) )
((move OLD MOVE) (pp (rule 3)) (line LINE1 OLD)
				(line LINE2 OLD)
				(negg eq LINE1 LINE2)
				(contains (o blank blank) MOVES1 LINE1) 
				(contains (o blank blank) MOVES2 LINE2) 
				(common MOVE MOVES1 MOVES2))
				
((move OLD B1) (pp (rule 4)) (line LINE OLD)
				(contains (o blank blank) (B1 B2) LINE))
				
((move OLD MOVE) (pp (rule 5)) (findall N ((space N OLD)) BLANKS) (select MOVE BLANKS))
				

((move OLD MOVE) (print_board OLD) (p error creating computer move)(read_move MOVE))

/* 
 * select <var> <list-of-blank-squares> chooses the best move in the absence of, determined by the
 * order of the clauses "preferred" i.e. middle square (4), corner square (0 2 6 8), 
 * central edge square (1 3 5 7)
 */
 
((select MOVE BLANKS) (preferred MOVE) (member MOVE BLANKS) (!))

((preferred 4))
((preferred 0))
((preferred 2))
((preferred 6))
((preferred 8))
((preferred 1))
((preferred 3))
((preferred 5))
((preferred 7))

((common EL (EL|T) L2) (member EL L2) (!))
((common EL (_|T) L2) (common E T L2))