/*
 *
 * cmove.c -- computer move algorithm
 *
 * This code is copyright 1995 by James A. Cherry, jac@doe.carleton.ca.
 * It is not to be redistributed or modified without his permission.
 *
 */

#include "funddefs.h"
#include "globals.h"
#include "proto.h"

/* Static global definitions */

int ntiles, nused;       /* number of tiles on rack and number used */
int tilev[7];            /* conversion of A-Z, ? to 0-25, 26 */
struct plrlet newlet[7]; /* temporary newlet structure */
int tiles_left_to_draw;  /* 100 - number of tiles not on board */
int rms1, rms2;          /* rack leave scores for non-endgame and endgame */
int theirrack;           /* value of tiles on opponent's rack at endgame */

compmove *ComputerMove( plr )
    int plr;
/* Find a move given the board, scores, and racks. */
{
    compmove *mvptr;
    
    init_cmove( plr );
    dump_scores( plr );
    LPrint( "After dump_scores()\n" ); 
    if( Board[8][8] < 'A' ) {
	first_move( plr );
    } else {
	cpu_move( plr );
    }
    LPrint( "After cpu_move()\n" ); 
    mvptr = pick_word( plr );
    LPrint( "After pick_word()\n" ); 
    if( mvptr == NULL ) {
	LPrint( "No moves on queue.\n" ); 
    }
    
    return( mvptr );
}

void init_cmove( plr )
    int plr;
/* Initialization for computer move routine. */
{
    int i;
    int ttl[27];
    
    tiles_left_to_draw = 0;
    for( i = 0; i < 27; i++ ) {
	ttl[i] = TilesLeft[i];
	tiles_left_to_draw += TilesLeft[i];
    }
    ntiles = 0;
    for( i = 0; i < 7; i++ ) {
	if( PlrTiles[plr][i] != 0 ) {
	    tilev[i] = PlrTiles[plr][i] - 'A';
	    if( PlrTiles[plr][i] == CH_BL ) tilev[i] = 26;
	    ttl[tilev[i]]--;
	    ntiles++;
	} else tilev[i] = 27;
    }
/* Calculate the points on the opponent's rack. */
    theirrack = 0;
    if( tiles_left_to_draw <= 14 ) {
	LPrint( "Their rack is " );
	for( i = 0; i < 27; i++ ) {
	    theirrack += Letters[i].points * ttl[i];
	    while( ttl[i]-- > 0 )
		LPrint( "%c", ( i != 26 ) ? ( i + 'A' ) : CH_BL );
	}
	LPrint( ", worth %d\n", theirrack );
    }
    CHead = NULL;
    LPrint( "I think there are %d tiles left.\n", tiles_left_to_draw ); 
}

void first_move( plr )
    int plr;
/* Look for play crossing h8. */
{
    int s, p;
    
    for( p = 2; p < 8; p++ ) {
	for( s = 9 - p; s < 9; s++ ) {
	    if( VerticalPlay == 0 )
		try_tiles( s, 8, p, 0 );
	    else
		try_tiles( 8, s, p, 1 );
	}
    }
}

void add_to_move_list( newptr )
    compmove *newptr;
/* Add a move to the list of possible moves.  Sorted from highest-scoring to
   lowest-scoring. */
{
    int sc, ru;
    compmove *ptr1, *ptr2;
    
    sc = newptr->score;
    ru = newptr->rms;
    if( CHead == NULL ) CHead = newptr;
    else if( sc > CHead->score || ( sc == CHead->score && ru > CHead->rms ) ) {
	newptr->next = CHead;
	CHead = newptr;
    } else {
	ptr2 = NULL;
	ptr1 = CHead;
	while( ptr1 != NULL &&
	       ( ( sc < ptr1->score )
		 || ( sc == ptr1->score && ru <= ptr1->rms ) ) ) {
	    ptr2 = ptr1;
	    ptr1 = ptr1->next;
	}
	newptr->next = ptr1;
	ptr2->next = newptr;
    }
}

