%    Overview:  This file contains procedures for use in the genetic
%    determination of an optimal static_evaluator.
%
%   NOTE:  This program should be used before the final completion of
%   antichess.  It is part of a set of artificial intellenge programs
%   which are used to develop a good strategy BEFORE the final product
%   is assembled.  This program is written for the express purpose of
%   being used by the designers of the antichess program and therefore:
%   1)  It is not very watertight (i.e., the user should
%   have a good knowledge of how the rest of the antichess program
%   works and try not to use anything that doesn't agree with the
%   requires clause of specific procedures.)  2) This program
%   should be compiled with the -debug option otherwise it won't do
%   anything.

% written by twm

start_up = proc()
    
    % This program should be compiled with the debug option, because
    % it won't do anything otherwise.
    
    random$seed(time$get_millis(run_time())*1000 +
		time$get_micros(run_time()))
    %breed_v2(static_evaluator$create(), 1001001)
    %best_white_moves()
    %best_black_moves()
    %evolve(static_evaluator$create(), 1001001)
    %callibrate(5000)
    %computer_player$best_white_moves(30000.0)
    computer_player$best_black_moves(8000.0)
  end start_up

population = array[static_evaluator]

breed = proc(eve: static_evaluator, generations: int) returns(static_evaluator)

    % effects:  Applies natural selection to eve and her descendents
    %   in favor of static evaluators that are the most fit (win the most
    %   games.)  With each new generation the fitness of all individuals
    %   is tested, the most fit individual is unparsed to primary_output,
    %   the population is reduced in favor of the more fit individuals,
    %   a few random individuals are created, some mating occurs,
    %   some mutants are created, and the remaining individuals, their
    %   descendants, the mutants, and the random individuals
    %   are used as the next
    %   generation.  When the number of generations is equal to
    %   "generations" the most fit individual is returned.  When
    %   generations < 1, eve is returned.    
    
    % define the way in which each new generation is divided    
    
    randoms = 1
    mutants = 1
    top = 3
    children = (top - 2 + randoms + mutants) * 2 + 1
    pop = randoms + top + children + mutants
    fatality_rate = pop - top
    
    best: static_evaluator := eve
    second_best: static_evaluator := eve
    current: population := population$create(1)
    population$addh(current, eve)
    for gen: int in int$from_to(1, generations) do
	stream$putl(stream$primary_output(), "\n\n\nGeneration Number " ||
		    int$unparse(gen) || "\n\n")
	
	% Pad empty spaces with randoms.  Empty spaces
	% occur at the beginning when Eve is the only individual
	% and when duplicates are deleted from the pool.
	
	while population$size(current) < pop do 
	    population$addh(current, static_evaluator$create_random())
	  end 
	
	ratings: array[int] := array[int]$fill(1, pop, 0)
	final: int := population$high(current)
	for challenger: int in int$from_to(population$low(current), final-1) do
	    for opponent: int in int$from_to(challenger+1, final) do
		stream$putl(stream$primary_output(), int$unparse(challenger)
			    || " vs. " || int$unparse(opponent) || ":   ")
		
		winner : int := pit(current, challenger, opponent)
		ratings[winner] := ratings[winner] + 1
		
		stream$putl(stream$primary_output(),
			    int$unparse(winner) || "\n")
		
	      end
	  end
	
	% Sort current in order of descending fitness based on ratings
	% and eliminate the weaker portion of the population.
	
	new_pop: population:= population$create(1)
	cut_off: int := pop
	counter: int := 0
	while counter < top do
	    for fitness: int in array[int]$indexes(ratings) do
		if ratings[fitness] = cut_off then
		    population$addh(new_pop, current[fitness])
		    counter := counter + 1
		  end
	      end
	    cut_off := cut_off - 1
	  end
	while counter > top do
	    population$remh(new_pop)
	    counter := counter - 1
	  end
		    
	% generate new population from the best of the old,
	% mating, mutating, and randomness.
	
	for dummy_int2: int in int$from_to(1, randoms) do
	    population$addh(new_pop, static_evaluator$create_random())
	  end
	for dummy_int3: int in int$from_to(1, mutants) do
	    population$addh(new_pop, static_evaluator$create_mutant(best))
	    end
	current := population$copy(new_pop)
	tot: int:= population$high(new_pop)
	best:=current[1]
	second_best:=current[2]
	for count: int in int$from_to(3, tot) do
	    population$addh(current, static_evaluator$mate(best, current[count]))
	    population$addh(current, static_evaluator$mate(second_best, current[count]))
	  end
	population$addh(current, static_evaluator$mate(best, second_best))
	
	% eliminate duplicates
	
	original_size: int:= population$high(current)
	new_pop:= population$copy(current)
	for index: int in int$from_to(1, original_size-1) do
	    check: static_evaluator := current[index]
	    for index2: int in int$from_to(index+1, population$high(current)) do
		if check = current[index2] then
		    current[index2] := population$remh(new_pop)
		    break
		  end   %  if statement
	      end  %  inner for loop
	  end  % outer for loop
	current:= population$copy(new_pop)
	
	static_evaluator$unparse(best)
      end   % for gen loop
    
    return(best)    
  end breed


