
//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
//
//	Gerbil
//
//	Copyright (c) 2001, Bruce Moreland.  All rights reserved.
//
//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
//
//	This file is part of the Gerbil chess program project.
//
//	Gerbil 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.
//
//	Gerbil 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 Gerbil; if not, write to the Free Software Foundation, Inc.,
//	59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

#include "engine.h"
#include "gproto.h"
#include <stdlib.h>

#ifdef	DEBUG
static char const s_aszModule[] = __FILE__;
#endif

//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

//	These end up being dummies since there is no pawn hash.

void VClearHashp(void)
{
}

BOOL FInitHashp(PCON pcon, int cbMaxPawnHash)
{
	return fTRUE;
}

//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

//	"coWin" just checkmated or took the last piece.  Meaning lost.

void VMates(int coLose)
{
	char	aszResult[64];
	char	aszReason[64];
				
	sprintf(aszResult, "%d-%d", coLose, coLose ^ 1);
	sprintf(aszReason, "%s wins", s_argszCo[coLose ^ 1]);
	VPrSendResult(aszResult, aszReason);
}

//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

//	Stalemate is a win in a Loser's game, and all the cases make it into the
//	"VMates" routine.

void VStalemate(int coStalemated)
{
}

//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

int	const c_argvalPos[pcMAX][coMAX][csqMAX] = {
	//
	//	White pawn.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	-10,0,	0,	0,	0,	0,	0,	-10,0,	0,	0,	0,	0,	0,	0,	0,
	-9,	0,	0,	0,	0,	0,	0,	-9,	0,	0,	0,	0,	0,	0,	0,	0,
	-8,	1,	1,	1,	1,	1,	1,	-8,	0,	0,	0,	0,	0,	0,	0,	0,
	-7,	2,	2,	2,	2,	2,	2,	-7,	0,	0,	0,	0,	0,	0,	0,	0,
	-5,	4,	4,	4,	4,	4,	4,	-5,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	10,	10,	10,	10,	10,	10,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	Black pawn.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	10,	10,	10,	10,	10,	10,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	-5,	4,	4,	4,	4,	4,	4,	-5,	0,	0,	0,	0,	0,	0,	0,	0,
	-7,	2,	2,	2,	2,	2,	2,	-7,	0,	0,	0,	0,	0,	0,	0,	0,
	-8,	1,	1,	1,	1,	1,	1,	-8,	0,	0,	0,	0,	0,	0,	0,	0,
	-9,	0,	0,	0,	0,	0,	0,	-9,	0,	0,	0,	0,	0,	0,	0,	0,
	-10,0,	0,	0,	0,	0,	0,	-10,0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	White knight.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	Black knight.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	White bishop.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	Black bishop.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	White rook.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	Black rook.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	White queen.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	Black queen.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	White king.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	//
	//	Black king.
	//
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,	0,
};

//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

//	This is a very simple eval function, but it seems alright.
//
//	Positional terms handled through piece-square table:
//
//	1) An advanced pawn is good.
//	2) An a- or h-pawn is bad.
//
//	Evaluation terms:
//
//	1) Add up all the pieces.
//	2) Subtract the pawns.
//	3) You get a bonus if the opponent has no pieces.
//	4) You get a penalty if you have no pieces.
//	5) You get a penalty if the opponent has no pawns.
//	6) You get a bonus if you have no pawns.
//
//	Given current material values:
//
//	If there are pieces and pawns for both sides, it is most important to have
//	more pieces.  Secondarily, have fewer pawns.
//
//	A rook is the best piece and a queen is the worst.
//
//	A good future term is that an isolated a- or -pawn is really bad.

int ValEval(PCON pcon, PSTE pste)
{
	int	val;
	int	argval[coMAX];
	int	co;

	for (co = coWHITE; co <= coBLACK; co++) {
		int	i;

		argval[co] = 0;
		for (i = 0; i < pcon->argcpi[co]; i++) {
			PPI	ppi = &pcon->argpi[co][i];

			if (!ppi->fDead)
				argval[co] += c_argvalPos[ppi->pc][ppi->co][ppi->isq];
		}
	}
	if (pste->coUs == coWHITE)
		val = argval[coWHITE] - argval[coBLACK];
	else
		val = argval[coBLACK] - argval[coWHITE];
	val += pste->valPcUs - pste->valPcThem -
		pste->valPnUs + pste->valPnThem;
	if (pste->valPcUs == 0)
		val -= 5000;
	if (pste->valPcThem == 0)
		val += 5000;
	if (pste->valPnUs == 0)
		val += 5000;
	if (pste->valPnThem == 0)
		val -= 5000;
	return val;
}