void PassScore()
/* Calculate score for passing. */
/* Please note: this must be called _after_ ComputerMove(). */
{
    int used[7], rms, i;
    compmove *newptr;

    for( i = 0; i < 7; i++ ) used[i] = 0;
    eval_rack_leave( used );
    if( tiles_left_to_draw > 14 ) rms = rms1;
    else rms = rms2;
#if 0
/* Add sgordon's heuristic for opening moves: 4 * (# tiles left on rack) */
    if( tiles_left_to_draw == 100 )
	rms += 8 * 7;
#endif
    newptr = (compmove *) malloc( CM_SIZE );
    newptr->next = NULL;
    newptr->score = rms;
    newptr->rms = rms;
    newptr->placed = 0;
    add_to_move_list( newptr );
}

void dump_scores( plr )
    int plr;
/* Calculate score for exchanging tiles. */
{
    int i, s;
    int c, p[7];
    int used[7];
    int rms;
    compmove *newptr;
    
/* tiles_left_to_draw is 100 - (# tiles on Board already) */
    if( tiles_left_to_draw < 21 ) return;
    for( c = 1; c < 8; c++ ) {
	for( i = 0; i < c; i++ ) p[i] = i;
	s = 0;
	for( ;s >= 0; ) {
	    for( i = 0; i < 7; i++ ) used[i] = 0;
	    for( i = 0; i < c; i++ ) used[p[i]] = 1;
	    eval_rack_leave( used );
	    rms = rms1;
/* Add sgordon's heuristic for opening moves: 4 * (# tiles left on rack) */
	    if( tiles_left_to_draw == 100 )
		rms += 8 * ( 7 - c );

	    newptr = (compmove *) malloc( CM_SIZE );
	    if( newptr == NULL ) {
		LPrint( "*** Fatal error: no memory left in dump_scores()" ); 
		ExitWindow();
		exit( 11 );
	    }
	    newptr->next = NULL;
	    newptr->score = rms;
	    newptr->rms = rms;
	    newptr->placed = -c;
	    for( i = 0; i < c; i++ ) {
		newptr->newlet[i].letter = PlrTiles[plr][p[i]];
		newptr->newlet[i].tilepos = p[i];
	    }
	    add_to_move_list( newptr );
	    
	    for( s = c - 1; s >= 0; ) {
		p[s]++;
		if( p[s] > 7 - ( c - s ) ) s--;
		else break;
	    }
	    if( s >= 0 )
		for( i = s + 1; i < c; i++ )
		    p[i] = p[i - 1] + 1;
	}
    }
}

void prune_first_move()
/* If several first moves are identical but some don't put vowels next to
   DLSs, pick those moves preferentially. */
{
    int mcount, i, x, y;
    compmove *pstart, *pend, *ptemp;
    char c;

    if( CHead == NULL ) return;
    pend = CHead; mcount = 0;
    while( pend != NULL && pend->score == CHead->score
	&& pend->placed == CHead->placed ) {
	for( i = 0; i < pend->placed; i++ ) {
	    if( pend->newlet[i].letter != CHead->newlet[i].letter )
		break;
	    if( pend->newlet[i].letter == CH_BL
		&& pend->newlet[i].blankchar != CHead->newlet[i].blankchar )
		break;
	}
	if( i != pend->placed ) break;
	pend = pend->next;
	mcount++;
    }
    for( pstart = CHead; pstart != pend; pstart = pstart->next ) {
	pstart->winout = 0; /* overload winout */
	for( i = 0; i < pstart->placed; i++ ) {
	    x = pstart->newlet[i].x; y = pstart->newlet[i].y;
	    c = pstart->newlet[i].letter;
	    if( c == CH_BL ) c = pstart->newlet[i].blankchar;
	    if( ( x == 7 && y == 8 ) || ( x == 9 && y == 8 )
		|| ( x == 8 && y == 7 ) || ( x == 8 && y == 9 ) ) {
		if( c == 'A' || c == 'E' || c == 'I' || c == 'O'
		    || c == 'U' ) {
		    pstart->winout = 1;
		}
	    }
	}
	if( pstart->winout == 1 ) mcount--;
    }
    if( mcount != 0 ) {
/* There was at least one move that didn't put a vowel next to a DLS, so
   remove all other moves */
	ptemp = NULL;
	for( pstart = CHead; pstart != pend; pstart = pstart->next ) {
	    if( pstart->winout == 1 ) {
		if( ptemp == NULL ) CHead = pstart->next;
		else ptemp->next = pstart->next;
		free( (compmove *) pstart );
	    } else ptemp = pstart;
	}
    }
}

