/* GNU Chess 5.0 - ttable.c - transposition table 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 <string.h>
#include <malloc.h>
#include <stdlib.h>

#include "util.h"
#include "moveseq.h"
#include "ttable.h"
#include "move.h"

ttable_t TTable[1];

int ClusterSize=4;

void TTableInit(ttable_t *ttable){
    ttable->Slot=NULL;
    ttable->Size=0;
    ttable->Mask=0;
    ttable->Age=0;
    TTableResetStats(ttable);    
}

void TTableZero (ttable_t *ttable)
/****************************************************************************
 *   
 *  Zero out the transposition table.
 *
 ****************************************************************************/
{
   memset (ttable->Slot, 0, ttable->Size * sizeof (ttable_slot_t));
}



void TTableClear(ttable_t *ttable){
    if(ttable->Slot!=NULL){
	free(ttable->Slot);
    }
    TTableInit(ttable);
}

void TTableResetStats(ttable_t *ttable){
    ttable->TotalGetHashCnt=0;
    ttable->GoodGetHashCnt=0;
    ttable->TotalPutHashCnt=0;
    ttable->CollHashCnt=0;
}

void TTableIncAge(ttable_t *ttable){
    ttable->Age++;
}

void TTableSetSizeMb(ttable_t *ttable, unsigned int size){
    int slotsize;
    slotsize=(1048576*size)/(sizeof(ttable_slot_t));
    TTableSetSize(ttable,slotsize);
}

void TTableSetSize(ttable_t *ttable, unsigned int size)
/****************************************************************************
  *
  *  Allocate memory for our transposition tables.  By default, the
  *  transposition table will have 16K entries; 8K for each color.
  *  Add code to allocated memory for pawn table as well.
  *
  ****************************************************************************/
{
    unsigned int tsize;
    unsigned int i;

    TTableClear(ttable);
    i = (size < HASHSLOTS ? HASHSLOTS : size);
        
    ttable->Mask = 0;
    while ((i>>=1) > 0)	{
	ttable->Mask <<= 1;
	ttable->Mask |= 1;
    }
    ttable->Size = ttable->Mask + 1+(ClusterSize-1);
    ASSERT(size/2<ttable->Size<=size+(ClusterSize-1));

    ttable->Slot = malloc (ttable->Size * sizeof (ttable_slot_t));
    if (ttable->Slot == NULL) {
         OutputConsole("Not enough memory for transposition table,\n");
	 exit(EXIT_FAILURE);
    }
    tsize = (ttable->Size *  sizeof (ttable_slot_t)) >> 10;
    OutputConsole("Transposition table:  Entries=%dK Size=%dK\n",
              ttable->Size>>10, tsize);
    TTableZero(ttable);

}


void TTableRefresh(ttable_t *ttable, board_t *board){
    ttable_slot_t *t, *s;
    t = ttable->Slot + (board->HashKey & ttable->Mask); 
    for(s=t;s<=t+ClusterSize-1;s++){
	if(s->key==board->HashKey){
	    s->age=ttable->Age;
	    break;
	}
    }
}

void TTablePut (ttable_t *ttable,
		board_t *board, 
		uint8_t depth, 
		uint8_t ply, 
		int alpha, 
		int beta, 
		int under_threat,
		int score, 
		int move){

    uint32_t quality; // the higher the worse
    uint32_t best; 
    ttable_slot_t *best_slot, *t, *s;

    ASSERT(move==NOMOVE || MoveIsPseudoLegal(board,move));

    t = ttable->Slot + (board->HashKey & ttable->Mask); 
    best=0;
    best_slot=t;

    for(s=t;s<=t+ClusterSize-1;s++){
	if(s->key==board->HashKey){
	    best_slot=s;
	    break;
	}
	quality=((ttable->Age-s->age)<<16)+((255-s->depth)<<4)+(TTABLE_FLAGMASK-s->flag);
	if(quality>best){
	    best=quality;
	    best_slot=s;
	    
	}
    }
    if (best_slot->flag && ttable->Age==best_slot->age){
      ttable->CollHashCnt++;
    }
    ttable->TotalPutHashCnt++;
    best_slot->move = move;
    best_slot->key = board->HashKey;
    best_slot->depth = depth;
    best_slot->age=ttable->Age;
    best_slot->flag=0;
    if (best_slot->depth == 0){
	best_slot->flag |= TTABLE_QUIESCENT;
    }else if (score >= beta){
	best_slot->flag |= TTABLE_LOWERBOUND;         
    }else if (score <= alpha){
	best_slot->flag |= TTABLE_UPPERBOUND;
    }else{
	best_slot->flag |= TTABLE_EXACTSCORE;
    }
    if(under_threat){
	best_slot->flag|=TTABLE_UNDERTHREAT;
    }
    if (MATESCORE(score)){
	best_slot->score = score + ( score > 0 ? (ply+1) : -(ply+1));
    }else{
	best_slot->score = score;
    }
    ASSERT(best_slot->score>=-MATE-1);
    ASSERT(best_slot->score<=MATE+1);

}