//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

//	The basic deal is that in the full-width part (plyRem >= 0), it searches
//	legal captures first.  If it finds any, it stops when it finds the first
//	non-capture.  If it finds no captures, it searches the rest of the moves.

//	If it's in the quiescent part (plyRem < 0), it works as above, except that
//	if it finds no captures (and yet at least one legal move), it scores the
//	position via the eval function and leaves.

//	I banged this out in a short time to see if I could get this working
//	without making a mess out of the entire project.  Apparently I could,
//	because I think I did.

//	It's quite possible that this search algorithm sucks, and I know the eval
//	function sucks.  In any case, it does sometimes beat reasonable players
//	on ICC, and sometimes it returns pretty long forced win sequences.

//	The scores returned to indicate winning or losing positions (the mate
//	scores) are probably wrong.  I haven't bothered to figure out exactly
//	what values to return there; I just wanted to get it working vaguely.

int ValSearch(PCON pcon, PSTE pste)
{
	PCM	pcm;
	PCM	pcmBest;
	BOOL	fFoundLegalMove;
	BOOL	fFoundLegalCapture;
	int	hashf = hashfALPHA;
	int	val;

	if (++pcon->ss.nodes >= pcon->ss.nodesNext) {
		pcon->ss.nodesNext = pcon->ss.nodes + 2000;
		VPrCallback((void *)pcon);
		VCheckTime(pcon);
		if ((pcon->fAbort) || (pcon->fTimeout))
			return 0;
	}
	//	We're out of material so we win.
	//
	if (pste->valPcUs + pste->valPnUs == 0) {
		pste->ccmPv = 0;
		return valMATE - (pste - pcon->argste);
	}
	//	They are out of material so they win.
	//
	if (pste->valPcThem + pste->valPnThem == 0) {
		pste->ccmPv = 0;
		return -valMATE + (pste - pcon->argste);
	}
	//	Repetition, score as a draw.
	//
	if ((pste != pcon->argste) && (FRepSet(pcon, pste->hashkPc))) {
		pste->ccmPv = 0;
		return 0;
	}
	//	Hash cutoff.
	//
	if ((FProbeHash(pcon, pste, &val)) && (pste > pcon->argste + 1)) {
		pste->ccmPv = 0;
		return val;
	}
	//	Mark this position as "seen" in the repetition hash.  If I return out
	//	of this function, I have to clear the position or bad things happen.
	//
	VSetRep(pcon, pste->hashkPc);
	//
	//	Generate moves, set sort flags.  Note that the "capture" flag sorts
	//	highest.  A capture with a hash table flag set will sort above other
	//	captures, but a non-capture with a hash table flag set will sort after
	//	the captures.  You'd think this would be impossible, but it could
	//	happen if I get a hash table collision.  Hash table collisions are
	//	fine to ignore unless they make you crash get into an unstable state,
	//	and something like that might happen here, so I had to change the
	//	sort keys in "engine.h" for Loser's chess.
	//
	VGenMoves(pcon, pste, fFALSE);
	if (pste->cmPv.isqFrom != isqNIL) {
		VFindPvCm(pste);
		pste->cmPv.isqFrom = isqNIL;
	}
	if (pste->phashAlways != NULL)
		VFindHash(pste, pste->phashAlways);
	if (pste->phashDepth != NULL)
		VFindHash(pste, pste->phashDepth);
	//
	//	Ready to loop through moves.
	//
	pcmBest = NULL;
	fFoundLegalMove = fFALSE;
	fFoundLegalCapture = fFALSE;
	for (pcm = pste->pcmFirst; pcm < (pste + 1)->pcmFirst; pcm++) {
		VSort(pste, pcm);
		VMakeMove(pcon, pste, pcm);
		//
		//	In this variant, every move is a legal chess move, so you could
		//	run a loser's game through a PGN eater and you wouldn't find any
		//	illegal moves.  The next part weeds out moves that leave us in
		//	check.
		//
		if (FAttacked(pcon, pcon->argpi[pste->coUs][0].isq, pste->coUs ^ 1)) {
			VUnmakeMove(pcon, pste, pcm);
			continue;
		}
		//	I can't be checkmated or stalemated if I've gotten here.
		//
		fFoundLegalMove = fTRUE;
		//
		//	Remember that we found a capture.
		//
		if (pcm->cmf & cmfCAPTURE)
			fFoundLegalCapture = fTRUE;
		else {
			//	Non-capturing move.
			//
			//	This 50-move check might be in a funny and/or wrong place.
			//
			if ((pste->plyFifty >= 50 * 2) && (pste != pcon->argste)) {
				pste->ccmPv = 0;
				VUnmakeMove(pcon, pste, pcm);
				VClearRep(pcon, pste->hashkPc);
				return 0;
			}
			//	Non-captures are not legal if we found a capture.
			//
			if (fFoundLegalCapture) {
				VUnmakeMove(pcon, pste, pcm);
				break;
			} else if (pste->plyRem < 0) {
				//
				//	If we're in here, we're in quiescent search and no
				//	captures are available, do a static eval.  If that doesn't
				//	cause a cutoff, break out of here.
				//
				VUnmakeMove(pcon, pste, pcm);
				val = ValEval(pcon, pste);
				if (val > pste->valAlpha) {
					if (val >= pste->valBeta) {
						VRecordHash(pcon, pste, pcm,
							pste->valBeta, hashfBETA);
						VClearRep(pcon, pste->hashkPc);
						return pste->valBeta;
					}
					pste->valAlpha = val;
					pste->ccmPv = 0;
				}
				break;
			}
		}
		//	The rest of the loop is straightforward chess stuff that would
		//	work as well in a "normal" chess program.
		//
		//	Set up for recursion.
		//
		(pste + 1)->fInCheck = FAttacked(pcon,
			pcon->argpi[pste->coUs ^ 1][0].isq, pste->coUs);
		if (pste->plyRem < 0)
			(pste + 1)->plyRem = -1;
		//
		//	Maybe the following extension is good and maybe not.
		//
		else if (pcm->cmf & cmfCAPTURE)
			(pste + 1)->plyRem = pste->plyRem;
		else
			(pste + 1)->plyRem = pste->plyRem - 1;
		(pste + 1)->valAlpha = -pste->valBeta;
		(pste + 1)->valBeta = -pste->valAlpha;
		//
		//	Recurse into normal search or quiescent search, as appropriate.
		//
		val = -ValSearch(pcon, pste + 1);
		VUnmakeMove(pcon, pste, pcm);
		if ((pcon->fAbort) || (pcon->fTimeout)) {
			VClearRep(pcon, pste->hashkPc);
			return 0;
		}
		if (val > pste->valAlpha) {
			if (val >= pste->valBeta) {
				//
				//	This move failed high, so we are going to return beta,
				//	but if we're sitting at the root of the search I will set
				//	up a one-move PV (if this isn't already the move I'm
				//	planning to make), so this move will be made if I run out
				//	of time before resolving the fail-high.
				//
				if (pste == pcon->argste) {
					if (memcmp(pcm, pste->argcmPv, sizeof(CM))) {
						pste->argcmPv[0] = *pcm;
						pste->ccmPv = 1;
					}
					VDumpPv(pcon, pcon->ss.plyDepth, val, '+');
				}
				VRecordHash(pcon, pste, pcm, pste->valBeta, hashfBETA);
				VClearRep(pcon, pste->hashkPc);
				return pste->valBeta;
			}
			//	This move is between alpha and beta, which is actually pretty
			//	rare.  If this happens I have to add a PV move, and append the
			//	returned PV to it, and if I'm at the root I'll send the PV to
			//	the interface so it can display it.
			//
			memcpy(pste->argcmPv + 1, (pste + 1)->argcmPv,
				(pste + 1)->ccmPv * sizeof(CM));
			pste->argcmPv[0] = *pcm;
			pste->ccmPv = (pste + 1)->ccmPv + 1;
			pste->valAlpha = val;
			if (pste == pcon->argste)
				VDumpPv(pcon, pcon->ss.plyDepth, val, '\0');
			hashf = hashfALPHA | hashfBETA;
			pcmBest = pcm;
		}
	}
	VClearRep(pcon, pste->hashkPc);
	//
	//	Both stalemate and being checkmated win for us.
	//
	if (!fFoundLegalMove) {
		pste->ccmPv = 0;
		VRecordHash(pcon, pste, pcmBest, valMATE - 500, hashfBETA);
		return valMATE - (pste - pcon->argste);
	}
	//	Record fail-low or PV node.
	//
	VRecordHash(pcon, pste, pcmBest, pste->valAlpha, hashf);
	return pste->valAlpha;
}

//	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