pit = proc(pop: population, challenger, opponent: int) returns(int)
    
    % requires: challenger and opponent are legitimate
    %   indeces of pop.
    % effects: Pits the static_evaluators of the
    %   population "pop" whose indeces are
    %   "challenger" and "opponent" against
    %   each other in a game of antichess and returns the 
    %   index of the winner.
    
    oppnnt: computer_player:=
    computer_player$create(options${level: 5,
				    iswhite: true,
				    telestate: t_state$make_off(nil)},
			   "White")
    computer_player$set_evaluator(oppnnt, pop[opponent])
    chlngr: computer_player:=
    computer_player$create(options${level: 5,
				    iswhite: false,
				    telestate: t_state$make_off(nil)},
			   "Black")
    computer_player$set_evaluator(chlngr, pop[challenger])
    move: moveData
    board: chess_board:= chess_board$create()
    counter: int := 200
    while true do
	if ~chess_board$can_move(board, whitePiece) cor (counter = 0)
	  then
	    return(opponent)
	  end
	move:= computer_player$make_move(oppnnt, 5000, board)
	chess_board$make_move(board, whitePiece, move)
	
	stream$putl(stream$primary_output(),
		    chess_board$unparse(board))
	
	computer_player$opponent_moved(chlngr, move)
	if ~chess_board$can_move(board, blackPiece)
	  then
	    return(challenger)
	  end
	move:= computer_player$make_move(chlngr, 5000, board)
	chess_board$make_move(board, blackPiece, move)
	
	stream$putl(stream$primary_output(),
		    chess_board$unparse(board))
	
	computer_player$opponent_moved(oppnnt, move)
	counter := counter - 1
      end
    
  end pit

best_white_moves = proc()
    % Requires:  The first move for black is not hardwired into the
    %   computer_player.  The best first move for white is the move
    %   called best_first below.
    % Effects:  Returns the best second move for white that the
    %   default level 5 computer_player will give with the default
    %   static_evaluator.
    
    best_first = moveData${fromrow:2,
			   fromcol:8,
			   torow:4,
			   tocol:8}
    
    print("Best second moves for white")
    print("---------------------------\n")
    board: chess_board := chess_board$create()
    player1: computer_player:=
    computer_player$create(options${level: 5,
				    iswhite: true,
				    telestate: t_state$make_off(nil)},
			   "White")
    computer_player$set_evaluator(player1, static_evaluator$create())
    b: chess_board:= chess_board$create()
    chess_board$make_move(b, whitePiece, best_first)
    for fr, fc, tr, tc: int, ufoo: undoMoveInfo in
	chess_board$all_possible_moves(b, blackPiece) do
	mv: moveData:=computer_player$make_move(player1, 50000, b)
	undo: undoMoveInfo:= chess_board$make_move(b, whitePiece, mv)
	print(chess_board$unparse(b) || "\n")
	chess_board$undo_move(b, undo)
      end
  end best_white_moves

print = proc(mess: string)
    % effects:  Sends mess to primary_output as a line.
    
    stream$putl(stream$primary_output(), mess)
  end print