compmove *pick_word( plr )
    int plr;
/* Choose the best move.  Among equal-scoring alternatives, choose one at
   random. */
{
    int i, j;
    compmove *moveptr;
    
    if( tiles_left_to_draw == 100 ) prune_first_move();
    moveptr = CHead;
    if( CHead != NULL ) {
	i = 0;
	while( moveptr != NULL && moveptr->score == CHead->score ) {
	    moveptr = moveptr->next;
	    i++;
	}
	j = GetRandom() % i;
	moveptr = CHead;
	while( --j >= 0 ) moveptr = moveptr->next;
    }
    
    return( moveptr );
}

void cpu_move( plr )
    int plr;
/* Go over entire board and find possible starting squares for a move that
   will connect to the existing puzzle. */
{
    int sx, sy, dir, xinc, yinc;
    int x, y, rc;
    int blank, tile, oldbl;
    
    for( sy = 1; sy < 16; sy++ ) {
	for( sx = 1; sx < 16; sx++ ) {
	    for( dir = 0; dir < 2; dir++ ) {
		xinc = 1 - dir;
		yinc = dir;
		x = sx;
		y = sy;
		blank = 0;
		tile = 0;
		oldbl = 0;
		if( x - xinc > 0 && y - yinc > 0 )
		    if( Board[y - yinc][x - xinc] >= 'A' ) continue;
		while( x < 16 && y < 16 && blank < ntiles ) {
		    if( Board[y][x] < 'A' ) blank++;
		    if( Board[y][x] >= 'A' ||
			( x - xinc > 0 && y - yinc > 0 &&
			  Board[y - yinc][x - xinc] >= 'A' ) ||
			( x + xinc < 16 && y + yinc < 16 &&
			  Board[y + yinc][x + xinc] >= 'A' ) ||
			( x - yinc > 0 && y - xinc > 0 &&
			  Board[y - xinc][x - yinc] >= 'A' ) ||
			( x + yinc < 16 && y + xinc < 16 &&
			  Board[y + xinc][x + yinc] >= 'A' ) )
			tile++;
		    if( blank > oldbl && tile > 0 ) {
			oldbl = blank;
			rc = try_tiles( sx, sy, blank, dir );
			if( rc == -1 ) blank = ntiles;
		    }
		    x += xinc; y += yinc;
		}
	    }
	}
    }
}

int try_tiles( sx, sy, placed, dir )
    int sx, sy, placed, dir;
