/* 
 *   Gnome Nine Mens Morris
 *   Written by Dirk Farin <dirk.farin@gmx.de>
 * 
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include "tree.hh"
#include "util.hh"
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#include <assert.h>

#undef CONSOLE_DISP
#undef WATCH

#include <gtk/gtk.h>


void SearchAlgo::StopComputer()
{
  stop = true;
}

Move SearchAlgo::ComputerMove(int nNodes)
{
  stop = false;

  Move m;

#define MINDEPTH 9
#define MAXDEPTH 6

  //for (int depth=2;depth<=MINDEPTH;depth++)

  //int depth = MINDEPTH;

  d_nodes_visited=0;

  double e;
  for (int depth=2; d_nodes_visited < nNodes ; depth++)
    {
#ifdef CONSOLE_DISP
      cout << "searching depth: " << depth; cout.flush();
#endif
      e = Recurse(d_current_board,-99999.9,99999.9,depth,&m);
#ifdef CONSOLE_DISP
      cout << " (" << d_nodes_visited << " nodes)\n";
#endif
      if (abs((int)e)>100)
	break;

      if (stop)
	{
	  Move mm; mm.Reset(); return mm;
	}
    }

#ifdef CONSOLE_DISP
  cout << "eval: " << e << "  nodes searched: " << d_nodes_visited << endl;
#endif
  return m;
}


bool SearchAlgo::OpponentHasLost() const
{
  return d_current_board.OpponentHasLost();
}


bool SearchAlgo::CurrentHasLost() const
{
  return d_current_board.CurrentHasLost();
}


void indent(int n)
{
  while (n--) cout << " ";
}

double SearchAlgo::Recurse(const Board& board,double alpha,double beta,
			   int levels_to_go,Move* m)
{
#ifdef WATCH
  indent(MINDEPTH-levels_to_go); cout << "(" << alpha << " - " << beta << ") ";
  if (board.next == WHITE) cout << "WHITE "; else cout << "BLACK ";
#endif

  d_nodes_visited++;

  if (levels_to_go==0)
    {
      double e = d_eval->Eval(board);
#ifdef WATCH
      cout << " " << e << endl;
#endif
      assert(!m);
      return e;
    }


  // check for lost game

  if (board.CurrentHasLost())
    {
      double e;
      if (board.next==WHITE) e=-9999.9-levels_to_go;
      else e=+9999.9+levels_to_go;
#ifdef WATCH
      cout << e << endl;
#endif
      assert(!m);
      return e;
    }


  if (gtk_events_pending())
    gtk_main_iteration();

  if (stop)
    return 0.0;

  // internal node: expand node

  Board tmp;

  Move moves[200];
  int n_moves = board.GenMoves(moves,200);
  if (n_moves==0)
    {
      double e;
      if (board.next==WHITE) e=-9999.9-levels_to_go;
      else e=9999.9+levels_to_go;
#ifdef WATCH
      cout << e << endl;
#endif
      assert(!m);
      return e;
    }
  assert(n_moves<200);

  double best_eval;
  int    best_idx=0;  // =0 just in case that there is no valid move
  bool   move_found=false;

  if (board.next == WHITE)
    {
      best_eval = -99999.9;

      for (int i=0;i<n_moves;i++)
        {
	  if (best_eval>beta)
	    return best_eval;

          tmp=board;
          tmp.DoMove(moves[i]);


#ifdef WATCH
	  indent(MINDEPTH-levels_to_go);
	  char buf[10]; board.MoveToString(moves[i],buf); cout << buf;
	  if (levels_to_go>1) cout << endl;
#endif

          double eval = Recurse(tmp,alpha,beta,
                                levels_to_go-1,NULL);
	  if (stop)
	    return 0.0;

          if (eval>alpha) alpha=eval;
          
          if (eval > best_eval || (eval==best_eval && (rand()%2)))
            {
#ifdef WATCH
	      indent(MINDEPTH-levels_to_go); cout << "best\n";
#endif
              best_idx=i;
              best_eval=eval;
	      move_found=true;
            }
        }
    }
  else
    {
      best_eval = 99999.9;

      for (int i=0;i<n_moves;i++)
        {
	  if (best_eval<alpha)
	    return best_eval;

          tmp=board;
          tmp.DoMove(moves[i]);

#ifdef WATCH
	  indent(MINDEPTH-levels_to_go);
	  char buf[10]; board.MoveToString(moves[i],buf); cout << buf;
	  if (levels_to_go>1) cout << endl;
#endif

          double eval = Recurse(tmp,alpha,beta,
                                levels_to_go-1,NULL);
	  if (stop)
	    return 0.0;

          if (eval<beta) beta=eval;

          if (eval < best_eval || (eval==best_eval && (rand()%2)))
            {
#ifdef WATCH
	      indent(MINDEPTH-levels_to_go); cout << "best\n";
#endif
              best_idx=i;
              best_eval=eval;
	      move_found=true;
            }
        }
    }

  assert(move_found);

  if (m) *m = moves[best_idx];

  return best_eval;
}