computer_player = cluster is create, opponent_moved, make_move, reset_state,
    get_options, set_options, get_name, set_name, get_evaluator,
    set_evaluator, get_color
    
    % Overview: computer_player is a mutable data type representing a
    % computer anti-chess player.  Given the state of an anti-chess game,
    % it is able to propose an "intelligent" move. The related machine_player
    % data structure is implemented as a wrapper around this data structure
    % and the chess_board data structure.
    
    % We use this, rather than machine_player, for two reasons.  First,
    % since the arbiter can pass our computer_player the chess_board data
    % structure, we don't have to keep a redundant copy of all that
    % information (as we would have to with machine_player).  Second,
    % machine_player requires you to pass information to it in a
    % human-readable format, which is silly, and it breaks down the
    % abstraction barrier between the strategy and interface modules.
    
    % Uses the same options data structure as machine_player
    
    % written by stevenj and twm
    
    rep = record[opts: options, name: string, evaluator: static_evaluator,
		 moves: int, nodes: real, reset: bool, ncount: real,
		 tm: real, limit: real]
    
    % Abstraction function: A typical computer_player is a set
    % containing opts (of type options) which describe the
    % computer_player's options, a name for the computer_player (of
    % type string), and a static_evaluator which the computer_player
    % uses in the determination of a strategy.  Opts is a struct
    % containing the level (type int) which describes the level
    % of skill with which the computer_player plays 
    % (with higher numbers indicating more skill) and "iswhite" which
    % is a boolean flag which indicates the color of the computer_player.
    % Moves is the number of times the player has been called to make
    % a move since the last call to reset_state.  Reset is a boolean flag
    % which indicates whether the internal state has been reset since
    % the game has started.  Nodes is the number of nodes in the game
    % tree that the computer_player expects to search through on
    % each turn.  Ncount is the total number of nodes that the computer_player
    % has searched through since the start of the last game.  Tm is
    % the amount of time spent searching nodes inside the procedure
    % make_move since the last call to reset state.  Limit is the total time
    % that a game should take in milliseconds.
    % The abstraction function
    % is:
    %   A(r) = {[level, iswhite], name, evaluator,
    %            moves, nodes, reset, ncount, tm, limit]}
    
    % Rep. Invariants:
    %  * 1 <= level <= 5
    %  * moves = # of calls to make_move since most recent reset_state,
    %              or since create, whichever is more recent
    %  * ncount = # of nodes searched since the last call to reset_state,
    %              or since create, whichever is more recent
    %  * tm = the time (in milliseconds) spent searching nodes inside
    %              make_move since the last call to reset_state, or since
    %              create, whichever was more recent.
    %  * reset = False if and only if the last call to reset_state 
    %              was made with the flag new_game being true.
    %  * limit = The time passed to computer_player$make_move after the
    %              last call to reset_state or create
    
    max_time = 300000 % 5 minutes
    rmax_time= 300000.0 % rmax_time: real:= real$i2r(max_time)
    panic_time = 45000 % 45 seconds
    r3panic_time = 135000.0 % : real:= 3.0 * real$i2r(panic_time)
    white_best_first = moveData${fromrow: 2,
				 fromcol: 8,
				 torow: 4,
				 tocol: 8}
    black_best_first = moveData${fromrow: 7,
				 fromcol: 8,
				 torow: 5,
				 tocol: 8}
    white_best_2nd = moveData${fromrow: 4,
			       fromcol: 8,
			       torow: 5,
			       tocol: 8}
    white_best_2nd_2 = moveData${fromrow: 2,
				 fromcol: 7,
				 torow: 4,
				 tocol: 7}
    
    % Variables whose scope is the entire cluster.  These variables
    % are defined outside of procedures so that maximize and minimize
    % can be called without passing many parameters (to increase
    % efficeincy).  These procedures are not visible outside the cluster
    % and these variables threrefore do not hinder the implimentation
    % in any way.
    
    own b: chess_board
    own clr: pieceColor
    own clr2: pieceColor
    own evlt: static_evaluator
    own actual: int:= 0
    
    create = proc(the_options: options, the_name: string) returns(cvt)
	% effects: returns a new computer_player with options described
	%          by the_options and name the_name.  It will have the
	%          default static_evaluator to start with.  If the level
	%          field in the_options is not in the range [1, 5], the
	%          computer_player returned has the closest legal level
	%          to the desired level (e.g., calling create with a level
	%          of -3 will cause the level to be set at 1, and calling
	%          create with a level of 7 will cause the level to be set
	%          at 5).
	
	e: static_evaluator
	if the_options.level < 4 then
	    e:=static_evaluator$parse(10,10,10,10,10,1,10000)  
	  else
	    if the_options.level = 6 then
		e:=static_evaluator$parse(2,3,2,2,2,1,10000)
	      else
		e:=static_evaluator$create()
	      end
	  end
	moves: real:= static_evaluator$get_anticipation(e)
	
	%  (msec/move)*(nodes/msec) = nodes/move
	
	n: real:= (rmax_time/moves) * callibrate_nodes(e, 300.0)
	p:rep:=rep${opts: options${level:int$max(1, int$min(5, the_options.level)),
				   iswhite: the_options.iswhite,
				   telestate: the_options.telestate},
		    name:the_name,
		    evaluator:e,
		    moves: 0,
		    nodes: n,
		    reset: true,
		    ncount: 0.0,
		    tm: 0.0,
		    limit: rmax_time}
	reset_state(up(p), false)
	return(p)
      end create
    
    get_name = proc(p: cvt) returns(string)
	% effects: Returns a string name for the computer player
	return(p.name)
      end get_name

    set_name = proc(p: cvt, new_name: string)
	% modifies: p
	%  effects: Sets the string name for the computer player
	p.name := new_name
      end set_name
    
    get_options = proc(p: cvt) returns(options)
	% effects: Returns the options for p
	return(p.opts) % does not reveal the rep since options is immutable
      end get_options
    
    set_options = proc(p: cvt, new_opts: options)
	% modifies: p
	%  effects: Sets p's options to new_opts.  If the level field in
	%     new_opts is not in the range [1, 5], p's options are set
	%     to the closest legal level.
	
	e: static_evaluator
	if new_opts.level < 4 then
	    e:=static_evaluator$parse(10,10,10,10,10,1,10000)  
	  else
	    if new_opts.level = 6 then
		e:=static_evaluator$parse(2,3,2,2,2,1,10000)
	      else
		e:=static_evaluator$create()
	      end
	  end
	p.nodes := (p.nodes * static_evaluator$get_anticipation(p.evaluator)/
		    static_evaluator$get_anticipation(e))
	p.evaluator := e
	p.opts := options${level: int$max(1, int$min(5, new_opts.level)),
			   iswhite: new_opts.iswhite,
			   telestate: new_opts.telestate}
      end set_options
    
    get_evaluator = proc(p: cvt) returns(static_evaluator)
	% effects: Returns the static evaluator p uses
	return(p.evaluator) % doesn't reveal rep: static_evaluator immutable
      end get_evaluator
    
    set_evaluator = proc(p: cvt, e: static_evaluator)
	% modifies: p
	%  effects: Sets the static evaluator used by p
	
	p.evaluator := e;  % doesn't reveal rep: static_evaluator immutable
	moves: real:= static_evaluator$get_anticipation(e)
	
	%  (msec/move)*(nodes/msec) = nodes/move
	p.nodes:= p.limit/moves * callibrate_nodes(e, 300.0)
      end set_evaluator
    
    callibrate_nodes = proc(e: static_evaluator, tm: real) returns(real)
	% effects:  Returns the speed of the machine that the computer_player
	%   is on in nodes/millisecond.  The timing test is run for at least
	%   tm milliseconds.
	
	t:real:=0.0
	total:real:=0.0
	tstart, tfinish: realtime
	tstart:=realtime$now()
	bd: chess_board:=chess_board$create()
	while t < tm do  % run for at least tm milliseconds
	    clr:=whitePiece
	    clr2:=blackPiece
	    evlt:=e
	    b:=bd
	    maximize_position(-10000000, 10000000, 100.0)
	    total:=total+100.0
	    tfinish:=realtime$now()
	    t:=duration$to_milliseconds(realtime$difference(tfinish, tstart))
	  end
	return(5.0*total/t)
      end callibrate_nodes
	
    reset_state = proc(p: cvt, new_game: bool)
	% modifies: p
	%  effects: Resets any internal state that p may be holding
	%           regarding the current game.  This must be done when
	%           a new game is started, for example.  The flag
	%           new_game indicates whether this reset_state
	%           is being called because a new game is being started.
	
	p.reset := bool$not(new_game)
	p.moves := 0
	p.ncount := 0.0
	p.tm := 0.0
	p.nodes := callibrate_nodes(p.evaluator, 300.0)
      end reset_state
    
    opponent_moved = proc(p: cvt, m: moveData)
	% requires: m is a valid move for p's opponent
	% modifies: p
	%  effects: Updates p's internal state to reflect the fact that
	%           p's opponent has made the move m.
      end opponent_moved
    
    maximize_position = proc(alpha, beta: int , nodes:real) returns(int)
	% effects: Returns the maximizing score
	%          that clr is guaranteed at the current node.
	%          Returns the number of nodes that are actually searched.
	%          Note:  the score is only heuristic and is not
	%          a guarantee on actual fitness.
	%          
	%          Also, increments actual by the actual number of node
	%          searched.
	% modifies: alpha, beta, actual
	
	val: int
	for ri,ci,rn,cn:int,uinfo:undoMoveInfo in
	    chess_board$all_possible_moves(b, clr) do
	    actual:=actual + 1
	    n: int:=chess_board$count_possible_moves(b, clr2)
	    if n=0 then val:=-10000000 
	      else
		nds:real:=nodes / real$i2r(n)
		if nds > 1.0 then
		    val:=minimize_position(alpha, beta, nds)
		  else
		    val:=static_evaluator$evaluate(evlt,b,clr)
		  end
	      end % if n = 0...
	    if val > alpha then
		alpha := val
	      end
	    if alpha >= beta then
		chess_board$undo_move(b, uinfo)
		break
	      end % if alpha ...
	  end % for ri ...
	return(alpha)
      end maximize_position
    
    minimize_position = proc(alpha, beta: int, nodes:real) returns(int)
	% effects: Returns the minimizing score
	%          that clr is guaranteed at the current node.
	%          Note:  the score is only heuristic and is not
	%          a guarantee on actual fitness.
	%          
	%          Also, increments actual by the actual number of node
	%          searched.
	% modifies: alpha, beta, actual
	
	val: int
	for ri,ci,rn,cn:int,uinfo:undoMoveInfo in
	    chess_board$all_possible_moves(b, clr2) do
	    actual:=actual + 1
	    n: int:= chess_board$count_possible_moves(b, clr)
	    if n=0 then val:=20000000
	      else
		nds:real:=nodes / real$i2r(n)
		if nds > 1.0 then
		    val:=maximize_position(alpha, beta, nds)
		  else
		    val:=static_evaluator$evaluate(evlt,b,clr)
		  end
	      end % if n=0...
	    if val < beta then
		beta := val
	      end
	    if alpha >= beta then
		chess_board$undo_move(b, uinfo)
		break
	      end % if alpha ...
	  end % for ri, rc ...
	return(beta)
      end minimize_position
    
    make_move = proc(p: cvt, tleft: int, board: chess_board) returns(moveData)
	% requires: p's state must be current for the given board; i.e.
	%           either opponent_moved was called for each move of
	%           p's opponent, or reset_state was called since the last
	%           move or change to the board.  tleft is the amount of
	%           time the computer player has left on its clock (millisecs).
	% modifies: p, bfr, bfc, btr, btc, clr, clr2, evlt, b
	%  effects: Given p's internal state, and the chess_board, board,
	%           returns p's move.  May change p's internal state.  If
	%           no move is possible, returns the empty move.
	
	% This procedure will do a min-max search using p.evaluator
	% as the board static evaluator.
	
	
	% recalibrate p.nodes
	
	tstart, tfinish: realtime
	tstart:=realtime$now()
	if p.ncount ~= 0.0
	  then
	    p.nodes:= ((p.ncount / p.tm) *
		       (p.limit/
			static_evaluator$get_anticipation(p.evaluator)))
	  else
	    p.limit:=real$i2r(tleft)
	  end
	p.moves:=p.moves+1
	
	% Special cases when the number of possible moves is 0 or 1
	
	clr:=get_color(up(p))
	n:int
	move: moveData
	n:=chess_board$count_possible_moves(board, clr)
	if n=1 then
	    the_move: moveData
	    for fr, fc, tr, tc: int, ufoo: undoMoveInfo in
		chess_board$all_possible_moves(board, clr) do
		the_move:=moveData${fromrow:fr,
				    fromcol:fc,
				    torow:tr,
				    tocol:tc}
	      end
	    return(the_move)
	  end
	if n=0 then return(moveData${fromrow:0,
				     fromcol:0,
				     torow:0,
				     tocol:0})
	  end
	
	% first move is hardwired into the system
	
	if p.moves = 1
	  then
	    bd: chess_board := chess_board$create()
	    if p.opts.iswhite
	      then
		if board = bd then % do white's first move
		    return(white_best_first)
		  end % if board ...
	      else % do blacks first move
		for fr, fc, tr, tc: int, fooInfo: undoMoveInfo in
		    chess_board$all_possible_moves(bd, whitePiece) do
		    if board = bd then
			return(black_best_first)
		      end % if board ...
		  end % if p.opts
	      end % if p.moves
	    
	    % second move for white is hardwired into the system
	    % The best second move for white happens to be the same
	    % in all cases except two.  In the first case black has
	    % moved its pawn in column 7 out to row 5 and white must
	    % take it.  This is covered by the one move optimization.
	    % The only other case is when black moves its pawn in column
	    % 8 to row 5 blocking white's destination.  This is
	    % covered below by checking to see if this spot is empty.
	    
	  else % if p.moves = 1
	    if false then
	    if p.moves = 2 cand p.opts.iswhite
	      then
		bd: chess_board:=chess_board$create()
		chess_board$make_move(bd, whitePiece, white_best_first)
		for foo1, foo2, foo3, foo4: int, foo5:undoMoveInfo in
		    chess_board$all_possible_moves(bd, blackPiece) do
		    if bd = board then
			if ~chess_board$spot_empty(bd, 5, 8) then
			    return(white_best_2nd_2)
			  else return(white_best_2nd)
			  end % if ~chess_board$spot...
		      end % if bd ...
		  end % for foo1...
	      end % if p.moves = 2
	      end
	  end % if p.moves = 1
	
	%  move must be determined with a minimax search
	
	clr2:=pieceColor$not(clr)
	evlt:=p.evaluator
	b:=board
	no: real:=p.nodes
	if p.opts.level = 5 then
	  else if p.opts.level = 4 then
		no:=8000.0 % pick in range of 80000.0 - 
	      else if p.opts.level = 3 then
		    no:= 450.0 % pick in range of 400.0 - 500.0
		  else if p.opts.level = 2 then
			no:= 45.0 % pick in range of 40 - 45
		      else if p.opts.level = 1 then
			    no:= 0.0001 % no look-ahead
			  end
		      end
		  end
	      end
	  end
		
	% if the panic time is reached used 2/5 of time_left
	if tleft < panic_time then
	    no:=(no*static_evaluator$get_anticipation(evlt)*.4*
		 real$i2r(tleft)/p.limit)
	  end 
	
	r_n: real:=real$i2r(n)
	no:=no/r_n
	no_16:real:=no/16.0
	p.ncount:=p.ncount + no_16*r_n
	
	% maximization of depth 1 is built into this loop for
	% efficeincy in the maximize procedure
	
	% first do a mini-max search with 1/16 the desired nodes
	% to guard against time overflow
	
	nds: real
	alpha: int:=-10000000
	beta: int:= 10000000
	actual := 0
	bfr: int:=0
	bfc: int:=0
	btr: int:=0
	btc: int:=0
	val: int
	for ri,ci,rn,cn:int,uinfo:undoMoveInfo in
	    chess_board$all_possible_moves(b, clr) do
	    actual:=actual + 1
	    n1: int:=chess_board$count_possible_moves(b, clr2)
	    if n1=0 then val:=-10000000 
	      else
		nds:=no_16 / real$i2r(n1)
		if nds > 1.0 then
		    val:=minimize_position(alpha, beta, nds)
		  else
		    val:=static_evaluator$evaluate(evlt,b,clr)
		  end
	      end % if n1 = 0...
	    if val >= alpha then
		alpha := val
		bfr := ri
		bfc := ci
		btr := rn
		btc := cn
	      end
	    if alpha >= beta then
		chess_board$undo_move(b, uinfo)
		break
	      end % if alpha ...
	  end % for ri ...
	
	% now do the full search if there is enough time
	
	tfinish:=realtime$now()
	if duration$to_milliseconds(realtime$difference(tfinish, tstart)) <
	    0.25*p.limit/static_evaluator$get_anticipation(p.evaluator)
	  then
	    p.ncount:=p.ncount+no*r_n
	    alpha:=-10000000
	    beta:= 10000000
	    bfr:=0
	    bfc:=0
	    btr:=0
	    btc:=0
	    for ri2,ci2,rn2,cn2:int,uinfo2:undoMoveInfo in
		chess_board$all_possible_moves(b, clr) do
		actual:=actual + 1
		n2: int:=chess_board$count_possible_moves(b, clr2)
		if n2=0 then val:=-10000000 
		  else
		    nds:=no / real$i2r(n2)
		    if nds > 1.0 then
			val:=minimize_position(alpha, beta, nds)
		      else
			val:=static_evaluator$evaluate(evlt,b,clr)
		      end
		  end % if n2 = 0...
		if val >= alpha then
		    alpha := val
		    bfr := ri2
		    bfc := ci2
		    btr := rn2
		    btc := cn2
		  end
		if alpha >= beta then
		    chess_board$undo_move(b, uinfo2)
		    break
		  end % if alpha ...
	      end % for ri2 ...
	  else
	  end
	
	tfinish:=realtime$now()
	p.tm:=p.tm+duration$to_milliseconds(realtime$difference(tfinish,
								tstart))
	return(moveData${fromrow:bfr,
			 fromcol:bfc,
			 torow:btr,
			 tocol:btc})	
      end make_move

    get_color = proc(p: cvt) returns(piececolor)
	% effects:  returns the color of p.
	
	if options$get_iswhite(p.opts)
	  then return(whitePiece)
	  else return(blackPiece)
	  end     
	
      end get_color
    
    print = proc(message: string)
	% effects: Sends message to primary_output as a line.
	%   (Used as a debugging tool.)
	
	stream$putl(stream$primary_output(), message)
      end print
        
  end computer_player