Simulate connect 4

conn4.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#include <assert.h>

#define ENABLE_MOVE_COUNTER

struct game {
	uint8_t col[2][7];
	int p;
	int num_moves;
};

void
setup(struct game *g)
{
	for (int i = 0; i < 7; ++i) {
		g->col[0][i] = 1 << 6;
		g->col[1][i] = 1 << 6;
	}
	g->p = 0;
#ifdef ENABLE_MOVE_COUNTER
	g->num_moves = 0;
#endif
}

int
is_valid_move(const struct game *g, int n)
{
	return !((g->col[0][n] | g->col[1][n]) & 1);
}

void
move(struct game *g, int n)
{
	assert(n >= 0);
	assert(n < 7);
	uint8_t m = g->col[0][n] | g->col[1][n];
	g->col[g->p][n] |= (m & (uint8_t)(-m)) >> 1;
	g->p ^= 1;
#ifdef ENABLE_MOVE_COUNTER
	g->num_moves++;
#endif
}

int
result(const struct game *g)
{
	for (int p = 0; p < 2; ++p) {
		int r = 0;
		const uint8_t *x = g->col[p];

		/* Horizontal wins */
		for (uint8_t m = 1; m < (1 << 6); m <<= 1) {
			for (int i = 0; i < 4; ++i) {
				r |= (x[i + 0] & m) &
				     (x[i + 1] & m) &
				     (x[i + 2] & m) &
				     (x[i + 3] & m);
			}
		}

		/* Vertical wins */
		for (int j = 0; j < 3; ++j) {
			for (int i = 0; i < 7; ++i) {
				r |= ((x[i] >> j) & 15) == 15;
			}
		}

		/* Diagonal wins */
		for (int j = 0; j < 3; ++j) {
			for (int i = 0; i < 4; ++i) {
				r |= ((x[i + 0] >> (j + 0)) & 1)
				   & ((x[i + 1] >> (j + 1)) & 1)
				   & ((x[i + 2] >> (j + 2)) & 1)
				   & ((x[i + 3] >> (j + 3)) & 1);
				r |= ((x[i + 0] >> (j + 3)) & 1)
				   & ((x[i + 1] >> (j + 2)) & 1)
				   & ((x[i + 2] >> (j + 1)) & 1)
				   & ((x[i + 3] >> (j + 0)) & 1);
			}
		}

		if (r) {
			return p ? -1 : 1;
		}
	}
	return 0;
}

void
draw(struct game *g)
{
	puts("/+-+-+-+-+-+-+-+\\");
	for (uint8_t m = 1; m < (1 << 6); m <<= 1) {
		putchar('|');
		for (int i = 0; i < 7; ++i) {
			putchar(' ');
			if (g->col[0][i] & m) {
				putchar('X');
			} else if (g->col[1][i] & m) {
				putchar('O');
			} else {
				putchar(' ');
			}
		}
		puts(" |");
	}
	puts("|+-+-+-+-+-+-+-+|");
	puts("| A B C D E F G |");
}

int
play_random(struct game *g)
{
	for (;;) {
		int i;
		for (i = 0; i < 7; ++i) {
			if (is_valid_move(g, i))
				break;
		}
		if (i == 7)
			return 0;
		/* Warning: not uniformly random */
		for (i = rand() % 7; ; (i = (i + 1) % 7)) {
			if (is_valid_move(g, i))
				break;
		}
		move(g, i);

		int r = result(g);
		if (r)
			return r;
	}
}

void
search(void)
{
	struct game gs[6 * 7];
	int n = 0;
	setup(&gs[0]);

	for (;;) {
		setup(&gs[n]);
	}
}

void
mean_moves(int n_games)
{
	int n;
	struct game g;

	long long move_count = 0;
	long long scores[3] = {0};

	srand(1);

	for (n = 0; n < n_games; ++n) {
		setup(&g);
		scores[play_random(&g) + 1]++;
		move_count += g.num_moves;
	}
	printf("Averaged %lld moves in %d games\n", move_count / n, n);
	printf("O won %lld/%d = %%%0.1f\n",
			scores[0], n, 100.0 * (double)scores[0]/n);
	printf("X won %lld/%d = %%%0.1f\n",
			scores[2], n, 100.0 * (double)scores[2]/n);
	printf("Draw %lld/%d = %%%0.1f\n",
			scores[1], n, 100.0 * (double)scores[1]/n);
}

int
main(int argc, const char *argv[])
{
	int n;
	int r;
	struct game g;

	srand(1);

	int n_to_log = argc >= 2 ? atoi(argv[1]) : 1;
	int n_to_analyse = argc >= 3 ? atoi(argv[2]) : 0;

	for (n = 0; n < n_to_log; ++n) {
		const char *msg[] = {"O", "Nobody", "X"};
		setup(&g);
		r = play_random(&g);
		draw(&g);
		printf("%s wins in %d moves\n\n", msg[r + 1], g.num_moves);
	}

	if (n_to_analyse > 0)
		mean_moves(n_to_analyse);

	return 0;
}

Plays ~380K games per second