/* GNU Chess 5.0 - sort.c - move sorting code
   Copyright (c) 1999-2002 Free Software Foundation, Inc.

   GNU Chess is based on the two research programs 
   Cobalt by Chua Kong-Sian and Gazebo by Stuart Cracraft.

   GNU Chess 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.

   GNU Chess 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 GNU Chess; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.

   Contact Info: 
     bug-gnu-chess@gnu.org
     cracraft@ai.mit.edu, cracraft@stanfordalumni.org, cracraft@earthlink.net
*/
/*
 *
 */

#include <stdio.h>

#include "util.h"
#include "eval.h"
#include "bitboard.h"
#include "move.h"
#include "square.h"
#include "piece.h"
#include "sort.h"
#include "searchdata.h"
#include "swap.h"
#include "genmove.h"

#define WEIGHT  12
#define HASHSORTSCORE   INFIN
#define KILLERSORTSCORE 1000
#define CASTLINGSCORE   500


void PickStateInit(pickstate_t *pickstate){
  pickstate->movelist->gencnt=0;
  pickstate->captures->gencnt=0;
  pickstate->quietchecks->gencnt=0;
  pickstate->badcap=NULL;
  pickstate->p=pickstate->movelist->moves;
  pickstate->phase=PICKHASH;
  pickstate->count=0;
  pickstate->killer1_invalid=false;
  pickstate->killer2_invalid=false;
#ifdef DEBUG
  pickstate->all_moves->gencnt=0;
#endif
}


void SortCaptures (board_t *board, movelist_t *movelist)
/***************************************************************************
 *
 *  Actually no sorting is done.  Just scores are assigned to the captures.
 *  When we need a move, we will select the highest score move from the
 *  list, place it at the top and try it.  This move might give us a cut
 *  in which case, there is no reason to sort.
 *  
 ***************************************************************************/
{
   leaf *p;
   int temp, f, t;

   for (p = movelist->moves; p < movelist->moves+movelist->gencnt; p++)
   {
      f = Value[board->cboard[FROMSQ(p->move)]];
      t = Value[board->cboard[TOSQ(p->move)]];
      if (f < t){
         p->score = t - f;
      }else{
	temp = SwapOff (board,p->move);
	 p->score = (temp < 0 ? -INFIN : temp);
      }

   }
}


void SortQuietChecks (board_t *board, movelist_t *movelist)
/***************************************************************************
 *
 *  Actually no sorting is done.  Just scores are assigned to the captures.
 *  When we need a move, we will select the highest score move from the
 *  list, place it at the top and try it.  This move might give us a cut
 *  in which case, there is no reason to sort.
 *  
 ***************************************************************************/
{
   leaf *p;

   for (p = movelist->moves; p < movelist->moves+movelist->gencnt; p++){
       p->score = SwapOff (board,p->move);
   }
}


void SortMoves (board_t *board, 
		searchdata_t *searchdata, 
		movelist_t *movelist,
		int ply)
