canfield_jw.c

/* Copyright 2014 Jan Wolter */
#include "stack.h"
#include "tableau.h"
#include "found.h"
#include "bouquet.h"
#include "solve.h"
#include "game.h"

char *gamename= "Canfield";
char *gameopt= "OF";
Stack *gathered= NULL;
Stack *temp= NULL;

int reservei;

int nplayed= 0;
int nwon= 0;
int nabandoned= 0;
int cardsleft= 0;
int maxoff;
int baserank;

int dealchunk= 3;
int autofill= 1;

void setopt(char c)
{
    switch (c)
    {
	case 'O': dealchunk= 1; break;  /* Deal one-by-one, infinite redeals */
	case 'F': autofill= 0; break;  /* Turn off autofills */
    }
}

/* Given the pip value of a card, what is it's foundation rank, where the
 * basecard's baserank is 0, the next card is 1, and so on.
 */
int basepip(int n)
{
    return (n - baserank + npip)%npip;
}


/* This is the main program for setting up the current game */
void exec(int gather, int arif, int over, int cut)
{

    /* Could set things like ndeck, nsuit here */

    /* Shuffle the deck */
    Stack *shuf= mixcards(arif, over, cut);

    /* The first card will be the base card for our foundations */
    Card *basecard= popStack(shuf);
    baserank= basecard->n;

    /* Create the foundations */
    superfound= sf_constbase;
    for (int s= 0; s < nsuit; s++)
    {
	makeFound(baserank, s, +1, 13);
	/* If the suit of this foundation matches our basecard put it on */
	if (s == basecard->s)
	    pushStack(stacks+foundation[nfound-1].id, basecard);
    }

    /* Create the reserve - part of the tableau really */
    makeTableau(13, FLIP_ALL, shuf, S_NONE, 0, S_NONE, 0, 0, F_NONE, BREAK_ANYWHERE, 0);
    reservei= ntableau-1;

    /* Create the tableau */
    for (int i= 1; i <= 4; i++)
	makeTableau(1, FLIP_NONE, shuf,
	    S_DIFFCOLOR, -1, S_DIFFCOLOR, -1, baserank, F_ANYTHING, 0, reservei+1);

    /* Create the stock/waste - really a bouquet with chunksize 3 */
    makeBouquet(shuf, dealchunk, 1);

    freeStack(shuf);

    /* Print initial state */
    if (verbose > 1) printState(stdout, stacks);

    maxoff= 0;
    int win= solve(gather,0);

    if (verbose > 0) printf("maxoff=%d\n",maxoff);
    nplayed++;
    cardsleft+= maxoff;
    if (win == 1)
	nwon++;
    else if (win == 2)
	nabandoned++;

    cleanFound();
    cleanTableau();
    cleanBouquet();
    cleanStacks();
    cleanVisited();
}

/* Gather up the cards into the global 'gathered' stack. This has to be
 * non-destructive, since we may not be done solving when it is called.
 */
void gatherAll()
{
    if (gathered == NULL)
	gathered= allocStack(ncard);
    else
	gathered->n= 0;

    gatherFound(gathered);
    gatherTableau(gathered);
    gatherBouquet(gathered);
    if (gathered->n != ncard)
    {
	printf("Gather Failed - found %d cards\n",gathered->n);
	exit(1);
    }
}

/* How good is a move?
 *
 * Returns 0 if the move is completely safe or manditory. Such moves will not
 * be marked as choice points for backtracking.
 *
 * For other moves, positive values are returned with lower values for better
 * moves.
 *
 * Negative values mean the move should not be done at all.
 *
 * So for Canfield:
 *
 *   0 = Actual safe moves to foundation that don't mess up bouquet,
 *       and auto fills of tableau spaces from reserve.
 *   1 = moves from reserve to tableau, except last card in reserve.
 *       moves that empty a tableau pile.
 *   2-10 = moves from waste that build toward connecting tableau piles or
 *          lifting reserve pile. Rating is 1 + distance from moved card toward
 *          card we are building toward.
 *   2-10 = moves to foundation that build toward lifting top card of reserve
 *          or bottom card of a tableau pile.
 *   20 = moves from mid-waste to safe foundation spaces
 *   21 = moves to unsafe foundation spaces
 *   22 = tableau to tableau moves that open no empty spaces, but expose a card
 *        that could be moved to the foundation.
 *   23 = moves from waste to tableau that build toward nothing
 *   -1 = tableau to tableau moves that open no empty spaces and don't expose
 *        any card that could be moved to the foundation.
 */
