/*	$NetBSD: makemove.c,v 1.43 2022/06/19 10:23:48 rillig Exp $	*/

/*
 * Copyright (c) 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Ralph Campbell.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/cdefs.h>
/*	@(#)makemove.c	8.2 (Berkeley) 5/3/95	*/
__RCSID("$NetBSD: makemove.c,v 1.43 2022/06/19 10:23:48 rillig Exp $");

#include "gomoku.h"

const int     dd[4] = {		/* direction deltas */
	1,			/* right */
	-(BSZ + 1) + 1,		/* down + right */
	-(BSZ + 1),		/* down */
	-(BSZ + 1) - 1		/* down + left */
};

static const int weight[5] = { 0, 1, 7, 22, 100 };

static void update_overlap(spot_index);

static bool
is_tie(void)
{

	for (int y = 1; y <= BSZ; y++)
		for (int x = 1; x <= BSZ; x++)
			if (board[PT(x, y)].s_wval != 0)
				return false;
	return true;
}

static void
sortframes_remove(struct combostr *cbp)
{

	if (cbp->c_next == NULL)
		return;

	if (sortframes[BLACK] == cbp)
		sortframes[BLACK] = cbp->c_next;
	if (sortframes[WHITE] == cbp)
		sortframes[WHITE] = cbp->c_next;
	cbp->c_next->c_prev = cbp->c_prev;
	cbp->c_prev->c_next = cbp->c_next;
}

static int
old_weight_value(const struct spotstr *sp, direction r)
{
	union comboval cb;
	int val = 0;
	if ((cb = sp->s_fval[BLACK][r]).s <= 0x500)
		val += weight[5 - cb.cv_force - cb.cv_win];
	if ((cb = sp->s_fval[WHITE][r]).s <= 0x500)
		val += weight[5 - cb.cv_force - cb.cv_win];
	return val;
}

/*
 * Return values:
 *	MOVEOK	everything is OK.
 *	RESIGN	Player resigned.
 *	ILLEGAL	Illegal move.
 *	WIN	The winning move was just played.
 *	TIE	The game is a tie.
 */
int
makemove(player_color us, spot_index mv)
{

	/* check for end of game */
	if (mv == RESIGN)
		return RESIGN;

	/* check for illegal move */
	struct spotstr *sp = &board[mv];
	if (sp->s_occ != EMPTY)
		return ILLEGAL;

	/* make move */
	sp->s_occ = us;
	game.moves[game.nmoves++] = mv;

	/* compute new frame values */
	sp->s_wval = 0;
	for (direction r = 4; r-- > 0; ) {
	    int d = dd[r];
	    struct spotstr *fsp = &board[mv];

	    for (int f = 5; --f >= 0; fsp -= d) {	/* for each frame */
		if (fsp->s_occ == BORDER)
		    goto nextr;
		if (is_blocked(fsp, r))
		    continue;

		struct combostr *cbp = &frames[fsp->s_frame[r]];
		sortframes_remove(cbp);

		int val = old_weight_value(fsp, r);

		/* compute new combo value for this frame */
		bool space = fsp->s_occ == EMPTY;
		int n = 0;
		sp = fsp;
		for (int off = 5; off-- > 0; sp += d) {	/* for each spot */
		    if (sp->s_occ == us)
			n++;
		    else if (sp->s_occ == EMPTY)
			sp->s_wval -= val;
		    else {
			set_blocked(fsp, r);
			/* adjust values */
			fsp->s_fval[BLACK][r].s = 0x600;
			fsp->s_fval[WHITE][r].s = 0x600;
			while (off-- > 0) {
			    sp += d;
			    if (sp->s_occ == EMPTY)
				sp->s_wval -= val;
			}
			goto nextf;
		    }
		}

		/* check for game over */
		if (n == 5) {
		    game.win_spot = (spot_index)(fsp - board);
		    game.win_dir = r;
		    return WIN;
		}

		/* compute new value & combo number for this frame & color */
		player_color them = us != BLACK ? BLACK : WHITE;
		fsp->s_fval[them][r].s = 0x600;
		union comboval *cp = &fsp->s_fval[us][r];
		/* both ends open? */
		if (space && sp->s_occ == EMPTY) {
		    cp->cv_force = 4 - n;
		    cp->cv_win = 1;
		} else {
		    cp->cv_force = 5 - n;
		    cp->cv_win = 0;
		}
		val = weight[n];
		sp = fsp;
		for (int off = 5; off-- > 0; sp += d)	/* for each spot */
		    if (sp->s_occ == EMPTY)
			sp->s_wval += val;

		/* add this frame to the sorted list of frames by combo value */
		struct combostr *cbp1 = sortframes[us];
		if (cbp1 == NULL)
		    sortframes[us] = cbp->c_next = cbp->c_prev = cbp;
		else {
		    union comboval *cp1 =
			&board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
		    if (cp->s <= cp1->s) {
			/* insert at the head of the list */
			sortframes[us] = cbp;
		    } else {
			do {
			    cbp1 = cbp1->c_next;
			    cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
			    if (cp->s <= cp1->s)
				break;
			} while (cbp1 != sortframes[us]);
		    }
		    cbp->c_next = cbp1;
		    cbp->c_prev = cbp1->c_prev;
		    cbp1->c_prev->c_next = cbp;
		    cbp1->c_prev = cbp;
		}

	    nextf:
		;
	    }

	    /* both ends open? */
	    if (fsp->s_occ == EMPTY) {
		union comboval *cp = &fsp->s_fval[BLACK][r];
		if (cp->cv_win != 0) {
		    cp->cv_force++;
		    cp->cv_win = 0;
		}
		cp = &fsp->s_fval[WHITE][r];
		if (cp->cv_win != 0) {
		    cp->cv_force++;
		    cp->cv_win = 0;
		}
	    }

	nextr:
	    ;
	}

	update_overlap(mv);

	if (is_tie())
		return TIE;

	return MOVEOK;
}