/*****************************************************************************
 *
 *  Sort criteria is as follows.
 *  1.  The move from the hash table
 *  2.  Captures as above.
 *  3.  Killers.
 *  4.  History.
 *  5.  Moves to the centre.
 *
 *****************************************************************************/
{
   leaf *p;
   int f, t, m, tovalue;
   int side, xside;
   BitBoard enemyP;

   side = board->side;
   xside = 1^side;
   enemyP = board->b[xside][pawn];

   for (p = movelist->moves; p < movelist->moves+movelist->gencnt; p++) {
       p->score = -INFIN/2;
      f = FROMSQ (p->move);
      t = TOSQ (p->move);
      m = p->move & MOVEMASK;

      /* Hash table move (highest score) */
      if (m == searchdata->Hashmv[ply]){
         p->score += HASHSORTSCORE;
      }else if (board->cboard[t] != 0 || p->move & PROMOTION) {

	/* ***** SRW My Interpretation of this code *************
           * Captures normally in other places but.....         *
           *                                                    *
           * On capture we generally prefer to capture with the *
	   * with the lowest value piece so to chose between    *
           * pieces we should subtract the piece value .... but *
           *                                                    *
           * The original code was looking at some captures     *
           * last, especially where the piece was worth more    *
           * than the piece captured - KP v K in endgame.epd    *
           *                                                    *
           * So code modified to prefer any capture by adding   *
           * ValueK                                             *
           ****************************************************** */

        tovalue = (Value[board->cboard[t]] + Value[PROMOTEPIECE (p->move)]);
        p->score += tovalue + ValueK - Value[board->cboard[f]];

      }else if /*killers*/ (m == searchdata->killer1[ply] || m == searchdata->killer2[ply]){
         p->score += KILLERSORTSCORE; 
      }else if (ply > 1 && (m == searchdata->killer1[ply-2] || m == searchdata->killer2[ply-2])){
	  p->score += KILLERSORTSCORE; 
      }
      p->score += HistoryGet(searchdata->history,board,p->move)+ taxicab[f][D5] - taxicab[t][E4];

      if ( board->cboard[f] == pawn ) {
        /* Look at pushing Passed pawns first */
	  if ( (enemyP & bitboards.PassedPawnMask[side][t]) == NULLBITBOARD ){
           p->score +=50;
	  }
      } 
      ASSERT(p->score!=-INFIN);
   }
}


void SortRoot (board_t *board, movelist_t *movelist)
/*****************************************************************************
 *
 *  Sort the moves at the root.  The heuristic is simple.  Try captures/
 *  promotions first.  Other moves are ordered based on their swapoff values.
 *
 *****************************************************************************/
{
   leaf *p;
   int f, t ;
   int side, xside;
   BitBoard enemyP;

   side = board->side;
   xside = 1^side;
   enemyP = board->b[xside][pawn];

   for (p = movelist->moves; p < movelist->moves+movelist->gencnt; p++)
   {
      f = Value[board->cboard[FROMSQ(p->move)]];
      if (board->cboard[TOSQ(p->move)] != 0 || (p->move & PROMOTION))
      {
         t = Value[board->cboard[TOSQ(p->move)]];
         if (f < t)
            p->score = -1000 + t - f;
         else
	   p->score = -1000 + SwapOff (board,p->move);
      }
      else 
	p->score = -3000 + SwapOff (board,p->move);

      p->score += taxicab[FROMSQ(p->move)][D5] - taxicab[TOSQ(p->move)][E4];

      if ( f == ValueP ) {
        /* Look at pushing Passed pawns first */
        if ( (enemyP & bitboards.PassedPawnMask[side][TOSQ(p->move)]) == NULLBITBOARD )
           p->score +=50;
      } 
   }
}



int PhasePick (board_t *board, 
	       searchdata_t *searchdata, 
	       pickstate_t *pickstate,
	       leaf **p1, 
	       int ply,
	       int depth)