int rateMove(Stack *src, int index1, int len, Stack *dst)
{
    Card *mc= src->c[index1];

    if (dst->type == FOUND)
    {
	FoundStack *f= foundation + dst->tid;
	/* Moving Aces and Twos to the foundation is generally safish, except
	 * that they aren't necessarily aces and two in Canfield. */
	int safe= (mc->n == f->baserank || mc->n == (f->baserank%npip) + 1);
	if (!safe)
	{
	    /* Find the two foundation stacks with different colors */
	    /* Here we assume suitcolor[] contains alternate ones and zeros */
	    int f1= (dst->tid + 1)%nsuit;
	    int f2= (dst->tid + 3)%nsuit;
	    /* We want to make sure our pile doesn't get more than two cards
	     * ahead of the piles of the opposite suit.
	     */
	    int safe= (dst->n - 1 <= stacks[f1].n &&
	               dst->n - 1 <= stacks[f2].n);
	}
	/* Actually, these "safe" moves aren't really safe if the card comes
	 * from the middle of the Bouquet, because then it might mess up
	 * accessibility of other cards we need. If it is from a tableau pile
	 * or if it is one of the last two cards on the bouquet, then it is
	 * really safe. Still, any "safe" foundation move is a good thing to
	 * try.
	 */
	int bestrc;
	if (safe)
	{
	    if  (dealchunk == 1 || src->type != BOUQUET || index1 >= src->n - 2)
		return 0;
	    bestrc= 20;
	}
	else
	    bestrc= 21;
	/* Now we are left with unsafe foundation moves. This are high priority
	 * if they build toward lifting the top reserve pile or an only card on
	 * a tableau, otherwise they are low priority.
	 */
	int mn= basepip(mc->n);
	for (int k= 0; k < ntableau; k++)
	{
	    /* Skip empty stacks */
	    if (stacks[tableau[k].id].n == 0 ||
	        (k != reservei && stacks[tableau[k].id].n != 1)) continue;

	    Card *gc;
	    if (k == reservei)
		/* For Reserve, want to build to top card */
		gc= topStack(stacks + tableau[k].id);
	    else
		/* For Tableau, want to build to bottom card */
		gc= stacks[tableau[k].id].c[0];
	    /* This is a possible target to build to if it is the same
	     * suit and of lower rank */
	    int gn= basepip(gc->n);
	    if (gn > mn && gc->s == mc->s)
	    {
		int rc= gn - mn + 1;
		if (rc < bestrc) bestrc= rc;
	    }
	}
	return bestrc;
    }
    else
    {
	/* Moving to tableau */
	if (src->type == TABLEAU)
	{
	    if (src->tid == reservei)
	    {
		/* Moving from reserve */

		/* Moving a reserve card into an empty space is not only safe,
		 * it's manditory.
		 */
		if (dst->n == 0 && autofill) return 0;
		/* Generally moving cards out of the reserve is a very high
		 * priority, except that there is no particular rush to remove
		 * the last one.
		 */
		if (src->n > 1) return 1;

		/* otherwise drop through */
	    }
	    else
	    {
		/* Moving from another tableau pile */

		/* If this move empties a tableau pile, even if the reserve is
		 * already empty, then it is a fine idea.
		 */
		if (index1 == 0) return 1;

		/* Other tableau to tableau moves must necessarily be breaking
		 * up an already built sequence.  These moves are useful only
		 * if they expose a card that can be moved to a foundation
		 * pile. Don't even consider them otherwise.
		 */
		Card *expcard= src->c[index1 - 1];
		for (int k= 0; k < nfound; k++)
		    if (found_mayInsert(stacks+foundation[k].id,expcard,1,src))
			    return 22;
		return -1;
	    }
	}
	/* Here we are moving either a waste card or the last reserve card
	 * to the tableau. This is more useful if it builds toward joining
	 * two tableau piles, or lifting the top reserve card.
	 */
	int bestrc= 23; /* return code for building toward nothing */

	/* All cards fit either in red-odd sequences or black-odd sequences.
	 * Where does this one fit? */
	int blackodd= (mc->n + suitcolor[mc->s]) % 2;

	/* Loop through the tableaus and reserve, looking for things we might
	 * be building toward
	 */
	int mn= basepip(mc->n);
	for (int k= 0; k < ntableau; k++)
	{
	    /* Skip empty stacks */
	    if (stacks[tableau[k].id].n == 0) continue;

	    Card *gc;
	    if (k == reservei)
		/* For Reserve, want to build to top card */
		gc= topStack(stacks + tableau[k].id);
	    else
		/* For Tableau, want to build to bottom card */
		gc= stacks[tableau[k].id].c[0];
	    /* This is a possible target to build to if it is also
	     * red-odd/black-odd and if it has a lower pip value than
	     * the moved card.  */
	    int gn= basepip(gc->n);
	    if (gn < mn && blackodd == (gc->n + suitcolor[gc->s]) % 2)
	    {
		int rc= mn - gn + 1;
		if (rc < bestrc) bestrc= rc;
	    }
	}
	return bestrc;
    }
}