best_black_moves = proc()
    % Requires:  The first move for black is not hardwired into the
    %   computer_player.  The best first move for white is the move
    %   called best_first below.
    % Effects:  Returns the best second move for white that the
    %   default level 5 computer_player will give with the default
    %   static_evaluator.
    
    print("Best moves for black")
    print("--------------------\n")
    board: chess_board := chess_board$create()
    player2: computer_player:=
    computer_player$create(options${level: 5,
				    iswhite: false,
				    telestate: t_state$make_off(nil)},
			   "Black")
    computer_player$set_evaluator(player2, static_evaluator$create())
    b: chess_board:= chess_board$create()
    for fr, fc, tr, tc: int, ufoo: undoMoveInfo in
	chess_board$all_possible_moves(b, whitePiece) do
	mv: moveData:=computer_player$make_move(player2, 50000, b)
	undo: undoMoveInfo:= chess_board$make_move(b, blackPiece, mv)
	print(chess_board$unparse(b) || "\n")
	chess_board$undo_move(b, undo)
      end
  end best_black_moves


evolve = proc(e: static_evaluator, mutations: int)
    % modifies: e
    % effects:  Makes "mutations" number of mutations on e 1 by 1
    %   and after each mutation, plays the mutant off against e.
    %   The winner becomes e, the loser is destroyed, and the
    %   process continues.  Unlike breed, games are timed here.
    
    play_time = 300000
    
    tstart, tfinish: realtime
    count: int:= 1
    while count <= mutations do
	print("Mutation No. " || int$unparse(count) || "\n")
	b: chess_board:= chess_board$create()
	
	% Comment out one of the two following lines (but not both)
	% depending on whether you want to optimize the piece
	% weights or the time that computer_player takes for each move.
	
	e2: static_evaluator:= static_evaluator$create_mutant(e)
%	e2: static_evaluator:= static_evaluator$create_move_mutant(e)
		
	white:computer_player:=
	computer_player$create(options${level: 5,
					iswhite: true,
					telestate: t_state$make_off(nil)},
			       "John Lenon")
	computer_player$set_evaluator(white, e)
	computer_player$reset_state(white, true)
	black:computer_player:=
	computer_player$create(options${level: 5,
					iswhite:false,
					telestate: t_state$make_off(nil)},
			       "George Harrison")
	computer_player$set_evaluator(black, e2)
	computer_player$reset_state(black, true)
	white_time: int := play_time
	black_time: int := play_time
	move: moveData
	while true do
	    print("White with " || int$unparse(white_time) ||
		  " milliseconds left...")
	    tstart:=realtime$now()
	    if ~chess_board$can_move(b, whitePiece)
	      then
		static_evaluator$unparse(e)
		e:= e
		break
	      end
	    move:= computer_player$make_move(white, white_time, b)
	    chess_board$make_move(b, whitePiece, move)
	    computer_player$opponent_moved(black, move)
	    tfinish:=realtime$now()
	    white_time:= (white_time -
			  (real$r2i(duration$to_milliseconds
				    (realtime$difference(tfinish, tstart)))))
	    print(chess_board$unparse(b))
	    print("... White now has "||int$unparse(white_time)||
		  " milliseconds left\n\n")
	    if white_time <= 0
	      then 
%		e:=e2
		print("\n\n You should not reach this line!!!!\n\n\n")
		static_evaluator$unparse(e2)
		break
	      end
	    print("Black with " || int$unparse(black_time) ||
		  " milliseconds left...")
	    tstart:=realtime$now()
	    if ~chess_board$can_move(b, blackPiece)
	      then
		static_evaluator$unparse(e2)
		e:=e2
		break
	      end
	    move:= computer_player$make_move(black, black_time, b)
	    chess_board$make_move(b, blackPiece, move)
	    computer_player$opponent_moved(white, move)
	    tfinish:=realtime$now()
	    black_time:= (black_time -
			  (real$r2i(duration$to_milliseconds
				    (realtime$difference(tfinish, tstart)))))
	    print(chess_board$unparse(b))
	    print("... Black now has "||int$unparse(black_time)||
		  " milliseconds left\n\n")
	    if black_time <= 0
	      then 
		print("\n\n You should not reach this line either!!!!\n\n\n")
		static_evaluator$unparse(e)
		e:=e
		break
	      end
	  end % while true do
	count:=count+1
      end % while count...
  end evolve

