/* Yo Emacs, this -*- C++ -*-
 *******************************************************************
 *******************************************************************
 *
 *
 * KREVERSI
 *
 *
 *******************************************************************
 *
 * A Reversi (or sometimes called Othello) game
 *
 *******************************************************************
 *
 * Created 1997 by Mario Weilguni <mweilguni@sime.com>. This file
 * is ported from Mats Luthman's <Mats.Luthman@sylog.se> JAVA applet.
 * Many thanks to Mr. Luthman who has allowed me to put this port
 * under the GNU GPL. Without his wonderful game engine kreversi
 * would be just another of those Reversi programs a five year old
 * child could beat easily. But with it it's a worthy opponent!
 *
 * If you are interested on the JAVA applet of Mr. Luthman take a
 * look at http://www.sylog.se/~mats/
 *
 *******************************************************************
 *
 * This file is part of the KDE project "KREVERSI"
 *
 * KREVERSI 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, or (at your option)
 * any later version.
 *
 * KREVERSI 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 KREVERSI; see the file COPYING.  If not, write to
 * the Free Software Foundation, 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 *
 *******************************************************************
 */

// The class Engine produces moves from a Game object through calls to the
// function ComputeMove().
//
// First of all: this is meant to be a simple example of a game playing
// program. Not everything is done in the most clever way, particularly not
// the way the moves are searched, but it is hopefully made in a way that makes
// it easy to understand. The function ComputeMove2() that does all the work
// is actually not much more than a hundred lines. Much could be done to
// make the search faster though, I'm perfectly aware of that. Feel free
// to experiment.
//
// The method used to generate the moves is called minimax tree search with
// alpha-beta pruning to a fixed depth. In short this means that all possible
// moves a predefined number of moves ahead are either searched or refuted
// with a method called alpha-beta pruning. A more thorough explanation of
// this method could be found at the world wide web at http:
// //yoda.cis.temple.edu:8080/UGAIWWW/lectures96/search/minimax/alpha-beta.html
// at the time this was written. Searching for "minimax" would also point
// you to information on this subject. It is probably possible to understand
// this method by reading the source code though, it is not that complicated.
//
// At every leaf node at the search tree, the resulting position is evaluated.
// Two things are considered when evaluating a position: the number of pieces
// of each color and at which squares the pieces are located. Pieces at the
// corners are valuable and give a high value, and having pieces at squares
// next to a corner is not very good and they give a lower value. In the
// beginning of a game it is more important to have pieces on "good" squares,
// but towards the end the total number of pieces of each color is given a
// higher weight. Other things, like how many legal moves that can be made in a
// position, and the number of pieces that can never be turned would probably
// make the program stronger if they were considered in evaluating a position,
// but that would make things more complicated (this was meant to be very
// simple example) and would also slow down computation (considerably?).
//
// The member m_board[10][10]) holds the current position during the
// computation. It is initiated at the start of ComputeMove() and
// every move that is made during the search is made on this board. It should
// be noted that 1 to 8 is used for the actual board, but 0 and 9 can be
// used too (they are always empty). This is practical when turning pieces
// when moves are made on the board. Every piece that is put on the board
// or turned is saved in the stack m_squarestack (see class SquareStack) so
// every move can easily be reversed after the search in a node is completed.
//
// The member m_bc_board[][] holds board control values for each square
// and is initiated by a call to the function private void SetupBcBoard()
// from Engines constructor. It is used in evaluation of positions except
// when the game tree is searched all the way to the end of the game.
//
// The two members m_coord_bit[9][9] and m_neighbor_bits[9][9] are used to
// speed up the tree search. This goes against the principle of keeping things
// simple, but to understand the program you do not need to understand them
// at all. They are there to make it possible to throw away moves where
// the piece that is played is not adjacent to a piece of opposite color
// at an early stage (because they could never be legal). It should be
// pointed out that not all moves that pass this test are legal, there will
// just be fewer moves that have to be tested in a more time consuming way.
//
// There are also two other members that should be mentioned: Score m_score
// and Score m_bc_score. They hold the number of pieces of each color and
// the sum of the board control values for each color during the search
// (this is faster than counting at every leaf node).
//

// The classes SquareStackEntry and SquareStack implement a
// stack that is used by Engine to store pieces that are turned during
// searching (see ComputeMove()).
//
// The class MoveAndValue is used by Engine to store all possible moves
// at the first level and the values that were calculated for them.
// This makes it possible to select a random move among those with equal
// or nearly equal value after the search is completed.


#include "Engine.h"
#include <qapplication.h>