static void
update_overlap_same_direction(spot_index s1, spot_index s2,
			      frame_index a, int d, int off_minus_f,
			      direction r)
{
	/*
	 * count the number of empty spots to see if there is
	 * still an overlap.
	 */
	int n = 0;
	spot_index s = s1;
	spot_index es = 0;
	for (int b = off_minus_f; b < 5; b++, s += d) {
		if (board[s].s_occ == EMPTY) {
			es = s;	/* save the intersection point */
			n++;
		}
	}

	frame_index b = board[s2].s_frame[r];
	if (n == 0) {
		if (board[s].s_occ == EMPTY) {
			overlap[a * FAREA + b] &= 0xA;
			overlap[b * FAREA + a] &= 0xC;
			intersect[a * FAREA + b] = s;
			intersect[b * FAREA + a] = s;
		} else {
			overlap[a * FAREA + b] = 0;
			overlap[b * FAREA + a] = 0;
		}
	} else if (n == 1) {
		if (board[s].s_occ == EMPTY) {
			overlap[a * FAREA + b] &= 0xAF;
			overlap[b * FAREA + a] &= 0xCF;
		} else {
			overlap[a * FAREA + b] &= 0xF;
			overlap[b * FAREA + a] &= 0xF;
		}
		intersect[a * FAREA + b] = es;
		intersect[b * FAREA + a] = es;
	}
	/* else no change, still multiple overlap */
}

/*
 * The last move was at 'os', which is part of frame 'a'. There are 6 frames
 * with direction 'rb' that cross frame 'a' in 'os'. Since the spot 'os'
 * cannot be used as a double threat anymore, mark each of these crossing
 * frames as non-overlapping with frame 'a'.
 */
static void
update_overlap_different_direction(spot_index os, frame_index a, direction rb)
{

	int db = dd[rb];
	for (int off = 0; off < 6; off++) {
		const struct spotstr *sp = &board[os - db * off];
		if (sp->s_occ == BORDER)
			break;
		if (is_blocked(sp, rb))
			continue;

		frame_index b = sp->s_frame[rb];
		overlap[a * FAREA + b] = 0;
		overlap[b * FAREA + a] = 0;
	}
}

/*
 * fix up the overlap array according to the changed 'os'.
 */
static void
update_overlap(spot_index os)
{

	for (direction r = 4; r-- > 0; ) {
	    int d = dd[r];
	    spot_index s1 = os;

	    /* for each frame 'a' that contains the spot 'os' */
	    for (int f = 0; f < 6; f++, s1 -= d) {
		if (board[s1].s_occ == BORDER)
		    break;
		if (is_blocked(&board[s1], r))
		    continue;

		/*
		 * Update all other frames that intersect the current one
		 * to indicate whether they still overlap or not.
		 * Since F1 overlap F2 == F2 overlap F1, we only need to
		 * do the rows 0 <= r1 <= r. The r1 == r case is special
		 * since the two frames can overlap in more than one spot.
		 */
		frame_index a = board[s1].s_frame[r];

		spot_index s2 = s1 - d;
		for (int off = f + 1; off < 6; off++, s2 -= d) {
		    if (board[s2].s_occ == BORDER)
			break;
		    if (is_blocked(&board[s2], r))
			continue;

		    update_overlap_same_direction(s1, s2, a, d, off - f, r);
		}

		/* the other directions can only intersect at spot 'os' */
		for (direction rb = 0; rb < r; rb++)
			update_overlap_different_direction(os, a, rb);
	    }
	}
}