war.c

// -rw-r--r--@   1 ficus  1876110778      5344 Oct  8  2004 war.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>

typedef struct _card card;

#define min(a,b) ((a)<(b)?(a):(b))

#define PLUS_B 0

struct _card {
	int value;
	card *next;
};

typedef struct {
	card *top;
	card *bottom;
	int count;
} deck;

deck deck_a;
deck deck_b;
deck spoils;

#define SUIT_SHIFT 8
#define RANK_MASK 0xff

char card_names[] = { '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A' };
char suit_names[] = { 'c', 'd', 'h', 's' };

void
dump(deck *d)
{
	card *c;

	for (c = d->top; c != NULL; c = c->next) {
		printf("%c%c, ", card_names[(c->value & RANK_MASK)], suit_names[c->value >> SUIT_SHIFT]);
	}

	printf("\n");
}

void
_shuffle(int *values, int count)
{
	int i, ii;
	for (ii = 0; ii < 5; ii++) {
		for (i = 0; i < count; i++) {
			int s = values[i];
			int p = rand() % count;
			values[i] = values[p];
			values[p] = s;
		}
	}
}

void
shuffle(deck *d)
{
	int *ii = (int *)malloc(sizeof(int) * d->count);
	card *c;
	int i = 0;

	for (c = d->top; c != NULL; c = c->next) {
		ii[i++] = c->value;
	}

	_shuffle(ii, i);

	i = 0;
	for (c = d->top; c != NULL; c = c->next) {
		c->value = ii[i++];
	}
}

void
add_top(deck *d, int v)
{
	card *c = (card *)malloc(sizeof(card));
	c->value = v;
	c->next = d->top;
	d->top = c;
	if (d->bottom == NULL)
		d->bottom = c;

	d->count++;
}

void
add_bottom(deck *d, int v)
{
	card *c = (card *)malloc(sizeof(card));
	c->value = v;
	c->next = NULL;
	if (d->bottom != NULL) {
		d->bottom->next = c;
	}
	d->bottom = c;

	if (d->top == NULL)
		d->top = c;

	d->count++;
}

int
pick_top(deck *d)
{
	card *pick;
	int v;

	if (d->top == NULL)
		return -1;

	pick = d->top;
	d->top = d->top->next;
	if (d->top == NULL)
		d->bottom = NULL;


	v = pick->value;
	free(pick);
	d->count--;
	return v;
}

void
init_decks()
{
	int i, ii;
	int init[52];

	for (ii = 0; ii < 4; ii++) {
		for (i = 0; i < 13; i++) {
			init[(ii*13)+i] = i | (ii << SUIT_SHIFT);
		}
	}

	_shuffle(init, 52);

	deck_a.top = NULL;
	deck_b.top = NULL;
	deck_a.bottom = NULL;
	deck_b.bottom = NULL;
	deck_a.count = 0;
	deck_b.count = 0;

	for (i = 0; i < 26; i++) {
		add_top(&deck_a, init[i]);
	}

	for (i = 26; i < 52; i++) {
		add_top(&deck_b, init[i]);
	}
}

void
cleanup_decks()
{
	while (pick_top(&deck_a) != -1);
	while (pick_top(&deck_b) != -1);
	while (pick_top(&spoils) != -1);
}

void push_spoils(deck *d)
{
	int v;

	shuffle(&spoils);

	while ((v = pick_top(&spoils)) != -1)
		add_bottom(d, v);
}

int pop(deck *d)
{
	int v = pick_top(d);

	add_top(&spoils, v);

	return v;
}


#define A_WINS	1
#define B_WINS	2

#define pop_a() pop(&deck_a)
#define pop_b() pop(&deck_b)

int findstuck_orig[52];
int findstuck[52];

int
play1(int *_moves)
{
	int moves = 0;

	for (;;) {
		int a = pop(&deck_a);
		int b = pop(&deck_b)+PLUS_B;

		while (min(12, (a & RANK_MASK)) == min(12, (b & RANK_MASK))) {
			//printf("WAR\n");

			switch(deck_a.count) {
			default:
			case 4:
				a = pop_a();
			case 3:
				a = pop_a();
			case 2:
				a = pop_a();
			case 1:
				a = pop_a();
			case 0:
			}

			//printf("A (%d) risks: "); dump(&spoils);

			switch(deck_b.count) {
			default:
			case 4:
				b = pop_b()+PLUS_B;
			case 3:
				b = pop_b()+PLUS_B;
			case 2:
				b = pop_b()+PLUS_B;
			case 1:
				b = pop_b()+PLUS_B;
			case 0:
			}
			//printf("B (%d) risks: ", b); dump(&spoils);

		}

		if ((a & RANK_MASK) == 12 && (b & RANK_MASK) == 0) {
			push_spoils(&deck_b);
/*
		} else if ((a & RANK_MASK == 0 && (b & RANK_MASK) == 12) {
			push_spoils(&deck_a);
*/
		} else if (min(12, (a & RANK_MASK)) > min(12, (b & RANK_MASK))) {
			push_spoils(&deck_a);
		} else {
			push_spoils(&deck_b);
		}

		moves++;

#if 0
		if (++moves >= 10000) {
			if (moves == 10000) {
				card *c;
				int iii = 0;
				for (c = deck_a.top; c != NULL; c = c->next) {
					findstuck_orig[iii++] = c->value;
				}
				for (c = deck_b.top; c != NULL; c = c->next) {
					findstuck_orig[iii++] = c->value;
				}
				printf("A:"); dump(&deck_a);
				printf("B:"); dump(&deck_b);
			} else {
				card *c;
				int iii = 0;
				for (c = deck_a.top; c != NULL; c = c->next) {
					findstuck[iii++] = c->value;
				}
				for (c = deck_b.top; c != NULL; c = c->next) {
					findstuck[iii++] = c->value;
				}
				if (memcmp(findstuck, findstuck_orig, sizeof(findstuck)) == 0) {
					printf("LOOP at 10000 and %d!\n", moves);
					printf("A:"); dump(&deck_a);
					printf("B:"); dump(&deck_b);
					exit(1);
				}
			}
		}
#endif

		if (deck_a.count == 0) {
			//printf("A wins\n");
			*_moves = moves;
			return A_WINS;
		} else if (deck_b.count == 0) {
			//printf("B wins\n");
			*_moves = moves;
			return B_WINS;
		}
	}
}

int
main()
{
	int a_wins = 0, b_wins = 0, total = 0;
	struct timeval tv;
	int moves;
	long long move_log = 0;

	gettimeofday(&tv, 0);
	srand(tv.tv_sec * tv.tv_usec);


	while (1) {
		int result;

		init_decks();
		result = play1(&moves);
		cleanup_decks();
		if (result == A_WINS) {
//printf("A wins in %d moves\n", moves);
			a_wins++;
		} else {
//printf("B wins in %d moves\n", moves);
			b_wins++;
		}

		total++;
		move_log += moves;

		if ((total % 1000) == 0) {
			printf("a: %d (%.2f%%), b: %d (%.2f%%) (avg moves %.2f)\n",
				a_wins, ((double)a_wins) / (double)total,
				b_wins, ((double)b_wins) / (double)total,
				(double)move_log / (double)total);
		}
	}

	return 0;
}