const int Engine::LARGEINT = 99999;
const int Engine::ILLEGAL_VALUE = 8888888;
const int Engine::BC_WEIGHT = 3;

inline void SquareStackEntry::setXY(int x, int y) {
  m_x = x;
  m_y = y;
}

#if !defined(__GNUC__)

ULONG64::ULONG64() : QBitArray(64) {
  fill(0);
}

ULONG64::ULONG64( unsigned int value ) : QBitArray(64) {
  fill(0);
  for(int i = 0; i < 32; i++) {
    setBit(i, (bool)(value & 1));
    value >>= 1;
  }
}

void ULONG64::shl() {
  for(int i = 63; i > 0; i--)
    setBit(i, testBit(i-1));
  setBit(0, 0);
}

#endif


SquareStackEntry::SquareStackEntry() {
  setXY(0,0);
}


SquareStack::SquareStack() {
  init(0);
}


SquareStack::SquareStack(int size) {
  init(size);
}


void SquareStack::resize(int size) {
  m_squarestack.resize(size);
}


void SquareStack::init(int size) {
  resize(size);
  m_top = 0;
  for (int i=0; i<size; i++)
    m_squarestack[i].setXY(0,0);
}


inline SquareStackEntry SquareStack::Pop() {
  return m_squarestack[--m_top];
}


inline void SquareStack::Push(int x, int y) {
  m_squarestack[m_top].m_x = x;
  m_squarestack[m_top++].m_y = y;
}


inline void MoveAndValue::setXYV(int x, int y, int value) {
  m_x = x;
  m_y = y;
  m_value = value;
}


MoveAndValue::MoveAndValue() {
  setXYV(0,0,0);
}


MoveAndValue::MoveAndValue(int x, int y, int value) {
  setXYV(x, y, value);
}


Engine::Engine(int st, int sd) : SuperEngine(st, sd) {
  SetupBcBoard();
  SetupBits();
}


Engine::Engine(int st) : SuperEngine(st) {
  SetupBcBoard();
  SetupBits();
}


Engine::Engine() : SuperEngine(1) {
  SetupBcBoard();
  SetupBits();
}


// keep GUI alive
void Engine::yield() {
  qApp->processEvents();
}

Move Engine::computeMove(Game g) {
  m_exhaustive = false;

  Player player = g.whoseTurn();

  if (player == Nobody)
    return Move(-1, -1, Nobody);

  // Figure out the current score
  m_score.set(White, g.score(White));
  m_score.set(Black, g.score(Black));
  // If the game just started...
  if (m_score.score(White) + m_score.score(Black) == 4)
    return ComputeFirstMove(g);

  // JAVA m_board = new int[10][10];
  //m_squarestack = new SquareStack(3000); // More than enough...
  m_squarestack.init(3000);
  m_depth = m_strength;

  if (m_score.score(White) + m_score.score(Black) +
      m_depth + 3 >= 64)
    m_depth =
      64 - m_score.score(White) - m_score.score(Black);
  else if (m_score.score(White) + m_score.score(Black) +
	   m_depth + 4 >= 64)
    m_depth += 2;
  else if (m_score.score(White) + m_score.score(Black) +
	   m_depth + 5 >= 64)
    m_depth++;

  if (m_score.score(White) + m_score.score(Black) +
      m_depth >= 64) m_exhaustive = true;

  m_coeff =
    100 - (100*
	   (m_score.score(White) + m_score.score(Black) +
	    m_depth - 4))/60;

  m_nodes_searched = 0;

  for (uint x=0; x<10; x++)
    for (uint y=0; y<10; y++)
      m_board[x][y] = Nobody;

  for (uint x=1; x<9; x++)
    for (uint y=1; y<9; y++)
      m_board[x][y] = g.player(x, y);

  m_bc_score.set(White, CalcBcScore(White));
  m_bc_score.set(Black, CalcBcScore(Black));

  ULONG64 playerbits = ComputeOccupiedBits(player);
  ULONG64 opponentbits = ComputeOccupiedBits(opponent(player));

  int maxval = -LARGEINT;
  int max_x = 0;
  int max_y = 0;

  MoveAndValue moves[60];
  int number_of_moves = 0;
  int number_of_maxval = 0;

  setInterrupt(false);

  ULONG64 null_bits;
  null_bits = 0;

  //struct tms tmsdummy;
  //long starttime = times(&tmsdummy);
  // Compute this once at the start of the loops.
//  int high = 20 - m_strength;

  for (int x=1; x<9; x++)
    for (int y=1; y<9; y++)
      if (m_board[x][y] == Nobody &&
	  (m_neighbor_bits[x][y] & opponentbits) != null_bits)
	{

	  int val = ComputeMove2(x, y, player, 1, maxval,
				 playerbits, opponentbits);

	  if (val != ILLEGAL_VALUE)
	    {
	      moves[number_of_moves++].setXYV(x, y, val);

	      if (val > maxval)
		{
		  // Make it so it is easy for us to "miss" something.
		  // i.e. more relistic.  Also makes m_strength mean more.
	          int randi = m_random.getLong(7);
		  if(maxval == -LARGEINT ||
                    randi < (int)m_strength ){
	            maxval = val;
		    max_x = x;
		    max_y = y;
		    number_of_maxval = 1;
		  }
		}
	      else if (val == maxval) number_of_maxval++;
	    }

	  if (interrupt()) break;
	}

  // long endtime = times(&tmsdummy);

  if (number_of_maxval > 1)
    {
      int r = m_random.getLong(number_of_maxval) + 1;

      int i;

      for (i=0; i < number_of_moves; i++)
	if (moves[i].m_value == maxval && --r <= 0) break;

      max_x = moves[i].m_x;
      max_y = moves[i].m_y;
    }

  if (interrupt()) {
    return Move(-1, -1, Nobody);
  } else if (maxval != -LARGEINT) {
    return Move(max_x, max_y, player);
  } else {
    return Move(-1, -1, Nobody);
  }
}