make_move = proc(fr, fc, tr, tc: int) returns(moveData)
    % requires: fr, fc, tr, and tc are all in the range [1, 8]
    % effect: returns a move in the form of moveData.  Useful for when
    %   you're compiling in the debug mode and compile time equates are
    %   no longer valid.
    
    return(moveData${fromrow: fr,
		     fromcol: fc,
		     torow: tr,
		     tocol: tc})
  end make_move

run_through = proc(b: chess_board, c: pieceColor, t: int) returns(real)
    % effects: Determines how long it takes, on average, to search through
    %   one move out of all the moves for a particular color, c, of
    %   player on the given board b (no recursion,
    %   just a level 1 test).  t is the minimum time in milliseconds that
    %   the test is run.  If a test of all possible moves on a board runs
    %   in less time than t, then the test is run repeatedly until the
    %   total time reaches or exceeds t.  Returns the average time
    %   taken to search a node in milliseconds per node.

    tstart, tfinish: realtime
    e:static_evaluator:=static_evaluator$create()
    counter: int:= 0
    nodes:real:=0.0
    tstart:=realtime$now()
    while counter < t do
	for foo1, foo2, foo3, foo4: int, foo5: undoMoveInfo
	    in chess_board$all_possible_moves(b, c) do
	    static_evaluator$evaluate(e, b, c)
	    nodes:=nodes+1.0
	  end
	tfinish:=realtime$now()
	counter:=(real$r2i(duration$to_milliseconds
			   (realtime$difference(tfinish, tstart))))
      end
    return(real$i2r(counter)/nodes)
  end run_through

callibrate = proc(t: int)
    % effects:  For each different piece in piecKind, callibrate
    %   calls run_through with a board representative of a board in which
    %   the selected piece has several moves, and sends the average
    %   time it takes per node for each pieceKind to primary_output.
    %   t is the minimun callibration time (in milliseconds) that is
    %   spent on each piece.
    
    bk: chess_board:=chess_board$parse("--------\n" ||
				       "p-------\n" ||
				       "--------\n" ||
				       "---K----\n" ||
				       "--------\n" ||
				       "---p----\n" ||
				       "p-------\n" ||
				       "--------\n")
    bq: chess_board:=chess_board$parse("--------\n" ||
				       "p-------\n" ||
				       "--------\n" ||
				       "---Q----\n" ||
				       "--------\n" ||
				       "--------\n" ||
				       "-p------\n" ||
				       "--------\n")
    bn: chess_board:=chess_board$parse("--------\n" ||
				       "p-------\n" ||
				       "--------\n" ||
				       "---N-N--\n" ||
				       "--------\n" ||
				       "---p----\n" ||
				       "p-------\n" ||
				       "--------\n")
    bb: chess_board:=chess_board$parse("--------\n" ||
				       "p-------\n" ||
				       "--------\n" ||
				       "---BB---\n" ||
				       "--------\n" ||
				       "---p----\n" ||
				       "--p-----\n" ||
				       "--------\n")
    br: chess_board:=chess_board$parse("--------\n" ||
				       "p-------\n" ||
				       "--------\n" ||
				       "--RR----\n" ||
				       "--------\n" ||
				       "----p---\n" ||
				       "p-------\n" ||
				       "--------\n")
    bp: chess_board:=chess_board$parse("--------\n" ||
				       "pppppppp\n" ||
				       "--------\n" ||
				       "--------\n" ||
				       "--------\n" ||
				       "--------\n" ||
				       "PPPPPPPP\n" ||
				       "--------\n")
    val: real:= run_through(bk, whitePiece, t)
    print("King callibrated at " || real$unparse(val) || " milliseconds")
    val:= run_through(bq, whitePiece, t)
    print("Queen callibrated at " || real$unparse(val) || " milliseconds")
    val:= run_through(br, whitePiece, t)
    print("Rook callibrated at " || real$unparse(val) || " milliseconds")
    val:= run_through(bb, whitePiece, t)
    print("Bishop callibrated at " || real$unparse(val) || " milliseconds")
    val:= run_through(bn, whitePiece, t)
    print("Knight callibrated at " || real$unparse(val) || " milliseconds")
    val:= run_through(bp, whitePiece, t)
    print("Pawn callibrated at " || real$unparse(val) || " milliseconds")
  end callibrate