/* Try a given number of tiles (`placed') at column `sx' and row `sy', in
   the direction given by `dir'. */
{
    int xinc, yinc, x, y;
    int i, j, k, hooks;
    int used[7], tilepos[7], tile[7], blank[7], index[7], map[7];
    int stack, prevtile;
    int len;
    char tword[20], dword[20];
        
    prevtile = 0;
    strcpy( tword, "***************" );
    xinc = 1 - dir;
    yinc = dir;
    x = sx;
    y = sy;
    hooks = 0;
    for( i = 0; i < ntiles; i++ ) used[i] = 0;
    for( i = 0; i < placed; i++ ) {
	blank[i] = -1;
	index[i] = -1;
	tilepos[i] = -1;
	while( Board[y][x] >= 'A' ) {
	    if( dir == 0 )
		tword[x - sx] = Board[y][x];
	    else
		tword[y - sy] = Board[y][x];
	    x += xinc;
	    y += yinc;
	}
	if( dir == 0 ) {
/* Skip it when there are hooks that cannot be made */
	    if( HHook[y][x][26] == 0 ) return( -1 );
	    else if( HHook[y][x][26] > 0 ) {
		map[hooks] = i;
		index[hooks++] = x - sx;
		tword[x - sx] = '-';
	    }
	} else {
	    if( VHook[y][x][26] == 0 ) return( -1 );
	    else if( VHook[y][x][26] > 0 ) {
		map[hooks] = i;
		index[hooks++] = y - sy;
		tword[y - sy] = '-';
	    }
	}
	newlet[i].x = x;
	newlet[i].y = y;
	x += xinc;
	y += yinc;
    }
/* Fill in tword[] with any letters already on the board. */
    while( Board[y][x] >= 'A' && x < 16 && y < 16 ) {
	if( dir == 0 )
	    tword[x - sx] = Board[y][x];
	else
	    tword[y - sy] = Board[y][x];
	x += xinc;
	y += yinc;
    }
    if( dir == 0 )
	tword[x - sx] = '\0';
    else
	tword[y - sy] = '\0';
    strcpy( dword, tword );
    len = strlen( tword );
    for( i = 0, j = hooks, k = 0; i < len; i++ ) {
	if( tword[i] == '*' && index[j] == -1 ) {
	    map[j] = k;
	    index[j++] = i;
	}
	if( tword[i] < 'A' ) k++;
    }
    stack = 0;
    while( stack >= 0 ) {
	if( stack < hooks ) {
/* See if we can satisfy the hooks in our path. */
	    if( tilepos[stack] == -1 ) {
		i = 0;	
		prevtile = -1;
	    } else if( tile[stack] != 26 || blank[stack] == -1 ) {
		i = tilepos[stack];
		prevtile = tile[stack];
		used[i] = 0;
		i++;
	    } else {
		i = -1;
		blank[stack]++;
	    }
	    if( i != -1 )
		while( ( used[i] != 0 || prevtile == tilev[i] )
		       && i < ntiles )
		    i++;
	    if( i == ntiles ) {
		tilepos[stack] = -1;
		stack--;
	    } else {
		if( i != -1 ) {
		    tilepos[stack] = i;
		    tile[stack] = tilev[i];
		    used[i] = 1;
		    if( tilev[i] == 26 )
			blank[stack] = 0;
		}
		if( tile[stack] != 26 ) {
		    if( dir == 0 )
			j = HHook[sy][sx + index[stack]][tile[stack]];
		    else
			j = VHook[sy + index[stack]][sx][tile[stack]];
		    if( j != 0 ) stack++;
		} else {
		    if( dir == 0 )
			while( HHook[sy][sx + index[stack]][blank[stack]] == 0
			       && blank[stack] < 26 ) blank[stack]++;
		    else
			while( VHook[sy + index[stack]][sx][blank[stack]] == 0
			       && blank[stack] < 26 ) blank[stack]++;
		    if( blank[stack] != 26 ) stack++;
		    else blank[stack] = -1;
		}
	    }
	} else {
/* Once hooks are filled in, fill in rest of word */
	    if( stack == hooks )
		for( i = 0; i < hooks; i++ ) {
		    j = index[i];
		    if( tile[i] != 26 )
			tword[j] = tile[i] + 'A';
		    else
			tword[j] = blank[i] + 'A';
		}
	    if( stack == placed ) {
/* Once all tiles are placed, see if it forms a valid word */
		if( BinSearch( tword ) ) {
/* If so, find the rack leave and score and store the move */
		    for( i = 0; i < placed; i++ ) {
			j = map[i];
			if( tile[i] == 26 ) {
			    newlet[j].letter = CH_BL;
			    newlet[j].blankchar = tword[index[i]];
			} else {
			    newlet[j].letter = tword[index[i]];
			}
			newlet[j].tilepos = tilepos[i];
		    }
		    eval_rack_leave( used );
		    eval_score( placed, hooks + 1, dir );
		}
		stack--;
		continue;
	    }
	    if( tilepos[stack] == -1 ) {
		i = 0;	
		prevtile = -1;
	    } else if( tile[stack] != 26 || blank[stack] == 25 ) {
		i = tilepos[stack];
		prevtile = tile[stack];
		used[i] = 0;
		i++;
	    } else {
		blank[stack]++;
		i = -1;
	    }
	    if( i != -1 )
		while( ( used[i] != 0 || prevtile == tilev[i] )
		       && i < ntiles )
		    i++;
	    if( i == ntiles ) {
		tilepos[stack] = -1;
		tword[index[stack]] = '*';
		stack--;
	    } else {
		if( i != -1 ) {
		    tilepos[stack] = i;
		    tile[stack] = tilev[i];
		    used[i] = 1;
		    if( tilev[i] == 26 )
			blank[stack] = 0;
		}
		if( tile[stack] != 26 )
		    tword[index[stack]] = tile[stack] + 'A';
		else
		    tword[index[stack]] = blank[stack] + 'A';
		if( BinSearch( tword ) ) stack++;
	    }
	}
    }
    return( 0 );
}