/***************************************************************************
 *
 *  A phase style routine which returns the next move to the search.
 *  Hash move is first returned.  If it doesn't fail high, captures are
 *  generated, sorted and tried.  If no fail high still occur, the rest of
 *  the moves are generated and tried.
 *  The idea behind all this is to save time generating moves which might
 *  not be needed.
 *  CAVEAT: To implement this, the way that genmoves & friends are called
 *  have to be modified.  In particular, TreePtr[ply+1] = TreePtr[ply] must
 *  be set before the calls can be made.
 *  If the board ever gets corrupted during the search, then there is a bug
 *  in MoveIsPseudoLegal() which has to be fixed.
 *
 ***************************************************************************/
{
    leaf *p2;
    int mv;
    int side;
#ifdef DEBUG
    movelist_t movelist[1];
#endif 
    
    side = board->side;
    switch (pickstate->phase){
    case PICKHASH:
	pickstate->phase = PICKGEN1;
	if (searchdata->Hashmv[ply] && MoveIsPseudoLegal (board, searchdata->Hashmv[ply])) {
	    *p1=pickstate->hashmv;
	    (*p1)->move = searchdata->Hashmv[ply];
	    pickstate->count++;
#ifdef DEBUG
	    MoveListAdd(board,pickstate->all_moves,*p1);
#endif
            return (true);
	}
    case PICKGEN1:
	pickstate->phase = PICKCAPT;
	pickstate->p=pickstate->captures->moves;
	GenPseudoCaptures (board,pickstate->captures);
	for (p2 = pickstate->captures->moves; 
	     p2 < pickstate->captures->moves+pickstate->captures->gencnt; 
	     p2++){
	    p2->score = SwapOff(board,p2->move) * WEIGHT + 
		Value[board->cboard[TOSQ(p2->move)]];
	    if((p2->move & MOVEMASK) == searchdata->killer1[ply]){
		pickstate->killer1_invalid=true;
	    }
	    if((p2->move & MOVEMASK) == searchdata->killer2[ply]){
		pickstate->killer2_invalid=true;
	    }
	}
    case PICKCAPT:
	while (pickstate->p < pickstate->captures->moves+pickstate->captures->gencnt) {
	    MoveListPickSel(pickstate->captures,pickstate->p);
	    if(pickstate->p->score<0){
		break;
	    }
            if ((pickstate->p->move & MOVEMASK) == searchdata->Hashmv[ply]) {
		(pickstate->p)++;
		continue;
            } 
            *p1 = (pickstate->p)++;
	    pickstate->count++;
#ifdef DEBUG
	    MoveListAdd(board,pickstate->all_moves,*p1);
#endif
            return (true);
	}
	pickstate->badcap=pickstate->p;
	
    case PICKKILL1:
	pickstate->phase = PICKKILL2;
	if (searchdata->killer1[ply] && !pickstate->killer1_invalid && 
	    searchdata->killer1[ply] != searchdata->Hashmv[ply] && 
	    MoveIsPseudoLegal (board,searchdata->killer1[ply])){
	    *p1=pickstate->killer1;
	    (*p1)->move=searchdata->killer1[ply];
	    ASSERT(board->cboard[TOSQ(searchdata->killer1[ply])]==0);
	    pickstate->count++;
#ifdef DEBUG
	    MoveListAdd(board,pickstate->all_moves,*p1);
#endif
	    return (true);
	}
	
    case PICKKILL2:
	pickstate->phase = PICKGEN2;
	if (searchdata->killer2[ply] && !pickstate->killer2_invalid &&
	    searchdata->killer2[ply] != searchdata->Hashmv[ply] && 
	    MoveIsPseudoLegal (board,searchdata->killer2[ply])) {
	    *p1=pickstate->killer2;
	    (*p1)->move=searchdata->killer2[ply];
	    ASSERT(board->cboard[TOSQ(searchdata->killer2[ply])]==0);
	    pickstate->count++;
#ifdef DEBUG
	    MoveListAdd(board,pickstate->all_moves,*p1);
#endif
	    return (true);
	}
	
    case PICKGEN2:
	pickstate->phase = PICKREST;
	pickstate->p=pickstate->movelist->moves;
	GenPseudoNonCaptures (board,pickstate->movelist);
	for (p2 = pickstate->movelist->moves; 
	     p2 < pickstate->movelist->moves+pickstate->movelist->gencnt; 
	     p2++) {
	    p2->score=HistoryGet(searchdata->history,board,p2->move)+
		taxicab[FROMSQ(p2->move)][D5]  - taxicab[TOSQ(p2->move)][E4];
	    if (p2->move & CASTLING){
		p2->score += CASTLINGSCORE;
	    }
	}
    case PICKREST:
	while (pickstate->p < pickstate->movelist->moves+pickstate->movelist->gencnt){
	    MoveListPickSel(pickstate->movelist,pickstate->p);
	    mv = pickstate->p->move & MOVEMASK;
	    if (mv == searchdata->Hashmv[ply] || mv == searchdata->killer1[ply] || 
		mv == searchdata->killer2[ply]) {
		(pickstate->p)++;
		continue;
	    }
	    *p1 = (pickstate->p)++;
	    pickstate->count++;
#ifdef DEBUG
	    MoveListAdd(board,pickstate->all_moves,*p1);
#endif
	    return (true);
	}
	pickstate->phase=PICKBADCAPT;
	pickstate->p=pickstate->badcap;
    case PICKBADCAPT:
	while (pickstate->p < pickstate->captures->moves+pickstate->captures->gencnt) {
	    MoveListPickSel(pickstate->captures,pickstate->p);
	    ASSERT(pickstate->p->score<0);
	    mv = pickstate->p->move & MOVEMASK;
            if (mv == searchdata->Hashmv[ply]) {
		(pickstate->p)++;
		continue;
            } 
            *p1 = (pickstate->p)++;
	    pickstate->count++;
#ifdef DEBUG
	    MoveListAdd(board,pickstate->all_moves,*p1);
#endif
            return (true);
	}
	pickstate->phase=PICKDONE;
    case PICKDONE:
	return false;
       
    }
    ASSERT(false);
    return (false);
} 


