abstract-game.c

/* https://www.reddit.com/r/abstractgames/comments/6dklih/ */
#include <stdio.h>
#include <stdlib.h>

/*
 * The game is played on a board like this, every player has three
 * pieces named a, b, and c.  The player to play first (blue) has
 * uppercase pieces, the other player has lowercase pieces.  This is
 * the initial setup:
 *
 *
 *   +-+-+-+
 *   |B| |C|
 * +-+-+-+-+-+
 * |A| | | |a|
 * +-+-+-+-+-+
 *   |c| |b|
 *   +-+-+-+
 *
 * The game is won when a player arranges his pieces in a vertical,
 * horizontal, or diagonal line.  The following moves exist:
 *
 *  - move one of your pieces to a vertically or horizontally adjacent
 *    spot.
 *  - swap the two pieces named B and b.
 *
 * ---
 *
 * This program can be run with either zero arguments or six of them.  A
 * position can be provided using the following square numbers, if no
 * position is provided, the initial setup is used:
 *
 *    +--+--+--+
 *    | 0| 1| 2|
 * +--+--+--+--+--+
 * | 3| 4| 5| 6| 7|
 * +--+--+--+--+--+
 *    | 8| 9|10|
 *    +--+--+--+
 *
 * Then the program solves the game and prints the evaluation for blue
 * to play.  A positive number indicates that blue can win in the given
 * number of moves.  A negative number indicates that red can win in the
 * given number of moves minus one, if red already has a combination on
 * the board, the value is -1.  Zero indicates a draw.
 */
struct gamestate {
	char a, b, c, A, B, C;
};

/*
 * The board is implemented as a 7x5 array of squares with the border
 * squares being off limit.  This way, we can easily implement
 * out-of-bounds checks.  This table maps board coordinates to square
 * numbers, out of bounds squares are numbered -1.
 */
char sqnum[35] = {
	-1, -1, -1, -1, -1, -1, -1,
	-1, -1,  0,  1,  2, -1, -1,
	-1,  3,  4,  5,  6,  7, -1,
	-1, -1,  8,  9, 10, -1, -1,
	-1, -1, -1, -1, -1, -1, -1
};

/* this table maps square numbers to board coordinates. */
char sqcoord[11] = {
	 9, 10, 11,
	15, 16, 16, 18, 19,
	23, 24, 25,
};

/* return zero if two pieces occupy the same square, otherwise return
 * an occupation map */
static int
occupation(struct gamestate *gs)
{
	int overlap = 1 << gs->a;

	if (1 << gs->b & overlap) return (0);
	overlap |= 1 << gs->b;
	if (1 << gs->c & overlap) return (0);
	overlap |= 1 << gs->c;
	if (1 << gs->A & overlap) return (0);
	overlap |= 1 << gs->A;
	if (1 << gs->B & overlap) return (0);
	overlap |= 1 << gs->B;
	if (1 << gs->C & overlap) return (0);
	overlap |= 1 << gs->C;

	return (overlap);
}

/* this table contains a bitmap of all winning combinations */
short wins[10] = {
	1792, /* 111 00000 000 */
	 224, /* 000 11100 000 */
	 112, /* 000 01110 000 */
	  56, /* 000 00111 000 */
	  15, /* 000 00000 111 */

	1092, /* 100 01000 100 */
	 546, /* 010 00100 010 */
	 273, /* 001 00010 001 */

	1057, /* 100 00100 001 */
	 292, /* 001 00100 100 */
};

/* return nonzero if the bitmap is one of the winning combinations */
static int
winning_bitmap(int m)
{
	size_t i;

	for (i = 0; i < 10; i++)
		if (wins[i] == m)
			return (1);

	return (0);
}

/* return nonzero if red has a winning combination on the board */
static int
red_wins(struct gamestate *gs)
{

	return (winning_bitmap(1 << gs->a | 1 << gs->b | 1 << gs->c));
}

/*
 * The endgame table we compute. Each entry is a position with blue to
 * move.  An entry is...
 *
 *  - positive if the position is won for blue, the magnitude is the
 *    distance to mate.
 *  - negative if the position is lost for blue, the magnitude is again
 *    the distance to mate.
 *  - zero if it hasn't been computed yet.
 */
static short egtable[11*11*11*11*11*11];

/* compute an index into the endgame table */
static int
index(struct gamestate *gs)
{

	return (gs->A + 11 * (gs->B + 11 * (gs->C + 11 * (gs->a + 11 * (gs->b + 11 * gs->c)))));
}

/* compute an index into the endgame table with swapped pieces*/
static int
swindex(struct gamestate *gs)
{

	return (gs->a + 11 * (gs->b + 11 * (gs->c + 11 * (gs->A + 11 * (gs->B + 11 * gs->C)))));
}

