// FILE: game_engine.cxx
// Written by Michael Main (main@colorado.edu) Nov 23, 1999
// This program is a general game engine that can play any two-person
// strategy game by adding the two pieces specified below.
// Note that this version of the game engine uses minimax search, but does no
// implement alpha-beta pruning. The alpha-beta pruning is left to the
// inquisitive student to implement.
#include <stdlib.h>    // Provides EXIT_SUCCESS

// 1. STRATEGY PIECE:
// The following header file must provide these pieces of the game:
// 1a. A data type called state, which represents the state of a game.
// 1b. A data type called move, which represents a move of the game.
// 1c. Integer SEARCH_DEPTH: maximum level to search the game tree.
// 1d. Integer MAXIMUM_MOVES: maximum number of moves returned by compute_mov
// 1e. Integers PLAYER1, PLAYER2, EVAL_LIMIT.
// 1f. These functions:
//     void change_state(int who, move m, state& s);
//     void compute_legal_moves(int who, state s, move moves[], int& many_mov
//     int evaluate(int who, const state& s);
//       The value of who can be the constant PLAYER1 or PLAYER2. The return 
//       (with a magnitude up to EVAL_LIMIT) indicates how good the specified
//       is to this player.
//     void initialize_state(state& s);
//     bool is_game_over(const state& s);
//     bool is_legal(int who, move m, const state& s);
//     int winner(const state& s);
#include "strategy.h"
using namespace std;

// 2. DISPLAY PIECE:
// The following header file must provide these functions:
//   void clear_message( );
//   void draw_state(const state& s);
//   void finish(const state& s);
//   void get_user_move(move& m);
//   void initialize_display( );
//   void write(const char message[]);
#include "display.h"

// The following functions are provided by this game engine:
int eval_with_minimax(int who, move m, state s, int level, int best_sibling);
int main( );
void make_computer_move(int who, state& s);
void make_user_move(int who, state& s);


int main( )
{
    state s;

    initialize_display( );
    initialize_state(s);
    draw_state(s);
    
    while (!is_game_over(s))
    {
	make_user_move(PLAYER1, s);
	draw_state(s);
	if (is_game_over(s))
	    break;
	write("Computer making move...");
	make_computer_move(PLAYER2, s);
	draw_state(s);
	clear_message( );
    }

    finish(s);
    return EXIT_SUCCESS;
}

// Function to evaluate how good a move appears to a particular player.
//   int who:     The player who is about to make the move
//   move m:      The move that the player will make
//   state s:     The state of the game before the player's move
//   int level:   How deep the minimax search should go to evaluate the move.
// The return value is large (up to EVAL_LIMIT) if move is a good one for who;
// it is small (down to -EVAL_LIMIT) if the move is a bad one for who.
int eval_with_minimax(int who, move m, state s, int level, int best_sibling)
{
    int i;                             // Loop control variable
    int value;                         // Evaluation of one board position
    int best_value = -(EVAL_LIMIT + 1);// Evaluation of best opponent move
    move attempts[MAXIMUM_MOVES];      // All possible opponent moves
    int many_moves;                    // Number of possible opponent moves
    int opponent = -1 * who;           // The opponent (PLAYER2, PLAYER1)
    int who_won;                       // Winner (if the game is over)
    
    // Make the move and compute the opponent's possible reactions.
    change_state(who, m, s);
    compute_legal_moves(opponent, s, attempts, many_moves);

    // Check whether the game is over. If so, it is easy to evaluate:
    if (many_moves == 0)
    {
	who_won = winner(s);
	if (who == who_won)
	    return EVAL_LIMIT;
	else if (opponent == who_won)
	    return -EVAL_LIMIT;
	else
	    return 0;
    }
    
    // When level has dropped to 0, evaluate how good s looks to who right now.
    if (level == 0)
	return evaluate(who, s);

    // With level above zero, try every possible opponent reaction to the move.
    // Keep the value of the best of these moves from opponent's perspective.
    for (i = 0; i < many_moves; i++)
    {
	value = eval_with_minimax(opponent, attempts[i], s, level-1, best_value);
	if (-value <= best_sibling)
	    return -(EVAL_LIMIT-1);
	if (value > best_value)
	    best_value = value;
    }

    // The value has been calculated from the opponent's perspective. The answer
    // we return should be from who's perspective, so multiply times -1:
    return -best_value;
}

void make_computer_move(int who, state& s)
{
    int i;
    int many_moves;
    move attempts[MAXIMUM_MOVES];
    int value;
    int best_value = -(EVAL_LIMIT + 1);
    int best_index;

    // Compute all legal moves that who could make.
    compute_legal_moves(who, s, attempts, many_moves);
    
    if (many_moves > 0)
    {
	// Evaluate each possible legal move, saving the index of the best move
	// in best_index and saving its value in best_value.
	for (i = 0; i < many_moves; i++)
	{
	    value = eval_with_minimax(who, attempts[i], s, SEARCH_DEPTH, best_value);
	    if (value > best_value)
	    {
		best_value = value;
		best_index = i;
	    }
	}

	// Make the best move.
	change_state(who, attempts[best_index], s);
    }
}

void make_user_move(int who, state& s)
{
    move m;

    get_user_move(m);
    while (!is_legal(who, m, s))
    {
	write("Illegal move");
	get_user_move(m);
    }
    change_state(who, m, s);
}