int PhasePick1 (board_t *board, 
		searchdata_t *searchdata, 
		pickstate_t *pickstate,
		leaf **p1, 
		int ply,
		int depth)
/***************************************************************************
 *
 *  Similar to phase pick, but only used when the King is in check.
 *
 ***************************************************************************/
{

    
    switch (pickstate->phase) {
    case PICKHASH:
	pickstate->phase = PICKGEN1;
    case PICKGEN1:
	GenPseudoCheckEscapes (board,pickstate->movelist);
	SortMoves (board,searchdata,pickstate->movelist,ply);
	pickstate->phase=PICKREST;
    case PICKREST:
	while (pickstate->p < pickstate->movelist->moves+pickstate->movelist->gencnt) {
	    MoveListPickSel(pickstate->movelist,pickstate->p);
	    *p1 = (pickstate->p)++;
	    return (true);
	}
	pickstate->phase=PICKDONE;
    case PICKDONE:
	return false;
    }
    return (false);
}

int PhasePickQuiesce(board_t *board, 
		     searchdata_t *searchdata, 
		     pickstate_t *pickstate,
		     leaf **p1, 
		     int ply,
		     int depth)
/***************************************************************************
 *
 *  Similar to phase pick, but during quiescence search
 *
 ***************************************************************************/
{
    while(true){
	switch (pickstate->phase) {
	case PICKHASH:
	    pickstate->phase = PICKGEN1;
	    // fall through
	case PICKGEN1:
	    GenPseudoCaptures (board,pickstate->captures);
	    SortCaptures (board,pickstate->captures); 
	    pickstate->phase = PICKCAPT;
	    pickstate->p=pickstate->captures->moves;
	    // fall through
	case PICKCAPT:
	    while (pickstate->p < pickstate->captures->moves+pickstate->captures->gencnt) {
		MoveListPickSel(pickstate->captures,pickstate->p);
		if(pickstate->p->score<0){
		    break;
		}
		*p1 = (pickstate->p)++;
		pickstate->count++;
		return (true);
	    }
	    if(depth>=0){
		pickstate->phase=PICKGENQUIETCHECKS;
		break;
	    }else{
		pickstate->phase=PICKDONE;
		break;
	    }
	    ASSERT(false);   // we shouldn't be here!
	case PICKGENQUIETCHECKS:
	    GenPseudoQuietChecks(board,pickstate->quietchecks);
	    SortQuietChecks(board,pickstate->quietchecks);
	    pickstate->phase=PICKQUIETCHECKS;
	    pickstate->p=pickstate->quietchecks->moves;
	    // fall trough
	case PICKQUIETCHECKS:
	    while (pickstate->p < pickstate->quietchecks->moves+pickstate->quietchecks->gencnt) {
		MoveListPickSel(pickstate->quietchecks,pickstate->p);
		if(pickstate->p->score<0){
		    break;
		}
		*p1 = (pickstate->p)++;
		pickstate->count++;
		return (true);
	    }
	    pickstate->phase=PICKDONE;
	    // fall through
	case PICKDONE:
	    return false;
	}
    }
    ASSERT(false);
    return false; // we shouldn't be here.
}