breed_v2 = proc(eve: static_evaluator, generations: int)
    returns(static_evaluator)

    % effects:  Applies natural selection to eve and her descendents
    %   in favor of static evaluators that are the most fit (win the most
    %   games.)  With each new generation the fitness of all individuals
    %   is tested, the most fit individual is unparsed to primary_output,
    %   the population is reduced in favor of the more fit individuals,
    %   a few random individuals are created, some mating occurs,
    %   some mutants are created, and the remaining individuals, their
    %   descendants, the mutants, and the random individuals
    %   are used as the next
    %   generation.  When the number of generations is equal to
    %   "generations" the most fit individual is returned.  When
    %   generations < 1, eve is returned.    
    
    % define the way in which each new generation is divided    
    
    randoms = 1
    mutants = 2
    top = 3
    children = 1
    pop = randoms + top + children + mutants
    fatality_rate = pop - top
    
    best: static_evaluator := eve
    second_best: static_evaluator := eve
    current: population := population$create(1)
    population$addh(current, eve)
    for gen: int in int$from_to(1, generations) do
	stream$putl(stream$primary_output(), "\n\n\nGeneration Number " ||
		    int$unparse(gen) || "\n\n")
	
	% Pad empty spaces with randoms.  Empty spaces
	% occur at the beginning when Eve is the only individual
	% and when duplicates are deleted from the pool.
	
	while population$size(current) < pop do 
	    population$addh(current, static_evaluator$create_random())
	  end 
	
	ratings: array[int] := array[int]$fill(1, pop, 0)
	final: int := population$high(current)
	for challenger: int in int$from_to(population$low(current), final-1) do
	    for opponent: int in int$from_to(challenger+1, final) do
		print(int$unparse(challenger)
		      || " vs. " || int$unparse(opponent) || ":   ")
		
		winner : int := pit_v2(current, challenger, opponent)
		ratings[winner] := ratings[winner] + 1
		winner2: int := pit_v2(current, opponent, challenger)
		ratings[winner] := ratings[winner] + 1
		print(int$unparse(winner) || "   " || 
		      int$unparse(winner2) || "\n")
		
	      end
	  end
	
	% Sort current in order of descending fitness based on ratings
	% and eliminate the weaker portion of the population.
	
	new_pop: population:= population$create(1)
	cut_off: int := pop*2
	counter: int := 0
	while counter < top do
	    for fitness: int in array[int]$indexes(ratings) do
		if ratings[fitness] = cut_off then
		    population$addh(new_pop, current[fitness])
		    counter := counter + 1
		  end
	      end
	    cut_off := cut_off - 1
	  end
	while counter > top do
	    population$remh(new_pop)
	    counter := counter - 1
	  end
		    
	% generate new population from the best of the old,
	% mating, mutating, and randomness.
	
	for dummy_int2: int in int$from_to(1, randoms) do
	    population$addh(new_pop, static_evaluator$create_random())
	  end
	for dummy_int3: int in int$from_to(1, mutants) do
	    population$addh(new_pop, static_evaluator$create_mutant(best))
	    end
	current := population$copy(new_pop)
	tot: int:= population$high(new_pop)
	best:=current[1]
	second_best:=current[2]
	population$addh(current, static_evaluator$mate(best, second_best))
	
	% eliminate duplicates
	
	original_size: int:= population$high(current)
	new_pop:= population$copy(current)
	for index: int in int$from_to(1, original_size-1) do
	    check: static_evaluator := current[index]
	    for index2: int in
		int$from_to(index+1, population$high(current)) do
		if check = current[index2] then
		    current[index2] := population$remh(new_pop)
		    break
		  end   %  if statement
	      end  %  inner for loop
	  end  % outer for loop
	current:= population$copy(new_pop)
	
	static_evaluator$unparse(best)
      end   % for gen loop
    
    return(best)    
  end breed_v2

