/////////////////////////////////////////////////////////////////////////
// Game Playing using Minimax                                          //
// By: Nick Cash                                                       //
//                                                                     //
// Fall 2007                                                           //
// 810:161 - Aritifical Intelligence                                   //
//                                                                     //
// minimax.cpp - Contains the Minimax algorithm implementation         //
/////////////////////////////////////////////////////////////////////////

#include "game.h"

// Our search algorithm
cNode* MiniMax( cNode* node )
{
  cNode* ret = NULL;

  // if this is a leaf (ie, has an endgame value) return it
  if ( node->GetEGValue() != None )
   return node;

  // grab the min of all children
  if ( node->GetType() == Min )
  {
    ChildList::iterator iter;
    
    // iterate through children and run the algorithm on them too
    for ( iter = node->children.begin(); iter != node->children.end(); iter++ )
    {
       cNode* temp = MiniMax(*iter);

       // if ret is null or temp has a lower value then our return node
       if ( temp->GetEGValue() != None )
        if ( !ret || (temp->GetValue() < ret->GetValue()) )
         ret = temp;
    }
    
    return ret;
  }

  // grab the max of all children
  if ( node->GetType() == Max )
  {
    ChildList::iterator iter;

    // iterate through children and run the algorithm on them too
    for ( iter = node->children.begin(); iter != node->children.end(); iter++ )
    {
       cNode* temp = MiniMax(*iter);

       // if ret is null or temp has a lower value then our return node
       if ( temp->GetEGValue() != None )
        if ( !ret || (temp->GetValue() > ret->GetValue()) )
         ret = temp;
    }
    return ret;
  }
  
  // if we get this far we have an error
  Error( "MiniMax: Hit the end of the function." );
}

// Static evaluator
// Wins are ranked highest (most preferable), and the fewer moves are ranked higher
// Draws are static at 0
// If the node is a max node
short EvaluateNode( cNode* node )
{
  short x = 0;

  switch ( node->GetEGValue() )
  {
    case Win:
         x += 100/node->GetDepth(); // lower the depth, the faster/better the win
         break;

    case Draw:
         break;

    case None:
    default:
         Error("EvaluateNode -> GetEGValue switch, default case reached" );
  }

  // if its a Max node then its actually Min's move
  if ( node->GetType() == Max )
   x *= -1;

  return x;
}

// Starting point for building the game tree.
cNode* BuildGameTree( string s )
{
  cNode* root = new cNode(NULL, -1, 1, s.c_str());
  
  root->SetType(Max);
  root->SetEGValue(root->CheckEndGame());
  root->SetValue(0);
  
  // Start our recursive child generator
  GenerateChildren( root );
  
  return root;
}

// Recursive function that generates an X and O for each neutral space on a board
void GenerateChildren( cNode* node )
{
  cNode* n = NULL;
  NodeType type = (node->GetType() == Max ? Min : Max);
  
  // Loop through all cells of this board.
  // If we hit a Neutral cell, generate an X and an O and run the process on its kids
  for ( int i = 0; i <= MAX_CELL; i++ )
  {
    if ( node->GetCell(i) != Neutral )
     continue;
     
    // Grab our board string
    string s = node->GetBoard();
    
    // Generate X outcome first
    s[i] = 'x';
    n = new cNode( node, i, (node->GetDepth()+1), s.c_str());
    n->SetType(type);
    n->SetEGValue(n->CheckEndGame());
    
    if ( n->GetEGValue() != None )
        n->SetValue(EvaluateNode(n));
    else
        n->SetValue(0);
        
    node->children.push_back(n);
    GenerateChildren( n );

    // Now generate O
    s[i] = 'o';
    n = new cNode( node, i, (node->GetDepth()+1), s.c_str());
    n->SetType(type);
    n->SetEGValue(n->CheckEndGame());
    
    if ( n->GetEGValue() != None )
        n->SetValue(EvaluateNode(n));
    else
        n->SetValue(0);
        
    node->children.push_back(n);
    GenerateChildren( n );
  }
}