int TTableGet(ttable_t *ttable,
		  board_t *board, 
		  uint8_t ply, 
		  uint8_t *depth, 
		  uint8_t *flag,
		  int *score,
		  int *move){
    ttable_slot_t *s,*t;
    ttable->TotalGetHashCnt++;
    t = ttable->Slot + (board->HashKey & ttable->Mask); 
    for(s=t;s<=t+ClusterSize-1;s++){
	if(s->key==board->HashKey){
	    ttable->GoodGetHashCnt++;
	    *move = s->move;
	    *score = s->score;
	    if (MATESCORE(*score)){
		*score -= (*score > 0 ? (ply+1) : -(ply+1));
	    }
	    *flag = s->flag;
	    *depth=s->depth;
	    return 1;
	}
    }
    return 0;
}


void TTableGetPV(ttable_t *ttable,
		 board_t *board, 
		 int score,
		 int maxgen,
		 moveseq_t *moveseq
		  ){
    ttable_slot_t *s,*t;
    int found;
    board_t board_work[1];
    moveseq->gencnt=0;
    memcpy(board_work,board,sizeof(board_t));
    while(1){
	if ((MATESCORE(score) && abs(score) == MATE-moveseq->gencnt) || 
	    BoardRepeat (board_work) || moveseq->gencnt==maxgen){
	    break;
	}
	t = ttable->Slot + (board_work->HashKey & ttable->Mask); 
	found=false;
	for(s=t;s<=t+ClusterSize-1;s++){
	    if(s->key==board_work->HashKey && s->flag==TTABLE_EXACTSCORE && 
		(!(moveseq->gencnt & 1 && score == s->score)||
		 ((moveseq->gencnt & 1) && score == -s->score))
	       ){
		ASSERT(s->move!=0);
		moveseq->moves[moveseq->gencnt]=s->move;
		found=true;
		break;
	    }
	}
	if(!found){
	    break;
	}else{
	    MoveMake(board_work,moveseq->moves[moveseq->gencnt]);
	    (moveseq->gencnt)++;
	}
    }
}

void TTableFeedPV(ttable_t *ttable,
		  board_t *board,
		  uint8_t depth,
		  int score,
		  moveseq_t *moveseq){
    int i;
    board_t board_work[1];
    memcpy(board_work,board,sizeof(board_t));
    for(i=0;i<moveseq->gencnt;i++){
	TTablePut(ttable,
		  board_work,
		  depth-i,                      /*depth*/
		  i,                            /*ply*/
		  -INFIN,                    /*alpha*/
		  INFIN,                     /*beta*/
		  false,                      /*move connected*/
		  i%2?score:-score,             /*score*/
		  moveseq->moves[i]             /*move*/
		  );
	MoveMake(board_work,moveseq->moves[i]);
    }
}
    



void TTShow(ttable_t *ttable, board_t *board){
    ttable_slot_t *s, *t;
    int move, score;
    uint8_t stored_depth;
    uint16_t age;
    Output("Age=%u Hash=" U64_FORMAT" \n",ttable->Age, board->HashKey);
    t = ttable->Slot + (board->HashKey & ttable->Mask); 

    for(s=t;s<=t+ClusterSize-1;s++){
	if(s->key==board->HashKey){
	    move = s->move;
	    score = s->score;
	    age=s->age;
	    stored_depth=s->depth;
	    
	    if(!s->flag){
		Output("NOTFOUND ");
	    }else if(s->flag & TTABLE_QUIESCENT){
		Output("QUIESCENT ");
	    }else if(s->flag & TTABLE_LOWERBOUND){
		Output("LOWERBOUND ");
	    }else if(s->flag & TTABLE_UPPERBOUND){
		Output("UPPERBOUND ");
	    }else if(s->flag & TTABLE_EXACTSCORE){
		Output("EXACTSCORE ");
	    }
	    if(s->flag & TTABLE_UNDERTHREAT){
		Output("Under threat! ");
	    }
    
	    if(s->flag){
		Output("move=%s score=%d depth=%d age=%u\n",AlgbrMove(move),score,stored_depth, age);
	    }
	}
    }
    Output("\n");
}

void TTableStatsShow(ttable_t *ttable){
    OutputConsole("Hash: Get=%uk Good=%2.0f%% Put=%uk Coll=%2.0f%%\n",
		  ttable->TotalGetHashCnt/1000,
		  100*((double) ttable->GoodGetHashCnt)/((double) ttable->TotalGetHashCnt),
		  ttable->TotalPutHashCnt/1000,
		  100*((double) ttable->CollHashCnt)/ ((double) ttable->TotalPutHashCnt));
}