Move Engine::ComputeFirstMove(Game g) {
  int r;
  Player player = g.whoseTurn();

  r = m_random.getLong(4) + 1;

  if (player == White)
    {
      if (r == 1) return Move(3, 5, player);
      else if (r == 2) return  Move(4, 6, player);
      else if (r == 3) return  Move(5, 3, player);
      else return  Move(6, 4, player);
    }
  else
    {
      if (r == 1) return  Move(3, 4, player);
      else if (r == 2) return  Move(5, 6, player);
      else if (r == 3) return  Move(4, 3, player);
      else return  Move(6, 5, player);
    }
}


int Engine::ComputeMove2(int xplay, int yplay, Player player, int level,
			 int cutoffval, ULONG64 playerbits,
			 ULONG64 opponentbits)
{
  int number_of_turned = 0;
  SquareStackEntry mse;
  Player opponent = ::opponent(player);

  m_nodes_searched++;

  m_board[xplay][yplay] = player;
  playerbits |= m_coord_bit[xplay][yplay];
  m_score.inc(player);
  m_bc_score.add(player, m_bc_board[xplay][yplay]);

  ///////////////////
  // Turn all pieces:
  ///////////////////

  for (int xinc=-1; xinc<=1; xinc++)
    for (int yinc=-1; yinc<=1; yinc++)
      if (xinc != 0 || yinc != 0)
	{
	  int x, y;

	  for (x = xplay+xinc, y = yplay+yinc; m_board[x][y] == opponent;
	       x += xinc, y += yinc)
	    ;

	  if (m_board[x][y] == player)
	    for (x -= xinc, y -= yinc; x != xplay || y != yplay;
		 x -= xinc, y -= yinc)
	      {
		m_board[x][y] = player;
		playerbits |= m_coord_bit[x][y];
		opponentbits &= ~m_coord_bit[x][y];
		m_squarestack.Push(x, y);
		m_bc_score.add(player, m_bc_board[x][y]);
		m_bc_score.sub(opponent, m_bc_board[x][y]);
		number_of_turned++;
	      }
	}

  int retval = -LARGEINT;

  if (number_of_turned > 0)
    {
      //////////////
      // Legal move:
      //////////////

      m_score.add(player, number_of_turned);
      m_score.sub(opponent, number_of_turned);

      if (level >= m_depth) retval = EvaluatePosition(player); // Terminal node
      else
	{
	  int maxval = TryAllMoves(opponent, level, cutoffval, opponentbits,
				   playerbits);

	  if (maxval != -LARGEINT) retval = -maxval;
	  else
	    {
	      ///////////////////////////////////////////////////////////////
	      // No possible move for the opponent, it is players turn again:
	      ///////////////////////////////////////////////////////////////
	      retval= TryAllMoves(player, level, -LARGEINT, playerbits,
				  opponentbits);

	      if (retval == -LARGEINT)
		{
		  ///////////////////////////////////////////////
		  // No possible move for anybody => end of game:
		  ///////////////////////////////////////////////

		  int finalscore =
		    m_score.score(player) - m_score.score(opponent);

		  if (m_exhaustive) retval = finalscore;
		  else
		    {
		      // Take a sure win and avoid a sure loss (may not be optimal):

		      if (finalscore > 0) retval = LARGEINT - 65 + finalscore;
		      else if (finalscore < 0) retval = -(LARGEINT - 65 + finalscore);
		      else retval = 0;
		    }
		}
	    }
	}

      m_score.add(opponent, number_of_turned);
      m_score.sub(player, number_of_turned);
    }

  /////////////////
  // Restore board:
  /////////////////

  for (int i = number_of_turned; i > 0; i--)
    {
      mse = m_squarestack.Pop();
      m_bc_score.add(opponent, m_bc_board[mse.m_x][mse.m_y]);
      m_bc_score.sub(player, m_bc_board[mse.m_x][mse.m_y]);
      m_board[mse.m_x][mse.m_y] = opponent;
    }

  m_board[xplay][yplay] = Nobody;
  m_score.sub(player, 1);
  m_bc_score.sub(player, m_bc_board[xplay][yplay]);

  if (number_of_turned < 1 || interrupt()) return ILLEGAL_VALUE;
  else return retval;
}