void eval_rack_leave( used )
    int *used;
/* Evaluate rack leave given unused tiles. */
/* Please note: assumes tiles are _sorted_ on the rack! */
{
    int i, tf, tc;
    int vowel, cons;
    
    tc = 0;
    rms1 = 0;
    rms2 = 0;
    tf = -1;
    vowel = 0;
    cons = 0;
    nused = 0;
    for( i = 0; i < ntiles; i++ ) {
	if( used[i] ) {
	    nused++;
	    continue;
	}
	if( tilev[i] == tf ) {
	    tc++;
	} else {
	    if( tf != -1 ) {
		rms1 += RackLeave[tf][tc];
		rms2 -= 2 * Letters[tf].points * tc;
	    }
	    tf = tilev[i];
	    tc = 1;
	}
	if( tf == 0 || tf == 4 || tf == 8 || tf == 14 || tf == 20 )
	    vowel++;
	else if( tf != 26 ) cons++;
    }
    if( tf != -1 ) {
	rms1 = rms1 + RackLeave[tf][tc] + VCMix[vowel][cons] * 2;
	rms2 -= 2 * Letters[tf].points * tc;
    }
}

void eval_score( placed, w, dir )
    int placed, w, dir;
/* Calculate score for a play. */
/* Factor of two is because rack leaves are measured in 0.5 increments. */
{
    int xinc, yinc;
    int i, winout;
    int score, rmsused;
    compmove *newptr;
    
    xinc = 1 - dir;
    yinc = dir;
    i = FindNewWords( newlet, placed, xinc, yinc );
    score = 0; winout = 0;
    for( i = 0; i < w; i++ ) score += NewWords[i].score;
    score *= 2;
/* At EndGame, if we can use all our tiles and win, mark winout. */
    if( nused == ntiles && tiles_left_to_draw <= 14 ) {
	LPrint( "Me %d, they %d, ntiles=%d\n",
		 PlrScores[MyPlrNum], PlrScores[TheirPlrNum], ntiles );
	if( PlrScores[MyPlrNum] + score + 2 * theirrack > PlrScores[TheirPlrNum] ) {
	    score += 200;
	    winout = 1;
	}
    }
/* Use rms1 if not in endgame, rms2 if in endgame */
    if( tiles_left_to_draw > 14 )
	rmsused = rms1;
    else
	rmsused = rms2;
/* Add sgordon's heuristic for opening moves: 4 * (# tiles left on rack) */
    if( tiles_left_to_draw == 100 )
	rmsused += 8 * ( 7 - placed );
    score += rmsused;
    if( CHead == NULL || IgnoreSmaller == 0 ) goto alloc_cmove;
    if( placed == 7 ) goto alloc_cmove;
/* If IgnoreSmaller is 1 and this move scores less than the first move on the
   queue, don't bother remembering it */
    if( score < CHead->score ) return;
  alloc_cmove:
    newptr = (compmove *) malloc( CM_SIZE );
    if( newptr == NULL ) {
	LPrint( "*** Fatal error: no memory left in eval_score()" );
	ExitWindow();
	exit( 12 );
    }
    newptr->next = NULL;
    newptr->score = score;
    newptr->rms = rmsused;
    newptr->winout = winout;
    newptr->placed = placed;
    newptr->dir = dir;
    for( i = 0; i < placed; i++ ) {
	newptr->newlet[i].x = newlet[i].x;
	newptr->newlet[i].y = newlet[i].y;
	newptr->newlet[i].letter = newlet[i].letter;
	newptr->newlet[i].blankchar = newlet[i].blankchar;
	newptr->newlet[i].tilepos = newlet[i].tilepos;
    }
    add_to_move_list( newptr );
}