/* return the worse of two endgame table entries */
static int
worse(int a, int b)
{
	if (a > 0)
		return (b <= 0 || b > a ? b : a);
	else if (a == 0)
		return (b <= 0 ? b : a);
	else
		return (b < 0 && b > a ? b : a);
}

/* mark all immediately winning combinations and all invalid
 * combinations with 1 */
static void
first_round(void)
{
	int count = 0;
	struct gamestate gs;

	for (gs.A = 0; gs.A < 11; gs.A++)
	for (gs.B = 0; gs.B < 11; gs.B++)
	for (gs.C = 0; gs.C < 11; gs.C++)
	for (gs.a = 0; gs.a < 11; gs.a++)
	for (gs.b = 0; gs.b < 11; gs.b++)
	for (gs.c = 0; gs.c < 11; gs.c++) {
		if (occupation(&gs) == 0 || red_wins(&gs)) {
			egtable[index(&gs)] = -1;
			count++;
		}
	}

	printf("round  -1: %7d\n", count);
}


/*
 * pc is a pointer to a member of gs, oc is the occupation map of gs.
 * Find the position with the worst evaluation we can move to when
 * moving piece pc.
 */
static int
one_piece(char *pc, struct gamestate *gs, int oc)
{
	/* all the offsets we can apply */
	static const char offsets[4] = { -7, -1, 1, 7 };

	int i, worst = 1, opc = *pc;

	for (i = 0; i < 4; i++) {
		*pc = sqnum[sqcoord[opc] + offsets[i]];
		if (*pc == -1 || oc & 1 << *pc)
			continue;

		worst = worse(worst, egtable[swindex(gs)]);
	}

	*pc = opc;

	return (worst);
}

/*
 * check all possible moves for one gamestate and return the worst
 * position we can reach (i.e. the position we can reach using our
 * best move).
 */
static int
one_position(struct gamestate *gs)
{
	int worst, oc = occupation(gs), b, B;

	if (oc == 0)
		return (1);

	/* regular moves */
	worst = one_piece(&gs->A, gs, oc);
	worst = worse(worst, one_piece(&gs->B, gs, oc));
	worst = worse(worst, one_piece(&gs->C, gs, oc));

	/* swap b and B */
	b = gs->b;
	B = gs->B;
	gs->B = b;
	gs->b = B;

	worst = worse(worst, egtable[swindex(gs)]);
	gs->b = b;
	gs->B = B;

	return (worst);
}

/*
 * Iterate through the endgame table, if any position's worst move
 * leads to prev, set its its entry to round.  Return the number of
 * updates made.
 */
static int
one_round(int prev, int round)
{
	struct gamestate gs;
	int count = 0;

	for (gs.A = 0; gs.A < 11; gs.A++)
	for (gs.B = 0; gs.B < 11; gs.B++)
	for (gs.C = 0; gs.C < 11; gs.C++)
	for (gs.a = 0; gs.a < 11; gs.a++)
	for (gs.b = 0; gs.b < 11; gs.b++)
	for (gs.c = 0; gs.c < 11; gs.c++) {
		int idx = index(&gs);

		/* ignore positions that have already a value assigned */
		if (egtable[idx] != 0)
			continue;		

		if (one_position(&gs) == prev) {
			egtable[idx] = round;
			count++;
		}
	}

	printf("round %3d: %7d\n", round, count);

	return (count);
}

/* print number of wins, draws, and losses */
static void
statistics(void)
{
	int wins = 0, draws = 0, losses = 0, i;

	for (i = 0; i < 11 * 11 * 11 * 11 * 11 * 11; i++)
		if (egtable[i] > 0)
			wins++;
		else if (egtable[i] < 0)
			losses++;
		else
			draws++;

	printf("wins:      %7d\n", wins);
	printf("draws:     %7d\n", draws);
	printf("losses:    %7d\n", losses);
}

/* fill endgame table with values until all rounds are done */
static void
fill_egtable(void)
{
	int round;

	first_round();

	for (round = 1; ; round++) {
		if (one_round(-round, round) == 0)
			break;
		if (one_round(round, -round -1) == 0)
			break;
	}

	statistics();
}

int main(int argc, char *argv[])
{
	struct gamestate start = { 3, 0, 2, 7, 10, 8 };

	if (argc == 7) {
		start.A = atoi(argv[1]);
		start.B = atoi(argv[2]);
		start.C = atoi(argv[3]);
		start.a = atoi(argv[4]);
		start.b = atoi(argv[5]);
		start.c = atoi(argv[6]);
	}

	fill_egtable();

	printf("start: %d\n", egtable[index(&start)]);
}