pit_v2 = proc(pop: population, challenger, opponent: int) returns(int)
    % requires: challenger and opponent are legitimate
    %   indeces of pop.
    % effects: Pits the static_evaluators of the
    %   population "pop" whose indeces are
    %   "challenger" and "opponent" against
    %   each other in a tournament style game of antichess and returns the 
    %   index of the winner.
    
    if match(pop[challenger], pop[opponent], 300000)
      then return(challenger)
      else return(opponent)
      end
  end pit_v2    

match = proc(e, e2: static_evaluator, play_time: int) returns (bool)
    % effects: Pits e and e2 against each other in a game
    %   of antichess and returns whether e1 is the winner.  Each player
    %   is given a time limit of play_time.
 
    winner: bool
    tstart, tfinish: realtime
    b: chess_board:= chess_board$create()
    white:computer_player:=
    computer_player$create(options${level: 5,
				    iswhite: true,
				    telestate: t_state$make_off(nil)},
			   "John Lenon")
    computer_player$set_evaluator(white, e)
    computer_player$reset_state(white, true)
    black:computer_player:=
    computer_player$create(options${level: 5,
				    iswhite:false,
				    telestate: t_state$make_off(nil)},
			   "George Harrison")
    computer_player$set_evaluator(black, e2)
    computer_player$reset_state(black, true)
    white_time: int := play_time
    black_time: int := play_time
    move: moveData
    while true do
	tstart:=realtime$now()
	if ~chess_board$can_move(b, whitePiece)
	  then
	    winner:= true
	    break
	  end
	print("White with " || int$unparse(white_time) || " milliseconds\n")
	move:= computer_player$make_move(white, white_time, b)
	chess_board$make_move(b, whitePiece, move)
	computer_player$opponent_moved(black, move)
	tfinish:=realtime$now()
	white_time:= (white_time -
		      (real$r2i(duration$to_milliseconds
				(realtime$difference(tfinish, tstart)))))
	print(chess_board$unparse(b))
	print("white:  " ||
	      int$unparse(static_evaluator$evaluate(e,b,whitePiece))
	      || "       black:  " ||
	      int$unparse(static_evaluator$evaluate(e,b,blackPiece))
	      || "\n")
	print("White now has " || int$unparse(white_time)||" milliseconds\n")
	if white_time <= 0
	  then 
	    winner:=false
	    break
	  end
	tstart:=realtime$now()
	if ~chess_board$can_move(b, blackPiece)
	  then
	    winner:=false
	    break
	  end
	print("Black with " || int$unparse(black_time) || " milliseconds\n")
	move:= computer_player$make_move(black, black_time, b)
	chess_board$make_move(b, blackPiece, move)
	computer_player$opponent_moved(white, move)
	tfinish:=realtime$now()
	black_time:= (black_time -
		      (real$r2i(duration$to_milliseconds
				(realtime$difference(tfinish, tstart)))))
	print("white:  " ||
	      int$unparse(static_evaluator$evaluate(e,b,whitePiece))
	      || "       black:  " ||
	      int$unparse(static_evaluator$evaluate(e,b,blackPiece))
	      || "\n")
	print(chess_board$unparse(b))
	print("Black now has " || int$unparse(black_time)||" milliseconds\n")
	if black_time <= 0
	  then 
	    winner:=true
	    break
	  end
      end % while true do
    return(winner)
  end match

test_se = proc(e: static_evaluator, d: int)
    % requires d > 0
    % effects: Tests the static_evaluator cluster using d,c, and e as a basis.
    % modifies: b
    
    b: chess_board:=chess_board$create()
    c: pieceColor:=whitePiece
    for fr, fc, tr, tc: int, uinfo: undoMoveInfo
	in chess_board$all_possible_moves(b, c) do
	print(chess_board$unparse(b))
	print("white:  " ||
	      int$unparse(static_evaluator$evaluate(e,b,whitePiece))
	      || "       black:  " ||
	      int$unparse(static_evaluator$evaluate(e,b,blackPiece))
	      || "\n")
      end
    
  end test_se