int Engine::TryAllMoves(Player opponent, int level, int cutoffval,
			ULONG64 opponentbits, ULONG64 playerbits)
{
  int maxval = -LARGEINT;

  // keep GUI alive
  yield();

  ULONG64 null_bits;
  null_bits = 0;

  for (int x=1; x<9; x++)
    {
      for (int y=1; y<9; y++)
	if (m_board[x][y] == Nobody &&
	    (m_neighbor_bits[x][y] & playerbits) != null_bits)
	  {
	    int val = ComputeMove2(x, y, opponent, level+1, maxval, opponentbits,
				   playerbits);

	    if (val != ILLEGAL_VALUE && val > maxval)
	      {
		maxval = val;
		if (maxval > -cutoffval || interrupt()) break;
	      }
	  }

      if (maxval > -cutoffval || interrupt()) break;
    }

  if (interrupt()) return -LARGEINT;
  return maxval;
}


int Engine::EvaluatePosition(Player player)
{
  int retval;

  Player opponent = ::opponent(player);
  int score_player = m_score.score(player);
  int score_opponent = m_score.score(opponent);

  if (m_exhaustive) retval = score_player - score_opponent;
  else
    {
      retval = (100-m_coeff) *
	(m_score.score(player) - m_score.score(opponent)) +
	m_coeff * BC_WEIGHT *
	(m_bc_score.score(player)-m_bc_score.score(opponent));
    }

  return retval;
}


void Engine::SetupBits()
{
  //m_coord_bit = new long[9][9];
  //m_neighbor_bits = new long[9][9];

  ULONG64 bits = 1;

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      {
	m_coord_bit[i][j] = bits;
#if !defined(__GNUC__)
	bits.shl();
#else
	bits *= 2;
#endif
      }

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      {
	m_neighbor_bits[i][j] = 0;

	for (int xinc=-1; xinc<=1; xinc++)
	  for (int yinc=-1; yinc<=1; yinc++)
	    if (xinc != 0 || yinc != 0)
	      if (i + xinc > 0 && i + xinc < 9 && j + yinc > 0 && j + yinc < 9)
		m_neighbor_bits[i][j] |= m_coord_bit[i + xinc][j + yinc];
      }
}


void Engine::SetupBcBoard()
{
  // JAVA m_bc_board = new int[9][9];

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      {
	if (i == 2 || i == 7) m_bc_board[i][j] = -1; else m_bc_board[i][j] = 0;
	if (j == 2 || j == 7) m_bc_board[i][j] -= 1;
      }

  m_bc_board[1][1] = 2;
  m_bc_board[8][1] = 2;
  m_bc_board[1][8] = 2;
  m_bc_board[8][8] = 2;

  m_bc_board[1][2] = -1;
  m_bc_board[2][1] = -1;
  m_bc_board[1][7] = -1;
  m_bc_board[7][1] = -1;
  m_bc_board[8][2] = -1;
  m_bc_board[2][8] = -1;
  m_bc_board[8][7] = -1;
  m_bc_board[7][8] = -1;
}


int Engine::CalcBcScore(Player player)
{
  int sum = 0;

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      if (m_board[i][j] == player)
	sum += m_bc_board[i][j];

  return sum;
}


ULONG64 Engine::ComputeOccupiedBits(Player player)
{
  ULONG64 retval = 0;

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      if (m_board[i][j] == player) retval |= m_coord_bit[i][j];

  return retval;
}