void printState(FILE *f, Stack *stks)
{
    printFound(f, stks);
    printTableau(f, stks);
    printBouquet(f, stks);
}

int victory()
{
    int off= nOff();
    if (off > maxoff) maxoff= off;
    return (off == ncard);
}

/* Return a quality rating for the current solution. Bigger is better. Usually
 * it's just cards off. This is used to decide which solution to report in
 * cases where we never win.
 */
int quality()
{
    return nOff();
}

void summary()
{
    printf("Played:    %d games\n",nplayed);
    printf("Won:       %d games (%.2f%)\n",nwon,(float)nwon*100/nplayed);
    printf("Abandoned: %d games (%.2f%)\n",nabandoned,(float)nabandoned*100/nplayed);
    printf("Cards Off: %.2f\n",(float)cardsleft/nplayed);
}

/* Return a string that uniquely describes the current state. */
char *currstate()
{
    /* ncards for all the cards on things, 4 for tableaus, 1 for reserve,
     * 4 for list terminators.
     */
    char buf[ncard+20], *p= buf;

    /* Numbers of cards in each foundation pile */
    /* We add one to each count because we don't want any zeros */
    for (int k= 0; k < nfound; k++)
	*(p++)= stacks[foundation[k].id].n + 1;

    /* Count of cards on the reserve */
    *(p++)= stacks[tableau[reservei].id].n + 1;

    /* List of cards on each tableau pile - probably we should normalize
     * the order of tableau piles, sorting them by the first card on them,
     * but that is unlikely to be a bit deal in Canfield. Also the flippedness
     * of cards may need to matter, but again, that doesn't matter in Canfield.
     */
    for (int k= 0; k < ntableau; k++)
    {
	if (k == reservei) continue;
	Stack *s= stacks + tableau[k].id;
	for (int i= 0; i < s->n; i++)
	    *(p++)= (s->c[i] - deck) + 1;
	*(p++)= ncard + 1; /* The card list terminator */
    }

    /* List of cards on bouquet */

    /* We don't need this. For any given deal, the other state variables
     * give us enough information to tell what cards are in the bouquet, and
     * their order never changes, so this is redundant.
    Stack *bs= stacks + bouquet[0].id;
    for (int i= 0; i < bs->n; i++)
	*(p++)= (bs->c[i] - deck) + 1;
    */

    /* We do need to know the top card of the bouquet though, as different
     * values mean different cards are playable.
     */

    *(p++)= bouquet[0].top;

    *p= '\0';

    return strdup(buf);
}